CNOT-count and depth frontier for quantum Golay state preparation

Problem

What is the exact CNOT-count and depth frontier for ancilla-free Clifford preparation of the logical zero state of the \([[23,1,7]]_2\) quantum Golay code?

Let \(C_{23}\) be the classical binary \([23,12,7]\) Golay code and

\begin{equation} |0_G\rangle=2^{-11/2}\sum_{c\in C_{23}^{\perp}}|c\rangle. \tag{1} \end{equation}

Consider Clifford circuits on exactly \(23\) qubits initialized in \(|0\rangle^{\otimes23}\), with arbitrary connectivity, free single-qubit Clifford gates, and unit-cost CNOT gates, but no ancillas, measurements, or postselection. If \(N_{\mathrm{CX}}(U)\) is the CNOT count and \(d_2(U)\) the number of disjoint two-qubit layers, define

\begin{equation} g_G(D)=\min\left\{N_{\mathrm{CX}}(U): U|0\rangle^{\otimes23}=e^{i\theta}|0_G\rangle,\ d_2(U)\leq D\right\}. \tag{2} \end{equation}

Determine \(g_G(\infty)\) and the tradeoff \(g_G(D)\) in Eq. (2), particularly for \(D=7\) and \(D=8\), for the state in Eq. (1).

Source

The question is explicitly posed or retained as open in the cited primary literature [Paetznick12]. The statement is rewritten here to make its hypotheses and success criterion self-contained.

Progress

This is a precise circuit-model formulation of an explicitly published Golay preparation question, not a conjecture that a particular currently known circuit is optimal.
Original open question. Paetznick and Reichardt explicitly ask in Section 6 how to prepare the Golay logical zero state with the fewest CNOT gates while respecting depth bounds. Their overlap-based construction uses \(57\) CNOT gates in seven parallel rounds. They also distinguish this unverified preparation circuit from the subsequent verification required for fault tolerance [Paetznick12], Sections 3 and 6.
Subsequent constructive progress. The relevant preparation benchmarks are:
Source and method: Paetznick–Reichardt overlap construction [Paetznick12]; Two-qubit gate count: 57; Two-qubit depth: 7; What the result establishes: Explicit preparation circuit, not an optimality proof. Source and method: Webster–Koutsioumpas–Browne A* search [Webster25]; Two-qubit gate count: 56; Two-qubit depth: 17; What the result establishes: Improved gate count; the depth is also tabulated in [Doherty26]. Source and method: Doherty et al., beam search or model-free reinforcement learning [Doherty26]; Two-qubit gate count: 45; Two-qubit depth: 7; What the result establishes: Improved preparation at depth seven. Source and method: Doherty et al., QuSynth [Doherty26]; Two-qubit gate count: 44; Two-qubit depth: 8; What the result establishes: Smallest gate count established by the cited searches. Source and method: Peham et al., rollout synthesis [Peham26]; Two-qubit gate count: 45; Two-qubit depth: 10; What the result establishes: Independent subsequent construction; their note added acknowledges the \(44\)-gate, depth-eight result.
Doherty et al. count entangling gates locally equivalent to CNOT, including controlled-\(Z\). With free local Clifford gates these have the same unit cost as a CNOT; replacing them by CNOTs preserves two-qubit count and depth. Their benchmark therefore yields the upper bounds [Doherty26], Section V and Table I

\begin{equation} g_G(7)\le45, \qquad g_G(8)\le44, \qquad g_G(\infty)\le44. \tag{3} \end{equation}

The displayed definitions, constraints, and target bounds are recorded in Eqs. (3).
These inequalities are not established equalities. The explicit \(44\)-gate construction defeats the older question of whether one can merely improve on \(56\) or \(57\) gates; it does not determine the optimum.
Latest-version and task distinctions. Reference [Webster25] was checked in its September 7, 2026 revision. Its \(56\)-gate Golay result comes from A* search, not its reinforcement-learning result. Reading that paper alone would miss the stronger March 2026 benchmark [Doherty26]. The May 2026 paper [Peham26] independently acknowledges the \(44\)-gate construction and also gives a \(49\)-CNOT encoder for an arbitrary logical input. The latter solves a different synthesis task from preparing one fixed logical state and should not be entered as a competing \(|0_G\rangle\) preparation record.
Lower-bound perspective. Kumabe, Mori, and Yoshimura provide structural lower bounds for graph-state preparation in terms of graph rank-width, an entanglement-related graph parameter. Their framework even permits ancillary qubits and measurements, and hence can potentially supply lower bounds for the stricter model above. However, their result is not a matching, Golay-specific certificate for the \(44\)-gate construction [Kumabe26]. Establishing a useful invariant of the Golay state, or completing a certified exact search, remains a potential route to an optimality result.
Scope of the evidence. The original question, the newer synthesis papers, their reported Golay benchmarks, and their publication or revision dates were checked. No located source establishes the exact Golay minimum or a complete gate-count/depth frontier. The distinction between a successful search and an exhaustive optimality certificate is essential here.

Comment

The unresolved issue is certified optimality, including the tradeoff with two-qubit depth, rather than the existence of a Golay preparation circuit. The cited constructions give an upper bound of \(44\) gates. None establishes either \(44\)-gate optimality or depth-eight optimality. Adding verification, changing connectivity, allowing measurements, or encoding an arbitrary logical input changes the problem and requires separate resource accounting. Unpublished or unindexed work is outside this record.

References

[Paetznick12]: Adam Paetznick and Ben W. Reichardt, “Fault-tolerant ancilla preparation and noise threshold lower bounds for the 23-qubit Golay code,” Quantum Information & Computation 12, 1034–1080 (2012). Original preprint June 11, 2011; revised April 12, 2013. See the overlap preparation construction and Figure 4, and the explicit open question in Section 6.arXiv
[Webster25]: Mark Webster, Stergios Koutsioumpas, and Dan E. Browne, “Heuristic and Optimal Synthesis of CNOT and Clifford Circuits,” arXiv:2503.14660. Original preprint March 18, 2025; version 3 dated September 7, 2026. Version checked. See the state-preparation benchmarks, especially Table 5, and the description of the bounded search.link
[Doherty26]: Michael Doherty, Matteo Puviani, Jasmine Brewer, Gabriel Matos, David Amaro, Ben Criger, and David T. Stephen, “Fast stabilizer state preparation via AI-optimized graph decimation,” arXiv:2603.17743, March 18, 2026. arXiv record. See Section V, Table I, and Appendix A for the treatment of CSS states.arXiv
[Peham26]: Tom Peham, Matthew Steinberg, Robert Wille, and Sascha Heußen, “Synthesis and Optimization of Encoding Circuits for Fault-Tolerant Quantum Computation,” arXiv:2605.15266, May 14, 2026. arXiv record. See Section V.B on best-found circuits and the acknowledgment discussion following Section VI acknowledging the \(44\)-gate Golay preparation circuit.arXiv
[Kumabe26]: Soh Kumabe, Ryuhei Mori, and Yusei Yoshimura, “Complexity of graph-state preparation by Clifford circuits,” Quantum 10, 2165 (July 18, 2026). DOI:10.22331/q-2026-07-18-2165; This is general lower-bound machinery, not a solution of the Golay optimization problem.DOI arXiv

CNOT-count and depth frontier for quantum Golay state preparation

Problem

Source

Progress

Comment

References

Cite this problem

BibTeX

Plain text

Problem

Source

Progress

Comment

References

Related problems