We seek to develop better upper bound guarantees on the depth of quantum CZ gate, CNOT gate, and Clifford circuits than those reported previously. We focus on the number of qubits$n\,{\leq }\,$1,345,000 [1], which represents the most practical use case. Our upper bound on the depth of$\textsc {CZ}$circuits is$\lfloor n/2 + 0.4993{\cdot }\log ^{2}(n) + 3.0191{\cdot }\log (n) - 10.9139\rfloor$, improving best known depth by a factor of roughly 2. We extend the constructions used to prove this upper bound to obtain depth upper bound of$\lfloor n + 1.9496{\cdot }\log ^{2}(n) + 3.5075{\cdot }\log (n) - 23.4269 \rfloor$for CNOT gate circuits, offering an improvement by a factor of roughly$4/3$over state of the art, and depth upper bound of$\lfloor 2n + 2.9487{\cdot }\log ^{2}(n) + 8.4909{\cdot }\log (n) - 44.4798\rfloor$for Clifford circuits, offering an improvement by a factor of roughly$5/3$.
We seek to develop better upper bound guarantees on the depth of quantum CZ gate, CNOT gate, and Clifford circuits than those reported previously. We focus on the number of qubitsn≤1,345,000 [1], which represents the most practical use case. Our upper bound on the depth of\textscCZcircuits is⌊n/2+0.4993⋅log2(n)+3.0191⋅log(n)−10.9139⌋, improving best known depth by a factor of roughly 2. We extend the constructions used to prove this upper bound to obtain depth upper bound of⌊n+1.9496⋅log2(n)+3.5075⋅log(n)−23.4269⌋for CNOT gate circuits, offering an improvement by a factor of roughly4/3over state of the art, and depth upper bound of⌊2n+2.9487⋅log2(n)+8.4909⋅log(n)−44.4798⌋for Clifford circuits, offering an improvement by a factor of roughly5/3.
Optimal circuit synthesis is the problem of finding the shortest-depth circuit representation of a given functionality with respect to a pre-specified elementary gate set. This is a central problem in both quantum and classical hardware design. While the classical version is very well understood -- both in terms of heuristics and rigorous hardness assertions -- much less is known about optimal quantum circuit synthesis.
We focus on optimal Clifford circuit synthesis, for which various heuristics are known, e.g. via reduction to 3-SAT. Our main result supplies a matching hardness result: a variant of optimal Clifford synthesis is NP-hard. The proof proceeds in two parts: (i) reduce 3-edge colorability on 3-regular graphs to a circuit synthesis problem that only involves CZ gates, (ii) prove that the availability of additional elementary Clifford gates -- most notably: Hadamard, phase and CNOT -- cannot lead to further improvements of the optimal circuit depth. Our work sharpens the complexity-theoretic understanding of Clifford circuits: simulation and equivalence checking are in P, whereas deciding whether a Clifford unitary admits an implementation within a prescribed depth is NP-complete.
Clifford circuit optimization is an important step in the quantum compilation pipeline. Major compilers employ heuristic approaches. While they are fast, their results are often suboptimal. Minimization of noisy gates, like 2-qubit CNOT gates, is crucial for practical computing. Exact approaches have been proposed to fill the gap left by heuristic approaches. Among these are SAT based approaches that optimize gate count or depth, but they suffer from scalability issues. Further, they do not guarantee optimality on more important metrics like CNOT count or CNOT depth. A recent work proposed an exhaustive search only on Clifford circuits in a certain normal form to guarantee CNOT count optimality. But an exhaustive approach cannot scale beyond 6 qubits. In this paper, we incorporate search restricted to Clifford normal forms in a SAT encoding to guarantee CNOT count optimality. By allowing parallel plans, we propose a second SAT encoding that optimizes CNOT depth. By taking advantage of flexibility in SAT based approaches, we also handle connectivity restrictions in hardware platforms, and allow for qubit relabeling. We have implemented the above encodings and variations in our open source tool Q-Synth. In experiments, our encodings significantly outperform existing SAT approaches on random Clifford circuits. We consider practical VQE and Feynman benchmarks to compare with TKET and Qiskit compilers. In all-to-all connectivity, we observe reductions up to 32.1% in CNOT count and 48.1% in CNOT depth. Overall, we observe better results than TKET in the CNOT count and depth. We also experiment with connectivity restrictions of major quantum platforms. Compared to Qiskit, we observe up to 30.3% CNOT count and 35.9% CNOT depth further reduction.
This project focused on upper and lower bounds for quantum computability using constant depth quantum circuits, and on the complexity theory of such circuits. It established significant differences between resource bounded quantum and classical computation models, particularly emphasizing new examples of where quantum circuits are more powerful than their classical counterparts. A second focus and outgrowth of this work was the creation of efficient quantum algorithms for specific problems and central combinatorial functions. Recent finding include upper bounds for the computational power of constant depth circuits composed of single qubit and CNOT gates, and lower bounds for the computational power of constant depth circuits with single qubit, CNOT and fanout gates. These results represent the power and the limits of small, possibly realizable quantum circuits. Also examined were bounds on computations with additional storage qubits (ancillae), and natural simple functions (realized by small depth circuits) which require ancillae for their computation.
Minimizing the number of CNOT gates required to synthesize a Clifford operator is a central problem in quantum circuit optimization. We extend the link--middle--cut (LMC) framework for linear reversible circuits to Clifford operators represented by binary symplectic tableaux. By introducing block-support connectivity graphs and determinantal invariants, we obtain efficiently computable lower bounds on ancilla-free CNOT complexity. We prove that these bounds are tight for qubit permutations: a permutation of n qubits with k cycles requires exactly 3(n−k) CNOT gates, even when arbitrary one-qubit Clifford gates are available. We also derive efficiently computable bounds for synthesis up to a permutation of the output qubits, corresponding to free qubit relabeling. Finally, we further demonstrate the utility of the bound by using it as an admissible heuristic for A∗-based Clifford synthesis and show that, on benchmark instances, the resulting search can prove optimality beyond what was possible with earlier SAT-based methods, and that it may be used in combination with earlier A∗ heuristics to improve the CNOT counts obtained through heuristic search.
Short note with the circuit, an independent verifier and the search records. For ancilla-free Clifford preparation of the logical zero |0_G> = 2^{-11/2} Σ_{c ∈ C^⊥} |c> of the [[23,1,7]] quantum Golay code (Open Problem Zoo op_c847b635f53b0812, after Paetznick and Reichardt 2012), the best documented circuits were 45 two-qubit gates at two-qubit depth 7 and 44 gates at depth 8 (Doherty et al., arXiv:2603.17743). We exhibit an explicit circuit with 44 two-qubit gates (all controlled-Z, i.e. CNOT up to free single-qubit Cliffords) in six disjoint two-qubit layers of sizes 9, 10, 7, 6, 7, 5, so g_G(D) ≤ 44 for every D ≥ 6; it dominates both previous Pareto points. The circuit is given in the cyclic coordinates of the Golay code (generator polynomial 1+x^2+x^4+x^5+x^6+x^10+x^11) and verified two independent ways: a stabilizer-tableau proof (the output stabilizer group is CSS with all + signs, its Z-code is a binary [23,12,7] code, hence the Golay code by uniqueness, and an explicit wire permutation is exhibited) and a full 2^23-amplitude statevector overlap of 1.0 with the target. The circuit was found by an autonomous AI research agent (the depositor's EVO discovery harness, Claude Sonnet 5.5 proposer) by a local search started from the published 44-gate depth-8 circuit: a bit-packed C tableau simulator, a cost equal to the number of qubits left entangled when the circuit is run backwards from the target, and a random walk among 44-gate circuits that penalises gates in layers beyond the target depth. The same searches did not find 43 gates at any depth or 44 gates at depth 5 (about 10^10 and 10^9 evaluations respectively; these are negative search outcomes, not bounds). Claim boundary: an upper bound g_G(6) ≤ 44 witnessed by an explicit, machine-checkable circuit; no optimality or priority claim. Files: the note (PDF + LaTeX), the circuit in three equivalent JSON forms (agent wire labels; cyclic coordinates; cyclic coordinates with CNOT as the only two-qubit gate), the verifier and relabeling finder, the agent's notes and search code, the task text, SHA-256 sums.
In this work, we prove the strongest known lower bounds for QAC0, allowing polynomially many gates and ancillae. Our main results show that:
(1) Depth-3 QAC0 circuits cannot compute PARITY, and require Ω(exp(n)) gates to compute MAJORITY.
(2) Depth-2 circuits cannot approximate high-influence Boolean functions (e.g., PARITY) with non-negligible advantage, regardless of size.
We develop new classical simulation techniques for QAC0 to obtain our depth-3 bounds. In these results, we relax the output requirement of the quantum circuit to a single bit, making our depth 2 approximation bound stronger than the previous best bound of Rosenthal (2021). This also enables us to draw natural comparisons with classical AC0 circuits, which can compute PARITY exactly in depth 2 (exp size). Our techniques further suggest that, for boolean total functions, constant-depth quantum circuits do not necessarily provide more power than their classical counterparts. Our third result shows that depth 2 QAC0 circuits, regardless of size, cannot exactly synthesize an n-target nekomata state (a state whose synthesis is directly related to the computation of PARITY). This complements the depth 2 exponential size upper bound of Rosenthal (2021) for approximating nekomatas (which is used as a sub-circuit in the only known constant depth PARITY upper bound). Finally, we argue that approximating PARITY in QAC0, with significantly better than 1/poly(n) advantage on average, is just as hard as computing it exactly. Thus, extending our techniques to higher depths would also rule out approximate circuits for PARITY and related problems