# Low-cost noise reduction for Clifford circuits

Nicolas Delfosse  Edwin Tham  IonQ Inc.

###### Abstract

We propose a Clifford noise reduction (CliNR) scheme that provides a reduction
of the logical error rate of Clifford circuit with lower overhead than error
correction and without the exponential sampling overhead of error mitigation.
CliNR implements Clifford circuits by splitting them into sub-circuits that
are performed using gate teleportation. A few random stabilizer measurements
are used to detect errors in the resources states consumed by the gate
teleportation. This can be seen as a teleported version of the CPC scheme [1,
2, 3], with offline fault-detection making it scalable. We prove that CliNR
achieves a vanishing logical error rate for families of $n$-qubit Clifford
circuits with size $s$ such that $nsp^{2}$ goes to 0, where $p$ is the
physical error rate, meaning that it reaches the regime $ns=o(1/p^{2})$
whereas the direct implementation is limited to $s=o(1/p)$. Moreover, CliNR
uses only $3n+1$ qubits, $2s+o(s)$ gates and has zero rejection rate. This
small overhead makes it more practical than quantum error correction in the
near term and our numerical simulations show that CliNR provides a reduction
of the logical error rate in relevant noise regimes.

##  I Introduction

Quantum error correction (QEC) and quantum error mitigation (QEM) are heavily-
studied techniques for coping with imperfect quantum hardware.

Fault-tolerant quantum computing (FTQC) relies on quantum error correction [4]
to achieve a vanishing logical error rate at constant physical error rate
(below some threshold value) [5, 6]. This approach is scalable as it comes
with a polynomial asymptotic overhead in terms of qubit and gate count, but
the error correction overhead is massive in practice. For example, the
factorization of RSA-2,048 may require surface codes using 1,457 physical
qubits per logical qubit [7]. In the asymptotic regime, constructions based on
quantum LDPC codes and code concatenation achieve smaller overhead in terms of
qubit count [8, 9, 10, 11, 12, 13] or gate count [14, 15]. However, the cost
remains daunting for explicit examples. Recent simulations of quantum LDPC
codes outperforming surface codes [16, 17, 18, 19] consume respectively 49,
32, 24 and 22 physical qubits per logical qubit, and extra qubits are needed
to required for logical operations. For comparison, the scheme proposed in
this paper uses only 3 physical qubits per logical qubit.

Over the past few years, several building blocks of a fault-tolerant quantum
computing architecture have been demonstrated experimentally [20, 21, 22, 23,
24, 25, 26, 27, 28, 29]. These experiments provide critical insights into the
long-term goal of building a large-scale fault-tolerant quantum computer.
However, for current machines, it may be preferable to use more qubit-
efficient techniques like quantum error mitigation. Quantum error mitigation
includes a variety of techniques reducing the impact of noise in a quantum
circuit by collecting data from different variants of the circuit and post-
processing this data [30, 31, 32]. It is already used in today’s machines
because it consumes only few or no extra qubits. However, it is not a viable
solution for large quantum circuits because the sampling cost, i.e., the
number of circuit executions required, generally grows exponentially with the
size of the circuit.

In this work, we propose a scheme for noise reduction in Clifford circuits
that fills the gap between the regime of FTQC and QEM. This Clifford noise
reduction (CliNR) scheme is not fault-tolerant but it still reduces the
logical error rate of Clifford circuits in practically relevant regimes, and
it does so at the price of comparatively small overheads.

CliNR implements Clifford operations by gate teleportation [33], which allows
for offline preparation and checking of the associated stabilizer resource
state. A small number of random stabilizer measurements is used to detect
errors in that resource state. Gate teleportation is typically used to
implement logical $T$ gates, together with $T$ state distillation [34].
However, fault-tolerance requires measuring a complete set of stabilizer
generators of the $T$ state. In CliNR, we measure only a few stabilizer
generators to detect faults with a sufficiently large probability, ensuring
the fault detection circuit remains small.

Our scheme can be seen as a teleported version of the coherent parity-check
(CPC) scheme introduced in [1], which achieves a reduction of the logical
error rate (by $50\%$ in [2] and $34\%$ in [35]) by measuring a few parity-
checks. Increasing the number of parity-checks in CPC leads to a more
substantial reduction of the logical error rate, but results in an exponential
sampling overhead [3]. The use of gate teleportation in CliNR avoids this
issue because fault-detection is done offline – an ancilla state is prepared
and checked for faults, and then injected through gate teleportation only if
no faults are observed. If a fault is detected, only the ancilla state needs
to be re-prepared, obviating the need to restart the entire computation from
scratch. This advantage holds with large Clifford circuits, as well as
arbitrary quantum programs that can contain many Clifford sub-circuits, each
of which can be realized through a CliNR procedure.

For large Clifford circuits, the sampling overhead can be kept in check
through partitioning of the circuit into smaller sub-circuits with fewer
gates, with each subcircuit being implemented using CliNR. By adjusting the
size of the sub-circuits, CliNR provides an extra flexibility to optimize the
trade-off between the sampling overhead and the logical error rate. Another
advantage of our protocol is that the ancilla qubit used to measure the
stabilizers is kept active for a shorter time than ancilla qubits in the CPC
scheme, further reducing fault-detection noise stemming from idle errors.

We next consider the problem of implementing Clifford circuits with vanishing
logical error rate and low overhead in the regime of vanishing physical error
rate $p\rightarrow 0$. The direct implementation provides a vanishing logical
error rate for $n$-qubit Clifford circuits containing $s$ gates satisfying
$sp\rightarrow 0$. Theorem 2 achieves a vanishing logical error rate for
Clifford circuits with $nsp^{2}\rightarrow 0$, meaning that the CliNR reaches
circuits such that $ns=o(1/p^{2})$, while the direct implementation requires
$s=o(1/p)$. Corollary 2 shows that CliNR implements arbitrary $n$-qubit
Clifford unitaries (for which $s\lesssim n^{2}$) with vanishing logical error
rate for all $n=O(p^{-2/3})$, whereas the direct implementation only reaches
$O(p^{-1/2})$. Notably, CliNR accomplishes this error suppression while
consuming only $3n+1$ physical qubits and an average of $2s+o(s)$ single-qubit
and two-qubit gates.

The remainder of this paper is organized as follows. Background on quantum
circuits is provided in Section II. Section III describes the CliNR circuit
and presents our main results, Theorem 1, which provides a bounds on the
performance of the CliNR circuits and Theorem 2, which shows that one can
implement Clifford circuits with $ns=o(1/p^{2})$ with vanishing logical error
rate. Our numerical simulations are discussed in Section V. Appendix E
considers a special case of CliNR, applicable to sequences of $CZ$ gates with
reduced overheads, which could be relevant for chemistry applications [36].

##  II Implementation of a circuit

A circuit with size $s$ is a sequence of $s$ operations. Each operation is
either a preparation $|0\rangle$ or $|+\rangle$, a single-qubit unitary, a
controlled-Pauli ($CNOT=CX$, $CY$, or $CZ$), or the measurement of a qubit. A
measured qubit can be re-prepared and reused.

A Clifford circuit is a sequence of single-qubit Clifford unitaries and
controlled-Paulis. These circuits take as an input a $n$-qubit state and
output a $n$-qubit state.

We consider the standard circuit-level noise model with physical error rate
$p$. Preparations and single-qubit unitaries are followed by a Pauli error
$X$, $Y$ or $Z$ with probability $p/3$ each. Controlled-Paulis are followed by
one of the 15 non-trivial Pauli errors acting on their support with
probability $p/15$ each. Measurement outcomes are flipped with probability
$p$. Errors corresponding to different operations are independent. For now, we
assume that all operations have the same error rate $p$ and that idle qubits
are noiseless.

Faults in a Clifford circuit propagate through the circuit, resulting in an
error $E$ on the output state of the circuit that we refer to as the output
error. The output error can be computed by conjugating the circuit faults
through the circuit [37].

We say that a circuit $C^{\prime}$ implements a $n$-qubit Clifford circuit $C$
if, in the absence of fault, for any input state, $C^{\prime}$ produces the
same output state as $C$. The logical error rate for the implementation of $C$
with $C^{\prime}$, denoted ${p_{\log}}$, is defined to be the probability that
faults propagate into a non-trivial output error. In this definition, $C$ is
the ideal circuit we wish to execute and $C^{\prime}$ is the noisy circuit
effectively implemented. The circuit $C^{\prime}$ is not restricted to
Clifford unitaries and may contain measurements and ancilla qubits. The extra
qubits are traced-out at the end of the circuit to obtain a $n$-qubit output
state as in $C$.

The number of qubits $n^{\prime}$ and the size $s^{\prime}$ of the
implementation $C^{\prime}$ are random variables because the circuit
$C^{\prime}$ may contains random or adaptive operations. The qubit overhead,
denoted ${\omega_{\operatorname{Q}}}$, is defined as the ratio between the
maximum number of qubits of the circuit $C^{\prime}$ and the number of qubits
of $C$. The gate overhead, denoted ${\omega_{\operatorname{G}}}$, is defined
to be the ratio between the expected number of gates of $C^{\prime}$ and the
number of gates of $C$. For the qubit overhead, we use the maximum number of
qubits in $C^{\prime}$ instead of the expectation because these qubits must
physically exist in the machine, even if we do not use all of them at each
execution of $C^{\prime}$.

For example, the direct implementation of the circuit $C$ is the
implementation $C^{\prime}=C$. Its qubit and gate overhead is $1$ and its
logical error rate is upper bounded as ${p_{\log}}\leq g_{p}(s)$ where
$g_{p}(x)=1-(1-p)^{x}$ and $s$ is the size of $C$.

##  III Clifford noise reduction

Throughout this section, $C$ is a $n$-qubit Clifford circuit and $r,t\geq 1$
are two integers.

Figure 1:  The CliNR circuit (with $t=1$) implements a $n$-qubit Clifford
circuit $C$ by gate teleportation using $2n+1$ ancilla qubits. We insert $r$
stabilizer measurements before the CNOTs, to detect errors in the application
of $C$ on the ancilla qubits. Here $r=1$ and we measure the stabilizer $P$. If
a stabilizer measurement returns a non-trivial outcome, the circuit restarts.
Here $Q$ is a $n$-qubit Pauli operation that depends on the outcome of the
measurement of the first $2n$ qubits.

Let us first define the Clifford noise reduction circuit, denoted
$\operatorname{CliNR}_{t,r}(C)$, for $t=1$. The circuit
$\operatorname{CliNR}_{1,r}(C)$, represented in Fig. 1, acts on $3n+1$ qubits.
We refer to the first three blocks of $n$ qubits as first block, second block
and third block respectively and qubit $3n+1$ is an extra qubit. The circuit
$\operatorname{CliNR}_{1,r}(C)$ is made with the following operations.

  1. 1.

Prepare $n$ Bell states on qubits $n+i$ and $2n+i$ for $i=1,\dots,n$.

  2. 2.

Apply $C$ to the third block.

  3. 3.

Measure $r$ random stabilizers of the state supported on blocks two and three.

  4. 4.

If a stabilizer measurement returns a non-trivial outcome, restart the
circuit.

  5. 5.

Apply $CNOT_{i,n+i}$, followed by $H_{i}$, for $i=1,\dots,n$.

  6. 6.

Measure the first and second block and apply the operation $Q$ (defined below)
to the third block.

The stabilizers are measured sequentially using qubit $3n+1$ and a sequence of
up to $2n$ controlled-Pauli gates. Following [3], we select the $r$
independent stabilizers uniformly at random so that each stabilizer
measurement detect $50\%$ of the faults. A new set of $r$ random stabilizer
generators is selected for each run of the circuit.

If a stabilizer measurement returns a non-trivial outcome, we know that a
fault has occurred and we restart the circuit. Crucially, these faults do not
affect the input state $|\psi\rangle$ because they are detected before the
CNOTs connecting the first block to the last $2n+1$ qubits.

The final classically-controlled operation is

$\displaystyle
Q=\prod_{i=1}^{n}\left(C^{\dagger}X_{2n+i}C\right)^{o_{n+i}}\left(C^{\dagger}Z_{2n+i}C\right)^{o_{i}}$
(1)

where $o_{i}$ is the outcome of the measurement of the $i$ th qubit.

The main limitation of the CliNR implementation with $t=1$ is that the restart
probability increases rapidly as circuit size $s$ approaches $1/p$, resulting
in a large gate overhead. To maintain a low cost for larger circuits, we
decompose the input circuit $C$ into $t$ smaller sub-circuits and we apply
$\operatorname{CliNR}(1,r)$ to each of these sub-circuits.

For $t\geq 1$, the circuit $\operatorname{CliNR}_{t,r}(C)$ is defined by
writing $C$ as the concatenation of $t$ sub-circuits $C_{1},\dots,C_{t}$ and
by applying $\operatorname{CliNR}_{1,r}$ to each sub-circuit. In other words,
it is the concatenation of the circuits
$\operatorname{CliNR}_{1,r}(C_{1}),\dots,\operatorname{CliNR}_{1,r}(C_{t})$.
Formally, we need to swap the first and third blocks to concatenate two such
circuits. These swaps can be done fully in software by relabelling the qubits.

In what follows, we denote $s_{0}:=\lceil s/t\rceil$. If $s$ is a multiple of
$t$, each sub-circuit has size $s_{0}$. Otherwise, the first $s\mod t$ sub-
circuits have size $s_{0}$ and the remaining ones have size $s_{0}-1$.

######  Theorem 1.

The circuit $\operatorname{CliNR}_{t,r}(C)$ implements the Clifford circuit
$C$ with logical error rate

$\displaystyle{p_{\log}}\leq$ $\displaystyle
t\cdot\frac{g_{p}(3n+s_{0})2^{-r}+2g_{p}(2n+3)+g_{p}(5n)}{(1-p)^{m_{0}}}$ (2)

where $m_{0}=3n+s_{0}+(2n+3)r$. Moreover, the overhead satisfies
${\omega_{\operatorname{Q}}}=3+\frac{1}{n}$ and
${\omega_{\operatorname{G}}}\leq\frac{10n}{s_{0}}+\frac{2m_{0}}{s_{0}(1-p)^{m_{0}}}$.

This result is proven in Appendix B. This bound on the logical error rate only
holds for Clifford circuits because then $Q$ is comprised of just $n$ single-
qubit Pauli gates. When $C$ is non-Clifford, $Q$ is more complex and generally
consists of longer sequence of noisy gates.

##  IV The $snp^{2}$ threshold

Consider the problem of implementing $n$-qubit Clifford circuits with
vanishing logical error rate and low overhead, in the regime where the
physical error rate $p$ goes to 0.

We are given a family $(C_{j})_{j\in{\mathbb{N}}}$ of Clifford circuits,
acting on $n_{j}$ qubits with size $s_{j}$, implemented with qubits with
physical error rate $p_{j}$. To keep the notation simple, we omit the index
$j$ and we write $sp\rightarrow 0$ and $snp^{2}\rightarrow 0$.

The expected number of faults in a circuit with size $s$ is $sp$. Therefore,
if $sp\rightarrow 0$, the direct implementation achieves a vanishing logical
error rate. The following result shows that CliNR goes beyond this threshold.

######  Theorem 2 ($snp^{2}$ threshold).

Consider a family of $n$-qubit Clifford circuits with size $s$. If
$snp^{2}\rightarrow 0$, then we can implement these circuits with vanishing
logical error rate. Moreover, we have $\limsup{\omega_{\operatorname{Q}}}\leq
3$ and $\limsup{\omega_{\operatorname{G}}}\leq 2$.

This result reaches circuits with size up to $s=o(1/p^{2})$, whereas the
direct implementation achieves a vanishing logical error rate only if
$s=o(1/p)$. It is based on the CliNR implementation with parameters $t,r$
given in Eq. 5.

###### Proof.

Let $\varepsilon:=snp^{2}$. By assumption, we have $\varepsilon\rightarrow 0$.
If $s<\frac{\varepsilon^{1/4}}{p}$, then $s=o(1/p)$ and the direct
implementation is enough to achieve a vanishing logical error rate.

In the remainder of this proof, assume that
$s\geq\frac{\varepsilon^{1/4}}{p}$. Then, we have

$\displaystyle
n=\frac{\varepsilon}{sp^{2}}\leq\frac{\varepsilon^{3/4}}{p}=o\left(\frac{1}{p}\right)$
(3)

and

$\displaystyle\frac{n}{s}\leq\sqrt{\varepsilon}\rightarrow 0\cdot$ (4)

Consider $C^{\prime}=\operatorname{CliNR}_{t,r}(C)$ with

$\displaystyle r:=\left\lfloor\log(\frac{s}{n})\right\rfloor\text{ and
}t:=\left\lfloor\sqrt{\frac{s}{n}}\right\rfloor\cdot$ (5)

We want to apply Lemma 2, proven in Appendix C. Let us first prove that this
result applies. Because $s_{0}$ is proportional with $\frac{s}{t}$, we have

$\displaystyle\frac{rn}{s_{0}}=O\left(\frac{rnt}{s}\right)=O\left(\log\left(\frac{s}{n}\right)\sqrt{\frac{n}{s}}\right)$
(6)

which goes to $0$ based on Eq. 4. Moreover,

$\displaystyle s_{0}p=O\left(\frac{sp}{t}\right)=O\left(\sqrt{sn}\cdot
p\right)$ (7)

which goes to $0$ because $snp^{2}$ vanishes. Because $\frac{rn}{s_{0}}$ and
$s_{0}p\rightarrow 0$ we can use Lemma 2.

To show that the logical error rate of the implementation $C^{\prime}$
vanishes, it is sufficient to prove that the bound in Eq. 19 tends to $0$.
Based on Eq. 7, the denominator goes to $1$, hence it is enough to show that
$ts_{0}p2^{-r}$ and $tnp$ go to 0. Using $ts_{0}=O(s)$ and
$2^{-r}=O(\frac{n}{s})$, we obtain $ts_{0}p2^{-r}=O\left(np\right)$ which goes
to 0 by Eq. 3. For $tnp$, we get $tnp=O\left(\sqrt{sn}p\right)$ which goes to
0 because $snp^{2}$ does. ∎

######  Corollary 1 (size-$n^{\alpha}$ threshold).

Consider a family of $n$-qubit Clifford circuits with size $s=O(n^{\alpha})$
for some $\alpha>0$. If $np^{\frac{2}{1+\alpha}}\rightarrow 0$, we can
implement these circuits with vanishing logical error rate. Moreover, we have
$\limsup{\omega_{\operatorname{Q}}}\leq 3$ and
$\limsup{\omega_{\operatorname{G}}}\leq 2$.

This result is an immediate application of Theorem 2. It applies to circuits
acting on up to $n=O(p^{-\frac{2}{1+\alpha}})$ qubits, whereas the direct
implementation only reaches $n=O(p^{-\frac{1}{\alpha}})$.

######  Corollary 2 (Clifford unitary threshold).

If $p\rightarrow 0$ and $n=O(p^{-\frac{2}{3}})$, we can implement arbitrary
$n$-qubit Clifford unitaries with vanishing logical error rate. Moreover, we
have $\limsup{\omega_{\operatorname{Q}}}\leq 3$ and
$\limsup{\omega_{\operatorname{G}}}\leq 2$.

This is an application of Theorem 2, together with the fact that any $n$-qubit
Clifford unitary can be implemented with a Clifford circuit $C$ with size
$s=O\left(n^{2}/\log(n)\right)=o(n^{2})$ [38]. Again, this goes beyond the
direct implementation which only reaches $n=O(p^{-\frac{1}{2}})$.

##  V Numerical results

We numerically estimate the logical error rate of CliNR for the implementation
of uniform random Clifford unitaries, sampled using Algorithm 2 of [39],
synthesized into $s\approx n^{2}$ gates from the set $H_{i}$, $S_{i}$,
$CNOT_{i,j}$.

We consider the circuit-level noise model with noise rate $p_{2}$ for two-
qubit operations and $p_{1}=p_{2}/10$ for single-qubit operations because two-
qubit gates are typically the noisiest operations. Moreover, we include noise
on idle qubits with rate $p_{1}$.

In Fig. 1, we set $p_{2}=10^{-3}$ and $10^{-4}$. Ten random Clifford circuits
are generated for each $n$, and each circuit is simulated over $10^{5}$ shots
with the direct implementation and $10^{5}$ shots with the CliNR
implementation. We observe that CliNR outperforms the direct implementation in
relevant noise regimes. We obtain a $2\times$ reduction of the logical error
rate for the implementation of 25-qubit Clifford circuits when
$p_{2}=10^{-3}$. For $p_{2}=10^{-4}$, we get a $4\times$ reduction of the
logical error rate for Clifford circuits on 60 qubits.

Figure 2: Averge logical error rate of the CliNR implementation of random
Clifford circuits in two different noise regimes. We chose
$r=\left\lfloor\log(\frac{s}{n})\right\rfloor$, as in Eq. 5, and $t$ is the
smallest integer such that the ${\omega_{\operatorname{G}}}\leq 2$ for CliNR
$2\times$ and ${\omega_{\operatorname{G}}}\leq 4$ for CliNR $4\times$. The
value of $t$ varies with $n$.

Instead of using stabilizers selected uniformly at random to detect faults,
like the proof suggests, we restrict ourselves to stabilizers obtained by
propagating weight-2 stabilizers of the Bell state
$\frac{1}{\sqrt{2}}(|00\rangle+|11\rangle)^{\otimes n}$ through $I\otimes U$.
The resulting stabilizers have weight at most $n+1$ instead of $2n$, making
their measurements less noisy. Clifford circuits with unevenly distributed
noisy gates may require a modified choice of measured stabilizers better
adapted to its shape and noise profile.

It is worth noting, we do not select a new set of stabilizers for every run,
but do so in batches of $10^{3}$ shots instead, for expedience while
performing numerical simulations. This is justified for random Clifford
circuits because they rapidly scramble faults as they propagate, but may not
work well for shallower structured circuits. We leave a more careful analysis
of such circuits for a later work.

##  VI Conclusion

We proposed a method for error reduction in Clifford circuits offering a low-
cost alternative to error correction in near term devices. Clifford circuits
are split into small sub-circuits that are implemented by gate teleportation.
Faults are detected by measuring stabilizers of the resource states consumed
by the gate teleportation circuit. Instead of stabilizer measurements, one
could verify the resource states by measuring gauge operators of the spacetime
code of the circuit [40, 41]. This paper focuses on fully connected qubits but
the scheme can be adapted to other qubit topologies at a moderate price in
term of overhead as demonstrated in [3].

This scheme is limited to Clifford circuits that are not computationally
universal. We envision applications wherein a suitable compiler collates
Clifford gates within a given “real-world” circuit in order to yield large
Clifford sub-circuits separated by thin layers of single-qubit gates, which is
sufficient for universality. Alternatively, CliNR can be applied to error-
corrected qubits with universality achieved through magic states [34].

##  VII Acknowledgement

The authors thank Aharon Brodutch, Laird Egan, John Gamble, Andrii Maksymov,
Jeremy Sage, Pat Tang and Brendan Wyker for insightful discussions.

##  Appendix A Gate teleportation

The gate teleportation circuit [33] is a key ingredient of the CliNR scheme.
Fig. 1(a) shows the standard gate teleportation circuit for one qubit. It
performs simultaneously the teleportation of the state $|\psi\rangle$ from
qubit 1 to qubit 3, and the application of a unitary gate $U$ to
$|\psi\rangle$.

The one-bit teleportation circuit of Fig. 3(b), introduced in [42], performs
the teleportation of a quantum state $|\psi\rangle$ without using any ancilla
qubit. If $I\otimes U$ commutes with the $CNOT$ gate of the one-bit
teleportation circuit, we can play the same trick as in the original
teleportation circuit to merge the one-bit teleportation and the application
of $U$. This results in a circuit that uses the ancilla state $U|+\rangle$ to
apply the gate $U$ to $|\psi\rangle$. In Appendix E, we use this idea to build
a state injection circuit for sequences of $CZ$ gates.

(a)

(b)

Figure 3:  (a) Gate teleportation circuit implementing $U$ [33]. When $U=I$,
we recover the original teleportation circuit [43]. (b) One-bit teleportation
circuit [42].

##  Appendix B Bound on the performance of CliNR

The goal of this section is to prove Theorem 1. We start with the following
lemma, which bounds the performance of CliNR in the special case $t=1$.

######  Lemma 1.

The circuit $\operatorname{CliNR}_{1,r}(C)$ implements the circuit $C$ with
logical error rate

$\displaystyle{p_{\log}}\leq$
$\displaystyle\frac{g_{p}(3n+s)2^{-r}+2g_{p}(2n+3)+g_{p}(5n)}{(1-p)^{m}}$ (8)

where $m=3n+s+(2n+3)r$. Moreover, the overhead satisfies
${\omega_{\operatorname{Q}}}=3+\frac{1}{n}$ and
${\omega_{\operatorname{G}}}\leq\frac{5n}{s}+\frac{m}{s(1-p)^{m}}$.

###### Proof.

Denote $C^{\prime}=\operatorname{CliNR}_{1,r}(C)$. The fact that $C^{\prime}$
implements $C$ is clear because, in the absence of fault, the stabilizer
measurements have no effect, and removing these measurements, we obtain the
standard gate teleportation circuit.

Let us bound the overhead of the implementation. The qubit overhead is clear.
To bound the gate overhead, we need an upper bound on the probability
${p_{\operatorname{res}}}$ of $C^{\prime}$ to restart during the stabilizer
measurements. Naively, it is upper bounded by the probability that at least
one fault occurs before the end of the stabilizer measurement loop. This leads
to

$\displaystyle{p_{\operatorname{res}}}\leq 1-(1-p)^{m}$ (9)

where $m=3n+s+(2n+3)r$ is the number of circuit operations before the last
stabilizer measurement (included). Each restart adds at most $m$ operations to
the circuit. Moreover, if no restart is triggered, $5n$ operations are added
to finish the gate teleportation. Therefore, the expected number of operations
executed by $C^{\prime}$ is upper bounded by

$\displaystyle 5n+\sum_{i\geq
1}im\cdot{p_{\operatorname{res}}}^{i-1}(1-{p_{\operatorname{res}}})$ (10)
$\displaystyle\leq 5n+\frac{m}{1-{p_{\operatorname{res}}}}$ (11)
$\displaystyle\leq 5n+\frac{m}{(1-p)^{m}}\cdot$ (12)

The gate overhead is given by dividing this bound by the size $s$ of $C$.

To bound the logical error rate of the implementation of $C$ by $C^{\prime}$,
assume that a combination of faults occurs in the circuit, resulting in a
output error $E$. Below, we say a combination of faults is non-trivial if they
propagate into a non-trivial output error. If the output error $E$ is non-
trivial, then, one of the following events must have occurred.

(1) Non-trivial faults occur before the beginning of the stabilizer
measurements and they are not detected by the stabilizer measurements.

(2) Non-trivial faults occur during the $i$ th stabilizer measurement and they
are not detected by the subsequent stabilizer measurements

(3) Non-trivial faults occur after the last stabilizer measurement.

Denote by $P_{1},P_{2}$ and $P_{3}$ the respective probabilities of these
three events. Then, the logical error rate of the CliNR implementation is
upper bounded by

$\displaystyle{p_{\log}}\leq\frac{P_{1}+P_{2}+P_{3}}{1-{p_{\operatorname{res}}}}\cdot$
(13)

Next, we bound the three terms in the numerator.

Case (1). The circuit $C^{\prime}$ contains $3n+s$ noisy operations before the
first stabilizer measurement. The probability that at least one fault occurs
in these operations is $1-(1-p)^{3n+s}$. If these faults are non-trivial, the
outcome $\sigma\in\\{0,1\\}^{r}$ for the $r$ stabilizer measurements is a
uniform random bit-string. This distribution remains uniform when including
the effect of fault occurring during the measurement. Therefore, we have

$\displaystyle P_{1}\leq(1-(1-p)^{3n+s})2^{-r}$ (14)

because the faults are undetected only if $\sigma=0$.

Case (2). Each stabilizer measurement contains at most $2n+3$ operations. By
the same argument as in (1), a non-trivial combination of faults in the $i$ th
measurement induces a uniform outcome on the last $r-i$ stabilizer
measurements. Therefore, it is undetected with probability at most $2^{-r+i}$,
which yields

$\displaystyle P_{2}$
$\displaystyle\leq\sum_{1=1}^{r}(1-(1-p)^{2n+3})2^{-r+i}$ (15)
$\displaystyle\leq 2(1-(1-p)^{2n+3})$ (16)

Case (3). Counting the circuit operations after the last measurement, we get

$\displaystyle P_{3}\leq(1-(1-p)^{5n})\cdot$ (17)

Injecting Eqs. 9, LABEL:, 14, LABEL:, 15, LABEL: and 17 in Eq. 13 provides the
bound on ${p_{\log}}$. ∎

###### Proof of Theorem 1.

The fact that $\operatorname{CliNR}_{t,r}(C)$ implements $C$ is a consequence
of Lemma 1 which shows that $\operatorname{CliNR}_{1,r}(C_{i})$ implements the
sub-circuit $C_{i}$.

The logical error rate is at most $t$ times the logical error rate per sub-
circuit, for which we use the bound from Lemma 1.

The qubit overhead is the same as in $\operatorname{CliNR}_{1,r}$ because the
$2n+1$ ancilla qubits are re-used for the implementation of each sub-circuit.
The expected number of operations in the implementation of one of the sub-
circuits is at most $s_{0}{\omega_{\operatorname{G}}}^{\prime}$ where
${\omega_{\operatorname{G}}}^{\prime}$ is the maximum gate overhead for a sub-
circuit. By linearity of the expectation, the expected number of operations
for the implementation of the entire circuit $C$ is upper bounded by
$ts_{0}{\omega_{\operatorname{G}}}^{\prime}$. Using $ts_{0}\leq t\lceil
s/t\rceil\leq s+t\leq 2s$ (if $t\geq s$, the last $t-s$ sub-circuits $C_{i}$
have size 0), we get

$\displaystyle{\omega_{\operatorname{G}}}\leq\frac{ts_{0}{\omega_{\operatorname{G}}}^{\prime}}{s}\leq
2{\omega_{\operatorname{G}}}^{\prime}$ (18)

Plugging in the bound on the gate overhead obtained in Lemma 1 leads to the
bound announced in Theorem 1. ∎

##  Appendix C Proof of Lemma 2

The goal of this section is to prove the following lemma.

######  Lemma 2.

If $nr=o(s_{0})$ and $s_{0}p\rightarrow 0$, then

$\displaystyle{p_{\log}}=O\left(\frac{ts_{0}2^{-r}p+9tnp}{1-s_{0}p}\cdot\right)$
(19)

Moreover, the overhead satisfies $\limsup{\omega_{\operatorname{Q}}}\leq 3$
and $\limsup{\omega_{\operatorname{G}}}\leq 2$.

###### Proof.

We compute the asymptotic equivalent of the upper bound in Eq. 2 when $s_{0}p$
vanishes. The expansion $g_{p}(\ell)=\ell p+o\left((\ell p)^{2}\right)$ leads
to a numerator dominated by

$\displaystyle t\left((As_{0}+A^{\prime}n)2^{-r}+(Bn+B^{\prime})\right)p$ (20)

with $A=1,A^{\prime}=3,B=9$ and $B^{\prime}=6$. We can discard the term
$A^{\prime}n$, dominated by $As_{0}$ (because we assume $nr=o(s_{0})$) and the
term $B^{\prime}$, dominated by $Bn$. For the denominator, we use
$(1-p)^{m}=1-mp+o((mp)^{2})$. This proves Eq. 19.

The bound on ${\omega_{\operatorname{Q}}}$ is clear from Theorem 1. In the
upper bound on ${\omega_{\operatorname{G}}}$, the term $\frac{10n}{s_{0}}$
vanishes and $\frac{2m_{0}}{s_{0}(1-p)^{m_{0}}}$ goes to $2$ because
$\frac{2m_{0}}{s_{0}}\rightarrow 2$ and
$\frac{1}{(1-p)^{m_{0}}}=e^{-m_{0}p+o((m_{0}p)^{2})}\rightarrow 1$. ∎

##  Appendix D CliNR and Circuit Shape

The efficacy of CliNR at reducing noise varies significantly with the
circuit’s shape parameter $\alpha$, where the circuit size is given by
$s=n^{\alpha}$. At a given width $n$, smaller $\alpha$ implies a circuit with
fewer gates in the intended Clifford block $C$, even as the overheads
associated with CliNR remain independent of $\alpha$. Thus, for any given $n$,
circuits with smaller $\alpha$ are more likely to favor direct implementation,
whereas CliNR becomes increasingly effective as $\alpha\to 2$. Nevertheless at
sufficiently large qubit counts ($n>p^{-1/{\alpha+1}}$), direct implementation
becomes very noisy, whereas from Corollary 1 we expect a CliNR implementation
to remain effective.

In Fig. 4, we plot differences in the logical error rate between CliNR and
direct implementation of Clifford circuits of various sizes. Each cell in the
color-coded grids represent random Clifford circuits of distinct $n$ and
$\alpha$. Random Clifford circuits at a given $n$ and $\alpha$ are constructed
by randomly sampling $n^{\alpha}$ gates from the set {$H$, $S$, $CX$}.

Logical error rate differences,
$p_{\text{log}}^{\text{direct}}-p_{\text{log}}^{\text{CliNR}}$ are depicted as
a color map. At small $n$ and $\alpha$, we observe direct implementation
yielding error rates competitive with CliNR, without the overheads of the
latter. As $\alpha$ or $n$ increase, CliNR becomes strongly favored with
substantial error rate improvements over direct implementation.

Figure 4: Improvement of the logical error rate of random Clifford circuits
under CliNR for the circuit-level noise model of Section V with
$p_{2}=p_{1}/10=10^{-4}$ as functions of the qubit count $n$ and the circuit
shape $\alpha$ (for circuit size $s=n^{\alpha}$). Gray dashed lines are guides
to the eye that delineates between regions where direct implementation is
favored (white, upper-left) vs where CliNR yields lower noise (lower-right).

##  Appendix E CZ noise reduction circuit

Figure 5:  Middle: A graph $G$ with five vertices and five edges. The sequence
of $CZ$ gates corresponding to the edges of $G$ defines a unitary $U_{G}$.
Left: Teleportation of five qubits, followed by the application of $U_{G}$
(dashed box) to the teleported qubits. Right: The graph state injection
circuit associated with $G$. Commuting the sequence of $CZ$ gates through the
circuit, we see that these two circuits are equivalent.

Here, we show that the CliNR circuit can be simplified in the case of a
Clifford circuit containing only CZ gates. The basic idea is to implement a
sequence of CZ using the one-bit teleportation, shown in Fig. 3(b), instead of
the original teleportation circuit. This results in a circuit that can be seen
as a state injection circuit, similar to the $T$-state injection circuit,
where the resource state is a graph state instead of a $T$-state.

###  E.1 Graph state injection circuit

Any $n$-qubit unitary made with a sequence of $CZ$ gates can be represented by
a graph $G$ with $n$ vertices, corresponding to the qubits, and whose edges
are in one-to-one correspondence with the $CZ$ gates in the circuit. The
unitary associated with $G$ is denoted $U_{G}$.

The graph state injection circuit, represented in Fig. 5(right), associated
with a graph $G$ with $n$ vertices is the $2n$-qubit circuit defined as
follows. Assume that the vertices of $G$ are indexed by $1,2,\dots,n$ and the
qubits are indexed by $1,2,\dots,2n$. First, qubits $n+1,n+2,\dots,2n$ are
initialized in the state $|+\rangle$. Then, for each edge $\\{i,j\\}$ in $G$,
apply a $CZ$ gate between qubit $n+i$ and qubit $n+j$. This prepares the so-
called graph state, denoted $|G\rangle$, on the last $n$ qubits111For a review
of graph states see [45].. Then, implement $CNOT$ gates controlled on qubit
$n+i$ and targeting qubit $i$ for $i=1,2,\dots,n$. After the $CNOT$, the first
$n$ qubits are measured. If the outcome of the $i$-th measurement is non-
trivial, the Pauli operation

$\displaystyle X_{n+i}\prod_{j\in N(i)}Z_{n+j}$ (21)

is applied, where $N(i)$ denotes the set of neighbors of vertex $i$ in $G$.

The following lemma shows that the graph state injection circuit consumes the
graph state $|G\rangle$ prepared on the second block of qubits to implement
the operation $U_{G}$.

######  Lemma 3 (Graph state injection circuit).

The state-injection circuit simultaneously performs the teleportation of the
state of the first $n$ qubits onto the last $n$ qubits, and apply the unitary
$U_{G}$ to this state.

###### Proof.

By commuting the sequence of $CZ$ to the end of the graph state injection
circuit, we see that this circuit is equivalent to applying the one-bit
teleportation circuit to the $n$ input qubits and applying the $CZ$ gates,
that is $U_{G}$, to the output qubits of the teleportations. This is clear by
examination of Fig. 5. ∎

###  E.2 Noise reduction in CZ circuits

Figure 6:  The CZNR circuit implements a $n$-qubit $U$ made with a sequence of
$CZ$ using $n+1$ ancilla qubits. The ancilla qubits are used to prepare a
graph state and check it using $r$ stabilizer measurements. In this figure
$r=1$ and the stabilizer $P$ of the graph state is measured. It is a
simplification of the CliNR circuit of Fig. 1 in the case of sequences of $CZ$
gates.

Similarly to the CliNR circuit, the $CZ$ noise reduction (CZNR) circuit,
described in Fig. 6, is obtained by inserting $r$ stabilizer measurements in
the graph state injection circuit, right after the graph state preparation.
Like in the CliNR circuit, the stabilizers are independent stabilizers,
selected uniformly at random in the stabilizer group of the first $n$ ancilla
qubits and a new set of $r$ stabilizer generators is selected for each run of
the circuit. The circuit restarts if one of the stabilizer measurements
returns a non-trivial outcome. The CZNR circuit is limited to $CZ$ sequences
but because it is built from the one-bit teleportation circuit, it consumes
only $n$ ancilla qubits instead of $2n$. We denote by
$\operatorname{CZNR}_{t,r}(C)$ the analog of $\operatorname{CliNR}_{t,r}(C)$
for $CZ$ sequences.

The following result is adapted from Theorem 1 to $CZ$ sequences, that is
Clifford circuits containing only $CZ$ gates.

Figure 7: Average logical error rate of a dense block of CZ gates with and
without CZNR, in two noise regimes. As in the CliNR case, here $t$ is selected
for CZNRt,r such that the overhead is bounded, $\omega_{G}\leq 2$.

######  Theorem 3.

The circuit $\operatorname{CZNR}_{t,r}(C)$ implements a $CZ$ sequence $C$ with
logical error rate

$\displaystyle{p_{\log}}\leq$ $\displaystyle
t\cdot\frac{g_{p}(n+s)2^{-r}+2g_{p}(n+3)+g_{p}(3n)}{(1-p)^{m_{0}}}$ (22)

where $m=n+s_{0}+(n+3)r$. Moreover, the overhead satisfies
${\omega_{\operatorname{Q}}}=2+\frac{1}{n}$ and
${\omega_{\operatorname{G}}}\leq\frac{6n}{s_{0}}+\frac{2m_{0}}{s_{0}(1-p)^{m}}$.

We omit the proof of this result as it is an immediate application of the same
technique used to prove Lemma 1 and Theorem 1.

In Fig. 7, we show numerical results comparing direct implementation of a
dense ($\mathcal{O}(n^{2})$) block of CZ gates against a CZNR equivalent. As
described in the main text for CliNR, we similarly cap the $\omega_{G}\leq 2$
for CZNRt,r here by varying $t$.

## References

  * Roffe  _et al._ [2018] J. Roffe, D. Headley, N. Chancellor, D. Horsman, and V. Kendon, Protecting quantum memories using coherent parity check codes, Quantum Science and Technology 3, 035010 (2018).
  * Debroy and Brown [2020] D. M. Debroy and K. R. Brown, Extended flag gadgets for low-overhead circuit verification, Physical Review A 102, 052409 (2020).
  * van den Berg  _et al._ [2023] E. van den Berg, S. Bravyi, J. M. Gambetta, P. Jurcevic, D. Maslov, and K. Temme, Single-shot error mitigation by coherent pauli checks, Physical Review Research 5, 033193 (2023).
  * Shor [1995] P. W. Shor, Scheme for reducing decoherence in quantum computer memory, Physical review A 52, R2493 (1995).
  * Aharonov and Ben-Or [1997] D. Aharonov and M. Ben-Or, Fault-tolerant quantum computation with constant error, in  _Proceedings of the twenty-ninth annual ACM symposium on Theory of computing_ (1997) pp. 176–188.
  * Aliferis  _et al._ [2006] P. Aliferis, D. Gottesman, and J. Preskill, Quantum accuracy threshold for concatenated distance-3 codes, Quantum Info. Comput. 6, 97–165 (2006).
  * Gidney and Ekerå [2021] C. Gidney and M. Ekerå, How to factor 2048 bit rsa integers in 8 hours using 20 million noisy qubits, Quantum 5, 433 (2021).
  * Gottesman [2013] D. Gottesman, Fault-tolerant quantum computation with constant overhead, arXiv preprint arXiv:1310.2984 (2013).
  * Breuckmann and Eberhardt [2021] N. P. Breuckmann and J. N. Eberhardt, Quantum low-density parity-check codes, PRX Quantum 2, 040101 (2021).
  * Panteleev and Kalachev [2022] P. Panteleev and G. Kalachev, Asymptotically good quantum and locally testable classical ldpc codes, in  _Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing_ (2022) pp. 375–388.
  * Leverrier and Zémor [2022] A. Leverrier and G. Zémor, Quantum tanner codes, in  _2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS)_ (IEEE, 2022) pp. 872–883.
  * Pattison  _et al._ [2023] C. A. Pattison, A. Krishna, and J. Preskill, Hierarchical memories: Simulating quantum ldpc codes with local gates, arXiv preprint arXiv:2303.04798 (2023).
  * Yoshida  _et al._ [2024] S. Yoshida, S. Tamiya, and H. Yamasaki, Concatenate codes, save qubits, arXiv preprint arXiv:2402.09606 (2024).
  * Yamasaki and Koashi [2024] H. Yamasaki and M. Koashi, Time-efficient constant-space-overhead fault-tolerant quantum computation, Nature Physics , 1 (2024).
  * Zhou  _et al._ [2024] H. Zhou, C. Zhao, M. Cain, D. Bluvstein, C. Duckering, H.-Y. Hu, S.-T. Wang, A. Kubica, and M. D. Lukin, Algorithmic fault tolerance for fast quantum computing, arXiv preprint arXiv:2406.17653 (2024).
  * Tremblay  _et al._ [2022] M. A. Tremblay, N. Delfosse, and M. E. Beverland, Constant-overhead quantum error correction with thin planar connectivity, Physical Review Letters 129, 050504 (2022).
  * Higgott and Breuckmann [2023] O. Higgott and N. P. Breuckmann, Constructions and performance of hyperbolic and semi-hyperbolic floquet codes, arXiv preprint arXiv:2308.03750 (2023).
  * Bravyi  _et al._ [2024] S. Bravyi, A. W. Cross, J. M. Gambetta, D. Maslov, P. Rall, and T. J. Yoder, High-threshold and low-overhead fault-tolerant quantum memory, Nature 627, 778 (2024).
  * Scruby  _et al._ [2024] T. R. Scruby, T. Hillmann, and J. Roffe, High-threshold, low-overhead and single-shot decodable fault-tolerant quantum memory, arXiv preprint arXiv:2406.14445 (2024).
  * Egan  _et al._ [2021] L. Egan, D. M. Debroy, C. Noel, A. Risinger, D. Zhu, D. Biswas, M. Newman, M. Li, K. R. Brown, M. Cetina, _et al._ , Fault-tolerant control of an error-corrected qubit, Nature 598, 281 (2021).
  * Ryan-Anderson  _et al._ [2021] C. Ryan-Anderson, J. G. Bohnet, K. Lee, D. Gresh, A. Hankin, J. Gaebler, D. Francois, A. Chernoguzov, D. Lucchetti, N. C. Brown, _et al._ , Realization of real-time fault-tolerant quantum error correction, Physical Review X 11, 041058 (2021).
  * Postler  _et al._ [2023] L. Postler, F. Butt, I. Pogorelov, C. D. Marciniak, S. Heußen, R. Blatt, P. Schindler, M. Rispler, M. Müller, and T. Monz, Demonstration of fault-tolerant steane quantum error correction, arXiv preprint arXiv:2312.09745 (2023).
  * Abobeih  _et al._ [2022] M. H. Abobeih, Y. Wang, J. Randall, S. Loenen, C. E. Bradley, M. Markham, D. J. Twitchen, B. M. Terhal, and T. H. Taminiau, Fault-tolerant operation of a logical qubit in a diamond quantum processor, Nature 606, 884 (2022).
  * Krinner  _et al._ [2022] S. Krinner, N. Lacroix, A. Remm, A. Di Paolo, E. Genois, C. Leroux, C. Hellings, S. Lazar, F. Swiadek, J. Herrmann, _et al._ , Realizing repeated quantum error correction in a distance-three surface code, Nature 605, 669 (2022).
  * Zhao  _et al._ [2022] Y. Zhao, Y. Ye, H.-L. Huang, Y. Zhang, D. Wu, H. Guan, Q. Zhu, Z. Wei, T. He, S. Cao, _et al._ , Realization of an error-correcting surface code with superconducting qubits, Physical Review Letters 129, 030501 (2022).
  * goo [2023] Suppressing quantum errors by scaling a surface code logical qubit, Nature 614, 676 (2023).
  * Bluvstein  _et al._ [2024] D. Bluvstein, S. J. Evered, A. A. Geim, S. H. Li, H. Zhou, T. Manovitz, S. Ebadi, M. Cain, M. Kalinowski, D. Hangleiter, _et al._ , Logical quantum processor based on reconfigurable atom arrays, Nature 626, 58 (2024).
  * Ryan-Anderson  _et al._ [2024] C. Ryan-Anderson, N. Brown, C. Baldwin, J. Dreiling, C. Foltz, J. Gaebler, T. Gatterman, N. Hewitt, C. Holliman, C. Horst, _et al._ , High-fidelity and fault-tolerant teleportation of a logical qubit using transversal gates and lattice surgery on a trapped-ion quantum computer, arXiv preprint arXiv:2404.16728 (2024).
  * Mayer  _et al._ [2024] K. Mayer, C. Ryan-Anderson, N. Brown, E. Durso-Sabina, C. H. Baldwin, D. Hayes, J. M. Dreiling, C. Foltz, J. P. Gaebler, T. M. Gatterman, _et al._ , Benchmarking logical three-qubit quantum fourier transform encoded in the steane code on a trapped-ion quantum computer, arXiv preprint arXiv:2404.08616 (2024).
  * Li and Benjamin [2017] Y. Li and S. C. Benjamin, Efficient variational quantum simulator incorporating active error minimization, Physical Review X 7, 021050 (2017).
  * Temme  _et al._ [2017] K. Temme, S. Bravyi, and J. M. Gambetta, Error mitigation for short-depth quantum circuits, Physical review letters 119, 180509 (2017).
  * Cai  _et al._ [2023] Z. Cai, R. Babbush, S. C. Benjamin, S. Endo, W. J. Huggins, Y. Li, J. R. McClean, and T. E. O’Brien, Quantum error mitigation, Reviews of Modern Physics 95, 045005 (2023).
  * Gottesman and Chuang [1999] D. Gottesman and I. L. Chuang, Quantum teleportation is a universal computational primitive, arXiv preprint quant-ph/9908010 (1999).
  * Bravyi and Kitaev [2005] S. Bravyi and A. Kitaev, Universal quantum computation with ideal clifford gates and noisy ancillas, Physical Review A 71, 022316 (2005).
  * Gonzales  _et al._ [2023] A. Gonzales, R. Shaydulin, Z. H. Saleem, and M. Suchara, Quantum error mitigation by pauli check sandwiching, Scientific Reports 13, 2122 (2023).
  * Anand and Brown [2023] A. Anand and K. R. Brown, Hamiltonians, groups, graphs and ans$\backslash$” atze, arXiv preprint arXiv:2312.17146 (2023).
  * Gottesman [1998] D. Gottesman, The heisenberg representation of quantum computers, arXiv preprint quant-ph/9807006 (1998).
  * Aaronson and Gottesman [2004] S. Aaronson and D. Gottesman, Improved simulation of stabilizer circuits, Physical Review A 70, 052328 (2004).
  * Bravyi and Maslov [2021] S. Bravyi and D. Maslov, Hadamard-free circuits expose the structure of the clifford group, IEEE Transactions on Information Theory 67, 4546 (2021).
  * Bacon  _et al._ [2015] D. Bacon, S. T. Flammia, A. W. Harrow, and J. Shi, Sparse quantum codes from quantum circuits, in  _Proceedings of the forty-seventh annual ACM symposium on Theory of Computing_ (2015) pp. 327–334.
  * Delfosse and Paetznick [2023] N. Delfosse and A. Paetznick, Spacetime codes of clifford circuits, arXiv preprint arXiv:2304.05943 (2023).
  * Zhou  _et al._ [2000] X. Zhou, D. W. Leung, and I. L. Chuang, Methodology for quantum logic gate construction, Physical Review A 62, 052316 (2000).
  * Bennett  _et al._ [1993] C. H. Bennett, G. Brassard, C. Crépeau, R. Jozsa, A. Peres, and W. K. Wootters, Teleporting an unknown quantum state via dual classical and einstein-podolsky-rosen channels, Physical review letters 70, 1895 (1993).
  * Note [1] For a review of graph states see [45].
  * Hein  _et al._ [2006] M. Hein, W. Dür, J. Eisert, R. Raussendorf, M. Nest, and H.-J. Briegel, Entanglement in graph states and its applications, arXiv preprint quant-ph/0602096 (2006).