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

A 44-gate, depth-6 Clifford circuit preparing the [[23,1,7]] Golay logical zero: a new point on the CNOT-count/depth frontier

Harish Santhanalakshmi Ganesan

Published Oct 20, 2026• 0 citations
Publisher

Abstract

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.

DOI
10.5281/zenodo.23509366

Related papers

A T-count Zero Protocol for Heralded W-state Preparation via Clifford-only Gates

Amrita Mitra

Abstract The W state is a key resource for quantum communication and distributed quantum computing. Its entanglement survives the loss of any single qubit. Preparing the W state exactly is nevertheless hard in fault-tolerant architectures. The amplitude 1/√3 lies outside the ring Z[1/√2, i]. So no Clifford+T unitary can prepare the three-qubit W state exactly, and deterministic circuits must approximate the required rotation at a T-count that grows as log(1/ϵ). We present a heralded protocol that prepares the three-qubit W state exactly using Clifford gates and a single non-Clifford operation. A shallow Clifford circuit with two CNOT gates first prepares an equal superposition of |001⟩, |010⟩, |100⟩ and |111⟩. A logical-AND measurement on one ancilla then removes the |111⟩ component without disturbing the remaining coherent superposition. The protocol succeeds with probability 3/4, a failed attempt leaves the known product state |111⟩, and each attempt consumes four T gates or one |CCZ⟩ magic state. This gives an expected cost of about 5.33 T gates independent of target precision. We prove that some non-Clifford step is necessary, and by exhaustively enumerating all 315,057,600 six-qubit stabilizer tensors we show that no post-selected Clifford circuit with three or fewer T gates outputs the W state. Every heralded Clifford+T preparation of the W state therefore uses at least four T gates per successful run, and our protocol attains this bound. The protocol uses 6 to 19 times fewer T gates than gate synthesis at precisions between 10−3 and 10−10. We compare it with a deterministic circuit using an exact repeat-untilsuccess rotation, which achieves a slightly lower expected cost of about 4.67 T gates, and discuss implementation in modular architectures and extensions to N-qubit W states. Note on this version. This version replaces and corrects the first version of this preprint (“A Tcount Zero Protocol for Heralded W-state Preparation via Clifford-only Gates”). The claim there that the W state can be prepared with Clifford gates alone is incorrect: as shown here, some non-Clifford step is necessary, and at least four T gates are needed per successful run.

•Jul 22, 2026•0 citations

Heuristic and Optimal Synthesis of CNOT and Clifford Circuits

Mark Webster, Stergios Koutsioumpas, Dan E. Browne

Efficiently implementing Clifford circuits is crucial for quantum error correction and quantum algorithms. Linear reversible circuits, equivalent to circuits composed of CNOT\xspace gates, have important applications in classical computing. In this work we present methods for CNOT\xspace and general Clifford circuit synthesis which can be used to minimise either the entangling two-qubit gate count or the circuit depth. We present three families of algorithms - optimal synthesis which works on small circuits, A* synthesis for intermediate-size circuits and greedy synthesis for large circuits. We benchmark against existing methods, including rustiq, tket and qiskit and show that our approach results in circuits with lower two-qubit gate count. For encoding circuits, our methods outperform previous reinforcement learning results and find a lower two-qubit gate count circuit for the Golay code than previously known. The algorithms have been implemented in a GitHub repository for use by the classical and quantum computing community.

arXiv:2503.14660•Quantum•Sep 21, 2026•0 citations

Link-middle-cut lower bounds for Clifford circuit synthesis

Søren Fuglede Jørgensen

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.

quant-pharXiv:2609.16208•Sep 16, 2026•0 citations

Quantum Logic Codes: Complete Transversal Logical Clifford Instruction Sets for High-Rate Stabilizer Quantum Error Correcting Codes

Adam Holmes

We study the structure and transversal logical capabilities of stabilizer quantum error correcting codes. Among our results, we identify universal lower bounds on circuit depth to generate a full logical Clifford algebra, and develop novel constructions of logical transversal gates including a new depth-one transversal phase $\mathrm{\overline{S}}$ gate in the rotated surface code and a depth-one intra-block $\mathrm{\overline{CZ}}$ gate in the 2D-toric code that generalizes to all odd distances and all lengths $L\ge3$, respectively. Finally, we construct a high-rate non-LDPC CSS code family with parameters $[[n,\sqrt{n},Θ({n^β})]]$ where $β\approx 0.2823$ in one demonstrated case, that provably possesses a constant-depth complete 2-local transversal logical Clifford basis instruction set architecture (ISA) composed of all individually targeted $\mathrm{\overline{S}}$, $\mathrm{\overline{SHS}} = \sqrt{X}$, and $\mathrm{\overline{CZ}}$ gates. This ISA is depth-one for certain subfamilies that we design and generally constant-depth under certain conditions. The code family is built from a small code with parameters $[[n_0, 2, d_0]]$, and is tunable in the standard way: it tiles out to form utility-scale logical qubit counts, and it scales up through concatenation to achieve higher distances and error suppression. We show that this construction preserves the depth-one complete transversal logical Clifford basis ISA when composed with these commuting construction actions, inheriting structure from the core codes so that at scale the complete logical Clifford basis ISA remains depth-one up to depth-two addressable operations between tiled cores. We call these Quantum Logic Codes.

quant-pharXiv:2606.13521•Jun 12, 2026•0 citations

CNOT-Optimal Clifford Synthesis as SAT

Irfansha Shaik, Jaco van de Pol

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.

arXiv:2504.00634•Leibniz international proceedings in informatics•Jan 1, 2025•0 citations

Good Stabilizer Codes from Shallow Clifford Circuits with Random Matchings

Emile Anand, Elia Gorokhovsky, Jennifer Hritz +1 more

Encoding quantum information with low circuit overhead is a fundamental challenge in fault-tolerant quantum computation. Random circuits provide a natural mechanism for rapidly spreading logical information through simple gates applied in parallel. Brown and Fawzi showed that random Clifford circuits on two-qubit Clifford gates provide such encoders that achieve the quantum Gilbert-Varshamov rate-distance tradeoff with depth $O(\log^3 n)$. We show that the same asymptotic tradeoff is attained in optimal $O(\log n)$ depth under a gate distribution with a more restricted support. For every fixed $δ>0$ and sufficiently large $n$, if $\frac kn < 1 - H(\frac{d}{n}) - \frac{d}{n}\log_2 3 - δ$, we can construct random circuits of depth $O(\log n)$ which define, with high probability, an $[n,k]$ stabilizer code of distance at least $d+1$, which matches the $Ω(\log n)$ light-cone lower bound for linear distance encoders. Our ensemble employs a random matching circuit architecture consisting of $T$ independent permutation-invariant layers. In each layer, the qubits are paired up by a uniformly random perfect matching, and a random independent two-qubit Clifford gate is applied to each pair. The gate distribution need not be uniform over, or even have full support on, the two-qubit Clifford group; rather, we allow for very general distributions on Clifford gates satisfying three regularity conditions. In particular, the construction can be implemented using $n/2$ CNOT gates on randomly matched pairs in each layer, with parallel one-qubit Clifford twirls. These regularity conditions allow us to reduce the second-moment dynamics of our random circuits to a reversible Markov chain on binary support strings. We establish logarithmic hitting-time bounds for this Markov chain and comparisons of its stationary distribution to prove the coding properties of the circuits.

quant-pharXiv:2608.18536•Aug 20, 2026•0 citations
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.
Abstract The W state is a key resource for quantum communication and distributed quantum computing. Its entanglement survives the loss of any single qubit. Preparing the W state exactly is nevertheless hard in fault-tolerant architectures. The amplitude 1/√3 lies outside the ring Z[1/√2, i]. So no Clifford+T unitary can prepare the three-qubit W state exactly, and deterministic circuits must approximate the required rotation at a T-count that grows as log(1/ϵ). We present a heralded protocol that prepares the three-qubit W state exactly using Clifford gates and a single non-Clifford operation. A shallow Clifford circuit with two CNOT gates first prepares an equal superposition of |001⟩, |010⟩, |100⟩ and |111⟩. A logical-AND measurement on one ancilla then removes the |111⟩ component without disturbing the remaining coherent superposition. The protocol succeeds with probability 3/4, a failed attempt leaves the known product state |111⟩, and each attempt consumes four T gates or one |CCZ⟩ magic state. This gives an expected cost of about 5.33 T gates independent of target precision. We prove that some non-Clifford step is necessary, and by exhaustively enumerating all 315,057,600 six-qubit stabilizer tensors we show that no post-selected Clifford circuit with three or fewer T gates outputs the W state. Every heralded Clifford+T preparation of the W state therefore uses at least four T gates per successful run, and our protocol attains this bound. The protocol uses 6 to 19 times fewer T gates than gate synthesis at precisions between 10−3 and 10−10. We compare it with a deterministic circuit using an exact repeat-untilsuccess rotation, which achieves a slightly lower expected cost of about 4.67 T gates, and discuss implementation in modular architectures and extensions to N-qubit W states. Note on this version. This version replaces and corrects the first version of this preprint (“A Tcount Zero Protocol for Heralded W-state Preparation via Clifford-only Gates”). The claim there that the W state can be prepared with Clifford gates alone is incorrect: as shown here, some non-Clifford step is necessary, and at least four T gates are needed per successful run.
Efficiently implementing Clifford circuits is crucial for quantum error correction and quantum algorithms. Linear reversible circuits, equivalent to circuits composed of CNOT\xspace gates, have important applications in classical computing. In this work we present methods for CNOT\xspace and general Clifford circuit synthesis which can be used to minimise either the entangling two-qubit gate count or the circuit depth. We present three families of algorithms - optimal synthesis which works on small circuits, A* synthesis for intermediate-size circuits and greedy synthesis for large circuits. We benchmark against existing methods, including rustiq, tket and qiskit and show that our approach results in circuits with lower two-qubit gate count. For encoding circuits, our methods outperform previous reinforcement learning results and find a lower two-qubit gate count circuit for the Golay code than previously known. The algorithms have been implemented in a GitHub repository for use by the classical and quantum computing community.
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 nnn qubits with kkk cycles requires exactly 3(n−k)3(n-k)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∗A^*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∗A^*A∗ heuristics to improve the CNOT counts obtained through heuristic search.
We study the structure and transversal logical capabilities of stabilizer quantum error correcting codes. Among our results, we identify universal lower bounds on circuit depth to generate a full logical Clifford algebra, and develop novel constructions of logical transversal gates including a new depth-one transversal phase S‾\mathrm{\overline{S}}S gate in the rotated surface code and a depth-one intra-block CZ‾\mathrm{\overline{CZ}}CZ gate in the 2D-toric code that generalizes to all odd distances and all lengths L≥3L\ge3L≥3, respectively. Finally, we construct a high-rate non-LDPC CSS code family with parameters [[n,n,Θ(nβ)]][[n,\sqrt{n},Θ({n^β})]][[n,n​,Θ(nβ)]] where β≈0.2823β\approx 0.2823β≈0.2823 in one demonstrated case, that provably possesses a constant-depth complete 2-local transversal logical Clifford basis instruction set architecture (ISA) composed of all individually targeted S‾\mathrm{\overline{S}}S, SHS‾=X\mathrm{\overline{SHS}} = \sqrt{X}SHS=X​, and CZ‾\mathrm{\overline{CZ}}CZ gates. This ISA is depth-one for certain subfamilies that we design and generally constant-depth under certain conditions. The code family is built from a small code with parameters [[n0,2,d0]][[n_0, 2, d_0]][[n0​,2,d0​]], and is tunable in the standard way: it tiles out to form utility-scale logical qubit counts, and it scales up through concatenation to achieve higher distances and error suppression. We show that this construction preserves the depth-one complete transversal logical Clifford basis ISA when composed with these commuting construction actions, inheriting structure from the core codes so that at scale the complete logical Clifford basis ISA remains depth-one up to depth-two addressable operations between tiled cores. We call these Quantum Logic Codes.
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.
Encoding quantum information with low circuit overhead is a fundamental challenge in fault-tolerant quantum computation. Random circuits provide a natural mechanism for rapidly spreading logical information through simple gates applied in parallel. Brown and Fawzi showed that random Clifford circuits on two-qubit Clifford gates provide such encoders that achieve the quantum Gilbert-Varshamov rate-distance tradeoff with depth O(log⁡3n)O(\log^3 n)O(log3n). We show that the same asymptotic tradeoff is attained in optimal O(log⁡n)O(\log n)O(logn) depth under a gate distribution with a more restricted support. For every fixed δ>0δ>0δ>0 and sufficiently large nnn, if kn<1−H(dn)−dnlog⁡23−δ\frac kn < 1 - H(\frac{d}{n}) - \frac{d}{n}\log_2 3 - δnk​<1−H(nd​)−nd​log2​3−δ, we can construct random circuits of depth O(log⁡n)O(\log n)O(logn) which define, with high probability, an [n,k][n,k][n,k] stabilizer code of distance at least d+1d+1d+1, which matches the Ω(log⁡n)Ω(\log n)Ω(logn) light-cone lower bound for linear distance encoders. Our ensemble employs a random matching circuit architecture consisting of TTT independent permutation-invariant layers. In each layer, the qubits are paired up by a uniformly random perfect matching, and a random independent two-qubit Clifford gate is applied to each pair. The gate distribution need not be uniform over, or even have full support on, the two-qubit Clifford group; rather, we allow for very general distributions on Clifford gates satisfying three regularity conditions. In particular, the construction can be implemented using n/2n/2n/2 CNOT gates on randomly matched pairs in each layer, with parallel one-qubit Clifford twirls. These regularity conditions allow us to reduce the second-moment dynamics of our random circuits to a reversible Markov chain on binary support strings. We establish logarithmic hitting-time bounds for this Markov chain and comparisons of its stationary distribution to prove the coding properties of the circuits.