# Verifiable measurement-based quantum random sampling with trapped ions

Martin Ringbauer<EMAIL_ADDRESS>Universität Innsbruck, Institut
für Experimentalphysik, Technikerstrasse 25, 6020 Innsbruck, Austria  Marcel
Hinsche  Dahlem Center for Complex Quantum Systems, Freie Universität Berlin,
14195 Berlin, Germany  Thomas Feldker  Universität Innsbruck, Institut für
Experimentalphysik, Technikerstrasse 25, 6020 Innsbruck, Austria  Alpine
Quantum Technologies GmbH, 6020 Innsbruck, Austria  Paul K. Faehrmann  Dahlem
Center for Complex Quantum Systems, Freie Universität Berlin, 14195 Berlin,
Germany  Juani Bermejo-Vega  Dahlem Center for Complex Quantum Systems, Freie
Universität Berlin, 14195 Berlin, Germany  Departamento de Electromagnetismo y
Física de la Materia, Avenida de la Fuente Nueva, 18071 Granada, Universidad
de Granada, Granada, Spain  Institute Carlos I for Theoretical and
Computational Physics, Campus Universitario Fuentenueva, Calle Dr. Severo
Ochoa, 18071, Granada, Spain.  Claire Edmunds  Universität Innsbruck, Institut
für Experimentalphysik, Technikerstrasse 25, 6020 Innsbruck, Austria  Lukas
Postler  Universität Innsbruck, Institut für Experimentalphysik,
Technikerstrasse 25, 6020 Innsbruck, Austria  Roman Stricker  Universität
Innsbruck, Institut für Experimentalphysik, Technikerstrasse 25, 6020
Innsbruck, Austria  Christian D. Marciniak  Universität Innsbruck, Institut
für Experimentalphysik, Technikerstrasse 25, 6020 Innsbruck, Austria  Michael
Meth  Universität Innsbruck, Institut für Experimentalphysik, Technikerstrasse
25, 6020 Innsbruck, Austria  Ivan Pogorelov  Universität Innsbruck, Institut
für Experimentalphysik, Technikerstrasse 25, 6020 Innsbruck, Austria  Rainer
Blatt  Universität Innsbruck, Institut für Experimentalphysik,
Technikerstrasse 25, 6020 Innsbruck, Austria  Alpine Quantum Technologies
GmbH, 6020 Innsbruck, Austria  Institut für Quantenoptik und
Quanteninformation, Österreichische Akademie der Wissenschaften, Otto-
Hittmair-Platz 1, 6020 Innsbruck, Austria  Philipp Schindler  Universität
Innsbruck, Institut für Experimentalphysik, Technikerstrasse 25, 6020
Innsbruck, Austria  Jens Eisert  Dahlem Center for Complex Quantum Systems,
Freie Universität Berlin, 14195 Berlin, Germany  Helmholtz-Zentrum Berlin für
Materialien und Energie, 14109 Berlin, Germany  Fraunhofer Heinrich Hertz
Institute, 10587 Berlin, Germany  Thomas Monz  Universität Innsbruck, Institut
für Experimentalphysik, Technikerstrasse 25, 6020 Innsbruck, Austria  Alpine
Quantum Technologies GmbH, 6020 Innsbruck, Austria  Dominik Hangleiter
<EMAIL_ADDRESS>Joint Center for Quantum Information and Computer Science
(QuICS), University of Maryland & NIST, College Park, MD 20742, USA  Joint
Quantum Institute (JQI), University of Maryland & NIST, College Park, MD
20742, USA

(August 0 d , 2024)

###### Abstract

Quantum computers are now on the brink of outperforming their classical
counterparts. One way to demonstrate the advantage of quantum computation is
through quantum random sampling performed on quantum computing devices.
However, existing tools for verifying that a quantum device indeed performed
the classically intractable sampling task are either impractical or not
scalable to the quantum advantage regime. The verification problem thus
remains an outstanding challenge. Here, we experimentally demonstrate
efficiently verifiable quantum random sampling in the measurement-based model
of quantum computation on a trapped-ion quantum processor. We create and
sample from random cluster states, which are at the heart of measurement-based
computing, up to a size of $4\times 4$ qubits. By exploiting the structure of
these states, we are able to recycle qubits during the computation to sample
from entangled cluster states that are larger than the qubit register. We then
efficiently estimate the fidelity to verify the prepared states—in single
instances and on average—and compare our results to cross-entropy
benchmarking. Finally, we study the effect of experimental noise on the
certificates. Our results and techniques provide a feasible path toward a
verified demonstration of a quantum advantage.

In _quantum random sampling_ , a quantum device is used to produce samples
from the probability distribution generated by a random quantum computation
hangleiter_computational_2023. This is a particularly challenging task for a
classical computer asymptotically aaronson_computational_2013;
bremner_average-case_2016; bouland_complexity_2019 and in practice
pan_solving_2022; kalachev_classical_2021 and thus at the center of recent
demonstrations of a quantum advantage arute_quantum_2019_short;
zhu_quantum_2022_short; zhong_phase-programmable_2021; madsen_quantum_2022. A
key challenge for such experiments, however, is to verify that the produced
samples indeed originate from the probability distribution generated by the
correct random quantum computation. Verification based only on classical
samples from the device is fundamentally inefficient hangleiter_sample_2019.
In practice, the verification problem has been approached using so-called
linear _cross-entropy benchmarking_ (XEB) boixo_characterizing_2018;
arute_quantum_2019_short. The corresponding _XEB score_ is obtained by
averaging the ideal probabilities corresponding to the observed experimental
samples. XEB is appealing since it has been argued that even achieving any
non-trivial XEB score might be a classically computationally intractable task
aaronson_complexity-theoretic_2017; aaronson_classical_2020 and that it can be
used to sample-efficiently estimate the _quantum fidelity_ of the experimental
quantum state arute_quantum_2019_short; choi_emergent_2021. However, XEB
requires a classical simulation of the implemented circuits to obtain the
ideal output distribution. The computational run-time of estimating XEB from
samples thus scales exponentially, rendering it practically infeasible in the
quantum advantage regime. Moreover, it is not always a good measure of the
quantum fidelity gao_limitations_2021; ware_sharp_2023; morvan_phase_2023.
Another way classical verification of quantum devices has been approached is
via interactive proof systems brakerski_cryptographic_2018;
mahadev_classical_2018, albeit at the cost of large device overheads
zhu_interactive_2021-1; stricker_towards_2022. Hence, classical approaches to
verification have limited applicability for devices operating in the quantum
advantage regime.

Figure 1:  Overview of the experiment. (a) Sketch of the ion trap quantum
processor. Strings of up to 16 ions are trapped in a linear chain. Any single
ion or pair of ions can be individually addressed by means of steerable,
tightly focused laser beams (dark red) to apply resonant operations
$\mathrm{R}_{j}$ or Mølmer-Sørensen entangling gates $\mathrm{MS}_{i,j}$.
Global detection, cooling (blue), and repumping (pink) beams are used to
perform a mid-circuit reset of part of the qubit register Ringbauer2021. (b)
Implemented cluster states. Cluster states with local rotation angles
$\beta_{i}\in\\{0,\frac{\pi}{4},\ldots,\frac{7\pi}{4}\\}$ up to a size of
$4\times 4$ qubits are created in the qubit register. Each cluster state is
defined by its $N$ stabilizers $S_{k}$ which are given by rotated $X$
operators $\tilde{X}_{k}=X_{k}(\beta_{k})$ at each site $k=1,\ldots,N$
multiplied with $Z$ operators on the respective neighbouring sites. (c)
Recycling of qubits. Using sub-register reset of qubits, we prepare cluster
states that are larger than the qubit register. For example, using four ions,
we prepare cluster states of size $2\times 3$. (d) Single-instance
verification. In order to verify single cluster state preparations with fixed
rotation angles $\beta$, we measure it in different bases. To perform fidelity
estimation we measure uniformly random elements of its stabilizer group, which
is obtained by drawing a random product of the $N$ stabilizers $S_{k}$,
indexed by a length-$N$ random bitstring indicating for each $S_{k}$ whether
it participates in the product. To sample from the output distribution, we
measure in the $X$-basis. These samples are verified in small instances by the
empirical total-variation distance (TVD). (e) Average-case verification. To
assess the average quality of the cluster state preparations, we perform
measurements on cluster states with random rotations. By measuring a random
element of the stabilizer group of each random cluster state, we obtain an
estimate of the average fidelity. From the samples from random cluster states
in the $X$-basis, we compute the _cross-entropy benchmark_ (XEB) by averaging
the ideal probabilities $p_{\beta}(x)$ corresponding to the samples $x$ and
the cluster with angles $\beta$.

These challenges raise the question of whether there are quantum verification
techniques that could be used to _efficiently verify_ quantum random sampling
experiments, even when their simulation is beyond the computational
capabilities of classical devices. Answering this question in the affirmative,
we turn to a different universal model of quantum computation— _measurement-
based quantum computing_ (MBQC) raussendorf_one-way_2001;
raussendorf_measurement-based_2003. In contrast to the circuit model, a
computation in MBQC proceeds through measurements, instead of unitary
operations, applied sequentially to an entangled _cluster state_
raussendorf_measurement-based_2003. Roughly speaking, a cluster state on an
$n\times m$ grid of qubits can be used to execute an $n$-qubit, depth-$m$
quantum circuit. Appropriately randomized, cluster states turn out to be a
source of random samples appropriate for demonstrating a quantum advantage via
random sampling gao_quantum_2017; bermejo-vega_architectures_2018;
haferkamp_closing_2020. Crucially, though, each cluster state is fully
determined by a small set of so-called _stabilizer operators_. By measuring
the stabilizer operators using well-characterized single-qubit measurements,
preparations of these cluster states can be efficiently verified
flammia_direct_2011; hangleiter_direct_2017; Saggio2018;
dangniam_optimal_2020; hangleiter_sampling_2021; tiurev_fidelity_2021.

Here, we experimentally demonstrate efficiently verifiable quantum random
sampling in the MBQC model in two _trapped-ion quantum processors_ (TIQP).
While cluster state generation in TIQP has previously been limited to a size
of $2\times 2$ lanyon_measurement-based_2013, we overcome this limitation with
a two-fold approach. First, we use pairwise addressed Mølmer-Sørensen
entangling operations Ringbauer2021; Pogorelov2021 in a fully connected linear
chain to enable the efficient generation of clusters up to a size of $4\times
4$ qubits. Second, we make use of spectroscopic decoupling and optical pumping
schindler_quantum_2013 to perform mid-circuit readout and reset of qubits in
order to recycle them. In this way, we are able to sequentially measure rows
of the cluster and then reuse the measured qubits to prepare a new row of the
cluster, while maintaining entanglement with the remaining qubits, see Fig.
1(c). This allows us to sample from a cluster state on a lattice that is
larger than the size of the physical qubit register. This combination of
techniques provides a feasible path towards generating large-scale entangled
cluster states using trapped ions.

We then estimate the fidelity of the experimental cluster states in order to
verify those states. Specifically, we apply a novel variant of _direct
fidelity estimation_ flammia_direct_2011; hangleiter_sampling_2021 to estimate
the single-instance fidelity of a fixed cluster state, and the average
fidelity of random cluster states. The single-instance fidelity certifies the
samples from a fixed, random cluster state, and therefore a quantum advantage
for sufficiently large cluster states hangleiter_direct_2017. Conversely, the
average fidelity of random cluster states is a benchmark of the average
performance of the quantum processor in the quantum advantage regime
eisert_quantum_2020. Direct (average) fidelity estimation is therefore a
unified framework for verification and benchmarking of MBQC, analogously to
XEB. However, in contrast to XEB, the fidelity estimation approach has several
major advantages: First, it is efficient in terms of both the required number
of experiments, and the complexity of the postprocessing. Second, it requires
knowledge only of the measurement noise as opposed to the noise properties of
all gates which is required for XEB gao_limitations_2021; ware_sharp_2023;
morvan_phase_2023. Finally, the fidelity gives a rigorous bound on the quality
of the samples from a single quantum state, whereas XEB is generally only
accurate on average.

In order to assess the performance of the fidelity-derived certificates, we
compare them to the available—but inefficient—classical means of certification
of the samples, which is still possible in our proof-of-principle
demonstration. In the single-instance case, we compare the experimental
performance of the single-instance fidelity estimate to the empirical total-
variation distance of the sampled distribution. In the average case, we
compare the average fidelity estimate to the average XEB score. Additionally,
we study the effect of native noise sources on the different measures of
quality.

Our work thus provides a clear and feasible path towards verified quantum
advantage. It does so by developing a new approach to verifying random cluster
states based on a variant of direct fidelity estimation, introducing the use
of qubit recycling in order to generate large clusters, and demonstrating the
feasibility of the proposed techniques in the presence of experimental noise.

Figure 2:  Sketch of the circuit with qubit recycling. (a) Recycling. After
detection, a measured qubit is either still in the $|{1}\rangle$ state (“dark”
outcome) or in one of the two S levels (“bright” outcome). We reset it to the
$|{0}\rangle$ state by first applying an addressed $\pi$-pulse (1) on the
$|{S^{\prime}}\rangle\rightarrow|{D^{\prime}}\rangle$-transition. A subsequent
global $854\text{\,}\mathrm{nm}$ quench pulse (2) transfers population from
all D-levels to the P3/2 manifold, from which (3) spontaneous decay occurs,
preferentially to the $|{0}\rangle$ state in the S manifold. We repeat this
process twice, which is sufficient to return about 99% of the population to
the $|{0}\rangle$ state. (b) Circuit. The individual qubits are prepared in a
product state depending on the random angles $\beta_{i}$ and entangled via
$XX$ interactions and some single-qubit gates (white boxes) to create a
cluster state; see the SI, Section S3 for details. The measurement of the
qubits is achieved by exciting the $P\leftrightarrow S$ transition. In order
to perform a circuit with recycling, a coherent $\pi$-pulse on the
$S\rightarrow D^{\prime}$ transition (denoted by HS) is applied to ‘hide’ the
qubits which should not be measured in the D-manifold. After the measurement,
the chain is cooled using polarization-gradient cooling. The reset makes use
of local pulses on the measured qubit that transfer the remaining population
of $|{S^{\prime}}\rangle$ to the D5/2-manifold (denoted by P) and global
pulses that transfer the population of that manifold back to $|{0}\rangle$.
Prior to the reset, all unmeasured qubits are ‘hidden’ in the S1/2-manifold.
For this, the population which was in $|{0}\rangle$ prior to the measurement
is coherently transferred back to $|{S}\rangle$ via a $\pi$-pulse
(H${}_{S}^{-1}$), and the population which is in $|{1}\rangle$ is transferred
to $|{S^{\prime}}\rangle$ via a $\pi$-pulse on the $D\rightarrow S^{\prime}$
transition (HD). After the reset procedure (a), a $\pi$-pulse (H${}_{D}^{-1}$)
is applied to the unmeasured qubits to transfer the population which was
previously in $|{1}\rangle$ back from $S^{\prime}$.

Sampling and verification protocols. In the circuit model, natural examples of
random computations are, for instance, circuits composed of Haar-random two-
qubit gates brandao_local_2016, or composed of native entangling gates and
random single-qubit gates arute_quantum_2019_short. In contrast, in MBQC, a
universal quantum computation can be realized by adaptively performing single-
qubit rotations around the $Z$-axis on a cluster state and measuring in the
Hadamard basis conditioned on the outcomes of previous Hadamard-basis
measurements raussendorf_measurement-based_2003; mantri_universality_2017;
haferkamp_closing_2020. This leads to a natural notion of random MBQC wherein
those single-qubit $Z$-rotations are applied with angles chosen randomly from
an appropriate discretization of the unit circle bermejo-
vega_architectures_2018; haferkamp_closing_2020. Adaptively performing single-
qubit rotations then becomes superfluous since they are chosen randomly
anyway, and an outcome pattern on the square lattice defines both, an
effective quantum circuit given the random rotations, and the outcomes of
measuring that circuit. Hence, repeatedly measuring a fixed, random cluster
state without adaptive rotations is equivalent to measuring many different
quantum circuits chosen randomly from an ensemble defined by the random
rotations, see Fig. S2 of the Supplementary Information (SI) for details.

The largest discretization in the choice of single-qubit rotations leading to
a computationally universal MBQC scheme consists of eight evenly spaced
angles, corresponding to powers of the $T$ gate. In exactly the same way as
for circuit-based sampling schemes bremner_average-case_2016;
boixo_characterizing_2018, there is strong complexity-theoretic evidence that
for $m\gtrsim n$ approximately reproducing the outcome statistics of such
random measurements is classically intractable bermejo-
vega_architectures_2018; haferkamp_closing_2020. In fact, in both cases, even
producing samples from a quantum state with a non-vanishing or only slowly
vanishing fidelity is likely classically hard gao_limitations_2021;
aharonov_polynomial-time_2022. Quantum advantage aside, the effective
computations implemented by random cluster states generate a unitary
$2$-design haferkamp_closing_2020 and therefore yield a reliable average-
performance benchmark for measurement-based computations
heinrich_general_2022.

Concretely, the MBQC random sampling protocol we apply is then the following
bermejo-vega_architectures_2018; haferkamp_closing_2020 (see Fig. 1, and
Section S3 of the SI for explicit circuits):

  1. 1.

Prepare a cluster state on $N=n\times m$ qubits on a rectangular lattice by
preparing each qubit in the $|{+}\rangle$ state and applying controlled-$Z$
gates between all neighbors.

  2. 2.

Apply single-qubit rotations $Z(\beta)=\mathrm{e}^{-\mathrm{i}\beta Z/2}$ with
random angles $\beta\in\\{0,\frac{\pi}{4},\ldots,\frac{7\pi}{4}\\}$ to every
qubit.

  3. 3.

Measure all qubits in the Hadamard basis.

We note that the state preparation steps 1 and 2 can also be achieved by time-
evolving an initial state $|{+}\rangle^{\otimes N}$ under an Ising Hamiltonian
on an $n\times m$ lattice with random local fields depending on the
$\beta_{k}$ bermejo-vega_architectures_2018; haferkamp_closing_2020, but the
gate-based approach outlined here is more suitable for TIQP.

Using a variant of direct fidelity estimation (DFE), we assess the quality of
both single cluster states with local $Z$ rotations, and the average quality
of such state preparations. In DFE, we estimate the fidelity
$F(\rho,|{\psi}\rangle\langle{\psi}|)=\langle{\psi}|\rho|{\psi}\rangle$ of a
fixed experimental state $\rho$ by measuring random operators from the
_stabilizer group_ of the random cluster state $|{\psi}\rangle$ and averaging
the results, see Methods for detail. The stabilizer group is the group
generated by the $N$ stabilizers of the random cluster. Each stabilizer
$S_{k}$ is the product of a rotated $X$-operator at site $k$—given by
$X_{k}(\beta)=\mathrm{e}^{-\mathrm{i}\beta X_{k}/2}$—and $Z$-operators on the
neighboring sites, giving rise to a characteristic star shape on the square
lattice, see Fig. 1(b). Importantly, all elements of the stabilizer group are
products of single-qubit operators. Our trust in the fidelity estimate
therefore only depends on our ability to reliably perform single-qubit
measurements, which we verify. In order to measure the average fidelity over
the set of cluster states, we prepare random cluster states and for each state
measure a random element of its stabilizer group. We then average the results
to obtain an estimate of the average fidelity. At a high level, fidelity
estimation thus exploits our ability to measure the experimental state in
different bases. It requires a number of experimental state preparations that
is _independent_ of the size of the system, making it scalable to arbitrary
system sizes, see Methods for details. We note that we also measured a witness
for the fidelity hangleiter_direct_2017 and find that it is not practical in a
scalable way for noisy state preparations, as we detail in Section S1 of the
SI.

Given the relatively small system sizes of the experiments in this work, we
are also able to directly compute non-scalable measures of quality that make
use of the classical samples only. This enables us to compare fidelity
estimation with inefficient classical verification methods in different
scenarios. To classically assess the quality of samples from a fixed
experimental state preparation, we use the _total-variation distance_ (TVD)
${d_{\text{TV}}(P,Q)=\sum_{x}|P(x)-Q(x)|/2}$. The TVD quantifies the optimal
probability of distinguishing the experimentally sampled distribution $Q$ and
the ideal one for a noiseless cluster $P$. The TVD is the classical analog of
the trace distance
$d_{\operatorname{Tr}}(\rho,|{\psi}\rangle\langle{\psi}|)=\operatorname{Tr}(|\rho-|{\psi}\rangle\langle{\psi}||)/2$,
which quantifies the optimal probability of distinguishing the sampled quantum
states $\rho$ and $|{\psi}\rangle\langle{\psi}|$. The fidelity $F$ upper-
bounds the trace distance fuchs_cryptographic_1999 and therefore the TVD of
the sampled distributions as

$\displaystyle d_{\text{TV}}\leq d_{\operatorname{Tr}}\leq\sqrt{1-F}.$ (1)

The root infidelity $\sqrt{1-F}$ can therefore be used to certify the
classical samples from $\rho$. We note that it is a priori not clear how tight
this bound is in an experimental scenario and how experimental noise affects
the different verification methods. In order to classically assess the average
quality of the quantum device, we estimate the linear XEB fidelity between $Q$
and $P$, which is defined as $f_{\textsf{lin}}(Q,P)=2^{n}\sum_{x}Q(x)P(x)-1$
hangleiter_computational_2023. The average XEB fidelity over the random
cluster states measures the average quantum fidelity in the regime of low
noise gao_limitations_2021; ware_sharp_2023; morvan_phase_2023, see Section S5
of the SI for details.

Experimental implementation. We implement the random MBQC sampling and
verification protocols in two ion-trap quantum processors. Quantum information
is encoded in the S1/2 ground state and D5/2 excited state of up to 16 40Ca+
ions confined in a linear Paul trap schindler_quantum_2013; Pogorelov2021. We
use these devices to implement two sets of experiments. First, we generate
rectangular $n\times m$ random cluster states of up to 16 ions by
appropriately entangling the respective ions in a linear chain using pairwise
addressed Mølmer-Sørensen-gates Ringbauer2021; Pogorelov2021. In a second,
proof-of-principle set of experiments on a device with an extended control
toolbox yet somewhat lower fidelities, we make use of spectroscopic decoupling
and optical pumping to recycle qubits to demonstrate a more qubit-efficient
way to sample from large-scale entangled cluster states. By construction, the
2D cluster states require entangling gates between neighboring qubits only. As
a consequence, when generating the cluster from top to bottom, once the first
row has been entangled to the second, we can measure the qubits of the first
row. Once measured, these qubits can be reset to the ground state, prepared in
their appropriate initial states and entangled as the third row of the cluster
state, and so on. Due to the local entanglement structure of the cluster
state, the measurement statistics obtained in this way are identical to the
statistics that would be obtained from preparing and measuring the full
cluster state at once.

Experimentally, we make use of mid-circuit readout capabilities Stricker2020
using an EMCCD camera to read out a subset of the qubits, while
spectroscopically decoupling the remaining qubits from the readout beams, see
Fig. 2. After the readout, we re-cool the ion string using a combination of
Doppler cooling and polarization-gradient cooling for a total of
$3\text{\,}\mathrm{ms}$. Then we employ two rounds of optical pumping using
addressed $729\text{\,}\mathrm{nm}$ pulses in combination with a global
$854\text{\,}\mathrm{nm}$ quench beam to reset the qubits to the $|{0}\rangle$
ground state schindler_quantum_2013, while the remaining qubits are
spectroscopically decoupled. This completes the reset and we can now prepare
the measured qubits in their new states and entangle them to the remaining
qubits of the cluster, see Fig. 2. This procedure enables us to sample from
entangled quantum states with more qubits than the physical register size of
the used quantum processor. Specifically, to prepare an $n\times m$ cluster
state at least $n+1$ repeatedly recycled qubits are required, and the required
circuit depth (and recycling steps) decreases as the number of available
physical qubits increases.

For every state, we perform sampling and verification measurements. We measure
the state in the Hadamard basis in order to perform sampling. For
verification, we measure a random element of its stabilizer group. When
verifying a single instance of a state preparation, we repeat this procedure
for a fixed state and then estimate the fidelity from the random stabilizer
measurements and the TVD from the classical samples. To estimate the average
performance of the device, we repeat the procedure for random states and
estimate the average fidelity and the average XEB fidelity, see Fig. 1(d,e).
Finally, for the $2\times 2$ cluster, we study the effect of increasing global
(local) dephasing noise on the verification performance by adding small
(un)correlated random $Z$-rotations before and after each entangling gate.

Figure 3:  Experimental results for single-instance verification. Root
infidelity estimate $\sqrt{1-F}$ (hexagons), and empirical TVD (stars) for
single instances of random MBQC cluster states with recycling (blue) and
without (pink). Note that the horizontal axis is labelled with the cluster
size $n\times m$ and scaled with qubit number $n\,m$. The root infidelity
upper-bounds the TVD per Eq. 1. Colored error bars represent the 3$\sigma$
interval of the statistical error. Uncorrelated measurement noise reduces or
increases the measured state fidelity compared to the true fidelity
asymmetrically depending on its value, such that the shown values are lower
bounds to the true state fidelity, see the Methods section for details. The
worst-case behaviour of the measurement noise is represented by gray error
bars. In the non-recycling experiment, the register size is increased between
the $2\times 3$ and the $3\times 3$ instance, leading to a decrease in the
local gate fidelities. Modeling the noise as local depolarizing noise after
each entangling gate (dotted lines), we obtain effective local Pauli error
probabilities after the two-qubit gates of 5.3%, 2.6%, and 1.0%, for the
recycling data, for the large-register non-recycling data, and the small
register non-recycling data, respectively; see Section S5 of the SI. The
shaded green area is the acceptance region corresponding to an infidelity
threshold of 8.6% arising in the rigorous hardness argument as sketched in
Section S4 of the SI. Since the accuracy of the TVD estimate scales with the
system dimension already for cluster sizes of $4\times 3$ and $4\times 4$
infeasible amount of samples would be required for an accurate estimate, and
hence these are not shown. See Table S1 of the SI for experimental details.
Figure 4:  Single-instance verification with artificially added phase noise.
Root infidelity estimate $\sqrt{1-F}$ (hexagons) and empirical total-variation
distance $d_{\text{TV}}$ (stars) of a $2\times 2$ cluster state with
artificially introduced local (pink) and global (green) phase
noise—$Z$-rotations with rotation angle drawn from a Gaussian distribution
with variance $\sigma^{2}$—before and after Mølmer-Sørensen gate applications
as a function of the noise strength $\sigma$, see Methods for details. Solid
(dashed) lines show simulated root infidelity (total-variation distance) for
the respective types of noise. The experimental data (top axis) is shifted
with respect to the simulations (bottom axis) due to the fact that there is
residual noise when no artificial noise is introduced. The value of the
relative shift given by $0.045\pi$ (dashed vertical line) provides an estimate
for the natural noise strength. Colored error bars represent the 3$\sigma$
interval of the statistical error. The systematic measurement error of the
fidelity estimate is represented by gray error bars.

Results. We first measure the fidelity and TVD of single random cluster state
preparations for various cluster sizes. The results demonstrate that the root-
infidelity provides meaningful upper bounds on the TVD, see Fig. 3.
Importantly, while the efficiently measurable and computable root infidelity
estimate is guaranteed to bound the TVD per Eq. 1, these scalable bounds are
not tight. This is seen in Fig. 3 as a gap between the root infidelity upper
bound and the measured TVD values. Indeed, it is expected that reproducing the
full quantum state (as measured by the fidelity) is a more stringent
requirement than merely reproducing the outcome distribution in one particular
measurement basis (as measured by the TVD). Hence, the efficient quantum
methods require higher fidelities for the corresponding certificate to meet
the quantum advantage threshold. Notably, above the cluster size of $3\times
3$ qubits, empirically estimating the TVD with sufficient accuracy is
practically infeasible due to the exponentially growing state space. In the
proof-of-principle experiments, where recycling is used, we see the same
qualitative behavior, although the overall root infidelities are higher. This
is likely due to imperfect re-cooling, which only cools the system to low
motional occupation of $\mathrm{bar}n\sim 2$ phonons. While the _Mølmer-
Sørensen_ (MS) gate is insensitive to the motional occupation to first order
Kirchmair2009, higher phonon number leads to a larger sensitivity to
calibration errors. Moreover, the recooling process takes
$3\text{\,}\mathrm{ms}$, during which the system experiences some dephasing.
Hence, the recycling and non-recycling experiments are not directly
comparable. It is, however, anticipated that the technical limitations can be
overcome through the use of mid-circuit ground-state cooling and faster
recycling schemes, such that comparable fidelities between the two methods can
be achieved, as would also be required for realizing quantum error correction.

Fig. 4 shows the results of the fidelity and TVD measurements for an
increasing amount of noise on the $2\times 2$ cluster state in comparison to
numerical simulations. We observe an increasing gap between TVD and upper
bound from the root infidelity estimate (cf. Eq. 1) with the amount of noise
in a fixed quantum circuit. These results indicate that output distributions
of states subject to a significant amount of dephasing noise may still have a
TVD well below the root infidelity. Comparing the experimental results with
the simulations also allows us to deduce the natural noise floor in the
experiment.

Figure 5:  Experimental results for average performance verification. Average
fidelity estimate from direct fidelity estimation (DFE) (pink hexagons), from
linear XEB (triangles), and from logarithmic (log) XEB (diamonds, see Methods
for the definition) using $1000$ random cluster states and $50$ shots per
state. Based on calibration data for the gate fidelities of single-qubit gates
$f_{1Q}=99.8\%$, two-qubit gates $f_{2Q}=97.5\pm 0.5\%$, and measurements
$f_{M}=99.85\%$, we compute a prediction for the fidelity (gray shaded line).
We extract an effective local Pauli error probability of $1.7\%$ (dotted
line), see Section S5 of the SI. Colored error bars represent the statistical
$3\sigma$ error. For uncorrelated measurement noise, the fidelity estimate
provides a lower bound to the true state fidelity. Gray error bars represent
the worst-case systematic measurement error.

We then measure the fidelity of cluster state preparations, averaged over the
random circuits and show the results in Fig. 5. We compare the fidelity
estimates to the classical estimates of fidelity via XEB depending on the
relative dimensions of the cluster, since in the circuit model the quality of
XEB as a fidelity estimator depends on the circuit depth ware_sharp_2023;
morvan_phase_2023. We observe a consistently larger variance of the XEB
estimate of the fidelity than of the direct fidelity estimate, and deviates
for the $2\times 5$ cluster. This may be due to the fact that the XEB fidelity
depends on the type and strength of the experimental noise, but also the
specific dimensions of the cluster state and the effective circuit ensemble
gao_limitations_2021; ware_sharp_2023; morvan_phase_2023. Hence, while XEB
generally seems to reflect the order of magnitude of the true fidelity,
extreme care must be taken when using the XEB as an estimator of the fidelity.

Discussion and conclusion. We conclude that direct (average) fidelity
estimation provides an efficient and scalable means of certifying both single
instances and the average quality of measurement-based computations. This is
the case since the sample complexity of the fidelity estimate for arbitrary
generalized stabilizer states is independent of the size of the system and the
postprocessing is efficient. Larger systems can therefore be verified with the
same number of experiments as we have performed.

More generally, our results demonstrate that the measurement-based model of
quantum computation provides a viable path toward efficient verification of
quantum random sampling experiments, which is not known to be possible in the
circuit model. In particular, all known methods for fidelity estimation
flammia_direct_2011; huang_predicting_2020 in general scale exponentially with
the number of qubits. We also note that, although MBQC is formally equivalent
to the circuit model, relating a quantum circuit to an MBQC requires a space-
time mapping and a feedforward procedure. Hence, our verification protocol at
the level of the cluster state has no direct analog in circuit-based
computations. While the experiments in this work are still far from the
quantum advantage regime, we have successfully demonstrated how to use qubit
recycling to perform large-scale MBQC with a qubit number that can be
quadratically larger than the used ion register. This will enable trapped-ion
quantum processors comprising on the order of 100 ions and depth 50 to achieve
a fully verified quantum advantage in sampling from cluster states with more
than $50\times 50$ nodes.

Besides trapped ions, several other platforms are compelling candidates for
demonstrating a verifiable quantum advantage via random cluster state
sampling. Examples include arrays of Rydberg atoms in optical tweezers, where
the creation of large atom arrays manetsch_tweezer_2024 has recently been
demonstrated. Another leading platform for cluster state generation is
photonics Istrati2020, and continuous-variable optical systems where cluster
states with up to 30 000 nodes have been experimentally prepared
Asavanant2019; Larsen2019. Currently, these states are still Gaussian states
and therefore not useful for quantum computing, but it is intriguing to think
about how the non-standard topologies of continuous-variable cluster states
might be exploited. Traditionally, such continuous variable systems have been
used for boson sampling, rather than quantum circuit sampling. While boson
sampling is not a universal model for computation, its efficient verification
is possible for both photon-number chabaud_efficient_2021 and Gaussian
aolita_reliable_2015 input states. In practice, however, the verification
measurements are entirely different in type compared to the sampling
experiments, requiring a different apparatus. In contrast, for verifying MBQC
states as performed in this work, the difference between sampling and
verification is only local basis rotations. This makes MBQC a particularly
compelling candidate for verifiable quantum random sampling.

## Methods

### Verification protocols

MBQC with cluster states is amenable to various types of verification. In
particular, we can perform single-instance verification, that is, verification
of a single quantum state using many copies of that state. We also perform
average verification, that is, an assessment of the quality of state
preparations averaged over the ensemble of measurement-based computations
defined by the random choices of single-qubit rotation angles $\beta$. We
distinguish classical means of verification in which we only make use of
classical samples from the cluster state measured in a fixed (the Hadamard)
basis, and quantum means of verification in which we measure the cluster state
in various different bases.

##### Single-instance verification.

In order to perform single-instance verification we apply direct fidelity
estimation flammia_direct_2011, which uses single-qubit measurements on
preparations of the target state $|{\psi}\rangle$. Since the target state
vector $|{\psi}\rangle$ for our random sampling problem is a locally rotated
stabilizer state, with stabilizer operators $S_{i}$,
$\rho=|{\psi}\rangle\langle{\psi}|$ is the projector onto the joint
$+1$-eigenspace of its $N$ stabilizers. We can therefore expand $\rho$ as the
uniform superposition over the elements of its stabilizer group
$\mathcal{S}=\langle S_{1},\ldots,S_{N}\rangle$, where $\langle
S_{1},\ldots,S_{N}\rangle$ denotes the multiplicative group generated by
$S_{1},\ldots,S_{N}$. The fidelity can then be expressed as

$\displaystyle F$ $\displaystyle=\frac{1}{2^{N}}\sum_{s\in\mathcal{S}}\langle
s\rangle_{\rho}=\frac{1}{2^{N}}\sum_{s\in\mathcal{S}}\sum_{\sigma=\pm
1}\langle\pi_{s}^{\sigma}\rangle_{\rho}\cdot\sigma,$ (2)

where $s=\pi_{s}^{+}-\pi_{s}^{-}$ is the eigendecomposition of the stabilizer
$s$ into its $\pm 1$ subspaces, and
$\langle\cdot\rangle_{\rho}=\operatorname{Tr}[\rho\cdot]$ denotes the
expectation value. This suggests a simple verification protocol where in each
run a uniformly random element of $\mathcal{S}$ is measured on $\rho$.
Averaging over the measurement outcomes $\sigma$ then gives an unbiased
estimate of the fidelity according to Eq. 2. Since the measurement outcomes
$\sigma$ are bounded by $1$ in absolute value, we can estimate the average up
to error $\epsilon$ using a number $M$ of measurements from $\mathcal{S}$ that
scales as $1/\epsilon^{2}$ and is independent of the number of qubits.

We also directly estimate the TVD between the empirical distribution and the
ideal distribution. Note that estimating the TVD is sample-inefficient since
the empirical probabilities need to be estimated, requiring exponentially many
samples hangleiter_sample_2019. It is also computationally inefficient since
the ideal probabilities need to be computed.

##### Average-case verification.

We measure the average quality of the cluster state preparations
$\rho_{\beta}$ by their average state fidelity

$\displaystyle\overline{F}\coloneqq\operatorname{\mathbb{E}}_{\beta}[\langle{\psi_{\beta}}|\rho_{\beta}|{\psi_{\beta}}\rangle]$
(3)

with the generalized cluster state $|{\psi_{\beta}}\rangle$ with random angles
$\beta\in\\{0,\frac{\pi}{4},\ldots,\frac{7\pi}{4}\\}^{n\times m}$. Here,
$\mathbb{E}_{\beta}[\cdot]$ denotes the expectation value over random
$\beta\in[8]^{nm}$, where we let $[8]=\\{1,2,\ldots,8\\}$ and
$[k]^{l}=[k]\times\cdots\times[k]$ $l$ times.

In order to classically estimate the average state fidelity, one can make use
of _cross-entropy benchmarking_ (XEB) as proposed by
boixo_characterizing_2018; arute_quantum_2019_short. XEB makes use of the
classical samples from a distribution $Q$ and aims to measure how distinct $Q$
is from a target distribution $P$. The linear and logarithmic XEB fidelities
between $Q$ and $P$ are defined as

$\displaystyle f_{\textsf{lin}}(Q,P)$ $\displaystyle\coloneqq
2^{n}\sum_{x}Q(x)P(x)-1,$ (4) $\displaystyle f_{\textsf{log}}(Q,P)$
$\displaystyle\coloneqq-\sum_{x}Q(x)\log P(x),$ (5)

respectively. Letting $P_{\beta}$ be the output distribution of
$|{\psi_{\beta}}\rangle$ and $Q_{\beta}$ the output distribution of
$\rho_{\beta}$ after Hadamard-basis measurements, we can estimate the average
state fidelity from the average linear (logarithmic) XEB fidelity

$\displaystyle\overline{f}_{{\textsf{lin}}\,({\textsf{log}})}$
$\displaystyle\coloneqq\mathbb{E}_{\beta}\left[f_{{\textsf{lin}}\,({\textsf{log}})}(Q_{\beta},P_{\beta})\right],$
(6)

assuming that the total noise affecting the experimental state preparation
$\rho_{\beta}$ is not correlated with
$|{\psi_{\beta}}\rangle\langle{\psi_{\beta}}|$. In order to estimate the
(average) XEB fidelities, we need to compute the ideal output probabilities
$P_{\beta}(x)$ and average those over the observed samples $x$. This renders
the XEB fidelities a computationally inefficient estimator of the fidelity.
They are _sample-efficient_ estimators, hangleiter_sampling_2021, however,
provided that the target distribution $P_{\beta}$ satisfies the expected
exponential shape for deep random quantum circuits (or larger cluster states).
That is, to achieve an additive estimation error $\epsilon$, a polynomial
number of samples in $n$ and $1/\epsilon$ are required. In Section S5 of the
SI, we provide the details of the estimation procedure.

To date, XEB is the only available means of practically verifying (on average
or in the single-instance) universal random quantum circuits.

Here, we observe that in the measurement-based model of quantum computations
_fully efficient_ (i.e., computationally and sample-efficiently) average-case
verification is possible using single-qubit measurements. In fact, we observe
that direct fidelity estimation can be extended to measure the average
fidelity of random MBQC state preparations. To this end, we observe that the
average state fidelity (3) can be expressed analogously to Eq. 2 as

$\displaystyle\overline{F}=\frac{1}{2^{nm}}\frac{1}{8^{nm}}\sum_{\beta\in\frac{\pi}{4}\cdot[8]^{nm}}\sum_{s_{\beta}\in\mathcal{S}_{\beta}}\sum_{\sigma=\pm
1}\langle\pi_{s_{\beta}}^{\sigma}\rangle_{\rho_{\beta}}\cdot\sigma,$ (7)

where $\mathcal{S}_{\beta}$ denotes the stabilizer group of the locally
rotated cluster state $|{\psi_{\beta}}\rangle$ with rotation angles $\beta$,
$\pi_{s_{\beta}}^{\sigma}$ is the projector onto the $\sigma$-eigenspace of
$s_{\beta}\in\mathcal{S}_{\beta}$, and . Hence, in order to estimate the
average state fidelity with respect to the choice of $\beta$, we simply need
to sample uniformly random rotation angles $\beta$, and elements $s_{\beta}$
from the stabilizer group $\mathcal{S}_{\beta}$ and then measure $s_{\beta}$
on the state preparation $\rho_{\beta}$ of $|{\psi_{\beta}}\rangle$, yielding
outcome $\sigma\in\\{\pm 1\\}$. Averaging over those outcomes yields an
estimator of the average state fidelity with the same sample complexity as
direct fidelity estimation has for a single instance. As discussed below, the
only assumption required to trust the validity of the result is that the noise
in the local single-qubit measurements does not behave adversarially. Direct
fidelity estimation and direct average fidelity estimation thus provide a
unified method for efficiently assessing the single-instance quality and the
average quality of MBQC state preparations.

### Finite sampling and error bars

When performing direct fidelity estimation of a fixed cluster state, the
simplest protocol is to sample an element $s\in\mathcal{S}$ of the stabilizer
group uniformly at random and measure $s$ once; cf. Eq. 2. In this case, the
samples are distributed binomially with ideal probability
$p=\sum_{s}\langle\pi_{s}^{\sigma}\rangle_{\rho}/2^{N}$, and the error on the
mean estimation is given by the standard deviation of the observed binomial
distribution. However, in practice, it is much cheaper to repeat a measurement
of a stabilizer than to measure a new stabilizer, which requires a different
measurement setting. This is why we estimate the fidelity according to the
following protocol. We sample $K$ stabilizers uniformly at random and measure
each of them $M$ times, obtaining an empirical estimate of the conditional
expectation value $\mathbb{E}[\sigma|s]=\sum_{\sigma=\pm
1}\operatorname{Tr}[\rho\pi_{s}^{\sigma}]\sigma$. In Section S6 of the SI, we
show that the variance of the fidelity estimator
$\hat{F}=(KM)^{-1}\sum_{i=1}^{K}\sum_{j=1}^{M}\sigma_{i,j}$, where
$\sigma_{i,j}$ is the outcome of measuring stabilizer $s_{i}$ the
$j^{\text{th}}$ time, is given by

$\displaystyle\operatorname{Var}[\hat{F}]=\frac{4}{KM}(\mathbb{E}[p_{s}](1-\mathbb{E}[p_{s}]))+\frac{4}{K}\left(1-\frac{1}{M}\right)\operatorname{Var}[p_{s}].$
(8)

Here, the expectation value and variance are taken over $s\in\mathcal{S}$ and
$p_{s}=\operatorname{Tr}[\rho\pi_{s}^{+1}]$, respectively. Furthermore, the
same results carry over to the average fidelity estimate, since sampling from
the stabilizer group $\mathcal{S}$ of a single cluster state is now replaced
by sampling a random choice of angles $\beta$, and random element of the
corresponding stabilizer group $\mathcal{S}_{\beta}$, not altering the
variance.

Eq. 8 gives rise to an optimal choice of $K$ and $M$ for a fixed total number
of shots $K\cdot M$, depending on the expectation value and variance of the
stabilizer values $p_{s}$ and the experimental trade-off between repetitions
of the same measurement and changing the measurement setting. In particular,
if the distinct elements of the stabilizer group have a small variance over
the imperfect state preparation $\rho$, a larger choice of $M$ might be
advantageous. In practice, for the instances in which we have abundant data,
we subsample the data in order to remain in the situation $M=1$ of Eq. 2,
while in the case of sparse data, we make use of a larger number of shots $M$
per stabilizer.

The variance of the estimate of the XEB fidelity is also given by the law of
total variance, generalizing Eq. 8, and spelled out in detail in Section S6 of
the SI. Finally, for the TVD, we estimate the error using bootstrapping by
resampling given the observed distribution. Specifically, we repeatedly sample
from the empirical distribution the same number of times as the experiment and
compute the TVD of the samples to the sampled distribution. The resulting TVD
follows a Gaussian distribution of which we show the $3\sigma$ interval
estimated from $1000$ iterations.

### Measurement errors

A key assumption for the efficient verification of the cluster states prepared
here is the availability of accurate, well-characterized single-qubit
measurements. A deviation in the measurement directly translates into a
deviation in the fidelity estimate, and hence a high measurement error in the
worst case translates into a high error in the resulting fidelity estimate.
Because the single-qubit measurements we use comprise single-qubit gates
followed by readout in a fixed basis, the measurement error has two main
contributions: (i) imperfections in the single-qubit rotations for the basis
choice, and (ii) imperfections in the readout.

The single-qubit gate errors are well characterized by randomized
benchmarking, showing an average single-qubit Clifford error rate of $3\pm
2\cdot 10^{-4}$ Ringbauer2021 for the recycling device and $14\pm 1\cdot
10^{-4}$ Pogorelov2021 for the second device. The native $Z$ measurement is
then performed by scattering photons on the short-lived
$\mathrm{S}_{1/2}\leftrightarrow\mathrm{P}_{1/2}$ transition. Ions in the
$|{0}\rangle$ state will scatter photons, while ions in the $|{1}\rangle$
state remain dark. Hence, there are two competing contributions to the readout
error. On the one hand, long measurement times suffer from amplitude damping
noise due to spontaneous decay of the $|{1}\rangle$ state (lifetime $\sim
1.15$s) during readout. On the other hand, for short readout times, the
Poisson distributions for the two outcomes will start to overlap, leading to
discrimination errors. In the experiments presented here, the second
contribution is suppressed to well below $10^{-5}$ by using measurement times
of 1ms for the recycling device and 2ms on the non-recycling device, leaving
only a spontaneous decay error of $<1\cdot 10^{-3}$ schindler_quantum_2013 for
the recycling device and $<2\cdot 10^{-3}$ for the non-recycling device.
Hence, the worst-case readout error is $<1.5\cdot 10^{-3}$ per qubit for the
recycling device and $<3.5\cdot 10^{-3}$ per qubit for the second device.
Given the single-qubit readout error $e_{1}$, the overall measurement error on
an $n$-qubit device is then given by $e_{M}=1-(1-e_{1})^{n}$.

Given a true pre-measurement state fidelity $F$, we consider the effect of the
measurement errors on the estimated fidelity $\hat{F}$. In the one extreme
case, the measurement errors flip the sign of the stabilizers with value $+1$
on the pre-measurement state, but keep the sign of those with a $-1$ outcome,
resulting in a reduced state fidelity
$\hat{F}_{\min}=2((1+F)/2-e_{M}\cdot(1+F)/2)-1$. In the other extreme case,
they flip the sign of only the stabilizers with value $-1$ on the pre-
measurement state yielding $\hat{F}_{\max}=2((1+F)/2+e_{M}\cdot(1-F)/2)-1$.
This defines the worst-case error interval for $\hat{F}$ as
$[(\hat{F}-e_{M})/(1-e_{M}),(\hat{F}+e_{M})/(1-e_{M})]$.

If on the other hand the measurement errors are benign, i.e., uncorrelated
from the circuit errors, they will flip all stabilizers regardless of their
value on the pre-measurement state with equal probability. In this case, the
measured fidelity satisfies $\hat{F}=F\cdot(1-2e_{M})$ so that we can deduce
the true fidelity $F$ from the measured fidelity and the measurement error.
Note that in this case, the measured state fidelity is always a lower bound to
the true state fidelity.

### Noisy circuits

Figure 6:  Noisy circuits for the $2\times 2$ cluster. Dephasing noise is
simulated by adding random (virtual) $Z$ rotations on all qubits after the
initial state preparation and after each MS gate, see Methods. This amounts to
roughly equidistant time steps. The rotation angles for the $Z$ rotations are
drawn randomly from a normal distribution with zero mean and standard
deviation $\sigma\in[0,0.2\pi]$ every 50 shots. For correlated noise, the
parameters in each time step are chosen equally and for uncorrelated noise,
they are chosen independently.

.

In order to study the influence of experimental noise on the reliability and
tightness of our bounds on the TVD, we artificially induce dephasing noise on
the $2\times 2$ cluster. This simulates a reduced spin-coherence time, which
could come from laser phase noise or magnetic field noise. These are the
dominant error sources in the experiment. To this end, we pick a fixed
instance of the $2\times 2$ cluster and add small random $Z$ rotations on all
qubits at roughly equidistant time steps. Specifically, we apply virtual $Z$
gates (i.e., realized in software as an appropriate phase shift on all
subsequent gate operations) after the initial local state preparation gates,
and again after each MS gate, see Fig. 6. In each run of the experiment (with
50 shots each), we randomly pick rotation angles for the virtual $Z$ gates
from a normal distribution with 0 mean and standard deviation $\sigma$. Here
$\sigma$ is a measure of the noise strength and corresponds to a local phase-
flip probability of $\xi/2$, where $\xi=1-e^{-\sigma^{2}/2}$. If we want to
engineer global, correlated noise, we use the same angle for all $Z$ gates in
a given “time-step”, whereas for engineering local, uncorrelated noise we pick
each angle independently. We then average these random choices over 50
instances for the fidelity estimate and 150 instances for the TVD. This
averaging turns the random phase shifts into independent (correlated)
dephasing channels in the case of local (global) noise. This effectively
appears as single-qubit depolarizing noise after every two-qubit gate with a
local Pauli error probability of $3\gamma/4$, where
$\gamma=1-e^{-0.310\sigma^{2}}$, where the constant was obtained from a
numerical fit to simulated data, see Section S5 of the SI for details.

Acknowledgements. D.H. acknowledges funding from the U.S. Department of
Defense through a QuICS Hartree fellowship. This work was completed while D.
H. was visiting the Simons Institute for the Theory of Computing. The Berlin
team acknowledges funding from the BMBF (DAQC, MUNIQC-ATOMS), the DFG
(specifically EI 519/21-1 on paradigmatic quantum devices, but also CRC 183),
the Einstein Foundation (Einstein Research Unit), the BMWi (EniQmA, PlanQK)
and the Studienstiftung des Deutschen Volkes. This research is also part of
the Munich Quantum Valley (K-8), which is supported by the Bavarian state
government with funds from the Hightech Agenda Bayern Plus. It has also
received funding from the EU’s Horizon 2020 research and innovation programme
under the Quantum Flagship projects PASQuanS2 and Millenion. JBV acknowledges
funding from EU Horizon 2020, Marie Skłodowska-Curie GA. Nr. 754446 - UGR
Research and Knowledge Transfer Fund Athenea3i; Digital Horizon Europe project
FoQaCiA, GA. Nr. 101070558., and FEDER/Junta de Andalucía program
A.FQM.752.UGR20. The Innsbruck team acknowledges support by the Austrian
Science Fund (FWF), through the SFB BeyondC (FWF Project No. F7109) and the EU
QuantERA project T-NiSQ (I-6001), and the Institut für Quanteninformation
GmbH. We also acknowledge funding from the EU H2020-FETFLAG-2018-03 under
Grant Agreement No. 820495, by the Office of the Director of National
Intelligence (ODNI), Intelligence Advanced Research Projects Activity (IARPA),
via US Army Research Office (ARO) grant No. W911NF-20-1-0007, and the US Air
Force Office of Scientific Research (AFOSR) via IOE Grant No. FA9550-19-1-7044
LASCEM. This research was funded by the European Union under Horizon Europe
Programme—Grant Agreement 101080086—NeQST. Funded by the European Union (ERC,
QUDITS, 101039522). Views and opinions expressed are, however, those of the
author(s) only and do not necessarily reflect those of the European Union or
the European Commission. Neither the European Union nor the granting authority
can be held responsible for them.

Author contributions. M.R. T.F. and L.P. performed the experiments. D.H.,
M.H., and M.R. analyzed the data and performed the numerical simulations. D.H.
and M.H. derived the theory of average (XEB) fidelity in MBQC. D.H., P.K.F.,
M.H., J.B-V., and J.E. conceived of the protocols. M.R., T.F., C.E., C.D.M.,
R.S., M.M., I.P., L.P., P.S., and T.M. contributed to the experimental setup.
R.B., J.E., and T.M. supervised the project. D.H. and M.R. wrote the initial
draft of the manuscript. All authors contributed to discussions and writing
the final manuscript.

Competing interests. The authors declare no competing interests.

Data availability. The experimental data and python code (which uses the
Qiskit package Qiskit) used in the numerical simulations and data analysis can
be obtained from the authors.

## References

Supplementary Information for
“Verifiable measurement-based quantum random sampling with trapped ions”

###### Contents

  1. S1 Fidelity witness
  2. S2 Experimental details
  3. S3 Compiled circuits
  4. S4 Computing the threshold fidelity from Stockmeyer’s argument
  5. S5 Properties of the average fidelity in measurement-based quantum computing
    1. S5.1 Direct average fidelity estimation
    2. S5.2 Cross-entropy benchmarking of measurement-based quantum computing
    3. S5.3 Estimating the average fidelity via XEB
      1. S5.3.1 Linear XEB fidelity with depolarizing noise
      2. S5.3.2 Log-XEB
      3. S5.3.3 How to estimate fidelity
    4. S5.4 A numerical study
  6. S6 Error analysis for the mean of means estimator

##  S1 Fidelity witness

In addition to the fidelity estimate, we have also measured a witness for the
fidelity on the generalized cluster states cramer_efficient_2010;
hangleiter_direct_2017. A fidelity witness of a quantum state $|{\psi}\rangle$
is a Hermitian operator $W$ with the properties

$\displaystyle\operatorname{Tr}[\rho
W]=1\Leftrightarrow\rho=|{\psi}\rangle\langle{\psi}|\quad\text{ and
}\quad\operatorname{Tr}[\rho W]\leq F(\rho,|{\psi}\rangle).$ (S1)

In other words, the expectation value of a fidelity witness provides a
meaningful lower bound on the fidelity of a state preparation $\rho$ with a
target state $|{\psi}\rangle$.

Figure S1:  Experimental results for cluster states with and without
recycling. (Fig. 3 from the main text including the fidelity witness) Root
infidelity witness $\sqrt{1-W_{F}}$ (triangles), root infidelity estimate
$\sqrt{1-F}$ (hexagons), and empirical total-variation distance (stars) for
single instances of random MBQC cluster states with recycling (blue) and
without (pink). Colored error bars represent the 3$\sigma$ interval of the
statistical error. For uncorrelated measurement noise, the systematic
measurement error only reduce the measured state fidelity. The worst-case
behaviour of the measurement error is represented by the gray error bars.
Modelling the circuit noise as local depolarizing noise after each entangling
gate (dotted lines), we extract effective local depolarizing error
probabilities of 5.3%, 2.6 % and 1% for the cluster with recycling, the
cluster in the large register, and the cluster in the small register,
respectively; see Eq. S44 below for details.

To construct a fidelity witness for the cluster states, we observe that the
pre-measurement cluster state in the protocol is the ground state of a
commuting, local Hamiltonian $H$ with gap $\Delta=2$, consisting of local
terms given by the locally rotated stabilizers $S_{i}$ of the cluster state.
The energy of the local terms in an imperfect state preparation $\rho$ yields
a certificate for the fidelity $F=\langle{\psi}|\rho|{\psi}\rangle$ with the
target state vector $|{\psi}\rangle$ in terms of the witness $W_{F}$ as
cramer_efficient_2010; hangleiter_direct_2017

$\displaystyle W_{F}=1-\frac{1}{2}\sum_{i=1}^{N}\langle
S_{i}\rangle_{\rho}\leq F.$ (S2)

In particular, this implies that the root infidelity bound (1) can be
supplemented as

$\displaystyle d_{\text{TV}}\leq\sqrt{1-F}\leq\sqrt{1-W_{F}}.$ (S3)

We have measured the fidelity witness for the same quantum states prepared for
Fig. 3 in the main text by measuring their stabilizers, see Fig. S1. We find
that the upper bound (S3) remains meaningful (i.e., smaller than one) only for
very small sizes of the cluster, and conclude that the fidelity witness has
very limited use in the presence of a significant amount of noise in the
system.

##  S2 Experimental details

In Table S1, we detail the number of experimental shots for sampling and
verification used in Fig. 3 and Fig. S1.

| Size | Sampling shots | Verification shots
---|---|---|---
|  |  | $M(W_{F})$ | $K(F)$ | $M(F)$
Recycling | 1 x 3 | 15 000 | 15 000 | 118 980 | 1
| 2 x 3 | 62 500 | 3 600 | 223 980 | 1
Non-recycling | 2 x 2 | 15 000 | 10 000 | 157 611 | 1
| 2 x 3 | 15 000 | 2 500 | 154 177 | 1
| 3 x 3 | 15 000 | 500 | 225 865 | 1
| 4 x 3 | — | 50 | 110 408 | 1
| 4 x 4 | — | 50 | 640 | 50
Table S1:  Number of samples used in Fig. 3. $M(W_{F})$: Number of shots per
stabilizer for the witness. $K(F)$: Number of randomly drawn stabilizers for
the fidelity estimate. $M(F)$: Number of shots per stabilizer for the fidelity
estimate.

##  S3 Compiled circuits

The quantum circuit giving rise to the cluster state can be succinctly written
as

$\displaystyle|{\text{CS}(\beta)}\rangle=\left(\prod_{\langle
k,l\rangle}CZ_{k,l}\right)\left(\prod_{k}\mathrm{e}^{-\mathrm{i}\beta_{k}Z_{k}}H_{k}\right)|{0^{N}}\rangle.$
(S4)

Here $\langle k,l\rangle$ denotes all pairs of neighboring ions in the
respective cluster state. We express this circuit in terms of the native gates
in the ion-trap architecture, pairwise addressed Mølmer Sørensen gates
$\text{MS}_{k,l}$ and arbitrary rotations around an axis in the X-Y plane
$R(\theta,\phi)$, given by

$\displaystyle\text{MS}_{k,l}$
$\displaystyle=\exp\left(-\mathrm{i}\frac{\pi}{4}X_{k}X_{l}\right),$ (S5)
$\displaystyle R(\theta,\phi)$
$\displaystyle=\exp\left(-\mathrm{i}\frac{\theta}{2}\left(\cos(\phi)X+\sin(\phi)Y\right)\right)=\begin{pmatrix}\cos\frac{\theta}{2}&-\mathrm{i}\mathrm{e}^{-\mathrm{i}\phi}\sin\frac{\theta}{2}\\\
\mathrm{i}\mathrm{e}^{\mathrm{i}\phi}\sin\frac{\theta}{2}&\cos\frac{\theta}{2}\end{pmatrix}.$
(S6)

Here, the polar angle $\theta$ corresponds to the laser pulse area, while the
azimuthal angle $\phi$ is determined by the phase of a laser pulse. With these
definitions, we observe some properties of the rotation gate

  * •

$X(\theta)=\mathrm{e}^{-\mathrm{i}\frac{\theta}{2}X}=R(\theta,0)$,

  * •

$Y(\theta)=R(\theta,\pi/2)$,

  * •

$R(\theta,\phi+\pi)|{0}\rangle=\mathrm{e}^{\mathrm{i}\pi/2}ZR(\theta,\phi)|{0}\rangle$.

Since the phase can be controlled much more precisely than the pulse area, it
is advantageous to only perform $\theta=\pi/2$-pulses with variable azimuthal
angle $\phi$. Now, let us decompose $CZ$ in terms of the above gates. We start
by writing

$\displaystyle
CZ_{k,l}=\mathrm{e}^{-\mathrm{i}\frac{\pi}{4}}\cdot\mathrm{e}^{\mathrm{i}\frac{\pi}{4}Z_{i}}\mathrm{e}^{\mathrm{i}\frac{\pi}{4}Z_{j}}\mathrm{e}^{-\mathrm{i}\frac{\pi}{4}Z_{i}Z_{j}},$
(S7)

and then observe that $Y(\pi/2)Z(\pi)=H$, and since the rotation angle of $Z$
does not matter for computational-basis measurements, we can replace $H$ by
$Y(\pi/2)$ and $H^{\dagger}=Z(-\pi)Y(-\pi/2)$. Hence
$Y(-\pi/2)X(\theta)Y(\pi/2)=Z(\theta)$ such that

$\displaystyle
CZ_{k,l}=\mathrm{e}^{-\mathrm{i}\pi/4}\left(\prod_{i=k,l}Y_{i}(-\frac{\pi}{2})X_{i}(-\frac{\pi}{2})\right)\text{MS}_{k,l}\left(\prod_{i=k,l}Y_{i}(\frac{\pi}{2})\right).$
(S8)

Putting this back into the first part of Eq. (S4) we observe that intermediate
$Y(\pm\pi/2)$ gates cancel and $X$-gates commute to the left leaving

$\displaystyle\prod_{\langle
k,l\rangle}CZ_{k,l}=\mathrm{e}^{-\mathrm{i}M\pi/4}\left(\prod_{i=1}^{N}Y_{i}\left(-\frac{\pi}{2}\right)X_{i}\left(-\frac{\deg(i)\pi}{2}\right)\right)\left(\prod_{\langle
k,l\rangle}\text{MS}_{k,l}\right)\left(\prod_{i=1}^{N}Y_{i}\left(\frac{\pi}{2}\right)\right),$
(S9)

where $M$ is the total number of MS-gates and $\deg(i)$ is the degree of site
$i$ (i.e., the number of links in the cluster). We can further simplify

$\displaystyle
Z(\beta)H|{0}\rangle=Z(\beta+\pi)Y(\pi/2)|{0}\rangle=\mathrm{e}^{-\mathrm{i}\frac{\beta}{2}}R(\pi/2,\beta+\pi/2)|{0}\rangle=\mathrm{e}^{-\mathrm{i}(\frac{\beta}{2}-\frac{\pi}{2})}Z(\pi)R(\pi/2,\beta-\pi/2)|{0}\rangle,$
(S10)

and since $Y(\pi/2)Z(\pi)=X(\pi)Y(\pi/2)$ we obtain the total circuit

$\displaystyle|{\text{CS}(\beta)}\rangle$
$\displaystyle=\mathrm{e}^{-\mathrm{i}(M\pi/4+\frac{1}{2}\sum_{i}\beta_{i}-N\pi/2)}\left(\prod_{i=1}^{N}Y_{i}\left(-\frac{\pi}{2}\right)X_{i}\left(-\frac{(\deg(i)-2)\pi}{2}\right)\right)\left(\prod_{\langle
k,l\rangle}\text{MS}_{k,l}\right)\left(\prod_{i=1}^{N}Y_{i}\left(\frac{\pi}{2}\right)R_{i}\left(\frac{\pi}{2},\beta-\frac{\pi}{2}\right)\right)$
(S11)
$\displaystyle=\mathrm{e}^{-\mathrm{i}(M\pi/4+\frac{1}{2}\sum_{i}\beta_{i}-N\pi/2)}\left(\prod_{i=1}^{N}Y_{i}\left(-\frac{\pi}{2}\right)\left(X_{i}\left(-\frac{\pi}{2}\right)\right)^{\deg(i)-2}\right)\left(\prod_{\langle
k,l\rangle}\text{MS}_{k,l}\right)\left(\prod_{i=1}^{N}Y_{i}\left(\frac{\pi}{2}\right)R_{i}\left(\frac{\pi}{2},\beta-\frac{\pi}{2}\right)\right).$

To perform a measurement in the Hadamard basis, we can now rotate back using
$H=ZY(-\pi/2)$, which can be absorbed in the leftmost layer of
$Y(-\pi/2)$-gates, to give a layer of $Y(-\pi)=Y$ gates. Since these are just
a phase flip and a bit flip, we can leave them out in the experiment and
perform them in the classical postprocessing.

##  S4 Computing the threshold fidelity from Stockmeyer’s argument

In the rigorous argument for the hardness of quantum random sampling, one
makes use of Stockmeyer’s algorithm stockmeyer_complexity_1983, an algorithm
in the third level of the polynomial hierarchy, in order to estimate #P-hard
probabilities; see Chapter 2 of Ref. hangleiter_sampling_2021 for an
accessible explanation of the algorithm. Let us briefly summarize the argument
here, and refer the reader to Ref. hangleiter_computational_2023 for a more
detailed exposition. We assume that there exists a classical algorithm
$\mathcal{A}$ that samples from the output distribution $p_{U}$ with
probabilities $p_{U}(x)=|\langle{x}|U|{0}\rangle|^{2}$ up to an additive
total-variation-distance error $\varepsilon$. We then feed $\mathcal{A}$ into
Stockmeyer’s algorithm and ask that it compute an approximation $q_{U}(x)$ of
the probability $p_{U}(x)$ for some binary string $x$.

The crucial step in the hardness proof then consists in balancing the error
stemming from Stockmeyer’s algorithm itself and the error incurred from the
assumption to obtain a multiplicative approximation up to a factor $1/4$ with
constant probability over the choice of $U$ and $x$. The relevant expression
is given by applying Markov’s inequality yielding that with probability
$1-\delta$

$|p_{U}(x)-q_{U}(x)|\leq\frac{p_{U}(x)}{\operatorname{poly}(n)}+\frac{\varepsilon}{2^{n}\delta}\left(1+\frac{1}{\operatorname{poly}(n)}\right).$
(S12)

We conjecture the distribution $p_{U}$ to anticoncentrate in the sense that

$\mathrm{Pr}_{U}\left[p_{U}(x)\geq\frac{1}{2^{n}}\right]\geq\gamma,$ (S13)

for some constant $\gamma>0$. As a result we obtain that with probability
$\gamma(1-\delta)$ Stockmeyer’s algorithm yields a relative-error
$\varepsilon/\delta+o(1)$ approximation of $p_{U}(x)$. Hence, assuming that
any $\gamma(1-\delta)$-fraction of the instances is #P-hard to approximate up
to relative error $\varepsilon/\delta+o(1)$, then this argument shows that one
can approximate #P-hard quantities in the third level of the polynomial
hierarchy – counter the established belief in theoretical computer science.

Consequently, we can trade the fraction of instances we conjecture to be hard
with the tolerated error $\varepsilon$ of the classical algorithm. Making a
bolder average-case conjecture results in a larger error bound from the
argument. As discussed in Ref. bermejo-vega_architectures_2018, we numerically
find $\gamma=1/\mathrm{e}$. Setting the average-case hard fraction
$\nu=10^{-3}$, and relative-error $\min(1-1/\sqrt{2},\sqrt{2}-1)=0.2928$
approximation fujii_commuting_2017, we obtain a threshold total variation-
distance $\nu/\gamma$ and consequently threshold infidelity

$\displaystyle 1-F_{T}=(0.2928\cdot(1-\nu/\gamma))^{2}=0.0857.$ (S14)

To summarize, we conjecture that any $10^{-3}$ fraction of the output
probability instances is #P-hard to approximate. We then obtain that sampling
is hard up to total-variation distance $0.29$ with probability at least 1%.
Correspondingly, the threshold infidelity of accepting a quantum state is
roughly 8.6%; see Fig. 3.

We emphasize, however, that the threshold fidelity from the hardness argument
above does not have a fundamental meaning in the sense that it does not imply
easiness above the threshold. Rather, it gives a threshold such that—if the
complexity-theoretic conjectures underlying the argument are true—hardness of
sampling is guaranteed if the infidelity remains below the threshold. More
generally, the takeaway should be that sampling from a family of distributions
whose TVD to the target distributions does not increase if the cluster size is
increased is likely a classically hard task; potentially even for a slow
(polynomial) increase, see also Refs. aaronson_complexity-theoretic_2017;
barak_spoofing_2021.

##  S5 Properties of the average fidelity in measurement-based quantum
computing

In this section, we discuss the average fidelity

$\displaystyle\overline{F}=\operatorname{\mathbb{E}}_{\beta}[\langle{\psi_{\beta}}|\rho_{\beta}|{\psi_{\beta}}\rangle]$
(S15)

of state preparations $\rho_{\beta}$ of the generalized cluster state
$|{\psi_{\beta}}\rangle$ with respect to random local rotation angles
$\beta\in[8]^{n\times m}\cdot\pi/4$.

First, in Section S5.1, we show that the _direct fidelity estimation_ (DFE)
protocol of flammia_direct_2011 can be directly applied to estimating average
state fidelities. Then, in Section S5.2 we study properties of the cross-
entropy measures in measurement-based computing, and in particular, discuss
some specifics of measurement-based quantum computing, in particular, the role
of logical and physical circuits for these cross-entropy measures. Given this,
we show in Section S5.3 how to use cross-entropy measures as an alternative
way to estimate average fidelities, analogous to the theory of _cross-entropy
benchmarking_ (XEB) for random circuits by arute_quantum_2019_short. We show
analytically that under certain assumptions on the noise in the device, such
cross-entropy measures can indeed also be applied in the context of MBQC to
estimate average fidelities. Lastly, in Section S5.4 we support our analytical
considerations with a numerical study comparing the resulting average
fidelities from the DFE protocol with those obtained via XEB.

###  S5.1 Direct average fidelity estimation

In this section, we show how DFE can be directly applied to estimating the
average cluster state fidelity $\overline{F}$. To this end, we observe that,
analogously to the single-instance case discussed in the Methods section of
the main text,

$\displaystyle\overline{F}$
$\displaystyle=\operatorname{\mathbb{E}}_{\beta}\left[\frac{1}{2^{N}}\sum_{s_{\beta}\in\mathcal{S}_{\beta}}\langle
s_{\beta}\rangle_{\rho_{\beta}}\right]$
$\displaystyle=\frac{1}{2^{N}}\frac{1}{8^{N}}\sum_{\beta\in\frac{\pi}{4}\cdot[8]^{N}}\sum_{s_{\beta}\in\mathcal{S}_{\beta}}\sum_{\sigma=\pm
1}\sigma\cdot\langle\pi_{s_{\beta}}^{\sigma}\rangle_{\rho_{\beta}}.$ (S16)

Here, the stabilizer group $\mathcal{S}_{\beta}=\langle
S^{\beta}_{1},\ldots,S^{\beta}_{N}\rangle$ and $\pi_{s_{\beta}}^{\sigma}$ is
the projector onto the $\sigma$-eigenspace of
$s_{\beta}\in\mathcal{S}_{\beta}$. Hence, we obtain an unbiased estimator
$\hat{\overline{F}}$ of the average fidelity by drawing a uniformly random
pair $(\beta,S_{\beta})$, measuring $S_{\beta}$ on $\rho_{\beta}$, and
averaging over the measurement outcomes $\sigma$.

Since the measurement outcomes are bounded by $1$ in absolute value, we can
estimate the average up to error $\epsilon$ using a number $M$ of uniformly
random samples $(\beta,S_{\beta})$ that scales as $1/\epsilon^{2}$ and is in
particular independent of the number of qubits. As before, if we measure $M$
shots per random pair of state and stabilizer of which we draw $K$ many, the
variance of this will be given by the variance formula

$\displaystyle\operatorname{Var}[\hat{\overline{F}}]=\frac{4}{KM}(\operatorname{\mathbb{E}}_{i}[p_{i}](1-\operatorname{\mathbb{E}}_{i}[p_{i}]))+\frac{4}{K}\left(1-\frac{1}{M}\right)\operatorname{Var}_{i}[p_{i}],$
(S17)

where the expectation runs over the choice of random state and stabilizer as
labeled by $i$.

###  S5.2 Cross-entropy benchmarking of measurement-based quantum computing

_Cross-entropy benchmarking_ (XEB) has been proposed as a way to measure the
average fidelity of quantum state preparations and has been applied to
computations in the circuit model arute_quantum_2019_short;
zhu_quantum_2022_short, as well as to certain analog quantum simulations
choi_emergent_2021. This benchmark has been developed by
boixo_characterizing_2018; arute_quantum_2019_short, and the key property that
makes it useful to experiments is that it can be sample-efficiently estimated
for sufficiently random ensembles of circuits whose output probabilities are
exponentially distributed. XEB has a complexity-theoretic interpretation in
terms of the task dubbed _heavy outcome generation_ aaronson_complexity-
theoretic_2017; aaronson_classical_2020, an interpretation as a proxy for the
TVD under assumptions on the noise in the classical output distribution
bouland_complexity_2019, and provides a means to estimate the (average)
quantum fidelity of the state from which the classical samples are produced
arute_quantum_2019_short, see Ref. hangleiter_computational_2023 for an
overview.

The most important XEB quantities are the so-called _linear_ and _logarithmic
XEB fidelities_ (see, e.g., Ref. hangleiter_computational_2023, Section V.B).
For an ideal target probability distribution $P$ and a noisy distribution $Q$
on $n$-bit strings, we define those as

$\displaystyle f_{\textsf{lin}}(Q,P)$ $\displaystyle\coloneqq
2^{n}\sum_{x}Q(x)P(x)-1,$ (S18) $\displaystyle f_{\textsf{log}}(Q,P)$
$\displaystyle\coloneqq-\sum_{x}Q(x)\log P(x),$ (S19)

respectively. These quantities can be empirically estimated by drawing samples
$x_{1},\dots,x_{k}$ from the noisy distribution $Q$ and averaging
$P(x_{1}),\dots,P(x_{k})$ or the logarithms of these, respectively.

For any single fixed circuit instance, the value of the XEB fidelities defined
above and the actual quantum state fidelity of the state preparation before
measurement could behave quite differently. A relation between XEB fidelity
and quantum state fidelity can only be established on average over wide
ensembles of circuits and only under additional assumptions described in more
detail below. To this effect, we consider the average XEB fidelities
$\overline{f}_{\textsf{lin}}$ and $\overline{f}_{\textsf{log}}$, where the
average is taken over the ensembles of circuit instances. As described in
Section S5.3, those average XEB fidelities will serve us as estimators of the
average state fidelity $\overline{F}$.

Figure S2:  Distinction between physical and logical circuit. (a) The
_physical circuit_ is the circuit which we apply in the experiment. It is a
constant-depth circuit on $n\times m$ qubits that comprises a layer of single-
qubit Hadamard gates and local rotations, and a layer of entangling $CZ$
gates, followed by a measurement in the Hadamard basis. We further distinguish
by convention the _bulk_ of the lattice comprising the first $m-1$ columns and
its _last column_. (b) The _logical circuit_ is the effective depth-$m$
circuit applied to the last column of qubits. It is generated by the
measurements in the bulk of the cluster and, for each column of the physical
state, comprises three layers: a layer of single-qubit rotations $Z_{\beta}$
with rotation angles $\beta$ corresponding to the respective position in the
cluster and randomly applied $Z$ gates depending on whether or not the outcome
of the corresponding qubit was $1$ or $0$, a layer of entangling $CZ$ gates,
and a layer of Hadamard gates.

We note that the above notions of XEB quantities apply to any model of quantum
computation. In the following, we will discuss aspects of XEB that are
particular to the measurement-based quantum computing setting considered in
this work. We will denote the output probability distributions of an ideal
cluster state preparation $|{\psi_{\beta}}\rangle$ and an imperfect cluster
state preparation $\rho_{\beta}$ upon measurement in the Hadamard basis, by
$P_{\beta}$ and $Q_{\beta}$, respectively. Now, in contrast to the circuit
model, in the context of MBQC, we seem to face a choice regarding which
distributions to base our XEB quantities on: Recall that in MBQC, the
measurement outcomes in the ‘bulk’ of the system—that is, all qubits but those
in the last (rightmost) column of the cluster—determine a _logical circuit_
applied to the state $|{+}\rangle^{\otimes n}$ on the ‘boundary’ of the
cluster—precisely that last column—see Fig. S2. According to this distinction
between bulk and boundary, we split full outcome strings as $x=(x_{b},x_{f})$
into bulk outcomes $x_{b}\in\\{0,1\\}^{n(m-1)}$ and the outcomes on the final
column $x_{f}\in\\{0,1\\}^{n}$.

Now, there are two output distributions that one could consider as inputs to
XEB: First, there is the (joint) output distribution
$P_{\beta}(x)=P_{\beta}(x_{b},x_{f})$ over the outcomes of the whole physical
circuit, that is, the circuit which we actually apply in the lab, including
all $N=n\cdot m$ measurement outcomes. Alternatively, there is the output
distribution $\tilde{P}_{\beta,x_{b}}(x_{f})$ of the logical circuit over the
$n$ outcomes $x_{f}$ of only the last column of qubits. The logical circuit is
determined by the choices of angles $\beta$ as well as the $N-n$ measurement
outcomes in the bulk $x_{b}.$ Hence, the logical outcome distribution is
simply the conditional distribution
$\tilde{P}_{\beta,x_{b}}=P_{\beta}(\cdot|x_{b})$ and the noisy samples are
distributed according to $\tilde{Q}_{\beta,x_{b}}=Q_{\beta}(\cdot|x_{b})$.
This suggests, that we could also consider logical XEB quantities associated
with the logical distribution $\tilde{P}_{\beta,x_{b}}(x_{f})$ as follows

$\displaystyle\tilde{f}_{\textsf{lin}}(\tilde{Q}_{\beta,x_{b}},\tilde{P}_{\beta,x_{b}})$
$\displaystyle=2^{n}\sum_{x_{f}}\tilde{Q}_{\beta,x_{b}}(x_{f})\tilde{P}_{\beta,x_{b}}(x_{f})-1,$
(S20)
$\displaystyle\tilde{f}_{\textsf{log}}(\tilde{Q}_{\beta,x_{b}},\tilde{P}_{\beta,x_{b}})$
$\displaystyle=-\sum_{x_{f}}\tilde{Q}_{\beta,x_{b}}(x_{f})\log\tilde{P}_{\beta,x_{b}}(x_{f}).$
(S21)

A motivation for considering logical output distributions of an $n\times m$
cluster state is that, in contrast to the physical output distributions, the
logical ones behave analogously to the outcome distribution of random circuits
on $n$ qubits with depth $O(m)$. In particular, their statistical
properties—which are an important ingredient in XEB theory—match up to
constant factors haferkamp_closing_2020. Conversely, if our goal is to
estimate the average fidelity of the full cluster state, the XEB fidelity of
the physical output distribution $P_{\beta}(x_{b},x_{f})$ seems to be the
relevant quantity.

As it turns out, however, the XEB fidelities associated with physical and
logical output distributions are in fact equivalent when used for average
fidelity estimation via XEB. To see this, we have to consider the averaged XEB
quantities introduced above. Concretely, we consider averages over the
ensemble of circuits induced by a uniformly random choice of $\beta$ from
$\frac{\pi}{4}\cdot[8]^{n\times m}$. This random choice induces via the map
$\beta\mapsto P_{\beta}$, a distribution over ideal output distributions which
we denote by $\mathcal{P}$. Similarly, we denote by $\mathcal{Q}$ the
distribution over noisy output distributions induced via $\beta\mapsto
Q_{\beta}$. Hence, the average XEB fidelities are written as

$\displaystyle\overline{f}_{\textsf{lin}}(\mathcal{Q},\mathcal{P})$
$\displaystyle=\operatorname{\mathbb{E}}_{Q\sim\mathcal{Q},P\sim\mathcal{P}}\left[f_{\textsf{lin}}(Q,P)\right],$
(S22) $\displaystyle\overline{f}_{\textsf{log}}(\mathcal{Q},\mathcal{P})$
$\displaystyle=\operatorname{\mathbb{E}}_{Q\sim\mathcal{Q},P\sim\mathcal{P}}\left[f_{\textsf{log}}(Q,P)\right].$
(S23)

Analogously, the average logical XEB fidelities arise from drawing logical
circuit instances $(\beta,x_{b})$ according to the uniform choice of $\beta$
and $x_{b}$ from the marginal distribution with probabilities
$Q_{\beta}(x_{b})=\sum_{x_{f}}Q_{\beta}(x_{f},x_{b})$.

Now, to relate the average XEB fidelites corresponding to physical and logical
circuits, we will use the fact that, under the ideal distribution
$P_{\beta}(x)$, the outcomes $x_{b}$ are uniformly distributed
childs_unified_2005 so that
$P_{\beta}(x_{f},x_{b})=2^{-n(m-1)}P_{\beta}(x_{f}|x_{b})$. Then, we compute

$\displaystyle\mathbb{E}_{\beta}\left[f_{\textsf{lin}}(Q_{\beta},P_{\beta})\right]$
$\displaystyle=2^{N}\mathbb{E}_{\beta}\sum_{x}Q_{\beta}(x)P_{\beta}(x)-1,$
(S24)
$\displaystyle=2^{N}\mathbb{E}_{\beta}\sum_{x_{b}}\sum_{x_{f}}Q_{\beta}(x_{f},x_{b})P_{\beta}(x_{f},x_{b})-1,$
$\displaystyle=2^{n}\mathbb{E}_{\beta}\sum_{x_{b}}Q_{\beta}(x_{b})\sum_{x_{f}}Q_{\beta}(x_{f}|x_{b})P_{\beta}(x_{f}|x_{b})-1,$
$\displaystyle=2^{n}\mathbb{E}_{\beta}\mathbb{E}_{x_{b}}\sum_{x_{f}}\tilde{Q}_{\beta,x_{b}}(x_{f})\tilde{P}_{\beta,x_{b}}(x_{f})-1,$
$\displaystyle=\mathbb{E}_{\beta}\mathbb{E}_{x_{b}}\left[\tilde{f}_{\textsf{lin}}(\tilde{Q}_{\beta,x_{b}},\tilde{P}_{\beta,x_{b}})\right],$

which we can rewrite in short notation as

$\overline{f}_{\textsf{lin}}=\overline{\tilde{f}}_{\textsf{lin}}.$ (S25)

An analogous computation yields

$\overline{f}_{\textsf{log}}=\overline{\tilde{f}}_{\textsf{log}}+\log
2^{n(m-1)}.$ (S26)

To summarize, the physical and logical average XEB fidelities are equivalent
in both the linear and the logarithmic versions up to a shift for the log XEB
fidelity. However, their empirical variance—given in Eq. S59—might still
differ, because the samples are grouped differently in the mean of means
estimator. In practice, we will therefore use XEB estimates from the physical
circuits whenever possible given system size constraints (which influences the
complexity of computing the ideal probabilities). This is because we are able
to take more samples per circuit (reducing the first term of Eq. S59) since
the circuits of the logical XEB fidelity are partially determined by
the—random—physical measurement outcomes. Moreover, in the experimental
setting, taking more samples per circuit is cheaper than running more
different circuits.

##### Ideal values of the XEB fidelity.

For completeness, we conclude this subsection by demonstrating how to compute
ideal values of the average XEB fidelities. These are the values of
$\overline{f}_{\textsf{lin}}$ and $\overline{f}_{\textsf{log}}$ resulting from
the case where $Q_{\beta}=P_{\beta}$, i.e.

$\displaystyle\overline{f}_{\textsf{lin}}(\mathcal{P},\mathcal{P})$
$\displaystyle=\mathbb{E}_{\beta}\left[f_{\textsf{lin}}(P_{\beta},P_{\beta})\right]\quad\text{
and
}\quad\overline{f}_{\textsf{log}}(\mathcal{P},\mathcal{P})=\mathbb{E}_{\beta}\left[f_{\textsf{log}}(P_{\beta},P_{\beta})\right].$
(S27)

To compute these ideal values we make use of statistical properties of the
logical output distributions. In particular, it was shown by
haferkamp_closing_2020 that the logical circuits form an
$\epsilon$-approximate $2$-design in depth $m\in O(n+\log(1/\epsilon))$. This
implies that the second moments
$\mathbb{E}_{\beta,x_{b}}[\tilde{P}_{\beta,x_{b}}^{2}]$ of the ideal logical
output probability distributions approximate the Haar-random value with
relative error $\epsilon$. Neglecting this error, we find that the ideal
average linear XEB fidelity of circuits with such scaling of $m$ with $n$
asymptotically behaves as

$\displaystyle\overline{f}_{\textsf{lin}}(\mathcal{P},\mathcal{P})$
$\displaystyle=\overline{\tilde{f}}_{\textsf{lin}}(\mathcal{P},\mathcal{P}),$
$\displaystyle=2^{n}\sum_{x_{f}}\mathbb{E}_{\beta,x_{b}}\left[\tilde{P}_{\beta,x_{b}}(x_{f})^{2}\right]-1,$
$\displaystyle=\frac{2\cdot 2^{2n}}{2^{n}(2^{n}+1)}-1,$
$\displaystyle=\frac{2}{1+2^{-n}}-1\approx 1-\frac{1}{2^{n-1}}.$ (S28)

In particular, because of the equality of physical and logical linear XEB, the
ideal value can only depend on the size of the logical circuit which is in
turn given by the shortest side of the square lattice. Moreover, it is easy to
see that the average linear XEB fidelity with the uniform distribution
$\mathcal{U}$ (defined by $\beta\mapsto
U([2^{n}])\coloneqq(2^{-n},2^{-n},\ldots,2^{-n})\in[0,1]^{2^{n}}$) is given by
$\overline{f}_{\textsf{lin}}(\mathcal{U},\mathcal{P})=0$.

We can repeat the same calculation for the logarithmic XEB fidelity, to find

$\displaystyle\overline{f}_{\textsf{log}}(\mathcal{P},\mathcal{P})$
$\displaystyle=\overline{\tilde{f}}_{\textsf{log}}(\mathcal{P},\mathcal{P})+\log
2^{n(m-1)},$
$\displaystyle=-\sum_{x_{f}}\mathbb{E}_{\beta,x_{b}}\left[\tilde{P}_{\beta,x_{b}}(x_{f})\log\tilde{P}_{\beta,x_{b}}(x_{f})\right]+\log
2^{n(m-1)},$ (S29) $\displaystyle=\log 2^{n}-1+\gamma+\log 2^{n(m-1)},$ (S30)
$\displaystyle=\log 2^{nm}-1+\gamma$

where the step from Eq. S29 to (S30) follows from the properties of the
exponential distribution (see Ref. (boixo_characterizing_2018, Sec. II of the
SI) for details) and $\gamma\approx 0.5774$ is the Euler constant. In
particular, this calculation implies that for distributions with uniformly
distributed marginals and Porter-Thomas distributed conditional probabilities,
we get the same average value as for global Porter-Thomas distributed
distributions. Likewise, we find the average value of the log XEB fidelity
when comparing it to the uniform distribution $\mathcal{U}$ to be

$\displaystyle\overline{f}_{\textsf{log}}(\mathcal{U},\mathcal{P})$
$\displaystyle=-\operatorname{\mathbb{E}}_{\beta}[\log P_{\beta}(x)]=\log
2^{nm}+\gamma,$ (S31)

again, assuming Porter-Thomas shape of the distribution.

Figure S3:  Ideal values of the linear and logarithmic XEB fidelities. We
compute the ideal values of the XEB fidelities for clusters of size $n\times
m$ with fixed values of the height $n=2,3,4,5,10$ (corresponding to the number
of qubits of the logical circuit) in increasing opacity and scaling of the
width $m$ (corresponding to the depth of the logical circuit). To this end, we
average the XEB fidelities of the ideal output distributions of $K=10^{5}$
random (logical) circuits per data point. Error bars are $3\sigma$ intervals.
(a) Ideal values of the linear XEB (pink hexagons). For the linear XEB
fidelity, the ideal value of the physical circuit equals that of the logical
circuit by the uniformity property of the marginals, cf. Eq. S24. Dotted lines
indicate the ideal values (S28). (b) Ideal value of the logical log XEB
fidelity $\overline{\tilde{f}}_{\textsf{log}}(\mathcal{P},\mathcal{P})$ (blue
triangles). Dashed lines represent the asymptotic value $\log 2^{n}+\gamma-1$
(Eq. S30 & (S26)). (c) Logical log XEB fidelity for uniform samples
$\overline{\tilde{f}}_{\textsf{log}}(\mathcal{U},\mathcal{P})$. Dashed lines
indicate the ideal value $\log 2^{n}+\gamma$ (Eq. S31). (d–f) Deviations of
the estimated finite-size values from the ideal values of (a–c), respectively.

The theoretical ideal values found above pertain to the asymptotic limit of
cluster states of increasing size. However, in the experiments reported in the
main text, we deal with small instance sizes. In Fig. S3, we confirm the
convergence to the ideal values computed above for small instance sizes as
relevant to our experiment. We find that the linear XEB fidelity significantly
deviates from the expected asymptotic value for small sizes $n\times m$ of the
cluster. It is also true that the XEB fidelity of $n\times m$ clusters equals
that of $m\times n$ clusters and is given by the ideal value of the logical
circuit corresponding to the shorter side. When we measure the deviation of
the ideal XEB fidelity of the logical circuits from their expected value, this
deviation decays exponentially with the depth $m$ of the logical circuit
(corresponding to the width of the cluster), independently of the number of
qubits $n$ (corresponding to its height)—until we hit the noise floor set by
the precision of our computation around $m=10$.111 Note that in this
comparison, we sometimes compare the XEB fidelities of rectangular clusters to
the ideal XEB fidelity corresponding to the _longer side_ , namely whenever
$n\geq m$.

In contrast, the ideal logarithmic logical XEB is almost immediately close to
its ideal value (S24), but the deviation (after an initial decay) stays
roughly constant with the width of the cluster while it decays with the
height. We interpret this fact in terms of the Porter-Thomas distribution: For
a small number of qubits $n$ on which the logical circuit acts, the
exponential distribution is not a good approximation of the actual
distribution of output probabilities of Haar-random quantum states. Hence, the
calculation of the mean value, which uses the exponential distribution, incurs
a systematic error.222See the Supplementary Material of Ref.
hangleiter_anticoncentration_2018 for details of this calculation.  Finally,
the deviation of the ideal log XEB fidelity for uniform samples from the
expected values decay with both the height and the width of the cluster. For
the small-size experiments (up to $m=n=4$) we therefore need to use the
computed values of the XEB fidelities (instead of the asymptotic values) when
using XEB to estimate the fidelity; see the subsequent section.

###  S5.3 Estimating the average fidelity via XEB

In this section, we discuss how the average XEB fidelities
$\overline{f}_{\textsf{lin}}$ and $\overline{f}_{\textsf{log}}$ and their
logical counterparts $\overline{\tilde{f}}_{\textsf{lin}}$ and
$\overline{\tilde{f}}_{\textsf{log}}$ can be used to estimate the average
state fidelity $\overline{F}$ of the underlying quantum states under
assumptions on the noise in the device. We follow the argumentation of
arute_quantum_2019_short, see also Ref. (hangleiter_computational_2023, Sec.
V.B.3) for an overview.

####  S5.3.1 Linear XEB fidelity with depolarizing noise

Let us begin with the linear XEB fidelity. We consider first the toy model of
global depolarizing noise and then generalize it to uncorrelated and unbiased
noise.

##### Depolarizing noise.

Consider the noisy state

$\displaystyle\rho_{\beta}(\epsilon)=\epsilon|{\psi_{\beta}}\rangle\langle{\psi_{\beta}}|+(1-\epsilon)\mathbbm{1}/2^{N}.$
(S32)

where $|{\psi_{\beta}}\rangle$ is the generalized cluster state. Then, the
fidelity is given by
$F=\langle{\psi_{\beta}}|\rho_{\beta}(\epsilon)|{\psi_{\beta}}\rangle=\epsilon+(1-\epsilon)/2^{N}$,
and the same holds true for the average fidelity $\overline{F}$. In this case,
the XEB fidelity is given by

$\displaystyle f_{\textsf{lin}}(Q_{\beta}(\epsilon),P_{\beta})=\epsilon
f_{\textsf{lin}}(P_{\beta},P_{\beta})+(1-\epsilon)f_{\textsf{lin}}(U([2^{N}]),P_{\beta}).$
(S33)

Averaging over $\beta$, we find

$\displaystyle\overline{f}_{\textsf{lin}}(\mathcal{Q}_{,}\mathcal{P})$
$\displaystyle=\operatorname{\mathbb{E}}_{\beta}[f_{\textsf{lin}}(Q_{\beta}(\epsilon),P_{\beta})]$
(S34)
$\displaystyle=\epsilon\operatorname{\mathbb{E}}_{\beta}[f_{\textsf{lin}}(P_{\beta},P_{\beta})]+(1-\epsilon)\underbrace{\overline{f}_{\textsf{lin}}(\mathcal{U},\mathcal{P})}_{=0}$
$\displaystyle=\epsilon\overline{f}_{\textsf{lin}}(\mathcal{P},\mathcal{P}),$

and hence, we can estimate $\epsilon$ as

$\displaystyle\hat{\epsilon}=\frac{\hat{\overline{f}}_{\textsf{lin}}(\mathcal{Q},\mathcal{P})}{\overline{f}_{\textsf{lin}}(\mathcal{P},\mathcal{P})},$
(S35)

where $\hat{\overline{f}}_{\textsf{lin}}(\mathcal{Q},\mathcal{P})$ is the
empirical estimate of the experimental average linear XEB fidelity. We can
then estimate the average fidelity as

$\displaystyle\overline{F}(\hat{\epsilon})=\hat{\epsilon}+(1-\hat{\epsilon})/2^{nm}.$
(S36)

arute_quantum_2019_short justify this estimator further using Bayes rule.

##### Uncorrelated and unbiased noise.

One can make the same argument in case the quantum state is given by some
noisy state

$\displaystyle\rho_{\beta}(\epsilon)=\epsilon|{\psi_{\beta}}\rangle\langle{\psi_{\beta}}|+(1-\epsilon)\chi_{\beta},$
(S37)

decomposed into the ideal state and a state $\chi_{\beta}$ capturing the
noise. Now, the same conclusions regarding estimates of the _average fidelity_
will hold in case the noise is

  * •

_uncorrelated_ in the sense that
$\operatorname{\mathbb{E}}_{\beta}[\langle{x}|\chi_{\beta}|{x}\rangle\langle{x}|\psi_{\beta}\rangle\langle{\psi_{\beta}}|x\rangle]=\operatorname{\mathbb{E}}_{\beta}[\langle{x}|\chi_{\beta}|{x}\rangle]\operatorname{\mathbb{E}}_{\beta}[\langle{x}|\psi_{\beta}\rangle\langle{\psi_{\beta}}|x\rangle]$,
and

  * •

_unbiased_ in the sense that
$\operatorname{\mathbb{E}}_{\beta}[\langle{x}|\chi_{\beta}|{x}\rangle]=1/2^{N}$.

The estimator $\hat{\overline{F}}$ using Eq. S35 will then give a good
estimate of the average fidelity.

We note that one can similarly relate the average logical linear XEB
$\overline{\tilde{f}}_{\textsf{lin}}$ to the average fidelity of the “logical”
output state, i.e., the state on the final column that arises from measuring
the bulk qubits obtaining some outcome $x_{b}$ which we denote by
$|{\psi_{\beta,x_{b}}}\rangle$. To see this, consider this noisy logical state
$\rho_{\beta,x_{b}}(\tilde{\epsilon})$ and write analogously to Equation S32

$\rho_{\beta,x_{b}}(\tilde{\epsilon})=\tilde{\epsilon}|{\psi_{\beta,x_{b}}}\rangle\langle{\psi_{\beta,x_{b}}}|+(1-\tilde{\epsilon})\mathbbm{1}/2^{n}.$
(S38)

Then, the average fidelity of the noisy logical output state is given by

$\displaystyle\overline{\tilde{F}}(\tilde{\epsilon})=\tilde{\epsilon}+(1-\tilde{\epsilon})/2^{n}.$
(S39)

In analogy to Equation S35, this average logical fidelity can be estimated via
the average logical XEB as follows

$\displaystyle\hat{\tilde{\epsilon}}_{\textsf{lin}}=\frac{\hat{\overline{\tilde{f}}}_{\textsf{lin}}(\mathcal{Q},\mathcal{P})}{\overline{\tilde{f}}_{\textsf{lin}}(\mathcal{P},\mathcal{P})}=\hat{\epsilon}_{\textsf{lin}}$
(S40)

where the last equality follows from the equivalence of physical and logical
average linear XEB derived in Equation S25.

####  S5.3.2 Log-XEB

We can repeat the same argument for the logarithmic XEB under the global
depolarizing noise assumption, and find

$\displaystyle\overline{f}_{\textsf{log}}(\mathcal{Q}_{,}\mathcal{P})$
$\displaystyle=\operatorname{\mathbb{E}}_{\beta}[f_{\textsf{log}}(Q_{\beta}(\epsilon),P_{\beta})]$
(S41)
$\displaystyle=\epsilon\overline{f}_{\textsf{log}}(\mathcal{P},\mathcal{P})+(1-\epsilon)\overline{f}_{\textsf{log}}(\mathcal{U},\mathcal{P})$
(S42)

and hence an estimator of $\epsilon$ is given by

$\displaystyle\hat{\epsilon}_{\textsf{log}}$
$\displaystyle=\frac{\hat{\overline{f}}_{\textsf{log}}(\mathcal{Q},\mathcal{P})-\overline{f}_{\textsf{log}}(\mathcal{U},\mathcal{P})}{\overline{f}_{\textsf{log}}(\mathcal{P},\mathcal{P})-\overline{f}_{\textsf{log}}(\mathcal{U},\mathcal{P})}.$
(S43)

Again, from $\hat{\epsilon}$, we can estimate the average (physical) fidelity
according to $\overline{F}(\hat{\epsilon})$. Again, we find
$\hat{\epsilon}_{\textsf{log}}=\hat{\tilde{\epsilon}}_{\textsf{log}}$, since
all logical logarithmic XEB quantities are just shifted by $\log 2^{n(m-1)}$.
However, for the same derivation to work with more general noise, we need to
adapt the “uncorrelated” assumption to the logarithm, i.e.,
$\operatorname{\mathbb{E}}_{\beta}[\langle{x}|\chi_{\beta}|{x}\rangle\log(P_{\beta}(x)]=\operatorname{\mathbb{E}}_{\beta}[\langle{x}|\chi_{\beta}|{x}\rangle]\operatorname{\mathbb{E}}_{\beta}[\log(P_{\beta}(x)]$,
while the unbiasedness condition remains the same. Notice that all estimators
above are unbiased since they are just linear in the empirical estimates of
the XEB fidelities.

####  S5.3.3 How to estimate fidelity

While the estimates $\hat{\tilde{\epsilon}}$ and $\hat{\epsilon}$ always
agree, the average fidelity estimators thus differ in the normalization of the
correction term to the state fidelity in Eqs. (S36) and (S39). Which
correction to the average depolarizing fidelity will yield a better estimate
of the fidelity depends on how accurate the uncorrelated and unbiased noise
assumption is for the logical versus the physical output state, or in other
words, how well the model of Eqs. (S32) and (S37) applies to the corresponding
states.

dalzell_random_2021 show that for local random circuits of at least
logarithmic depth, local depolarizing noise approximately transforms into
global depolarizing (white) noise at the level of the output state and thus
build confidence in the validity of these assumptions. Specifically,
dalzell_random_2021 prove that the white-noise assumption is approximately
true in random circuits provided the physical noise is local and unbiased. In
that case, the effective noise at the end of the circuit will be approximately
depolarizing with an error scaling inversely with the number of gates. More
precisely, they show that the normalized linear XEB
$\overline{f}=\overline{f}_{\textsf{lin}}(\mathcal{Q},\mathcal{P})/\overline{f}_{\textsf{lin}}(\mathcal{P},\mathcal{P})$
between the noisy distribution $\mathcal{Q}$ and the ideal distribution
$\mathcal{P}$ behaves as

$\displaystyle\overline{f}(\eta)=\mathrm{e}^{-2S\eta},$ (S44)

where $S$ is the number of two-qubit gates and $\eta$ is the probability of a
local Pauli error on each qubit after a two-qubit gate. Moreover, for
incoherent _unital_ noise, the noisy distribution approaches the uniform
distribution at the same rate with an error given by
$O(\overline{f}_{\textsf{lin}}\eta\sqrt{S})$ all in the regime of
$S\in\Omega(n\log n)$.

Given that the statistical properties of random logical MBQC circuits behave
completely analogously to those of random circuits in the circuit model, we
would expect an analogous result to hold for the fidelity of the logical
output state in MBQC. More precisely, random logical MBQC circuits behave like
random universal circuits on the level of lower moments in the sense that
random logical MBQC circuits also generate unitary $2$-designs
haferkamp_closing_2020 (and presumably polynomial designs as well). A possible
caveat, however, is that in MBQC physical noise translates non-trivially into
logical noise as considered for single-qubit circuits by usher_noise_2017.
Thus, while we are unclear on the exact conditions on a local noise model, we
do expect that an analogous result to that of dalzell_random_2021 holds for
logical MBQC circuits. In this case, the logical XEB fidelity will be a good
measure of the quantum fidelity of the output of the logical circuit. In this
case, the fidelity will decay approximately according to Eq. S44.

Notice, though, that our direct estimate of the fidelity measures the fidelity
of the _physical output state_ and hence we cannot experimentally certify that
XEB yields quality estimates for the logical fidelity $\overline{\tilde{F}}$.
But for the physical output state, we are much less confident in the validity
of the uncorrelatedness and unbiasedness of the noise with the circuit.
Indeed, a priori, there is no good reason to expect that the physical XEB
fidelity estimator $\overline{F}(\hat{\epsilon})$ matches the physical
fidelity $\overline{F}$ accurately unless physical and logical average
fidelity behave in the same way.

We do find, however, that the estimator $\overline{F}(\hat{\epsilon})$ works
reasonably well as an estimate for the fidelity for local depolarizing noise,
and also the noise we face in the experiment; see the following section. This
suggests that the uncorrelated and unbiasedness assumption does in fact hold
true for the physical circuit as well. Furthermore, it suggests, that as $n,m$
grow, the physical and logical physical fidelity converge. We leave a more
detailed analysis of the effect of noise in MBQC on the estimates of fidelity
to future work. In the following section, we will provide numerical evidence
that, indeed, the XEB fidelities can be used to estimate the quantum fidelity
in the presence of various types of local noise on the physical circuit.

###  S5.4 A numerical study

Figure S4: Average fidelity estimation for depolarizing noise. We simulate
sampling in the Hadamard basis and DFE for noisy random cluster states of size
$2\times m$ for $m\in\\{2,3,\ldots,10\\}$ with local depolarizing noise with
parameter $\gamma$ after every entangling $CZ$ gate. We sample $K=10^{5}$
random circuits and take $M=50$ samples per circuit. From the classical
samples, we compute estimates of the average fidelity
$\overline{F}(\hat{\epsilon})$ according to (S36) using the linear and
logarithmic average XEB fidelity $\overline{f}_{\textsf{lin}}$ and
$\overline{f}_{\textsf{log}}$ (represented by purple triangles and green
diamonds, respectively) and compare them to the DFE estimate
$\hat{\overline{F}}$ of the average fidelity (pink hexagons) as well as the
prediction (S44) by dalzell_random_2021 (dotted line). Error bars are
$3\sigma$ intervals. (a) Decay of the average fidelity with the width of the
cluster state for fixed noise parameter $\gamma=0.05$. (b) Decay of the
average fidelity with the noise parameter for a fixed width of the cluster
$m=6$ (blue boxes). (c) Deviation
$\overline{F}(\hat{\epsilon}_{\textsf{lin}})-\hat{\overline{F}}$ between the
fidelity estimate from the linear XEB fidelity and the average fidelity. (d)
Deviation $\overline{F}(\hat{\epsilon}_{\textsf{log}})-\hat{\overline{F}}$
between the fidelity estimate from the linear XEB fidelity and the average
fidelity.  Figure S5: Average fidelity estimation for dephasing noise. We
simulate sampling in the Hadamard basis and DFE for noisy random cluster
states of size $2\times m$ for $m\in\\{2,3,\ldots,10\\}$ with local dephasing
noise with parameter $\xi$ after every entangling $CZ$ gate. We sample
$K=10^{5}$ random circuits and take $M=50$ samples per circuit. From the
classical samples, we compute estimates of the average fidelity
$\overline{F}(\hat{\epsilon})$ according to (S36) using the linear and
logarithmic average XEB fidelity $\overline{f}_{\textsf{lin}}$ and
$\overline{f}_{\textsf{log}}$ (represented by purple triangles and green
diamonds, respectively) and compare them to the DFE estimate
$\hat{\overline{F}}$ of the average fidelity (pink hexagons) as well as the
prediction (S44) by dalzell_random_2021 (dotted line). Error bars are
$3\sigma$ intervals. (a) Decay of the average fidelity with the width of the
cluster state for fixed noise parameter $\xi=0.05$. (b) Decay of the average
fidelity with the noise parameter for a fixed width of the cluster $m=6$ (blue
boxes). (c) Deviation
$\overline{F}(\hat{\epsilon}_{\textsf{lin}})-\hat{\overline{F}}$ between the
fidelity estimate from the linear XEB fidelity and the average fidelity. (d)
Deviation $\overline{F}(\hat{\epsilon}_{\textsf{log}})-\hat{\overline{F}}$
between the fidelity estimate from the linear XEB fidelity and the average
fidelity. . Figure S6: Average fidelity estimation for the noisy experimental
circuits. We simulate sampling in the Hadamard basis and DFE for noisy random
cluster states of size $2\times m$ for $m\in\\{2,3,\ldots,10\\}$ with random
local $Z$-rotations with rotation angle drawn from a normal distribution with
mean $0$ and standard deviation $\sigma$ inserted in every layer of the
experimental circuit; see the Methods section for details. We sample
$K=10^{5}$ random circuits and take $M=1$ sample per circuit. From the
classical samples, we compute estimates of the average fidelity
$\overline{F}(\hat{\epsilon})$ according to (S36) using the linear and
logarithmic average XEB fidelity $\overline{f}_{\textsf{lin}}$ and
$\overline{f}_{\textsf{log}}$ (represented by purple triangles and green
diamonds, respectively) and compare them to the DFE estimate
$\hat{\overline{F}}$ of the average fidelity (pink hexagons) as well as the
prediction $\overline{f}(3\gamma/4)$ (S44) by dalzell_random_2021 (dotted
line). Error bars are $3\sigma$ intervals. (a) Decay of the average fidelity
with the width of the cluster state for fixed noise strength $\sigma=0.08\pi$.
(b) Decay of the average fidelity with the noise parameter for a fixed width
of the cluster $m=8$ (blue boxes). (c) Deviation
$\overline{F}(\hat{\epsilon}_{\textsf{lin}})-\hat{\overline{F}}$ between the
fidelity estimate from the linear XEB fidelity and the average fidelity. (d)
Deviation $\overline{F}(\hat{\epsilon}_{\textsf{log}})-\hat{\overline{F}}$
between the fidelity estimate from the linear XEB fidelity and the average
fidelity.

In the previous sections, we have explained how to obtain estimates
$\hat{\overline{F}}$ for the average fidelity of the state preparation of the
cluster state in two different ways:

  * •

From random stabilizer measurements on the cluster state via DFE as considered
in Section S5.1.

  * •

From quantum random sampling in the Hadamard basis via XEB fidelity estimation
as explained in Section S5.3.

In this section, we numerically study the quality of fidelity estimates
obtained via XEB fidelity estimation by using the estimates obtained via DFE
as a benchmark. In particular, we generate data according to the above-
mentioned two methods by numerically simulating noisy state preparations
$\rho_{\beta}$ of the cluster state for many randomly drawn $\beta$. We do so
for different types of noise, system sizes, and noise strengths. From these
data, we then obtain the corresponding average fidelity estimates as a
function of the system size and noise strength. More concretely, we
numerically simulated two different settings.

The first setting is inspired by the theoretical work of dalzell_random_2021
on random circuit sampling under local, unbiased noise. This is the setting in
which we most likely expect the average XEB fidelity estimate
$\overline{F}(\hat{\epsilon})$ to be a good estimate of the average fidelity
$\overline{F}$. Here, we consider noisy cluster state preparations
$\rho_{\beta}$ via circuits built from Hadamard and $CZ$ gates and
$Z$-rotation gates. We take all single-qubit gates to be perfect but all $CZ$
gates are followed by local depolarizing or dephasing noise channels,
respectively. In Fig. S4 and Fig. S5 we compare the fidelity estimates
obtained via the DFE and XEB methods for these two noise settings. We also
compare these results to fidelity scaling predicted via the formula (S44),
where the number of two-qubit $CZ$ gates is in our case just the number of
edges of the $n\times m$ square lattice, given by $n(m-1)+m(n-1)$. Writing the
single-qubit depolarizing and dephasing channels $\mathcal{D}_{\gamma}$ and
$D_{\xi}$ with parameters $\gamma$ and $\xi$, respectively, as

$\displaystyle\mathcal{D}_{\gamma}(\rho)$
$\displaystyle=(1-\gamma)\rho+\gamma\frac{\mathbbm{1}}{2}$ (S45)
$\displaystyle D_{\xi}(\rho)$
$\displaystyle=(1-\gamma)\rho+\xi\operatorname{diag}(\rho),$ (S46)

the error probability $\eta$ takes values $\eta=3\gamma/4$ for depolarizing
noise and $\eta=\xi/2$ for dephasing noise.

We find excellent agreement of the prediction $\overline{F}(\eta)$ for the
average physical fidelity—although it was derived for the XEB fidelity, while
the XEB fidelity estimators are approximately correct for depolarizing noise
in the regime of low noise parameters $\gamma\sim 1/n$. For dephasing noise,
we find that the XEB fidelity estimators greatly underestimate the average
fidelity.

In contrast, the second setting models the actual experimental setup reported
in the main text. That is, we simulate the noisy experimental circuits
described in the Methods section. Again, we find excellent agreement of the
physical fidelity with the prediction $\overline{F}(\eta)$ by
dalzell_random_2021. We find that setting the effective depolarizing noise
parameter $\gamma=1-\exp(-0.310\sigma^{2}/2)$, where $\sigma$ is the measure
of the noise strength, gives the best fit with the observed fidelity.

##  S6 Error analysis for the mean of means estimator

In order to compute the statistical error associated with our estimates of the
fidelity and the XEB fidelity, we need to compute the variance of a finite-
sample estimator of a random variable $A$ conditioned on a random variable $B$
so that

$\displaystyle
F=\mathbb{E}_{B\sim\mathcal{B}}\left[\mathbb{E}_{A\sim\mathcal{A}}[A|B]\right].$
(S47)

We think of $B$ as the random circuit and $A$ as the samples or random
stabilizer values of the random circuit. Concretely, the fidelity estimate,
average fidelity estimate (S16), and XEB fidelity (S18) estimate are obtained
as the empirical estimate of the expectation values

$\displaystyle F(\rho,|{\psi}\rangle\langle{\psi}|)$
$\displaystyle=\frac{1}{2^{N}}\sum_{s\in\mathcal{S}}\sum_{\sigma\in\pm
1}\sigma\cdot\operatorname{Tr}[\rho\pi_{s}^{\sigma}]$ (S48)
$\displaystyle=\mathbb{E}_{s\sim\mathcal{S}}\left[\mathbb{E}_{\sigma\sim
p_{\rho,s}}[\sigma]\right],$ $\displaystyle\overline{F}$
$\displaystyle=\frac{1}{2^{N}}\frac{1}{8^{N}}\sum_{\beta\in\frac{\pi}{4}\cdot[8]^{n}}\sum_{s_{\beta}\in\mathcal{S}_{\beta}}\sum_{\sigma=\pm
1}\sigma\cdot\langle\pi_{s_{\beta}}^{\sigma}\rangle_{\rho_{\beta}}$ (S49)
$\displaystyle=\mathbb{E}_{\beta,s_{\beta}\sim\mathcal{S}_{\beta}}\left[\mathbb{E}_{\sigma\sim
p_{\rho_{\beta},s_{\beta}}}[\sigma]\right],$ (S50)
$\displaystyle\overline{f}_{\textsf{lin}}$
$\displaystyle=\mathbb{E}_{\beta\sim\frac{\pi}{4}\cdot[8]^{N}}\left[\frac{1}{2^{N}}\sum_{x\in\\{0,1\\}^{N}}Q_{\beta}(x)\left(2^{N}P_{\beta}(x)-1\right)\right]$
(S51)
$\displaystyle=\mathbb{E}_{\beta\sim\frac{\pi}{4}\cdot[8]^{N}}\left[\mathbb{E}_{x\sim
Q_{\beta}}\left[2^{N}P_{\beta}(x)-1\right]\right],$

where $p_{\rho,s}(\sigma)=\operatorname{Tr}[\rho\pi_{s}^{\sigma}]$ and
$s=\pi_{s}^{+}-\pi_{s}^{-}$ is a stabilizer of $|{\psi}\rangle$. We now wish
to estimate the variance of a finite-sample estimate of such an expectation
value, that is, an estimator

$\displaystyle\hat{F}=\frac{1}{K}\frac{1}{M}\sum_{i=1}^{K}\sum_{j=1}^{M}A_{i,j},$
(S52)

where $K$ is the number of times the first expectation value is sampled out,
and $M$ is the number of times the second expectation value is sampled out,
given the result of the first. For instance, to estimate the average bias of a
bag of coins with different biases, we draw $K$ coins and flip each drawn coin
$M$ times. In this case, $A_{i,j}\in\\{0,1\\}$ is the outcome of the $j$th
flip of the $i$th drawn coin.

Very generally, we can compute the variance of such a conditional expectation
value using the law of total variance, which states that for two random
variables $A,B$ on the same probability space

$\displaystyle\operatorname{Var}(A)=\mathbb{E}[\operatorname{Var}[A|B]]+\operatorname{Var}[\mathbb{E}[A|B]].$
(S53)

Consider the fidelity estimate. If we let $A_{i}=\sum_{j=1}^{M}A_{i,j}$ be the
random variable, representing the empirical cumulative value of the $M$
measurement outcomes $A_{i,j}\in\\{\pm 1\\}$ of the stabilizer $s_{i}$ on the
state preparation $\rho$ with associated probability distribution
$p_{s_{i},\rho}$, then the overall variance is given by
$\operatorname{Var}(\hat{F})=(KM)^{-2}\sum_{i=1}^{K}\operatorname{Var}(A_{i})$.
To understand the variance $\operatorname{Var}(A_{i})$, letting
$p_{i}=p_{s_{i},\rho}(+1)$ so that $\mathbb{E}[A_{i}]=M(2p_{i}-1)$, we now
invoke the law of total variance, to get

$\displaystyle\operatorname{Var}[A_{i}]$
$\displaystyle=\mathbb{E}_{p_{i}}\left[\operatorname{Var}[A_{i}|p_{i}]\right]+\operatorname{Var}_{p_{i}}\left[\mathbb{E}[A_{i}|p_{i}]\right]$
(S54)
$\displaystyle=\mathbb{E}[4Mp_{i}(1-p_{i})]+\operatorname{Var}[M(2p_{i}-1)]$
$\displaystyle=4M\mathbb{E}[p_{i}]-4M\mathbb{E}[p_{i}^{2}]+4M^{2}\operatorname{Var}[p_{i}]$
$\displaystyle=4M\mathbb{E}[p_{i}]-4M(\operatorname{Var}[p_{i}]+\mathbb{E}[p_{i}]^{2})+4M^{2}\operatorname{Var}[p_{i}]$
$\displaystyle=4M(\mathbb{E}[p_{i}](1-\mathbb{E}[p_{i}]))+4M(M-1)\operatorname{Var}[p_{i}].$

This yields the overall variance

$\displaystyle\operatorname{Var}[\hat{F}]$
$\displaystyle=\frac{4}{KM}\left((\mathbb{E}[p_{i}](1-\mathbb{E}[p_{i}]))+(M-1)\operatorname{Var}[p_{i}]\right)$
(S55)
$\displaystyle=\frac{4}{KM}(\mathbb{E}[p_{i}](1-\mathbb{E}[p_{i}]))+\frac{4}{K}\left(1-\frac{1}{M}\right)\operatorname{Var}[p_{i}].$

Consequently, the variance is asymptotically dominated by the variance over
the stabilizers, but in the finite-sample case, there is a trade-off between
choosing $M$ and $K$ governed by the specific value of
$\operatorname{Var}[p_{i}]$.

For the case of the (linear and logarithmic) XEB fidelity estimated from $K$
random choices of rotation angles $\beta_{i}$, $i=1,\ldots,K$ and $M$ samples
per $\beta_{i}$, we follow the same reasoning, defining the average estimator
$\hat{\overline{f}}_{\textsf{lin}}=(KM)^{-1}\sum_{i,j=1}^{K,M}(2^{N}P_{\beta_{i}}(x_{j})-1)$,
and the single-circuit estimator
$\hat{f}_{\textsf{lin}}(Q_{\beta},P_{\beta})=M^{-1}\sum_{j=1}^{M}(2^{N}P_{\beta_{i}}(x_{j})-1)$.
We then consider the random variable
$A_{i}=\sum_{j=1}^{M}(2^{N}P_{\beta_{i}}(x_{j})-1)$ and
$\operatorname{Var}[\hat{\overline{f}}_{\textsf{lin}}]=(KM)^{-2}\sum_{i=1}^{K}\operatorname{Var}[A_{i}]$,
and find

$\displaystyle\operatorname{Var}[A_{i}]=\mathbb{E}[\operatorname{Var}[A_{i}|\beta_{i}]]+\operatorname{Var}[\mathbb{E}[A_{i}|\beta_{i}]],$
(S56)

and estimate the separate terms as

$\displaystyle\mathbb{E}_{i}[\operatorname{Var}_{x}[A_{i}|\beta_{i}]]$
$\displaystyle=\mathbb{E}_{i}[M\operatorname{Var}_{x}[2^{N}P_{\beta_{i}}(x)-1]]$
$\displaystyle=\mathbb{E}_{i}[\sum_{x}Q_{\beta_{i}}(x)(2^{N}P_{\beta_{i}}(x)-1-f_{\textsf{lin}}(Q_{\beta_{i}},P_{\beta_{i}})))^{2}]$
$\displaystyle\approx\frac{1}{K}\sum_{i=1}^{K}\sum_{j=1}^{M}(2^{N}P_{\beta_{i}}(x_{j})-1-\hat{f}_{\textsf{lin}}(Q_{\beta_{i}},P_{\beta_{i}}))^{2},$
(S57) $\displaystyle\operatorname{Var}_{i}[\mathbb{E}_{x}[A_{i}|\beta_{i}]]$
$\displaystyle=\operatorname{Var}_{i}[Mf_{\textsf{lin}}(Q_{\beta_{i}},P_{\beta_{i}})]$
$\displaystyle\approx
M^{2}\frac{1}{K}\sum_{i=1}^{K}(\hat{f}_{\textsf{lin}}(Q_{\beta_{i}},P_{\beta_{i}})-\hat{\overline{f}}_{\textsf{lin}}(Q_{\beta_{i}},P_{\beta_{i}}))^{2}.$
(S58)

Overall, we obtain

$\displaystyle\operatorname{Var}[\hat{\overline{f}}_{\textsf{lin}}]$
$\displaystyle=\frac{1}{K^{2}}\frac{1}{M^{2}}\left(\sum_{i=1}^{K}\sum_{x=1}^{M}(2^{N}P_{\beta_{i}}(x)-1-f_{\textsf{lin}}(Q_{\beta_{i}},P_{\beta_{i}}))^{2}+M^{2}\sum_{i=1}^{K}(f_{\textsf{lin}}(Q_{\beta_{i}},P_{\beta_{i}})-\overline{f}_{\textsf{lin}}(Q_{\beta_{i}},P_{\beta_{i}}))^{2}\right)$
$\displaystyle=\frac{1}{KM}\mathbb{E}_{\beta}[\operatorname{Var}_{x}[2^{N}P_{\beta}(x)-1]]+\frac{1}{K}\operatorname{Var}_{\beta}[f_{\textsf{lin}}(Q_{\beta},P_{\beta})],$
(S59)

which we estimate using the expressions in Eqs. (S57) and (S58). An analogous
expression gives the variance of the logarithmic XEB estimate.

## References