# Efficient Long-Range Entanglement using Dynamic Circuits

Elisa Bäumer<EMAIL_ADDRESS>IBM Quantum, IBM Research – Zurich, 8803
Rüschlikon, Switzerland  Vinay Tripathi  IBM Quantum, IBM T.J. Watson Research
Center, Yorktown Heights, NY 10598, USA  Department of Physics & Astronomy,
University of Southern California, Los Angeles, California 90089, USA  Derek
S. Wang  IBM Quantum, IBM T.J. Watson Research Center, Yorktown Heights, NY
10598, USA  Patrick Rall  IBM Quantum, MIT-IBM Watson AI Lab, Cambridge, MA
02142, USA  Edward H. Chen  IBM Quantum, Almaden Research Center, San Jose, CA
95120, USA  IBM Quantum, Research Triangle Park, NC 27709, USA  Swarnadeep
Majumder  IBM Quantum, IBM T.J. Watson Research Center, Yorktown Heights, NY
10598, USA  Alireza Seif  IBM Quantum, IBM T.J. Watson Research Center,
Yorktown Heights, NY 10598, USA  Zlatko K. Minev  IBM Quantum, IBM T.J. Watson
Research Center, Yorktown Heights, NY 10598, USA

###### Abstract

Quantum simulation traditionally relies on unitary dynamics, inherently
imposing efficiency constraints on the generation of intricate entangled
states. In principle, these limitations can be superseded by non-unitary,
dynamic circuits. These circuits exploit measurements alongside conditional
feed-forward operations, providing a promising approach for long-range
entangling gates, higher effective connectivity of near-term hardware, and
more efficient state preparations. Here, we explore the utility of shallow
dynamic circuits for creating long-range entanglement on large-scale quantum
devices. Specifically, we study two tasks: CNOT gate teleportation between up
to 101 qubits by feeding forward 99 mid-circuit measurement outcomes, and the
preparation of Greenberger–Horne–Zeilinger (GHZ) states with genuine
entanglement. In the former, we observe that dynamic circuits can outperform
their unitary counterparts. In the latter, by tallying instructions of
compiled quantum circuits, we provide an error budget detailing the obstacles
that must be addressed to unlock the full potential of dynamic circuits.
Looking forward, we expect dynamic circuits to be useful for generating long-
range entanglement in the near term on large-scale quantum devices.

##  I Introduction

Quantum systems present two distinct modes of evolution: deterministic unitary
evolution, and stochastic evolution as the consequence of quantum
measurements. To date, quantum computations predominantly utilize unitary
evolution to generate complex quantum states for information processing and
simulation. However, due to inevitable errors in current quantum devices [1],
the computational reach of this approach is constrained by the depth of the
quantum circuits that can realistically be implemented on noisy devices. The
introduction of non-unitary dynamic circuits, or adaptive circuits, may be
able to overcome some of these limitations by employing mid-circuit
measurements and feed-forward operations. Such conditional operations are a
necessary ingredient for quantum error correction (see, e.g., Ref. [2]). In
the near term, dynamic circuits present a promising avenue for generating
long-range entanglement, a task at the heart of quantum algorithms. This
includes both implementation of long-range entangling gates that, due to local
connectivity among the qubits in many quantum platforms, can require deep
unitary quantum circuits, and preparation of many-qubit entangled [3, 4] and
topologically ordered quantum states [5, 6, 7, 8, 9, 10, 11, 12, 13].

From a physical standpoint, the entanglement needs to propagate across the
entire range between the qubits. Given that the entanglement cannot spread
faster than its information light cone [14, 15], entangling two qubits that
are a distance $n$ apart requires a minimum two-qubit gate-depth that scales
as $\mathcal{O}(n)$, and even when assuming all-to-all connectivity, the
generation of entanglement over $n$ qubits necessitates a minimum two-qubit
gate depth of $\mathcal{O}(\log n)$. Thus, the task becomes challenging when
applying only unitary gates. Using dynamic circuits, the spread of information
can be mostly conducted by classical calculations, which can be faster and
with a higher fidelity than the quantum gates, and long-range entanglement can
be created in a shallow quantum circuit [16, 17, 18], i.e. the depth of
quantum gates is constant for any $n$.

While dynamic circuits have been explored in small-scale experiments [19, 20,
21, 22, 23], only recently have there been experimental capabilities on large-
scale quantum devices. However, most demonstrations (with the exception of
e.g. Refs. [24, 25, 26]) have utilized post-selection [27] or post-processing
[28, 29] instead of feed-forward to prepare entangled states. Such approaches
enable the study of properties of the state prepared in isolation, but have
limited applicability when the state preparation is part of a larger quantum
information processing task.

Here, we explore the utility of shallow dynamic circuits for creating long-
range entanglement on large-scale superconducting quantum devices. In Section
II, we demonstrate an advantage with dynamic circuits by teleporting a long-
range entangling CNOT gate over up to 101 locally connected superconducting
qubits. We also discuss how this approach can be generalized to more complex
gates, such as the three-qubit Toffoli gate. Then, in Section III, we prepare
a long-range entangled state, the GHZ state [3], with a dynamic circuit. We
show that—with a composite error mitigation stack customized for the hardware
implementation of dynamic circuits—we can prepare genuinely entangled GHZ
states but fall short of state-of-the-art system sizes achieved with unitary
gates due to hardware limitations. We predict conditions under which dynamic
circuits should be advantageous over unitary circuits based on our error
budget calculation.

Figure 1:  Teleporting a CNOT gate for long-range entanglement. (a) Left:
Circuit for a long-range CNOT gate spanning a 1D chain of $n$-qubits subject
to nearest-neighbor connections only. Middle: Equivalent unitary decomposition
into implementable CNOT gates; circuit depth $\mathcal{O}(n)$. Right:
Equivalent circuit employing measurements with feed-forward operations;
circuit depth $\mathcal{O}(1)$. If the post-measurement state is unused, feed-
forward operations can be handled in post-processing, eliminating the need for
their experimental implementation. Yellow regions indicate the idle time
during CNOT gates on other qubits as well as during measurement and feed-
forward (which is denoted by duration $\mu$). (b) Error model inputs for
unitary, measurement-based, and dynamic-circuit CNOT protocols comprise the
total number of: non-zero idle-block times, CNOT gates, and additional
measurements. (c) Experimental results, where dynamic circuits offer improved
fidelity for CNOT gate teleportation across a qubit chain $\gtrsim$ 10 qubits.
(d) Map of a 127-qubit heavy-hexagonal processor, ibm_sherbrooke, overlaid
with system configurations for long-range gate teleportation across a locally
connected bus. To establish an effective all-to-all connectivity, we show one
possible strategy of dividing the qubits into system (purple and orange) and
sacrificial ancilla (turquoise and blue for extra connections) qubits. To
parallellize gate execution with increased connectivity, orange qubits can be
used as ancillas. We show how a particular long-range CNOT can be implemented
through an ancilla bus marked as turquoise spins.

##  II Gate teleportation

The limited connectivity between qubits in many quantum computational
platforms can result in the compilation of non-local unitary circuits into
deep and error-prone unitary circuits. A potential solution is the use of
shallow dynamic circuits. The crucial ingredient for such protocols is long-
range CNOT gates from the first to $n$th qubit, as shown on the left in Fig.
1(a). In the following, we demonstrate a regime under which dynamic circuits
enable higher-fidelity long-range CNOT gates via gate teleportation. We first
describe the dynamic circuit and compare to its equivalent unitary
counterpart. We argue, using a simple error budget, that there exists a regime
in which the dynamic circuit implementation has an advantage over the unitary
one, see Fig. 1(b). Then, using up to $101$ qubits on a superconducting
processor, we demonstrate a crossover in the fidelity of CNOT gate
teleportation, where dynamic circuits perform better for entangling qubits
over longer ranges; see Fig. 1(c). This gate teleportation scheme enables an
effective all-to-all connectivity in devices with a more limited connectivity,
such as those on a heavy-hexagonal lattice. By using some of the qubits as
ancillas for measurement and classical feed-forward operations, the ancilla
qubits form a bus that connects all system qubits with each other. Therefore,
by sacrificing some of the qubits in a large device with limited connectivity,
we gain effective access to an all-to-all connected device with fewer qubits;
see Fig 1(d). Finally, we show that these ideas can be generalized to
teleporting multi-qubit gates, such as the Toffoli or CCZ gate.

###  II.1 CNOT

We describe the dynamic circuit for CNOT gate teleportation, shown on the
right in Fig. 1(a) and derived in Appendix A.1. Importantly, this dynamic
circuit can be straightforwardly extended for any number of qubits $n$ (where
$n$ is the number of ancillas) such that the depth remains constant for any
initial states $\ket{\varphi_{1}}$ $\left(\ket{\varphi_{2}}\right)$ of the
control (target) qubit. We expect the error to be dominated by the $n$ mid-
circuit measurements, $n+1$ CNOT gates parallelized over 2 gate layers, and
idle time mostly over the classical feed-forward time. Note that in this
particular realization, each of the $n$ ancilla qubits between the two system
qubits must be in the state $\ket{0}$. Therefore, during the course of the
gate teleportation, the ancillas cannot also be used as memory qubits, further
motivating the division of qubits into system and sacrificial ancilla qubits
in Fig. 1(d).

We also present an equivalent, low-error unitary counterpart in the middle of
Fig. 1(a). (In Appendix B, we propose several different unitary
implementations of the long-range CNOT gate. Based on experimental results, as
well as the noise model described in Appendix E that gives rise to the error
budget described in Appendix B.2, we select this one.) In this unitary
realization, the system qubits are connected by a bus of ancilla qubits that
are initialized in and returned to the $|0\rangle$ state, just as in its
dynamic counterpart. In our particular compilation, throughout the execution
of the circuit, qubits that are not in the $|\phi_{1}\rangle$ or
$|\phi_{2}\rangle$ state are in the $|0\rangle$ state. Doing so minimizes both
decoherence and cross-talk errors intrinsic to our superconducting qubit
design. Therefore, relative to the dynamic version, there is no error due to
idle time or mid-circuit measurements, although there are $\sim$4 times more
CNOT gates.

A summary of the error budgets for the dynamic and unitary circuits is in Fig.
1(b). Based on this table, we expect that dynamic circuits should be
advantageous over unitary circuits if the additional $n$ mid-circuit
measurements in the dynamic circuit introduce less error than the $3n$ extra
CNOT gates in the unitary circuit, assuming $n$ is large enough such that the
idling error $\mu$ incurred during measurement and classical feed-forward in
the dynamic circuit is relatively small. Importantly, we should note that
these error analyses only consider the gate error on the two respective
qubits, but not the error introduced on other qubits, which we expect to be
much larger in the unitary case due to the linear depth. Thus, the constant-
depth dynamic circuit might be even more advantageous than what we can see
from the gate fidelity.

To determine the experimental gate fidelity, let our ideal unitary channel be
$\mathcal{U}(\rho)\coloneqq U\rho U^{\dagger}$ and its noisy version be
$\tilde{\mathcal{U}}(\rho)\coloneqq\mathcal{U}(\Lambda(\rho))$, where
$\Lambda$ is the effective gate noise channel and $\rho$ is a quantum state.
The average gate fidelity of the noisy gate is
$\mathcal{F}_{\mathrm{avg}}\left(\mathcal{U},\tilde{\mathcal{U}}\right)=\int\mathrm{d}\psi\,\operatorname{Tr}\left[\mathcal{U}\left(\rho_{\psi}\right)\tilde{\mathcal{U}}\left(\rho_{\psi}\right)\right]$,
where the Haar average is taken over the pure states
$\rho_{\psi}=\left|\psi\vphantom{\psi}\right\rangle\left\langle\vphantom{\psi}\psi\right|$.
This fidelity can be faithfully estimated from Pauli measurements on the
system, using Monte Carlo process certification [30, 31], as detailed in
Appendix C.2.

The results from a superconducting quantum processor are shown in Fig. 1(c).
As expected, for a small number of qubits $n\lesssim 10$ the unitary
implementation yields the best fidelities. However, for increasing $n$ it
converges much faster to the fidelity of a random gate (0.25) than the dynamic
circuits implementation, which converges to a value slightly below 0.4. These
align well with the error budget analysis in Appendix B.2 and the noise model
predictions depicted in Appendix E. Note that, in the limit of large $n$, the
fidelities of the measurement-based scheme are limited by the $Z$ and $X$
corrections on $\ket{\phi_{1}}$ and $\ket{\phi_{2}}$ (see Fig. 1(a)). A
straightforward derivation using this noise model shows that the minimum
possible process fidelity due to only incorrect $Z$ and $X$ corrections
(without the fixed infidelity from the idle time and CNOT gates) is 0.25,
which converts to a gate fidelity of 0.4.

The measurement-based protocol with post-processing performs slightly better
than the dynamic circuits as the former does not incur errors from the
classical feed-forward, allowing us to isolate the impact of classical feed-
forward from other errors, such as the $n+1$ intermediate CNOT gates and mid-
circuit measurements. Note, however, that the post-processing approach is
generally not scalable if further circuit operations follow the teleported
CNOT due to the need to simulate large system sizes, further emphasizing the
advantage of dynamic circuits as errors rooted in classical feedforward are
reduced. Overall, we find that CNOT gates over large distances are more
efficiently executed with dynamic circuits than unitary ones.

###  II.2 Toffoli or CCZ

Dynamic circuits can also be applied to more efficiently compile multi-qubit
gates. As an example, we describe how the CCZ, or Toffoli gate up to two
single-qubit Hadamard gates, can be implemented by optimizing multiple
teleported CNOT gates. Compilation of the unitary circuit on a 1D chain of
$n+3$ qubits using CNOT gates naïvely requires a two-qubit gate depth of
$\mathcal{O}\left(n\right)$. Using dynamic circuits, we can implement this
long-range entangling gate in shallow depth. Naïvely, one could successively
implement each CNOT gate of the typical Toffoli decomposition (shown at the
top of Fig. 2(a)) using the gate teleportation described previously. However,
involving an ancillary qubit between the three system qubits to merge the
teleported gates, as shown at the bottom of Fig. 2(a), allows for a more
efficient implementation with the dynamic circuit; see Fig. 2(b). In total,
this formulation requires $n+1$ measurements, $n+6$ CNOT gates, and 5 feed-
forward operations divided across two sequential steps. Notably, as most
qubits are projectively measured early in the circuit, the idling error should
be low. Thus, we expect this shallow implementation with dynamic circuits to
be advantageous over its unitary counterpart, especially for large $n$.

Figure 2: CCZ with (a) unitary circuit and (b) a dynamic circuit over long
ranges.

##  III State preparation: GHZ

Figure 3:  Preparing long-range entangled states. (a) Illustration of a GHZ
state with chosen qubit spins (spheres) in a superposition of “all up” and
“all down” polarizations (arrows), overlaid on a quantum processor. (b)
Circuits to prepare an $n$-qubit GHZ state using either a unitary (left) or
dynamic (right) circuit. For a 1D qubit chain, the depth of the unitary
(resp., dynamic) circuit scales as $\mathcal{O}(n)$ (resp., $\mathcal{O}(1)$).
If the final state is not directly used, the feed-forward operations can be
implemented in classical post-processing on the output bits (classically
controlled X gates and resets can be omitted). Yellow regions indicate the
idle time during CNOT gates on other qubits as well as during measurement and
feed-forward (which is denoted by duration $\mu$). (c) Error model inputs for
the GHZ preparation circuits. The model incorporates the noisy components of
the circuits: non-zero idle circuit periods (yellow), number of CNOT gates
(pink), and the number of mid-circuit measurements (green). These parameters
are used to derive an error model that yields a lower-bound on the protocol
fidelity, shown in the following panel. (d) Fidelity of preparing the GHZ
state on quantum hardware using unitary, measurement-based post-processing, or
dynamic circuits in the absence or presence of dynamical decoupling (DD). Data
shown with dots. Theory curves based on the error model parameters of panel
(c) shown in dashed lines.

Dynamic circuits can also be used to prepare long-range entangled states. A
prototypical example is the GHZ state [3], shown schematically in Fig. 3(a).
While it can be created using only Clifford gates and thus can be simulated
efficiently on a classical computer [32], it becomes non-simulatable when
followed by a sufficient number of non-Clifford gates in a larger algorithm,
or when inserted as a crucial ingredient in e.g. efficient compilation of
multi-qubit gates [33, 34].

Here, we show that GHZ states with long-range entanglement can be prepared
with dynamic circuits. Although we do not see a clear advantage of dynamic
circuits over unitary ones in this case, we provide a detailed description of
the challenges that must be addressed to realize such an advantage.

For preparation of a GHZ state on a 1D $n$-qubit chain, in Fig. 3, we show the
equivalence between the unitary circuit (left) and dynamic circuit (right).
(For a detailed derivation, see Appendix A.2.) Notably, the unitary equivalent
has a two-qubit gate depth that scales as $\mathcal{O}\left(n\right)$ with
quadratically increasing idle time and $n-1$ total CNOT gates, while the depth
of the dynamic circuits remains constant with linearly increasing idle time,
$3n/2-1$ total CNOT gates, and $n/2-1$ mid-circuit measurements (see Fig.
3(c)). The dynamic circuit incurs less idle time and fewer two-qubit gate
depth at the cost of increased CNOT gates and mid-circuit measurements.
Therefore, we expect dynamic circuits to be advantageous for large system
sizes $n$ and low errors in mid-circuit measurement. For a more detailed
analysis of the error budget, see Appendix D.1.

We explore whether current large-scale superconducting quantum devices enable
an advantage with dynamic circuits for preparation of the entangled GHZ state.
To efficiently verify the preparation of a quantum state $\sigma$, we use the
Monte Carlo state certification that samples from Pauli operators with non-
zero expectation values, as implemented in Ref. [27] and described in detail
in Appendix C.1. As the $n$-qubit GHZ state is a stabilizer state, we can
randomly sample $m$ of the $2^{n}$ stabilizers $\\{S_{i}\\}_{i=1..2^{n}}$ and
approximate the fidelity by $F=\frac{1}{m}\sum_{k=1}^{m}\langle
S_{k}\rangle_{\sigma}+\mathcal{O}\left(\frac{1}{\sqrt{m}}\right)$.

The experimental results of GHZ state preparation with unitary and dynamic
circuits are shown in Fig. 3(d). They all include measurement error mitigation
on the final measurements [35]. On the left, we show the results without
dynamical decoupling. In the unitary case, we observe genuine multipartite
entanglement, defined as state fidelity $F>0.5$ [36], within a confidence
interval of $95\%$ up to 7 qubits with a rapid decay in fidelity with
increasing system size due to coherent errors in two-qubit gates and ZZ
crosstalk errors during idling time [37]. In the dynamic case, we observe
genuine entanglement up to 6 qubits. Here, we do not find a crossover point
after which dynamic circuits have an advantage over unitary circuits. We
attribute the performance of dynamic circuits to several factors, including
the fact that the current implementation results in an average classical
feedforward time that scales with the number of potential mid-circuit
measurement bitstring outcomes, which itself grows exponentially with system
size. By reducing the error induced by idle time during classical feedforward,
we expect dynamic circuits to surpass unitary circuits at $\gtrsim$10
qubits—we can see this by studying the post-processing case, which is
equivalent to the dynamic circuit implementation except that the classical
logic is executed in post-processing, not during execution of the quantum
circuit itself. We expect the exponential scaling of classical feedforward
time to be reduced to linear or constant scaling in the near term.

On the right of Fig. 3(d), we show the results using dynamical decoupling (DD)
[38, 39]. We observe improved fidelities for both the unitary and dynamic
circuit cases, but not for the post-processing case as there is little error
induced by idle times to quench with dynamical decoupling in the first place.
For the unitary case, we observe genuine multipartite entanglement up to 17
qubits, more than twice as many compared to the unmitigated unitary case. This
result is close to the state of the art on superconducting quantum processors
and is limited by the fact that we do not leverage the 2D connectivity of the
device, as in Ref. [40]. While the fidelities are improved with DD for dynamic
circuits, the improvement is less dramatic. We attribute this difference to
two reasons: First, the unitary circuit has a quadratic idling error term in
contrast to a leading linear term for dynamic circuits, resulting in
comparatively smaller improvement for dynamic circuits with dynamical
decoupling. Second, with the current controls, we are not able to apply DD
pulses during the classical feedforward time, which is the main source of
idling error in the dynamic circuit. As in the unmitigated case, we observe
rapid decay of the fidelity with increasing system. This can again be
partially attributed to exponential growth of the classical feedforward time.
In the near future, we expect to reduce this scaling to linear, in which case
we expect drastically improved performance and genuine entanglement up to
$\sim$15 qubits. Still, however, we do not expect to observe an advantage with
dynamic circuits for preparation of GHZ states over unitary ones. To realize
an advantage with dynamic circuits, we require a scenario where the
quadratically scaling idle error of the unitary circuit dominates over
sufficiently small CNOT and mid-circuit measurement error; see Appendix D.2
for a more detailed analysis. We anticipate these conditions can be realized
through a combination of hardware improvements and the extension of error
mitigation techniques, such as probabilistic error cancellation [41, 42],
toward mid-circuit measurements.

##  IV Conclusion and Outlook

Dynamic circuits are a promising feature toward overcoming connectivity
limitations of large-scale noisy quantum hardware. Here, we demonstate their
potential for efficiently generating long-range entanglement with two useful
tasks: teleporting entangling gates over long ranges to enable effective all-
to-all connectivity, and state preparation with the GHZ state as an example.
For CNOT gate teleportation, we show a regime in which dynamic circuits result
in higher fidelities on up to 101 qubits of a large-scale superconducting
quantum processor. We leave incorporating this more efficient implementation
of long-range entangling gates as a subroutine in another quantum algorithm to
future work; potential studies can include simulating many-body systems with
non-local interactions. As we demonstrate theoretically, gate teleportation
schemes can be extended beyond CNOT gates to multi-qubit ones, such as the CCZ
gate. Its experimental implementation is also a promising project for the
future. For state preparation, based on both unmitigated and mitigated
hardware experiments, we expect to see the value of dynamic circuits once the
classical post-processing becomes more efficient and the mid-circuit
measurement errors can be reduced. We plan on revising the experiments as soon
these capabilities are available. We anticipate that further experiments with
dynamic circuits and the development of noise models describing them will be
vital contributions toward efficient circuit compilation, measurement-based
quantum computation, and fault-tolerant quantum computation.

##  V Acknowledgements

We thank Diego Ristè, Daniel Egger, and Alexander Ivrii for valuable
discussions and feedback. We thank Emily Pritchett, Maika Takita, Abhinav
Kandala, and Sarah Sheldon for their help. We also thank Thomas Alexander,
Marius Hillenbrand, and Reza Jokar for their support with implementing dynamic
circuits.

## References

  * Preskill [2018] J. Preskill, Quantum computing in the NISQ era and beyond, Quantum 2, 79 (2018).
  * Terhal [2015] B. M. Terhal, Quantum error correction for quantum memories, Rev. Mod. Phys. 87, 307 (2015).
  * Greenberger  _et al._ [1989] D. M. Greenberger, M. A. Horne, and A. Zeilinger, Going beyond bell’s theorem, in  _Bell’s Theorem, Quantum Theory and Conceptions of the Universe_, edited by M. Kafatos (Springer Netherlands, Dordrecht, 1989) pp. 69–72.
  * Raussendorf  _et al._ [2005] R. Raussendorf, S. Bravyi, and J. Harrington, Long-range quantum entanglement in noisy cluster states, Phys. Rev. A 71, 062313 (2005).
  * Dennis  _et al._ [2002] E. Dennis, A. Kitaev, A. Landahl, and J. Preskill, Topological quantum memory, J. Math. Phys. 43, 4452 (2002).
  * Piroli  _et al._ [2021] L. Piroli, G. Styliaris, and J. I. Cirac, Quantum circuits assisted by local operations and classical communication: Transformations and phases of matter, Phys. Rev. Lett. 127, 220503 (2021).
  * Lu  _et al._ [2022] T.-C. Lu, L. A. Lessa, I. H. Kim, and T. H. Hsieh, Measurement as a shortcut to long-range entangled quantum matter, PRX Quantum 3, 040337 (2022).
  * Verresen  _et al._ [2021] R. Verresen, N. Tantivasadakarn, and A. Vishwanath, Efficiently preparing schrödinger’s cat, fractons and non-abelian topological order in quantum devices,(2021), arXiv:2112.03061 (2021).
  * Tantivasadakarn  _et al._ [2021] N. Tantivasadakarn, R. Thorngren, A. Vishwanath, and R. Verresen, Long-range entanglement from measuring symmetry-protected topological phases, arXiv:2112.01519 (2021).
  * Tantivasadakarn  _et al._ [2022] N. Tantivasadakarn, R. Verresen, and A. Vishwanath, The shortest route to non-abelian topological order on a quantum processor, arXiv:2209.03964 (2022).
  * Tantivasadakarn  _et al._ [2023] N. Tantivasadakarn, A. Vishwanath, and R. Verresen, Hierarchy of topological order from finite-depth unitaries, measurement, and feedforward, PRX Quantum 4, 020339 (2023).
  * Bravyi  _et al._ [2022] S. Bravyi, I. Kim, A. Kliesch, and R. Koenig, Adaptive constant-depth circuits for manipulating non-abelian anyons, arXiv:2205.01933 (2022).
  * Lu  _et al._ [2023] T.-C. Lu, Z. Zhang, S. Vijay, and T. H. Hsieh, Mixed-state long-range order and criticality from measurement and feedback, PRX Quantum 4, 030318 (2023).
  * Lieb and Robinson [1972] E. H. Lieb and D. W. Robinson, The finite group velocity of quantum spin systems, Commun. Math. Phys. 28, 251 (1972).
  * Bravyi  _et al._ [2006] S. Bravyi, M. B. Hastings, and F. Verstraete, Lieb-robinson bounds and the generation of correlations and topological quantum order, Phys. Rev. Lett. 97, 050401 (2006).
  * Raussendorf  _et al._ [2003] R. Raussendorf, D. E. Browne, and H. J. Briegel, Measurement-based quantum computation on cluster states, Phys. Rev. A 68, 022312 (2003).
  * Jozsa [2005] R. Jozsa, An introduction to measurement based quantum computation, arXiv:0508124 (2005).
  * Beverland  _et al._ [2022] M. Beverland, V. Kliuchnikov, and E. Schoute, Surface code compilation via edge-disjoint paths, PRX Quantum 3, 10.1103/prxquantum.3.020342 (2022).
  * Barrett  _et al._ [2004] M. D. Barrett, J. Chiaverini, T. Schaetz, J. Britton, W. M. Itano, J. D. Jost, E. Knill, C. Langer, D. Leibfried, R. Ozeri, and D. J. Wineland, Deterministic quantum teleportation of atomic qubits, Nature 429, 737 (2004).
  * Pfaff  _et al._ [2012] W. Pfaff, T. H. Taminiau, L. Robledo, H. Bernien, M. Markham, D. J. Twitchen, and R. Hanson, Demonstration of entanglement-by-measurement of solid-state qubits, Nat. Phys. 9, 29 (2012).
  * Ristè  _et al._ [2013] D. Ristè, M. Dukalski, C. A. Watson, G. de Lange, M. J. Tiggelman, Y. M. Blanter, K. W. Lehnert, R. N. Schouten, and L. DiCarlo, Deterministic entanglement of superconducting qubits by parity measurement and feedback, Nature 502, 350 (2013).
  * Wan  _et al._ [2019] Y. Wan, D. Kienzler, S. D. Erickson, K. H. Mayer, T. R. Tan, J. J. Wu, H. M. Vasconcelos, S. Glancy, E. Knill, D. J. Wineland, A. C. Wilson, and D. Leibfried, Quantum gate teleportation between separated qubits in a trapped-ion processor, Science 364, 875 (2019).
  * Córcoles  _et al._ [2021] A. D. Córcoles, M. Takita, K. Inoue, S. Lekuch, Z. K. Minev, J. M. Chow, and J. M. Gambetta, Exploiting dynamic quantum circuits in a quantum algorithm with superconducting qubits, Phys. Rev. Lett. 127, 100501 (2021).
  * Foss-Feig  _et al._ [2023] M. Foss-Feig, A. Tikku, T.-C. Lu, K. Mayer, M. Iqbal, T. M. Gatterman, J. A. Gerber, K. Gilmore, D. Gresh, A. Hankin, N. Hewitt, C. V. Horst, M. Matheny, T. Mengle, B. Neyenhuis, H. Dreyer, D. Hayes, T. H. Hsieh, and I. H. Kim, Experimental demonstration of the advantage of adaptive quantum circuits, arXiv:2302.03029 (2023).
  * Iqbal  _et al._ [2023] M. Iqbal, N. Tantivasadakarn, T. M. Gatterman, J. A. Gerber, K. Gilmore, D. Gresh, A. Hankin, N. Hewitt, C. V. Horst, M. Matheny, T. Mengle, B. Neyenhuis, A. Vishwanath, M. Foss-Feig, R. Verresen, and H. Dreyer, Topological order from measurements and feed-forward on a trapped ion quantum computer, arXiv:2302.01917 (2023).
  * Moses  _et al._ [2023] S. Moses, C. Baldwin, M. Allman, R. Ancona, L. Ascarrunz, C. Barnes, J. Bartolotta, B. Bjork, P. Blanchard, M. Bohn, _et al._ , A race track trapped-ion quantum processor, arXiv:2305.03828 (2023).
  * Cao  _et al._ [2023] S. Cao, B. Wu, F. Chen, M. Gong, Y. Wu, Y. Ye, C. Zha, H. Qian, C. Ying, S. Guo, Q. Zhu, H.-L. Huang, Y. Zhao, S. Li, S. Wang, J. Yu, D. Fan, D. Wu, H. Su, H. Deng, H. Rong, Y. Li, K. Zhang, T.-H. Chung, F. Liang, J. Lin, Y. Xu, L. Sun, C. Guo, N. Li, Y.-H. Huo, C.-Z. Peng, C.-Y. Lu, X. Yuan, X. Zhu, and J.-W. Pan, Generation of genuine entanglement up to 51 superconducting qubits, Nature 619, 738 (2023).
  * Smith  _et al._ [2023] K. C. Smith, E. Crane, N. Wiebe, and S. Girvin, Deterministic constant-depth preparation of the aklt state on a quantum processor using fusion measurements, PRX Quantum 4, 020315 (2023).
  * Chen  _et al._ [2023] E. H. Chen, G.-Y. Zhu, R. Verresen, A. Seif, E. Bäumer, D. Layden, N. Tantivasadakarn, G. Zhu, S. Sheldon, A. Vishwanath, S. Trebst, and A. Kandala, Realizing the nishimori transition across the error threshold for constant-depth quantum circuits,  _to appear_ (2023).
  * Flammia and Liu [2011] S. T. Flammia and Y.-K. Liu, Direct fidelity estimation from few pauli measurements, Phys. Rev. Lett. 106, 230501 (2011).
  * da Silva  _et al._ [2011] M. P. da Silva, O. Landon-Cardinal, and D. Poulin, Practical characterization of quantum devices without tomography, Phys. Rev. Lett. 107, 210404 (2011).
  * Gottesman [1998] D. Gottesman, The heisenberg representation of quantum computers, arXiv:9807006 (1998).
  * Hoyer and Spalek [2005] P. Hoyer and R. Spalek, Quantum fan-out is powerful, Theory Comput. 1, 81 (2005).
  * Yang and Rall [2023] W. Yang and P. Rall, Harnessing the power of long-range entanglement for clifford circuit synthesis, arXiv:2302.06537 (2023).
  * Nation and Treinish [2023] P. D. Nation and M. Treinish, Suppressing quantum circuit errors due to system variability, PRX Quantum 4, 010327 (2023).
  * Leibfried  _et al._ [2005] D. Leibfried, E. Knill, S. Seidelin, J. Britton, R. B. Blakestad, J. Chiaverini, D. B. Hume, W. M. Itano, J. D. Jost, C. Langer, R. Ozeri, R. Reichle, and D. J. Wineland, Creation of a six-atom ‘schrödinger cat’ state, Nature 438, 639 (2005).
  * Tripathi  _et al._ [2022] V. Tripathi, H. Chen, M. Khezri, K.-W. Yip, E. Levenson-Falk, and D. A. Lidar, Suppression of crosstalk in superconducting qubits using dynamical decoupling, Phys. Rev. Appl. 18, 024068 (2022).
  * Viola  _et al._ [1999] L. Viola, E. Knill, and S. Lloyd, Dynamical decoupling of open quantum systems, Phys. Rev. Lett. 82, 2417 (1999).
  * Jurcevic  _et al._ [2021] P. Jurcevic, A. Javadi-Abhari, L. S. Bishop, I. Lauer, D. F. Bogorin, M. Brink, L. Capelluto, O. Günlük, T. Itoko, N. Kanazawa, A. Kandala, G. A. Keefe, K. Krsulich, W. Landers, E. P. Lewandowski, D. T. McClure, G. Nannicini, A. Narasgond, H. M. Nayfeh, E. Pritchett, M. B. Rothwell, S. Srinivasan, N. Sundaresan, C. Wang, K. X. Wei, C. J. Wood, J.-B. Yau, E. J. Zhang, O. E. Dial, J. M. Chow, and J. M. Gambetta, Demonstration of quantum volume 64 on a superconducting quantum computing system, Quantum Sci. Technol. 6, 025020 (2021).
  * Mooney  _et al._ [2021] G. J. Mooney, G. A. L. White, C. D. Hill, and L. C. L. Hollenberg, Generation and verification of 27-qubit greenberger-horne-zeilinger states in a superconducting quantum computer, J. Phys. Commun. 5, 095004 (2021).
  * Temme  _et al._ [2017] K. Temme, S. Bravyi, and J. M. Gambetta, Error mitigation for short-depth quantum circuits, Phys. Rev. Lett. 119, 180509 (2017).
  * van den Berg  _et al._ [2023] E. van den Berg, Z. K. Minev, A. Kandala, and K. Temme, Probabilistic error cancellation with sparse pauli–lindblad models on noisy quantum processors, Nat. Phys. 19, 1116 (2023).
  * Jamiołkowski [1972] A. Jamiołkowski, Linear transformations which preserve trace and positive semidefiniteness of operators, Rep. Math. Phys. 3, 275 (1972).
  * Horodecki  _et al._ [1999] M. Horodecki, P. Horodecki, and R. Horodecki, General teleportation channel, singlet fraction, and quasidistillation, Phys. Rev. A 60, 1888 (1999).

##  Appendix A Circuit Derivations

Figure 4: Useful circuit identities that are used in the illustrative
derivation of the CNOT gate teleportation and GHZ state preparation.

In the following we show the circuit equivalences of the CNOT gate
teleportation (Fig. 1(a)) and the GHZ state preparation (Fig. 3(b)). We are
not claiming any novelty with this “proof”, but just wanted to show the reader
how to derive them in an illustrative way. Before, let us start with some
features that we will be using:

  * •

The Bell state $\frac{1}{\sqrt{2}}(\ket{00}+\ket{11})$ can be illustrated as a
so-called “cup”, as shown in Fig. 4(a), We can move gates along wires
including along the cup, as in Fig. 4(b).

  * •

Principle of deferred measurement: a controlled gate followed by a measurement
of the controlled qubit results in the same as first performing the
measurement and then applying a classically-controlled gate as in Fig. 4(c).

  * •

While CNOT gates commute when they are conditioned on the same qubit or have
the same target qubit, we get an extra gate when they act on the same qubit
differently as shown in Fig. 4(d).

###  A.1 Long-Range CNOT

Figure 5: Graphical derivation for reducing a long-range CNOT gate into gate
teleportation executed with measurements and feed-forward operations, i.e., a
dynamic circuit. Roman numerals indicate sequential step numbers described in
main text.

In Fig. 5 we illustrate a derivation of the CNOT gate teleportation, as
exemplified for $7$ qubits, which can be straightforwardly extended to an
arbitrary number of qubits. In the following, we provide explanations for each
step of the derivation, labeled by roman numerals in the figure:

  1. (i)

In the first step, we observe that entangling, measuring, and resetting the
ancilla qubits does not affect the circuit.

  2. (ii)

We insert CNOT gates that would cancel each other. From now on we omit to
write down the reset of the ancilla qubits following the measurement.

  3. (iii)

We move the pink CNOT gates along the Bell states to the respective qubits
above. Also, we add Hadamard gates to flip the direction of the orange CNOT
gates (except for the one at the bottom). Note that we can omit the hadamard
gates right before the measurements, as they are not affecting the other
qubits anymore.

  4. (iv)

By moving the bottom orange CNOT “up” along the Bell state and passing a pink
CNOT, we get the extra purple CNOT gate.

  5. (v)

Moving the new purple CNOT “up” along the Bell state, an extra gate appears
that cancels with the initial long-range CNOT gate when pushed to the left
(and then it is controlled on state $\ket{0}$, so can be omitted as well).

  6. (vi)

Now we make use of the principle of deferred measurement.

  7. (vii)

In a final step we merge the classically-conditioned gates. The orange
$\oplus$ correspond to XOR gates, i.e. addition mod 2. We also represented the
initial Bell states again with their circuit representation.

###  A.2 GHZ state preparation

Figure 6: Graphical derivation for the preparation of a GHZ state by
converting its canonical but deep unitary circuit into a constant-depth
circuit utilizing measurement and feed-forward operations—a dynamic circuit.
Roman numerals indicate sequential step numbers described in main text.

In Fig. 6 we have illustrated a derivation of the GHZ state preparation,
exemplary for $7$ qubits, but it can be straightforwardly extended to an
arbitrary number of qubits. In the following, we provide explanations for each
step of the derivation, labeled by roman numerals in the figure:

  1. (i)

Pushing every second CNOT gate to the very right introduces the extra pink
CNOT gates.

  2. (ii)

We can omit CNOT gates that are conditioned on state $\ket{0}$.

  3. (iii)

As every second qubit is only involved at the very end, we can use those
before and reset them.

  4. (iv)

A Bell state followed by a CNOT gate results in two uncorrelated qubits in
states $\ket{+}$ and $\ket{0}$.

  5. (v)

We move the pink CNOT gates along the Bell states to the respective qubits
above (they commute with the other CNOTs they are “passing”).

  6. (vi)

Pushing the pink CNOT gates to the left through the purple CNOT gates
introduces the extra orange CNOT gates.

  7. (vii)

We make use of the principle of deferred measurement.

  8. (viii)

In a final step we merge the classically-conditioned gates. As the classical
calculation can be done extremely fast compared to quantum gates, we draw it
as a vertical line. The orange $\oplus$ correspond to XOR gates, i.e. addition
mod 2. We also represented the initial Bell states again with their circuit
representation.

##  Appendix B CNOT circuits

###  B.1 Unitary variants

In order to compare the dynamic circuits implementation to a solely unitary
one, let us first consider different unitary strategies that might be more or
less powerful in different regimes:

Strategy I: Ancilla-based implementation
We can consider a similar setting as for dynamic circuits, where we place the
system qubits in a way that they are connected by a bus of empty ancilla
qubits. In this case, we need to swap the system qubits towards each other and
back, so that the ancillas are empty in the end again. The swaps can be
simplified since the ancillas are empty in the beginning. Here we can divide
into different scenarios:

  * •

Circuit Ia: To minimize the number of CNOT gates, we could swap the controlled
qubit all the way to the target qubit and back, which results in the circuit
depicted in Fig. 7. Here, a lot of gates cancel, so given $n$ ancilla qubits,
the number of CNOT gates is $2n+1$. However, here the idle time of the qubits
while they are not in state $\ket{0}$ equals $n^{2}+2n$ times the CNOT gate
time.

  * •

Circuit Ib: In order to decrease the idle time, we could essentially swap
both, the controlled qubit and the target qubit half-way and back as
illustrated in Fig. 7. In that case, less gates “cancel”, so for $n$ ancilla
qubits we get $3n+1$ CNOT gates, but the idle time reduces to
$\frac{n^{2}}{4}+n$ times the CNOT gate time.

  * •

Circuit Ic: If we wanted to reduce the idle time even further, it might be
beneficial to not cancel the CNOT gates in scenario 1b), but keep them to
bring the swapped qubits back to state $\ket{0}$ as shown in Fig. 7. In that
case, we have essentially no idle time (as qubits in state $\ket{0}$ are not
prone to idling errors). Here, the number of CNOT gates increased to $4n+1$
though.

Strategy II: SWAP-based implementation without ancillas
This is the case that happens if we just feed our circuit to the transpiler.
Here we do not use any ancilla qubits, but only system qubits and apply swaps
to move them around. The qubits can be at a different location in the end, so
we do not need to swap back. The corresponding circuit is shown in Fig. 7. In
this case we require $3\tilde{n}+1$ CNOT gates and the idle time is
$\frac{3}{2}\tilde{n}^{2}-2\tilde{n}$ times the CNOT gate time. However, it is
important to note here that the number of qubits lying between the two qubits
of interest $\tilde{n}$ is on average much shorter than the number of ancillas
between two system qubits in the first scenario. Considering the connectivity
illustrated in Fig. 1 (c), the relation is approximately $n=2\tilde{n}+3$.

Figure 7: Comparison of the different unitary implementations of a long-range
CNOT gate. While the circuits in panels (Ia), (Ib), and (Ic) realize ancilla-
based implementations, the circuit of panel (II) realizes a SWAP-based
implementation without ancillas. The shaded regions indicate idle periods that
accumulate errors.

###  B.2 Error budget

Let us now compare the regimes in which we expect the different
implementations to be most useful to demonstrate the benefit of dynamic
circuits. In Appendix E we derive a simple noise model that allows us to
compute the combined effect of different sources of decoherence as a single
Pauli noise rate:

$\displaystyle\lambda_{\mathrm{tot}}=t_{\mathrm{idle}}\lambda_{\mathrm{idle}}+N_{\mathrm{CNOT}}\lambda_{\mathrm{CNOT}}+N_{\mathrm{meas}}\lambda_{\mathrm{meas}}\;.$
(1)

In Lemma 1 we show that the final process fidelity is loosely lower-bounded by
$e^{-\lambda_{\mathrm{tot}}}$. The quantity $\lambda_{\mathrm{tot}}$ combines
the following noise sources:

  * •

The total amount of time $t_{\mathrm{idle}}$ that qubits spend idle within the
circuit, and a conversion factor $\lambda_{\mathrm{idle}}$ that quantifies the
strength of decoherence. $t_{\mathrm{idle}}$ is expressed in multiples of the
CNOT gate time (i.e. $t_{\mathrm{idle}}=3$ for 3 CNOT gate times). The time
for a mid-circuit measurement, including the additional time waiting for
feedback, is defined as $\mu$ times the time for a CNOT gate.

  * •

The total number of CNOT gates $N_{\mathrm{CNOTs}}$ and an average Pauli noise
rate $\lambda_{\mathrm{CNOT}}$ per CNOT.

  * •

The total number of mid-circuit measurements $N_{\mathrm{meas}}$ and an
average Pauli noise rate $\lambda_{\mathrm{meas}}$ per measurement.

In Table 1, we have summarized the error budget for each of the cases.

Case |  | $t_{\mathrm{idle}}$
---
| $N_{\mathrm{CNOT}}$
---
| $N_{\mathrm{meas}}$
---
|  Two-qubit gate depth
---
Unitary Ia) | $n^{2}+2n$ | $2n+1$ | $0$ | $2n+1$
Unitary Ib) | $\frac{n^{2}}{4}+n$ | $3n+1$ | $0$ | $2n+1$
Unitary Ic) | $0$ | $4n+1$ | $0$ | $2n+1$
Unitary II) | $\frac{3}{4}\tilde{n}^{2}-\frac{3}{2}\tilde{n}$ | $3\tilde{n}+1$ | $0$ | $\frac{3}{2}\tilde{n}+1$
Unitary II) with normed $n$ | $\approx\frac{3}{16}n^{2}-\frac{15}{8}n+\frac{45}{16}$ | $\approx\frac{3}{2}n-2$ | $0$ | $\approx\frac{3}{4}n-\frac{5}{4}$
Dynamic circuits | $2\mu+2$ | $n+1$ | $n$ |  $2+\mu$, or $O(1)$
Table 1: Comparison of the error budget of the unitary and the dynamic
circuits implementation in terms of idle time, number of CNOT gates and mid-
circuit measurements and two-qubit gate depth. Note, that as the number of
involved qubits $\tilde{n}$ needed for the unitary implementation II) is in
general much smaller, we rescale it for the error budget with the relation
$n\approx 2\tilde{n}+3$

Comparing the different unitary cases it becomes clear that for large $n$ the
unitary implementation Ic) will be the best, as all other implementations have
an error in the idling time that scales quadratically. This might be slightly
counter-intuitive, as it tells us that even without measurement and feed-
forward, it can be still beneficial to use ancilla qubits and thereby increase
the distances. For small $n$ we need to keep in mind that for the swap-based
implementation (unitary II) the number of involved qubits $\tilde{n}$ is
smaller than the number of qubits $n$ needed for the same task in the ancilla-
based implementation. Respecting the rescaled errors, unitary II would be the
most promising implementation for small $n$. In addition to the CNOT errors
and idling errors, for dynamic circuits we also need to consider the error
from the additional measurements, as well as a constant term $\mu$ that comes
from the idling error during measurement and feed-forward.

Given this rough error analysis in Table 1, we can infer that for large $n$
dynamic circuits will be beneficial if the measurement of $n$ qubits
introduces less error than $3n$ CNOT gates, that is, when
$\lambda_{\mathrm{meas}}<3\lambda_{CNOT}$. A sketch of how the fidelities for
the different cases decrease with $n$ is illutrated in Fig. 8. Note, that
these error analyses only take into account the error on the involved qubits
though. Considering also the fact that there are potentially a lot of other
$m$ qubits “waiting” for this operation to be performed would add another
idling error of $m\cdot(2n+1)$. So the fact that dynamic circuits can perform
entangled gates between arbitrary qubits in constant depth instead of linear
depth with only unitary operations speeds up the whole algorithm and therefore
might be much more powerful than what we can see in the error on the
respective qubits.

Figure 8: Comparison of the process fidelities of the different unitary
implementations as well as the dynamic circuits implementation considering the
error budget indicated in Table 1. In this figure we use
$\mu=(t_{\text{meas}}+t_{\text{feed-forward}})/t_{\text{cnot}}\approx 3.65$,
$\lambda_{\mathrm{idle}}=0.03$, $\lambda_{\mathrm{CNOT}}=0.02$ and
$\lambda_{\mathrm{meas}}=0.03$.

##  Appendix C Estimation of the state and gate fidelities using Monte-Carlo
sampling

###  C.1 State fidelity

In order to determine the fidelity of the experimentally prepared quantum
state, denoted as $\sigma$, we employ the Monte Carlo state certification
method, which was introduced inRefs. [31, 30]. We first briefly review the
notion of fidelity between two quantum states.

#### Quantum state fidelity.

Let us introduce the Uhlmann-Jozsa state fidelity between two general quantum
states $\rho$ and $\sigma$. These objects are elements of the space of valid
density operators associated with the system Hilbert space, $\mathcal{H}$,
i.e., $\rho,\sigma\in D\left(\mathcal{H}\right)$. Assuming one of them is a
pure state
$\sigma=\left|\phi\vphantom{\phi}\right\rangle\left\langle\vphantom{\phi}\phi\right|$,
we can simplify the general expression as shown in the following:

$\displaystyle F\left(\rho,\sigma\right)$
$\displaystyle\coloneqq\left[\operatorname{Tr}\left(\sqrt{\sqrt{\rho}\sigma\sqrt{\rho}}\right)\right]^{2}$
(2) $\displaystyle=\left\langle\phi\middle|\rho\middle|\phi\right\rangle$ (3)
$\displaystyle=\operatorname{Tr}\left[\rho\sigma\right]\;.$ (4)

If $\rho$ is also a pure state
$\rho=\left|\psi\vphantom{\psi}\right\rangle\left\langle\vphantom{\psi}\psi\right|$,
the expression reduces to a simple overlap
$F\left(\rho,\sigma\right)=\left|\left\langle\psi\middle|\phi\right\rangle\right|^{2}$.
We note that some authors define the square root of this as the fidelity.

#### Pauli decomposition.

To connect to experimental measurements, let us decompose the quantum sates in
the standard Pauli basis. The set of all Pauli operators on $n$ qubits
$\left\\{I,X,Y,Z\right\\}^{\otimes n}$ forms an orthogonal Hermitian operator
basis. The inner product in operator space $L\left(\mathcal{H}\right)$ between
two Pauli operators $P_{i},P_{j}\in\mathcal{L}\left(\mathcal{H}\right)$ is
$\left\langle
P_{i},P_{j}\right\rangle=\operatorname{Tr}\left(P_{i}P_{j}\right)=d\delta_{ij}$,
where the dimension of the pure state Hilbert space
$d\coloneqq\dim\mathcal{H}=2^{n}$. In terms of this basis, any quantum state
$\rho\in D\left(\mathcal{H}\right)$, can be decomposed into

$\rho=\sum_{i=0}^{4^{n}-1}\frac{\left\langle
P_{i},\rho\right\rangle}{\left\langle
P_{i},P_{i}\right\rangle}P_{i}=\frac{1}{d}\sum_{i=0}^{4^{n}-1}\rho_{i}P_{i}\;,\quad\mathrm{with}\quad\rho_{i}\coloneqq\left\langle
P_{i},\rho\right\rangle=\operatorname{Tr}\left(P_{i}\rho\right)\;,$

where the Pauli expectation value of the state with respect to the $i$-th
Pauli is $\rho_{i}$—an easily measurable quantity. We can similarly define the
expectation values of the Pauli $P_{i}$ with respect to the prepared state
$\sigma$ and the desired state $\rho$ as $\sigma_{i}:=\langle
P_{i}\rangle_{\sigma}=\text{Tr}\left(\sigma P_{i}\right)$ and
$\rho_{i}:=\langle P_{i}\rangle_{\rho}=\text{Tr}\left(\rho P_{i}\right)$,
respectively.

#### Fidelity in terms of Pauli expectation values.

The state fidelity between the measured $\sigma$ and ideally expected pure
$\rho$ state, see Eq. (2), in terms of the Pauli decomposition of each is

$\displaystyle
F(\rho,\sigma)=\text{Tr}\left[\rho\sigma\right]=\sum_{i}\frac{\rho_{i}\sigma_{i}}{d}=\sum_{i}\frac{\rho_{i}^{2}}{d}\frac{\sigma_{i}}{\rho_{i}}\;,$
(5)

where $\sigma_{i}$ is an experimentally measured expectation value and
$\rho_{i}$ is a theoretically calculated one. Given this, we can now define
the relevance distribution $r(P_{i}):=\frac{\rho_{i}^{2}}{d}$, such that
$F(\rho,\sigma)=\sum_{i:\rho_{i}\neq 0}r(P_{i})\frac{\sigma_{i}}{\rho_{i}}$.

#### Random sampling of expectation values.

When sampling $m$ random operators $\\{P_{k}\\}_{k=1..m}$ according to the
relevance distribution $r(P_{k})$ and determining their expectation values
$\sigma_{k}$, the estimated fidelity
$\tilde{F}:=\sum_{k=1}^{m}\frac{\sigma_{k}}{\rho_{k}}$ approximates the actual
fidelity $F$ with an uncertainty that decreases as $\frac{1}{\sqrt{m}}$. Note
that there is also an uncertainty in estimating each $\sigma_{k}$, where for
an additive precision $\epsilon$ roughly $(\epsilon\rho_{k})^{-2}$ shots are
required.

#### Random sampling of GHZ stabilizers.

As the GHZ state is a stabilizer state, for each $n$ there are exactly $2^{n}$
non-zero Pauli operators $P_{i}$ that each have eigenvalue $\pm 1$. Note that
some stabilizers of the GHZ state have a minus sign, e.g. $-YYX$. For the
$n$-qubit GHZ state, by defining the set of stabilizers
$\\{S_{i}\\}_{i=1..2^{n}}$, we can express the fidelity in terms of only
expectation values on the stabilizers

$\displaystyle F(\rho,\sigma)$
$\displaystyle=\frac{1}{2^{n}}\sum_{i=1}^{2^{n}}\langle
S_{i}\rangle_{\sigma}\;.$ (6)

This expression can be approximated by randomly sampling $m$ of the $2^{n}$
stabilizers, defining the unbiased estimator
$\tilde{F}=\frac{1}{m}\sum_{k=1}^{m}\langle
S_{k}\rangle_{\sigma}=F+\mathcal{O}\left(\frac{1}{\sqrt{m}}\right)$, which
converges with the number of random samples chosen to the ideal fidelity.

###  C.2 Average gate fidelity

Similarly to the state fidelity, we use the Monte Carlo process certification
following [31] to determine the average gate fidelity of our noisy CNOT gate.

#### Average gate fidelity.

Consider the case in which we want to implement an ideal gate
$\mathcal{U}(\rho)\coloneqq U\rho U^{\dagger}$. However, instead we can
implement only a noisy gate
$\tilde{\mathcal{U}}(\rho)\coloneqq\mathcal{U}(\Lambda(\rho))$, where
$\Lambda$ is some effective noise channel and $\rho$ is a quantum state. What
is the gate fidelity of noisy $\tilde{\mathcal{U}}$ relative to the ideal
$\mathcal{U}$. For a single given pure state
$\rho=\left|\phi\vphantom{\phi}\right\rangle\left\langle\vphantom{\phi}\phi\right|$,
the state fidelity of the output of the ideal and noisy channels is

$\displaystyle F\left(\mathcal{U},\tilde{\mathcal{U}};\rho\right)$
$\displaystyle=\left[\operatorname{Tr}\left[\sqrt{\sqrt{\mathcal{U}\left(\rho\right)}\tilde{\mathcal{U}}\left(\rho\right)\sqrt{\mathcal{U}\left(\rho\right)}}\right]\right]^{2}$
(7)
$\displaystyle=\operatorname{Tr}\left[\mathcal{U}\left(\rho\right)\tilde{\mathcal{U}}\left(\rho\right)\right]$
(8)
$\displaystyle=\operatorname{Tr}\left[\rho\Lambda\left(\rho\right)\right]\;,$
(9)

which can be used to obtain the average gate fidelity devised by a uniform
Haar average over the fidelity of the ideal and noisy output states, with
$\rho_{\psi}=\left|\psi\vphantom{\psi}\right\rangle\left\langle\vphantom{\psi}\psi\right|$,

$\displaystyle\mathcal{F}_{\mathrm{avg}}\left(\mathcal{U},\tilde{\mathcal{U}}\right)$
$\displaystyle=\int\mathrm{d}\psi\,F\left(\mathcal{U},\tilde{\mathcal{U}};\rho_{\psi}\right)$
(10)
$\displaystyle=\int\mathrm{d}\psi\,\operatorname{Tr}\left[\mathcal{U}\left(\rho\right)\tilde{\mathcal{U}}\left(\rho\right)\right]$
(11)
$\displaystyle=\operatorname{Tr}\left[\int\mathrm{d}\psi\,\left|\psi\vphantom{\psi}\right\rangle\left\langle\vphantom{\psi}\psi\right|\Lambda\left(\left|\psi\vphantom{\psi}\right\rangle\left\langle\vphantom{\psi}\psi\right|\right)\right]\;.$
(12)

To estimate
$\mathcal{F}_{\mathrm{avg}}\left(\mathcal{U},\tilde{\mathcal{U}}\right)$, we
will use the process (or entanglement) fidelity as a more experimentally-
accessible quantity.

#### Process fidelity.

Compared to the gate fidelity, the process fidelity is more readily estimated.
It can in turn serve as a direct proxy to the gate fidelity. To make the
connection, recall that the Choi-Jamiolkowski isomorphism [43] maps every
quantum operation $\Lambda$ on a $d$-dimensional space to a density operator
$\rho_{\Lambda}=(\mathbb{I}\otimes\Lambda)\ket{\phi}\bra{\phi}$, where
$\ket{\phi}=\frac{1}{\sqrt{d}}\sum_{i=1}^{d}\ket{i}\otimes\ket{i}$. For a
noise-free, ideal unitary channel $\mathcal{U}$ and its experimental, noisy
implementation $\tilde{\mathcal{U}}$, the process fidelity
$\mathcal{F}_{\mathrm{proc}}$ is the state fidelity of the respective Choi
states $\rho_{\mathcal{U}}$ and $\rho_{\tilde{\mathcal{U}}}$:

$\displaystyle\mathcal{F}_{\mathrm{proc}}({{\mathcal{U}}},{\tilde{\mathcal{U}}}):=F(\rho_{{\mathcal{U}}},\rho_{\tilde{\mathcal{U}}})\;.$
(13)

From this fidelity, the gate fidelity can be extracted using the following
relation derived in [44]:

$\displaystyle\mathcal{F}_{\mathrm{gate}}({{\mathcal{U}}},{\tilde{\mathcal{U}}})=\frac{d\mathcal{F}_{\mathrm{proc}}(\rho_{{\mathcal{U}}},\rho_{\tilde{\mathcal{U}}})+1}{d+1}\;.$
(14)

#### Estimating the process fidelity.

As described in Ref. [31], instead of a direct implementation of
$(\mathbb{I}\otimes\tilde{\mathcal{U}})\ket{\phi}\bra{\phi}$ followed by
measuring random Pauli operators on all qubits, we follow the more practical
approach, where $\tilde{\mathcal{U}}$ is applied to the complex conjugate of a
random product of eigenstates of local Pauli operators $P_{i}\otimes P_{j}$,
followed by a measurement of random Pauli operators $P_{k}\otimes P_{l}$. This
leads to the same expectation values

$\displaystyle\rho_{ijkl}:=\text{Tr}\left[(P_{i}\otimes P_{j}\otimes
P_{k}\otimes
P_{l})(\mathbb{I}\otimes\mathcal{U})\ket{\phi}\bra{\phi}\right]=\text{Tr}\left[(P_{k}\otimes
P_{l})\mathcal{U}(P_{i}\otimes P_{j})^{\ast}\right]/d\;.$ (15)

The operators are then sampled according to the relevance distribution

$\displaystyle r_{ijkl}:=r(P_{i}P_{j}P_{k}P_{l})=\frac{\rho_{ijkl}^{2}}{d}\;.$
(16)

For $\Lambda(\rho)=\mathrm{CNOT}\rho\mathrm{CNOT}^{\dagger}$, there are only
$16$ combinations of Pauli operators with a non-zero expectation value
$\rho_{ijkl}$: $\rho_{ijkl}=-\frac{1}{2}$ for $P_{i}P_{j}P_{k}P_{l}\in\
\\{YYXZ,XZYY\\}$ and $\rho_{ijkl}=\frac{1}{2}$ for the remaining 14. Thus, the
relevance distribution is uniform amongst those with $r=\frac{1}{16}$ and we
can just take the average expectation value of those $16$ operators.

##  Appendix D Error analysis for GHZ states

###  D.1 Error budget

As in Appendix B.2, we leverage (1) to estimate the total noise
$\lambda_{\mathrm{tot}}$ of a quantum circuit as motivated by the model
discussed in Appendix E. There, it is derived that
$e^{-\lambda_{\mathrm{tot}}}$ gives a lower bound on the _process_ fidelity of
the circuit. For GHZ states however, we are interested the _state_ fidelity,
so the bound from Lemma 1 no longer applies in a rigorous sense. However, we
find that the same model can still provide useful intuition if we accept that
the model parameters $\lambda_{\mathrm{CNOT}},\lambda_{\mathrm{meas}}$ no
longer have a direct interpretation in terms of worst-case Pauli-Lindblad
noise or a combination of amplitude- and phase-damping noise respectively. See
Appendix E for details.

For the unitary approach we require $n$ CNOT gates to entangle $n$ qubits. For
simplicity we assume (and implement) only a one-dimensional connectivity chain
in our protocols and the following numbers correspond to an even number $n$
(only constant terms change when considering odd $n$). To minimize the idling
time, we start in the middle and apply CNOT gates simultaneously towards both
ends. This leads to an idle time of $\frac{n^{2}}{4}-\frac{3}{2}n+2$ times the
CNOT gate time, as displayed in Table 2. In the dynamic circuits approach we
require $\frac{3}{2}n-2$ CNOT gates in total, while the idling time is
$\frac{\mu}{2}n+1$ times the CNOT gate time, where $\mu$ corresponds to the
measurement and feed-forward time (as a multiple of the CNOT gate time).
However, here we also need to consider the errors of the additional
$\frac{n}{2}-1$ measurements. As the error coming from the CNOT gates and the
measurements is usually substantially larger than the error from the idling
time, we expect that for small $n$ the standard unitary preparation succeeds.
However, as the idling time there scales as $\mathcal{O}\left(n^{2}\right)$ in
contrast to all errors in the measurement-based approach scaling only as
$\mathcal{O}\left(n\right)$, we expect a crossover for large $n$, where the
implementation with dynamic circuits will become more beneficial. The error
budget is summarized in Table 2.

Case |  | $t_{\mathrm{idle}}$
---
| $N_{\mathrm{CNOT}}$
---
| $N_{\mathrm{meas}}$
---
|  Two-qubit gate depth
---
Unitary | $n^{2}/4-3n/2+2$ | $n-1$ | $0$ | $n-1$
Dynamic circuits | $1+\mu n/2$ | $3n/2-2$ | $n/2-1$ |  $3+\mu$, or $O(1)$
Table 2: Comparison of the error budget of the unitary and the dynamic
circuits implementation in terms of idle time, number of CNOT gates and mid-
circuit measurements and two-qubit gate depth.

###  D.2 Expected cross-over for lower mid-circuit measurement errors

Here we use the values of $t_{\mathrm{idle}},N_{\mathrm{CNOT}},$ and
$N_{\mathrm{meas}}$ shown in Table 2 to predict how many qubits are required
to see and the state fidelity at the cross-over, or where the performance of
dynamic circuits becomes higher than that of its unitary counterpart, as a
function of the mid-circuit measurement errors. Note that in this noise model
we assume that we can eliminate all ZZ errors by applying dynamical
decoupling. We keep the idling error constant at
$\lambda_{\mathrm{idle}}=0.001$ and consider different CNOT errors
$\lambda_{\mathrm{CNOT}}\in\\{0.001,0.01,0.02\\}$. We can reach a fidelity
$>0.5$ for a CNOT error of $\lambda_{\mathrm{CNOT}}=0.01$ with mid-circuit
measurement errors $\lambda_{\mathrm{meas}}\lesssim 0.003$ and for a CNOT
error $\lambda_{\mathrm{CNOT}}=0.001$ with mid-circuit measurement errors
$\lambda_{\mathrm{meas}}\lesssim 0.012$

Figure 9: Noise-model predictions that indicate how many qubits are required
to see a cross-over and what the corresponding fidelity would be as a function
of the mid-circuit measurement errors.

##  Appendix E Pauli-Lindblad Noise Model

In this section we present a simple framework for computing lower bounds on
fidelities using the Pauli-Lindblad noise model discussed in [42]. Pauli-
Lindblad noise channels have several nice properties that we can use to
simplify calculations, and also allow us to reduce estimates of the noise
properties of our hardware to relatively few parameters.

Normally, Pauli-Lindblad noise is the workhorse of probabilistic error
cancellation - an error mitigation scheme that leverages characterization of
noise in order to trade systematic uncertainty for statistical uncertainty.
But we are more interested in using Pauli-Lindblad noise as a tool for
capturing the behavior of fidelity as a function of circuit size with an
appropriate balance of rigor and simplicity.

As such, our central goal in this section is to develop mathematical tools
that allow us develop a Pauli-Lindblad representation of various noise sources
such as decoherence and gate noise and to find a method to combine all of this
noise into a fidelity for the entire process. In particular, we aim to give a
justification for modeling noise via the quantity $\lambda_{\mathrm{tot}}$ as
in (1). This is achieved by Lemma 1, which states that
$e^{-\lambda_{\mathrm{tot}}}$ gives a lower bound on the process fidelity.

We leave the majority of our mathematical exposition without proof for sake of
brevity, but present the proof of Lemma 1 at the end of this section.

#### Pauli-Lindblad noise.

Pauli-Lindblad noise is a quantum channel defined as follows. Let
$\mathcal{P}$ be the $n$-qubit Pauli group modulo phase, and consider some
$P\in\mathcal{P}$. Then for some noise rate $\lambda\in\mathbb{R}^{+}$ the
noise channel $\Gamma^{\lambda}_{P}$ is given by:

$\displaystyle\Gamma_{P}^{\lambda}(\rho)=(1-\omega)\rho+\omega P\rho
P^{\dagger}\quad\mathrm{where}\quad\omega:=\frac{1-e^{-2\lambda}}{2}\;.$ (17)

This is essentially applying $P$ with probability $\omega$. Pauli noise
channels also have a representation as time evolution with respect to a simple
Lindbladian: for $P\in\mathcal{P}$, let $\mathcal{L}_{P}(\rho):=P\rho P-\rho$.
This way $\Gamma_{P}^{\lambda}=e^{\lambda\mathcal{L}_{P}}$.

The main justification for why we can restrict to Pauli noise channels is
twirling. Conjugating an arbitrary noise channel by a random Pauli matrix
yields a channel that is always expressible as a product of Pauli noise.
Although our experiments do not feature twirling, even for untwirled circuits
we expect the Pauli-Lindblad noise to capture the first-order noise behavior.

Another reason why we expect our noise model to only capture the behavior to
first-order is that we assume the noise rates are the same for all qubits. All
CNOT gates and idle times are assumed to contribute the same amount of noise.
But this is not a realistic representation of our hardware - in actuality
different qubits have different coherence times and gate qualities also vary.
When we consider circuits on many qubits we expect these differences to
average out.

Let $\Lambda$ be a quantum channel. Then let $\tilde{\Lambda}$ be its Pauli-
twirled version given by:

$\displaystyle\tilde{\Lambda}:=\frac{1}{|\mathcal{P}|}\sum_{P\in\mathcal{P}}P\Lambda(P\rho
P)P\;.$ (18)

For $Q\in\mathcal{P}$, twirled channels $\tilde{\Lambda}$ satisfy
$\tilde{\Lambda}(Q)=c_{Q}Q$ for some coefficients $c_{Q}$. For every
$\tilde{\Lambda}$ there exist noise rates $\lambda_{P}$ for
$P\in\mathcal{P}/\\{I\\}$ such that
$\tilde{\Lambda}=\prod_{P}\Gamma_{P}^{\lambda_{P}}$. These noise rates
satisfy:

$\displaystyle c_{Q}=e^{-2\sum_{P}(\lambda_{P}\cdot 1_{PQ=-QP})}\;.$ (19)

A central convenience of Pauli noise channels is that they do not interfere
with each other when propagated: Pauli noise channels commute
$\Gamma^{\lambda_{P}}_{P}\Gamma^{\lambda_{Q}}_{Q}=\Gamma^{\lambda_{Q}}_{Q}\Gamma^{\lambda_{Q}}_{P}$,
and the noise rates can be added together when the Pauli is the same
$\Gamma^{\lambda_{1}}_{P}\Gamma^{\lambda_{2}}_{P}=\Gamma^{\lambda_{1}+\lambda_{2}}_{P}$
.

#### Combining noise channels into a single fidelity.

Say we are trying to compute the overall amount of noise in a particular
quantum circuit that has been appropriately twirled. Gates and idle time of
the qubits all contribute some amount of Pauli noise. We propagate all of the
Pauli noise to the end of the circuit, thereby removing any noise that does
not affect certain mid-circuit measurements. Finally, we must tally up the
noise Paulis on the resulting quantum state.

One metric for measuring the error on the final state is trace distance, or
diamond norm if we are considering a channel. For a single Pauli noise source,
we have the simple relation that for any $P$ we have
$\left|\Gamma^{\lambda}_{P}-I\right|_{\diamond}=1-e^{-2\lambda}$. To
generalize this to multiple Paulis, a simple approach could be to just apply
the triangle inequality to all of the different Paulis. But it turns out we
can do much better using the following bound on the process fidelity:

######  Lemma 1.

Consider a channel $\Lambda=\prod_{P}\Gamma_{P}^{\lambda_{P}}$ for some rates
$\lambda_{P}$. Then
$\mathcal{F}_{\mathrm{proc}}(\Lambda,\mathcal{I})\geq\exp(-\sum_{P}\lambda_{P})$.

This bound is still pretty loose, but it is very simple and does better than
adding up diamond norms. This can be seen by, for example, looking at the
channel $\prod_{i=1}^{N}\Gamma_{P_{i}}^{c/N}$. Lemma 1 gives
$\mathcal{F}_{\mathrm{proc}}\geq\exp(-c)$ while adding up diamond norms and
and converting them to a fidelity bound gives $\mathcal{F}_{\mathrm{proc}}\geq
1-\frac{1}{2}N(1-e^{-2c/N})$. The latter is looser for $N\geq 2$ and for any
$c$.

Lemma 1 also has the key advantage that it makes computation of the overall
noise rate very simple: just add up all the noise rates. This allows us to
simply tally the total idle time and count the number of CNOTs to obtain the
total amount of noise, as in Appendix B.2.

An issue with using Lemma 1 is that it becomes increasingly loose in the limit
of large $\sum_{P}\lambda_{P}$. The quantity $\exp(-\sum_{P}\lambda_{P})$
vanishes in this limit, but in general we have
$\mathcal{F}_{\mathrm{proc}}(\Lambda,\Lambda^{\prime})\geq 1/d$ for all
$\Lambda,\Lambda^{\prime}$. When we only have one source of Pauli noise
$\Gamma_{P}^{\lambda}$ then not even the lower limit of $1/d$ can be reached
as $\lambda\to\infty$. Unfortunately, we see now way of overcoming this
limitation while preserving the mathematical elegance of this tool: we would
like to simply consider the quantity $\sum_{P}\lambda_{P}$. The reason for
this shortcoming is that we do not account for cancellations between Pauli
errors - we discuss the details of the derivation at the end of this section.

Another limitation of this analysis is that it completely ignores crosstalk.
Every gate is assumed to behave independently. Assuming independent errors
corresponds to a worst-case analysis analogous to the union bound, so we would
expect the bounds resulting from Lemma 1 to still roughly capture average
error from crosstalk by accounting for it as $T_{2}$ dephasing noise, an error
that we include when modeling experiments without dynamical decoupling.

#### Propagating noise to the end of the circuit.

Next, we discuss how to move all the noise sources to the end of the circuit.
This is particularly easy since we are considering Clifford circuits. Once all
the noise is in one place, we can use Lemma 1 to combine it into a single
fidelity.

With $\mathcal{U}\cdot\coloneqq U\cdot U^{\dagger}$ as before, elementary
calculation shows that
$\mathcal{U}\Gamma^{\lambda}_{P}=\Gamma^{\lambda}_{\mathcal{U}(P)}\mathcal{U}$,
so Pauli-Lindblad noise propagated through a unitary Clifford circuit is still
Pauli-Lindblad noise.

Our circuits also feature several adaptive gates, propagation through which
can be achieved as follows. Let $\Lambda_{\mathrm{disc}}$ be the channel that
traces out the first of two qubits. Then
$\Lambda_{\mathrm{disc}}\Gamma^{\lambda}_{P\otimes
Q}=\Gamma^{\lambda}_{Q}\Lambda_{\mathrm{disc}}$. Similarly, let
$\Lambda_{\mathrm{corr},P}$ be the channel that measures the first qubit and
applies a correction $P$ onto the second qubit. If $P$ and $Q$ commute, then
$\Lambda_{\mathrm{corr},P}\Gamma^{\lambda}_{Q\otimes
R}=\Gamma^{\lambda}_{R}\Lambda_{\mathrm{corr},P}$. Otherwise,
$\Lambda_{\mathrm{corr},P}\Gamma^{\lambda}_{Q\otimes
R}=\Gamma^{\lambda}_{PR}\Lambda_{\mathrm{corr},P}$.

Now that we have established how to move noise to the end of the circuit and
to tally it into a bound on the fidelity, all that remains is to show how to
bring various noise sources into Pauli-Lindblad form.

#### Decoherence noise.

We begin with decoherence noise that affects idling qubits. We consider
depolarizing, dephasing, and amplitude damping noise.

Conveniently, depolarizing and dephasing noise are already Pauli noise
channels. A depolarizing channel $\Lambda_{\mathrm{dep},q}$ replaces the input
$\rho$ with the maximally mixed state with probability $1-q$:

$\displaystyle\Lambda_{\mathrm{dep},q}(\rho)=q\rho+(1-q)\frac{I}{2^{n}}\;.$
(20)

We derive that
$\Lambda_{\mathrm{dep},q}=\prod_{P\in\mathcal{P}_{n}/\\{I\\}}\Gamma^{\lambda}_{P}$
with $q=\exp(-4^{n}\lambda)$.

The phase damping process is given by the Lindbladian with
$L_{0}=\ket{0}\bra{0}$ and $L_{1}=\ket{1}\bra{1}$:

$\displaystyle\mathcal{L}_{\mathrm{ph}}=\sum_{i\in\\{0,1\\}}L_{i}\rho
L_{i}^{\dagger}-\frac{1}{2}\left\\{L^{\dagger}_{i}L_{i},\rho\right\\}\;.$ (21)

Since $\mathcal{L}_{\mathrm{ph}}=\frac{1}{2}\left(Z\rho Z-\rho\right)$, it
satisfies $e^{\lambda\mathcal{L}_{\mathrm{ph}}}=\Gamma^{\lambda/2}_{Z}$. We
can easily compute $\lambda$ from a phase damping experiment: since
$\bra{+}\Lambda^{\lambda}_{\mathrm{damp}}(\ket{+}\bra{+})\ket{+}=\frac{1}{2}(1+e^{-\lambda})$
we have $\lambda=t/T_{2}$.

The amplitude damping channel is not a Pauli-Lindblad channel, and must be
twirled in order to bring into Pauli-Lindblad form. The amplitude damping
process $\mathcal{L}_{\mathrm{damp}}$ is given by $L=\ket{0}\bra{1}$ with:

$\displaystyle\mathcal{L}_{\mathrm{damp}}(\rho)=L\rho
L-\frac{1}{2}\left\\{L^{\dagger}L,\rho\right\\}\;.$ (22)

If we let
$\Lambda^{\lambda}_{\mathrm{damp}}:=e^{\lambda\mathcal{L}_{\mathrm{damp}}}$
then we have
$\tilde{\Lambda}^{\lambda}_{\mathrm{damp}}=\Gamma^{\lambda/4}_{X}\Gamma^{\lambda/4}_{Y}$.
Similarly, $\lambda$ can be obtained from an amplitude damping experiment:
since
$\bra{1}\Lambda^{\lambda}_{\mathrm{damp}}(\ket{1}\bra{1})\ket{1}=e^{-\lambda}$
we straightforwardly have $\lambda=t/T_{1}$.

If we have both dephasing and amplitude damping noise, we can combine the two
together as follows. For some $T_{1},T_{2}$, consider the combined noise
channel
$\Lambda^{t}_{\mathrm{noise}}=\exp\left(\frac{t}{T_{1}}\mathcal{L}_{\mathrm{damp}}+\frac{t}{T_{2}}\mathcal{L}_{\mathrm{ph}}\right)$.
Then:

$\displaystyle\tilde{\Lambda}^{t}_{\mathrm{noise}}=\Gamma_{X}^{\frac{t}{4T_{1}}}\Gamma_{Y}^{\frac{t}{4T_{1}}}\Gamma_{Z}^{\frac{t}{2T_{2}}}\;.$
(23)

This follows from the fact that $\mathcal{L}_{\mathrm{damp}}$ and
$\mathcal{L}_{\mathrm{ph}}$ commute.

#### Noise from unitary gates.

In principle we could perform experiments, as in [42], to determine the exact
Pauli rates for each unitary, as is necessary for probabilistic error
cancellation. However, two-qubit gates like the CNOT gate have fifteen noise
parameters corresponding to the $4^{2}-1$ nontrivial two-qubit Pauli
operators. For our purposes we would prefer to model CNOT noise using just a
single number.

One approach could be to just assume that the CNOT noise is simply
depolarizing noise. In this case, all fifteen Pauli noise rates are equal and
can be connected to the process fidelity. Say we aim to implement an ideal
unitary $U$, but our hardware can only implement
$\bar{\mathcal{U}}=\mathcal{U}\Lambda_{\mathrm{dep},q}$ up to a known fidelity
$F(\mathcal{U},\bar{\mathcal{U}})$. Then
$q=(4^{n}F(\mathcal{U},\bar{\mathcal{U}})-1)/(4^{n}-1).$

However, it turns out that spreading out the error uniformly over all the
Paulis is rather cumbersome because it requires propagating every possible
Pauli error. A more tractable approach is to just consider the worst case
Pauli error. In that case, For any unitary $U$ and $P\in\mathcal{P}$, we have
$F(\mathcal{U},\mathcal{U}\Gamma_{P}^{\lambda})=(1+e^{-2\lambda})/2$.

#### Conclusions.

We have derived a rigorous justification for a rather simple strategy for
deriving theoretical predictions of noisy superconducting quantum hardware.
Expressions for noise as a function of circuit size can be derived simply by
counting the amount of idle time, CNOT gates, and number of mid-circuit
measurements. The model has very few parameters, which are simply the Pauli-
Lindblad noise rates corresponding to each of these operations (sometimes per
unit time). These different noise rates are added up and converted to a
fidelity via Lemma 1.

The advantage of a rigorous derivation is that we can directly see the ways in
which this model fails to tightly capture the actual error. A central issue is
that Lemma 1 does not take into account cancellation between various noise
sources, causing the fidelity to approach zero in the limit of high rate. This
is despite the fact that the worst possible process fidelity is nonzero.
Another oversimplification is that we do not capture the fact that not all
possible Pauli noise rates can affect a given observable. We also cannot
capture correlations between errors, as may be the case with crosstalk, and
instead take a worst-case approach reminiscent of the union-bound. All of
these reasons indicate that this model should produce relatively loose lower
bounds.

###### Proof of Lemma 1..

Say $\Lambda(\rho)=\sum_{P,Q}c_{P,Q}P\rho Q$. Then
$\mathcal{F}_{\mathrm{proc}}(I,\Lambda)=\mathcal{F}_{\mathrm{proc}}(I,\tilde{\Lambda})=c_{I,I}$.

The proof proceeds with two loose lower bounds that notably fail to capture
cancellations between different error sources. Given
$\Lambda=\prod_{P}\Gamma_{P}^{\lambda_{P}}$, recall that
$\Gamma_{P}^{\lambda_{P}}(\rho)=(1-\omega_{P})\rho+\omega_{P}P\rho
P^{\dagger}$. Expanding out $\Lambda$, we see that:

$\displaystyle
c_{I,I}\geq\prod_{P}(1-\omega_{P})=\prod_{P}\frac{1+e^{-2\lambda_{P}}}{2}\;.$
(24)

Next, observing that $(1+e^{-2x})/2\geq e^{-x}$ for $x>0$:

$\displaystyle...\geq\prod_{P}e^{-\lambda_{P}}=\exp\left(-\sum_{P}\lambda_{P}\right)\;.$
(25)

∎

#### Convergence to 0.4.

In the main text, we remarked that the fidelities of the measurement-based
CNOT experiments converge to a value slightly below 0.4, as is observed in
Figure 1 (c). As discussed, this is due to the structure of the measurement-
based circuit in Figure 1 (a). While the circuit also experiences infidelity
on the top and bottom qubits due to idle time and some CNOTs, the only
infidelity that actually scales with $n$ is due to incorrect $Z$ and $X$
corrections on the top and bottom qubits respectively.

We can model this noise as
$\Gamma_{ZI}^{\lambda_{ZI}}\Gamma_{IX}^{\lambda_{IX}}$ in the limit of large
$\lambda_{ZI},\lambda_{IX}$, in which case $\omega_{ZI},\omega_{IX}$ approach
$1/2$. We proceed as in (24). Since these Pauli errors cannot cancel, the
calculation is exact.

$\displaystyle\mathcal{F}_{\mathrm{proc}}(I,\Gamma_{ZI}^{\lambda_{ZI}}\Gamma_{IX}^{\lambda_{IX}})=c_{I,I}=(1-\omega_{ZI})(1-\omega_{IX})=1/4\;.$
(26)

This converts to
$\mathcal{F}_{\mathrm{gate}}(I,\Gamma_{ZI}^{\lambda_{ZI}}\Gamma_{IX}^{\lambda_{IX}})=(4\mathcal{F}_{\mathrm{proc}}(I,\Gamma_{ZI}^{\lambda_{ZI}}\Gamma_{IX}^{\lambda_{IX}})+1)/(4+1)=0.4$.