Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2606.17589

Asymptotically Optimal Circuit Depth for Diagonal Unitary Synthesis and Compilation on Two-Dimensional Grids

Chengzhuo Xu, Xiao Chen, Zhihao Liu, Zhigang Li

quant-phSubmitted Jun 16, 2026• Announced Jun 17, 2026• 0 citations
arXivHTMLPDF

Abstract

Diagonal unitaries are a fundamental but resource-intensive class of quantum operations, arising as the phase separators of QAOA and the time-evolution blocks of Hamiltonian simulation. Under all-to-all connectivity their optimal depth is established, but on nearest-neighbor hardware general-purpose compilers fall back on heuristic search, which yields no analyzable cost bound and becomes intractable at the very sizes where depth is the bottleneck. We address synthesis and compilation jointly. On the synthesis side, we develop a Gray-Path Framework (GPF) that realizes any $n$-qubit diagonal unitary in asymptotically optimal $R_z$ and CNOT depth $O(2^n/n)$ without ancillas. Our main result is that compiling GPF onto a two-dimensional nearest-neighbor grid preserves this optimality: routing adds depth $Θ(2^n/n)$ and gate count $Θ(2^n)$. Because GPF fixes its entire interaction structure in advance, routing reduces to scheduling a known sequence, with no heuristic search. We give the construction both with and without ancillas: the ancilla-free, cost-optimized layout is a two-row grid, and a $2k$-row layout introduces a space--time tradeoff that cuts depth by $1/k$ while remaining asymptotically optimal for the enlarged register; both are deterministic and analyzed in closed form. The same complexity is also attained on a linear nearest-neighbor chain, so the preservation is topology-independent, holding on any architecture that contains such a chain. All routing bounds are closed-form, giving the concrete resource estimates that heuristic compilers cannot provide at scale.

Comments
24 pages, 25 figures

Related papers

Asymptotically Optimal Depth Fermionic Permutation on 2D Grid Quantum Architecture without Ancillas

Dantong Li, Shifan Xu, Yongshan Ding

Simulating fermionic systems on qubit hardware involves many nonlocal interactions, and efficient routing of these interactions is critical to the overall cost of fermionic simulation algorithms. Recent works reduce this routing overhead to polylogarithmic depth under all-to-all connectivity, but degrade to $O(\sqrt{N}\log N)$ for $N$ fermionic modes on 2D nearest-neighbor architectures. We present a fermionic permutation protocol tailored to 2D grid architectures that achieves the optimal $O(\sqrt{N})$ depth with $O(N\sqrt{N})$ nearest-neighbor gates and no ancilla qubits, measurements, or classical feedforward. For $N=L^2$ modes, the CNOT depth is at most $10L+12$. This matches the $Ω(\sqrt{N})$ lower bound, which holds even when $O(N)$ ancillas and classical feedforward are permitted. We further construct an $O(\sqrt{N})$-depth transformation between the Jordan--Wigner, Bravyi--Kitaev, and Parity encodings on the 2D grid via a Hilbert-curve layout, extending our result to all three encodings. Benchmarks on a standalone fermionic permutation circuit, the fermionic fast Fourier transform, and Trotter simulation of a sparse SYK model demonstrate that the practical crossover is near the analytical depth-bound breakeven at $L=6$ ($N=36$), followed by consistent reductions in circuit depth and spacetime volume and higher estimated no-fault probability in the early fault-tolerant regime, growing with system size.

quant-pharXiv:2605.26041•May 26, 2026•0 citations

Toward Optimal Circuit Depth for Geometrically Local Hamiltonian Simulation

Zheyu Shen, Yusen Wu, Penghui Yao +2 more

Understanding the dynamics of interacting quantum systems is a central goal of quantum simulation. For geometrically local Hamiltonians, locality suggests that digital simulation should retain much of the parallelism of the underlying dynamics. For a target accuracy $ε$, we construct a nearest-neighbor quantum circuit that simulates the dynamics of an $n$-qubit, time-independent, finite-range Hamiltonian with normalized local interaction strength on a fixed-dimensional lattice for time $T\ge1$, with circuit depth $O(T\log(nT/ε))$ and gate count $O(nT\log(nT/ε))$. This reduces the polylogarithmic overhead of Haah, Hastings, Kothari, and Low to a single logarithm. On logarithmic-scale blocks from the Lieb--Robinson decomposition, a shallow but highly accurate implementation is essential for reducing the circuit depth. Our key observation is that spatial localization also controls the cost of high precision. In each block, the error of a constant-order product formula is compensated for by a correction, yielding exponential accuracy. The correction can be implemented with depth proportional to the block diameter, introducing no additional asymptotic depth scale beyond that required by spatial localization. Furthermore, we prove an unconditional circuit-depth lower bound for uniform XXZ Hamiltonians: at fixed evolution time $T$ in the stated regime and sufficiently small fixed error $ε$, any nearest-neighbor quantum circuit simulating these dynamics requires depth $Ω(\log n/\log\log n)$. This matches our $O(\log n)$ upper bound up to a doubly logarithmic factor, establishing near-optimal circuit depth for lattice Hamiltonian simulation in this regime. Together, these results clarify the role of locality and precision in determining the circuit complexity of quantum dynamics and suggest broader principles for spatially constrained quantum computation.

quant-pharXiv:2610.01839•Oct 2, 2026•0 citations

Depth-optimized quantum circuit synthesis for diagonal unitary operators with asymptotically optimal gate count

Shihao Zhang, Kai Huang, Lvzhou Li

Diagonal unitary operators are well known to be key building blocks of many quantum algorithms and quantum computing procedures, and thus resource-efficient quantum circuit implementations are in demand. Here we propose a constructive algorithm that can generate a quantum circuit over the primitive gate set {cnot, ${R}_{Z}$} for realizing any given diagonal unitary operator piece by piece. The theoretical analysis reveals that, for the general case, our generated circuit not only ensures the asymptotically optimal gate count, but also nearly halves the circuit depth compared with the previous Welch's method [New J. Phys. 16, 033040 (2014)]. Specifically, this substantial depth optimization originates from the use of a uniform circuit rewriting rule developed here. The performance of our circuit synthesis algorithm is further validated by numerical evaluations on two examples. First, we achieve a nearly 50% depth reduction over Welch's method for synthesizing random diagonal unitary operators with up to 16 qubits. Second, we achieve an average of 22.05% depth reduction for resynthesizing the diagonal part of the specific quantum approximate optimization algorithm (QAOA) circuits with up to 14 qubits.

arXiv:2212.01002•Physical Review A•Apr 1, 2024•12 citations

Provably Optimal Quantum Circuits with Mixed-Integer Programming

Harsha Nagarajan, Zsolt Szabó

We present a depth-aware optimization framework for quantum circuit compilation that unifies provable optimality with scalable heuristics. For exact synthesis of a target unitary, we formulate a mixed-integer linear program (MILP) that linearly handles global-phase equivalence and uses explicit parallel scheduling variables to certify depth-optimal solutions for small-to-medium circuits. Domain-specific valid constraints, including identity ordering, commuting-gate pruning, short-sequence redundancy cuts, and Hermitian-conjugate linkages, significantly accelerate branch-and-bound, yielding speedups up to 43x on standard benchmarks. The framework supports hardware-aware objectives, enabling fault-tolerant (e.g. T-count) and NISQ-era (e.g. entangling gates) devices. For approximate synthesis, we propose 3 objectives: (i) exact, but non-convex, phase-invariant fidelity maximization; (ii) a linear surrogate that maximizes the real trace overlap, yielding a tight lower bound to fidelity; and (iii) a convex quadratic function that minimizes the circuit's Frobenius error. To scale beyond exact MILP, we propose a novel rolling-horizon optimization (RHO) that rolls primarily in time, caps the active-qubits, and enforces per-qubit closure while globally optimizing windowed segments. This preserves local context, reduces the Hilbert-space dimension, and enables iterative improvements without ancillas. On a 142-gate seed circuit, RHO yields 116 gates, an 18.3% reduction from the seed, while avoiding the trade-off between myopic passes and long run times. Empirically, our exact compilation framework achieves certified depth-optimal circuits on standard targets, high-fidelity Fibonacci-anyon weaves, and a 36% gate-count reduction on multi-body parity circuits. All methods are in the open-source QuantumCircuitOpt, providing a single framework that bridges exact certification and scalable synthesis.

arXiv:2510.00649•Oct 1, 2025•1 citation

Efficient Circuit Transpilation of Commuting Gates on 2D Grids

Sabina Drăgoi, Daniel J. Egger

Combinatorial optimization problems are central to many applications but can be challenging to solve. Quantum approaches such as the Quantum Approximate Optimization Algorithm (QAOA) offer new tools with which to tackle such problems. However, QAOA circuits inherit the interaction structure of the target Hamiltonian, often resulting in deep circuits when compiled onto hardware with limited connectivity. Efficient transpilation is therefore critical to their practical performance. In this work, we propose a transpilation scheme for circuits consisting of blocks of commuting two-qubit gates on two-dimensional lattices. Unlike standard approaches based on random initial mappings and fixed routing, our method alternates between constructing problem-dependent SWAP-layer sequences and updating the qubit layout. By adapting the routing to the required interactions, this yields significantly shorter circuits for graphs with few edges. We benchmark our approach on QAOA instances for Maximum Cut (MC) on Random Regular graphs and Maximum Independent Set (MIS) on Erdős-Rényi graphs. Compared to standard methods, we reduce circuit depth and gate count by about a factor of two, enabling experiments with up to $80$ qubits and improving approximation ratios by up to $6.6\%$ for MC and $9.3\%$ for MIS.

quant-pharXiv:2607.10274•Jul 14, 2026•0 citations

Surface Code Compilation via Edge-Disjoint Paths

Michael E. Beverland, Vadym Kliuchnikov, Eddie Schoute

We provide an efficient algorithm to compile quantum circuits for fault-tolerant execution.We target surface codes, which form a two-dimensional grid of logical qubits with nearest-neighbor logical operations.Embedding an input circuit's qubits in surface codes can result in long-range two-qubit operations across the grid.We show how to prepare many long-range Bell pairs on qubits connected by edge-disjoint paths of ancillae in constant depth that can be used to perform these long-range operations.This forms one core part of our edge-disjoint path compilation (EDPC) algorithm, by easily performing many parallel long-range Clifford operations in constant depth.It also allows us to establish a connection between surface code compilation and several well-studied edge-disjoint path problems.Similar techniques allow us to perform non-Clifford single-qubit rotations far from magic state distillation factories.In this case, we can easily find the maximum set of paths by a max-flow reduction, which forms the other major part of EDPC.EDPC has the best asymptotic worst-case performance guarantees on the circuit depth for compiling parallel operations when compared to related compilation methods based on SWAP gates and network coding.EDPC also shows a quadratic depth improvement over sequential Pauli-based compilation for parallel rotations requiring magic resources.We implement EDPC and find significantly improved performance for circuits built from parallel controlled-NOT (CNOT) gates, and for circuits that implement the multicontrolled X gate C k NOT.

arXiv:2110.11493•PRX Quantum•May 25, 2022•61 citations
Diagonal unitaries are a fundamental but resource-intensive class of quantum operations, arising as the phase separators of QAOA and the time-evolution blocks of Hamiltonian simulation. Under all-to-all connectivity their optimal depth is established, but on nearest-neighbor hardware general-purpose compilers fall back on heuristic search, which yields no analyzable cost bound and becomes intractable at the very sizes where depth is the bottleneck. We address synthesis and compilation jointly. On the synthesis side, we develop a Gray-Path Framework (GPF) that realizes any nnn-qubit diagonal unitary in asymptotically optimal RzR_zRz​ and CNOT depth O(2n/n)O(2^n/n)O(2n/n) without ancillas. Our main result is that compiling GPF onto a two-dimensional nearest-neighbor grid preserves this optimality: routing adds depth Θ(2n/n)Θ(2^n/n)Θ(2n/n) and gate count Θ(2n)Θ(2^n)Θ(2n). Because GPF fixes its entire interaction structure in advance, routing reduces to scheduling a known sequence, with no heuristic search. We give the construction both with and without ancillas: the ancilla-free, cost-optimized layout is a two-row grid, and a 2k2k2k-row layout introduces a space--time tradeoff that cuts depth by 1/k1/k1/k while remaining asymptotically optimal for the enlarged register; both are deterministic and analyzed in closed form. The same complexity is also attained on a linear nearest-neighbor chain, so the preservation is topology-independent, holding on any architecture that contains such a chain. All routing bounds are closed-form, giving the concrete resource estimates that heuristic compilers cannot provide at scale.
Simulating fermionic systems on qubit hardware involves many nonlocal interactions, and efficient routing of these interactions is critical to the overall cost of fermionic simulation algorithms. Recent works reduce this routing overhead to polylogarithmic depth under all-to-all connectivity, but degrade to O(Nlog⁡N)O(\sqrt{N}\log N)O(N​logN) for NNN fermionic modes on 2D nearest-neighbor architectures. We present a fermionic permutation protocol tailored to 2D grid architectures that achieves the optimal O(N)O(\sqrt{N})O(N​) depth with O(NN)O(N\sqrt{N})O(NN​) nearest-neighbor gates and no ancilla qubits, measurements, or classical feedforward. For N=L2N=L^2N=L2 modes, the CNOT depth is at most 10L+1210L+1210L+12. This matches the Ω(N)Ω(\sqrt{N})Ω(N​) lower bound, which holds even when O(N)O(N)O(N) ancillas and classical feedforward are permitted. We further construct an O(N)O(\sqrt{N})O(N​)-depth transformation between the Jordan--Wigner, Bravyi--Kitaev, and Parity encodings on the 2D grid via a Hilbert-curve layout, extending our result to all three encodings. Benchmarks on a standalone fermionic permutation circuit, the fermionic fast Fourier transform, and Trotter simulation of a sparse SYK model demonstrate that the practical crossover is near the analytical depth-bound breakeven at L=6L=6L=6 (N=36N=36N=36), followed by consistent reductions in circuit depth and spacetime volume and higher estimated no-fault probability in the early fault-tolerant regime, growing with system size.
Understanding the dynamics of interacting quantum systems is a central goal of quantum simulation. For geometrically local Hamiltonians, locality suggests that digital simulation should retain much of the parallelism of the underlying dynamics. For a target accuracy εεε, we construct a nearest-neighbor quantum circuit that simulates the dynamics of an nnn-qubit, time-independent, finite-range Hamiltonian with normalized local interaction strength on a fixed-dimensional lattice for time T≥1T\ge1T≥1, with circuit depth O(Tlog⁡(nT/ε))O(T\log(nT/ε))O(Tlog(nT/ε)) and gate count O(nTlog⁡(nT/ε))O(nT\log(nT/ε))O(nTlog(nT/ε)). This reduces the polylogarithmic overhead of Haah, Hastings, Kothari, and Low to a single logarithm. On logarithmic-scale blocks from the Lieb--Robinson decomposition, a shallow but highly accurate implementation is essential for reducing the circuit depth. Our key observation is that spatial localization also controls the cost of high precision. In each block, the error of a constant-order product formula is compensated for by a correction, yielding exponential accuracy. The correction can be implemented with depth proportional to the block diameter, introducing no additional asymptotic depth scale beyond that required by spatial localization. Furthermore, we prove an unconditional circuit-depth lower bound for uniform XXZ Hamiltonians: at fixed evolution time TTT in the stated regime and sufficiently small fixed error εεε, any nearest-neighbor quantum circuit simulating these dynamics requires depth Ω(log⁡n/log⁡log⁡n)Ω(\log n/\log\log n)Ω(logn/loglogn). This matches our O(log⁡n)O(\log n)O(logn) upper bound up to a doubly logarithmic factor, establishing near-optimal circuit depth for lattice Hamiltonian simulation in this regime. Together, these results clarify the role of locality and precision in determining the circuit complexity of quantum dynamics and suggest broader principles for spatially constrained quantum computation.
Diagonal unitary operators are well known to be key building blocks of many quantum algorithms and quantum computing procedures, and thus resource-efficient quantum circuit implementations are in demand. Here we propose a constructive algorithm that can generate a quantum circuit over the primitive gate set {cnot, RZ{R}_{Z}RZ​} for realizing any given diagonal unitary operator piece by piece. The theoretical analysis reveals that, for the general case, our generated circuit not only ensures the asymptotically optimal gate count, but also nearly halves the circuit depth compared with the previous Welch's method [New J. Phys. 16, 033040 (2014)]. Specifically, this substantial depth optimization originates from the use of a uniform circuit rewriting rule developed here. The performance of our circuit synthesis algorithm is further validated by numerical evaluations on two examples. First, we achieve a nearly 50% depth reduction over Welch's method for synthesizing random diagonal unitary operators with up to 16 qubits. Second, we achieve an average of 22.05% depth reduction for resynthesizing the diagonal part of the specific quantum approximate optimization algorithm (QAOA) circuits with up to 14 qubits.
We present a depth-aware optimization framework for quantum circuit compilation that unifies provable optimality with scalable heuristics. For exact synthesis of a target unitary, we formulate a mixed-integer linear program (MILP) that linearly handles global-phase equivalence and uses explicit parallel scheduling variables to certify depth-optimal solutions for small-to-medium circuits. Domain-specific valid constraints, including identity ordering, commuting-gate pruning, short-sequence redundancy cuts, and Hermitian-conjugate linkages, significantly accelerate branch-and-bound, yielding speedups up to 43x on standard benchmarks. The framework supports hardware-aware objectives, enabling fault-tolerant (e.g. T-count) and NISQ-era (e.g. entangling gates) devices. For approximate synthesis, we propose 3 objectives: (i) exact, but non-convex, phase-invariant fidelity maximization; (ii) a linear surrogate that maximizes the real trace overlap, yielding a tight lower bound to fidelity; and (iii) a convex quadratic function that minimizes the circuit's Frobenius error. To scale beyond exact MILP, we propose a novel rolling-horizon optimization (RHO) that rolls primarily in time, caps the active-qubits, and enforces per-qubit closure while globally optimizing windowed segments. This preserves local context, reduces the Hilbert-space dimension, and enables iterative improvements without ancillas. On a 142-gate seed circuit, RHO yields 116 gates, an 18.3% reduction from the seed, while avoiding the trade-off between myopic passes and long run times. Empirically, our exact compilation framework achieves certified depth-optimal circuits on standard targets, high-fidelity Fibonacci-anyon weaves, and a 36% gate-count reduction on multi-body parity circuits. All methods are in the open-source QuantumCircuitOpt, providing a single framework that bridges exact certification and scalable synthesis.
Combinatorial optimization problems are central to many applications but can be challenging to solve. Quantum approaches such as the Quantum Approximate Optimization Algorithm (QAOA) offer new tools with which to tackle such problems. However, QAOA circuits inherit the interaction structure of the target Hamiltonian, often resulting in deep circuits when compiled onto hardware with limited connectivity. Efficient transpilation is therefore critical to their practical performance. In this work, we propose a transpilation scheme for circuits consisting of blocks of commuting two-qubit gates on two-dimensional lattices. Unlike standard approaches based on random initial mappings and fixed routing, our method alternates between constructing problem-dependent SWAP-layer sequences and updating the qubit layout. By adapting the routing to the required interactions, this yields significantly shorter circuits for graphs with few edges. We benchmark our approach on QAOA instances for Maximum Cut (MC) on Random Regular graphs and Maximum Independent Set (MIS) on Erdős-Rényi graphs. Compared to standard methods, we reduce circuit depth and gate count by about a factor of two, enabling experiments with up to 808080 qubits and improving approximation ratios by up to 6.6%6.6\%6.6% for MC and 9.3%9.3\%9.3% for MIS.
We provide an efficient algorithm to compile quantum circuits for fault-tolerant execution.We target surface codes, which form a two-dimensional grid of logical qubits with nearest-neighbor logical operations.Embedding an input circuit's qubits in surface codes can result in long-range two-qubit operations across the grid.We show how to prepare many long-range Bell pairs on qubits connected by edge-disjoint paths of ancillae in constant depth that can be used to perform these long-range operations.This forms one core part of our edge-disjoint path compilation (EDPC) algorithm, by easily performing many parallel long-range Clifford operations in constant depth.It also allows us to establish a connection between surface code compilation and several well-studied edge-disjoint path problems.Similar techniques allow us to perform non-Clifford single-qubit rotations far from magic state distillation factories.In this case, we can easily find the maximum set of paths by a max-flow reduction, which forms the other major part of EDPC.EDPC has the best asymptotic worst-case performance guarantees on the circuit depth for compiling parallel operations when compared to related compilation methods based on SWAP gates and network coding.EDPC also shows a quadratic depth improvement over sequential Pauli-based compilation for parallel rotations requiring magic resources.We implement EDPC and find significantly improved performance for circuits built from parallel controlled-NOT (CNOT) gates, and for circuits that implement the multicontrolled X gate C k NOT.