# Better-than-classical Grover search via quantum error detection and
suppression

Bibek Pokharel<EMAIL_ADDRESS>Department of Physics & Astronomy  Center for
Quantum Information Science & Technology  Daniel A. Lidar<EMAIL_ADDRESS>Department of Physics & Astronomy  Center for Quantum Information Science &
Technology  Department of Electrical & Computer Engineering  Department of
Chemistry
University of Southern California, Los Angeles, CA 90089, USA

###### Abstract

Grover’s search algorithm is one of the first quantum algorithms to exhibit a
provable quantum advantage. It forms the backbone of numerous quantum
applications and is widely used in benchmarking efforts. Here, we report
better-than-classical success probabilities for a complete Grover search
algorithm on the largest scale demonstrated to date, of up to five qubits,
using two different IBM superconducting transmon qubit platforms. This is
enabled, on the four and five-qubit scale, by error suppression via robust
dynamical decoupling pulse sequences, without which we do not observe better-
than-classical results. Further improvements arise after the use of
measurement error mitigation, but the latter is insufficient by itself for
achieving better-than-classical performance. For two qubits, we demonstrate a
success probability of $99.5\%$ via the use of the $[[4,2,2]]$ quantum error-
detection (QED) code. This constitutes a demonstration of quantum algorithmic
breakeven via QED. Along the way, we introduce _algorithmic error tomography,_
a method of independent interest that provides a holistic view of the errors
accumulated throughout an entire quantum algorithm, filtered via the errors
detected by the QED code used to encode the circuit. We demonstrate that
algorithmic error tomography provides a stringent test of an error model based
on a combination of amplitude damping, dephasing, and depolarization.

##  I Introduction

The best possible classical strategy for finding a particular “marked” element
in an unsorted list of length $N$ requires querying half of the elements in
the list on average; a quantum computer (QC) can do this in quadratically
fewer queries using Grover’s search algorithm [1]. This algorithm is optimal
and provably better than all classical strategies [2]. As one of the first
algorithms with a provable quantum speedup, Grover search is often used as a
subroutine for other quantum algorithms [3, 4]. Over the last two decades,
Grover search has been implemented on various quantum computing platforms [5,
6, 7, 8], albeit for relatively small $N$.

Encoding a list of length $N$ requires $n=\lceil\log_{2}(N)\rceil$ qubits. The
list can be queried classically or using quantum queries; in both cases, one
finds the marked element with some probability, which we refer to as the
classical or quantum success probability. The largest implementation of
Grover’s algorithm to date is for $n=8$ qubits, but without demonstrating a
better-than-classical quantum success probability [5]. Such better-than-
classical performance has been achieved for $n=3$ [6, 7] and $n=4$ [8] qubits.
Here, employing two seven-qubit IBM Quantum Experience (IBMQE) transmon qubit
platforms ibm_nairobi (Nairobi) and ibmq_jakarta (Jakarta), we demonstrate
higher success probabilities than all previous implementations, for $n\leq 5$.

Key to our demonstrations is the use of error suppression and mitigation
strategies. In particular, we use the $[[4,2,2]]$ quantum error-detecting code
[9, 10], which encodes $k=2$ logical qubits into $n=4$ physical qubits and
detects arbitrary single-qubit errors, to demonstrate a significant success
probability enhancement relative to using two copies of $n=2$ physical qubits.
These success probabilities are further improved by combining error detection
with measurement error mitigation [11, 12].

We use the quantum error detection results to perform what we call
_algorithmic error tomography_ : for each algorithm execution we compute the
probability of an output $X$, $Y$, or $Z$ error (corresponding to the three
Pauli matrices) on one of the four physical qubits, or a logical error. This
allows us to compute a detailed map of the errors that arise after executing
the entire algorithm. In this sense, algorithmic error tomography provides a
holistic and complementary perspective to techniques such as gate set
tomography [13, 14], which instead focus on individual gates.

We demonstrate better-than-classical performance for three or more physical
qubits by employing error suppression via dynamical decoupling (DD) [15, 16,
17, 18]. Toward this end, we consider three robust DD families: universally
robust (UR) [19], concatenated DD (CDD) [20], and robust genetic algorithm
(RGA) [21] sequences. We find that robust sequences with few pulses are vital
in achieving better-than-classical algorithmic performance.

We compare the experimentally obtained results for Grover’s algorithm with an
error model based on the concatenation of amplitude damping, phase damping,
and depolarization maps. Each map is parameterized by the calibration metrics
provided by the IBM Quantum Experience (IBMQE) backend [22]. We test this
model using the observed success probabilities and the algorithmic error
tomography results; the latter provides a much more stringent test. We find
good agreement with the model, but only after using DD. We interpret this in
terms of the suppression of crosstalk by DD [23, 24], which is unaccounted for
by the error model.

In summary, we demonstrate a better-than-classical Grover search for up to 5
qubits, enabled by quantum error detection and dynamical decoupling. That is,
we demonstrate algorithmic performance that is enhanced beyond the break-even
point – where protected operations outperform their unprotected counterparts –
and the capabilities of the best possible classical algorithm executing the
same task. Along the way, we introduce algorithmic error tomography – a
characterization of errors afflicting an entire quantum algorithm based on the
syndromes of a quantum error detecting code.

The structure of this paper is as follows. In Section II, we summarize
Grover’s algorithm’s salient aspects and discuss its implementation. In
Section III, we describe the open system model we use to compute the
theoretically expected algorithmic performance. Details about our dynamical
decoupling implementation are in Section IV. Section V focuses on the
performance of Grover’s algorithm on $n=2$ qubits with and without error
detection. Algorithmic error tomography is introduced in Section V as well.
The results for $2<n\leq 5$, where DD plays a crucial role in achieving
better-than-classical performance, are given in Section VI. We conclude with
observations and the implications of our results in Section VII.

##  II Grover’s Algorithm: background and implementation

Figure 1: Circuit description for Grover’s algorithm. The relative amplitudes
of all the states at each stage of the algorithm are shown. Starting with an
equal superposition state, the oracle assigns a relative phase difference of
$\pi$ to the marked state. The amplitude amplification step then performs an
inversion about the mean, allowing $|m\rangle$ to have a larger probability
amplitude than all other states. This round of querying and amplifying is
repeated $q$ times. The optimal number of rounds for the $n$-qubit Grover
problem is $q_{\text{opt}}=\lfloor\frac{\pi}{4}2^{n/2}\rfloor$. The only
multi-qubit operation required to implement both the oracle and the amplitude
amplification step is C${}_{n-1}Z$ (vertical line in the Oracle and Amplitude
Amplification boxes).

###  II.1 Problem Description

Informally, the Grover problem is to search an unsorted list with $N=2^{n}$
elements for a marked element. Formally, the goal is to find the marked
$n$-bit bitstring $m$ using the smallest number of queries of an oracle that
implements a function $f_{m}\mathrel{\mathop{\mathchar
58\relax}}\\{0,1\\}^{n}\mapsto\\{0,1\\}$ defined as $f_{m}(x)=\delta_{x,m}$.
Classically, after $q$ queries, the probability of correctly identifying the
marked element, which hereafter we refer to as the _success probability_ , is
$p_{s}^{\text{C}}(q,N)=(q+1)/N$ (see Appendix A). Consequently, the classical
algorithm requires $O(N)$ queries.

Grover’s algorithm provides a quadratic quantum speedup, requiring only
$O(\sqrt{N})$ queries [1]. This scaling remains valid with more than one
marked element [25], or even for an arbitrary initial amplitude distribution
over the list elements [26]. In the original setting of a single marked
element, the state after $q$ queries to the oracle is

$\left|\psi_{q}\right\rangle=\sin[(2q+1)\theta]\ket{m}+\cos[(2q+1)\theta]\ket{m^{\perp}},$
(1)

where $\ket{m^{\perp}}=\frac{1}{\sqrt{N-1}}\sum_{x\neq m}|x\rangle$ and
$\theta=\arcsin\left(\frac{1}{\sqrt{N}}\right)$. Thus, the quantum success
probability is $p_{s}^{\text{Q}}(q,N)=\sin^{2}\left[(2q+1)\theta\right]$, and
the theoretically optimal number of queries is
$q_{\text{opt}}=\lfloor\frac{\pi}{4}\sqrt{N}\rfloor$. Note that
$p_{s}^{\text{C}}(q,N)<p_{s}^{\text{Q}}(q,N)$ for all $q<q_{\text{opt}}$.
However, the theoretically optimal $q$ is often not experimentally optimal. As
circuit depth increases with the number of queries and the problem size, there
is a trade-off between the added decoherence and the increase in the success
probability. Most experimental implementations of Grover’s algorithm have
focused on a single query [6, 8, 5, 7], but this strategy does not scale well,
as both $p_{s}^{\text{C}}(1,N)$ and $p_{s}^{\text{Q}}(1,N)$ decrease
exponentially with $n$. We adopt an empirical approach to identify the optimal
number of queries such that $p_{s}$ is maximized. We set $q=2$ for all problem
sizes other than $n=2$ where $q_{\text{opt}}=1$. We justify our choice of the
number of queries in Appendix B.

###  II.2 Implementation

A schematic illustrating the implementation of the $n$-qubit Grover algorithm
is shown in Fig. 1. The only multi-qubit operation is the $n$-qubit
controlled-phase gate C${}_{n-1}Z$, which needs to be implemented twice for
each oracle query: once for the oracle and again for the amplitude
amplification step. Different marked elements are represented by sandwiching
the C${}_{n-1}Z$ gate with $X_{i}$ or $I_{i}$ depending on whether the
corresponding bit $b_{i}$ in the marked bitstring $m$ is 0 or 1. I.e., letting
$m=b_{1}b_{2}\dots b_{n}$, then C${}_{n-1}Z$ in the oracle layer is preceded
and followed by $X^{1-b_{1}}\otimes X^{1-b_{2}}\cdots\otimes X^{1-b_{n}}$.
Likewise, amplitude amplification is implemented as $H^{\otimes n}X^{\otimes
n}(\text{C}_{n-1}Z)X^{\otimes n}H^{\otimes n}$.

For all problem sizes and oracles, we repeated each circuit for the maximum
number of shots allowed on the QPU: $20000$ and $32000$ for Nairobi and
Jakarta, respectively. The reported success probabilities were extracted by
bootstrapping over these trials and all $N$ possible marked states. All error
bars reflect 95% confidence intervals obtained after bootstrapping unless
specified otherwise.

##  III Open system model

The QPUs used here are calibrated daily, and the following calibration metrics
are recorded: the gate error $e_{g}$ and gate duration $\tau_{g}$, the qubit
damping timescale $T_{1}$ and dephasing timescale $T_{2}$, and the response
matrix $M$ for readout errors (see Appendices C and D). In this section, we
describe how we estimate the theoretical performance of Grover’s algorithm
using these metrics. The model described here is mathematically equivalent to
the one used in Qiskit’s Aer API (see the supplementary information of Ref.
[27]).

In a closed system described by a state $\rho$, a unitary gate $U$ acts as
$\mathcal{U}(\rho)=U\rho U^{\dagger}$. In reality, the system is open, so we
model gate $U$ as a CPTP map
$\mathcal{E}=\mathcal{D}\circ\Phi\circ\mathcal{A}\circ\mathcal{U}$, where
$\mathcal{D},\mathcal{A},\Phi$ are depolarizing, amplitude damping and phase
damping maps respectively [28]. The amplitude damping and phase damping maps
account for thermal relaxation, which we represent as
$\mathcal{R}=\Phi\circ\mathcal{A}$. The single-qubit Kraus operators for
$\mathcal{A}=\\{A_{0},A_{1}\\}$ and $\Phi=\\{F_{0},F_{1}\\}$ are

$\displaystyle A_{0}$ $\displaystyle=\left(\begin{array}[]{cc}1&0\\\
0&\sqrt{1-p_{A}}\end{array}\right),\quad A_{1}=\sqrt{p_{A}}|0\rangle\langle
1|$ (2c) $\displaystyle F_{0}$ $\displaystyle=\sqrt{p_{\Phi}}I,\quad
F_{1}=\sqrt{1-p_{\Phi}}Z.$ (2d)

The $n$-qubit depolarizing map is

$\displaystyle\mathcal{D}\mathrel{\mathop{\mathchar
58\relax}}\rho\mapsto(1-p_{D})\rho+p_{D}\frac{\mathbb{I}}{2^{n}}=\sum_{j}K_{j}\rho
K_{j}^{\dagger},$ (3)

where $\mathcal{D}$ has $4^{n}$ Kraus operators:

$\displaystyle K_{0}$ $\displaystyle=\sqrt{1-\frac{4^{n}-1}{4^{n}}p_{D}}\
\mathbb{I}^{\otimes n},$ (4a) $\displaystyle K_{j}$
$\displaystyle=\sqrt{\frac{p_{D}}{4^{n}}}{P}_{j},\quad{P}_{j}\in\\{\mathbb{I},X,Y,Z\\}^{\otimes
n}\smallsetminus\mathbb{I}^{\otimes n}.$ (4b)

We parameterize these maps by their respective error probabilities $p_{A}$,
$p_{\Phi}$ and $p_{D}$, which in turn depend on the calibration metrics
$e_{g}$, $\tau_{g}$, $T_{1}$, and $T_{2}$. In particular,

$\displaystyle p_{A}$ $\displaystyle=1-e^{-\tau_{g}/T_{1}}$ (5a)
$\displaystyle p_{\Phi}$ $\displaystyle=\frac{1}{2}(1+e^{-\tau_{g}/T_{\Phi}})$
(5b) $\displaystyle p_{D}$
$\displaystyle=\frac{d(F(\mathcal{R})-1+e_{g})}{dF(\mathcal{R})-1},$ (5c)

where

$\frac{1}{T_{\Phi}}=\frac{1}{2T_{1}}-\frac{1}{T_{2}},$ (6)

and

$\displaystyle F(\mathcal{E})$ $\displaystyle=\int
d\psi\bra{\psi}U^{\dagger}\mathcal{E}(\ket{\psi}\\!\bra{\psi})U\ket{\psi}$
(7a) $\displaystyle=\frac{dF_{\mathrm{pro}}(\mathcal{E})+1}{d+1}$ (7b)

is the average gate fidelity for a CPTP map $\mathcal{E}$. Here
$F_{\text{pro}}(\mathcal{E})$ is the process fidelity of the map $\mathcal{E}$
with the target map $\mathcal{U}$, and $d$ is the dimension of the map [29].

For each gate, we know the total gate error $e_{g}$, and so we compute $p_{D}$
by setting $1-e_{g}=F(\mathcal{D}\circ\mathcal{R})$, which gives us Eq. 5c
(see Appendix E for more details). In other words, we assign any gate error
not accounted for by relaxation to depolarization. Since $p_{D}\geq 0$, we
must have $F(\mathcal{R})\geq F(\mathcal{D}\circ\mathcal{R})$, i.e., the error
due to relaxation alone cannot exceed the error due to relaxation followed by
depolarization. If this condition is not met, then we assume that the error is
entirely due to depolarization, so that $F(\mathcal{R})=1$ and hence we set
$p_{D}=e_{g}d/(d-1)$ and $\mathcal{E}=\mathcal{D}\circ\mathcal{U}$. For idle
intervals in the circuit, no gate error $e_{g}$ is reported by IBMQE [22], and
therefore we model idle intervals with duration $\tau$ as identity operations
where only the relaxation $\mathcal{R}$ matters. This is equivalent to setting
the gate error for idle intervals to $e_{\text{idle}}=1-F(\mathcal{R})$.

In summary, we model single-qubit gates $U_{1Q}$ with gate duration $\tau_{g}$
as

$\mathcal{D}(p_{D})\circ\mathcal{R}(T_{1},T_{2},\tau_{g})\circ\mathcal{U}_{1Q},$
(8)

and two-qubit gates $U_{2Q}$ with duration $\tau_{g}$ acting on qubits $j,k$
are modeled as

$\mathcal{D}(p_{D})\circ(\mathcal{R}(T_{1}^{j},T_{2}^{j},\tau_{g})\otimes\mathcal{I}_{k})\circ(\mathcal{I}_{j}\otimes\mathcal{R}(T_{1}^{k},T_{2}^{k},\tau_{g}))\circ\mathcal{U}_{2Q}$
(9)

where for $n=2$ $\mathcal{D}(p_{D})$ has $16$ Kraus operators [see Eq. 4].
Idle intervals with duration $\tau$ are described by

$\mathcal{R}(T_{1},T_{2},\tau).$ (10)

The quantum circuit for each experiment is first compiled into the QPU’s
native gate set and then scheduled using IBMQE’s API [22]. We use this circuit
to determine the order of operations and then replace each unitary map
$\mathcal{U}$ with the corresponding CPTP channel $\mathcal{E}$. In the end,
we acquire a probability distribution corresponding to the theoretical
estimate of the circuit’s output as measured in the computational basis.

##  IV Dynamical Decoupling

Figure 2: Grover and DD. The timeline for one oracle query for 4-qubit Grover
with the marked state $\ket{1111}$ is shown. Qubits q4 and q6 are spectators
in this example. Recall that each oracle query for 4-qubit Grover requires two
C${}_{3}Z$ gates. C${}_{3}Z$ requires 14 CNOTs, and the entire circuit uses 28
CNOTs; see Appendix F for circuit compilation details. The pre-DD circuit
elements are grayed out, and the colored lines represent the DD pulses. The DD
sequence exemplified here uses four pulses for illustration purposes; in
reality, we used longer sequences. The scheme demonstrated highlights four
primary features of our implementation: (1) all idle intervals, including the
ones on inactive qubits, are filled, (2) only one repetition of each sequence
is performed, and the pulse interval is adjusted accordingly, (3) each pulse
in the sequence can be unique, (4) a single qubit can experience multiple DD
repetitions if there are multiple idle intervals.

DD is an open-loop quantum control technique wherein a sequence of pulses is
strategically inserted between gates to suppress unwanted system-bath
interactions [15, 16, 17, 18]. While DD is fully compatible with quantum error
correction [30], its most economical form requires no encoding, measurements,
or post-processing. It is, therefore, perhaps the least resource-intensive
error suppression strategy. Error suppression via DD has a long history of
experimental demonstrations on various quantum devices (see Ref. [31] for a
review). Here, we employ a “decouple then compute” strategy [32, 33], whereby
control pulses constituting short but complete DD sequences are interleaved
with the quantum circuit, exploiting intervals when individual qubits in the
corresponding quantum circuits are idle. A scheme demonstrating our strategy
is shown in Fig. 2. This interleaving strategy has been used to improve
quantum volume [34], variational quantum algorithms [35], and most recently to
demonstrate an algorithmic quantum speedup [36].

In addition to the popular basic DD sequences – CPMG [37] and XY4 [16] – we
consider three robust sequence families: universally robust (UR) DD [19],
concatenated DD (CDD) [20], and robust genetic algorithm (RGA) DD [21] (see
Appendix B for more details). Other than CPMG, these are all high-order,
multi-axis sequences that are universal for single qubits, i.e., they suppress
arbitrary single-qubit errors beyond first order in the Magnus or Dyson
expansion [38]. Robustness refers to the mitigation of axis-angle and
over/under-rotation errors. In addition, these sequences can cancel crosstalk
errors [23, 24]. Our sequence choice is informed by the results of Ref. [39],
which reported on a significantly more comprehensive survey of sequences using
superconducting qubits and concluded that robust sequences are preferred
default choices. Here we do not utilize the OpenPulse functionality of the
IBMQE platforms, nor do we implement Uhrig-type [40] non-uniform pulse
interval DD sequences such as quadratic DD (QDD) [41], which were also found
to perform well in the survey [39]. Both have the potential to enhance our
results and are attractive options for future studies.

##  V Two-qubit encoded Grover algorithm protected by quantum error detection

$\Qcircuit@C=1em@R=0.8em@!R{&\textsc{Initialization}\ \ \ \ \ \textsc{Oracle}\
\ \ \ \ \ \ \textsc{Amplitude Amplification}\textsc{Measurement}\\\ \ \ \ \
U_{\text{encoding}}\ \ \ \ \ \ \ \text{ Oracle}_{01}\ \ \ \ \
\text{Oracle}_{00}\ \ \ \ \ \ \ U_{\text{decoding}}\\\
\qw\gate{H}\ctrl{1}\qw\qw\gate{H}\qw\qw\gate{X}\gate{P}\gate{I}\gate{X}\qw\qw\gate{H}\gate{I}\gate{P}\gate{I}\gate{I}\gate{H}\qw\qw\qw\qw\ctrl{1}\gate{H}\meter\\\
\qw\qw\targ\ctrl{1}\qw\gate{H}\qw\qw\gate{I}\gate{P}\gate{Z}\gate{I}\qw\qw\gate{H}\gate{X}\gate{P}\gate{Z}\gate{X}\gate{H}\qw\qw\qw\ctrl{1}\targ\qw\meter\\\
\qw\qw\qw\targ\ctrl{1}\gate{H}\qw\qw\gate{X}\gate{P}\gate{Z}\gate{X}\qw\qw\gate{H}\gate{X}\gate{P}\gate{Z}\gate{X}\gate{H}\qw\qw\ctrl{1}\targ\qw\qw\meter\\\
\qw\qw\qw\qw\targ\gate{H}\qw\qw\gate{I}\gate{P}\gate{I}\gate{I}\qw\qw\gate{H}\gate{I}\gate{P}\gate{I}\gate{I}\gate{H}\qw\qw\targ\qw\qw\qw\meter\\\
\\\
\gategroup{1}{2}{7}{8}{0.9em}{-}\gategroup{3}{3}{6}{6}{0.9em}{--}\gategroup{1}{9}{7}{14}{0.9em}{-}\gategroup{3}{10}{6}{13}{0.9em}{--}\gategroup{1}{15}{7}{22}{0.9em}{-}\gategroup{3}{17}{6}{20}{0.9em}{--}\gategroup{3}{24}{6}{27}{0.9em}{--}\gategroup{1}{23}{7}{29}{0.9em}{-}}$
Figure 3: Encoded two-qubit Grover. The two-qubit single-query ($q=1$) Grover
circuit encoded using the $[[4,2,2]]$ code for the marked state $\ket{01}$ is
shown. The encoding step (left dashed box) prepares the encoded initial state
$\ket{\overline{00}}=\frac{1}{\sqrt{2}}\left(|0000\rangle+|1111\rangle\right)$
(the 4-qubit GHZ state) from the physical initial state $\ket{0000}$. The
encoded Grover circuit is implemented by converting each physical gate of the
$n=2$ case of Fig. 1 into its logical counterpart, which is then converted
into a physical $4$-qubit implementation (middle left and right dashed boxes);
see Appendix F for details. $P=\text{diag}(1,i)$ is the phase gate. We post-
select the measured results by decoding (right dashed box) and discarding any
measurement outcome for which the code detects errors, i.e., does not result
in one of the four decoded states
$\\{\ket{0000},\ket{0010},\ket{0111},\ket{0101}\\}$.

The $[[4,2,2]]$ code [9] is the smallest possible qubit-based error detecting
code [10] and has been invoked for proof-of-principle demonstrations of
quantum error detection [42]. Notably, it has been used to improve Clifford
gate set fidelities [43] and the performance of variational algorithms [44].
However, measurement error mitigation (MEM) played a dominant role in Ref.
[44], and it is unclear if error detection alone would have improved
performance in that work. Here, we compare the performance of the two-qubit
Grover algorithm with and without the $[[4,2,2]]$ code and MEM. The unencoded
version needs two qubits, while the encoded version requires four. To equalize
resources, we simultaneously use two copies of the unencoded circuit and
report the best fidelity of the two copies. We incorporate MEM using iterative
Bayesian unfolding via the pyIBU package [45] (see Appendix D for details
about MEM). Ultimately, we demonstrate a conclusive improvement in algorithmic
performance due to quantum error detection.

###  V.1 Encoding into the $[[4,2,2]]$ code

The stabilizers of the $[[4,2,2]]$ code are $XXXX$ and $ZZZZ$. The logical
operators of this code can be chosen as $\overline{X}_{1}=XIXI$,
$\overline{X}_{2}=XXII$, $\overline{Z}_{1}=ZZII$, and $\overline{Z}_{2}=ZIZI$.
Two-qubit Grover also requires the encoded Hadamard $\overline{H}$ and
controlled-phase $\overline{\text{C}Z}$. The deconstruction of the logical
circuit into physical components is detailed in Appendix F, and the resultant
encoded two-qubit Grover circuit is shown in Fig. 3.

The encoding and decoding circuits, $U_{\text{enc}}$ and
$U_{\text{enc}}^{\dagger}$, are also depicted in Fig. 3. The logical basis
states are:

$\displaystyle\ket{\overline{00}}=U_{\text{enc}}\ket{0000}=\frac{\ket{0000}+\ket{1111}}{\sqrt{2}}$
(11a)
$\displaystyle\ket{\overline{01}}=U_{\text{enc}}\ket{0010}=\frac{\ket{0011}+\ket{1100}}{\sqrt{2}}$
(11b)
$\displaystyle\ket{\overline{10}}=U_{\text{enc}}\ket{0111}=\frac{\ket{0101}+\ket{1010}}{\sqrt{2}}$
(11c)
$\displaystyle\ket{\overline{11}}=U_{\text{enc}}\ket{0101}=\frac{\ket{1001}+\ket{0110}}{\sqrt{2}}$
(11d)

These are also the four possible marked states in the two-qubit Grover
problem. Consequently, after applying $U_{\text{enc}}^{\dagger}$ to decode the
results, only states from the set
$\mathcal{I}=\\{\ket{0000},\ket{0010},\ket{0111},\ket{0101}\\}$ could have
arisen from valid logical states. Therefore, we postselect by removing any of
the $12$ measurement outcomes that do not correspond to valid logical states,
i.e., states in $\mathcal{I}^{\perp}=\\{0,1\\}^{4}\smallsetminus\mathcal{I}$.

###  V.2 Algorithmic error tomography

Even though we discard any states not in the set $\mathcal{I}$ during
postselection, there is important information in such outcomes. They allow us
to diagnose the frequency with which different Pauli errors appear at the end
of the circuit for a given encoded marked state, i.e., to perform _algorithmic
error tomography_ (AET), which we now describe.

Let us first consider the different ways errors can occur before the
measurement outcome is obtained. In principle, errors can occur anywhere
during the circuit, including between the decoding and measurement steps or
even during the measurement. There can be multiple errors at multiple
locations of arbitrary weight. Given an $[[n,k,d]]$ code $\mathcal{C}$, in
AET, we treat all these errors as either the _effective_ errors that this code
can detect or as logical errors, and assign a location to these errors as if
they happened just before decoding. Namely, if
$\ket{\overline{b}}\in\mathcal{C}$ is a code basis state, where
$b\in\\{0,1\\}^{k}$, $E$ is an error,
$U_{\text{dec}}=U_{\text{enc}}^{\dagger}$ is the decoding unitary for
$\mathcal{C}$, and $\mathcal{M}$ denotes a projective measurement in the
computational basis, then in AET we interpret each measured computational
basis state $\ket{b^{\prime}}$ as having arisen from
$\mathcal{M}U_{\text{dec}}E\ket{\overline{b}}$, where
$b^{\prime}\in\\{0,1\\}^{n}$. If $E$ is an error the code can detect then
$\ket{b^{\prime}}=\mathcal{M}U_{\text{dec}}E\ket{\overline{b}}\in\mathcal{C}^{\perp}_{E}\subset\mathcal{C}^{\perp}$,
while if $E$ is a logical error then
$\ket{b^{\prime}}=\mathcal{M}U_{\text{dec}}E\ket{\overline{b}}\in\mathcal{C}$.
Here $\mathcal{C}\oplus\mathcal{C}^{\perp}=\mathcal{H}$, the full system
Hilbert space, and $\mathcal{C}^{\perp}=\bigoplus_{E}\mathcal{C}^{\perp}_{E}$.
We can now empirically compute the probability $p_{b^{\prime}}$ of each
measurement outcome $\ket{b^{\prime}}$, and from here the probability $p_{E}$
of each error $E$ by constructing the _error outcome table_
$\\{U_{\text{dec}}E\ket{\overline{b}}\\}$ for all $b\in\\{0,1\\}^{k}$ and all
the errors $E$ the code can detect. With this table in hand, we can check for
each measurement outcome $\ket{b^{\prime}}$ whether it is in the table (if so,
it corresponds to an effective error the code can detect) or not (in which
case it corresponds to a logical error, or no error). Suppose
$\ket{b^{\prime}}$ is in the error outcome table. In that case, we can further
identify the error type it arose from (i.e., associate it to a particular
_error subspace_ $\mathcal{C}^{\perp}_{E}$). By finding the empirical relative
frequency of this error type, we can compute this error’s probability $p_{E}$.
For logical errors, the procedure is similar; we need to find the empirical
relative frequency of $\ket{b^{\prime}}$ arising from a given code basis state
$\ket{b}$.

$E$ | $U_{\text{dec}}E\ket{\overline{00}}$ | $U_{\text{dec}}E\ket{\overline{01}}$ | $U_{\text{dec}}E\ket{\overline{10}}$ | $U_{\text{dec}}E\ket{\overline{11}}$
---|---|---|---|---
$X_{1}$ | $\ket{0100}$ | $\ket{0110}$ | $\ket{0011}$ | $\ket{0001}$
$X_{2}$ | $\ket{0110}$ | $\ket{0100}$ | $\ket{0001}$ | $\ket{0011}$
$X_{3}$ | $\ket{0011}$ | $\ket{0001}$ | $\ket{0100}$ | $\ket{0110}$
$X_{4}$ | $\ket{0001}$ | $\ket{0011}$ | $\ket{0110}$ | $\ket{0100}$
$iY_{1}$ | $\ket{1100}$ | $\ket{1110}$ | $\ket{1011}$ | $\ket{1001}$
$iY_{2}$ | $-\ket{1110}$ | $-\ket{1100}$ | $\ket{1001}$ | $\ket{1011}$
$iY_{3}$ | $-\ket{1011}$ | $\ket{1001}$ | $-\ket{1100}$ | $\ket{1110}$
$iY_{4}$ | $-\ket{1001}$ | $\ket{1011}$ | $\ket{1110}$ | $-\ket{1100}$
$Z_{1}$ | $\ket{1000}$ | $\ket{1010}$ | $\ket{1111}$ | $\ket{1101}$
$Z_{2}$ | $\ket{1000}$ | $\ket{1010}$ | $-\ket{1111}$ | $-\ket{1101}$
$Z_{3}$ | $\ket{1000}$ | $-\ket{1010}$ | $\ket{1111}$ | $-\ket{1101}$
$Z_{4}$ | $\ket{1000}$ | $-\ket{1010}$ | $-\ket{1111}$ | $\ket{1101}$
Table 1: Error outcome table for the $[[4,2,2]]$ code. The table describes the
effect of single-qubit Pauli errors $E$ on each of the encoded computational
basis elements $\ket{\overline{b_{1}b_{2}}}$. The $X$, $Y$, and $Z$-type
errors map each $\ket{\overline{b_{1}b_{2}}}$ to a distinct subspace after
decoding:
$\mathcal{C}^{\perp}_{X}=\text{span}(\\{\ket{0100},\ket{0110},\ket{0011},\ket{0001}\\})$,
$\mathcal{C}^{\perp}_{Y}=\text{span}(\\{\ket{1100},\ket{1110},\ket{1011},\ket{1001}\\})$,
and
$\mathcal{C}^{\perp}_{Z}=\text{span}(\\{\ket{1000},\ket{1010},\ket{1111},\ket{1101}\\})$,
respectively, such that
$\mathcal{C}^{\perp}=\mathcal{C}^{\perp}_{X}\oplus\mathcal{C}^{\perp}_{Y}\oplus\mathcal{C}^{\perp}_{Z}$.
Thus, each subspace uniquely determines the error type, which we use to
perform algorithmic error tomography.

Let us now illustrate this formal description of AET using the $[[4,2,2]]$
code. In this case
$\mathcal{C}=\text{span}(\\{\ket{0000},\ket{0010},\ket{0111},\ket{0101}\\})$.
It is clear from Eq. 11 that the decoding
$U_{\text{dec}}=U_{\text{enc}}^{\dagger}$ is a one-to-one map between encoded
states $\ket{\overline{b_{1}b_{2}}}$ and unencoded states:
$U_{\text{dec}}\ket{\overline{b_{1}b_{2}}}\in\mathcal{C}$. Table 1 is the
error outcome table for the $[[4,2,2]]$ code and shows
$U_{\text{dec}}E\ket{\overline{b_{1}b_{2}}}$ for all single-qubit Pauli errors
and logical computational basis elements. As the probability of each outcome
(i.e., each row in Table 1) depends on the error $E$, the bitstring observed
after applying the decoding circuit tells us the frequency with which
different single-qubit Pauli errors occurred. More specifically, since the
$[[4,2,2]]$ code is a distance-$2$ code, we can only infer which weight-$1$
error type occurred ($X$, $Y$, or $Z$), but not which specific qubit was
affected. In other words, we can associate each observed state
$\ket{b^{\prime}}$ ($b^{\prime}\in\\{0,1\\}^{4}\smallsetminus\mathcal{I}$)
with an error subspace $\mathcal{C}^{\perp}_{X}$, $\mathcal{C}^{\perp}_{Y}$,
or $\mathcal{C}^{\perp}_{Z}$. Each observed state $\ket{b^{\prime}}$ will have
an empirical probability $p_{b^{\prime}}=N_{b^{\prime}}/N_{\text{tot}}$, where
$N_{b^{\prime}}$ is the number of times $\ket{b^{\prime}}$ is observed out of
a total of $N_{\text{tot}}$ observations. The probability of single-qubit
$X$-type errors, $p_{X}$, is the sum of $p_{b^{\prime}}$ in the first four
rows, etc.

Figure 4: Algorithmic error tomography on Jakarta. The bitstring observed
after $U_{\text{dec}}$ either corresponds to a marked entry or an error
tabulated in Table 1. Top: experimental results. The numbers in each box are
the empirical percentage probabilities for detected $X$, $Y$, or $Z$-type
errors, with $2\sigma$ standard deviation. Logical error percentage
probabilities are shown in the first column of each table. Each row
corresponds to a different marked state. The probabilities in each row do not
sum to unity since we do not display the probability of obtaining the correct
marked state. Left: without DD protection. Right: with DD protection. Bottom:
the same for the simulated model. Figure 5: Algorithmic error tomography on
Nairobi. Data entries are as in Fig. 4, except that only data without DD is
shown. Good agreement is observed between the results of our error model and
the experiment. In particular, compared to the error tomography table for
Jakarta (Fig. 4), we do not observe an asymmetry in $Z$ errors across marked
states. Figure 6: Two-qubit Grover results. Two-qubit single-query Grover
failure probability results without (Unenc) and with (Enc) postselection using
the $\left[\left[4,2,2\right]\right]$ code on Jakarta and Nairobi are shown.
The transparent boxes represent the theoretically expected failure
probabilities from the model described in Section III, which does not include
DD; their centers correspond to the average over marked states, and their
boundaries correspond to 95% confidence intervals after bootstrapping. The
colored bars represent the experimental results (see the legend), and the
experimental error bars (black for Jakarta with DD and Nairobi, or pink for
Jakarta without DD) correspond to 95% confidence intervals after
bootstrapping. Dark green appears where the pink and light green colors (i.e.,
Jakarta with and without DD) overlap. In the Unenc case, we run two identical
copies of the two-qubit Grover problem to equalize resources with the Enc case
and choose the copy with the highest success probability. Also shown are the
results with MEM using iterative Bayesian unfolding (see Appendix D for
details). Failure probabilities with and without DD protection are shown for
Jakarta but not for Nairobi, where the simulated and observed error tomography
and failure probabilities are in agreement (see Section V.3.2). The presence
of DD does not affect the success probability in the encoded implementation,
and as a result, the pink bars are mostly hidden behind the green bars.
However, the nature of detected errors, even in the encoded case, is affected
by DD (see Fig. 4). All data for different runs on the same QPU were collected
on the same day; data from different QPUs were collected on different days.

Figure 7: Two-qubit Grover results for Jakarta (top) and Nairobi (bottom). The
left and right panels show the output distribution for all possible oracles
for two setups: unencoded and encoded with MEM. As in Fig. 6, Unenc
corresponds to two copies of unencoded two-qubit Grover, of which the best
result is reported. Enc corresponds to the results encoded using the
$[[4,2,2]]$ code. The Enc results are reported after postselection. Let
$p_{s}(m,b,e)$ be the observed success probability for marked state $m$,
detected state $b$, and experiment type
$e\in\\{\text{Enc,Unenc+MEM,Enc+MEM}\\}$. The success probability changes from
orange to green when $p_{s}(m,b,e)>\max_{m,b}p_{s}(m,b,\text{Unenc})$. Error
bars correspond to 95% confidence intervals.

###  V.3 Results

####  V.3.1 Algorithmic error tomography

Figs. 4 and 5 show the results of AET after implementing or simulating the
encoded two-qubit Grover algorithm on Jakarta and Nairobi, respectively. Each
of the four panels corresponds to a different error outcome table, with the
top row representing experiments and the bottom row representing simulations
using the model of Section III. The left and right columns of Fig. 4 exclude
or include DD, respectively. We did not use DD in the Nairobi case (Fig. 5).
Each row corresponds to a different encoded basis state within each error
outcome table, i.e., encoded marked state. Other than the logical errors
counted during postselection, all other columns represent outcomes ignored
during the postselection step. We discuss these results in more detail in the
following subsection, showing how AET allows us to identify and mitigate qubit
crosstalk.

####  V.3.2 DD protection and comparison with the open system model

Recall that we define the success probability $p_{s}$ as the probability of
correctly identifying the marked element. We denote the empirical success
probability obtained for a list of $N$ elements after $q$ oracle queries by
$p_{s}^{\text{e}}(q,N)$. Our results are summarized in Fig. 6, which shows the
failure probability ($1-p_{s}^{\text{e}}(1,4)$) for the unencoded and the
encoded implementations on two different QPUs.

Before comparing the results with and without encoding, we analyze whether the
observed performance matches the model of Section III in both cases. Let us
focus first on Jakarta, where without DD, the empirical failure probabilities
in the unencoded case are slightly higher than predicted; see the leftmost
column of Fig. 6. Fortunately, in the encoded case, Jakarta’s failure
probability overlaps with the prediction bands (Fig. 6, third column from the
left). However, a closer look at the detected errors via AET reveals a
different discrepancy. The simulated results for Jakarta (bottom-left table in
Fig. 4) do not match the empirical error profile (top-left table of Fig. 4),
which has significantly stronger $Z$ errors and also a state-dependent
asymmetry in these errors. In other words, Jakarta does not match the
simulations for unencoded or encoded circuits without DD. In contrast, for
Nairobi, Fig. 5 shows that the AET simulation results agree with the
empirically observed ones. This also holds for the simulated failure
probabilities (Fig. 6).

To investigate Jakarta’s observed discrepancy, we first attempt to
systematically amplify $p_{D},T_{1}$, and $T_{2}$ by multiplying each quantity
by a phenomenologically determined variable $\lambda_{i}$ (see Appendix G).
This leads to a better overlap between predicted and observed success
probabilities but does not reproduce the AET asymmetry seen in Fig. 4. This
shows the limitations of the phenomenological model of Section III and
highlights the level of detail provided by AET.

However, the Jakarta discrepancy is effectively removed after the application
of DD. Our two-qubit Grover implementation uses four qubits, leaving three
inactive qubits in the 7-qubit QPUs used in our experiments. As there are no
idle intervals in the unencoded two-qubit Grover circuit, we applied the XY4
sequence on the inactive qubits – q2,q4, and q6 (see Appendix C). We applied
the XY4 sequence to both the active and inactive qubits for the encoded case.
Due to the relative sparsity of idle intervals in the two-qubit Grover
circuits, we did not attempt to implement robust sequences, which require more
pulses than XY4.

Fig. 6 shows how the failure probability and the rates of various detected
errors on Jakarta are affected by the presence of DD. For the unencoded case
(the first two columns from left of Fig. 6), DD improves the performance
slightly, and the discrepancy between the predicted and observed failure
probabilities is removed. The improvement by DD in the unencoded two-qubit
Grover case is in concurrence with Refs. [23, 24], which showed the efficacy
of the XY4 sequence in suppressing static $ZZ$ crosstalk in superconducting
qubits. In other words, these results confirm that $ZZ$ crosstalk – which is
well-documented for superconducting QCs [46] – likely contributes to the
observed performance being slightly worse than expected from the model.

Adding the XY4 sequence removes most of the empirical-theoretical
discrepancies in both the magnitude and the asymmetry of the errors exhibited
by the AET profiles, as seen by comparing the top and bottom right of Fig. 4.
With DD, the encoded circuits have a weaker state-wise asymmetry in $Z$-errors
than seen in the left column of Fig. 4. Moreover, the DD-protected circuits
more closely reproduce the distribution of detected errors predicted by the
model of Section III than the same circuits without DD. This observation –
that the agreement between our theoretical model and the experimental results
improves under DD – is further validated below.

The close agreement we found for Nairobi between our (crosstalk-free) model
and the experimental results without DD or MEM (Fig. 5 and the first and third
from left columns of Fig. 6) suggests that crosstalk does not play a
significant role in this QPU. Fig. 6 does exhibit a significant discrepancy
between the model and the experimental Nairobi results when MEM is included
(second and last columns of Fig. 6). As we show in Appendix D, this
discrepancy arises from the choice to mitigate readout errors using iterative
Bayesian unfolding (IBU) [12].

Finally, Fig. 7 complements the first and last columns of Fig. 6, as well as
the AET results, and shows the output distributions for Jakarta and Nairobi
for the two-qubit Grover case, with and without encoding and MEM. The main
observation is that for the unencoded case, the maximum success probability is
obtained for the marked state $\ket{00}$, which is also the QPU’s ground
state; this is unsurprising given the dominance of amplitude damping errors.
With encoding plus error mitigation, the overall performance increases and
becomes independent of the marked state.

####  V.3.3 Success probability: beyond break-even improvement

We now focus on the effect of error detection on two-qubit Grover performance
as seen in Fig. 6. Due to the shallow circuit depth, even without any error
detection, $p_{s}^{\text{e}}(1,4)\sim 93.0\%$ \- already much higher than the
classical success probability $p_{s}^{\text{C}}(1,4)=\frac{1}{2}$. Adding
error detection improves the success probability to $\sim 96.0\%$. The effect
of MEM is similar to that of error detection: the success probability
increases to $\sim 97.0\%$. Combining error detection with MEM results in
additional improvement: we obtain success probabilities of $\sim 98.5\%$ on
Nairobi and $\sim 99.5\%$ on Jakarta. Due to error detection and MEM,
Jakarta’s success probabilities increase by an order of magnitude.

This improvement over the unencoded case is non-trivial, considering that the
$[[4,2,2]]$ code can only detect weight-1 errors, and the encoded circuit
requires six two-qubit gates. In contrast, the unencoded version requires only
two. The relatively high success probabilities we observe in the encoded case
suggest that most errors, even those due to the two-qubit gates, manifest as
weight-1 errors. This shows, albeit for a relatively small problem size, that
error detection can more than offset the extra errors introduced due to
increased circuit depth and complexity.

We have demonstrated an _algorithmic beyond break-even improvement_ using
error detection in the sense that the protected algorithm clearly outperforms
its unprotected counterpart. Previous break-even improvements were at the
individual gate level [47, 48]. Here we have demonstrated such an improvement
at the level of the execution of an entire algorithm, albeit of a fixed size.
The holy grail is to demonstrate the implementation of an algorithm for a
family of problem sizes at the logical level with higher fidelity than the
same algorithm executed at the physical level. Achieving this in our setting
would require increasing the problem and code sizes. The family of
$[[2k+2,k,2]]$ subsystem quantum error detecting codes is an attractive option
in this regard since all their logical operators can be chosen to be 2-local
[49], which simplifies the circuit design. An experimental implementation of
such larger codes and problem sizes remains a coveted goal.

Figure 8: Performance of DD sequences. Average success probability for 5-qubit
Grover with two oracle queries on Nairobi. The DD sequences are ranked in
order of decreasing success probability. The two dotted lines represent
success probabilities corresponding to a random and classical strategy,
respectively. RGA8a and RGA8c are tied as the best-performing sequences. Free
denotes the result of an unprotected implementation. Error bars correspond to
99% confidence intervals.  Figure 9: 5-qubit Grover results on Nairobi. Left:
average success probability with and without DD or MEM for 5-qubit Grover
implemented on Nairobi. The boxes correspond to the theoretically expected
success probabilities. The quantum oracle is queried twice; in the ideal case,
the success probability is 0.602. The unprotected (Free) evolution is on par
with a random guess, significantly worse than the optimal classical strategy
(dashed vertical line), and just adding MEM does not change the result. In
contrast, the DD-assisted implementation crosses the classical threshold, and
the results improve even more with MEM, up to a success probability of $0.15$.
Error bars correspond to 99% confidence intervals. Middle and right: the
complete input-output maps for all $2^{5}$ marked states, without and with DD
+ MEM, are shown. States are sorted by increasing Hamming weight; in the Free
case, low Hamming weight states have a higher success probability (more green
on the left). This is likely to be a consequence of amplitude damping
(spontaneous emission), which favors the $\ket{0}$ state of each qubit. In the
unprotected case (Free, middle), there is no discernible correlation between
the input marked state and the output detected state. In the protected case
(DD + MEM right), black-to-purple signifies better-than-classical success
probability, and this threshold is crossed for all $32$ marked states. The DD
sequence used here is RGA8a [21], which was the top-performing sequence in our
DD survey (see Fig. 8). Figure 10: Success probabilities vs problem size.
Nairobi (green) and Jakarta (orange) success probabilities for
$n\in\\{3,4,5\\}$ are shown for DD-protected and unprotected implementations.
The translucent bands indicate the theoretically estimated success
probabilities using the model described in Section III. We performed $q=2$
queries to the quantum oracle in all cases. The ideal success probabilities
are $0.945$, $0.908$, and $0.602$ for $n=3$, $4$, and $5$, respectively. The
white lines correspond to the success probabilities for the classical strategy
and random sampling from the unsorted list ($q=0$). Error bars correspond to
99% confidence intervals.

##  VI 3-qubit to 5-qubit Grover protected by dynamical decoupling

Crossing the classical threshold in Grover’s search for an increasingly larger
number of qubits is a meaningful goal, not only because the quadratic speedup
offered by Grover’s algorithm leads to a more dramatic improvement as the
problem size increases but also because it becomes more challenging to realize
the speedup experimentally as the controlled phase gate C${}_{n-1}Z$ is an
$n$-qubit entangling operation. In the implementation of Ref. [5], 5-qubit
Grover required nearly a thousand two-qubit gates, and for 8-qubit Grover,
nearly 15000 gates were used. Notably, this exponential increase in the number
of two-qubit gates with problem size is because Ref. [5] did not use ancilla
qubits to make the circuits shallower. It is possible to implement
C${}_{n-1}Z$ with circuits where two-qubit gates scale linearly with $n$ (see
Appendix F). Ref. [8] employed shallower circuits for C${}_{n-1}Z$ and solved
5-qubit Grover with slightly better-than-random success probabilities but
without better-than-classical performance. We use an efficient, ancilla-
assisted implementation of generalized Toffoli-type gates [50, 8] to implement
C${}_{n-1}Z$ (see Appendix F). Our implementation, which builds upon the
circuits from Ref. [8], uses $8$, $14$, and $22$ CNOTs for a single $C_{n-1}Z$
gate for $n=3$, $4$, and $5$, respectively. The deepest circuit we implement
is two oracle queries for 5-qubit Grover, totaling $88$ CNOTs. Despite being
far shallower than Ref. [5]’s implementation, this is still a relatively deep
circuit; e.g., the quantum supremacy demonstration of Ref. [51] and the
algorithmic quantum speedup demonstration of Ref. [36] involved circuits of
depth up to $40$ and $44$, respectively. As we detail in this section, owing
to error suppression via DD, we crossed the classical probability threshold
for all problem sizes, including for 5-qubit Grover.

###  VI.1 Implementation with dynamical decoupling

DD sequences are inserted into idle intervals of a quantum circuit using the
“decouple then compute strategy” demonstrated in Fig. 2, which shows the DD
insertion scheme for a single query on a 4-qubit Grover circuit. In contrast
to two-qubit Grover, where we restricted DD implementation to XY4, $n\geq 3$
has ample idle intervals. Therefore we can implement robust sequences (RGA,
CDD, UR) requiring more than four pulses. Each of these families has multiple
members that are parameterized by the number of pulses in the sequence. We
restrict our implementation to DD sequences with fewer than 32 pulses and, for
each circuit, only consider sequences that we can fit in the idle intervals
available in the quantum circuit.

At each problem size $n$, there are $2^{n}$ possible oracles, each
corresponding to one marked state $\ket{b}$, where $b\in\\{0,1\\}^{n}$. We
proceed as follows to avoid implementing this exponentially large set of
oracles. Given $0\leq k\leq n$, there are $\binom{n}{k}$ distinct bitstrings
that are identical to $0^{k}1^{n-k}$ up to qubit permutation. Recall that
marked states differ only by whether $X$ or $I$ gates surround the
C${}_{n-1}Z$ gate. Thus, we only consider the $n+1$ oracles with marked states
$\ket{0^{k}1^{n-k}}$, $k\in\\{0,\dots,n\\}$. We then estimate the average
success probability by computing

$\langle
p(n)\rangle=\frac{1}{2^{n}}\sum\limits_{k=0}^{n}\binom{n}{k}p(|0^{k}1^{n-k}\rangle).$
(12)

We use $\langle p(n)\rangle$ as the metric for selecting the optimal DD
sequences among those we tested and to identify the experimentally optimal
number of queries $q^{e}_{\text{opt}}$. Once the optimal DD sequence and
$q^{e}_{\text{opt}}$ are identified for each $n$, we run the unprotected and
the DD-protected Grover’s algorithm again at $q^{e}_{\text{opt}}$, but this
time for all $2^{n}$ oracles.

###  VI.2 Results

####  VI.2.1 Optimal DD sequence and number of queries

Our first goal is to identify the best DD sequence and $q_{\text{opt}}$. The
determinations made in this step inform our choices for the next step. For
conciseness, in this section, we focus on the results of the largest problem
size we implemented, i.e., $n=5$. Appendix B shows the results for $3\leq
n\leq 5$ on both Nairobi and Jakarta. The performance of various DD sequences
for Nairobi for 5-qubit Grover are compared in Fig. 8 by computing $\langle
p(5)\rangle$. The unprotected evolution (Free) is marginally better than
choosing an element randomly and does not cross the classical threshold. DD
protection is necessary to cross this threshold, but the two-pulse sequences
RGA2x and CPMG still result in worse-than-classical performance. The RGA and
UR sequences perform well, particularly those with fewer than 12 pulses. RGA8a
and RGA8c are tied as the best-performing sequences; we choose RGA8a for the
next step, where we implement all of the $2^{5}$ oracles. The performance
improvement seen due to robust sequences is consistent across problem sizes
and devices, as detailed in the Appendix B.

We also use $\langle p(n)\rangle$ to identify the experimentally optimal
number of oracle queries $q^{e}_{\text{opt}}$. The theoretically optimal
number of repetitions for $n=3,4,5$ is $q_{\text{opt}}=2,3,4$, respectively.
However, Appendix B shows that in reality, the theoretically expected
$q_{\text{opt}}$ often leads to worse performance than $q^{e}_{\text{opt}}$.
For the DD-protected implementation, $q=2$ maximizes the success probability
$p_{s}$ in all cases other than 5-qubit Grover on Jakarta, where the
performance at $q=2$ is comparable to $q=1$. As DD protection is necessary to
cross the classical threshold, for simplicity of analysis and to maximize
$p_{s}$ we set $q=2$ from here on.

####  VI.2.2 Better-than-classical performance

Fig. 9 shows our results for the 5-qubit Grover problem on Nairobi with and
without DD. Even in our relatively shallow-depth implementation, before error
suppression via DD (whether Free or Free + MEM), the final results are
indistinguishable from randomly guessing the marked state. The results change
significantly when we implement DD. With DD, the classical threshold is
crossed by all marked states. Adding MEM improves the results slightly, but
only when accompanied by DD.

This dramatic improvement due to DD holds for other problem sizes as well.
Fig. 10 shows the success probabilities after two oracle queries on both
devices for $3\leq n\leq 5$ (see Appendix H for the role of postselection in
these results). At the two smaller problem sizes ($n=3,4$), the unprotected
implementations are better than random sampling, but the success probability
is relatively low. For $n=4$, the unprotected quantum Grover circuit does not
exceed the classical single-query threshold. It is effectively on par with
random sampling for $n=5$. In contrast, for all problem sizes, the DD-
protected quantum strategy at $q=2$ outperforms the classical strategy for
$q\leq 3$. DD-protected Grover performance at $n=3,4,5$ is equivalent to
classical $q=4,5,3$ for Jakarta and $q=4,5,4$ for Nairobi, respectively. Thus,
DD is essential in attaining a better-than-classical performance.

The translucent bands in Fig. 10 and the boxes in Fig. 9 (left) show the
theoretically expected results computed from the open system model with the
IBMQE-supplied parameters. The success probability in this unprotected Grover
case (dashed lines in Fig. 10) is considerably lower than the theoretical
expectation. This discrepancy is likely due to crosstalk and non-Markovianity,
which are well-documented for IBMQE’s superconducting qubit-based QPUs. Once
we use DD, the observed fidelities improve and are close to the theoretical
predictions. This improvement is expected given DD’s ability to reduce the
effect of crosstalk [23, 24] and non-Markovian effects.

With DD, the algorithmic performance approaches the expectations based on our
error model. However, we emphasize that this model does not predict the QPU’s
performance under DD; it simply tells us what the performance would be if the
reported calibration metrics corresponded to observed dynamics. The overlap
between the theoretically predicted (translucent) and the DD-protected (solid)
performance implies that DD successfully mitigates the errors that our simple
model does not account for. However, the model does not provide an upper bound
on the possible performance improvement due to error suppression. For
instance, better-optimized sequences could suppress idle-time errors further,
and dynamically corrected gates can suppress errors during operations [52,
53].

We note that the restriction to $n\leq 5$ arose not because of circuit width
but depth. In particular, we used two oracle queries, though theoretically
$q_{\text{opt}}=4$ at $n=5$. The gap between the theoretically and
experimentally optimal number of queries is expected to grow with problem
size. As is true for any quantum algorithm, optimizing circuit compilation and
increasing metrics such as $T_{1}$, $T_{2}$, and gate fidelities are all vital
for scalability.

##  VII Discussion and Conclusions

We implemented Grover’s algorithm of various sizes on multiple superconducting
qubit devices. To our knowledge, this is the largest successful demonstration
of Grover’s algorithm for which the quantum strategy outperforms its classical
counterpart. For two-qubit Grover, we focused on error detection via the
$[[4,2,2]]$ code and showed that it allowed us to achieve near-optimal
performance. Along the way, we introduced the method of algorithmic error
tomography. We showed that it provides a wealth of information complementary
to previous protocols, such as gate set tomography or just measuring the
success probability of an algorithm. We showed that error suppression via DD
is essential in attaining better-than-classical performance for larger problem
sizes.

Grover’s algorithm is a demanding algorithm [5] as it requires multiple
implementations of C${}_{n-1}Z$ – a fully entangling operation. The
superconducting trimon device [6], which prior to our results achieved the
highest success probability for 3-qubit Grover, is an example of algorithm-
tailored hardware where C${}_{2}Z$ is a native gate. Constructing hardware
that can natively perform such entangling operations may be one path to
realizing the full potential of Grover’s algorithm. Still, it is desirable to
achieve this goal with more general-purpose quantum hardware, as we have
strived to do here.

Today’s quantum experimentalists have various error mitigation tools at their
disposal. Measurement error mitigation [54, 12], dynamical decoupling, zero
noise extrapolation [11], and quantum error detection [38] are parallel
strategies that address different kinds of errors. Whether and which error
mitigation method to employ must be decided based on the problem and available
resources. In this work, we combined MEM with DD and quantum error detection.
As expected, these strategies complement each other. However, we found that
often, MEM only became useful after DD was employed. Dynamical decoupling,
which arguably has the lowest resource overhead and requires no
postprocessing, was the single most effective strategy in improving the
performance of our implementation of Grover’s algorithm. Our work adds to the
growing literature [55, 34, 36, 35, 23, 39] on the effectiveness of error
suppression through DD.

While we demonstrated a crossing of the classical threshold at every problem
size we tested, better-than-classical success probabilities are not enough to
claim a provable quantum speedup [56]. Such a claim would require computing
the scaling of the time-to-solution metric as a function of problem size and
extending it to the largest possible problem size that can be embedded on the
device. Here we could not go to the largest possible problem size as even at
$n=5$, our circuit is quite deep – two queries required $88$ two-qubit gates,
and for a larger number of queries or qubits, we no longer observed a quantum
advantage. Achieving quantum speedup for Grover search will require devices
that can implement circuits much deeper than those used here without a
catastrophic drop in fidelity. Recent results [57, 58] suggest that without
significant improvements in the surface code implementation, the latter will
not necessarily provide an advantage over the type of error suppression and
mitigation methods we have explored here. Thus, our results are likely to be
necessary (but not sufficient) stepping stones toward a quantum speedup for
Grover’s algorithm.

##  Appendix A Classical success probability

Let $p_{s}^{\text{C}}(q,N)$ be the classical success probability after $q$
oracle queries for an unsorted list with $N$ elements. If the oracle is never
consulted, then we are simply picking an element at random, and the
probability of finding the marked element is $p_{s}^{\text{C}}(0,N)=1/N$. At
the other extreme, after $N-1$ queries with negative replies from the oracle,
we are guaranteed to identify the marked element by selecting the last
remaining element so that $p_{s}^{\text{C}}(N-1,N)=1$. Clearly, the
probability grows in proportion to $q$, so we may conclude that
$p_{s}^{\text{C}}(q,N)=\frac{q+1}{N}$.

A complete argument is the following. Suppose there are $N$ elements. With
zero queries, we pick the marked element with probability
$p_{s}^{\text{C}}(0,N)=1/N$ and stop. With one query, either we already picked
the correct element with probability $p_{s}^{\text{C}}(0,N)=1/N$ and are so
informed by the oracle, or we are told this was the wrong element, so pick
again from the remaining set of $N-1$ elements. The probability that the
marked element was in the set of $N-1$ is $(N-1)/N$, and the probability of
now picking the correct element is $1/(N-1)$:
$p_{s}^{\text{C}}(1,N)=p_{s}^{\text{C}}(0,N)+(N-1)/N\times 1/(N-1)=2/N$. With
another query, we’re now told whether our second pick was correct or wrong; if
the latter, we pick again from the remaining set of $N-2$ elements. The
probability that the marked element was in the set of $N-2$ is $(N-2)/N$, and
the probability of now picking the correct element is $1/(N-2)$:
$p_{s}^{\text{C}}(2,N)=p_{s}^{\text{C}}(1,N)+(N-2)/N\times 1/(N-2)=3/N$. Each
time we increase the probability of success by $1/N$. Thus, continuing, we
have $p_{s}^{\text{C}}(q,N)=p_{s}^{\text{C}}(q-1,N)+(N-q)/N\times
1/(N-q)=(q+1)/N$.

##  Appendix B Survey of dynamical decoupling sequences

(a) $n=3$, Nairobi (b) $n=4$, Nairobi (c) $n=5$, Nairobi (d) $n=3$, Jakarta
(e) $n=4$, Jakarta (f) $n=5$, Jakarta

Figure 11: Performance of DD sequences, expanding on the results shown in Fig.
8. Average success probability for $n=3,4,5$ with two oracle queries on
Jakarta (top) and Nairobi (bottom). The DD sequences are ranked in order of
decreasing success probability. The two dotted lines represent success
probabilities corresponding to a random and classical strategy, respectively.
For $n>3$, the unprotected evolution (Free) is marginally better than choosing
an element randomly and does not cross the classical threshold. DD protection
is necessary to cross the classical threshold, and the RGA and UR sequences
with fewer than 12 pulses are the best performers. Error bars correspond to
99% confidence intervals.

Figure 12: Performance under different oracle query numbers. Success
probabilities are shown as a function of the number of oracle queries for
Jakarta (left) and Nairobi (right). All results included MEM, and error bars
represent 99% confidence intervals. Dashed red lines correspond to the optimal
classical success probability. Except for $n=3$, the classical threshold is
crossed only with DD. In the main text, we set $q=2$, which is the optimal
number of repetitions for all instances other than $n=5$ on Jakarta. Error
bars correspond to 99% confidence intervals.

In addition to the well-known XY4 and CPMG sequences, we consider three
families of robust dynamical decoupling sequences. These sequences are
expected to work well on a superconducting device with finite pulse width and
flip-angle errors. The first sequence family is concatenated DD (CDD). CDD
comprises recursively generated sequences by concatenating a base sequence
such as the XY4 sequence. Formally,

$\displaystyle\mathrm{XY}4/\mathrm{CDD}_{1}$ $\displaystyle\equiv Y-X-Y-X$
(13a) $\displaystyle\mathrm{CDD}_{n}$
$\displaystyle\equiv\mathrm{XY}4\left(\left[\mathrm{CDD}_{n-1}\right]\right)$
(13b)

Here we could only proceed as far as $\mathrm{CDD}_{2}$, as the idle intervals
in the circuit were too short to incorporate higher-order CDD sequences.

The second family comprises the robust genetic algorithm (RGA) sequences [21].
These were found by assuming a generic single-qubit error term and a numerical
optimization using genetic algorithms. A subset of the sequences was enforced
to be robust against flip-angle errors. Therefore, these sequences are called
robust genetic algorithm sequences. Due to duration constraints, we only
attempted sequences up to $32$ pulses, even though longer sequences were
identified in Ref. [21].

$\displaystyle\mathrm{RGA}_{4}$ $\displaystyle\equiv\bar{Y}-X-\bar{Y}-X$ (14a)
$\displaystyle\mathrm{RGA}_{4p}$
$\displaystyle\equiv\bar{Y}-\bar{X}-\bar{Y}-\bar{X}$ (14b)
$\displaystyle\mathrm{RGA}_{8a}$ $\displaystyle\equiv
X-\bar{Y}-X-\bar{Y}-Y-\bar{X}-Y-\bar{X}$ (14c)
$\displaystyle\mathrm{RGA}_{8c}/\mathrm{EDD}$ $\displaystyle\equiv X-Y-X-Y-Y-
X-Y-X$ (14d) $\displaystyle\mathrm{RGA}_{16b}$
$\displaystyle\equiv\mathrm{RGA}_{4p}\left(\left[\mathrm{RGA}_{4p}\right]\right)$
(14e) $\displaystyle\mathrm{RGA}_{32a}$
$\displaystyle\equiv\mathrm{RGA}_{4}\left(\left[\mathrm{RGA}_{8a}\right]\right)$
(14f) $\displaystyle\mathrm{RGA}_{32c}$
$\displaystyle\equiv\mathrm{RGA}_{8c}\left(\left[\mathrm{RGA}_{4}\right]\right).$
(14g)

Here ${X}$ means a $\pi$-rotation about the $+x$ axis. In contrast, $\bar{X}$
means a $\pi$-rotation about the $-x$ axis (see Ref. [39] for a concise and
detailed summary with more explicit definitions, including the effect of pulse
width and the associated errors).

Finally, the third family is that with universally robust (UR) sequences [19].
UR sequences are defined such that

$\displaystyle\mathrm{UR}_{n}$
$\displaystyle=(\pi)_{\phi_{1}}-(\pi)_{\phi_{2}}-\ldots-(\pi)_{\phi_{n}}$
(15a) $\displaystyle\phi_{k}$
$\displaystyle=\frac{(k-1)(k-2)}{2}\Phi^{(n)}+(k-1)\phi_{2}$ (15b)
$\displaystyle\Phi^{(4m)}$
$\displaystyle=\frac{\pi}{m}\Phi^{(4m+2)}=\frac{2m\pi}{2m+1},$ (15c)

where $(\pi)_{\phi}$ is rotation about the axis at an angle $\phi$ from the
$+x$-axis. We choose $\phi_{1}=0$, and $\phi_{2}=\Phi(n)$ so that all URn
sequences are palindromic. Once again, we constrained our survey to sequences
with up to $32$ pulses.

Our results from testing these three robust families of DD sequences are shown
in Fig. 11. For $n>3$, almost all DD sequences improved the success
probability, but even among the sequences tried, there was a considerable
variation. Robust sequences with fewer than $12$ pulses per DD cycle were the
best performers. The eventual decrease in the performance of sequences with an
increasing number of pulses is to be expected as they are implemented using
noisy gates, and there is a trade-off between the protection provided by DD
and the accumulation of gate errors. The RGA8c and RGA8a sequences performed
consistently well and are the only sequences to cross the classical threshold
on Jakarta for $n=5$. RGA8c is also commonly known as the Eulerian DD (EDD)
sequence, and RGA8a is a slightly modified version of EDD. These palindromic
sequences are known to be robust against flip-angle and finite-width errors.
The best sequence at each problem size is shown in Table 2.

Problem Size | Jakarta | Nairobi
---|---|---
$n=3$ | UR6 | RGA8a
$n=4$ | RGA8a | UR6
$n=5$ | RGA8c | RGA8a
Table 2: The best-performing DD sequence at each problem size for both QPUs.
These sequences were determined by implementing $n+1$ oracles of the form
$0^{k}1^{n-k}$ for the $n$-qubit Grover problem.

(a) Jakarta, $n=3$ (b) Nairobi, $n=3$ (c) Jakarta, $n=4$ (d) Nairobi, $n=4$
(e) Jakarta, $n=5$ (f) Nairobi, $n=5$

Figure 13: 3-qubit, 4-qubit, and 5-qubit Grover on Jakarta (left) and Nairobi
(right) after two oracle queries, complementing Fig. 9, which only shows
Nairobi for $n=5$. Each row represents a problem size in ascending order. In a
row, the horizontal bar plot on the left shows the success probability under
no error suppression and mitigation (Free), with measurement error mitigation
(Free + MEM), with DD protection (DD), and with DD protection and measurement
error mitigation (DD + MEM). The dashed horizontal line and the boxes
represent the classical and the theoretically expected success probability,
respectively. The second and third columns show the input-output map for Free
and DD + MEM, highlighting the improvement offered by these strategies. The
states are sorted by increasing Hamming weight. The transition from green to
black occurs at the classical success probability threshold. With DD
protection, the classical threshold is crossed in all cases.

Fig. 12 shows the experimental success probabilities for the unprotected and
DD-protected Grover circuits for all queries $q$. Here, only the best DD
sequence from the survey above (listed in Table 2) is used in each case.
Theoretically, for $n=3,4,5$, $q_{\text{opt}}=2,3,4$ respectively.
Unfortunately, for 5-qubit Grover, software restrictions prevented us from
going beyond $q=2$ and $3$ on Jakarta and Nairobi, respectively. However, it
is already clear that the experimentally optimal value was reached in both
cases. Recall that we restricted our results to $q=2$ oracle queries in the
main text. For $n=3$, this is both experimentally and theoretically optimal.
For Nairobi, two queries have the highest experimental success probability for
all problem sizes. For Jakarta and $n=5$, a single query has a slightly higher
success probability, but the difference between $q=1$ and $q=2$ is not
substantial. Overall, for simplicity of analysis, in the main text, we focused
only on results for $q=2$.

Finally, Fig. 13 shows the results for all oracles at two queries using the DD
sequence found from the survey above. The results are qualitatively identical
on both devices. We have already clarified that DD is necessary to cross the
classical threshold. One might suspect that majority voting may suffice to
declare a detected state as the marked state if it is the mode of its
corresponding probability distribution. However, even under this criterion,
for 5-qubit Grover, there is no way to detect the marked state without DD.

##  Appendix C Device Specifications

Jakarta and Nairobi are 7-qubit QPUs comprising the IBMQE Falcon r5.11
processors [59]. On these transmon qubit-based devices, single qubit gates are
performed by driving a DRAG pulse, and two-qubit gates are implemented using
echoed cross-resonance gates. They have quantum volumes of 16 and 32,
respectively [22]. The qubit connectivity for these QPUs is shown in Fig. 14.
Table 3 shows the gate errors, readout errors and the $T_{1}$ and $T_{2}$
times for both devices. The qubits used for each $n$ are listed below in
increasing order: q0, q1, q3, and q5 for our encoded two-qubit Grover
implementation; q0, q1, and q2 for 3-qubit Grover; q0, q2, q3, q5 as the main
qubits and q1 as the ancilla for 4-qubit Grover; q0, q2, q3, q5, q6 as the
main qubits and q1 as the ancilla for 5-qubit Grover.

| Jakarta |  | Nairobi |
---|---|---|---|---
| Min | Mean | Max | Min | Mean | Max
$T_{1}$ ($\mu$s) | 74.54 | 140.36 | 179.61 | 98.73 | 135.52 | 179.93
$T_{2}$ ($\mu$s) | 23.02 | 48.74 | 106.67 | 40.52 | 74.58 | 136.91
1QG Error (%) | 0.02 | 0.03 | 0.03 | 0.03 | 0.04 | 0.07
2QG Error (%) | 0.6 | 0.79 | 1.08 | 0.52 | 1.0 | 1.61
1QG Duration ($\mu$s) | 0.04 | 0.04 | 0.04 | 0.04 | 0.04 | 0.04
2QG Duration ($\mu$s) | 0.23 | 0.34 | 0.54 | 0.24 | 0.31 | 0.43
RO Error (%) | 1.73 | 3.44 | 5.12 | 2.27 | 3.43 | 4.68
RO Duration ($\mu$s) | 5.35 | 5.35 | 5.35 | 5.35 | 5.35 | 5.35
Table 3: Device specifications for Jakarta and Nairobi on July 14, 2022. 1QG,
2QG, and RO denote 1-qubit gate, two-qubit gate, and readout, respectively
[22]. Figure 14: Device connectivity. Jakarta and Nairobi devices are built
using the IBM Quantum Falcon r5.11H processors and have seven qubits.

##  Appendix D Measurement Error Mitigation

Figure 15:  Nairobi and MEM for unencoded two-qubit Grover. The horizontal bar
plot on the left shows the failure probability for the unencoded two-qubit
Grover algorithm for the unmitigated data and under two MEM techniques:
iterative Bayesian unfolding (IBU) and response matrix inversion (Inv). The
three heat maps show the output distribution under no mitigation, IBU, and
Inv, going from left to right. The input marked states are on the vertical
axis, and the printed numbers on the diagonal represent $p_{s}$ for the
respective marked states. The off-diagonal elements in the output distribution
are written explicitly to emphasize the presence of negative probabilities
under Inv in the right-most figure. Figure 16:  Same as Fig. 15 but for
encoded two-qubit Grover.

Measurement error mitigation relies on data collected from quantum detector
tomography [54] and classical post-processing to address systematic
measurement errors. The calibration experiments involve the preparation of
computational basis states $|j\rangle$ and acquiring the response matrix $M$
with elements $m_{kj}=\text{probability}(\text{prepare
}|j\rangle|\text{measure bitstring }k)$. $M$ is used to extract the “true”
mitigated probability vector $\vec{t}=f(\vec{p},M)$ from the observed
probability vector $\vec{p}$. Different error mitigation methods differ in how
they define $f$. The most commonly used MEM method, response matrix inversion
(Inv), sets $\vec{t}=M^{-1}\vec{p}$. This is a frequently used MEM strategy
[34, 60, 61, 62, 63]. However, Inv is inherently flawed in the sense that
$M^{-1}$ need not be stochastic, and as a result $\vec{t}$ can have negative
elements. Ref. [12] notes that iterative Bayesian unfolding (IBU) – a well-
established method to correct detector defects in high-energy physics
experiments – can address readout noise without compromising on stochasticity.
IBU is a simplified form of the expectation-maximization method from machine
learning that maximizes the likelihood function. In particular, starting with
a prior “truth spectrum” $\vec{t}^{0}$, the error mitigated distribution
$\vec{t}^{n}$ is obtained by repeatedly applying Bayes’ rule to get

$t_{i}^{n}=\sum\limits_{j}\frac{M_{ji}t^{n-1}_{i}}{\sum\limits_{k}M_{jk}t_{k}^{n-1}}p_{j}.$
(16)

We rely on IBU, in particular, the pyIBU package [45] to perform MEM to avoid
dealing with negative probabilities. In Ref. [45], the optimal $n$ at which
the iteration stops is determined by placing a lower limit on the
$\ell_{1}$-distance between $\vec{t}^{n}$ and $\vec{t}^{n-1}$.

In Fig. 6, there is a slight discrepancy in the observed and predicted
fidelities in the Unenc + MEM and Enc + MEM columns for Nairobi: the success
probability is lower than expected. The bar plots in Figs. 15 and 16 show that
this discrepancy is reduced if the mitigated distribution is computed using
Inv instead of IBU. However, Inv leads to unphysical results, as seen in the
rightmost output distribution map in Fig. 16 where $p_{s}>1$ for the marked
states $\ket{01}$ and $\ket{10}$. In particular, when using Inv, the terms in
$\vec{t}$ sum to 1 but the elements $t_{i}$ are not guaranteed to be in
$[0,1]$. The off-diagonal terms under Enc + Inv in Fig. 16 are indeed
negative. So while Enc + Inv has the best reported average success
probability, which is also higher than our model predicts, the underlying
output distribution is unphysical. IBU, on the other hand, always returns a
valid probability distribution but does not fully invert the response matrix
$M$. The discrepancy in simulated and observed values of Nairobi’s measurement
error mitigated failure probabilities reflects this. Despite its limitations,
we err on the side of caution and use IBU as the default MEM method. A more
systematic and recent critique of MEM is provided in Ref. [64].

##  Appendix E Extracting the depolarizing parameter from gate errors

IBMQE devices are calibrated daily, and for each gate, the gate error $e_{g}$
and gate time $\tau_{g}$ are reported. The associated $T_{1}$ and $T_{2}$
times are also reported for each qubit. As $e_{g}$ is extracted in presence of
thermal relaxation errors $\mathcal{R}=\Phi\circ\mathcal{A}$,
$p_{D}=f(e_{g},\tau_{g},T_{1},T_{2})$. In order to extract $p_{D}$ from
$e_{g}$, we assume that

$e_{g}=1-F(\mathcal{D}\circ\mathcal{R}).$ (17)

Using

$F(\mathcal{D}\circ\mathcal{R})=(1-p_{D})F(\mathcal{R})+p_{D}F(\mathbb{D}\circ
R),$ (18)

where $\mathbb{D}$ is the completely depolarizing channel, we get

$\displaystyle 1-e_{g}$ $\displaystyle=F(\mathcal{D}\circ\mathcal{R})$ (19a)
$\displaystyle=(1-p_{D})F(\mathcal{R})+p_{D}F(\mathbb{D}\circ R)$ (19b)
$\displaystyle=(1-p_{D})F(\mathcal{R})+p_{D}F(\mathbb{D})$ (19c)
$\displaystyle=(1-p_{D})F(\mathcal{R})+\frac{p_{D}}{d}.$ (19d)

Here, $d=4^{n}$ for $n$ qubits. Consequently,

$p_{D}=d\frac{F(\mathcal{R})-1+e_{g}}{dF(\mathcal{R})-1}.$ (20)

If we assume that there are no relaxation errors and only depolarizing noise
affects the gate error $e_{g}$, then $p_{D}=(d/d-1)e_{g}$.

##  Appendix F Circuit Construction

Recall that implementing the $n$-qubit Grover’s algorithm requires the
C${}_{n-1}Z$ gate, the only multi-qubit gate necessary for both the oracle and
the amplitude amplification step. We provide circuit diagrams for how each
$n$-qubit controlled phase gate, C${}_{n-1}Z$, was transpiled. We rely on
previously known circuit designs for our circuit construction, particularly
the circuits used by Ref. [8].

###  F.1 Two-qubit Grover circuits

For two-qubit Grover, $\mathrm{C}Z$ does not require transpilation as
$\mathrm{C}Z=H\cdot\mathrm{C}X\cdot H$. However, a few nuances must be
considered when constructing the encoded two-qubit Grover circuits. There are
three components to a Grover circuit with marked element $m=b_{1}b_{2}$:
initialization into the state $|\psi\rangle$, oracle query $O_{m}$, and
amplitude amplification $A$. More precisely,

$\displaystyle|\psi\rangle$
$\displaystyle=\frac{1}{4}\sum\limits_{b_{i},b_{j}=\\{0,1\\}}|b_{j}\rangle\otimes|b_{k}\rangle=H\otimes
H|00\rangle$ (21a) $\displaystyle O_{m}$ $\displaystyle=(X^{1-b_{1}}\otimes
X^{1-b_{2}})\cdot\text{C}Z\cdot(X^{1-b_{1}}\otimes X^{1-b_{2}})$ (21b)
$\displaystyle A$ $\displaystyle=H\otimes H\cdot O_{00}\cdot H\otimes H.$
(21c)

To convert these circuits into their logical counterparts, we note that
$\overline{X}_{1}=XIXI$, $\overline{X}_{2}=XXII$, $\overline{Z}_{1}=ZZII$,
$\overline{Z}_{2}=ZIZI$, $H^{\otimes
4}=\overline{\text{SWAP}}_{12}(\overline{H}_{1}\overline{H}_{2})$ and
$P^{\otimes 4}=(\overline{Z}_{1}\overline{Z}_{2})\overline{\text{C}Z}$. It is
also helpful to notice that $[\text{SWAP}_{12},U\otimes U]=0$ for any unitary
$U$ and $[\text{SWAP}_{12},\text{C}Z]=0$. Moreover,
$\text{SWAP}_{12}\ket{b_{1}b_{1}}=\ket{b_{1}b_{1}}$ and
$[\text{SWAP}_{12},O_{00}]=0$ as $O_{00}$ only has operators of the form
$U\otimes U$ and C$Z$. Consequently,

$\displaystyle\ket{\overline{\psi}}$
$\displaystyle=\overline{H}\otimes\overline{H}\ket{\overline{00}}$ (22a)
$\displaystyle=\overline{H}\otimes\overline{H}\cdot\overline{\text{SWAP}_{12}}\ket{\overline{00}}$
(22b)
$\displaystyle=\overline{\text{SWAP}_{12}}\cdot\overline{H}\otimes\overline{H}\ket{\overline{00}}$
(22c) $\displaystyle=H^{\otimes 4}U_{\text{enc}}\ket{00}.$ (22d)

Implementing the encoded Grover oracle is straightforward and does not involve
any two-qubit operations:

$\overline{O_{m}}=\overline{X^{1-b_{1}}}\otimes\overline{X^{1-b_{2}}}\cdot
IZZI\cdot P^{\otimes
4}\cdot\overline{X^{1-b_{1}}}\otimes\overline{X^{1-b_{2}}}.$ (23)

Lastly,

$\displaystyle A$
$\displaystyle=\overline{H}\otimes\overline{H}\cdot\overline{O_{00}}\cdot\overline{H}\otimes\overline{H}$
(24a)
$\displaystyle=\overline{H}\otimes\overline{H}\cdot\overline{O_{00}}\cdot\overline{H}\otimes\overline{H}\cdot\overline{\text{SWAP}_{12}}\cdot\overline{\text{SWAP}_{12}}$
(24b)
$\displaystyle=\overline{\text{SWAP}_{12}}\cdot\overline{H}\otimes\overline{H}\cdot\overline{O_{00}}\cdot\overline{\text{SWAP}_{12}}\cdot\overline{H}\otimes\overline{H}$
(24c) $\displaystyle=H^{\otimes 4}\cdot\overline{O_{00}}\cdot H^{\otimes 4}$
(24d) $\displaystyle=H^{\otimes 4}\cdot IXXI\cdot IZZI\cdot P^{\otimes 4}\cdot
IXXI\cdot H^{\otimes 4}.$ (24e)

The corresponding circuits for the marked state $|01\rangle$ are shown in Fig.
3.

###  F.2 3-qubit to 5-qubit Grover circuits

The problem of transpilation increases in complexity with problem size.
C${}_{n-1}Z$ can be achieved by finding a circuit decomposition for the
$n$-qubit Toffoli gate C${}_{n-1}X$. It is known that the three-qubit Toffoli
gate, C${}_{2}X$, can be implemented using six CNOTs [65]. However, this
requires a fully connected architecture. As no fully connected group of three
qubits can be found in the QPUs we used, we rely on the $8$-CNOT decomposition
[8] of C${}_{2}Z$ shown in Eq. 25.

$\small\Qcircuit@C=0.7em@R=0.7em@!R{&\ctrl{1}\qw\gate{T^{\dagger}}\ctrl{1}\qw\ctrl{1}\qw\ctrl{1}\qw\qw\ctrl{1}\qw\qw\\\
\ctrl{1}\qw=\hskip
19.91684pt\gate{T^{\dagger}}\targ\ctrl{1}\targ\ctrl{1}\targ\gate{T}\ctrl{1}\targ\ctrl{1}\qw\\\
\control\qw\qw\gate{T^{\dagger}}\qw\targ\gate{T^{\dagger}}\targ\gate{T}\qw\targ\gate{T}\targ\qw\\\
}$ (25)

Here $T=Z^{1/4}$. For C${}_{3}Z$ and C${}_{4}Z$ we use relative-phase Toffoli
gates [50]. Breaking down C${}_{k}Z$ using C${}_{a}Z$ and C${}_{b}Y$ such that
$a+b=k+c$ allows for C${}_{k}Z$ to be implemented with fewer CNOTs as long as
we use $c$ ancillas. In our construction, we only use one ancilla for
C${}_{3}Z$ and C${}_{4}Z$. C${}_{2}Y$ is shown in Eq. 26,

$\small\Qcircuit@C=0.7em@R=1em{&\ctrl{1}\qw\qw\qw\qw\ctrl{2}\qw\qw\qw\ctrl{2}\qw\\\
\ctrl{1}\qw=\hskip 19.91684pt\qw\ctrl{1}\qw\qw\qw\ctrl{1}\qw\qw\qw\\\
\gate{Y}\qw\qw\gate{G}\targ\gate{G}\targ\gate{G^{\dagger}}\targ\gate{G^{\dagger}}\control\qw\qw\\\
}$ (26)

where $G=R_{y}(\pi/4)$, and C${}_{3}Y$ is shown in Eq. 27:

$\small\Qcircuit<EMAIL_ADDRESS>\ctrl{1}\qw\qw\qw\qw\qw\qw\qw\qw\ctrl{2}\qw\qw\qw\ctrl{2}\qw\qw\qw\qw\qw\qw\ctrl{1}\qw\\\
\ctrl{1}\qw\raisebox{11.38092pt}{=}\hskip
25.6073pt\qw\qw\ctrl{1}\qw\qw\qw\qw\qw\qw\qw\qw\qw\qw\qw\qw\ctrl{1}\qw\qw\ctrlo{1}\qw\\\
\gate{Y}\qw\qw\gate{H}\gate{T}\targ\gate{T^{\dagger}}\gate{H}\targ\gate{T}\targ\gate{T^{\dagger}}\targ\gate{T}\targ\gate{T^{\dagger}}\gate{H}\gate{T}\targ\gate{T^{\dagger}}\gate{H}\gate{-iZ}\qw\\\
}$ (27)

Finally, using the relative-phase Toffoli gates, C${}_{3}Z$ can be written as
in Eq. 28:

$\small\Qcircuit<EMAIL_ADDRESS>\ctrl{2}\qw\ctrl{1}\qw\ctrl{1}\qw\\\ \qw\qw\qw=\hskip 14.22636pt\hskip
11.38092pt|0\rangle\gate{Y}\ctrl{1}\gate{Y^{\dagger}}\qw\\\
\ctrl{1}\qw\qw\ctrl{1}\qw\qw\\\ \control\qw\qw\qw\control\qw\qw\qw}$ (28)

and likewise, C${}_{4}Z$can be constructed as in Eq. 29:

$\small\Qcircuit<EMAIL_ADDRESS>\ctrl{1}\qw\ctrl{1}\qw\ctrl{1}\qw\\\ \ctrl{2}\qw\ctrl{1}\qw\ctrl{1}\qw\\\
\qw\qw\qw\raisebox{14.22636pt}{=}\hskip 14.22636pt\hskip
11.38092pt|0\rangle\gate{Y}\ctrl{1}\gate{Y^{\dagger}}\qw\\\
\ctrl{1}\qw\qw\ctrl{1}\qw\qw\\\ \control\qw\qw\qw\control\qw\qw\qw}$ (29)

This scheme – where relative phase Toffoli gates [50] are sewn together to
generate a circuit for $\mathrm{C}_{n-1}Z$ ($n>k+2$) – can be generalized. In
particular, $\mathrm{C}_{n-1}Z$ can be implemented using C${}_{2}Y$,
C${}_{2}Y^{\dagger}$ and $\mathrm{C}_{n-2}Z$, which in turn uses
$\mathrm{C}_{n-3}Z$. As a result of this recursion, the number of CNOTS for a
$\mathrm{C}_{n-1}Z$ circuit is

$\\#(\mathrm{C}_{n-1}Z)=2(n-3)\ \\#(\mathrm{C}_{2}Y)+\\#(\mathrm{C}_{2}Z).$
(30)

Thus, the number of CNOTs required to implement a single query of $n$-qubit
Grover scales as $O(n)$. At the same time, the number of necessary ancillas is
$n-2$, i.e., it also scales linearly with $n$. As we did by using Eq. 29, this
linear scaling of ancillas could be avoided by considering $\mathrm{C}_{k}Y$
with $k>2$ while increasing the number of CNOTs. Whether entangling fewer
qubits by allowing for deeper circuits is worthwhile will depend on the QPU
architecture under consideration. Note that the theoretical optimal number of
queries $q_{\text{opt}}=O(2^{n/2})$ so at $q_{\text{opt}}$, the number of
CNOTs scales as $O(2^{n/2}n)$ where the exponential component will dominate.
However, as we noted before, the experimentally allowed number of queries
before decoherence takes over might be less than $q_{\text{opt}}$.

##  Appendix G Open system model optimization

Figure 17:  Scaling calibration metrics. The $\ell_{1}$-norm based distance
$D$ between the observed and simulated outputs for two-qubit Grover is shown
as a function of the scaling parameters $\lambda_{i}$. The model parameters
are scaled by setting $T_{1}\rightarrow\lambda_{1}^{-1}T_{1}$,
$T_{2}\rightarrow\lambda_{2}^{-1}T_{2}$ and
$p_{D}\rightarrow\lambda_{g}p_{D}$. The left and right columns represent
unencoded and encoded implementations, respectively. The dotted black line
represents the default setting $\lambda_{i}=1$. The grey band in the Jakarta
case (top row) is $D$ for the DD-protected circuit versions. For Nairobi
(bottom row), even without error suppression, the fit between theory and
experiment is already quite good, and our optimization aims to improve the fit
further. Thus, in the bottom row (Nairobi), the grey band corresponds to the
distance between simulated and observed at $\lambda_{i}=1$.  Figure 18:
Algorithmic error tomography on Jakarta for optimized parameters. The plot
shows the results of AET on the encoded two-qubit Grover algorithm after
setting $(\lambda_{1},\lambda_{2},\lambda_{g})=(1,1,6)$. Each row of the error
tomography table corresponds to a marked state, and each column represents
logical errors and $X,Y,Z$ type errors. Even after rescaling the model
parameters, compared to the error tomography table for Jakarta (Fig. 4), we do
not see an asymmetry in $Z$ errors across marked states.

The model presented in Section III only accounts for amplitude damping,
dephasing, and depolarization, which are a subset of the errors in a
superconducting device. Notably, this model does not include crosstalk,
leakage to higher energy levels, and non-Markovian system-environment
interaction. As we saw in the main text, introducing error suppression
improves the agreement between our model and the observations. However, in the
absence of DD, the model results often provide an upper bound on the
performance, and the device can perform worse than the model’s predictions.

It is plausible to ask if rescaling the calibration metrics provided by IBMQE
results in an improved phenomenological model and better predictability of the
device performance. To do this, we quantify model predictability by computing
the $\ell_{1}$-norm based distance between the experimentally observed
probability distribution $\mathbf{p}^{m}$ and the simulated distribution
$\mathbf{q}^{m}$ for marked states $\ket{m}$. We define

$D=\frac{1}{2^{n}}\sum_{m=0}^{2^{n}-1}D^{m}\ ,\quad
D^{m}=\frac{1}{2}\sum_{i=0}^{2^{n}-1}|p^{m}_{i}-q^{m}_{i}|,$ (31)

such that $D$ is the distance between the probability distributions averaged
over all the marked states $\ket{m}$. $D=0$ implies a perfect match between
the simulated and the observed distributions, and $D=1$ means completely
distinguishable distributions. We then consider $D$ as a function of rescaling
parameters $\lambda_{i}$ such that $T_{1}\rightarrow\lambda_{1}^{-1}T_{1}$,
$T_{2}\rightarrow\lambda_{2}^{-1}T_{2}$ and
$p_{D}\rightarrow\lambda_{g}p_{D}$.

To evaluate the feasibility of this approach, we focus on the smallest problem
size, $n=2$. The most significant error contribution comes from the
depolarizing channel, as $D$ is most responsive to $\lambda_{g}$. With this in
mind, we start from the default setting $\lambda_{i}=1$, then optimize
$\lambda_{g},\lambda_{1},\lambda_{2}$ in that order, using the optimal value
from the previous scan as the input for the next parameter.

Fig. 17 shows the distance $D$ as a function of $\lambda_{i}$. Recall that in
the absence of DD, we reported discrepancies in both the AET of the encoded
circuit (Fig. 4) and the failure probabilities of the unencoded circuit (Fig.
6) for Jakarta. To directly compare the result of optimizing $\lambda$ to the
effectiveness of error suppression, Fig. 17 (top row) also shows the distance
$D$ between theory and experiment after DD.

For the unencoded experiment, increasing $p_{D}$ by a factor of
$\lambda_{g}=10$ suffices for the model to match the experiment. $D$ is
minimized at $\lambda_{1},\lambda_{2}=1$, i.e., there is no change from the
default setting for $T_{1}$ and $T_{2}$. However, even with the optimized
values (i.e., setting $\lambda_{g}=10$, $\lambda_{1},\lambda_{2}=1$), the new
model barely improves upon activating DD, corresponding to the grey band.
Similarly, for the encoded two-qubit Grover on Jakarta, only optimizing
$p_{D}$ leads to a noticeable decrease in $D$, with the best fit found at
$\lambda_{g}=6$. The optimized model does match the success probability
acquired by activating DD (grey band, top right). However, AET at
$\lambda_{g}=6$, shown in Fig. 18, does not exhibit the state-wise asymmetry
seen in Fig. 4. A similar optimization on Nairobi confirms our earlier
observation: the model that uses the provided calibration metrics fits with
the observed results, and Nairobi does not benefit from parameter rescaling.

To summarize, rescaling the calibration metrics to improve predictability is
mildly effective: the agreement with the experimental $p_{s}$ results improves
by increasing the depolarization. However, the optimized model does not match
the AET results for Jakarta. A more sophisticated model that includes qubit
crosstalk and leakage to/from higher energy levels appears necessary for a
better agreement. However, as highlighted in the main text, introducing error
suppression via DD provides a reliable way to simultaneously improve
performance and agreement with a model that accounts only for Markovian
amplitude damping, dephasing, and depolarization.

##  Appendix H Postselection on 4-qubit and 5-qubit Grover

Figure 19: Postselection for 4-qubit and 5-qubit Grover: Success probabilities
are shown with and without postselection for Nairobi (green) and Jakarta
(orange). Here we only consider the DD-protected circuits. 3-qubit Grover does
not undergo postselection. For 4-qubit and 5-qubit Grover, we postselect to
count only the experiments for which the ancilla qubit (q1 in Fig. 14) is in
$\ket{0}$. The white lines correspond to the success probabilities for the
classical strategy and random sampling from the unsorted list ($q=0$). With
postselection, for all problem sizes, the DD-protected quantum $q=2$ strategy
outperforms the classical strategy for $q\leq 3$. Without postselection, the
better-than-classical requirement is met by all implementations other than
5-qubit Grover on Jakarta, where we achieve a breakeven. Error bars correspond
to 99% confidence intervals.

The circuits for $\mathrm{C}_{3}Z$ and $\mathrm{C}_{4}Z$ require 5 and 6
qubits, respectively [see Eqs. 28 and 29], with one ancilla qubit used to link
the Toffoli and relative-phase Toffoli gates. The ancilla qubit is initialized
in $\ket{0}$ and should be in that state at the end of the algorithm.
Consequently, when measured in the $Z$-basis, observing the ancilla qubit in
$\ket{1}$ implies that an error occurred in the implementation of the
$\mathrm{C}_{3}Z$ or $\mathrm{C}_{4}Z$ gate. We postselect the 4-qubit and
5-qubit Grover experiments by only considering experiments for which the
ancilla qubit (q1 in Fig. 14) is measured to be in state $\ket{0}$. Fig. 19
shows the effect of postselection on success probabilities. The better-than-
classical performance for Nairobi holds even if postselection is avoided.
However, without postselection, we see a tie with the classical result for
5-qubit Grover on Jakarta at $q=2$. Overall, there is a non-trivial increase
in success probabilities due to postselection. Using ancilla qubits for
postselection is convenient, as these ancilla qubits also allow for much
shallower circuits for implementing $\mathrm{C}_{n-1}Z$ (recall Appendix F).
All the results we report in other sections are after postselection, including
the survey of DD sequences.

## References

  * Grover [1997] L. K. Grover, Phys. Rev. Lett. 79, 325 (1997).
  * Bennett  _et al._ [1997] C. Bennett, E. Bernstein, G. Brassard, and U. Vazirani,  _SIAM Journal on Computing_ , SIAM Journal on Computing 26, 1510 (1997).
  * Dürr  _et al._ [2006] C. Dürr, M. Heiligman, P. Hoyer, and M. Mhalla, SIAM Journal on Computing 35, 1310 (2006).
  * Magniez  _et al._ [2007] F. Magniez, M. Santha, and M. Szegedy, SIAM Journal on Computing (2007), 10.1137/050643684.
  * Lubinski  _et al._ [2021] T. Lubinski, S. Johri, P. Varosy, J. Coleman, L. Zhao, J. Necaise, C. H. Baldwin, K. Mayer, and T. Proctor, “Application-Oriented Performance Benchmarks for Quantum Computing,”  (2021), arXiv:2110.03137 [quant-ph] .
  * Roy  _et al._ [2020] T. Roy, S. Hazra, S. Kundu, M. Chand, M. P. Patankar, and R. Vijay, Phys. Rev. Applied 14, 014072 (2020).
  * Figgatt  _et al._ [2017] C. Figgatt, D. Maslov, K. A. Landsman, N. M. Linke, S. Debnath, and C. Monroe, Nat. Commun. 8, 1 (2017).
  * Zhang  _et al._ [2021] K. Zhang, P. Rao, K. Yu, H. Lim, and V. Korepin, Quant. Inf. Proc. 20, 233 (2021).
  * Vaidman  _et al._ [1996] L. Vaidman, L. Goldenberg, and S. Wiesner, Physical Review A 54, R1745 (1996).
  * Gottesman [1997] D. Gottesman,  _Stabilizer codes and quantum error correction_ , Ph.D. thesis, California Institute of Technology (1997), arXiv:quant-ph/9705052 .
  * Kandala  _et al._ [2019] A. Kandala, K. Temme, A. D. Córcoles, A. Mezzacapo, J. M. Chow, and J. M. Gambetta, Nature 567, 491 (2019).
  * Nachman  _et al._ [2020] B. Nachman, M. Urbanek, W. A. de Jong, and C. W. Bauer, npj Quantum Information 6, 84 (2020).
  * Blume-Kohout  _et al._ [2013] R. Blume-Kohout, J. K. Gamble, E. Nielsen, J. Mizrahi, J. D. Sterk, and P. Maunz, arXiv:1310.4492 (2013).
  * Merkel  _et al._ [2013] S. T. Merkel, J. M. Gambetta, J. A. Smolin, S. Poletto, A. D. Córcoles, B. R. Johnson, C. A. Ryan, and M. Steffen, Physical Review A 87, 062119 (2013).
  * Viola and Lloyd [1998] L. Viola and S. Lloyd, Phys. Rev. A 58, 2733 (1998).
  * Viola  _et al._ [1999] L. Viola, E. Knill, and S. Lloyd, Physical Review Letters 82, 2417 (1999).
  * Zanardi [1999] P. Zanardi, Physics Letters A 258, 77 (1999).
  * Vitali and Tombesi [1999] D. Vitali and P. Tombesi, Physical Review A 59, 4178 (1999).
  * Genov  _et al._ [2017] G. T. Genov, D. Schraft, N. V. Vitanov, and T. Halfmann, Physical Review Letters 118, 133202 (2017).
  * Khodjasteh and Lidar [2005] K. Khodjasteh and D. A. Lidar, Physical Review Letters 95, 180501 (2005).
  * Quiroz and Lidar [2013] G. Quiroz and D. A. Lidar, Phys. Rev. A 88, 052306 (2013).
  * IBM [2022] “IBM Quantum,”  (2022).
  * Tripathi  _et al._ [2022] V. Tripathi, H. Chen, M. Khezri, K.-W. Yip, E. M. Levenson-Falk, and D. A. Lidar, Physical Review Applied 18, 024068 (2022).
  * Zhou  _et al._ [2022] Z. Zhou, R. Sitler, Y. Oda, K. Schultz, and G. Quiroz, “Quantum crosstalk robust quantum control,”  (2022), arXiv:2208.05978 [quant-ph] .
  * Boyer  _et al._ [1998] M. Boyer, G. Brassard, P. Hoyer, and A. Tapp, Fortschritte der Physik 46, 493 (1998).
  * Biham  _et al._ [1999] E. Biham, O. Biham, D. Biron, M. Grassl, and D. A. Lidar, Physical Review A 60, 2742 (1999).
  * Blank  _et al._ [2020] C. Blank, D. K. Park, J.-K. K. Rhee, and F. Petruccione, npj Quantum Information 6, 1 (2020).
  * Rivas and Huelga [2012] A. Rivas and S. F. Huelga,  _Open Quantum Systems: An Introduction_, SpringerBriefs in Physics (Springer-Verlag, Berlin Heidelberg, 2012).
  * Nielsen [2002] M. A. Nielsen, Physics Letters A 303, 249 (2002).
  * Paz-Silva and Lidar [2013] G. A. Paz-Silva and D. A. Lidar, Sci. Rep. 3, 1530 (2013).
  * Suter and Álvarez [2016] D. Suter and G. A. Álvarez, Rev. Mod. Phys. 88, 041001 (2016).
  * West  _et al._ [2010a] J. R. West, D. A. Lidar, B. H. Fong, and M. F. Gyure, Phys. Rev. Lett. 105, 230503 (2010a).
  * Ng  _et al._ [2011] H. K. Ng, D. A. Lidar, and J. Preskill, Phys. Rev. A 84, 012305 (2011).
  * 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, Quantum Sci. Technol. 6, 025020 (2021).
  * Ravi  _et al._ [2021] G. S. Ravi, K. N. Smith, P. Gokhale, A. Mari, N. Earnest, A. Javadi-Abhari, and F. T. Chong, “VAQEM: A Variational Approach to Quantum Error Mitigation,”  (2021).
  * Pokharel and Lidar [2022] B. Pokharel and D. A. Lidar, “Demonstration of algorithmic quantum speedup,”  (2022), arXiv:2207.07647 [quant-ph] .
  * Maudsley [1986] A. A. Maudsley, Journal of Magnetic Resonance (1969) 69, 488 (1986).
  * Lidar and Brun [2013] D. Lidar and T. Brun, eds.,  _Quantum Error Correction_ (Cambridge University Press, Cambridge, UK, 2013).
  * Ezzell  _et al._ [2022] N. Ezzell, B. Pokharel, L. Tewala, G. Quiroz, and D. A. Lidar, “Dynamical decoupling for superconducting qubits: a performance survey,”  (2022), arXiv:2207.03670 [quant-ph] .
  * Uhrig [2007] G. S. Uhrig, Phys. Rev. Lett. 98, 100504 (2007).
  * West  _et al._ [2010b] J. R. West, B. H. Fong, and D. A. Lidar, Phys. Rev. Lett. 104, 130501 (2010b).
  * [42] C. Vuillot, Quantum Information and Computation 18, 10/gktsqq, arXiv:1705.08957 .
  * Harper and Flammia [2019] R. Harper and S. T. Flammia, Physical Review Letters 122, 080504 (2019).
  * Urbanek  _et al._ [2020] M. Urbanek, B. Nachman, and W. A. de Jong, Physical Review A 102, 022427 (2020), arXiv:1910.00129 .
  * Srinivasan  _et al._ [2022] S. Srinivasan, B. Pokharel, G. Quiroz, and B. Boots, “Scalable Measurement Error Mitigation via Iterative Bayesian Unfolding,”  (2022), arXiv:2210.12284 [quant-ph] .
  * Krantz  _et al._ [2019] P. Krantz, M. Kjaergaard, F. Yan, T. P. Orlando, S. Gustavsson, and W. D. Oliver, Applied Physics Reviews 6, 021318 (2019).
  * Ofek  _et al._ [2016] N. Ofek, A. Petrenko, R. Heeres, P. Reinhold, Z. Leghtas, B. Vlastakis, Y. Liu, L. Frunzio, S. M. Girvin, L. Jiang, M. Mirrahimi, M. H. Devoret, and R. J. Schoelkopf, Nature 536, 441 EP (2016).
  * Ryan-Anderson  _et al._ [2022] C. Ryan-Anderson, N. C. Brown, M. S. Allman, B. Arkin, G. Asa-Attuah, C. Baldwin, J. Berg, J. G. Bohnet, S. Braxton, N. Burdick, J. P. Campora, A. Chernoguzov, J. Esposito, B. Evans, D. Francois, J. P. Gaebler, T. M. Gatterman, J. Gerber, K. Gilmore, D. Gresh, A. Hall, A. Hankin, J. Hostetter, D. Lucchetti, K. Mayer, J. Myers, B. Neyenhuis, J. Santiago, J. Sedlacek, T. Skripka, A. Slattery, R. P. Stutz, J. Tait, R. Tobey, G. Vittorini, J. Walker, and D. Hayes, “Implementing fault-tolerant entangling gates on the five-qubit code and the color code,”  (2022), arXiv:2208.01863 [quant-ph] .
  * Marvian and Lidar [2017] M. Marvian and D. A. Lidar, Phys. Rev. Lett. 118, 030504 (2017).
  * Maslov [2016] D. Maslov, Physical Review A 93, 022311 (2016).
  * Arute  _et al._ [2019] F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S. Humble, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, J. Kelly, P. V. Klimov, S. Knysh, A. Korotkov, F. Kostritsa, D. Landhuis, M. Lindmark, E. Lucero, D. Lyakh, S. Mandrà, J. R. McClean, M. McEwen, A. Megrant, X. Mi, K. Michielsen, M. Mohseni, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Y. Niu, E. Ostby, A. Petukhov, J. C. Platt, C. Quintana, E. G. Rieffel, P. Roushan, N. C. Rubin, D. Sank, K. J. Satzinger, V. Smelyanskiy, K. J. Sung, M. D. Trevithick, A. Vainsencher, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, and J. M. Martinis, Nature 574, 505 (2019).
  * Khodjasteh and Viola [2009] K. Khodjasteh and L. Viola, Phys. Rev. Lett. 102, 080501 (2009).
  * Khodjasteh  _et al._ [2010] K. Khodjasteh, D. A. Lidar, and L. Viola, Phys. Rev. Lett. 104, 090501 (2010).
  * Maciejewski  _et al._ [2020] F. B. Maciejewski, Z. Zimborás, and M. Oszmaniec, Quantum 4, 257 (2020).
  * Pokharel  _et al._ [2018] B. Pokharel, N. Anand, B. Fortman, and D. A. Lidar, Phys. Rev. Lett. 121, 220502 (2018).
  * Ronnow  _et al._ [2014] T. F. Ronnow, Z. Wang, J. Job, S. Boixo, S. V. Isakov, D. Wecker, J. M. Martinis, D. A. Lidar, and M. Troyer, Science 345, 420 (2014).
  * Campbell  _et al._ [2019] E. Campbell, A. Khurana, and A. Montanaro, Quantum 3, 167 (2019).
  * Sanders  _et al._ [2020] Y. R. Sanders, D. W. Berry, P. C. S. Costa, L. W. Tessler, N. Wiebe, C. Gidney, H. Neven, and R. Babbush, PRX Quantum 1, 020312 (2020).
  * Pednault  _et al._ [2019] E. Pednault, J. A. Gunnels, G. Nannicini, L. Horesh, and R. Wisnieff, arXiv preprint arXiv:1910.09534 (2019).
  * Mooney  _et al._ [2021a] G. J. Mooney, G. A. L. White, C. D. Hill, and L. C. L. Hollenberg, Journal of Physics Communications 5, 095004 (2021a).
  * Mooney  _et al._ [2021b] G. J. Mooney, G. A. L. White, C. D. Hill, and L. C. L. Hollenberg, Advanced Quantum Technologies 4, 2100061 (2021b).
  * Barron and Wood [2020] G. S. Barron and C. J. Wood, “Measurement Error Mitigation for Variational Quantum Algorithms,”  (2020), arXiv:2010.08520 [quant-ph] .
  * Bravyi  _et al._ [2021] S. Bravyi, S. Sheldon, A. Kandala, D. C. Mckay, and J. M. Gambetta, Physical Review A 103, 042605 (2021).
  * Quek  _et al._ [2022] Y. Quek, D. S. Franca, S. Khatri, J. J. Meyer, and J. Eisert, “Exponentially tighter bounds on limitations of quantum error mitigation,”  (2022).
  * Nielsen and Chuang [2010] M. A. Nielsen and I. L. Chuang,  _Quantum computation and quantum information_ (Cambridge University Press, 2010).