groups

# Demonstration of Algorithmic Quantum Speedup for an Abelian Hidden Subgroup
Problem

Phattharaporn Singkanipa  Department of Physics, University of Southern
California, Los Angeles, CA 90089, USA  Victor Kasatkin  Viterbi School of
Engineering, University of Southern California, Los Angeles, CA 90089, USA
Zeyuan Zhou  William H. Miller III Department of Physics & Astronomy, Johns
Hopkins University, Baltimore, Maryland 21218, USA  Gregory Quiroz  William H.
Miller III Department of Physics & Astronomy, Johns Hopkins University,
Baltimore, Maryland 21218, USA  Johns Hopkins University Applied Physics
Laboratory, Laurel, Maryland 20723, USA  Daniel A. Lidar  Departments of
Electrical Engineering, Chemistry, Physics and Astronomy, and Center for
Quantum Information Science & Technology, University of Southern California,
Los Angeles, CA 90089, USA

###### Abstract

Simon’s problem is to find a hidden period (a bitstring) encoded into an
unknown 2-to-1 function. It is one of the earliest problems for which an
exponential quantum speedup was proven for ideal, noiseless quantum computers,
albeit in the oracle model. Here, using two different $127$-qubit IBM Quantum
superconducting processors, we demonstrate an algorithmic quantum speedup for
a variant of Simon’s problem where the hidden period has a restricted Hamming
weight. The speedup is sub-exponential and is enhanced when the computation is
protected by dynamical decoupling to suppress decoherence. The speedup is
further enhanced with measurement error mitigation. This constitutes a
demonstration of a bona fide quantum advantage for an Abelian hidden subgroup
problem.

##  I Introduction

Quantum algorithms have been known to outperform classical algorithms for more
than 30 years Deutsch and Jozsa (1992); Bernstein and Vazirani (1997); Simon
(1997); Grover (1997); Shor (1997); Childs  _et al._ (2003); Van Dam  _et al._
(2006); Harrow  _et al._ (2009); Montanaro (2016); Bravyi  _et al._ (2018,
2020); Bharti  _et al._ (2022); Daley  _et al._ (2022), assuming that they run
on ideal, noiseless quantum devices. However, today’s noisy intermediate-scale
quantum (NISQ) Preskill (2018) devices are functional on a relatively small
scale of several hundreds of qubits and are highly susceptible to performance
degradation due to decoherence and control errors. A central current focus is
the experimental demonstration of an algorithmic quantum speedup on these
devices, i.e., a scaling advantage for a quantum algorithm solving a
computational problem. A variety of such demonstrations have been reported
Albash and Lidar (2018); King  _et al._ (2021); Saggio  _et al._ (2021);
Centrone  _et al._ (2021); Maslov  _et al._ (2021); Xia  _et al._ (2021);
Huang  _et al._ (2022); Ebadi  _et al._ (2022); Zhou  _et al._ (2022); King
_et al._ (2023); Kim  _et al._ (2023), but all are subject to various caveats
such as relying on computational complexity conjectures or being limited to an
advantage over a restricted set of classical algorithms. These demonstrations
are separate and distinct from recent quantum supremacy results Aaronson and
Chen (2017); Arute  _et al._ (2019); Wu  _et al._ (2021); Zhong  _et al._
(2020, 2021); Morvan  _et al._ (2023) and from benchmarking the performance of
NISQ devices Figgatt  _et al._ (2017); Wright  _et al._ (2019); Roy  _et al._
(2020); Pelofske  _et al._ (2022); Lubinski  _et al._ (2023). The former does
not corroborate a scaling advantage Barak  _et al._ (2021); Zlokapa  _et al._
(2023); Aharonov  _et al._ (2023), while the latter focuses on demonstrating
better-than-classical probabilities of success without resolving the question
of scaling of the time to solve the computational problem with problem size,
which is essential for the demonstration of an algorithmic quantum speedup
Ronnow  _et al._ (2014).

Recently, a conjecture-free algorithmic quantum speedup was demonstrated in
the oracle model against the best possible classical algorithm Pokharel and
Lidar (2023). In particular, a polynomial algorithmic quantum scaling
advantage for the single-shot version of the Bernstein-Vazirani algorithm was
observed when implemented on a 27-qubit IBM Quantum processor with noise
suppression via dynamical decoupling (DD) Viola and Lloyd (1998); Viola  _et
al._ (1999); Zanardi (1999), a well-established error suppression method for
NISQ devices Pokharel  _et al._ (2018); Souza (2021); Tripathi  _et al._
(2022); Jurcevic  _et al._ (2021); rav (2022). The Bernstein-Vazirani
algorithm was among the very first algorithms for which a quantum speedup was
rigorously proven, and in this sense, it is of historical significance. Even
more interesting would be an algorithmic quantum speedup for a problem that
belongs to the class of Abelian hidden subgroup problems Jozsa (2001), which
includes integer factorization. Simon’s problem Simon (1997), a precursor to
Shor’s factoring algorithm Shor (1997), involves finding a hidden subgroup of
the group $(\mathbb{Z}_{2}^{n},\oplus)$, which is the $n$-fold direct product
of the cyclic group $\mathbb{Z}_{2}$ (the integers modulo 2) with the group
operation being bitwise XOR ($\oplus$), and this group is Abelian. In Simon’s
problem, the Abelian hidden subgroup consists of the identity and a secret
string $b$, and the goal is to determine $b$.

Here, we revisit Simon’s problem and demonstrate an unequivocal algorithmic
quantum speedup for a restricted Hamming-weight version of this problem using
a pair of IBM Quantum processors. Similar to Ref. Pokharel and Lidar (2023),
we find an enhanced quantum speedup when the computation is protected by DD.
The use of measurement error mitigation (MEM) further enhances the scaling
advantage we observe. Our result can be viewed as bringing the field of NISQ
algorithms closer to a demonstration of a quantum speedup via Shor’s
algorithm. It also highlights the essential role of quantum error suppression
methods in such a demonstration.

To set the stage, we now explain the restricted-weight Simon’s problem that is
the focus of this work. In the original formulation of Simon’s problem, we are
given a function $f_{b}:\\{0,1\\}^{n}\rightarrow\\{0,1\\}^{n}$, where $n$ is
the problem size, and we are promised that $f_{b}$ is either 1-to-1 or 2-to-1,
such that $\forall x,y\in\\{0,1\\}^{n}$, $f_{b}(x)=f_{b}(y)$ if and only if
$x=y$ or $x=y\oplus b$ for a hidden bitstring $b\in\\{0,1\\}^{n}$. We wish to
determine which condition holds for $f_{b}$ and, in the latter case, find $b$.
Since the first condition (1-to-1) has one possible hidden bitstring
$b=0^{n}$, in this work we only consider the 2-to-1 version of Simon’s
problem, and our goal is to determine the length-$n$ hidden bitstring $b$. It
is well known (and we revisit this below in detail) that the classical and
quantum query complexities are $O(2^{n/2})$ and $O(n)$, respectively.

Instead of allowing all possible binary hidden bitstrings $b\in\\{0,1\\}^{n}$
as in the original Simon’s problem, we restrict their Hamming weight (HW),
that is, the number of $1$’s in $b$. We refer to this modification as the
‘restricted-HW’ version of Simon’s algorithm, denoted
$\mathsf{w}_{{w}}\textnormal{Simon-}{n}$. Here $w\leq n$ is the maximum
allowed HW. We will show that this modification allows us to exhibit a quantum
speedup for relatively shallow circuits, whose depth is set by $w$. The need
for the restriction arises because current NISQ devices are still too noisy to
fully solve the original, unrestricted ($w=n$) Simon’s problem when $n$
becomes large.

We work in the setting of a guessing game, the rules of which are tuned in
order to make the speedup possible and are explained in Section II. In
particular, we introduce an oracle-query metric we call NTS (number-of-oracle-
queries-to-solution), to quantify the performance of different players of this
game. The optimal classical and quantum algorithms to solve Simon’s problem
are described in Section III. We show that the classical algorithm requires
$\mathrm{poly}(n^{w/2})$ oracle queries, whereas the quantum algorithm
requires $\sim w\log_{2}(n)$ queries. In Section IV we quantify how a quantum
speedup can be detected using the NTS metric. In Section V we discuss the
experimental setup and IBMQ devices we used to perform our algorithmic speedup
tests, including the DD sequences we selected to enhance performance. Then, in
Section VI we discuss our results and the evidence for a quantum speedup in
the $\mathsf{w}_{{w}}\textnormal{Simon-}{n}$ problem. We conclude in Section
VII. The appendices contain additional technical details as well as
supplemental experimental results.

##  II Rules of the Game

The game is designed for a single player. If there are multiple players, they
can play the game individually and then compare their scores. At a high level,
the game works as follows. A function $f\colon\\{0,1\\}^{n}\to\\{0,1\\}^{n}$
that satisfies the 2-to-1 condition is chosen uniformly at random. The
function is not known to the player, but the player has oracle access to
compute $f(x)$ for any $x\in\\{0,1\\}^{n}$. For classical players, oracle
access means that the player can send a query $x$ to the oracle and receive
$f(x)$ in return. For quantum players, we define a unitary $\mathcal{O}_{f}$
such that $\mathcal{O}_{f}\ket{x}\ket{a}=\ket{x}\ket{a\oplus f(x)}$. The
player performs a certain number of such oracle queries and arbitrary
classical computations and then guesses the hidden bitstring $b$. The
correctness of the guess is checked, and a new round begins, i.e., a new
function is chosen, and the game is repeated. The goal of the player is to
maximize the number of correct guesses using the smallest number of oracle
queries.

The rest of this section is devoted to specifying the details missing in the
simplified description above: the set of functions $f$, the mechanism to
access the oracle, and the exact formula used to score the player.

###  II.1 Set of functions $f$

We would like to design a game that is hard for a classical computer and easy
for a quantum computer. The classical complexity lower bound (see Section
III.1) is based on the assumption that the only information about $b$ that the
classical player can extract by evaluating $f$ at various points is the
presence or absence of a match $f(x)=f(y)$ for pairs of queries $(x,y)$. In
$\mathsf{w}_{{w}}\textnormal{Simon-}{n}$, the conditions are as follows: (i)
$\operatorname{HW}(b)\leq w$; (ii) $f(x)=f(y)$ if and only if $x=y$ or
$x=y\oplus b$; and (iii) $b\neq 0^{n}$. The function $f$ is then chosen
uniformly at random from the set of all functions that satisfy these
conditions. Such a broad class of functions $f$ may seem overly complicated,
but to illustrate the importance of this choice, consider an extreme
alternative: $b$ is chosen uniformly from all bitstrings that satisfy
conditions (i) and (iii), and $f(x)=\min(x,x\oplus b)$, where $\min$ yields
the first bitstring in lexicographic ordering. In this case, since
$f(1^{n})=1^{n}\oplus b$, we have $b=1^{n}\oplus f(1^{n})$. Therefore, the
classical player can find $b$ in a single query: $x=1^{n}$.

Unfortunately, choosing $f$ uniformly at random from the set of all functions
that meet conditions (i)–(iii) leads to a problem. To select a function we
need to pick its value for each pair of inputs $x$ and $x\oplus b$. There are
$2^{n-1}$ such pairs and $2^{n}$ possible outputs, all of which should be
different. One way to compute the number of such functions is to first pick
one of the $\binom{2^{n}}{2^{n-1}}$ subsets as the image of $f$ and then one
of the $(2^{n-1})!$ ways to map $2^{n-1}$ inputs to $2^{n-1}$ outputs, giving
the total number of functions $f$ for a fixed $b$ as
$\binom{2^{n}}{2^{n-1}}(2^{n-1})!=2^{n}!/(2^{n-1})!>2^{(n-1)2^{n-1}}$, which
means that the choice of $f$ requires at least $(n-1)2^{n-1}$ encoding bits.
One would thus expect exponentially many gates to be required to implement the
unitary quantum oracle $\mathcal{O}_{f}$ in a quantum circuit. Such large
circuits are infeasible on NISQ devices. To circumvent this problem, we
introduce the notion of a compiler that preserves the shallowness of the
quantum circuits implementing $\mathcal{O}_{f}$ but prevents making the
problem trivial by offloading all computations to classical post-processing.
The details of this compiler are given in Appendix A. The corresponding
Simon’s oracle construction is described in Appendix B.

###  II.2 Scoring

Any function $f$ satisfying (i)–(iii) can be decomposed as
$f(x)=f_{1}(f_{0}(x))$, where $f_{0}$ is any 2-to-1 function satisfying
condition (ii) with the same $b$, and $f_{1}$ is a permutation of bitstrings.
A uniformly random $f$ can be obtained by fixing $f_{0}=f_{0b}$ for every $b$,
then picking $b$ and $f_{1}$ uniformly at random. Since exponentially many
bits are required to record the permutation $f_{1}$, the program to compute
$f_{1}$ occupies exponential memory. If no caching is involved, this program
would need to be loaded into memory every time, which takes exponential time
in $n$. Thus, classical post-processing may easily remove most of the quantum
advantage. To circumvent this, we introduce a scoring function that only
accounts for the number of oracle queries and ignores the time needed for all
other steps of the protocol.

Given the goal of maximizing the number of correct guesses of $b$ while
minimizing the number of oracle queries, the players’ performance can be
measured in terms of the average score per query, which we denote by
$\mathrm{NTS}^{-1}$, where

$\mathrm{NTS}=\frac{\langle Q\rangle}{\langle P\rangle}.$ (1)

Here NTS denotes the _number-of-oracle-queries-to-solution_ ,
$\langle\bullet\rangle$ denotes the expectation value (which can be obtained
as an average over many rounds of the game), $Q$ is the number of oracle
queries, and $P$ is the score obtained in a round. The best player is the one
with the highest $\mathrm{NTS}^{-1}$.

Naively, one could set $P=1$ if the guess is correct and $P=0$ otherwise.
However, this would allow the players to use the following strategy. Let $N$
be the total number of options for $b$, and let $C$ be a constant satisfying
$N\geq C>0$. With probability $C/N$, the player executes a single query and
discards the result; otherwise, $0$ queries are executed. Then the player
guesses $b$ uniformly at random. The expected score is $1/N$, and the expected
number of queries is $C/N$. Thus, $\mathrm{NTS}=C$, and the player can make
$\mathrm{NTS}$ arbitrarily small (e.g., $\mathrm{NTS}=1$) by picking $C$ small
enough.

To avoid this, we introduce a penalty for incorrect guesses. Let $p_{r}=1/N$
be the probability of a random $b$ being correct. Then we set $P=1$ if the
guess is correct and $P=-p_{r}/(1-p_{r})$ otherwise. This ensures that the
randomly guessing player has $\langle P\rangle=p_{r}\times
1+(1-p_{r})\times[-p_{r}/(1-p_{r})]=0$ and $\mathrm{NTS}=\infty$.

To recap, we focus on counting the number of oracle calls for two main
reasons: (i) optimizations performed by the compiler may change the time
significantly, and (ii) the data generated by NISQ devices, contrary to
classical and ideal quantum algorithms, requires non-trivial post-processing,
which is likely to destroy any quantum speedup we might otherwise derive from
such devices.

##  III Classical and quantum algorithms

We now explain in detail the algorithms for the different variants of the
algorithm we consider: (i) classical, (ii) noiseless quantum, (iiia) NISQ, and
(iiib) NISQ without measurement errors, simulated using measurement error
mitigation (MEM).

We first comment briefly on the quantum variants. In the _noiseless quantum_
case, an ideal gate-based quantum computer executes the circuit the player
designs. Whether any compilation is performed is irrelevant to determining the
optimal score since such a compilation does not affect the number of oracle
calls or the probability distribution of the outcomes of the circuit execution
returned to the player. In the _NISQ_ case, we run the compiled circuit on a
NISQ device and, after post-processing, return the result to the player. The
score a player receives in this case depends not only on the player’s strategy
but also on the NISQ device used. In the _NISQ without measurement errors_
case, we run the circuit multiple times and use MEM to estimate the
probability distribution we would have obtained from a single run if
measurement errors were absent. Then we sample from that probability
distribution, apply the post-processing, and return the result to the player.

From the standpoint of the player, the procedure for implementing the ‘NISQ’
and ‘NISQ with MEM’ variants remains identical. This is due to MEM being
processed within the compiler, with the observer receiving solely the outcome,
presumed to incorporate measurement errors (NISQ) or devoid of such errors
(NISQ with MEM).

###  III.1 Classical algorithm

The original Simon’s problem can be solved using a classical deterministic
algorithm in $O(2^{n/2})$ queries Simon (1997); Cai and Qiu (2018). We present
a derivation of this result here and generalize it to the setting of the
$\mathsf{w}_{{w}}\textnormal{Simon-}{n}$ problem. For a simplified but less
rigorous derivation, see Appendix C.

Let $S$ be the set of all possible values for the hidden bitstring $b\neq
0^{n}$. The size of this set is $N_{n}\equiv 2^{n}-1$. Consider a classical
player querying bitstrings $x_{1},x_{2},\dots,x_{k}$ to get values
$y_{1},\dots,y_{k}$, where $y_{j}=f(x_{j})\in\\{0,1\\}$. Having made $m$
queries, the player forms the set $R_{m}=\\{x_{j}\oplus x_{l}\colon 1\leq
j<l\leq m\\}$. If $b\in R_{m}$, then $b=x_{j}\oplus x_{l}$ for some $j,l\leq
m$ and $y_{j}=y_{l}$. In this case, the player knows $b$ and their best
strategy is to output it without further queries to the oracle. Under the
assumption that $f$ is a uniformly random function satisfying conditions
(i)–(iii) discussed in Section II, if $b\notin R_{m}$, then the only
information learned after $m$ queries is that $b$ is not in $R_{m}$. Thus, the
player cannot benefit from adjusting the sequence of queried bitstrings based
on the learned information and can assume that the classical algorithm is
fully described by the sequence $x_{1},x_{2},\dots,x_{k}$. Finally, one can
check that the $\mathrm{NTS}$ cannot be improved by guessing prematurely.
Hence, for an optimal algorithm, the player should know $b$ after all $k$
queries, i.e., $S\setminus R_{k}$ should contain at most one element. On the
other hand, $\left|R_{k}\right|\leq k(k-1)/2$. I.e., $k$ should satisfy

$\frac{k(k-1)}{2}\geq N_{n}-1.$ (2)

We now consider $\mathsf{w}_{{n}}\textnormal{Simon-}{w}$, where the set $S$ of
possible values of $b$ is restricted by $\operatorname{HW}(b)=w<n$. The size
of this set is

$N_{w}\equiv\sum_{j=1}^{w}\binom{n}{j}.$ (3)

Let $S_{k}=S\cap R_{k}$. Similar to the above, if $b\notin S_{k}$, then this
is the only information about $b$ available to the player, i.e., their
posterior distribution of all possible values of $b$ is uniform in $S\setminus
S_{k}$. The player is guaranteed to know the correct $b$ iff $S\setminus
S_{k}$ contains at most one element, i.e., $\left|S_{k}\right|\geq N_{w}-1$,
but $\left|S_{k}\right|\leq\left|R_{k}\right|\leq k(k-1)/2$. Hence,

$\frac{k(k-1)}{2}\geq N_{w}-1.$ (4)

Solving Eq. 4 for $k$, we obtain a lower bound on the worst-case number of
queries needed by the classical player to solve
$\mathsf{w}_{{w}}\textnormal{Simon-}{n}$:

$k\geq\left\lceil\sqrt{2N_{w}-\frac{7}{4}}+\frac{1}{2}\right\rceil\equiv
k_{\min}(N_{w}),$ (5)

where, since this result is for a deterministic classical algorithm, it is
also a lower bound on the worst-case classical NTS.

Equation 1, however, involves not the worst-case but the average number of
queries $\langle Q\rangle$. The lower bound on the expected number of
classical queries $\langle Q_{C}\rangle$ needed to know $b$ exactly can be
obtained by summing the lower bounds on the probability $b\notin S_{i}$. Since
there are at most $i(i-1)/2$ elements in $S_{i}$, and the total number of
possible $b$ values is $N_{w}$, we have $\mathrm{Pr}(b\in
S_{i})\leq\frac{i(i-1)}{2N_{w}}$. The probability that the next query #$i+1$
is needed (i.e., that $i$ queries are not enough: $i=0,\dots,k-1$) is
$1-\mathrm{Pr}(b\in S_{i})$. Thus,

$\langle
Q_{C}\rangle\geq\sum_{i=0}^{k-1}\left(1-\frac{i(i-1)}{2N_{w}}\right)=k-\frac{k(k-1)(k-2)}{6N_{w}}.$
(6)

As mentioned above, guessing $b$ when it is unknown to the classical player
does not increase the $\mathrm{NTS}$; hence, the lower bound on the classical
NTS $\equiv\mathrm{NTS}_{C}={\langle Q_{C}\rangle}/{\langle
P_{C}\rangle}\geq{\langle Q_{C}\rangle}$ is given by the r.h.s. of Eq. 6.
Combining this with Eq. 5 gives

$\mathrm{NTS}_{C}\geq\mathrm{NTS}^{\text{lb}}_{C}(N_{w})\equiv
k_{\min}-\frac{k_{\min}(k_{\min}-1)(k_{\min}-2)}{6N_{w}}$ (7)

as the lower bound on the average case classical NTS.

Note that $\binom{n}{w}\leq N_{w}\leq\min(w\binom{n}{w},2^{n}-1)$. Thus, for
constant $w$ (independent of $n$), $N_{w}\sim n^{w}$, $k_{\min}\sim n^{w/2}$,
and Eq. 7 yields $\mathrm{NTS}_{C}\sim n^{w/2}$. Without restricting
$\operatorname{HW}(b)$, $\mathrm{NTS}_{C}=O(2^{n/2})$. However, with a fixed
upper limit $w$ on $\operatorname{HW}(b)$, $\mathrm{NTS}_{C}$ is polynomial
asymptotically (as $n\to\infty$).

Although Eq. 7 lower-bounds $\mathrm{NTS}_{C}$, there is no guarantee that the
player will find a sequence of bitstrings $x=\\{x_{1},x_{2},\dots,x_{k}\\}$
that achieves it. Nevertheless, henceforth we use the lower bound given by Eq.
7 as the metric for $\mathrm{NTS}_{C}$ because if the quantum algorithm
defeats this lower bound, the implication is an unequivocal quantum speedup.
In Appendix D, we derive an upper bound on $\mathrm{NTS}_{C}$ and discuss the
gap between the lower and upper bounds.

###  III.2 Noiseless quantum algorithm

$\ket{0}_{d_{0}}$$\ket{0}_{d_{n-1}}$$\ket{0}_{a_{0}}$$\ket{0}_{a_{n-1}}$$\vdots$$\vdots$$\mathcal{O}_{b}$$\vdots$$\vdots$
Figure 1: Quantum circuit for solving Simon’s problem with a length-$n$ hidden
bitstring $b$. The structure of the oracle $\mathcal{O}_{b}$ is not visible to
the player who wishes to guess $b$. The top $n$ measurement results form the
bitstring $z$, and the bottom $n$ measurement results are discarded in the
algorithm.

The original Simon-$n$ problem can also, in theory, be solved on a noiseless
quantum computer (QC). Figure 1 shows a quantum circuit that executes this
algorithm. The circuit uses $2n$ qubits for
$\mathsf{w}_{{w}}\textnormal{Simon-}{n}$; the first $n$ are data qubits,
labeled $d_{j}$, and the other $n$ are ancilla qubits, labeled $a_{j}$, where
$j=0,1,\dots,n-1$. The box $\mathcal{O}_{b}$ is the oracle whose action is
$f_{b}(x)$ on an input $x$, but its circuit is hidden from the players. Each
execution of the circuit produces a uniformly random $z$ such that $z\cdot
b=0$. The well-known proof that $O(n)$ executions of this circuit (on average)
on an ideal quantum computer are sufficient for solving Simon-$n$ is given in
Appendix E for completeness.

For our purposes, we need the $\mathrm{NTS}$ for the noiseless quantum
$\mathsf{w}_{{w}}\textnormal{Simon-}{n}$ problem, for arbitrary $w$. More
precisely, we need the $\mathrm{NTS}$ for an optimal, ideal quantum player
executing the circuit in Fig. 1 until $b\in S$ can be uniquely determined,
which we denote by $\mathrm{NTS}_{\textnormal{IQ}}$ for ‘ideal quantum’. To
obtain this, we first consider a generalization of the
$\mathsf{w}_{{w}}\textnormal{Simon-}{n}$ problem to the case where $b$ is
known to belong to some subset $S$ of
$\mathbb{Z}_{2}^{n}\setminus\\{0^{n}\\}$, and obtain
$\mathrm{NTS}_{\textnormal{IQ}}$ exactly in the two limits $w=1,\infty$, after
which we construct $\mathrm{NTS}_{\textnormal{IQ}}$ for arbitrary $1<w<\infty$
via interpolation.

######  Theorem 1.

If $\left|S\right|=1$ then $\mathrm{NTS}_{\textnormal{IQ}}=0$. If
$\left|S\right|\geq 2$ then

$\log_{2}\left|S\right|\leq\mathrm{NTS}_{\textnormal{IQ}}\leq\log_{2}(\left|S\right|-1)+2.$
(8)

For $\mathsf{w}_{{w}}\textnormal{Simon-}{n}$, we have $\left|S\right|=N_{w}$.
For Simon-$n$ (i.e., $\mathsf{w}_{{\infty}}\textnormal{Simon-}{n}$),
$\left|S\right|=2^{n}-1$ and

$\mathrm{NTS}_{\textnormal{IQ}}=\sum_{k=1}^{n-1}\frac{1}{1-2^{-k}}=n+E_{\textnormal{EB}}-1+O(2^{-n}),$
(9)

where $E_{\textnormal{EB}}=1.60669\dots$ is the Erdős -Borwein constant Sloane
(2001). For $\mathsf{w}_{{1}}\textnormal{Simon-}{n}$, $\left|S\right|=n$ and

$\mathrm{NTS}_{\textnormal{IQ}}=\log_{2}(n)+\frac{1}{2}+\frac{\gamma}{\ln(2)}+\chi(\log_{2}(n))+O\left(\frac{1}{n}\right),$
(10)

where $\gamma=0.57721\dots$ is the Euler-Mascheroni constant and $\chi$ is a
small ($\ll 1$) periodic function with mean $0$.

The proof is given in Appendix F. Numerically, we estimate the amplitude of
$\chi$ in Eq. 10 as $1.58\times 10^{-6}$.

We now construct the aforementioned interpolation. Let $t\equiv
N_{w}/(2^{n}-1)$; $t$ represents the density of $b$’s in the space of all non-
zero bitstrings. In Eq. 9 $t=1$ and in Eq. 10 $t$ approaches $0$. The
interpolation between Eqs. 9 and 10 is then:

$\mathrm{NTS}_{\textnormal{IQ}}(t)=\log_{2}(N_{w})+\left(\frac{1}{2}+\frac{\gamma}{\ln(2)}\right)(1-t)+(E_{\textnormal{EB}}-1)t.$
(11)

Appendix G demonstrates that this interpolation is an accurate estimate of the
actual $\mathrm{NTS}_{\textnormal{IQ}}$ for the
$\mathsf{w}_{{w}}\textnormal{Simon-}{n}$ problem when $1<w<\infty$.

###  III.3 NISQ algorithm

The ‘NISQ algorithm’ executes the circuit depicted in Fig. 1 on a NISQ device.
Recall that to determine the correct hidden bitstring $b$ in the context of a
noiseless quantum algorithm, it is necessary to acquire a set of $n-1$
independent measurements $z$, all of which satisfy the condition $z\cdot b=0$.
However, in the presence of noise, the measurement outcomes from the first $n$
qubits are expected to deviate from the noiseless case, potentially leading to
incorrect values for $z$. The likelihood of obtaining at least one incorrect
$z$ increases as the problem size $n$ increases, and given the prevailing
noise levels in current NISQ devices, the probability of encountering at least
one erroneous $z$ is high even for relatively small problem sizes.
Consequently, attempting to determine the parameter $b$ based solely on $n-1$
measurements is highly likely to yield an incorrect solution.

As a remedy, we employ a modified algorithm that requires $O(n)$ measurements,
thereby increasing the robustness of the determination of $b$. The algorithm
aims to identify a unique binary string $b^{\prime}$ by sampling bitstrings
$z$ and scoring each $b^{\prime}$ based on the condition $z\cdot
b^{\prime}=0$. While theoretically, $O(n)$ samples should suffice to determine
$b$, the algorithm samples $O(kn)$ bitstrings to mitigate errors in $z$, with
$k$ being a constant independent of $n$. Each sampled $z$ is tested against
all candidate $b^{\prime}$ strings, incrementing the score of $b^{\prime}$
that satisfies the dot product condition. After processing $kn$ samples, the
algorithm selects the $b^{\prime}$ with the highest score. In case of a tie,
additional $z$ samples are used until a single $b^{\prime}$ stands out. This
method is robust to noise, allowing for the correct $b$ to be discerned even
when some sampled $z$’s are corrupted, provided that the noise does not lead
to a uniform score distribution. For a complete description, see Appendix H.

We subject the outcomes from the ‘NISQ’ and ‘NISQ with MEM’ algorithms to
identical post-processing methodologies. The speedup comparison between the
classical and quantum algorithms uses the better of the outcomes observed
between these two quantum variants.

##  IV Quantum speedup quantified

In Section II.2, we motivated and defined the NTS metric, which we use to
compare the number of oracle queries for classical and NISQ solutions to
Simon’s problem. Instead of computing the NTS for all possible oracles
$\mathcal{O}_{f}$, or even for all $N_{w}$ values of $b$, we note that our
NISQ implementation for $\mathsf{w}_{{w}}\textnormal{Simon-}{n}$ depends only
on $n$, $w$, and the Hamming weight $\operatorname{HW}(b)=i$, which allows us
to focus only on $w\leq n$ instances of $b$: one representative $b$ for each
$i$. For full details, see the reduction method described in Appendix I.

Let $h_{i}={n\choose i}$ be the corresponding number of length-$n$ bitstrings
$b$ and let $Q_{i}$ be the corresponding total number of oracle queries; we
can write the number of queries for a given $i$ as $h_{i}Q_{i}$, and thus the
total number of queries per hidden bitstring as
$\langle{Q}\rangle=\sum_{i=1}^{n}h_{i}Q_{i}/N_{n}$. Let $p_{i}$ be the
probability of the correct guess for a representative bitstring $b$ with
$\operatorname{HW}(b)=i$. That is, $p_{i}$ is the fraction of successful
guesses of the representative $b$ based on the $Q_{i}$ oracle calls. Assuming
all $h_{i}$ bitstrings of fixed Hamming weight $i$ are guessed with the same
probability $p_{i}$, the total probability of successfully guessing all
weight-$i$ bitstrings is $h_{i}p_{i}$, and the expected overall probability of
success over all bitstrings is
$\langle{p}\rangle=\sum_{i=1}^{n}h_{i}p_{i}/N_{n}$. In the restricted
$\mathsf{w}_{{w}}\textnormal{Simon-}{n}$ version, since the player knows $w$,
a random guess succeeds with probability $p_{r}=1/N_{w}$, where $N_{w}$
replaces $N_{n}$. Then the average score (which includes the penalty for
incorrect guesses and was defined in Section II.2) can be written as
$\langle{P}\rangle=\langle{p}\rangle\times
1+(1-\langle{p}\rangle)\times[-p_{r}/(1-p_{r})]=\langle{p}\rangle-(1-\langle{p}\rangle)/(N_{w}-1)=\frac{1}{N_{w}-1}(N_{w}\langle{p}\rangle-1)$.
We can now express the quantum NTS for the unrestricted ($w=n$) or restricted
($w<n$) version of Simon’s problem as:

$\mathrm{NTS}_{Q}(n;w)=\frac{\langle{Q}\rangle}{\langle{P}\rangle}=\frac{N_{w}-1}{N_{w}}\frac{\sum_{i=1}^{w}h_{i}Q_{i}}{\sum_{i=1}^{w}h_{i}p_{i}-1}.$
(12)

Recall that we need to compare $\mathrm{NTS}_{Q}$ to the lower bound on the
average-case classical NTS, i.e., $\mathrm{NTS}^{\text{lb}}_{C}$ given by Eq.
7, which is a simple function of $k_{\min}(N_{w})$, the lower bound on the
worst-case classical NTS given by Eq. 5. Since $k_{\min}(N_{w})\sim
N_{w}^{1/2}$ for $N_{w}\gg 1$, it is more convenient to define the NTS scaling
with respect to $N_{w}$ than $n$.

We can now define an _algorithmic quantum speedup_ for the
$\mathsf{w}_{{w}}\textnormal{Simon-}{n}$ problem as a better scaling with
$N_{w}$ of the function $\mathrm{NTS}_{Q}$ [Eq. 12] than the function
$\mathrm{NTS}^{\text{lb}}_{C}$ [Eq. 7]. We determine the scaling by fitting
the following two-parameter model:

$\log_{2}\mathrm{NTS}_{x}=a_{x}\log_{2}{N_{w}}+c_{x},\quad x\in\\{Q,C\\},$
(13)

where $a_{x}$ is the scaling exponent. _An algorithmic quantum speedup is
observed when $a_{Q}<a_{C}$ for a fixed $w$_. The fitting parameter $c_{x}$
does not matter for scaling purposes.

Note that Eq. 13 relates two logarithmic quantities; hence, the quantum
speedup it quantifies is subexponential.

##  V Experimental Implementation

Our experiments were conducted using the $127$-qubit devices Sherbrooke
(ibm_sherbrooke) and Brisbane (ibm_brisbane), as well as the $27$-qubit
devices Cairo (ibm_cairo) and Kolkata (ibmq_kolkata), whose specifications are
detailed in Appendix J.

The quantum circuit for each hidden bitstring $b$ was constructed according to
Fig. 1, then compiled to fit the architecture of the devices using the as-
late-as-possible (ALAP) schedule. This schedule initializes each qubit just
before its first operation. We performed our experiments in two main modes:
(i) ‘with DD’, i.e., error-suppressed experiments with different dynamical
decoupling sequences, and (ii) ‘without DD,’ i.e., the circuit as specified in
Fig. 1 without any additional error suppression.

Figure 2: Circuit for Simon-3 ($b=111$) compiled into the Sherbrooke
architecture using the ALAP schedule. The XY4 DD sequences shown here as an
example are placed such that they fill all available idle spaces after each
qubit is initialized. Pulse intervals vary depending on the length of the idle
period. $\sqrt{}$ denotes the $\sqrt{X}$ gate. ECR denotes an echoed cross-
resonance gate, which is equivalent to a CNOT up to single-qubit rotations.

Figure 3: NTS as a function of $\log_{2}(N_{w})$ on Sherbrooke (top) for
$\mathsf{w}_{{6}}\textnormal{Simon-}{15}$ and Brisbane (bottom) for
$\mathsf{w}_{{5}}\textnormal{Simon-}{15}$, both with MEM. The red lines
represent the unprotected, no-DD form of the algorithm. The blue lines
represent the DD-protected form, i.e., a circuit where DD fills the idle gaps,
with the optimal DD sequence from $\mathcal{D}$ used at each problem size $n$.
The dashed lines connect the data points and the solid lines are least-squares
fits. The function in Eq. 13 is fitted for $n$ in the range $[2,15]$ for both
Sherbrooke and Brisbane. Uncertainties expressed using “$\pm$” in the legend
are the 95% confidence intervals. The error bars, representing confidence
intervals derived through bootstrapping, extend $5\sigma$ in both directions
from each data point. The yellow solid line represents
$\mathrm{NTS}^{\text{lb}}_{C}(N_{w})$, the lower bound on the classical NTS
[Eq. 7]. The yellow dotted lines with the same slope as the asymptotic slope
of the solid yellow line are a guide to the eye. The grey dashed line is the
theoretical performance of the quantum algorithm running on a noiseless
device, given by Eq. 11.

We use a pre-compiled quantum circuit aligned with the underlying device
architecture as our base circuit. The base circuit contains idle gap periods,
suitable for the integration of DD sequences. We incorporated one iteration of
a DD sequence into each idle gap, with the condition that if the duration of
the period is insufficient for sequence inclusion, the gap remains unoccupied
Pokharel and Lidar (2023). The spacing of DD pulses is contingent upon both
the length of the idle gap and the total number of pulses of the DD sequence.
The compiled Simon-$3$ circuit ($b=111$) is depicted in Fig. 2. The idle
intervals within this circuit are schematically populated with a $4$-pulse DD
sequence denoted by “P” in purple boxes.

We thoroughly examined a broad set of DD sequences: $\mathcal{D}=\\{$CPMG,
RGA2x, XY4, UR6, RGA8a, UR10, RGA16b, UR18, UR26, RGA32a, RGA32c,
UR${}_{32}\\}$. These sequences were selected from a comprehensive array of
sequences investigated in Ref. Ezzell  _et al._ (2023) on $1$-$5$ qubit IBMQ
devices, which includes detailed descriptions of these sequences and concluded
that sequence performance is highly device- and metric-dependent. Based on
these findings, our sequence-selection process involved iterative
experimentation, with smaller-scale trials conducted repeatedly to discern
sequences that, on average, exhibited superior performance compared to others.
We also investigated the crosstalk-robust sequences proposed in Ref. Zhou  _et
al._ (2023).

Certain sequences, such as URm Genov  _et al._ (2017) and RGAm Quiroz and
Lidar (2013), are families depending on a parameter $m$, which (roughly)
counts the number of pulses and the corresponding error suppression order; we
optimized over $m$ and chose the best-performing sequences for the final
experiment. The optimization procedure we used relies on the NTS metric.
Subsequently, circuits incorporating idle periods, each filled with a specific
sequence, were executed independently, and the corresponding NTS was computed.
The DD sequence exhibiting the lowest NTS was chosen for each problem size
$n$. Thus, our final results, discussed below, compare the unprotected ‘no-DD’
circuits with DD-protected circuits where the NTS was minimized for each $n$
separately over all the sequences in $\mathcal{D}$.

The results for all the sequences in $\mathcal{D}$, in support of our DD
sequence ranking methodology, are presented in Appendix K.

##  VI Results and Discussion

Our first main result is shown in Fig. 3, which plots the NTS as a function of
problem size $n$ for the $\mathsf{w}_{{6}}\textnormal{Simon-}{15}$
($\mathsf{w}_{{5}}\textnormal{Simon-}{15}$) problem run on the $127$-qubit
Sherbrooke (Brisbane) device. The measurement results were post-processed
using MEM before attempting to solve for $b$; see Appendix L for details. We
used bootstrapping to compute all means and standard deviations, as documented
in Appendix M. We found Sherbrooke to be the top-performing device for solving
Simon’s problem. The main difference between Sherbrooke and Brisbane pertinent
to the somewhat better performance of Sherbrooke in our experiments is its
much smaller $2$-qubit gate error: a mean of $0.02\%$ vs. $1\%$, respectively
(see Appendix J).

The fitted values $a_{x}$ where $x\in\\{\text{Q},\text{C}\\}$ as given in Eq.
13 are shown in the legend. In order to present the least biased result for
the quantum scaling, we report the _worst_ -case slope $a_{Q}$. We determine
this value as follows: we fit Eq. 13 for $n_{\min}\leq n\leq n_{\max}$ with
$n_{\min}\in[2,n_{\max}-1]$ and report the highest value of $a_{Q}$. We find
$n_{\min}=2$ in the DD-protected case for both Sherbrooke and Brisbane; see
Appendix N for details. We set $n_{\max}=15$ since the results for $n>15$ are
essentially random, as shown in Appendix O (additionally, MEM becomes
impractical for $n>15$ due to time and memory costs). From Fig. 3, we observe
that $a_{Q}=0.44\pm 0.01$ for $\mathsf{w}_{{6}}\textnormal{Simon-}{15}$ run on
Sherbrooke and $a_{Q}=0.43\pm 0.01$ for
$\mathsf{w}_{{5}}\textnormal{Simon-}{15}$ run on Brisbane, both subject to DD
protection, where the uncertainty represents $95\%$ confidence intervals. We
therefore declare a subexponential algorithmic quantum speedup for the DD-
protected $\mathsf{w}_{{w}}\textnormal{Simon-}{n}$ problem for $w=6$ on
Sherbrooke and $w=5$ on Brisbane.

Whether there is further evidence of an algorithmic quantum speedup is
determined by comparing $a_{C}$ and $a_{Q}$ over a range of $w$ values. This
brings us to our second main result, shown in Fig. 4, where we plot $a_{C}$
and $a_{Q}$ with and without DD, as a function of $w$. Numerical fitting of
the form displayed in Fig. 3 but extended to other values of $w$ shows that
$a_{C}$ quickly approaches approximately $0.5$, as expected from the classical
NTS and as remarked below Eq. 7. As is further clear from Fig. 4, the
algorithmic quantum speedup persists for the DD-protected
$\mathsf{w}_{{w}}\textnormal{Simon-}{n}$ problem for $w\leq 6$ on Sherbrooke
and $w\leq 5$ on Brisbane. The speedup becomes ambiguous at $w=7$ ($w=6$) on
Sherbrooke (Brisbane) and disappears for $w\geq 8$ ($w\geq 7$). Without DD, we
observe a speedup on both devices only for $w\leq 4$.

Figure 4: The fitted scaling parameter $a$ as a function of $w$ for
$\mathsf{w}_{{w}}\textnormal{Simon-}{15}$ on Sherbrooke (top) and Brisbane
(bottom), both with MEM. When the quantum slope is below the classical slope,
we declare an algorithmic quantum speedup. This holds with statistical
confidence for $w\leq 6$ ($w\leq 5$) on Sherbrooke (Brisbane). The error bars,
representing the standard deviation of the fitted parameter $a$ on the
bootstrapped data, extend $1\sigma$ in each direction from each data point.

Further analysis shows that the speedup does not extend to $w>7$ on Sherbrooke
or to $w>6$ on Brisbane, even with DD protection. Additional results for the
27-qubit devices Cairo and Kolkata are shown in Appendix P, for which we do
not find evidence of a speedup.

The speedup we find for the $\mathsf{w}_{{w}}\textnormal{Simon-}{15}$ problem
involves $30$ physical qubits. The previously reported algorithmic quantum
speedup result for the single-shot Bernstein-Vazirani problem extended to $27$
physical qubits and used the $27$-qubit Montreal processor Pokharel and Lidar
(2023). Our present result thus increases both the number of physical qubits
for which an algorithmic quantum speedup has been reported and the complexity
of the quantum algorithm for which the result holds.

##  VII Summary and Conclusions

The goal of demonstrating an algorithmic quantum speedup, i.e., a quantum
speedup that scales favorably as the problem size grows, is central to
establishing the utility of quantum computers. Simon’s problem is an early
example of the Abelian hidden subgroup problem and a precursor to Shor’s
factoring algorithm. It requires exponential time to solve on a classical
computer but only linear time on a noiseless quantum computer, assuming we
count oracle queries but do not account for the actual resources spent on
executing the oracle. Here, we studied a modified version of Simon’s problem,
which restricts the allowed Hamming weight of the hidden bitstring to $w\leq
n$. The classical solution of this version scales as $n^{w/2}$. Our goal was
to determine whether NISQ devices are capable of providing an algorithmic
quantum speedup in solving this version of Simon’s problem.

We ran restricted-HW Simon’s algorithm experiments on the IBM Quantum platform
and demonstrated that two $127$-qubit devices, Sherbrooke and Brisbane,
exhibit an algorithmic quantum speedup, which extended to larger HW values
when we incorporated suitably optimized DD protection. MEM further enhanced
the speedup.

These results significantly extend the scope of conjecture-free algorithmic
quantum speedups for oracular algorithms. More generally, our work expands the
frontier of empirical quantum advantage results and suggests that algorithmic
quantum speedup results involving practically relevant algorithms may also be
within reach.

##  VIII Acknowledgements

We thank Bibek Pokharel for useful discussions. This research was supported by
the ARO MURI grant W911NF-22-S-0007 and is based in part upon work supported
by the National Science Foundation the Quantum Leap Big Idea under Grant No.
OMA-1936388. This material is also based upon work supported by the Defense
Advanced Research Projects Agency (DARPA) under Contract No. HR001122C0063. ZZ
and GQ acknowledge funding from the U.S. Department of Energy (DOE), Office of
Science, Office of Advanced Scientific Computing Research (ASCR), Accelerated
Research in Quantum Computing program under Award Number DE-SC0020316. This
research used resources of the Oak Ridge Leadership Computing Facility, which
is a DOE Office of Science User Facility supported under Contract DE-
AC05-00OR22725.

##  Appendix A Compiler

We explained in Section II.1 that even for a fixed $b$ the choice of $f$
requires at least $(n-1)2^{n-1}$ encoding bits, leading to infeasibly deep
circuits for NISQ devices. To circumvent this problem, we introduce the notion
of a compiler that performs the following functions: (i) it hides the
implementation details of $f$ from the player; (ii) it takes a circuit $C$
with $0$ or more boxes labeled “$\mathcal{O}$” and produces a circuit
$C^{\prime}$ obtained from $C$ by replacing each $\mathcal{O}$ box with a
circuit implementing it for the current $f$; (iii) further compiles
$C^{\prime}$ to ensure that it is compatible with the gate set and
connectivity of the NISQ device, to reduce the number of gates and the circuit
depth, and to select the best layout of the qubits on the device (i.e.,
avoiding the noisiest qubits and couplings), yielding a new circuit
$C^{\prime\prime}$ and classical post-processing instructions; (iv) sends
$C^{\prime\prime}$ to the NISQ device for execution, obtains the result,
performs the post-processing, and returns the final result to the player. Note
that in (ii), “$\mathcal{O}$” is just a box labeling a place to insert the
oracle (which is unknown to the player), as opposed to $\mathcal{O}_{f}$,
which is the unitary implementing the actual oracle.

$\ket{0}^{\otimes n}$$\ket{0}^{\otimes n}$$H^{\otimes
n}$$\mathcal{O}$$H^{\otimes n}$$z$$a$ $x$$a$$\ket{0}^{\otimes n}$$\oplus
f_{0}(x)$$f_{1}$$f_{1}^{-1}$$\oplus f_{0}(x)$$\ket{0}^{\otimes n}$$x$$a$

$\ket{0}^{\otimes n}$$\ket{0}^{\otimes n}$$H^{\otimes n}$$\oplus
f_{0}(x)$$H^{\otimes n}$$z$$a$ Figure 5: (a) The intended circuit $C$. The
thick wires indicate that each wire represents $n>1$ qubits. $H$ denotes a
Hadamard gate and $\mathcal{O}$ denotes the oracle. (b) Circuit implementing
the oracle $\mathcal{O}_{f}$ for arbitrary $f$ satisfying the conditions
(i)–(iii). Any such $f$ can be decomposed as $f(x)=f_{1}(f_{0}(x))$, where
$f_{0}$ is any 2-to-1 function satisfying condition (ii) with the same $b$,
and $f_{1}$ is a permutation of bitstrings. All gates are classical in the
sense that if the input $\ket{x,a}$ consists of a single computational basis
state (with amplitude $1$), so does the output. The circuit for $f_{1}$ may
need 3-qubit gates and ancillary qubits. The unitary controlled-($\oplus
f_{0}(x)$) maps a computational basis element $\ket{x}\ket{a}$ to
$\ket{x}\ket{a\oplus f_{0}(x)}$. The gate sequence shown is one possible
implementation of $\mathcal{O}_{f}$: the circuit prepares $f(x)$ on a third
$n$-qubit register, performs a CNOT with the $a$ register as the target, and
uncomputes the third register to return it to the $\ket{0}$ state. (c)
Compiled circuit. This circuit is equivalent to the unoptimized circuit shown
in (a) and (b), assuming $f_{1}$ is applied to $a$ in post-processing (such
optimization is allowed by the rules).

When defining these rules, we need to be careful about the optimizations
allowed in step (iii): if we allow too few, the circuit $C^{\prime\prime}$ may
be too large to be executed with reasonable fidelity; if we allow too many,
$C^{\prime\prime}$ may become a no-op and all computations will be performed
by classical post-processing.

To understand the rules we choose, consider the intended circuit $C$ and the
circuit $\mathcal{O}_{f}$ implementing the oracle, shown in Fig. 5(a) and Fig.
5(b), respectively. To see why Fig. 5(b) implements the oracle, note first
that any $f$ satisfying conditions (i)-(iii) can be written as
$f(x)=f_{1}(f_{0}(x))$. To verify the circuit, it suffices to ensure that it
works as intended on computational basis states, i.e., it maps
$\ket{x}\ket{a}$ to $\ket{x}\ket{a\oplus f_{1}(f_{0}(x))}$. As is easily
verified, the list of states along the computation is
$\ket{x}\ket{a}\mapsto\ket{x}\ket{a}\ket{0}^{\otimes
n}\mapsto\ket{x}\ket{a}\ket{f_{0}(x)}\mapsto\ket{x}\ket{a}\ket{f_{1}(f_{0}(x))}\mapsto\ket{x}\ket{a\oplus
f_{1}(f_{0}(x))}\ket{f_{1}(f_{0}(x))}\mapsto\ket{x}\ket{a\oplus
f_{1}(f_{0}(x))}\ket{f_{0}(x)}\mapsto\ket{x}\ket{a\oplus
f_{1}(f_{0}(x))}\ket{0}^{\otimes n}\mapsto\ket{x}\ket{a\oplus
f_{1}(f_{0}(x))}$, as required.

Before formulating the rules below, we introduce the notion of classical
gates. We say that a gate is classical if it maps computational basis states
(with amplitude $1$) to computational basis states. In particular, $X$, CNOT,
and the Toffoli (CCNOT) are classical, but $Y$, $Z$, and $H$ are not.
Performing a classical gate immediately before the measurement in the
computational basis is equivalent to performing the measurement first and then
applying the equivalent classical post-processing.

Based on this, we state the following rules for the compiler: (1) it can
perform a joint optimization of $C^{\prime}$, that is, it does not have to
preserve the separation between the gates inside and outside
$\mathcal{O}_{f}$; (2) it can perform any optimization that does not change
the output distribution of $C^{\prime}$ if it were executed on an ideal
quantum computer; (3) it can replace classical gates before the measurement
with the equivalent classical post-processing; (4) rules #2 and #3 can be
applied any number of times in any order.

With these rules, we expect the compiler to be able to compile the circuit in
Fig. 5(a) with $\mathcal{O}_{f}$ from Fig. 5(b) into the circuit
$C^{\prime\prime}$ as shown in Fig. 5(c). Moreover, we expect that the qubits
of the $x$ and $a$ registers will be reordered such that circuits with the
same $\operatorname{HW}(b)$ will be compiled into the same circuit. The
application of $f_{1}$ and the inverse of the qubit reordering will be done by
classical post-processing. Note that Fig. 1 is an expanded version of Fig. 5.

##  Appendix B Simon’s oracle construction

Although the structure of the oracle is not known to the player who wishes to
solve Simon’s problem, someone needs to play the role of the ‘verifier’ who
acts like a referee, that is, construct the oracle for the player and verify
whether the player’s guess is correct. The verifier needs to know the
structure of the quantum oracle $f_{b}$ in order to construct the quantum
circuit for each hidden bitstring $b$. Since it is a Clifford circuit, the
oracle presented below can be efficiently simulated by a classical computer.
However, this does not destroy the claimed speedup because our setting assumes
the ‘black box’ scenario Zantema (2022), i.e., the players are not allowed to
know the structure of the oracle and solve the problem in linear time by
classically constructing the oracle on their own.

Before presenting it, we remark that our oracle construction is not unique; it
only needs to satisfy the condition specified by Simon’s problem, i.e.,
$\forall x,y\in\\{0,1\\}^{n}$, $f_{b}(x)=f_{b}(y)$ if and only if $x=y$ or
$x=y\oplus b$ for a hidden bitstring $b\in\\{0,1\\}^{n}$.

To aid in visualization, we will interchangeably use quantum circuits and
directed graphs to represent the oracle. This is useful because the oracle
circuit consists entirely of CNOT gates, which can be represented as arrows
from the controlled qubit to the target qubit. Fig. 6 shows an example of how
to transform between the two representations. The data ($d_{j}$) and ancilla
($a_{j}$) qubits are drawn in the first and second columns in the graph
representation, respectively.

$\ket{d_{0}}$$\ket{d_{1}}$$\ket{a_{0}}$$\ket{a_{1}}$$\Leftrightarrow$$d_{0}$$d_{1}$$a_{0}$$a_{1}$
Figure 6: Conversion between a pure-CNOT circuit and its graph representation.
A CNOT gate is an arrow from the controlled to the target qubit.

Two operations are used to construct the oracle: classical copy and classical
addition modulo 2. Both are classical operations executed by quantum devices.

  * •

Classical copy: This operation copies a classical state from a 1-qubit
register into another 1-qubit register. Fig. 7 shows an example of copying
$\ket{d_{0}d_{1}}$ into the ancilla qubits $\ket{a_{0}a_{1}}$, which are
initialized as $\ket{00}$.

$\ket{d_{0}}$$\ket{d_{1}}$$\ket{0}$$\ket{0}$$d_{0}$$d_{1}$$a_{0}$$a_{1}$
Figure 7: A quantum circuit for the operation
$\ket{d_{0}d_{1}}\ket{00}\mapsto\ket{d_{0}d_{1}}\ket{d_{0}d_{1}}$.
$d_{0},d_{1},a_{0},a_{1}\in\\{0,1\\}$.

  * •

Classical XOR: This operation performs the XOR (single-digit addition modulo
2) between two 1-qubit registers and stores the result in another 1-qubit
register. Fig. 8 shows an example of adding $\ket{d_{0}d_{1}}$ and storing the
result in the first ancilla qubit $\ket{a_{0}}$, which is initialized as
$\ket{0}$.

$\ket{d_{0}}$$\ket{d_{1}}$$\ket{0}$$\ket{0}$$d_{0}$$d_{1}$$a_{0}$$a_{1}$
Figure 8: A quantum circuit that applies the operation
$\ket{d_{0}d_{1}}\ket{00}\mapsto\ket{d_{0}d_{1}}\ket{d_{0}\oplus d_{1},0}$.
$d_{0},d_{1},a_{0},a_{1}\in\\{0,1\\}$.

Next, we show how to construct a 2-to-1 oracle. We represent a length-$n$
bitstring $x=x_{0}\cdots x_{n-1}$, where $x_{j}\in\\{0,1\\}$, and use an
oracle that transforms $\ket{x}\ket{0}\rightarrow\ket{x}\ket{f_{b}(x)}$ when
$b=0^{n-i}1^{i}$. For each $b$ of this form,
$f_{b}:\\{0,1\\}^{n}\mapsto\\{0,1\\}^{n}$ is defined as follows:

$\displaystyle f_{b}(x)=(x_{0},\cdots,x_{n-i-1},0,x_{n-i+1}\oplus
x_{n-i},\cdots,x_{n-1}\oplus x_{n-i})$ (14)

for $1\leq i\leq n$.

Equivalently, we can write this transformation as

$\displaystyle\ket{x_{0}\cdots x_{n-1}}_{d}\ket{0^{n}}_{a}\mapsto$ (15)
$\displaystyle\ket{x_{0}\cdots x_{n-1}}_{d}\ket{x_{0}\cdots
x_{n-i-1}0(x_{n-i}\oplus x_{n-i+1})\cdots(x_{n-i}\oplus x_{n-1})}_{a}.$

The following Lemmas show that $f_{b}(x)$ is a valid family of oracles for
Simon’s problem.

######  Lemma 1.

$f_{b}(x)=f_{b}(y)$ if and only if $x=y$ or $y=x\oplus b$, where
$b=0^{n-i}1^{i}$, $1\leq i\leq n$. I.e., $f_{b}(x)$ is a 2-to-1 function.

###### Proof.

Consider two ancilla registers containing the output from two different inputs
$x$ and $y$. According to Eq. 15, we can write $f_{b}(x)$ and $f_{b}(y)$ as

$\displaystyle\ket{f_{b}(x)}$ $\displaystyle=\ket{x_{0}\cdots
x_{n-i-1}0(x_{n-i}\oplus x_{n-i+1})\cdots(x_{n-i}\oplus x_{n-1})}$ (16)
$\displaystyle\ket{f_{b}(y)}$ $\displaystyle=\ket{y_{0}\cdots
y_{n-i-1}0(y_{n-i}\oplus y_{n-i+1})\cdots(y_{n-i}\oplus y_{n-1})}.$

($\Rightarrow$) If $x=y$ or $y=x\oplus b$, then $f_{b}(x)=f_{b}(y)$: The
statement is trivial when $x=y$. We explicitly write $b=0_{0}\cdots
0_{n-i-1}1_{n-i}\cdots 1_{n-1}$, so that $\\{y_{0}\cdots
y_{n-i-1}\\}=\\{x_{0}\cdots x_{n-i-1}\\}$ and $\\{y_{n-i+1}\cdots
y_{n-1}\\}=\\{x_{n-i+1}\oplus 1\cdots x_{n-1}\oplus 1\\}$. It follows from Eq.
14 that trivially $f_{b}(y_{j})=f_{b}(x_{j})$ for $j\leq n-i$ and that for
$j\geq n-i+1$, $f_{b}(y_{j})=y_{n-i}\oplus y_{j}=(x_{n-i}\oplus
1)\oplus(x_{j}\oplus 1)=x_{n-i}\oplus x_{j}=f_{b}(x_{j})$.

($\Leftarrow$) If $f_{b}(x)=f_{b}(y)$, then $x=y$ or $y=x\oplus b$: The
calculation in the ‘$\Rightarrow$’ part of the proof shows that
$f_{b}(y)=f_{b}(x)$ if $y=x\oplus b$; therefore, $f_{b}^{-1}(x)$ outputs $x$
and $x\oplus b$ and likewise, $f_{b}^{-1}(y)$ outputs $y$ and $y\oplus b$.
Hence, $f_{b}(x)=f_{b}(y)$ implies that either (1) $x=y$ and $x\oplus
b=y\oplus b$, or (2) $x=y\oplus b$ and $x\oplus b=y$. Case (1) corresponds to
$x=y$ and case (2) corresponds to $y=x\oplus b$.

The conclusion that $f_{b}(x)$ is a 2-to-1 function now follows directly. ∎

Having shown that $f_{b}$ as defined in Eq. 14 and written explicitly in Eq.
15 is a valid oracle for Simon’s problem, we proceed to construct its quantum
version using classical copy (for the first $n-i$ positions) and classical XOR
(for the last $i$ positions). The $a_{n-i}$ qubit remains in the $\ket{0}$
state, hence no operation is required.

To construct the first $n-i$ positions in Eq. 15, one needs to copy the state
in $d_{0},\dots,d_{n-i-1}$ into $a_{0},\dots,a_{n-i-1}$. The quantum operation
for this is a CNOT from each qubit $d_{j}$ of the data register (controlled
qubit) to the corresponding qubit $a_{j}$ in the ancilla register (target
qubit), as shown in Fig. 7.

To construct the last $i$ positions in Eq. 15, one needs to perform XOR on
$d_{n-i}$ and $d_{j}$ from the data register and store the result in the qubit
$a_{j}$ in the ancilla register. Two CNOTs are required from two controlled
qubits, $d_{n-i}$ and $d_{j}$, onto the same target qubit $a_{j}$, similarly
to what is shown in Fig. 8.

We can construct an oracle for a Simon-$n$ problem using this method. Where to
apply classical copy or classical XOR depends on the hidden bitstring
$b=0^{n-i}1^{i}$: a $0$ is an instruction to copy, while a $1$ is an
instruction to perform an XOR. Fig. 9 shows an example of combining these two
types of operators to construct an oracle for Simon-3 with $b=011$. Fig. 10
shows an example of Simon-5 in the graph representation. An example of the
full quantum circuit to solve a Simon-3 problem with $b=011$ is given in Fig.
11.

$\ket{d_{0}}$$\ket{d_{1}}$$\ket{d_{2}}$$\ket{a_{0}}$$\ket{a_{1}}$$\ket{a_{2}}$$+$$d_{0}$$d_{1}$$d_{2}$$a_{0}$$a_{1}$$a_{2}$
Figure 9: Construction of an oracle for solving the Simon-3 problem with
$b=011$ according to Eq. 15. The first (second) part in the dashed (solid) box
applies classical copy (XOR), corresponding to the $0$’s ($1$’s) in $b$.
$d_{0}$$d_{1}$$d_{2}$$d_{3}$$d_{4}$$a_{0}$$a_{1}$$a_{2}$$a_{3}$$a_{4}$$d_{0}$$d_{1}$$d_{2}$$d_{3}$$d_{4}$$a_{0}$$a_{1}$$a_{2}$$a_{3}$$a_{4}$$d_{0}$$d_{1}$$d_{2}$$d_{3}$$d_{4}$$a_{0}$$a_{1}$$a_{2}$$a_{3}$$a_{4}$$d_{0}$$d_{1}$$d_{2}$$d_{3}$$d_{4}$$a_{0}$$a_{1}$$a_{2}$$a_{3}$$a_{4}$$d_{0}$$d_{1}$$d_{2}$$d_{3}$$d_{4}$$a_{0}$$a_{1}$$a_{2}$$a_{3}$$a_{4}$$b=0^{4}1^{1}$$b=0^{3}1^{2}$$b=0^{2}1^{3}$$b=0^{1}1^{4}$$b=0^{0}1^{5}$
Figure 10: Oracle construction for Simon-5 in the graph representation. Using
the reduction procedure, we can remove the dashed boxes to arrive at
Simon-$m$, where $m<5$.
$\ket{0}_{d_{0}}$$\ket{0}_{d_{1}}$$\ket{0}_{d_{2}}$$\ket{0}_{a_{0}}$$\ket{0}_{a_{1}}$$\ket{0}_{a_{2}}$
Figure 11: The quantum circuit to solve the Simon-3 problem with $b=011$,
which can be extracted from the dashed ($d_{2},a_{2}$) box and the lowermost
solid box in Simon-5 with $b=0^{3}1^{2}$.

##  Appendix C Alternative derivation of the classical complexity of Simon’s
problem

An alternative derivation of the classical complexity of Simon’s problem can
be given in the spirit of the birthday paradox. Given any input bitstring pair
$x_{i}\neq x_{j}$ such that $f_{b}(x_{i})=f_{b}(x_{j})$ (a collision), we have
the solution to Simon’s problem: $b=x_{i}\oplus x_{j}$. In the worst case,
excluding the $0^{n}$ string, it takes $k_{\max}=2^{n-1}$ strings to find a
collision. But suppose we pick $k<k_{\max}$ strings at random. There are
${k\choose 2}=k(k-1)/2$ pairs. Given a random string $x_{i}$, we can pick a
second random string $x_{j}$, and $x_{j}\neq 0^{n},x_{i}$ with probability
$1/(N_{n}-1)$, where $N_{n}=2^{n}-1$. This is also the probability of a
collision between $x_{i}$ and $x_{j}$. Therefore

$\mathrm{Pr}[f_{b}(x_{i})=f_{b}(x_{j})]=\frac{{k\choose 2}}{N_{n}-1},\quad
i\neq j.$ (17)

Setting $\mathrm{Pr}[f_{b}(x_{i})=f_{b}(x_{j})]=1$ guarantees a collision.
Solving for $k$, the required number of queries $k$ in Eq. 17 is $O(2^{n/2})$.

The classical complexity is affected by the change of the total number of
possible $b$’s from $N_{n}$ to $N_{w}=\sum_{j=1}^{w}{n\choose j}$ in
$\mathsf{w}_{{w}}\textnormal{Simon-}{n}$. Hence, Eq. 17 becomes:

$\mathrm{Pr}[f_{b}(x_{i})=f_{b}(x_{j})]=\frac{{k\choose 2}}{N_{w}-1}.$ (18)

By setting $\mathrm{Pr}[f_{b}(x_{i})=f_{b}(x_{j})]\geq 1$, we assume that a
collision is not found until all bitstring pairs have been tested, which
yields the worst-case number of classical queries (for the best possible
classical algorithm), and we recover Eq. 5.

##  Appendix D Upper bound on $\mathrm{NTS}_{C}$

As remarked in the main text, there is no guarantee that the player will find
a sequence of bitstrings $x=\\{x_{1},x_{2},\dots,x_{k}\\}$ that achieves the
lower bound on $\mathrm{NTS}_{C}$ given by Eq. 7. For Eq. 6 to be an equality,
all values of $x_{l}\oplus x_{m}$ should be different and satisfy
$\operatorname{HW}(x_{l}\oplus x_{m})\leq w$ for $1\leq l<m\leq k$. To find an
upper bound on $\mathrm{NTS}_{C}$, we consider an arbitrary sequence
$x_{1},\dots,x_{k}$ of bitstrings that a classical player intends to submit to
the oracle. Without loss of generality, we can assume that this sequence is
independent of the oracle replies unless a match $f(x_{j})=f(x_{l})$ is found
for $j<l\leq k$ (in which case the classical player stops and returns
$b=x_{j}\oplus x_{l}$). We can also assume that

$\left|S\setminus S_{j}\right|\leq 1\Leftrightarrow j=k.$ (19)

If Eq. 19 is not satisfied for $j=k$, the classical algorithm fails to find
$b$ for $b\in S\setminus S_{k}$, and if Eq. 19 is satisfied for $j<k$, we can
set $k$ to the smallest such $j$. Equation 19 can be seen as an exact version
of Eq. 5: it ensures that $k$ is the worst-case classical number of queries of
an algorithm described by the sequence $x$. For $x$ satisfying Eq. 19, we can
compute the NTS exactly:

$\mathrm{NTS}_{C}(x)=\sum_{i=0}^{k-1}\left(\frac{|S\setminus
S_{i}|}{|S|}\right)=\sum_{i=0}^{k-1}\left(1-\frac{|S_{i}|}{|S|}\right),$ (20)

which is the exact version of Eq. 6. Then

$\mathrm{NTS}_{C}=\min_{x:\
\mathrm{\lx@cref{creftype~refnum}{eq:k-def}}}\mathrm{NTS}_{C}(x).$ (21)

We do not know a method to find this minimum exactly for $n\geq 10$ because,
as $n$ grows, the search space involves sequences of $k$ bitstrings, where $k$
grows exponentially with $n$, i.e., the search space size grows as
$2^{n2^{n/2}}$ for the original Simon’s problem and as
$2^{n\sqrt{\binom{n}{w}}}$ for $\mathsf{w}_{{w}}\textnormal{Simon-}{n}$ with
constant $w$, which is infeasible already for $n=10$, $w=6$. We circumvent
this problem using a heuristic search for larger $n$. If we could show that
the sequence $x$ we found using a heuristic search minimizes Eq. 21, then we
would be able to claim that we found the exact value of $\mathrm{NTS}_{C}$. In
practice, we cannot show this for all but the few smallest values of $n$,
hence can only claim that $\mathrm{NTS}_{C}\leq\mathrm{NTS}_{C}(x)$.

The solution we compute for Eq. 21 from a heuristic search serves as the upper
bound for $\mathrm{NTS}_{C}$, while Eq. 7 represents its lower bound. We
selected the latter when contrasting the slope parameters $a_{Q}$ and $a_{C}$.
This ensures that the quantum algorithm’s performance surpasses the lower
threshold of its classical counterpart, guaranteeing a quantum scaling
advantage if achieved.

In larger problem sizes where the upper and lower bounds do not align, the
actual $\mathrm{NTS}_{C}$ lies somewhere between the two. The discrepancy
between the theoretical lower bound in Eq. 7 and the heuristic upper bound in
Eq. 21 is depicted in Fig. 12 for $\mathsf{w}_{{5}}\textnormal{Simon-}{n}$ and
$\mathsf{w}_{{6}}\textnormal{Simon-}{n}$ from $n=2$ to $n=15$.

Figure 12: Difference between the upper bound (UB) and lower bound (LB) of
$\mathrm{NTS}_{C}$ and the corresponding slope parameter $a$ for $w=5$ and
$w=6$. We use the LB slope in the quantum speedup analysis.

##  Appendix E Solving Simon-$n$ in $O(n)$ oracle queries on a noiseless QC

We prove that the circuit in Fig. 1 solves Simon’s problem in $O(n)$ oracle
queries, assuming that it is run on a noiseless QC. Starting from the left of
Fig. 1, every qubit is initialized in the all-zero state
$\ket{\psi_{0}}=\ket{0}^{\otimes n}\ket{0}^{\otimes n}$, and the first $n$
Hadamard gates put every data qubit into a uniform superposition:

$\ket{\psi_{1}}=H^{\otimes
n}\ket{\psi_{0}}=\frac{1}{\sqrt{2^{n}}}\sum_{x\in\\{0,1\\}^{n}}\ket{x}\ket{0}^{\otimes
n}.$ (22)

Next, for an input $x$, the oracle $\mathcal{O}_{b}$ outputs $f_{b}(x)$ stored
in the ancilla register, where $f_{b}(x)=f_{b}(y)$ if and only if $y=x$ or
$y=x\oplus b$,

$\ket{\psi_{2}}=\mathcal{O}_{b}\ket{\psi_{1}}=\frac{1}{\sqrt{2^{n}}}\sum_{x\in\\{0,1\\}^{n}}\ket{x}\ket{f_{b}(x)}.$
(23)

The ancilla qubits are then measured in the computational basis, an operation
denoted by $M_{a}^{\otimes n}$. The result could be any $f_{b}(x)$ where
$x\in\\{0,1\\}^{n}$ with equal probability, which is then discarded. The
remaining state in the data register is

$\ket{\psi_{3}}=M_{a}^{\otimes
n}\ket{\psi_{2}}=\frac{1}{\sqrt{2}}(\ket{x}+\ket{x\oplus b}).$ (24)

Applying the last set of Hadamard gates on the data qubits, we have

$\displaystyle\ket{\psi_{b}}$ $\displaystyle=H^{\otimes n}\ket{\psi_{3}}$
(25a)
$\displaystyle=\frac{1}{\sqrt{2^{n+1}}}\sum_{z\in\\{0,1\\}^{n}}[(-1)^{x\cdot
z}+(-1)^{(x\oplus b)\cdot z}]\ket{z}$ (25b)
$\displaystyle=\frac{1}{\sqrt{2^{n-1}}}\sum_{\\{z|z\cdot b=0\\}}(-1)^{x\cdot
z}\ket{z},$ (25c)

where the last line arises from the fact that the element in the sum vanishes
when $x\cdot z\neq(x\oplus b)\cdot z$. The remaining terms must have $x\cdot
z=(x\oplus b)\cdot z$, which reduces to $z\cdot b=0,\forall x$.

##  Appendix F Proof of 1

###### Proof.

The $\left|S\right|=1$ case is trivial. To prove the lower bound in Eq. 8,
consider the situation after $k$ executions of the circuit. It is known that
$b$ is uniformly distributed in some subset $S_{k}$ of $S$ (e.g., $S_{0}=S$).
Let $B_{k}$ be the random variable representing the value of $b$ and $Z_{k}$
be the random variable representing the value of $z$ obtained from the
$k+1$’th execution of the circuit. Then the information gain about $B_{k}$
from $Z_{k}$ is given by their mutual information
$I(B_{k};Z_{k})=H(B_{k})+H(Z_{k})-H(B_{k},Z_{k})$, where $H$ is the Shannon
entropy. We have $H(B_{k})=\log_{2}\left|S_{k}\right|$, $H(Z_{k})\leq n$, and
$H(B_{k},Z_{k})=(n-1)+\log_{2}\left|S_{k}\right|$ [because $(B_{k},Z_{k})$ is
uniformly distributed across $\left|S_{k}\right|2^{n-1}$ pairs $(b,z)$: for
each $b$ there are $2^{n-1}$ options for $z$ (the ones satisfying $b\cdot
z=0$)]. Hence $I(B_{k};Z_{k})\leq 1$, and it follows that
$\mathrm{NTS}_{\textnormal{IQ}}\geq\log_{2}\left|S\right|$: we learn at most
$1$ bit of information in every step and we need to learn
$\log_{2}\left|S\right|$ bits.

To prove the upper bound in Eq. 8, let $b^{*}$ be the true (hidden) value of
$b$ and let $S^{*}=S\setminus\\{b^{*}\\}$. For each $b\in S^{*}$ let $X_{b}$
be the random variable representing the number of circuit executions needed to
learn that $b^{*}\neq b$. Since upon each circuit execution $z$ is uniformly
distributed among all $z$ s.t. $z\cdot b^{*}=0$, we know that $X_{b}$ is
geometrically distributed: $\mathrm{Pr}(X_{b}=k)=2^{-k}$ for $k\geq 1$. Let
$X_{\textnormal{max}}=\max_{b\in S^{*}}X_{b}$. Then

$\mathrm{Pr}(X_{\textnormal{max}}=k)\leq\sum_{b\in
S^{*}}\mathrm{Pr}(X_{b}=k)=(\left|S\right|-1)2^{-k},$ (26)

which implies $\mathrm{Pr}(X_{\textnormal{max}}\geq
k)\leq(\left|S\right|-1)2^{1-k}$. Now, let
$a=\left\lfloor{\log_{2}(\left|S\right|-1)}\right\rfloor$ and let $b$ be the
fractional part of $\log_{2}(\left|S\right|-1)$ so that
$\left|S\right|-1=2^{a+b}$. We have:

$\mathrm{NTS}_{\textnormal{IQ}}=\mathbb{E}[X_{\textnormal{max}}]=\sum_{k=1}^{\infty}\mathrm{Pr}(X_{\textnormal{max}}\geq
k)\\\
\leq\sum_{k=1}^{\infty}\min(1,2^{a+b+1-k})=\sum_{k=1}^{a+1}1+\sum_{k=a+2}^{\infty}2^{a+b+1-k}\\\
=a+1+2^{b}=\log_{2}(\left|S\right|-1)+1+2^{b}-b\\\
\leq\log_{2}(\left|S\right|-1)+2,$ (27)

where in the second line we used
$\sum^{\infty}_{k^{\prime}=k}2^{-k^{\prime}}=2^{1-k}$.

Equation 9 follows from the observation that in the first step we either
obtain $z=0^{n}$ with probability $2^{1-n}$, in which case we learn nothing
about $b^{*}$, or we reduce the problem to Simon-($n-1$). Each term in the sum
in Eq. 9 represents the expected number of steps needed to reduce the problem
Simon-$(k+1)$ to Simon-$k$. The Erdős -Borwein constant is defined as
$E_{\textnormal{EB}}\equiv\sum_{k=1}^{\infty}1/(2^{k}-1)$, so
$\sum_{k=1}^{n-1}\frac{1}{1-2^{-k}}-(n+E_{\textnormal{EB}}-1)=-\sum_{k=n}^{\infty}1/(2^{k}-1)=O(2^{-n})$.

Equation 10 follows from the observation that for $w=1$ all $X_{b}$ are
independent, hence the task of computing $\mathrm{NTS}_{\textnormal{IQ}}$
reduces to the task of computing the expected value of the maximum of $n-1$
independent geometrically distributed random variables, which was solved in
Poblete  _et al._ (2006). ∎

##  Appendix G Ideal quantum $\mathrm{NTS}_{\textnormal{IQ}}$ calculation

1 states the upper and lower bounds for $\mathrm{NTS}_{\textnormal{IQ}}$ and
that it can be calculated exactly for the two limiting cases $w=1$ and
$w=\infty$. In the main text, we constructed an interpolation between the two
known values, Eqs. 9 and 10, which we can rewrite as:

$\mathrm{NTS}_{\textnormal{IQ}}=\log_{2}(N_{w})+t\Gamma_{w=\infty}+(1-t)\Gamma_{w=1},$
(28)

where the weighted $\Gamma_{w=\infty}=E_{\text{EB}}-1$ and
$\Gamma_{w=1}=0.5+\gamma/\ln(2)$ are constants from Eqs. 9 and 10,
respectively.

An alternative approach is to use a Monte Carlo simulation to compute
$\mathrm{NTS}_{\textnormal{IQ}}$. For a
$\mathsf{w}_{{w}}\textnormal{Simon-}{n}$ problem, we randomly picked 10
$b^{*}$’s from the possible set $S_{0}$ such that $|S_{0}|=N_{w}$. For each
$b^{*}$, a series of valid $z_{k}$’s such that $b^{*}\cdot z_{k}=0$ is drawn.
After each $z_{k}$ was drawn, we eliminated any $b$ in $S_{k}$ that did not
satisfy $b\cdot z_{k}=0$ and stopped when $|S_{k}|=1$. At this point, we
expected to only have $b^{*}$ as the only element left in $S_{k}$. The
simulated $\mathrm{NTS}_{\textnormal{IQ}}$ was calculated 10,000 times for
each $b^{*}$, and the average was taken. After performing the simulation for
10 $b^{*}$’s, we found the mean and standard deviation and reported this as
the Monte Carlo version of $\mathrm{NTS}_{\textnormal{IQ}}$.

Fig. 13 compares the upper bound and lower bound from Eq. 8, the interpolated
version of $\mathrm{NTS}_{\textnormal{IQ}}$, and the Monte Carlo version of
$\mathrm{NTS}_{\textnormal{IQ}}$ for $w=5$ and 6.

Figure 13: Upper bound (UB) and lower bound (LB) from Eq. 8, the interpolated
version of $\mathrm{NTS}_{\textnormal{IQ}}$ (IP), and the Monte Carlo version
of $\mathrm{NTS}_{\textnormal{IQ}}$ (MC) for $w=5$ (top) and 6 (bottom). The
error bars on the blue lines are $5\sigma$ in each direction.

##  Appendix H Post-processing for the ‘NISQ’ variant of the quantum algorithm

The original noiseless solver requires sampling $n-1$ independent output
bitstrings $z$’s and solves for the unique $b$ that satisfies $z\cdot
b=0,\forall z$. This means that if one of the $z$’s is altered by noise, the
resulting $b$ is guaranteed to be wrong. To reduce the effect of noise, we
employ Algorithm 1, a post-processing algorithm that applies in the ‘NISQ’
setting described in the main text.

Data: input $n,K_{\textnormal{min}}\in\mathbb{N}$, stream $Z$ of bitstrings

Initialize a dictionary $B$: $B[b^{\prime}]=0,\forall
b^{\prime}\in\\{0,1\\}^{n},b^{\prime}\neq 0$;

Initialize $K=0$;

while  _$K <K_{\textnormal{min}}$ or $\mathrm{argmax}(B)$ is not unique_ do

$K=K+1$;

$z=\mathrm{next}(Z)$;

for  _$b^{\prime}$ in $\mathrm{keys}(B)$_ do

if  _$z\cdot b^{\prime}=0$_ then

$B[b^{\prime}]=B[b^{\prime}]+1$;

end if

end for

end while

return $b^{\prime}=\mathrm{argmax}(B)$ and $K$;

Algorithm 1 Solving for $b$ in $K\geq K_{\textnormal{min}}$ shots

Algorithm 1 requires $K=O(kn)$ queries, but since $k=O(1)$, the quantum
speedup is maintained under the NTS metric, i.e., the algorithm’s query
complexity remains $O(n)$.

We find that optimal NTS performance is achieved when $k=2$ across a majority
of problem sizes. The variable $K$ extracted from the algorithm specified in
Algorithm 1 represents the actual count of shots (queries) utilized in solving
for $b$. This quantity is denoted $Q_{i}$ in Eq. 12, where
$i=\operatorname{HW}(b)$.

##  Appendix I Circuit Complexity Reduction

To avoid the impractical task of running $2^{n}-1$ different oracles for every
possible hidden bitstring for Simon-$n$ problems, we use permutation symmetry
and only run $n$ circuits for a problem size $n$. Our chosen bitstrings are
$b^{i}=0^{n-i}1^{i}$ for $1\leq i\leq n$. The number of queries $Q_{i}$ for
each $b^{i}$ is weighted in the NTS calculation in Eq. 12 according to the
corresponding weight $h_{i}={n\choose i}$, as explained in Section IV. We
assume that the permutation symmetry and weighting are processed within the
compiler, as detailed in Appendix A.

We aim to quantify the quantum speedup for a fixed $w\leq n$. To further
reduce the number of circuits, instead of running
$\mathsf{w}_{{w}}\textnormal{Simon-}{n}$ for every $n$ and $w$, we only run
$\mathsf{w}_{{w}}\textnormal{Simon-}{n_{\max}}$ and extract the
$\mathsf{w}_{{w}}\textnormal{Simon-}{m}$ cases where $m<n_{\max}$ during post-
processing.

Furthermore, we reduce Simon-$n$ to Simon-$m$, where $m<n$. For example, we
can use the result of the experiment at problem size $n=15$ to extract the
results for smaller problem sizes, $m=2$ to $m=14$. Figure 14 shows an example
of the reduction from $n=3$ ($b=011$) to $m=2$ ($b=11$).

$\ket{0}_{d_{0}}$$\ket{0}_{a_{0}}$$\ket{0}_{d_{1}}$$\ket{0}_{a_{1}}$$\ket{0}_{d_{2}}$$\ket{0}_{a_{2}}$$\mapsto$
Figure 14: Circuit reduction from Simon-3 to Simon-2. The right circuit $m=2$
($b=11$) can be extracted from the left circuit $n=3$ ($b=011$) by tracing out
qubits $d_{0}$ and $a_{0}$.

This reduction is possible under the assumption of a CPTP map governing the
circuit in the open-system setting. We give the proof of this fact next.

Since qubits $(d_{j},a_{j})$ are unentangled in our oracle construction from
the rest of the circuit if the $j$th bit of the hidden bitstring $b$ is zero,
these two qubits are separated from the rest of the oracle, as indicated by
the individual dashed boxes in Fig. 10. Therefore, the only difference between
$b_{n}=0^{n-i}1^{i}$ and $b_{m}=0^{m-i}1^{i}$ is that the circuit for
$|b_{n}|=n$ applies extra operations on extra qubits compared to the circuit
for $|b_{m}|=m$. Let $m\in[i,n-1]$; then all the circuits for
$b_{m}=0^{m-i}1^{i}$ have the identical output as the circuit for
$b_{n}=0^{n-i}1^{i}$ if we consider only the overlapping set of qubits, as
illustrated in Fig. 14. Intuitively, we may thus extract the Simon-$m$ results
from the Simon-$n$ results by running only the Simon-$n$ circuits and tracing
over the first $2(n-m)$ data qubits, a practice we implemented in our
experiments and subsequent analysis. Note that the left circuit in Fig. 14 is
the same circuit as in Fig. 11 but drawn with a different qubit order.

Let us now prove the equivalence of our procedure to actually running the
Simon-$m$ circuits, as long as the completely positive, trace preserving
(CPTP) map governing the circuit in the open system case factors into a
product over the “copied” and “XOR-ed” qubits, i.e., those corresponding to a
0 (copied) or 1 (XOR-ed) in the bitstring $b$ that defines the given oracle.

In preparation for our more general discussion below, let us equivalently
represent the action of the closed-system Simon-$n$ circuit with hidden
bitstring $b$ on some initial state $\rho$ of the $n$ data and $n$ ancilla
qubits as

$\mathrm{Simon}_{n}(b)[\rho]=\mathrm{Tr}_{a}\left[\left(H_{d}^{\otimes
n}\circ\mathcal{O}_{b}\circ H_{d}^{\otimes n}\right)[\rho]\right],$ (29)

where $\mathcal{O}_{b}$ represents the Simon oracle, and $\mathrm{Tr}_{a}$
means that the state of the ancilla qubits (labeled $a_{0},\dots,a_{n-1}$) is
discarded at the end, so that $\mathrm{Simon}_{n}(b)[\rho]$ is the state of
the $n$ data qubits at the end of one run of the algorithm. Thus, if we write
$\Pi_{b}=|{\psi_{b}}\rangle\\!\langle{\psi_{b}}|$ and
$|{\psi_{0}}\rangle\\!\langle{\psi_{0}}|=\Pi_{0^{n}}\otimes\Pi_{0^{n}}$, then
it follows from Eq. 29 that
$\mathrm{Simon}_{n}(b)[|{\psi_{0}}\rangle\\!\langle{\psi_{0}}|]=\Pi_{b}$.

Let us denote the qubit sets as follows: $D_{\nu}=\\{d_{0},\dots,d_{n-m-1}\\}$
($A_{\nu}=\\{a_{0},\dots,a_{n-m-1}\\}$) being the first $n-m$ data (ancilla)
qubits and $D_{\mu}=\\{d_{n-m},\dots,d_{n-1}\\}$
($A_{\mu}=\\{a_{n-m},\dots,a_{n-1}\\}$) being the remaining $m$ data (ancilla)
qubits in the circuit. Let $\cup_{\nu}\equiv D_{\nu}\cup
A_{\nu}=\\{d_{0},a_{0},\dots,d_{n-m-1},a_{n-m-1}\\}$. Let us show that if
$b_{n}=0^{n-i}1^{i}$, then

$\mathrm{Simon}_{m}(b_{m})[\Pi_{0^{m}}\otimes\Pi_{0^{m}}]=\mathrm{Tr}_{\cup_{\nu}}\left[\mathrm{Simon}_{n}(b_{n})[|{\psi_{0}}\rangle\\!\langle{\psi_{0}}|]\right],$
(30)

where the trace means that the states of qubits in $\cup_{\nu}$ are discarded
from the result of running $\mathrm{Simon}_{n}(b_{n})$. To prove this claim in
the absence of any noise, note that:

$\displaystyle\mathrm{Tr}_{\cup_{\nu}}$
$\displaystyle\left[\mathrm{Simon}_{n}(b_{n})[\ket{\psi_{0}}\\!\bra{\psi_{0}}]\right]$
(31a) $\displaystyle=\mathrm{Tr}_{\cup_{\nu}}\left[\Pi_{b_{n}}\right]$ (31b)
$\displaystyle=\mathrm{Tr}_{\cup_{\nu}}\left[\Pi_{\nu}\otimes\Pi_{b_{m}}\right]$
(31c) $\displaystyle=\Pi_{b_{m}}$ (31d)
$\displaystyle=\mathrm{Simon}_{m}(b_{m})[\Pi_{0^{m}}\otimes\Pi_{0^{m}}],$
(31e)

as claimed. Here, $b_{n}=0^{n-i}1^{i}$, $b_{m}=0^{m-i}1^{i}$ ($m<n$) and in
the third line, $\Pi_{\nu}=|{\psi_{\nu}}\rangle\\!\langle{\psi_{\nu}}|$, where
$\ket{\psi_{\nu}}=\ket{+}^{n-m}$ is derived from the last line of Eq. 29:

$\displaystyle\frac{1}{\sqrt{2^{n-1}}}\sum_{\\{z|z\cdot
b_{n}=0\\}}(-1)^{x\cdot z}\ket{z}_{d}$ (32a)
$\displaystyle=\frac{1}{\sqrt{2^{n-1}}}\sum_{y\in\\{0,1\\}^{n-m}}\ket{y}_{D_{\nu}}\otimes\sum_{\\{z|z\cdot
b_{m}=0\\}}(-1)^{x\cdot z}\ket{z}_{D_{\mu}}$ (32b)
$\displaystyle=\frac{1}{\sqrt{2^{n-m}}}\sum_{y\in\\{0,1\\}^{n-m}}\ket{y}_{D_{\nu}}\otimes$
$\displaystyle\qquad\frac{1}{\sqrt{2^{m-1}}}\sum_{\\{z|z\cdot
b_{m}=0\\}}(-1)^{x\cdot z}\ket{z}_{D_{\mu}}$ (32c)
$\displaystyle=\ket{\psi_{\nu}}\otimes\ket{\psi_{b_{m}}}.$ (32d)

Now consider the case where each gate is represented not by a unitary but by a
CPTP map. We can rewrite the initial state as

$|{\psi_{0}}\rangle\\!\langle{\psi_{0}}|=\Pi_{0^{n}}\otimes\Pi_{0^{n}}=\rho_{\nu}\otimes\rho_{\mu},$
(33)

where $\rho_{\nu}=\Pi_{0^{n-m}}\otimes\Pi_{0^{n-m}}$ and
$\rho_{\mu}=\Pi_{0^{m}}\otimes\Pi_{0^{m}}$. The Simon oracle does not
introduce any two-qubit gates between qubit sectors $\cup_{\mu}=D_{\mu}\cup
A_{\mu}$ and $\cup_{\nu}=D_{\nu}\cup A_{\nu}$, so it is reasonable to assume
that under the coupling to the environment, they remain uncoupled (as long as
there is no unintended crosstalk between the two sectors). Therefore, the CPTP
map for the noisy Simon-$n$ algorithm will be

$\displaystyle\mathcal{S}_{n}(b_{n})[\rho_{\nu}\otimes\rho_{\mu}]$
$\displaystyle=\mathrm{Tr}_{\cup_{\nu}}\left[(\mathcal{H}_{\nu}\otimes\mathcal{H}_{\mu})\circ(\mathcal{O}_{\nu}\otimes\mathcal{O}_{\mu})\right.$
$\displaystyle\qquad\qquad\left.\circ(\mathcal{H}_{\nu}\otimes\mathcal{H}_{\mu})[\rho_{\nu}\otimes\rho_{\mu}]\right],$
(34)

where $\mathcal{H}_{\nu,\mu}$ and $\mathcal{O}_{\nu,\mu}$ represent the CPTP
maps corresponding to the experimental implementation of the unitaries $H$
(multi-qubit Hadamard) and $\mathcal{O}_{f}$ (oracle) acting on qubit sectors
$\nu,\mu$. Recall that for arbitrary CPTP maps $\mathcal{U}$ and $\mathcal{V}$
acting on a tensor-product space

$\mathcal{U}\otimes\mathcal{V}[\rho\otimes\sigma]=\mathcal{U}[\rho]\otimes\mathcal{V}[\sigma].$
(35)

Therefore,

$\displaystyle\mathrm{Tr}_{\cup_{\nu}}\left[\mathcal{S}_{n}(b_{n})[\ket{\psi_{0}}\\!\bra{\psi_{0}}]\right]$
(36a)
$\displaystyle\quad=\mathrm{Tr}_{\cup_{\nu}}\left[(\mathcal{H}_{\nu}\otimes\mathcal{H}_{\mu})\circ(\mathcal{O}_{\nu}\otimes\mathcal{O}_{\mu})\right.$
$\displaystyle\left.\qquad\qquad\qquad\circ(\mathcal{H}_{\nu}\otimes\mathcal{H}_{\mu})[\rho_{\nu}\otimes\rho_{\mu}]\right]$
(36b)
$\displaystyle\quad=\mathrm{Tr}_{\cup_{\nu}}\left[(\mathcal{H}_{\nu}\circ\mathcal{O}_{\nu}\circ\mathcal{H}_{\nu})[\rho_{\nu}]\right.$
$\displaystyle\left.\qquad\qquad\qquad\otimes(\mathcal{H}_{\mu}\circ\mathcal{O}_{\mu}\circ\mathcal{H}_{\mu})[\rho_{\mu}]\right]$
(36c) $\displaystyle\quad=\mathcal{S}_{m}(b_{m})[\rho_{\mu}]$ (36d)
$\displaystyle\quad=\mathcal{S}_{m}(b_{m})[\Pi_{0^{m}}\otimes\Pi_{0^{m}}].$
(36e)

This is the CPTP map generalization of the closed-system result Eq. 30, and it
shows that the reduction from Simon-$n$ to Simon-$m$ holds rigorously also in
the open system setting, as long as the CPTP map factors according to the
qubit sectors $\nu$ and $\mu$.

##  Appendix J Device specifications

We performed our experiments on two 127-qubit and two 27-qubit IBM Quantum
devices, respectively: Brisbane and Sherbrooke, and Cairo and Kolkata. Table 1
and Table 2 give the device specifications.

We used $100,000$ shots per experiment parameterized by the Hamming weight of
the oracle $b$ for each device.

| Brisbane | Sherbrooke
---|---|---
| Min | Mean | Max | Min | Mean | Max
$T_{1}(\mu s)$ | 27.59 | 290.03 | 519.75 | 45.60 | 233.38 | 404.29
$T_{2}(\mu s)$ | 11.21 | 173.18 | 439.99 | 9.45 | 144.76 | 366.50
1QG Error (%) | 0.026 | 0.080 | 0.424 | 0.028 | 0.118 | 3.324
2QG Error (%) | 0.278 | 0.376 | 100 | 0.373 | 2.437 | 100
1QG Duration $(\mu s)$ | 0.171 | 0.171 | 0.171 | 0.180 | 0.180 | 0.180
2QG Duration $(\mu s)$ | 0.448 | 0.539 | 0.882 | 0.660 | 0.665 | 0.860
RO Error (%) | 0.180 | 1.813 | 27.670 | 0.430 | 2.063 | 11.90
RO Duration $(\mu s)$ | 1.244 | 1.244 | 1.244 | 4.000 | 4.000 | 4.000
Table 1: Device specifications for the 127-qubit devices Brisbane and Sherbrooke on May 5, 2023. 1QG and 2QG denote 1-qubit gate and 2-qubit gate, respectively. RO denotes readout. The numbers shown are averages over the qubits used in our experiments. | Cairo | Kolkata
---|---|---
| Min | Mean | Max | Min | Mean | Max
$T_{1}(\mu s)$ | 63.79 | 116.39 | 195.17 | 37.13 | 121.03 | 235.27
$T_{2}(\mu s)$ | 15.59 | 97.63 | 212.26 | 16.35 | 74.51 | 192.35
1QG Error (%) | 0.043 | 0.093 | 0.356 | 0.047 | 0.090 | 0.204
2QG Error (%) | 0.491 | 4.680 | 100 | 0.591 | 11.98 | 100
1QG Duration $(\mu s)$ | 0.075 | 0.075 | 0.075 | 0.107 | 0.107 | 0.107
2QG Duration $(\mu s)$ | 0.160 | 0.351 | 0.946 | 0.341 | 0.458 | 0.626
RO Error (%) | 0.750 | 1.679 | 6.120 | 0.340 | 2.607 | 11.76
RO Duration $(\mu s)$ | 0.732 | 0.732 | 0.732 | 0.640 | 0.640 | 0.640
Table 2: Device specifications for the 27-qubit devices Cairo and Kolkata on
April 20 and 22, 2023, respectively. 1QG and 2QG denote 1-qubit gate and
2-qubit gate, respectively. RO denotes readout. The numbers shown are averages
over the qubits used in our experiments.

##  Appendix K DD performance

This section presents the performance evaluation of all DD sequences
investigated in the experiments on Sherbrooke and Brisbane, specifically the
12 sequences from the set $\mathcal{D}$ as introduced in Section V. The
performance assessed by the NTS metric is illustrated in Fig. 15. The NTS
values are presented for each DD sequence across the problem size $n$, in the
range $[2,15]$. Sequences colored in blue ($\times$) indicate optimal
performers identified on their corresponding machines at each problem size.
The analysis reveals that UR10 (RGA8a) exhibits the best performance among
sequences on Sherbrooke (Brisbane), consistently achieving the lowest NTS
across a majority of $n$ ranging from 7 to 15.

Figure 15: DD performance under NTS metric on Sherbrooke (left) and Brisbane
(right) over the $12$ sequences in the set $\mathcal{D}=\\{$CPMG, RGA2x, XY4,
UR6, RGA8a, UR10, RGA16b, UR18, UR26, RGA32a, RGA32c, UR${}_{32}\\}$.
Sequences colored in blue ($\times$) denote those identified as optimal
performers on their respective machines at varying problem sizes $n$. The
arrangement of sequences in the plot reflects their performance averaged over
all problem sizes $n$. UR10 and RGA8a emerge as the best-performing sequence
overall on Sherbrooke and Brisbane, respectively, and become the top-
performing sequences for all $n\geq 7$ on both devices. The error bars,
representing confidence intervals derived through bootstrapping, extend
5$\sigma$ in both directions from each data point. Figure 16: Probability of
obtaining $z\cdot b=0$ with and without MEM on Brisbane (Bris) and Sherbrooke
(Sher). The data shown uses the best-performing DD sequences on each device.

Figure 17: The fitted scaling parameter $a$ as a function of $w$ for
$\mathsf{w}_{{w}}\textnormal{Simon-}{13}$ on Cairo (top) and Kolkata (bottom),
both with MEM. When the quantum slope is below the classical slope, we declare
an algorithmic quantum speedup. This does not hold for any value of $w$, and
instead, we observe a quantum slowdown, even with DD. The error bars,
representing the standard deviation of the fitted parameter $a$ on the
bootstrapped data, extend $1\sigma$ in each direction from each data point.

##  Appendix L Error Mitigation

DD suppresses noise during circuit execution. To complement DD, we used
measurement error mitigation (MEM) Temme  _et al._ (2017) as a means to reduce
measurement-related errors in the NISQ algorithm setting. Information on
device properties was collected on the days our experiments were run and used
as correction matrices in PyIBU Srinivasan  _et al._ (2022), which runs MEM
based on iterative Bayesian unfolding.

Fig. 16 shows the probability of obtaining $z\cdot b=0$ as a function of $n$,
the length of the hidden bitstring $b$. An improvement resulting from the
application of MEM is visible.

##  Appendix M Bootstrapping

We conducted a robust statistical analysis employing a $100,000$-sample
bootstrapping technique on the NTS values subjected to a $10$-fold cross-
validation. Each sample, consisting of $9$ uniformly selected data points from
the cross-validation set, underwent resampling to derive the mean and standard
deviation. The resulting bootstrapped means and standard deviations are
presented as individual data points in Fig. 3 and Fig. 15, where the mean
values are plotted as data points, with error bars extending $5\sigma$ in both
directions. These statistics are then used to fit for the parameter $a$ using
Scipy’s curve_fit, also reported as the “$\pm$” uncertainties in Fig. 3,
taking into account the bootstrapped mean as the $\mathrm{NTS}$ value and one
standard deviation as its error. In Fig. 4 and Fig. 17, the parameter $a$ was
fitted using the bootstrapped data in the same way as in Fig. 3 but with
different $w$ values. The standard deviation from the fitting is reported as
$1\sigma$ in each direction from each data point.

##  Appendix N Determination of $n_{\min}$

Figure 18 shows that $n_{\min}=2$ in the DD-protected case for both Sherbrooke
and Brisbane. In the unprotected case, we see that $n_{\min}=5$ and
$n_{\min}=2$ for Sherbrooke and Brisbane, respectively.

Maximizing the confidence intervals on $a_{Q}$ until they overlap $a_{C}$, we
find that $a_{C}>a_{Q}$ with $99.4\%$ and $99.9\%$ confidence on Sherbrooke
and Brisbane, respectively, as can also be seen from Fig. 18.

Figure 18: The fitted scaling parameter $a$ as a function of $n_{\min}$ on
Sherbrooke for $\mathsf{w}_{{6}}\textnormal{Simon-}{15}$ (top) and Brisbane
for $\mathsf{w}_{{5}}\textnormal{Simon-}{15}$ (bottom), both with MEM. The
error bars represent $99.4\%$ ($99.9\%$) confidence intervals on Sherbrooke
(Brisbane), except for $n_{\min}=13$, where we show an error bar of
$10\sigma$. This choice arises from the $t$-value used for calculating the
confidence interval at $n_{\min}=13$, which is approximately $10$ times larger
than that of other $n_{\min}$ values. There is no error bar for $n_{\min}=14$
because only two points are involved in the curve fitting. We report the $a$
value that is maximized over the range of $n_{\min}$ shown. In the unprotected
case, this corresponds to $n_{\min}=5$ on Sherbrooke and $n_{\min}=2$ on
Brisbane. In the DD-protected case, all values of $a$ lie below the classical
value, but we report the worst-case result obtained for $n_{\min}=2$ on both
devices.

##  Appendix O Mutual information

Solving Simon’s problem requires a series of “good” outcomes of the form
$z\cdot b=0$ and $z\neq 0$. Let $p$ be the probability of $z\cdot b=0$ and let
$q$ be the probability of obtaining $z=0$. The result of each measurement
round then falls into one of the following three categories:

$\displaystyle\mathrm{Pr}(z=0)$ $\displaystyle=q,$ (37)
$\displaystyle\mathrm{Pr}(z\cdot b=0|z\neq 0)$ $\displaystyle=(1-q)p,$
$\displaystyle\mathrm{Pr}(z\cdot b=1|z\neq 0)$ $\displaystyle=(1-q)(1-p).$

We can extract $p$ and $q$ from the counts data of the experiment. The
probability $\mathrm{Pr}(z\cdot b=0)=q+(1-q)p$ for both $127$-qubit devices is
plotted in Fig. 16. Note that we set $p=0$ when $n=1$ by definition. This is
because the only possible non-zero hidden bitstring is $b=1$ when $n=1$,
hence, every $z$ such that $z\cdot b=0$ is $z=0$, which contributes only to
$q$. With this choice, we start the plot in Fig. 16 from $n=2$.

We calculate the estimated information gained per circuit round, with the
optimistic assumption that we gain the same amount of information in every
round. Letting $S(X)$ denote the Shannon entropy of a random variable $X$, the
classical mutual information $I(Z;B)$ is defined as

$\displaystyle I(Z;B)$ $\displaystyle=S(Z)+S(B)-S(Z|B)$ (38)
$\displaystyle=\sum_{z,b}\mathrm{Pr}(z,b)\log_{2}\frac{\mathrm{Pr}(z,b)}{\mathrm{Pr}(z)\mathrm{Pr}(b)}$
$\displaystyle=\sum_{z,b}\mathrm{Pr}(z|b)\mathrm{Pr}(b)\log_{2}\frac{\mathrm{Pr}(z|b)}{\mathrm{Pr}(z)}$
$\displaystyle=\left(\sum_{b}\mathrm{Pr}(b)\right)\left(\sum_{z}\mathrm{Pr}(z|b)\log_{2}\frac{\mathrm{Pr}(z|b)}{\mathrm{Pr}(z)}\right)$
$\displaystyle=\sum_{z}\mathrm{Pr}(z|b)\log_{2}\frac{\mathrm{Pr}(z|b)}{\mathrm{Pr}(z)}.$

To go from the second to the third line, we used the fact that
$\mathrm{Pr}(z|b)\mathrm{Pr}(b)=\mathrm{Pr}(z,b)$. In the fourth line, the
summation over $b$ is separated from the summation over $z$ because the
quantity in the second bracket is independent of $b$ by permutation symmetry.
We used $\sum_{b}\mathrm{Pr}(b)=1$ to arrive at the last line and remove the
dependence on $b$.

Consider dividing the sum into three cases according to Eq. 37, we have
$I(Z;B)=\sum_{i=1,2,3}I^{i}(Z;B)$, where $I^{i}(Z;B)$ is given as follows.

  * •

Case I: $z=0$.

$\displaystyle I^{1}(Z;B)$
$\displaystyle=\mathrm{Pr}(z=0|b)\log_{2}\frac{\mathrm{Pr}(z=0|b)}{\mathrm{Pr}(z=0)}$
(39) $\displaystyle=q\log_{2}\frac{q}{q}=0.$

  * •

Case II: $z\cdot b=0$, $z\neq 0$. There are $N_{2}=2^{n-1}-1$ possibilities of
$z$’s (half of $2^{n}$ and excluding 0).

$\displaystyle I^{2}(Z;B)$ $\displaystyle=\sum_{z}\mathrm{Pr}(z\cdot b=0\land
z\neq 0|b)\log_{2}\frac{\mathrm{Pr}(z\cdot b=0\land z\neq
0|b)}{\mathrm{Pr}(z\cdot b=0\land z\neq 0)}$ (40)
$\displaystyle=\sum_{z}\frac{(1-q)p}{N_{2}}\log_{2}\frac{(1-q)p/N_{2}}{(1-q)/(2^{n}-1)}$
$\displaystyle=(1-q)p\log_{2}\frac{p(2^{n}-1)}{2^{n-1}-1}$

  * •

Case III: $z\cdot b=1$, $z\neq 0$. There are $N_{3}=2^{n-1}$ possibilities of
$z$’s (half of $2^{n}$).

$\displaystyle I^{3}(Z;B)$ $\displaystyle=\sum_{z}\mathrm{Pr}(z\cdot b=1\land
z\neq 0|b)\log_{2}\frac{\mathrm{Pr}(z\cdot b=1\land z\neq
0|b)}{\mathrm{Pr}(z\cdot b=1\land z\neq 0)}$ (41)
$\displaystyle=\sum_{z}\frac{(1-q)(1-p)}{N_{3}}\log_{2}\frac{(1-q)(1-p)/N_{3}}{(1-q)/(2^{n}-1)}$
$\displaystyle=(1-q)(1-p)\log_{2}\frac{(1-p)(2^{n}-1)}{2^{n-1}}$

We can calculate the classical mutual information $I(Z;B)$ in terms of $p$ and
$q$ as the sum of Eq. 39, Eq. 40, and Eq. 41:

$\displaystyle I(Z;B)$
$\displaystyle=(1-q)\left(p\log_{2}\frac{p(2^{n}-1)}{2^{n-1}-1}\right.$ (42)
$\displaystyle\qquad\qquad\left.+(1-p)\log_{2}\frac{(1-p)(2^{n}-1)}{2^{n-1}}\right).$

The expected information learned per circuit, $I(Z;B)$, is plotted as a
function of problem size $n$ in Fig. 19. We compare the free evolution and the
top-performing DD sequence of each device with and without MEM. From this
information, we expect, on average, to see these top-performing sequences
having better scaling in the NTS metric.

Both Figs. 16 and 19 confirm that the results are essentially random for
$n>15$, as stated in the main text.

Figure 19: Information learned per circuit with and without MEM from the best
sequence on 127-qubit devices, Brisbane (BB) and Sherbrooke (SB).

##  Appendix P Results for 27-qubit devices: no evidence of an algorithmic
quantum speedup

We performed the same set of experiments on two 27-qubit IBM Quantum devices,
Cairo (ibm_cairo) and Kolkata (ibmq_kolkata), each with 100,000 shots. Both
devices feature the heavy-hex lattice and the Falcon r5.11 processor. Their
specifications at the time of our experiments are given in Table 2.

For these experiments, we set $n_{\max}=13$, the maximum possible value
compatible with $27$ qubits. Unlike the $127$-qubit devices discussed in the
main text, there is no evidence of quantum speedup for any Hamming weight
considered, as seen from Fig. 17 (contrast with Fig. 4). However, DD
protection still results in a significant improvement.

## References

  * Deutsch and Jozsa (1992) David Deutsch and Richard Jozsa, “Rapid solution of problems by quantum computation,”  _Proceedings of the Royal Society of London. Series A: Mathematical and Physical Sciences_ , Proceedings of the Royal Society of London. Series A: Mathematical and Physical Sciences 439, 553–558 (1992).
  * Bernstein and Vazirani (1997) Ethan Bernstein and Umesh Vazirani, “Quantum Complexity Theory,” SIAM J. Comput. 26, 1411–1473 (1997).
  * Simon (1997) Daniel R. Simon, “On the power of quantum computation,” SIAM Journal on Computing 26, 1474–1483 (1997).
  * Grover (1997) Lov K. Grover, “Quantum mechanics helps in searching for a needle in a haystack,” Phys. Rev. Lett. 79, 325–328 (1997).
  * Shor (1997) P. Shor, “Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer,” SIAM Journal on Computing 26, 1484–1509 (1997).
  * Childs  _et al._ (2003) Andrew M Childs, Richard Cleve, Enrico Deotto, Edward Farhi, Sam Gutmann, and Daniel A Spielman, “Exponential algorithmic speedup by a quantum walk,” in  _Proceedings of the thirty-fifth annual ACM symposium on Theory of computing_ (ACM, 2003) pp. 59–68.
  * Van Dam  _et al._ (2006) Wim Van Dam, Sean Hallgren, and Lawrence Ip, “Quantum algorithms for some hidden shift problems,” SIAM Journal on Computing 36, 763–778 (2006).
  * Harrow  _et al._ (2009) Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd, “Quantum algorithm for linear systems of equations,” Physical Review Letters 103, 150502– (2009).
  * Montanaro (2016) Ashley Montanaro, “Quantum algorithms: An overview,” NPJ Quantum Inf. 2, 15023 (2016).
  * Bravyi  _et al._ (2018) Sergey Bravyi, David Gosset, and Robert König, “Quantum advantage with shallow circuits,” Science 362, 308 (2018).
  * Bravyi  _et al._ (2020) Sergey Bravyi, David Gosset, Robert König, and Marco Tomamichel, “Quantum advantage with noisy shallow circuits,” Nature Physics 16, 1040–1045 (2020).
  * Bharti  _et al._ (2022) Kishor Bharti, Alba Cervera-Lierta, Thi Ha Kyaw, Tobias Haug, Sumner Alperin-Lea, Abhinav Anand, Matthias Degroote, Hermanni Heimonen, Jakob S. Kottmann, Tim Menke, Wai-Keong Mok, Sukin Sim, Leong-Chuan Kwek, and Alán Aspuru-Guzik, “Noisy intermediate-scale quantum algorithms,” Reviews of Modern Physics 94, 015004– (2022).
  * Daley  _et al._ (2022) Andrew J. Daley, Immanuel Bloch, Christian Kokail, Stuart Flannigan, Natalie Pearson, Matthias Troyer, and Peter Zoller, “Practical quantum advantage in quantum simulation,” Nature 607, 667–676 (2022).
  * Preskill (2018) John Preskill, “Quantum Computing in the NISQ era and beyond,” Quantum 2, 79 (2018).
  * Albash and Lidar (2018) Tameem Albash and Daniel A. Lidar, “Demonstration of a scaling advantage for a quantum annealer over simulated annealing,” Physical Review X 8, 031016– (2018).
  * King  _et al._ (2021) Andrew D. King, Jack Raymond, Trevor Lanting, Sergei V. Isakov, Masoud Mohseni, Gabriel Poulin-Lamarre, Sara Ejtemaee, William Bernoudy, Isil Ozfidan, Anatoly Yu. Smirnov, Mauricio Reis, Fabio Altomare, Michael Babcock, Catia Baron, Andrew J. Berkley, Kelly Boothby, Paul I. Bunyk, Holly Christiani, Colin Enderud, Bram Evert, Richard Harris, Emile Hoskinson, Shuiyuan Huang, Kais Jooya, Ali Khodabandelou, Nicolas Ladizinsky, Ryan Li, P. Aaron Lott, Allison J. R. MacDonald, Danica Marsden, Gaelen Marsden, Teresa Medina, Reza Molavi, Richard Neufeld, Mana Norouzpour, Travis Oh, Igor Pavlov, Ilya Perminov, Thomas Prescott, Chris Rich, Yuki Sato, Benjamin Sheldan, George Sterling, Loren J. Swenson, Nicholas Tsai, Mark H. Volkmann, Jed D. Whittaker, Warren Wilkinson, Jason Yao, Hartmut Neven, Jeremy P. Hilton, Eric Ladizinsky, Mark W. Johnson, and Mohammad H. Amin, “Scaling advantage over path-integral monte carlo in quantum simulation of geometrically frustrated magnets,” Nature Communications 12, 1113 (2021).
  * Saggio  _et al._ (2021) V. Saggio, B. E. Asenbeck, A. Hamann, T. Strömberg, P. Schiansky, V. Dunjko, N. Friis, N. C. Harris, M. Hochberg, D. Englund, S. Wölk, H. J. Briegel, and P. Walther, “Experimental quantum speed-up in reinforcement learning agents,” Nature 591, 229–233 (2021).
  * Centrone  _et al._ (2021) Federico Centrone, Niraj Kumar, Eleni Diamanti, and Iordanis Kerenidis, “Experimental demonstration of quantum advantage for np verification with limited information,” Nature Communications 12, 850 (2021).
  * Maslov  _et al._ (2021) Dmitri Maslov, Jin-Sung Kim, Sergey Bravyi, Theodore J. Yoder, and Sarah Sheldon, “Quantum advantage for computations with limited space,” Nature Physics 17, 894–897 (2021).
  * Xia  _et al._ (2021) Yi Xia, Wei Li, Quntao Zhuang, and Zheshen Zhang, “Quantum-enhanced data classification with a variational entangled sensor network,” Physical Review X 11, 021047– (2021).
  * Huang  _et al._ (2022) Hsin-Yuan Huang, Michael Broughton, Jordan Cotler, Sitan Chen, Jerry Li, Masoud Mohseni, Hartmut Neven, Ryan Babbush, Richard Kueng, John Preskill, and Jarrod R. McClean, “Quantum advantage in learning from experiments,” Science 376, 1182–1186 (2022).
  * Ebadi  _et al._ (2022) S. Ebadi, A. Keesling, M. Cain, T. T. Wang, H. Levine, D. Bluvstein, G. Semeghini, A. Omran, J.-G. Liu, R. Samajdar, X.-Z. Luo, B. Nash, X. Gao, B. Barak, E. Farhi, S. Sachdev, N. Gemelke, L. Zhou, S. Choi, H. Pichler, S.-T. Wang, M. Greiner, V. Vuletic, and M. D. Lukin, “Quantum optimization of maximum independent set using rydberg atom arrays,” Science 376, 1209–1215 (2022).
  * Zhou  _et al._ (2022) Min-Gang Zhou, Xiao-Yu Cao, Yu-Shuo Lu, Yang Wang, Yu Bao, Zhao-Ying Jia, Yao Fu, Hua-Lei Yin, and Zeng-Bing Chen, “Experimental Quantum Advantage with Quantum Coupon Collector,” Research 2022 (2022).
  * King  _et al._ (2023) Andrew D. King, Jack Raymond, Trevor Lanting, Richard Harris, Alex Zucca, Fabio Altomare, Andrew J. Berkley, Kelly Boothby, Sara Ejtemaee, Colin Enderud, Emile Hoskinson, Shuiyuan Huang, Eric Ladizinsky, Allison J. R. MacDonald, Gaelen Marsden, Reza Molavi, Travis Oh, Gabriel Poulin-Lamarre, Mauricio Reis, Chris Rich, Yuki Sato, Nicholas Tsai, Mark Volkmann, Jed D. Whittaker, Jason Yao, Anders W. Sandvik, and Mohammad H. Amin, “Quantum critical dynamics in a 5,000-qubit programmable spin glass,” Nature 617, 61–66 (2023).
  * Kim  _et al._ (2023) Youngseok Kim, Andrew Eddins, Sajant Anand, Ken Xuan Wei, Ewout van den Berg, Sami Rosenblatt, Hasan Nayfeh, Yantao Wu, Michael Zaletel, Kristan Temme, and Abhinav Kandala, “Evidence for the utility of quantum computing before fault tolerance,” Nature 618, 500–505 (2023).
  * Aaronson and Chen (2017) Scott Aaronson and Lijie Chen, “Complexity-theoretic foundations of quantum supremacy experiments,” in  _Proceedings of the 32nd Computational Complexity Conference_, CCC ’17 (Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, DEU, 2017).
  * Arute  _et al._ (2019) Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C. Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, Fernando G. S. L. Brandao, David A. Buell, Brian Burkett, Yu Chen, Zijun Chen, Ben Chiaro, Roberto Collins, William Courtney, Andrew Dunsworth, Edward Farhi, Brooks Foxen, Austin Fowler, Craig Gidney, Marissa Giustina, Rob Graff, Keith Guerin, Steve Habegger, Matthew P. Harrigan, Michael J. Hartmann, Alan Ho, Markus Hoffmann, Trent Huang, Travis S. Humble, Sergei V. Isakov, Evan Jeffrey, Zhang Jiang, Dvir Kafri, Kostyantyn Kechedzhi, Julian Kelly, Paul V. Klimov, Sergey Knysh, Alexander Korotkov, Fedor Kostritsa, David Landhuis, Mike Lindmark, Erik Lucero, Dmitry Lyakh, Salvatore Mandrà, Jarrod R. McClean, Matthew McEwen, Anthony Megrant, Xiao Mi, Kristel Michielsen, Masoud Mohseni, Josh Mutus, Ofer Naaman, Matthew Neeley, Charles Neill, Murphy Yuezhen Niu, Eric Ostby, Andre Petukhov, John C. Platt, Chris Quintana, Eleanor G. Rieffel, Pedram Roushan, Nicholas C. Rubin, Daniel Sank, Kevin J. Satzinger, Vadim Smelyanskiy, Kevin J. Sung, Matthew D. Trevithick, Amit Vainsencher, Benjamin Villalonga, Theodore White, Z. Jamie Yao, Ping Yeh, Adam Zalcman, Hartmut Neven, and John M. Martinis, “Quantum supremacy using a programmable superconducting processor,” Nature 574, 505–510 (2019).
  * Wu  _et al._ (2021) Yulin Wu, Wan-Su Bao, Sirui Cao, Fusheng Chen, Ming-Cheng Chen, Xiawei Chen, Tung-Hsun Chung, Hui Deng, Yajie Du, Daojin Fan, Ming Gong, Cheng Guo, Chu Guo, Shaojun Guo, Lianchen Han, Linyin Hong, He-Liang Huang, Yong-Heng Huo, Liping Li, Na Li, Shaowei Li, Yuan Li, Futian Liang, Chun Lin, Jin Lin, Haoran Qian, Dan Qiao, Hao Rong, Hong Su, Lihua Sun, Liangyuan Wang, Shiyu Wang, Dachao Wu, Yu Xu, Kai Yan, Weifeng Yang, Yang Yang, Yangsen Ye, Jianghan Yin, Chong Ying, Jiale Yu, Chen Zha, Cha Zhang, Haibin Zhang, Kaili Zhang, Yiming Zhang, Han Zhao, Youwei Zhao, Liang Zhou, Qingling Zhu, Chao-Yang Lu, Cheng-Zhi Peng, Xiaobo Zhu, and Jian-Wei Pan, “Strong quantum computational advantage using a superconducting quantum processor,” Phys. Rev. Lett. 127, 180501– (2021).
  * Zhong  _et al._ (2020) Han-Sen Zhong, Hui Wang, Yu-Hao Deng, Ming-Cheng Chen, Li-Chao Peng, Yi-Han Luo, Jian Qin, Dian Wu, Xing Ding, Yi Hu, Peng Hu, Xiao-Yan Yang, Wei-Jun Zhang, Hao Li, Yuxuan Li, Xiao Jiang, Lin Gan, Guangwen Yang, Lixing You, Zhen Wang, Li Li, Nai-Le Liu, Chao-Yang Lu, and Jian-Wei Pan, “Quantum computational advantage using photons,” Science 370, 1460–1463 (2020).
  * Zhong  _et al._ (2021) Han-Sen Zhong, Yu-Hao Deng, Jian Qin, Hui Wang, Ming-Cheng Chen, Li-Chao Peng, Yi-Han Luo, Dian Wu, Si-Qiu Gong, Hao Su, Yi Hu, Peng Hu, Xiao-Yan Yang, Wei-Jun Zhang, Hao Li, Yuxuan Li, Xiao Jiang, Lin Gan, Guangwen Yang, Lixing You, Zhen Wang, Li Li, Nai-Le Liu, Jelmer J. Renema, Chao-Yang Lu, and Jian-Wei Pan, “Phase-programmable gaussian boson sampling using stimulated squeezed light,” Phys. Rev. Lett. 127, 180502– (2021).
  * Morvan  _et al._ (2023) A. Morvan, B. Villalonga, X. Mi, S. Mandrà, A. Bengtsson, P. V. Klimov, Z. Chen, S. Hong, C. Erickson, I. K. Drozdov, J. Chau, G. Laun, R. Movassagh, A. Asfaw, L. T. A. N. Brandão, R. Peralta, D. Abanin, R. Acharya, R. Allen, T. I. Andersen, K. Anderson, M. Ansmann, F. Arute, K. Arya, J. Atalaya, J. C. Bardin, A. Bilmes, G. Bortoli, A. Bourassa, J. Bovaird, L. Brill, M. Broughton, B. B. Buckley, D. A. Buell, T. Burger, B. Burkett, N. Bushnell, J. Campero, H. S. Chang, B. Chiaro, D. Chik, C. Chou, J. Cogan, R. Collins, P. Conner, W. Courtney, A. L. Crook, B. Curtin, D. M. Debroy, A. Del Toro Barba, S. Demura, A. Di Paolo, A. Dunsworth, L. Faoro, E. Farhi, R. Fatemi, V. S. Ferreira, L. Flores Burgos, E. Forati, A. G. Fowler, B. Foxen, G. Garcia, E. Genois, W. Giang, C. Gidney, D. Gilboa, M. Giustina, R. Gosula, A. Grajales Dau, J. A. Gross, S. Habegger, M. C. Hamilton, M. Hansen, M. P. Harrigan, S. D. Harrington, P. Heu, M. R. Hoffmann, T. Huang, A. Huff, W. J. Huggins, L. B. Ioffe, S. V. Isakov, J. Iveland, E. Jeffrey, Z. Jiang, C. Jones, P. Juhas, D. Kafri, T. Khattar, M. Khezri, M. Kieferová, S. Kim, A. Kitaev, A. R. Klots, A. N. Korotkov, F. Kostritsa, J. M. Kreikebaum, D. Landhuis, P. Laptev, K. M. Lau, L. Laws, J. Lee, K. W. Lee, Y. D. Lensky, B. J. Lester, A. T. Lill, W. Liu, A. Locharla, F. D. Malone, O. Martin, S. Martin, J. R. McClean, M. McEwen, K. C. Miao, A. Mieszala, S. Montazeri, W. Mruczkiewicz, O. Naaman, M. Neeley, C. Neill, A. Nersisyan, M. Newman, J. H. Ng, A. Nguyen, M. Nguyen, M. Yuezhen Niu, T. E. O’Brien, S. Omonije, A. Opremcak, A. Petukhov, R. Potter, L. P. Pryadko, C. Quintana, D. M. Rhodes, C. Rocque, P. Roushan, N. C. Rubin, N. Saei, D. Sank, K. Sankaragomathi, K. J. Satzinger, H. F. Schurkus, C. Schuster, M. J. Shearn, A. Shorter, N. Shutty, V. Shvarts, V. Sivak, J. Skruzny, W. C. Smith, R. D. Somma, G. Sterling, D. Strain, M. Szalay, D. Thor, A. Torres, G. Vidal, C. Vollgraff Heidweiller, T. White, B. W. K. Woo, C. Xing, Z. J. Yao, P. Yeh, J. Yoo, G. Young, A. Zalcman, Y. Zhang, N. Zhu, N. Zobrist, E. G. Rieffel, R. Biswas, R. Babbush, D. Bacon, J. Hilton, E. Lucero, H. Neven, A. Megrant, J. Kelly, I. Aleiner, V. Smelyanskiy, K. Kechedzhi, Y. Chen, and S. Boixo, “Phase transition in random circuit sampling,” arXiv e-prints (2023), arXiv:2304.11119 [quant-ph] .
  * Figgatt  _et al._ (2017) C. Figgatt, D. Maslov, K. A. Landsman, N. M. Linke, S. Debnath, and C. Monroe, “Complete 3-Qubit Grover search on a programmable quantum computer,” Nat. Commun. 8, 1–9 (2017).
  * Wright  _et al._ (2019) K. Wright, K. M. Beck, S. Debnath, J. M. Amini, Y. Nam, N. Grzesiak, J.-S. Chen, N. C. Pisenti, M. Chmielewski, C. Collins, K. M. Hudek, J. Mizrahi, J. D. Wong-Campos, S. Allen, J. Apisdorf, P. Solomon, M. Williams, A. M. Ducore, A. Blinov, S. M. Kreikemeier, V. Chaplin, M. Keesan, C. Monroe, and J. Kim, “Benchmarking an 11-qubit quantum computer,” Nat. Commun. 10, 5464 (2019).
  * Roy  _et al._ (2020) Tanay Roy, Sumeru Hazra, Suman Kundu, Madhavi Chand, Meghan P. Patankar, and R. Vijay, “Programmable Superconducting Processor with Native Three-Qubit Gates,” Phys. Rev. Applied 14, 014072 (2020).
  * Pelofske  _et al._ (2022) Elijah Pelofske, Andreas Bartschi, and Stephan Eidenbenz, “Quantum volume in practice: What users can expect from nisq devices,” IEEE Transactions on Quantum Engineering 3, 1–19 (2022).
  * Lubinski  _et al._ (2023) 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,” IEEE Transactions on Quantum Engineering 4, 1–32 (2023).
  * Barak  _et al._ (2021) Boaz Barak, Chi-Ning Chou, and Xun Gao, “Spoofing Linear Cross-Entropy Benchmarking in Shallow Quantum Circuits,” in  _12th Innovations in Theoretical Computer Science Conference (ITCS 2021)_, Leibniz International Proceedings in Informatics (LIPIcs), Vol. 185, edited by James R. Lee (Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 2021) pp. 30:1–30:20.
  * Zlokapa  _et al._ (2023) Alexander Zlokapa, Benjamin Villalonga, Sergio Boixo, and Daniel A. Lidar, “Boundaries of quantum supremacy via random circuit sampling,” npj Quantum Information 9, 36 (2023).
  * Aharonov  _et al._ (2023) Dorit Aharonov, Xun Gao, Zeph Landau, Yunchao Liu, and Umesh Vazirani, “A polynomial-time classical algorithm for noisy random circuit sampling,” in  _Proceedings of the 55th Annual ACM Symposium on Theory of Computing_, STOC 2023 (Association for Computing Machinery, New York, NY, USA, 2023) pp. 945–957.
  * Ronnow  _et al._ (2014) Troels F. Ronnow, Zhihui Wang, Joshua Job, Sergio Boixo, Sergei V. Isakov, David Wecker, John M. Martinis, Daniel A. Lidar, and Matthias Troyer, “Defining and detecting quantum speedup,” Science 345, 420–424 (2014).
  * Pokharel and Lidar (2023) Bibek Pokharel and Daniel A. Lidar, “Demonstration of algorithmic quantum speedup,” Physical Review Letters 130, 210602– (2023).
  * Viola and Lloyd (1998) Lorenza Viola and Seth Lloyd, “Dynamical suppression of decoherence in two-state quantum systems,” Phys. Rev. A 58, 2733–2744 (1998).
  * Viola  _et al._ (1999) Lorenza Viola, Emanuel Knill, and Seth Lloyd, “Dynamical decoupling of open quantum systems,” Physical Review Letters 82, 2417–2421 (1999).
  * Zanardi (1999) Paolo Zanardi, “Symmetrizing evolutions,” Physics Letters A 258, 77–82 (1999).
  * Pokharel  _et al._ (2018) Bibek Pokharel, Namit Anand, Benjamin Fortman, and Daniel A. Lidar, “Demonstration of fidelity improvement using dynamical decoupling with superconducting qubits,” Phys. Rev. Lett. 121, 220502 (2018).
  * Souza (2021) Alexandre M. Souza, “Process tomography of robust dynamical decoupling with superconducting qubits,” Quantum Information Processing 20, 237 (2021).
  * Tripathi  _et al._ (2022) Vinay Tripathi, Huo Chen, Mostafa Khezri, Ka-Wa Yip, E. M. Levenson-Falk, and Daniel A. Lidar, “Suppression of crosstalk in superconducting qubits using dynamical decoupling,” Physical Review Applied 18, 024068– (2022).
  * Jurcevic  _et al._ (2021) Petar Jurcevic, Ali Javadi-Abhari, Lev S. Bishop, Isaac Lauer, Daniela F. Bogorin, Markus Brink, Lauren Capelluto, Oktay Günlük, Toshinari Itoko, Naoki Kanazawa, Abhinav Kandala, George A. Keefe, Kevin Krsulich, William Landers, Eric P. Lewandowski, Douglas T. McClure, Giacomo Nannicini, Adinath Narasgond, Hasan M. Nayfeh, Emily Pritchett, Mary Beth Rothwell, Srikanth Srinivasan, Neereja Sundaresan, Cindy Wang, Ken X. Wei, Christopher J. Wood, Jeng-Bang Yau, Eric J. Zhang, Oliver E. Dial, Jerry M. Chow, and Jay M. Gambetta, “Demonstration of quantum volume 64 on a superconducting quantum computing system,” Quantum Sci. Technol. 6, 025020 (2021).
  * rav (2022) _2022 IEEE International Symposium on High-Performance Computer Architecture (HPCA)_ (2022).
  * Jozsa (2001) R. Jozsa, “Quantum factoring, discrete logarithms, and the hidden subgroup problem,” Computing in Science & Engineering 3, 34–43 (2001).
  * Cai and Qiu (2018) Guangya Cai and Daowen Qiu, “Optimal separation in exact query complexities for simon’s problem,” Journal of Computer and System Sciences 97 (2018), 10.1016/j.jcss.2018.05.001.
  * Sloane (2001) N. J. A. Sloane, “The On-Line Encyclopedia of Integer Sequences: Erdös-Borwein constant,”  (2001).
  * Ezzell  _et al._ (2023) Nic Ezzell, Bibek Pokharel, Lina Tewala, Gregory Quiroz, and Daniel A. Lidar, “Dynamical decoupling for superconducting qubits: A performance survey,” Physical Review Applied 20, 064027– (2023).
  * Zhou  _et al._ (2023) Zeyuan Zhou, Ryan Sitler, Yasuo Oda, Kevin Schultz, and Gregory Quiroz, “Quantum crosstalk robust quantum control,” Physical Review Letters 131, 210802– (2023).
  * Genov  _et al._ (2017) Genko T. Genov, Daniel Schraft, Nikolay V. Vitanov, and Thomas Halfmann, “Arbitrarily accurate pulse sequences for robust dynamical decoupling,” Physical Review Letters 118, 133202– (2017).
  * Quiroz and Lidar (2013) Gregory Quiroz and Daniel A. Lidar, “Optimized dynamical decoupling via genetic algorithms,” Phys. Rev. A 88, 052306– (2013).
  * Zantema (2022) Hans Zantema, “Complexity of Simon’s problem in classical sense,” arXiv e-prints (2022), 2211.01776 .
  * Poblete  _et al._ (2006) Patricio V Poblete, J Ian Munro, and Thomas Papadakis, “The binomial transform and the analysis of skip lists,” Theoretical computer science 352, 136–158 (2006).
  * Temme  _et al._ (2017) Kristan Temme, Sergey Bravyi, and Jay M. Gambetta, “Error mitigation for short-depth quantum circuits,” Physical Review Letters 119, 180509– (2017).
  * Srinivasan  _et al._ (2022) Siddarth Srinivasan, Bibek Pokharel, Gregory Quiroz, and Byron Boots, “Scalable measurement error mitigation via iterative bayesian unfolding,” arXiv e-prints (2022), 2210.12284 .