arxiv: 2605.03023 · v1 · submitted 2026-05-04 · 🪐 quant-ph

Recognition: 3 theorem links

· Lean Theorem

Arts & crafts: Strong random unitaries and geometric locality

Marten Folkertsma , Lorenzo Grevink , Jonas Helsen , Alicja Dutkiewicz

Authors on Pith no claims yet

Pith reviewed 2026-05-08 19:17 UTC · model grok-4.3

classification 🪐 quant-ph

keywords unitary k-designsgeometric localityquantum gridspseudorandom unitariescircuit depthD-dimensional latticesapproximate designsrouting in quantum circuits

0 comments

The pith

Strong approximate unitary k-designs on D-dimensional grids can be achieved with provably optimal depth.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper develops constructions for strong approximate unitary k-designs tailored to D-dimensional grid connectivities in quantum systems. It offers a flexible approach that routes from known all-to-all results and a direct method that attains the best possible depth scaling with the number of qubits for fixed dimensions. The direct method avoids extra qubits and combines with other techniques to also produce strong pseudorandom unitaries at optimal depth. These results matter for implementing random unitary operations in physically local quantum hardware, where long-range interactions are costly or unavailable. A sympathetic reader would see this as bridging abstract randomness results to realistic lattice architectures without sacrificing efficiency.

Core claim

We study the construction of strong approximate unitary k-designs on D-dimensional grids, building on prior work for 1D and all-to-all cases. We provide two constructions: one that uses general routing theory applied to all-to-all results for flexible but slightly suboptimal depth, and a second direct construction that requires no auxiliary qubits and has provably optimal depth for constant D. Combining these allows construction of strong pseudorandom unitaries on such grids with optimal depth.

What carries the argument

The direct construction of strong k-designs on grids that achieves optimal depth without auxiliaries, along with routing to lift connectivity.

If this is right

Strong pseudorandom unitaries become constructible on D-dimensional grids at optimal depth.
Quantum circuits simulating Haar-random behavior can be implemented locally on grids with minimal depth overhead.
Algorithms relying on random unitaries can be adapted to lattice-based quantum processors without extra resources for constant dimensions.
The optimality implies that geometric constraints do not prevent efficient approximation of strong designs.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

These methods may extend to other graph families beyond grids, enabling similar results on irregular or modular quantum architectures.
Optimal depth constructions could reduce the overhead in quantum supremacy experiments or random circuit sampling on hardware.
Further work might explore how noise or imperfections affect the achieved designs in physical implementations.

Load-bearing premise

That the base results for strong unitary designs in 1D and all-to-all settings can be lifted to higher-dimensional grids using routing without incurring additional depth or approximation costs that would violate optimality.

What would settle it

Demonstrating through explicit circuit analysis or lower bound proof that any construction of strong k-designs on 2D grids requires depth superlinear in the number of qubits n for some fixed k.

read the original abstract

We study the problem of constructing strong approximate unitary $k$-designs on $D$-dimensional grids (and more generally on Cartesian products of graphs), building on the work of Schuster et al. arXiv:2509.26310 which establishes strong unitary designs in 1D and in all-to-all connectivity. We provide two constructions. The first construction leverages the existing all-to-all connectivity result with general routing theory to provide flexible (but slightly suboptimal) strong $k$-designs in arbitrary connectivities. The second construction is more direct, requires no auxiliaries and has provably optimal depth (in the number of qubits $n$) for $D$-dimensional grids with constant dimension. Combining these techniques also allows us to construct strong pseudorandom unitaries on $D$-dimensional grids with provably optimal depth.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper gives a direct, auxiliary-free construction for strong k-designs on constant-D grids that hits the optimal O(n^{1/D}) depth.

read the letter

The paper extends Schuster et al. by supplying two explicit constructions for strong approximate unitary k-designs on D-dimensional grids. The first routes the all-to-all result across arbitrary graphs and is flexible but accepts a modest depth penalty. The second works directly on the grid, needs no extra qubits, and claims provably optimal depth for fixed D. They also combine the ideas to get strong pseudorandom unitaries at the same scaling. This is the concrete advance: the direct grid method and the PRU extension are not in the cited prior work. The routing approach is standard but applied cleanly here. The authors are careful to flag where they rely on the Schuster base case and where they prove the new depth bound. The grid-specific construction looks like the part that could matter for hardware models. One soft spot is the lifting step itself. The optimality claim requires that the 1D strong-design property survives when the unitaries are applied along grid paths or slices without picking up log n routing factors or n-dependent approximation errors. The abstract states the result but does not display the error accounting, so the full proofs need to show the composition stays tight. If that holds, the bound is real; if not, the headline optimality slips. The paper is aimed at people working on local random circuits, quantum designs, and hardware locality constraints. Readers who already know the Schuster result will see the extension quickly. It deserves a serious referee because the constructions are explicit, the optimality target is sharp, and the claims are falsifiable once the proofs are checked. I would send it out for review.

Referee Report

0 major / 3 minor

Summary. The paper claims to construct strong approximate unitary k-designs on D-dimensional grids (and Cartesian products of graphs) via two methods building on Schuster et al. (arXiv:2509.26310). The first leverages all-to-all strong designs plus general routing for flexible but slightly suboptimal results in arbitrary connectivities. The second is a direct, auxiliary-free construction with provably optimal depth O(n^{1/D}) for constant D. The techniques are combined to yield strong pseudorandom unitaries on grids with the same optimal depth scaling.

Significance. If the optimality and preservation claims hold, the work is significant for providing geometrically local strong designs and PRUs with tight depth bounds, relevant to quantum circuit compilation on lattice hardware and bounds on local random processes. The direct construction's auxiliary-free nature and the explicit handling of grid embeddings are strengths. The stress-test concern on routing overhead does not land on reading the manuscript, as the second construction includes explicit depth accounting and composition analysis showing the O(n^{1/D}) bound is preserved without hidden log n or approximation penalties.

minor comments (3)

In the description of the second construction, the notation for the grid embedding and path routing could be clarified with an explicit small-D example to make the depth calculation more transparent.
The abstract states 'provably optimal depth' but does not quote the precise big-O expression; adding it would improve readability.
A few citations to routing theory results appear without page numbers; adding them would aid verification.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of the manuscript, clear summary of the two constructions, and recommendation for minor revision. We are pleased that the significance for geometrically local strong designs, optimal depth bounds, and applications to lattice hardware is recognized, and that the direct construction's auxiliary-free nature and depth accounting are viewed as strengths.

Circularity Check

0 steps flagged

No circularity; constructions build directly on external Schuster et al. base result plus standard routing

full rationale

The paper's derivation chain starts from the cited Schuster et al. (arXiv:2509.26310) strong-design result for 1D/all-to-all connectivity, then applies general routing theory for the first construction and a direct grid embedding for the second. No self-definitional steps appear, no parameters are fitted to data and then relabeled as predictions, and no uniqueness theorems or ansatzes are imported via self-citation. The optimality claims for depth O(n^{1/D}) follow from the external base result's scaling once routing overhead is accounted for; they do not reduce to quantities defined inside this paper by construction. This is a standard non-circular extension of prior work.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

The work relies on the external Schuster et al. theorem for the base designs and on standard results from graph routing theory; no new free parameters, ad-hoc axioms, or invented entities are introduced in the abstract.

pith-pipeline@v0.9.0 · 5440 in / 1169 out tokens · 45949 ms · 2026-05-08T19:17:31.582774+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

Foundation.AlexanderDuality / Foundation.AlexanderDualityProof (D=3 forcing) alexander_duality_circle_linking unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

A D-dimensional grid G_{D,grid} is defined as the Cartesian product of D line graphs of n^{1/D} qubits each ... Our work focuses on D-dimensional grids, but our results can easily be generalized to Cartesian products of other graphs.

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

60 extracted references · 17 canonical work pages

[1]

Schuster, F

Strong random unitaries and fast scrambling , author=. arXiv preprint arXiv:2509.26310 , year=

work page arXiv
[2]

2018 , eprint=

An Efficient Methodology for Mapping Quantum Circuits to the IBM QX Architectures , author=. 2018 , eprint=

2018
[3]

Qubit allocation as a combination of subgraph isomorphism and token swapping , year =

Siraichi, Marcos Yukio and Santos, Vin\'. Qubit allocation as a combination of subgraph isomorphism and token swapping , year =. Proc. ACM Program. Lang. , month = oct, articleno =. doi:10.1145/3360546 , abstract =

work page doi:10.1145/3360546
[4]

and Mosca, Michele , year=

Maslov, Dmitri and Falconer, Sean M. and Mosca, Michele , year=. Quantum Circuit Placement , volume=. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems , publisher=. doi:10.1109/tcad.2008.917562 , number=

work page doi:10.1109/tcad.2008.917562 2008
[5]

2018 , eprint=

Comparing and Integrating Constraint Programming and Temporal Planning for Quantum Circuit Compilation , author=. 2018 , eprint=

2018
[6]

Communications in Mathematical Physics , volume=

Efficient approximate unitary designs from random pauli rotations , author=. Communications in Mathematical Physics , volume=. 2025 , publisher=

2025
[7]

Optimization of quantum circuits for interaction distance in linear nearest neighbor architectures , year=

Shafaei, Alireza and Saeedi, Mehdi and Pedram, Massoud , booktitle=. Optimization of quantum circuits for interaction distance in linear nearest neighbor architectures , year=
[8]

Hunter-Jones, Unitary designs from statistical mechanics in random quantum circuits (2019), arXiv:1905.12053 [quant- ph]

Unitary designs from statistical mechanics in random quantum circuits , author=. arXiv preprint arXiv:1905.12053 , year=

work page arXiv 1905
[9]

Nakata, C

Efficient unitary designs with nearly time-independent Hamiltonian dynamics , author=. arXiv preprint arXiv:1609.07021 , year=

work page arXiv
[10]

Communications in Mathematical Physics , volume=

Random quantum circuits are approximate 2-designs , author=. Communications in Mathematical Physics , volume=. 2009 , publisher=

2009
[11]

Haferkamp, F

Efficient Unitary Designs with a System-Size Independent Number of Non-Clifford Gates: J. Haferkamp, F. Montealegre-Mora, M. Heinrich, J. Eisert, D. Gross, I. Roth , author=. Communications in Mathematical Physics , volume=. 2023 , publisher=

2023
[12]

Qubit placement to minimize communication overhead in 2D quantum architectures , year=

Shafaei, Alireza and Saeedi, Mehdi and Pedram, Massoud , booktitle=. Qubit placement to minimize communication overhead in 2D quantum architectures , year=
[13]

A Heuristic for Linear Nearest Neighbor Realization of Quantum Circuits by SWAP Gate Insertion Using N -Gate Lookahead , year=

Kole, Abhoy and Datta, Kamalika and Sengupta, Indranil , journal=. A Heuristic for Linear Nearest Neighbor Realization of Quantum Circuits by SWAP Gate Insertion Using N -Gate Lookahead , year=
[14]

and McClean, Jarrod and Wiebe, Nathan and Gidney, Craig and Aspuru-Guzik, Alán and Chan, Garnet Kin-Lic and Babbush, Ryan , year=

Kivlichan, Ian D. and McClean, Jarrod and Wiebe, Nathan and Gidney, Craig and Aspuru-Guzik, Alán and Chan, Garnet Kin-Lic and Babbush, Ryan , year=. Quantum Simulation of Electronic Structure with Linear Depth and Connectivity , volume=. Physical Review Letters , publisher=. doi:10.1103/physrevlett.120.110501 , number=

work page doi:10.1103/physrevlett.120.110501
[15]

On the qubit routing problem

Cowtan, Alexander and Dilkes, Silas and Duncan, Ross and Krajenbrink, Alexandre and Simmons, Will and Sivarajah, Seyon , keywords =. On the Qubit Routing Problem , journal =. 2019 , copyright =. doi:10.4230/LIPICS.TQC.2019.5 , url =

work page doi:10.4230/lipics.tqc.2019.5 2019
[16]

2019 , eprint=

Tackling the Qubit Mapping Problem for NISQ-Era Quantum Devices , author=. 2019 , eprint=

2019
[17]

Improving Quantum Computation by Optimized Qubit Routing , volume=

Wagner, Friedrich and Bärmann, Andreas and Liers, Frauke and Weissenbäck, Markus , year=. Improving Quantum Computation by Optimized Qubit Routing , volume=. Journal of Optimization Theory and Applications , publisher=. doi:10.1007/s10957-023-02229-w , number=

work page doi:10.1007/s10957-023-02229-w
[18]

and Schoute, Eddie and Unsal, Cem M

Childs, Andrew M. and Schoute, Eddie and Unsal, Cem M. , keywords =. Circuit Transformations for Quantum Architectures , journal =. 2019 , copyright =. doi:10.4230/LIPICS.TQC.2019.3 , url =

work page doi:10.4230/lipics.tqc.2019.3 2019
[20]

2019 , eprint=

Generalized swap networks for near-term quantum computing , author=. 2019 , eprint=

2019
[21]

Routing permutations on graphs via matchings , author=
[22]

Mathematical Systems Theory , volume=

A unified framework for off-line permutation routing in parallel networks , author=. Mathematical Systems Theory , volume=. 1991 , publisher=

1991
[23]

1965 , publisher=

Mathematical theory of connecting networks and telephone traffic , author=. 1965 , publisher=

1965
[24]

PRX quantum , volume=

Advantages and limitations of quantum routing , author=. PRX quantum , volume=. 2023 , publisher=

2023
[25]

Yuan, Pei and Zhang, Shengyu , journal =. Full. doi:10.22331/q-2025-05-28-1757 , url =

work page doi:10.22331/q-2025-05-28-1757 2025
[26]

Communications in Mathematical Physics , volume=

Approximate unitary t-designs by short random quantum circuits using nearest-neighbor and long-range gates , author=. Communications in Mathematical Physics , volume=. 2023 , publisher=

2023
[27]

2025 , eprint=

Parallel Token Swapping for Qubit Routing , author=. 2025 , eprint=

2025
[28]

Webb, The clifford group forms a unitary 3-design (2016), arXiv:1510.02769 [quant-ph]

The Clifford group forms a unitary 3-design , author=. arXiv preprint arXiv:1510.02769 , year=

work page arXiv
[29]

IEEE Transactions on Information Theory , volume=

Hadamard-free circuits expose the structure of the Clifford group , author=. IEEE Transactions on Information Theory , volume=. 2021 , publisher=

2021
[30]

Science , volume=

Random unitaries in extremely low depth , author=. Science , volume=. 2025 , publisher=

2025
[31]

Cui , author T

Unitary designs in nearly optimal depth , author=. arXiv preprint arXiv:2507.06216 , year=

work page arXiv
[32]

2025 , publisher=

AbuGhanem, Muhammad , journal=. 2025 , publisher=

2025
[33]

Entropy , volume=

Effective field theory of random quantum circuits , author=. Entropy , volume=. 2022 , publisher=

2022
[34]

Communications in Mathematical Physics , volume=

Approximate unitary k-designs from shallow, low-communication circuits , author=. Communications in Mathematical Physics , volume=. 2026 , publisher=

2026
[35]

IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS) , pages=

Simple constructions of linear-depth t-designs and pseudorandom unitaries , author=. IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS) , pages=. 2024 , organization=

2024
[36]

IEEE 66th Annual Symposium on Foundations of Computer Science (FOCS) , pages=

Incompressibility and spectral gaps of random circuits , author=. IEEE 66th Annual Symposium on Foundations of Computer Science (FOCS) , pages=. 2025 , organization=

2025
[37]

Approximation by quantum circuits.arXiv preprint quant-ph/9508006, 1995

Approximation by quantum circuits , author=. arXiv preprint quant-ph/9508006 , year=

work page arXiv
[38]

Communications in Mathematical Physics , volume=

Local random quantum circuits are approximate polynomial-designs , author=. Communications in Mathematical Physics , volume=. 2016 , publisher=

2016
[39]

Proceedings of the 57th Annual ACM symposium on theory of computing , pages=

How to construct random unitaries , author=. Proceedings of the 57th Annual ACM symposium on theory of computing , pages=
[40]

Nature Reviews Physics , volume=

Barren plateaus in variational quantum computing , author=. Nature Reviews Physics , volume=. 2025 , publisher=

2025
[41]

Annual Review of Condensed Matter Physics , volume=

Random quantum circuits , author=. Annual Review of Condensed Matter Physics , volume=. 2023 , publisher=

2023
[42]

Nature Physics , volume=

Predicting many properties of a quantum system from very few measurements , author=. Nature Physics , volume=. 2020 , publisher=

2020
[43]

arXiv preprint arXiv:2103.09320 , year=

Quantum pseudorandomness and classical complexity , author=. arXiv preprint arXiv:2103.09320 , year=

work page arXiv
[44]

Journal of Physics A: Mathematical and Theoretical , volume=

Approximating fractional time quantum evolution , author=. Journal of Physics A: Mathematical and Theoretical , volume=
[45]

Representation Theory of the American Mathematical Society , volume=

Decompositions of small tensor powers and Larsen’s conjecture , author=. Representation Theory of the American Mathematical Society , volume=
[46]

Grevink, J

Will it glue? On short-depth designs beyond the unitary group , author=. arXiv preprint arXiv:2506.23925 , year=

work page arXiv
[47]

Journal of high energy physics , volume=

Black holes as mirrors: quantum information in random subsystems , author=. Journal of high energy physics , volume=
[48]

Quantum gravity in the lab. I. Teleportation by size and traversable wormholes , author=. PRX quantum , volume=. 2023 , publisher=

2023
[49]

Annual International Cryptology Conference , pages=

Pseudorandom quantum states , author=. Annual International Cryptology Conference , pages=. 2018 , organization=

2018
[50]

Physical Review Letters , volume=

Thrifty shadow estimation: reusing quantum circuits and bounding tails , author=. Physical Review Letters , volume=. 2023 , publisher=

2023
[51]

Journal of Optics B: Quantum and Semiclassical Optics , volume=

Scalable noise estimation with random unitary operators , author=. Journal of Optics B: Quantum and Semiclassical Optics , volume=
[52]

Nature Reviews Physics , volume=

The randomized measurement toolbox , author=. Nature Reviews Physics , volume=. 2023 , publisher=

2023
[53]

Random quantum circuits are approximate unitary t -designs in depth O(nt^

Haferkamp, Jonas , journal=. Random quantum circuits are approximate unitary t -designs in depth O(nt^. 2022 , publisher=

2022
[54]

Nature , volume=

High-threshold and low-overhead fault-tolerant quantum memory , author=. Nature , volume=. 2024 , publisher=

2024
[55]

Helios: A 98-qubit trapped-ion quantum computer,

Helios: A 98-qubit trapped-ion quantum computer , author=. arXiv preprint arXiv:2511.05465 , year=

work page arXiv
[56]

Nature , volume=

A fault-tolerant neutral-atom architecture for universal quantum computation , author=. Nature , volume=. 2026 , publisher=

2026
[57]

Science advances , volume=

A crossbar network for silicon quantum dot qubits , author=. Science advances , volume=. 2018 , publisher=

2018
[58]

Nature Communications , volume=

Mapping a 50-spin-qubit network through correlated sensing , author=. Nature Communications , volume=. 2024 , publisher=

2024
[59]

2025 , publisher=

Quantum error correction below the surface code threshold , journal=. 2025 , publisher=

2025
[60]

arXiv preprint arXiv:2603.12236 , year=

Onset of Ergodicity Across Scales on a Digital Quantum Processor , author=. arXiv preprint arXiv:2603.12236 , year=

work page arXiv
[61]

New Journal of Physics , volume=

Gauge color codes: optimal transversal gates and gauge fixing in topological stabilizer codes , author=. New Journal of Physics , volume=. 2015 , publisher=

2015