On Fault Tolerant Single-Shot Logical State Preparation and Robust Long-Range Entanglement

In our single-shot logical state preparation result discussed above, the classical decoding procedure (computing $P(s)$ from $s$) relies on an information-theoretic minimum weight decoder, and is not necessarily computationally efficient.⁴⁴4By dynamic programming, the decoding algorithm can be made to run in $\le T\cdot \exp \left(n\right)$ time. A natural question is whether an efficient decoder that runs in $\mathrm{𝗉𝗈𝗅𝗒}(n)$ time exists for single-shot logical state preparation, especially if the code is known to have an efficient decoder for quantum error correction.⁵⁵5We emphasize the distinction between a decoder for error-correction, and a decoder for state preparation. Here, we complement our results by showing a simple reduction to the efficient decoding of logical state preparation based on repeated syndrome measurements.

In other words, one can tradeoff time for space in logical state preparation. As discussed earlier, this reduction stems from mapping the repeated measurements circuit to a constant depth circuit via measurement based quantum computation, and as we illustrate naturally gives rise to the alternating tanner graph state $|\mathrm{ATG}⟩$.

Next we show that the ATG provides a powerful framework that goes beyond the preparation of encoded $|\overline{0}⟩$ and $|\overline{+}⟩$ as in logical state preparation based on repeated measurements, due to the flexibility in choosing different measurement patterns in the ATG. As an example, we show fault tolerant single-shot preparation of the encoded GHZ state

for any $m\ge 2$ in an arbitrary quantum LDPC code. Here we summarize the algorithm for GHZ state preparation, and then discuss this result from the perspective of robust long-range entanglement and noisy shallow circuits.

To prepare the GHZ state, we measure the ATG in the following pattern, depicted (horizontally) in Figure 2(a): we measure all the check qubits of all code blocks (blue and red in Figure 1), as well as all code qubits in the bulk (blue in Figure 2(a)), with the exception of a careful choice of $m$ layers of $n$ code qubits (in orange). We prove that the resulting state, after minimum-weight decoding and feedforward, is in fact the encoded GHZ state across the $m$ blocks (Figure 2(b)) up to residual stochastic noise.

This generalizes the RBH construction [23] for the surface code with $m=2$ and $k=1$, that is, the encoded Bell state $\frac{1}{\sqrt{2}}\left(|\overline{00}⟩+|\overline{11}⟩\right)$ in the surface code. Let us review the features of the entanglement in the resulting GHZ state:

• $\mathrm{■}$

  Noise robust. The preparation procedure uses a noisy constant depth circuit (with noise rate below a constant threshold). Yet, the resulting GHZ state is encoded in a LDPC code and is subject to residual local stochastic noise that is correctable with the code.

• $\mathrm{■}$

  Generic. The construction works for arbitrary quantum LDPC codes.

• $\mathrm{■}$

  Macroscopic. The final state encodes $m\cdot k$ logical qubits into $m\cdot n$ physical qubits, which can achieve a constant encoding rate using high-rate codes such as hypergraph product codes [26, 17].

• $\mathrm{■}$

  Long range. There are two aspects of long range entanglement: the first is the entanglement among physical qubits in each code block (which can exhibit topological order), the second is the logical GHZ entanglement that spans $m$ code blocks.

Finally, we discuss this result from the perspective of noisy shallow quantum circuits. The first step of this state preparation algorithm is to apply a constant depth circuit on a volume of qubits. At this point, there is no long-range entanglement at all. However, after the bulk (blue in Figure 2(a)) is measured, long-range entanglement is created across the orange blocks (Figure 2(b)): the subsequent decoding and feedforward operations are only used to correct the state into the desired GHZ state, but cannot create entanglement. Therefore, the GHZ-type entanglement is created by the teleportation effect of measurement. Interestingly, this teleportation effect is robust to noise.

We remark that Theorem 3 implies Theorem 1 as a special case. An interesting future direction is to explore whether there exists other families of interesting states that can be prepared using the ATG framework.

The fault-tolerance of our single-shot logical state preparation scheme has two main components. First, we identify the stabilizer structure of $|\mathrm{ATG}⟩$. As remarked earlier, the fault tolerance arises from redundancies in the ancilla qubits. Concretely, that manifests in the redundancies of the stabilizers of $|\mathrm{ATG}⟩$, which contains certain “meta-checks”. Second, we adapt the clustering arguments by [18, 12] for decoding quantum LDPC codes from random errors to our setting, and develop analogous techniques to argue that the meta-checks contain enough redundancy to be robust against random errors.
The meta-check information. Following [7], inside the $|\mathrm{ATG}⟩$ (which is a stabilizer state), one can define stabilizers which cleanly factorize into a product of $X$ Pauli’s on the bulk of the graph state. We refer to these stabilizers as “meta-checks”, since
1. After measuring the bulk in the $X$ basis, they remain stabilizers of the post-measurement state,
2. They inbuild redundancies (“syndrome of syndromes”) into the measured string $s$.
These redundancies will later allow us to use $s$ to infer errors that occur on the bulk, and in turn, correctly decode the error $P(s)$ for the qubits on the boundary. Here we give an example and defer a rigorous exposition to [2, Section 3.2]. Recall that on every even layer $t$ of the $\mathrm{ATG}$, there is a copy of the $Z$-Tanner graph lying on the layers $t-1$ and $t+1$ adjacent to it. Now, consider a $Z$-check of the code denoted as $c$, and let $\mathrm{𝖲𝗎𝗉𝗉}(c)\subseteq [n]$ be the set of qubits it acts on. We show that the following operator

which applies a Pauli-$X$ on the copies of the check qubit $c$ in layers $t-1$ and $t+1$, as well as the qubits supported in the check in layer $t$, is a stabilizer of $|\mathrm{ATG}⟩$.

While perhaps a bit abstract at first, this operator captures the change in the $Z$ syndrome after a layer of data-errors on the code and measurement errors on the checks: akin to the redundancy between adjacent syndrome measurements that appear in a repeated syndrome measurement protocol. The fact that these stabilizers factorize cleanly into products of $X$ Paulis is non-trivial and depends carefully on the structure of $|\mathrm{ATG}⟩$, which we discuss further in [2, Section 3.2].
The clustering argument. [18, 12] showed that any quantum LDPC code can correct random Pauli errors (below a constant threshold noise rate), even in the presence of syndrome measurement errors, by repeating the syndrome measurements $T$ times and running an information-theoretic minimum weight decoder. Their proof reasoned that the data-errors and syndrome-errors could be arranged in a low degree graph known as the syndrome adjacency graph, wherein the locations of mismatch errors (where the output of the decoder does not match the true error) clusters into connected components. By a percolation argument on this low-degree graph, one can argue these clusters are unlikely to “contrive” into configurations that induce logical errors on the code. Roughly speaking, the probability of a logical error is upper bounded by

where only clusters of size larger than the code distance $d$ can incur logical errors, and $z$ is the degree of the graph.⁶⁶6A function only of the locality of the LDPC code. We assumed the noise rate is bounded by a threshold for the geometric series to converge.

Here, we broadly follow this strategy and construct an analogous low-degree syndrome adjacency graph which captures where our min-weight decoder incorrectly guesses a data or check error. Unfortunately, making this argument rigorous is easier said than done. Arguably the main challenge lies in relating the size of clusters of mismatch errors, to the number of true physical errors which lie within the cluster, to properly claim the decay rate $p^{\mathrm{\Omega }(s)}$ with the cluster size. As we discuss in [2, Section 5] and [2, Appendix C], this calculation is highly dependent on the boundary conditions of the syndrome adjacency graph, tailored for Bell states and to GHZ states.

As a direct corollary, our single-shot logical state preparation can be used as the basis of a fault tolerant implementation of a shallow quantum circuit.

Here we simply run our single-shot logical state preparation scheme to prepare encoded initial states, and then directly apply transversal gates. Since the logical circuit is constant depth, the residual local stochastic noise still remains local stochastic, and the logical $Z$ or $X$ measurements at the end can be decoded using the code.

A natural question is whether we can remove the mid-circuit measurement and feedforward, and implement an ideal shallow quantum circuit purely via a noisy shallow quantum circuit. Ref. [7] gives such an example: starting from RBH, they directly apply a logical Clifford circuit without correcting the Pauli error $P(s)$. However, since the logical circuit is Clifford, the Pauli error $P(s)$ is propagated through the circuit and corrected at the end. Our result similarly implies a more general version:

Note that we do not address the issue of decoding efficiency. In particular, although Corollary 5 does not need mid-circuit decoding, the decoding at the end of the circuit may still be inefficient. An interesting direction is to explore if Corollary 5 can be the basis of other quantum advantage experiments with noisy shallow quantum circuits against shallow classical circuits, as in [7].

Beyond GHZ state preparation, we show that single-shot logical state preparation can also be achieved for more general stabilizer states, using a combination of the ATG and Steane’s logical measurement. Let $|\psi ⟩$ be a $m$-qubit stabilizer state with the following structure: there exists a set of $m$ stabilizer generators that can be divided into two sets $S_X\subseteq {\{I,X\}}^{\otimes m}$ and $S_Z\subseteq {\{I,Z\}}^{\otimes m}$, such that either $S_X$ or $S_Z$ has constant weight and degree. The $m$-qubit GHZ state is such an example, where $S_X=\{X^{\otimes m}\}$ and $S_Z=\{Z_1{Z}_2,Z_2{Z}_3,\mathrm{\dots },Z_{m-1}{Z}_m\}$. We prove fault tolerant single-shot preparation for any such state $|\psi ⟩$ encoded across $m$ copies of an arbitrary quantum LDPC code. See [2, Appendix D] for more details.

A closely related concept to our work is single-shot quantum error correction [5]: consider an encoded code block subject to random errors, it is shown that for certain codes a single round of syndrome measurement suffices to correct the error (instead of performing repeated syndrome measurements), even in the presence of syndrome measurement errors. Examples include high-dimensional color codes [4, 5] and toric codes [19], hypergraph product codes [11], quantum Tanner codes [13] and hyperbolic codes [9].

As the ATG is closely related to repeated syndrome measurements, it is natural to ask whether single-shot logical state preparation with constant space overhead exists for those codes, or more generally, for any code with single-shot error correction. While this is proven for 3D gauge color codes [4, 5], it is unclear whether a general reduction from single-shot logical state preparation to single-shot error correction exists. The key issue is that single-shot error correction is defined in the context of correcting errors on an existing encoded code block, while single-shot logical state preparation is about preparing an encoded code state from scratch. We leave further exploration of this issue for future work; it is an interesting question in the context of reducing the spacetime overhead of quantum fault tolerance (also see [27]).