Fewest CNOT gates to prepare the Golay code's logical zero

The 23-qubit Golay code protects one qubit against any three errors, and fault-tolerant schemes built on it must prepare its encoded zero state again and again. How few two-qubit gates does that take? The best circuits have dropped from 57 gates in 2011 to 44 in 2026, but nobody knows the minimum, or how it trades off against circuit depth.

Problem

Let $C_{23}$ be the binary $[23,12,7]$ Golay code. The logical zero of the $[[23,1,7]]$ quantum Golay code is the uniform superposition over the dual code,

$$\lvert 0_G\rangle=2^{-11/2}\sum_{c\in C_{23}^{\perp}}\lvert c\rangle .$$

Consider Clifford circuits on exactly 23 qubits that start from $\lvert0\rangle^{\otimes 23}$, with any connectivity, single-qubit Clifford gates for free and unit cost per CNOT, and no ancillas, measurements or postselection. For a depth budget $D$, let $g(D)$ be the fewest CNOTs in such a circuit that outputs $\lvert0_G\rangle$ up to a global phase using at most $D$ layers of two-qubit gates.

Question. Determine $g(\infty)$, and the trade-off $g(D)$, in particular $g(7)$ and $g(8)$.

Background

Paetznick and Reichardt studied fault-tolerant ancilla preparation for the Golay code in 2011 and built by hand a 57-CNOT circuit in seven rounds. They noted that it is not necessarily optimal and asked for a way to find the preparation circuit with the fewest CNOTs within a depth bound [1]. Cheaper state preparation lowers the overhead of every error-correction round, which is why this small, concrete instance has become a benchmark for circuit-synthesis methods [2, 3, 4].

What is known

• 57 CNOTs at two-qubit depth 7: the original hand construction [1].
• 56 two-qubit gates from an A* search for Clifford circuit synthesis [2]; Doherty et al. list its depth as 17 [3].
• 45 gates at depth 7, and 44 gates at depth 8, from searches based on graph-state decimation, beam search, reinforcement learning and tree search (Doherty et al., 2026). Their circuits use CX, CY and CZ gates, each a CNOT up to single-qubit Clifford gates, so the counts carry over [3].
• 45 CNOTs at depth 10 from independent rollout-based synthesis (Peham et al., 2026), whose authors acknowledge the 44-gate circuit [4].

So $g(7)\le45$, $g(8)\le44$ and $g(\infty)\le44$. No matching lower bound is known; none of these searches is exhaustive.

What would count as progress

• A circuit with at most 43 CNOTs, or with at most 44 CNOTs at depth 7. It can be verified in well under a second by stabilizer simulation: check that the output is stabilized by the 22 stabilizer generators of the code and by logical $Z$.
• A certificate that 44 is optimal, for example from an exhaustive search with symmetry reduction, or a lower bound from an invariant of $\lvert0_G\rangle$ that beats simple counting arguments.
• The same questions with the depth fixed at 7 or 8, which matter for fault-tolerant schedules.

References

1. A. Paetznick and B. W. Reichardt, "Fault-tolerant ancilla preparation and noise threshold lower bounds for the 23-qubit Golay code", Quantum Information & Computation 12, 1034–1080 (2012). arXiv:1106.2190
2. M. Webster, S. Koutsioumpas and D. E. Browne, "Heuristic and optimal synthesis of CNOT and Clifford circuits", Quantum 10, 2212 (2026). doi:10.22331/q-2026-09-21-2212
3. M. Doherty, M. Puviani, J. Brewer, G. Matos, D. Amaro, B. Criger and D. T. Stephen, "Fast stabilizer state preparation via AI-optimized graph decimation", preprint (2026). arXiv:2603.17743
4. T. Peham, M. Steinberg, R. Wille and S. Heußen, "Synthesis and optimization of encoding circuits for fault-tolerant quantum computation", preprint (2026). arXiv:2605.15266

Source

Imported from QIQCOP Zoo op_c847b635f53b0812, curated by Bikun Li, Qicheng Tang, Changhao Li, Chengkai Zhu, Minbo Gao, Zhong-Xia Shang, Bin Cheng and Naixu Guo. Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.