# Deterministic Ansätze for the Measurement-based Variational Quantum
Eigensolver

Anna Schroeder  Merck KGaA, Darmstadt, Germany  Department of Computer
Science, Technical University of Darmstadt, Darmstadt, Germany
<EMAIL_ADDRESS>Matthias Heller  Fraunhofer Institute for
Computer Graphics Research IGD, Darmstadt, Germany  Interactive Graphics
Systems Group, Technical University of Darmstadt, Darmstadt, Germany
<EMAIL_ADDRESS>Mariami Gachechiladze  Department of
Computer Science, Technical University of Darmstadt, Darmstadt, Germany
<EMAIL_ADDRESS>
###### Abstract

Measurement-based quantum computing (MBQC) is a promising approach to reducing
circuit depth in noisy intermediate-scale quantum algorithms such as the
Variational Quantum Eigensolver (VQE). Unlike gate-based computing, MBQC
employs local measurements on a preprepared resource state, offering a trade-
off between circuit depth and qubit count. Ensuring determinism is crucial to
MBQC, particularly in the VQE context, as a lack of flow in measurement
patterns leads to evaluating the cost function at irrelevant locations. This
study introduces MBVQE-ansätze that respect determinism and resemble the
widely used problem-agnostic hardware-efficient VQE ansatz. We evaluate our
approach using ideal simulations on the Schwinger Hamiltonian and $XY$-model
and perform experiments on IBM hardware with an adaptive measurement
capability. In our use case, we find that ensuring determinism works better
via postselection than by adaptive measurements at the expense of increased
sampling cost. Additionally, we propose an efficient MBQC-inspired method to
prepare the resource state, specifically the cluster state, on hardware with
heavy-hex connectivity, requiring a single measurement round, and implement
this scheme on quantum computers with $27$ and $127$ qubits. We observe
notable improvements for larger cluster states, although direct gate-based
implementation achieves higher fidelity for smaller instances.

##  1 Introduction

The notion of quantum advantage is a highly intriguing application of quantum
mechanics. Although it has been successfully showcased in computing problems
tailored to a particular hardware [1, 2, 3], attaining computational speedup
for problems with practical applications remains an important challenge. On
the one hand, we already have Shor’s algorithm [4] and concepts from error-
correction [5] to solve the factoring problem more efficiently than on any
classical supercomputers, but such fault-tolerant schemes have stringent and
potentially prohibitive requirements. On the other hand, quantum devices
available today are noisy, have a limited number of qubits, and can only
operate short quantum circuits on which we can endeavor to solve practical
problems. Therefore, the greatest challenge for the foreseeable future is
figuring out how to utilize noisy and intermediate-scale quantum (NISQ)
hardware.

Hybrid quantum-classical algorithms and specifically the variational methods,
which embed the problems into parameterized short-depth quantum circuits and
employ the classical optimization routines to find the quantum circuits that
best solve the problem at hand, have attracted significant interest [6, 7, 8,
9]. They address the problem of estimating the ground state energy of a
quantum many-body Hamiltonian and have applications in quantum chemistry [10,
9, 11], high-energy physics [12, 13, 14], materials science [15], and
classical optimization [16, 17]. Alongside the success, this approach suffers
from a few challenges: in general, training variational quantum algorithms is
NP-hard [18] and the error-mitigation might require a superpolynomial number
of samples even for logarithmically shallow circuits, threatening any possible
quantum advantage [19]. Even though a few methods have been proposed to ease
the former problem [20, 21, 22, 23, 24], the latter looks more terminal. For
significant classes of local Hamiltonians, any circuit aiming to prepare the
ground state must have at least logarithmic depth [25, 26, 27], which poses
the trade-off, one either resorts to inadequate approximation of the ground
state, or the noise takes over the computation. In general, optimizing the
depth of variational quantum algorithms is strongly QCMA-hard [28].

Here, we tackle the second problem. We propose a hardware-efficient protocol
that borrows tools from measurement-based quantum computation [29, 30], enjoys
extremely shallow circuits [31], and is deterministic in measurement outcomes.
It is well known that unlike dynamical languages, such as steps in the Turing
machine or gates in the quantum circuit, in the measurement-based model,
computation is performed just with local measurements on a many-body entangled
state. While the circuit model of quantum computation defines its logical
depth or computational time in terms of temporal gate sequences, MBQC allows a
different temporal ordering and parallelization of universal logical gates. In
this scheme, it is enough to achieve universality by analyzing the
correlations that exist in many-body quantum states and, thus, is a very
different, uniquely quantum way of thinking from all the dynamical
computational models. Here, we study the possible advantages of this model of
computation in variational algorithms.

Several variants of measurement-based variational quantum eigensolvers (MBVQE)
have been recently proposed [32, 33, 34, 35, 36, 37, 38] (see also Appendix A
for an overview of previous works). However, they are either of probabilistic
nature [32], which causes exponential overhead or are not tailored to the
current hardware capabilities requiring a high degree of qubit connectivity
[35, 34]. Here, we propose a general MBVQE scheme relying on the notion of
quantum information flow defined for the one-way model to guarantee
determinism independent of each measurement outcome [39, 40]. Determinism is
crucial to ensure that the variational steps in the classical training part
converge even during the perfect noiseless simulations. It becomes even more
pressing in the noisy regime when we have to incorporate current error-
mitigation methods. From the deterministic models, we choose the specific
ansatz architectures that are hardware efficient, and for two different
examples, we study the trade-off between the size of the MB resource state
translating into the number of parameters and the effectiveness of
approximating the ground state. As a testbed, we run simulations for the
Schwinger model and the $XY$-model and implement resource-conscious versions
of our MBVQE ansatz of a four-qubit $XY$-Hamiltonian on an IBM quantum
computer. We further study the efficacy of resource-state preparation on the
heavy-hex-connected IBM quantum machines.

##  2 Preliminaries

###  2.1 Variational Quantum Eigensolver

The Variational Quantum Eigensolver (VQE) is a quantum-classical hybrid
algorithm that approximates the lowest eigenvalue and its corresponding
eigenvector of a given hermitian operator, typically the Hamiltonian of the
investigated quantum system [9]. The basic idea of VQE is to generate quantum
states using a parametrized quantum circuit, the so-called ansatz, and
classically optimize the parameters $\bm{\theta}$ such that the generated
state $\ket{\psi(\bm{\theta})}$ minimizes the cost function $C(\bm{\theta})$,
which is the expectation value of the Hamiltonian $H$,

$C(\bm{\theta}):=\expectationvalue{H}{\psi{(\bm{\theta})}}\geq E_{gs}\;,$ (1)

where $E_{gs}$ is the exact groundstate energy. Gradients of $\bm{\theta}$ can
be efficiently measured directly from the quantum device using the parameter
shift rule [41, 42], making them accessible for gradient-based optimizers.
Various quantum ansätze, such as the problem-agnostic hardware-efficient
ansatz [43], annealer-inspired QAOA [44], or the adaptively growing ADAPT-VQE
[22] have been proposed and extensively explored. The quantum chemistry
community, in particular, has contributed numerous problem-inspired ansätze
[45], many derived from the extensive literature on classical variational
methods [46, 47]. Although there are known roadblocks to the productive use of
VQE, such as the high counts of associated quantum measurements [48] or
vanishing gradients (referred to as Barren plateaus) [49], VQEs remain the
primary workhorse of quantum algorithms in the NISQ era.

###  2.2 Measurement-based quantum computing

In MBQC, computation is carried out on a highly entangled resource state by
local measurements only. The typical resource state is a graph state [50],
however, other options have also been proposed [51, 52, 53]. A graph state
$\ket{G}$ corresponds to a graph $G=(V,E)$, consisting of a set of vertices
$V$ and edges $E$, in the following manner: Prepare $|V|$ qubits in the
$\ket{+}$ state and associate them each to a vertex in $G$. Then apply the
$CZ$ gate between two qubits if the corresponding graph vertices are
connected:

$\ket{G}=\prod_{\\{i,j\\}\in E}CZ_{i,j}\ket{+}^{\otimes|V|}.$ (2)

Graph states can equivalently be defined by means of the stabilizer formalism.
A graph state $\ket{G}$ corresponding to a graph $G=(V,E)$ is a unique
eigenstate with the eigenvalue $+1$ to the following local Pauli stabilizers,

$\ket{G}=X_{i}\bigotimes_{j\in\mathcal{N}(i)}Z_{j}\ket{G},\quad\forall i\in
V.$ (3)

Here each stabilizer operator is written for a vertex $i\in V$ and consists of
the Pauli-$X$ gate on a vertex $i$ and Pauli-$Z$ gates acting on the graph-
neighbors of $i$, denoted by the set $\mathcal{N}(i)$. The most standard
resource state for MBQC is a so-called cluster state; its associated graph is
a regular two-dimensional grid. To harness universal quantum computation, the
cluster resource state is paired with measurements in Pauli bases and
particular measurement bases in $X-Y$ plane, parameterized by an angle
$\theta$, $\ket{\theta_{\pm}}:=\frac{\ket{0}\pm e^{i\theta}\ket{1}}{\sqrt{2}}$
[29], which we denote sometimes as $R(\theta)$.

Figure 1: A: A 5-qubit measurement pattern that implements an arbitrary
single-qubit rotation $U_{x}(\xi)U_{z}(\eta)U_{x}(\zeta)$ from a linear graph
state, and B: a 4-qubit pattern that performs a CNOT gate. Successive
measurements of the blue qubits in the illustrated basis implement the desired
quantum operation on the orange output qubit.

Specific measurement patterns on snippets of the cluster state correspond to
implementing quantum gates. See Fig. 1 for measurement patterns implementing
an arbitrary single-qubit rotation and the CNOT gate. Typically, these
patterns consist of input qubits, initialized to an arbitrary quantum state,
output qubits, and qubits in between, depending on the pattern that is
implemented. After measuring all qubits but the output qubits, the output
qubits are modified to be equivalent to the input qubits with the intended
gates applied. Due to the intrinsic randomness of quantum measurement
outcomes, the output qubits generally carry additional random byproduct
operators. The unique feature of MBQC is the ability to account for these
byproducts and obtain a deterministic output state on the fly.

To nurture an intuition of the MBQC framework, i.e., which operations are
implemented with $R(\theta)$ basis measurements and how determinism is
ensured, let us discuss a simple example that starts with a three-qubit, one-
dimensional cluster state as a resource,

$\ket{G_{3}}:=CZ_{1,2}CZ_{2,3}\ket{\psi_{\mathrm{in}}}_{1}\otimes\ket{+}_{2}\otimes\ket{+}_{3}\,,$
(4)

comprising qubits $q_{1},q_{2},q_{3}$, where the input qubit $q_{1}$ is
initialized in an arbitrary state
$\ket{\psi_{\mathrm{in}}}=\alpha\ket{0}+\beta\ket{1}$.

Measuring $q_{1}$ in $R(\theta)$ basis disentangles $q_{1}$ from the rest of
the graph and yields one of the two possible subnormalized post-measurement
states:

$\displaystyle\begin{split}&\outerproduct{\theta_{\pm}}{\theta_{\pm}}_{1}\ket{G_{3}}\\\
\propto&\ket{\theta_{\pm}}_{1}CZ_{2,3}(\alpha\ket{+}_{2}\pm
e^{-i\theta}\beta\ket{-}_{2})\otimes\ket{+}_{3}\\\
=&\ket{\theta_{\pm}}_{1}\otimes\ket{G_{2}^{\pm}},\end{split}$ (5)

where
$\ket{G_{2}^{+}}=CZ_{2,3}H_{2}P_{2}(\theta)\ket{\psi_{\mathrm{in}}}_{2}\otimes\ket{+}_{3}$
and
$\ket{G_{2}^{-}}=CZ_{2,3}H_{2}Z_{2}P_{2}(\theta)\ket{\psi_{\mathrm{in}}}_{2}\otimes\ket{+}_{3}$,
where $H$ is the Hadamard gate and $P(\theta)$ is equivalent to rotation about
the $Z$-axis up to a global phase $P(\theta)=e^{-i\theta/2}U_{z}(\theta)$. In
other words, by projecting $q_{1}$ on $\ket{\theta_{+}}_{1}$, we effectively
apply gates $HP(\theta)$ to the input state. Iterating this step and measuring
$q_{2}$ in $R(\theta^{\prime})$ basis, we get the output qubit $q_{3}$ to be
$HP(\theta^{\prime})HP(\theta)\ket{\psi_{\mathrm{in}}}$ for two ‘$+$’ outcomes
on $q_{1}$ and $q_{2}$, but additional Pauli-$Z$ gates for other outcomes.

To obtain a deterministic post-measurement state, we need to account for the
random byproducts. First, we take care of the ones appearing in
$\ket{G^{+}_{2}}$ and $\ket{G^{-}_{2}}$. To this end, we use the relation
between the measurement $\ket{\theta_{\pm}}$,

$\outerproduct{\theta_{-}}{\theta_{-}}_{1}\ket{G_{3}}=\ket{\theta_{-}}\bra{\theta_{+}}_{1}Z_{1}\ket{G_{3}}\,.$
(6)

Along with the graph stabilizer equation
$Z_{1}\ket{G_{3}}=X_{2}Z_{3}\ket{G_{3}}$, we can shift that additional $Z_{1}$
gate onto the yet unmeasured qubits,

$\outerproduct{\theta_{-}}{\theta_{-}}_{1}\ket{G_{3}}=\ket{\theta_{-}}\bra{\theta_{+}}_{1}X_{2}Z_{3}\ket{G_{3}}\,.$
(7)

This indicates that $\ket{G^{-}_{2}}$ is equivalent to $\ket{G^{+}_{2}}$ up to
local Pauli byproducts. All Pauli-$Z$ byproducts that appear during
measurements can be commuted similarly to the neighboring unmeasured qubits,
introducing Pauli-$X$ byproducts. On the other hand, these new Pauli-$X$
byproducts can be accounted for through adaptive measurements as
$X\outerproduct{\theta^{\prime}_{\pm}}{\theta^{\prime}_{\pm}}X=\outerproduct{-\theta^{\prime}_{\pm}}{-\theta^{\prime}_{\pm}}$,
thus, the measurement basis has to be adapted from $R(\theta^{\prime})$ to
$R(-\theta^{\prime})$.

To summarize, projections onto the negative eigenstates introduce $Z$
byproducts that can be accounted for by commuting them onto neighboring
unmeasured qubits of the resource state. This introduces $Z$ and $X$
byproducts (specified by the stabilizers of the resource state) that can be,
in the case of $Z$ byproducts, shifted further employing the stabilizer rules,
and in the case of $X$ byproducts, compensated with adaptive measurements by
swapping measurement bases $\theta^{\prime}$ and $-\theta^{\prime}$ on the
respective qubit. Byproducts acting on the output qubits can be corrected
efficiently through classical post-processing. For a graphical illustration of
these rules, see Fig. 2. Note that adaptive measurements introduce a temporal
and causal measurement order and a geometric condition for a “correctable”
measurement pattern, known as the flow in MBQC literature [40].

Figure 2: A graphical representation of MBQC and byproduct corrections. Orange
qubits are called ansatz qubits in the MBVQE-context and are also the output
qubits. The blue qubits are measured in varied bases $R(\theta_{i})$.
Measurements results are depicted with overlapping green and red circles,
indicating a projection onto the positive or negative eigenstate,
respectively. These eigenstates are related via Pauli-$Z$ operations which
commute through the resource state via the graph state stabilizers. $X$
byproducts can be corrected via an adaptive measurement step defining a casual
and temporal measurement order. Whether these byproducts can be corrected in
MBVQE, depends on the selected decoration scheme. A: Ref. [32] introduced an
edge-wise decoration scheme. Horizontally aligned qubits can be measured
simultaneously. Here, two measurement orders coincide in the middle ansatz
qubit and break the flow condition – correcting for one byproduct introduces
another on the other side. We cannot obtain deterministic outcomes. B: A
deterministic decoration is obtained by layering the ansatz-graphs and
connecting them vertically. Every $Z$ byproduct can be corrected with the
stabilizer of the neighboring qubit in the subsequent measurement layer.

###  2.3 The flow condition in MBQC

The flow condition was derived in Ref. [40] to characterize measurement
patterns that can be executed deterministically by means of the byproduct
corrections discussed in Section 2.2. With the graph state as a resource and
$R(\theta)$ basis measurements, determinism is ensured whenever the temporal
measurement order, defined by the adaptive measurements, has a distinct flow
without collisions. For intuitive understanding, let us study measurement
patterns where the flow is missing (Fig. 2) and present (Fig. 2). In these
examples, orange qubits are the output qubits, and blue qubits are measured
layer by layer with the temporal order depicted by the arrow. Green and red
overlapping circles indicate the measurement results of the $R(\theta)$
measurement. Thus, pictorially, the measurement pattern can be executed
deterministically if it is possible to make all overlapping circles green. In
Fig. 2, two measurement orders coincide at the middle output qubit, which may
cause a conflict in the byproduct correction. I.e., if only one of the qubits
connected to the middle output qubit was projected onto the untargeted
eigenstate $\ket{\theta_{-}}$, there is no way to account for this without
causing an undesired phase kickback on the other side. For certain measurement
outcomes in Fig. 2, it is not possible to deterministically obtain a post-
measurement state $\ket{\psi(\vec{\theta})}$ that does not depend on the signs
of parameters $\pm\theta_{i}$. To be more precise, if the original resource
state in Fig. 2 is denoted by $\ket{G_{11}}$, and after measuring qubits $4$
and $5$ we project on the outcomes $\ket{\theta_{-}}_{4}$ and
$\ket{\theta_{+}}_{5}$, respectively, we have the equality with the case when
we project on the outcomes $\ket{\theta_{+}}_{4}$ and $\ket{\theta_{-}}_{5}$,

$\displaystyle\begin{split}\bra{\theta_{-}}_{4}\bra{\theta_{+}}_{5}\ket{G_{11}}=&\bra{\theta_{+}}_{4}\bra{\theta_{+}}_{5}Z_{4}\ket{G_{11}}\\\
=&\bra{\theta_{+}}_{4}\bra{\theta_{+}}_{5}Z_{l}X_{m}Z_{r}Z_{5}\ket{G_{11}}\\\
=&\bra{\theta_{+}}_{4}\bra{\theta_{-}}_{5}Z_{l}X_{m}Z_{r}\ket{G_{11}}.\end{split}$
(8)

On the other hand, if we project on the outcomes $\ket{\theta_{+}}_{4}$ and
$\ket{\theta_{+}}_{5}$, we have the equality with the case when we project on
the outcomes $\ket{\theta_{-}}_{4}$ and $\ket{\theta_{-}}_{5}$,

$\displaystyle\begin{split}\bra{\theta_{-}}_{4}\bra{\theta_{-}}_{5}\ket{G_{11}}=&\bra{\theta_{+}}_{4}\bra{\theta_{+}}_{5}Z_{4}Z_{5}\ket{G_{11}}\\\
=&\bra{\theta_{+}}_{4}\bra{\theta_{+}}_{5}Z_{l}X_{m}Z_{r}\ket{G_{11}}\\\
=&\bra{\theta_{+}}_{4}\bra{\theta_{+}}_{5}Z_{l}X_{m}Z_{r}\ket{G_{11}}.\end{split}$
(9)

While the random byproduct on the left (l), middle (m), and right (r) qubits
can be corrected in all the cases by classical post-processing, the post-
measurement states are not necessarily equal in the two cases present in Eqs.
(8, 9). Consequently, any such protocol, including patterns without a flow,
would require a postselection to obtain the “all-green” results, generally
requiring an exponential sampling overhead.

The pattern in Fig. 2 has a distinct measurement order and, thus, a flow.
$\ket{\theta_{-}}_{i}$ outcomes on any blue qubits can always be compensated
by the neighboring qubit in the upper measurement layer without introducing
inequivalent possible post-measurement state parametrization.

##  3 Measurement-based VQE

Ferguson et al. [32] presented two methods for transferring the gate-based VQE
to MBQC. The first method involves translating the parametrized gate-based
circuit into MBQC measurement patterns using the universal MBQC patterns
introduced by Raussendorf et al. [29]. While this approach may be suitable for
platforms exclusively supporting MBQC, as anticipated for photonic quantum
computers, it may be less appealing when evaluating the depth reduction
performance of MBQC on gate-based machines. Certain “cheap” operations in the
gate-based implementation, like single qubit rotations, require considerably
many qubits and adaptive measurements to implement with MBQC.

The second MBVQE method introduced in Ref. [32] is a more “MBQC-native”
approach, which forms the foundation of our work and inspired many other [33,
34, 35, 36, 37]. To illustrate, let us assume that we want to study an
$n$-qubit Hamiltonian using MBVQE. In this method, we select $n$ output-
qubits, a graph state, to act as the host for the parametrized $n$-qubit post-
measurement state. These qubits are called ansatz qubits. We have the
flexibility to choose a specific graph structure of the ansatz qubits,
aligning it with, for instance, known symmetries of the Hamiltonian or the
qubit-connectivity of the hardware. To introduce parametrization, we attach
additional qubits called decoration qubits to the ansatz qubits, all together
forming a large graph state. These decoration qubits are measured in varied
bases $R(\theta_{i})$, introducing a variational parameter $\theta_{i}$ per
decoration qubit. Once all $k$ decoration qubits are measured, the state of
the ansatz qubits depends on $k$ variational parameters. These parameters can
be optimized classically, following the standard approach utilized in VQE.

A further freedom of design in this scheme is how these decoration qubits are
attached to the ansatz qubits and how many.

###  3.1 MBVQE with edge-wise decoration

In Ref. [32], the authors decided on an edge-wise decoration strategy in the
context of a problem-specific MBVQE ansatz for studying perturbed instances of
the toric code. The ansatz qubits are chosen as the local-Clifford (LC)
equivalent graph state of the noise-free toric code’s ground state. Since the
perturbative terms weaken the ground state’s entanglement, decorations should
allow tweaking the correlation strength of the ansatz qubits. Inspired by this
idea, the edge-wise decoration suggests attaching four qubits to each edge in
the ansatz-graph, with each of the two qubits from the added four, allocated
to a vertex in an original graph (see Fig. 2). While this MBVQE ansatz shows a
favorable expressivity with respect to specific Hamiltonians [32], it is vital
to acknowledge that this edge-wise decoration scheme is impractical whenever
the ansatz graph state has a degree higher than one. Attaching multiple edge-
wise decorations to a single ansatz vertex breaks the flow condition,
prohibiting deterministic computation.

Figure 3: The effective quantum circuit that is deterministically implemented
when all byproducts are corrected that may occur during measurements for the
depicted MBVQE-ansatz. Increasing the number of decoration layers is
equivalent to increasing the gate-depth.

###  3.2 Deterministic MBVQE with node-wise decoration

In the context of MBVQE, a stringent treatment of random byproducts is
essential when starting from a highly entangled graph state as a resource
since the number of non-equalizable measurement outcomes grows exponentially
with the number of flow-infringing qubits. This, naturally, makes
postselection impractical with realistic problem sizes. To address this, we
propose a decoration scheme that guarantees a flow in all cases.

To this end, we take a “copy” of the ansatz graph $G_{0}=(V_{0},E_{0})$, and
call it the first decoration layer graph $G_{1}=(V_{1},E_{1})$. Every vertex
$v^{(1)}_{i}\in G_{1}$ is then connected to a vertex $v^{(0)}_{i}\in G_{0}$.
In an iterative way, we can then define the $l$-th decoration layer, where we
add the $l$-th copy of $G_{0}$ and connect its vertices with the ones in the
layer $(l-1)$. See Fig. 2 for a simple $3$-qubit example with $3$ decoration
layers. Similar measurement patterns have been considered in Refs. [36, 37].
This approach allows the correction of any $Z$ byproducts by leveraging the
stabilizer of the neighboring qubit in the above layer, starting the
measurements from the bottom layer. We call such a decoration scheme node-wise
decoration. This decoration scheme differs from the edge-wise one in resource
theoretic requirements: the edge-wise scheme maintains a planar graph, while
the node-wise scheme requires an additional dimension to the ansatz graph. In
Fig. 2, our ansatz graph is linear, demanding the preparation of a regular 2D
cluster state as the resource state. For a 2D ansatz graph, a three-
dimensional cluster state becomes necessary, which can be used as a resource
for fault-tolerant MBQC [54, 55, 56].

Since we aim to explore the depth-reduction capabilities of MBVQE compared to
gate-based VQE, we choose resource states that can be efficiently prepared on
current (superconducting) NISQ devices without the need for SWAP gates. Thus,
we limit to MBVQE-patterns that can be generated from a two-dimensional
cluster state. The gate-based equivalent circuit resulting from such patterns
(see Fig. 3) resembles a typical hardware-efficient entangler ansatz often
used in NISQ applications [43, 6]. As entangler circuits typically contain
nearest-neighbor interactions only, we demand that the resource-state
preparation is efficient and preferably constant in gate-depth to justify an
MB implementation on GB platforms for gate-depth reduction.

While the cluster state topology is naturally given on some platforms like
Google’s Sycamore-chip [1] with 2D-lattice qubit connectivity, other platforms
may have sparser connectivity as IBM’s quantum chips that exhibit a heavy-hex
lattice [57]. A naive implementation of the cluster state on such a device
would require the usage of many SWAP gates. Fortunately, there are already
known techniques to modify graph states with Pauli measurements and local
unitaries [58, 50]. In Appendix B, we demonstrate a measurement pattern that
generates cluster states from heavy-hex graph states with Pauli measurements
only.

##  4 Results and Experiments

###  4.1 Simulation of the $XY$\- and Schwinger models

We simulate the performance of the introduced MBVQE ansatz with two physical
Hamiltonians, the Schwinger model [59, 60],

$\displaystyle H_{S}=$
$\displaystyle\frac{J}{2}\sum^{S-2}_{n=1}\sum^{S-1}_{k=n=1}(S-k)Z_{n}Z_{k}$
$\displaystyle+$ $\displaystyle
w\sum^{S-1}_{n=1}(\sigma^{+}_{n}\sigma^{-}_{n+1}+\mathrm{H.C.})+\frac{\mu}{2}\sum^{S}_{n=1}(-1)^{n}Z_{n}$
$\displaystyle-$ $\displaystyle\frac{J}{2}\sum^{S-1}_{n=1}n\ \mathrm{mod}\
2\sum^{n}_{k=1}Z_{k},$ (10)

where $\sigma^{\pm}_{n}=\frac{1}{2}(X_{n}\pm iY_{n})$, and the perturbed
$XY$-model,

$\displaystyle H_{XY}$
$\displaystyle=\sum_{i=1}^{n-1}\frac{1+g}{2}X_{i}X_{i+1}+\frac{1-g}{2}Y_{i}Y_{i+1}$
$\displaystyle+\sum_{i=1}^{2}d\;Z_{i},$ (11)

as test beds. An arbitrary Euler rotation

$\displaystyle\begin{aligned} \\\
\hfil\displaystyle\begin{split}U3(\zeta,\eta,\xi)=\begin{pmatrix}\cos\frac{\zeta}{2}&-e^{i\xi}\sin\frac{\zeta}{2}\\\
e^{i\eta}\sin\frac{\zeta}{2}&e^{i(\eta+\xi)}\cos\frac{\zeta}{2}\end{pmatrix}\end{split}\end{aligned}$
(12)

is additionally applied to the output qubits, effectively implementing a basis
change of both Hamiltonians. To study the efficacy of the final Euler
rotations, we additionally test the MBVQE ansatz without them for $H_{XY}$. We
vary the size of both Hamiltonians from $4$ to $10$ qubits and employ $1$ to
$9$ node-wise decoration layers. We execute the identical configuration ten
times, generating the plots shown in Figs. (4-4), which display the average
relative error between the approximate and the exact ground state, with the
curve width representing the variance across the runs. The L-BFGS-B optimizer
[61] paired with gradient estimates from finite differences are used to
optimize the variational parameters.

Figure 4: A: In the scaling study, we vary the number of ansatz qubits
corresponding to the problem dimension and the number of appended decoration
layers, resulting in an $n\times l$ cluster state. Each decoration qubit
introduces a variational parameter $\theta_{i}$. In addition to the
variational decoration layer, we permit arbitrary local unitaries on the
ansatz qubits following the measurement of the decoration qubits. B: The
Jordan-Wigner transformed Schwinger model is examined for two to five fermions
(corresponding to four to ten qubits) with $J=w=1$. We investigate the
Hamiltonian ground-state problem in two scenarios: an uncritical case
($\mu=4$, left) and a critical or close to critical setting ($\mu=-0.7$,
right). The relative errors of the approximate ground state energies compared
to the exact solutions are plotted against the problem size in qubits. Line
thickness indicates the variance from executing the same MBQVE circuit $10$
times, while the color represents the number of applied node-wise decoration
layers. Increasing the layer count improves accuracy, but the scaling
accessible in the current simulations is insufficient for the exact ground
state recovery, in general. We could recover the exact ground state in the
$4$-qubit scenario for both settings, but it becomes more difficult for higher
qubit counts, although the estimate is more accurate in the uncritical case.
C: This figure is analogous to Fig. 4, showing the results for the linear
$XY$-model with an external Pauli-$Z$ perturbation of $d=0.01$ with problem
sizes varied from four to ten qubits. We investigate two cases: the
anisotropic case ($g=1$, left), equivalent to the Ising model, and the
isotropic case ($g=0$, right). The observed trends are consistent with those
in the previous figure, indicating that increased layering leads to improved
approximations. Notably, the left case exposes a limitation of the ansatz, as
disentangling a linear chain necessitates multiple layers of decorations. This
can be avoided by modifying the ansatz qubits. D: The same $XY$-model
Hamiltonians are examined, but local $U3(\zeta,\eta,\xi)$ rotations on the
ansatz qubits are omitted. This results in a slight quality decline, as the
decoration layers are exhausted for implementing the local rotations.

Generally, the ground state is well approximated when dealing with small
Hamiltonians. A linear increase in the number of layers improves the estimates
but does not yield accurate solutions for larger Hamiltonians. This outcome
was anticipated, as our ansatz emulates the hardware-efficient ansatz,
exhibiting the same limitations.

The Schwinger model is examined at $\mu=-0.7$, critical in the second
order[13, 62], and at $\mu=4$, situated far from the critical point, in all
cases with $J=w=1$. The uncritical scenario is easier to approximate; the
quality of the estimated ground state energy deteriorates around $9$ qubits.
This deterioration is already evident for the $6$-qubit Hamiltonian in the
critical case. See Fig. 4.

Our hardware-efficient MBVQE ansatz demonstrates relatively better performance
regarding the relative error than the entangler ansatz employed in Ref. [32].
In their approach, the relative error decreases below $0.2$ only using 8
decoration layers[32], whereas our ansatz achieves a significantly lower
relative error of less than $10^{-5}$ already with two decoration layers.

Fig. 4 illustrates the results obtained from analyzing the $XY$-Hamiltonian.
The Pauli-$Z$ perturbation term remains constant across all sites, with a
fixed value $d=0.01$. Choosing $g=1$ corresponds to the transverse field
Hamiltonian, while $g=0$ marks the critical point. In the case of the
uncritical setting, where the ground state is a product state, we can achieve
high levels of accuracy for larger Hamiltonians. However, as the system size
increases, it becomes increasingly challenging to disentangle our initially
highly entangled resource state with small numbers of decoration layers. For
the critical $XY$-model, the results are similar to those of the Schwinger
model. The accuracy of the estimates improves with an increasing number of
decoration layers, but an additional number of layers accessible in the
simulations is insufficient to reach the ground state accurately.

###  4.2 $XY$-model on IBM hardware

After discussing the optimal performance of the MBVQE entangler ansatz, our
next objective is to gain a better understanding of its applicability on
current gate-based quantum computers. Hardware experiments were carried out on
the IBM platform, successfully executing quantum simulations with up to $127$
qubits, recently shown in Ref. [63]. While adaptive measurements, or dynamic
circuits as they are called within the Qiskit environment [64], are available,
we found that in our use case they did not work as well as using a
postselection strategy (of course, neglecting the sampling overhead) – future
improvements in the dynamical control of the hardware will change this.
Another challenge lies in the effective preparation of the resource state at
the start. To address these concerns, we executed experiments using a
measurement pattern that can be implemented on a heavy-hex lattice without
requiring SWAP gates. Furthermore, this pattern is designed to be shallow
regarding decoration layers and contains only up to one adaptive measurement.

In order to accommodate the current hardware capacities, we propose a tree-
ansatz in Fig. 5. Following the general correction scheme of the measurement
byproducts in Section 2.2, the only adaptive measurement we need to perform is
that caused by a measurement outcome on the “parent-qubit” measured in
$R(\theta_{1})$ basis. We found that using more adaptive measurements leads to
significantly higher degree of noise in all our use cases. Measurement
outcomes of the remaining qubits can be treated by a classical post-processing
of the measurement results on the output qubits.

Figure 5: A: We analyze the 4-qubit XY model using the depicted MBVQE-tree-
ansatz on IBM hardware, employing a single variational parameter. This ansatz
is suitable for larger values of $g$. The MBVQE procedure is performed twice,
once using dynamic circuits (i.e., adaptive measurements) and once with
postselection. Both error-mitigated estimates align closely with simulated
data, falling within the expected error margin. B: Clifford data regression is
conducted for dynamic circuits (left panels) and postselection (right panels)
using $Y$ measurements (top) and $X$ measurements (bottom). We applied linear
regression to the Clifford points and estimated the quality of the fits. Our
analysis reveals that the mean-squared error (MSE) of the non-Clifford data
points in relation to the fit is smaller for postselection. However, the fit
fails to capture the error behavior of the $Y$ expectation value in the
dynamic circuits. C: CDR successfully mitigates hardware noise, with the
expected observation that errors in Y for the dynamic circuits are not
captured. The error margins of the postselection method are more accurate.
Combining data from the top and bottom, according to the Hamiltonian, and
finding the minimizing parameters results in Plot A.

We test the tree-ansatz for the periodic $4$-qubit $XY$-model,

$\displaystyle H_{XY}$
$\displaystyle\equiv-\frac{1+g}{2}H_{X}+\frac{1-g}{2}H_{Y}$
$\displaystyle=-\frac{1+g}{2}(X_{1}X_{2}+X_{2}X_{3}+X_{3}X_{4}+X_{4}X_{1})$
$\displaystyle\quad+\frac{1-g}{2}(Y_{1}Y_{2}+Y_{2}Y_{3}+Y_{3}Y_{4}+Y_{4}Y_{1}).$
(13)

Note that, we introduce a minus sign in front of $H_{X}$ compared to the
conventional $XY$-Hamiltonian. However, our Hamiltonian is equivalent up to
local unitaries to the conventional $XY$-Hamiltonian, since
$Y_{2}Y_{4}H_{X}Y_{2}Y_{4}=-H_{X}$ and $Y_{2}Y_{4}H_{Y}Y_{2}Y_{4}=H_{Y}$.

We choose the $H_{XY}$ Hamiltonian, as for any $g$, it is straightforward to
derive the expectation value for our ansatz,

$\displaystyle\begin{split}\expectationvalue{H_{XY}}=&-(1+g)(1+\cos\theta_{1})\\\
-&\frac{1-g}{2}\left(\sin\theta_{1}(\sin\theta_{2}+\sin\theta_{3})\right),\end{split}$
(14)

and minimize it for $\theta_{2}=\theta_{3}=\frac{\pi}{2}$. To say it
otherwise, with our choice of the ansatz and the Hamiltonian, the measurements
on the mid-layer qubits are always fixed in the Pauli-$Y$ basis. As a result,
we are able to test dynamic circuits only varying one parameter, $\theta_{1}$
without demanding implementation of gradient optimization for other bases,
which could possibly lead to additional error accumulation. In our hardware
experiments, we chose to adapt the measurement basis of
$\theta_{2}=\pm\frac{\pi}{2}$ depending on the outcome of the first
measurement.

As an alternative approach to compare with, we use a postselection strategy,
in which we only select those events for which the first qubit is projected on
the $\ket{\theta_{+}}_{1}$. Then, there is no need for any corrections in the
second layer. Since for our choice of the ansatz and the Hamiltonian, we only
need to implement Pauli-$Y$ measurements on the middle layer, we could
effectively achieve the postselection with the classical post-processing,
reducing the number of circuit runs. Furthermore, we use a combination of
randomized compiling [65], dynamical decoupling [66] and Clifford data
regression (CDR) [67] (c.f. Appendix C for more details) as error mitigation
strategies. We ran our experiments on ibm_algiers ($27$ qubits) using a total
budget of $100\;000$ shots to estimate each expectation value.

We perform a scan over the parameter range $\theta_{1}\in[0,\pi]$ using $20$
points in total, measuring the expectation values of $H_{X}$ and $H_{Y}$ (c.f.
Eq. (13)) separately. From these $20$ data points, we use the Clifford points
$\theta_{1}=0,\,\pi/2\ {\rm and}\ \pi$ as mitigation points. The measured
values are different from the ideal classically simulated points due to noise
in the circuit. In Fig. 5, we plot the measured values vs. the ideal values,
comparing the postselection strategy with the dynamic circuits for the $H_{X}$
and $H_{Y}$ expectation values. Under the assumption of a global noise
channel, there should be a linear relationship between the measured and ideal
values [67]. As can be seen in Fig. 5, this model works considerably better
for the postselection strategy than for the dynamic circuits – the mean-
squared error of the recorded non-Clifford data points with respect to the CDR
fit is larger for data points gathered from dynamic circuits. We perform
linear fits using the mitigation data and use them to mitigate the measured
expectation values.

In Fig. 5, we show the expectation values $H_{X}$ (upper panel) and $H_{Y}$
(lower panel). As can be seen, the mitigated values are in very good agreement
with the ideal, simulated values. From the data shown in Fig. 5 we calculate
the estimated groundstate energy of the Hamiltonian in Eq. (13)

by adding the data of $H_{X}$ and $H_{Y}$ with the correct factors, see Fig. 5
for results.

Figure 6: The performance of the measurement-based (MB) cluster state
preparation is compared to the regular gate-based (GB) implementation, which
requires high SWAP gate counts on the IBM hardware with heavy-hex
connectivity. The plots display the expectation values of the cluster state
stabilizer over 10,000 samples, with the median over all terms indicated by a
star. Each method is evaluated once with read-out mitigation and once with
additional randomization and dynamic decoupling, the latter marked by an
asterisk. Top: In the case of the $2\times 3$ cluster state, the GB method
exhibits higher fidelity. This can be attributed to the absolute CNOT count,
which is higher in the MB case, although the gate depth is smaller.
Furthermore, the GB compiler can select the best-performing six qubits from
the 27-qubit chip, while MB utilizes the entire chip. Bottom: The impact of
depth reduction becomes evident for larger examples, such as the $4\times 7$
cluster implemented on the 127-qubit machine. In GB, most expectation values
collapse to 0, revealing total randomness. In contrast, MB shows significant
signals, although still far away from the expected value of 1.

###  4.3 Cluster state preparation on IBM hardware

In anticipation of advancements in adaptive measurements and decreasing
readout errors, we develop a strategy to generate cluster states from heavy-
hex graph states without the need for SWAP gates. To engineer this pattern, we
leverage the graphical rules of Pauli measurements, which transform each
“honeycomb” into a cluster square up to local byproduct gates, which can be
corrected based on the measurement results on the auxiliary qubits. One
drawback of this approach is the number of lost qubits.

To assess the effectiveness of measurement-based resource generation, we
perform experiments on a $27$\- and a $127$-qubit quantum computer. Using the
Pauli measurement-based preparation technique, we generate a $2\times 3$
cluster state on the $27$-qubit machine and a $4\times 7$ cluster state on the
$127$-qubit machine. As a point of comparison, we also generate these cluster
states using a naive gate-based preparation method. Subsequently, we measure
the stabilizers of the generated cluster states. The commuting stabilizer
terms were grouped such that the observables to measure are reduced to two
[68].

It should be noted that the measurement-based method induces local unitaries
that modify the stabilizer of the state, which could be corrected using
dynamic circuits. However, to avoid readout errors in such adaptive
measurements, we refrained from correcting these unitaries to avoid additional
sources of noise. Instead, we adjusted the stabilizers to be measured
accordingly. For cluster qubits with an even number of neighbors, the
additional unitaries are a combination from $\\{I,Z\\}$; both either commute
with the graph stabilizer or introduce a minus sign that can be eliminated
with classical post-processing. On the other hand, qubits with an odd number
of neighbors could have additional Clifford gates from the set
$\\{I,Z,\sqrt{\pm iZ}\\}$. These $\sqrt{\pm iZ}$ gates commute with $Z$ but
transform $X$ to $\pm Y$. Consequently, we performed measurements in the $Y$
basis for such qubits whenever appropriate.

We used the sampler primitive provided in ibm-runtime to conduct our
experiments. The sampler has a built-in feature to correct read-out errors
using matrix-free measurement mitigation as implemented in the M3 package
[69]. Furthermore, we implemented each experiment twice, once without
additional modifications and another time using randomized compiling [65] and
dynamic decoupling techniques [66]. The results show that these methods indeed
reduce the scattering of data points, particularly in measurement-based
implementations. We ran the $27$-qubit experiment on ibmq_ehingen and the
$125$-qubit experiment on ibm_nazca. In all experiments, we used a total
budget of $10\;000$ shots to measure each of the two observables that had to
be estimated to calculate the expectation values of all stabilizers.

We show the measured expectation value of each stabilizer state in Fig. 6. In
the case of the small six-qubit example, the naive gate-based method proved to
be more effective. This can be attributed to the internal compiler selecting
the best-performing $6$ qubits out of the available $27$ in the direct
implementation. In contrast, the measurement-based method requires the use of
the entire chip, even though some qubits may be unreliable due to bad
calibration of two-qubit gates. Additionally, although there is a clear
advantage in terms of CNOT depth (defined as the CNOT count of the longest
path in the compiled circuit as a directed acyclic graph) for the measurement-
based method with a depth of $3$ compared to $11$ in the gate-based
implementation, the total count of CNOT gates required in the circuit is $22$
for the measurement-based method and $16$ for the gate-based implementation.
However, the benefits of the measurement-based method become apparent in a
larger example, such as creating a $4\times 7$ cluster state using $125$
qubits. In this case, we are able to obtain the cluster state with a CNOT
depth of $5$ and a total CNOT count of $142$. In comparison, the gate-based
implementation results in a CNOT depth of $69$ and a total CNOT count of
$186$. Although the stabilizer measurement in the measurement-based
implementation still exhibits significant noise in most terms, we observe
modest signals, especially with randomization and dynamic decoupling. In such
cases, despite the overall resource state still being noisy and potentially
impractical for MBQC, there is value in transitioning to the MBQC-based state
preparation scheme.

##  5 Conclusions and Outlook

In this work, we focus on one of the most popular hybrid quantum-classical
algorithms, the variational quantum eigensolver (VQE), in the measurement-
based setting (MB). The MBVQE approach has recently gained a lot of attention.
In our work, we put a particular focus on the importance of determinism when
performing MBVQE, which we identify with the notion of flow in a resource
state. For the cases where the flow is absent, we argue either for the
inevitable exponential computational overhead caused by post-selection, or for
the impossibility of convergence of the classical optimizer even in the
perfect noiseless simulations. The issue becomes even more drastic if we need
to use, for example, the read-out error mitigation.

As a next step, we propose a new MBVQE protocol featuring a resource state
that respects determinism and resembles the widely used problem-agnostic
hardware-efficient VQE ansatz. Moreover, our ansatz can be prepared “hardware
efficiently” on NISQ devices, such that it reduces the circuit-depth
requirements by respecting the native qubit connectivity of hardware and
avoids additional SWAP operations. We evaluate our approach using ideal
simulations on the Schwinger Hamiltonian and $XY$-model of an increasing
number of qubits. As a result, we obtain MBQC patterns that implement an
instance of the entangler ansatz that gets more expressive by increasing the
number of decoration layers in the proposed resource state. Additionally, we
use IBM hardware, which allows for the mid-circuit measurements to test our
results. Here, we propose a tree-shaped decoration scheme for the $4$-qubit
$XY$-Model with a single adaptive measurement step and compare its performance
in the case when determinism is ensured by post-selection (so no mid-circuit
measurements). In this particular scenario we find that the post-selection
works significantly better, since the adaptive measurement steps induce
additional hardware noise.

Finally, we propose an efficient MBQC-inspired method to prepare the resource
state, specifically the cluster state, on hardware with heavy-hex
connectivity, requiring just a single measurement round. We implemented this
scheme on quantum computers with $27$ and $127$ qubits and observed notable
improvements for larger cluster states, although direct gate-based
implementation achieved higher fidelity for smaller instances.

From our analysis, we conclude that the MBVQE approach offers a fruitful test
bed to characterize the expressivity of ansatz in VQE applications. As
expected from the theory of MBQC, the MBVQE also offers a trade-off between
different hardware requirements: e.g., a qubit count and gate-depth. Thus,
depending on the architecture and bottlenecks of available near-term hardware,
one can choose between the gate-based and MB-based approaches.

Recent announcements of next-generation quantum hardware, such as IBM Heron
with native $CZ$ gates [70], are promising for resource preparation in MBQC.
It is also interesting to explore how such modular quantum hardware with
classical interconnects behaves regarding resource state generation. The
effectiveness of MB approaches ultimately depends on the accuracy of adaptive
measurements. Improvements in this area are anticipated on the path towards
fault-tolerant quantum computing. Until these advancements materialize, it is
worth exploring and adopting error-mitigation methods specific to MBQC [71].

We thank Martin Kliesch, Wolfgang Dür, Luca Dellantonio, and Juani Bermejo-
Vega for fruitful discussions. This work was in part supported by the research
project Zentrum für Angewandtes Quantencomputing (ZAQC), which is funded by
the Hessian Ministry for Digital Strategy and Innovation and the Hessian
Ministry of Higher Education, Research and the Arts (MH). We acknowledge the
use of IBM Quantum services for this work. The views expressed are those of
the authors, and do not reflect the official policy or position of IBM or the
IBM Quantum team.

##  Appendix A Overview of other previous works

The work by Ferguson et al. [32] inspired further investigations of the
performance and resource requirements of other VQE instances in the MBQC
framework. Proietti et al. [33] studied an MBQC native way to implement the
Quantum Approximate Optimization Algorithm (QAOA) [44], which makes use of the
fact that operations that are diagonal in the computational basis are
exceptionally efficient in MBQC as “input” and “output” qubits coincide [72].
They tested the MBQC algorithm by simulating this method in the context of the
k-max cut problem. Qin et al. [34] showed an MBQC version of the Hamiltonian
variational ansatz [73] that makes use of efficient 2-body operators
implemented in the same sense as the QAOA operator. Combined with local
rotations on the input/output qubits; it is possible to generate all Pauli-
rotation. Chan et al. [35] included these efficient MBQC-based multi-qubit
Pauli-rotations, also referred to as Pauli-gadgets, within a gate-based
circuit. This work included experiments on the IBM 7-qubit machine that
indicate a possible advantage of operating gate-based hardware in MBQC manner.
Marqversen et al. [36] discuss and exhibit how MBQC can reduce hardware
resources for applications such as VQE, demonstrate specific use cases, and
introduce efficient ways to simulate MBQCs with tensor networks. While
Majumder et al. [37] used almost the same MBQC pattern as in our work to
generate their ansatz and acknowledge the importance of byproducts in MBVQE,
but, instead of correcting them, they utilize this randomness to learn
probability distributions better in the context of generative modeling. A part
of these works used post-selection to guarantee the convergence of variational
algorithm [32, 33], while others used different measurement bases than
$R(\theta)$ and achieved determinism [35, 38, 36]. While sufficient attention
was not given to determinism in the initial works of MBVQE, recent papers
(including ours) discuss the problem extensively for distinct settings and
applications.

##  Appendix B Graph state modifications

Here, we recall some valuable relations of graph states that are used in this
work. Local complementations (LC) implements [74, 75] the local unitary
transformation of the following form:

$\ket{G_{LC}}=\sqrt{-iX_{i}}\bigotimes_{j\in\mathcal{N}(i)}\sqrt{iZ_{j}}\ket{G}.$
(15)

Figure 7: Left: Graph states linked through local complementation are local
Clifford equivalent. In our experiments, we choose to implement the left graph
since it can be directly executed on the IBM device. Right: By preparing the
heavy-hex graph state and measuring the blue qubits in the illustrated bases,
it is possible to generate a cluster state without the need for SWAP gates.
However, it’s important to note that the measurement outcomes of Pauli
measurements on graph states are not graph states but rather local unitary
equivalents. Despite this, these “byproduct” operators can be efficiently
computed from the measurement outcomes of the auxiliary qubits and accounted
for in subsequent calculations due to Gottesman–Knill theorem.

If we want to implement a specific graph state, we could choose to implement
the representative from the LC equivalence class with the lowest edge count or
the representative that best suits the hardware topology. That is shown in
Fig. 7 – the edge between the two qubits in the middle layer requires SWAP
gates if implemented naively on quantum hardware with heavy-hex connectivity.
However, it is easy to see that this edge can eliminated by local
complementation on the parent-qubit. This graph can be directly mapped onto
the respective hardware.

To generate a cluster state with constant gate depth from hardware featuring
heavy-hex connectivity, we start by creating a heavy-hex graph state.

It is known that graph states stay graph states up to specific local unitaries
under Pauli measurements, and efficient graphical rules were developed to
predict the post-measurement state [50, 58]. By using these rules and minding
the commutation relation of measurement projectors and the emerging local
unitaries (see Table 1), it is possible to design an effective measurement
pattern illustrated in Fig. 7.

With this scheme, each honeycomb becomes a square of the cluster state. Hence,
on ibmq_ehingen, we can generate a $2\times 3$ cluster state, and on the
127-qubit machine ibmq_nazca $4\times 7$.

$P_{x,\pm}\sigma_{z}=\sigma_{z}P_{x,\mp}$, |  |  $P_{y,\pm}\sqrt{-i\sigma_{z}}=\sqrt{-i\sigma_{z}}P_{x,\pm}$,
---|---|---
$P_{y,\pm}\sigma_{z}=\sigma_{z}P_{y,\mp}$, |  |  $P_{y,\pm}\sqrt{i\sigma_{y}}=\sqrt{i\sigma_{y}}P_{y,\pm}$,
$P_{z,\pm}\sigma_{z}=\sigma_{z}P_{z,\pm}$, |  |  $P_{y,\pm}\sqrt{-i\sigma_{y}}=\sqrt{-i\sigma_{y}}P_{y,\pm}$,
|  |  $P_{y,\pm}\sqrt{i\sigma_{z}}=\sqrt{i\sigma_{z}}P_{x,\mp}$,
$P_{x,\pm}\sqrt{-i\sigma_{z}}=\sqrt{-i\sigma_{z}}P_{y,\mp}$, |  |  $P_{z,\pm}\sqrt{-i\sigma_{z}}=\sqrt{-i\sigma_{z}}P_{z,\pm}$,
$P_{x,\pm}\sqrt{i\sigma_{y}}=\sqrt{i\sigma_{y}}P_{z,{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\mp}}$, |  |  $P_{z,\pm}\sqrt{i\sigma_{y}}=\sqrt{i\sigma_{y}}P_{x,\pm}$,
$P_{x,\pm}\sqrt{-i\sigma_{y}}=\sqrt{-i\sigma_{y}}P_{z,\mp}$, |  |  $P_{z,\pm}\sqrt{-i\sigma_{y}}=\sqrt{-i\sigma_{y}}P_{x,{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\mp}}$,
$P_{x,\pm}\sqrt{i\sigma_{z}}=\sqrt{i\sigma_{z}}P_{y,\mp}$, |  |  $P_{z,\pm}\sqrt{i\sigma_{z}}=\sqrt{i\sigma_{z}}P_{z,\pm}$.
Table 1: The commutation relations play an essential role in simulating post-
measurement states of multiple Pauli measurements on a graph state, as the
resulting state is a graph state up to local Clifford operations. These
additional operations alter successive measurements but in an efficiently
simulable manner. The precise form of these operators and the table can be
found in [50]. We opted to include the commutation relations in the appendix
due to the presence of typos in the highlighted equations of the original
source.

##  Appendix C Clifford-data regression

Due to noise in the quantum hardware, expectation values extracted from
circuit measurements have to be post-processed. Several error-mitigation
strategies exist, such as zero-noise-extrapolation [76], self-mitigation [77],
or probabilistic error cancellation [78, 71]. For our experiments, we choose
Clifford-data regression [67] since dynamic circuits can be easily
incorporated into this framework.

Given a parametrized circuit $\mathcal{C}(\theta_{1},\dotsc\theta_{n})$ and a
Hamiltonian $H$, of which we try to estimate the expectation value
$\bra{\psi}H\ket{\psi}$ at some given point $(\theta_{1},\dotsc\theta_{n})$,
we first evaluate the circuit at near-Clifford points, i.e., we substitute
some of the parameters by multiples of $\pi/2$, $\theta_{i}=n\cdot\pi/2,\
n\in\mathbb{N}$, for which the circuit can be simulated efficiently
classically. At these so-called regression points, we can find a relationship
between the measured, noisy expectation values
$\expectationvalue{H}{\psi}_{\rm noisy}$, and the exact, simulated ones,

$\expectationvalue{H}{\psi}_{\rm exact}=f(\expectationvalue{H}{\psi}_{\rm
noisy},a_{0},\dotsc a_{n}),$ (16)

where $a_{i}$ are model parameters. In this work, we assume a linear
relationship, i.e.,

$\expectationvalue{H}{\psi}_{\rm exact}=a_{0}\expectationvalue{H}{\psi}_{\rm
noisy}+a_{1},$ (17)

which can be justified by the assumption of the existence of a global noise
channel [67].

## References

  * [1] Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C. Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, Fernando G. S. L. Brandao, David A. Buell, et al.  “Quantum supremacy using a programmable superconducting processor”.  Nature 574, 505–510 (2019).
  * [2] Han-Sen Zhong, Hui Wang, Yu-Hao Deng, Ming-Cheng Chen, Li-Chao Peng, Yi-Han Luo, Jian Qin, Dian Wu, Xing Ding, Yi Hu, et al.  “Quantum computational advantage using photons”.  Science 370, 1460–1463 (2020).
  * [3] Sergey Bravyi, David Gosset, and Robert König.  “Quantum advantage with shallow circuits”.  Science 362, 308–311 (2018).
  * [4] P. W. Shor.  “Algorithms for quantum computation: discrete logarithms and factoring”.  In Proceedings 35th Annual Symposium on Foundations of Computer Science.  Pages 20–22.  IEEE (1994).
  * [5] Earl T. Campbell, Barbara M. Terhal, and Christophe Vuillot.  “Roads towards fault-tolerant universal quantum computation”.  Nature 549, 172–179 (2017).
  * [6] Nikolaj Moll, Panagiotis Barkoutsos, Lev S. Bishop, Jerry M. Chow, Andrew Cross, Daniel J. Egger, Stefan Filipp, Andreas Fuhrer, Jay M. Gambetta, Marc Ganzhorn, et al.  “Quantum optimization using variational algorithms on near-term quantum devices”.  Quantum Sci. Technol. 3, 030503 (2018).
  * [7] Jarrod R. McClean, Jonathan Romero, Ryan Babbush, and Alán Aspuru-Guzik.  “The theory of variational hybrid quantum-classical algorithms”.  New J. Phys. 18, 023023 (2016).
  * [8] John Preskill.  “Quantum Computing in the NISQ era and beyond”.  Quantum 2, 79 (2018).  arXiv:1801.00862v3.
  * [9] Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, Man-Hong Yung, Xiao-Qi Zhou, Peter J. Love, Alán Aspuru-Guzik, and Jeremy L. O’Brien.  “A variational eigenvalue solver on a photonic quantum processor”.  Nat. Commun. 5, 1–7 (2014).
  * [10] Jules Tilly, Hongxiang Chen, Shuxiang Cao, Dario Picozzi, Kanav Setia, Ying Li, Edward Grant, Leonard Wossnig, Ivan Rungger, George H. Booth, et al.  “The Variational Quantum Eigensolver: A review of methods and best practices”.  Phys. Rep. 986, 1–128 (2022).
  * [11] Maximilian Amsler, Peter Deglmann, Matthias Degroote, Michael P. Kaicher, Matthew Kiser, Michael Kühn, Chandan Kumar, Andreas Maier, Georgy Samsonidze, Anna Schroeder, et al.  “Quantum-enhanced quantum Monte Carlo: an industrial view” (2023).  arXiv:2301.11838.
  * [12] Mari Carmen Bañuls, Rainer Blatt, Jacopo Catani, Alessio Celi, Juan Ignacio Cirac, Marcello Dalmonte, Leonardo Fallani, Karl Jansen, Maciej Lewenstein, Simone Montangero, et al.  “Simulating lattice gauge theories within quantum technologies”.  Eur. Phys. J. D 74, 1–42 (2020).
  * [13] C. Kokail, C. Maier, R. van Bijnen, T. Brydges, M. K. Joshi, P. Jurcevic, C. A. Muschik, P. Silvi, R. Blatt, C. F. Roos, et al.  “Self-verifying variational quantum simulation of lattice models”.  Nature 569, 355–360 (2019).
  * [14] Yasar Y. Atas, Jinglei Zhang, Randy Lewis, Amin Jahanpour, Jan F. Haase, and Christine A. Muschik.  “SU(2) hadrons on a quantum computer via a variational approach”.  Nat. Commun. 12, 1–11 (2021).
  * [15] Bela Bauer, Dave Wecker, Andrew J. Millis, Matthew B. Hastings, and Matthias Troyer.  “Hybrid Quantum-Classical Approach to Correlated Materials”.  Phys. Rev. X 6, 031045 (2016).
  * [16] Carlos Bravo-Prieto, Ryan LaRose, M. Cerezo, Yigit Subasi, Lukasz Cincio, and Patrick J. Coles.  “Variational Quantum Linear Solver” (2019).  arXiv:1909.05820.
  * [17] Ajinkya Borle, Vincent Elfving, and Samuel J. Lomonaco.  “Quantum approximate optimization for hard problems in linear algebra”.  SciPost Phys. Core 4, 031 (2021).
  * [18] Lennart Bittel and Martin Kliesch.  “Training Variational Quantum Algorithms Is NP-Hard”.  Phys. Rev. Lett. 127, 120502 (2021).
  * [19] Yihui Quek, Daniel Stilck França, Sumeet Khatri, Johannes Jakob Meyer, and Jens Eisert.  “Exponentially tighter bounds on limitations of quantum error mitigation” (2022).  arXiv:2210.11505.
  * [20] Lennart Bittel, Jens Watty, and Martin Kliesch.  “Fast gradient estimation for variational quantum algorithms” (2022).  arXiv:2210.06484.
  * [21] Leo Zhou, Sheng-Tao Wang, Soonwon Choi, Hannes Pichler, and Mikhail D. Lukin.  “Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices”.  Phys. Rev. X 10, 021067 (2020).
  * [22] Harper R. Grimsley, Sophia E. Economou, Edwin Barnes, and Nicholas J. Mayhall.  “An adaptive variational algorithm for exact molecular simulations on a quantum computer”.  Nat. Commun. 10, 1–9 (2019).
  * [23] Harper R. Grimsley, George S. Barron, Edwin Barnes, Sophia E. Economou, and Nicholas J. Mayhall.  “Adaptive, problem-tailored variational quantum eigensolver mitigates rough parameter landscapes and barren plateaus”.  npj Quantum Inf. 9, 1–8 (2023).
  * [24] David Wierichs, Christian Gogolin, and Michael Kastoryano.  “Avoiding local minima in variational quantum eigensolvers with the natural gradient optimizer”.  Phys. Rev. Res. 2, 043246 (2020).
  * [25] Giacomo De Palma, Milad Marvian, Cambyse Rouzé, and Daniel Stilck França.  “Limitations of Variational Quantum Algorithms: A Quantum Optimal Transport Approach”.  PRX Quantum 4, 010309 (2023).
  * [26] Sergey Bravyi, Alexander Kliesch, Robert Koenig, and Eugene Tang.  “Obstacles to Variational Quantum Optimization from Symmetry Protection”.  Phys. Rev. Lett. 125, 260505 (2020).
  * [27] Lior Eldar and Aram W. Harrow.  “Local Hamiltonians Whose Ground States Are Hard to Approximate”.  In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS).  Pages 15–17.  IEEE (2017).
  * [28] Lennart Bittel, Sevag Gharibian, and Martin Kliesch.  “Optimizing the depth of variational quantum algorithms is strongly QCMA-hard to approximate” (2022).  arXiv:2211.12519.
  * [29] Robert Raussendorf, Daniel E. Browne, and Hans J. Briegel.  “Measurement-based quantum computation on cluster states”.  Phys. Rev. A 68, 022312 (2003).
  * [30] H. J. Briegel, D. E. Browne, W. Dür, R. Raussendorf, and M. Van den Nest.  “Measurement-based quantum computation”.  Nat. Phys. 5, 19–26 (2009).
  * [31] Anne Broadbent and Elham Kashefi.  “Parallelizing Quantum Circuits” (2007).  arXiv:0704.1736.
  * [32] R. R. Ferguson, L. Dellantonio, A. Al Balushi, K. Jansen, W. Dür, and C. A. Muschik.  “Measurement-Based Variational Quantum Eigensolver”.  Phys. Rev. Lett. 126, 220501 (2021).
  * [33] Massimiliano Proietti, Filippo Cerocchi, and Massimiliano Dispenza.  “Native measurement-based quantum approximate optimization algorithm applied to the Max $K$-Cut problem”.  Phys. Rev. A 106, 022437 (2022).
  * [34] Zheng Qin, Xiufan Li, Yang Zhou, Shikun Zhang, Rui Li, Chunxiao Du, and Zhisong Xiao.  “Applicability of Measurement-based Quantum Computation towards Physically-driven Variational Quantum Eigensolver” (2023).  arXiv:2307.10324.
  * [35] Albie Chan, Zheng Shi, Luca Dellantonio, Wolfgang Dür, and Christine A. Muschik.  “Hybrid variational quantum eigensolvers: merging computational models” (2023).  arXiv:2305.19200.
  * [36] F. K. Marqversen and N. T. Zinner.  “Applications and resource reductions in measurement-based variational quantum eigensolvers” (2023).  arXiv:2302.00795.
  * [37] Arunava Majumder, Marius Krumm, Tina Radkohl, Hendrik Poulsen Nautrup, Sofiene Jerbi, and Hans J. Briegel.  “Variational measurement-based quantum computation for generative modeling” (2023).  arXiv:2310.13524.
  * [38] He-Liang Huang, Xiao-Yue Xu, Chu Guo, Guojing Tian, Shi-Jie Wei, Xiaoming Sun, Wan-Su Bao, and Gui-Lu Long.  “Near-Term Quantum Computing Techniques: Variational Quantum Algorithms, Error Mitigation, Circuit Compilation, Benchmarking and Classical Simulation” (2022).  arXiv:2211.08737.
  * [39] Daniel E. Browne, Elham Kashefi, Mehdi Mhalla, and Simon Perdrix.  “Generalized flow and determinism in measurement-based quantum computation”.  New J. Phys. 9, 250 (2007).
  * [40] Vincent Danos and Elham Kashefi.  “Determinism in the one-way model”.  Phys. Rev. A 74, 052310 (2006).
  * [41] Kosuke Mitarai, Makoto Negoro, Masahiro Kitagawa, and Keisuke Fujii.  “Quantum Circuit Learning” (2018).  arXiv:1803.00745.
  * [42] Maria Schuld, Ville Bergholm, Christian Gogolin, Josh Izaac, and Nathan Killoran.  “Evaluating analytic gradients on quantum hardware” (2018).  arXiv:1811.11184.
  * [43] Abhinav Kandala, Antonio Mezzacapo, Kristan Temme, Maika Takita, Markus Brink, Jerry M. Chow, and Jay M. Gambetta.  “Hardware-efficient Variational Quantum Eigensolver for Small Molecules and Quantum Magnets” (2017).  arXiv:1704.05018.
  * [44] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann.  “A Quantum Approximate Optimization Algorithm” (2014).  arXiv:1411.4028.
  * [45] Gian-Luca R. Anselmetti, David Wierichs, Christian Gogolin, and Robert M. Parrish.  “Local, Expressive, Quantum-Number-Preserving VQE Ansatze for Fermionic Systems” (2021).  arXiv:2104.05695.
  * [46] William J. Huggins, Joonho Lee, Unpil Baek, Bryan O’Gorman, and K. Birgitta Whaley.  “A Non-Orthogonal Variational Quantum Eigensolver” (2019).  arXiv:1909.09114.
  * [47] Jonathan Romero, Ryan Babbush, Jarrod R. McClean, Cornelius Hempel, Peter J. Love, and Alán Aspuru-Guzik.  “Strategies for quantum computing molecular energies using the unitary coupled cluster ansatz”.  Quantum Sci. Technol. 4, 014008 (2018).
  * [48] Jérôme F. Gonthier, Maxwell D. Radin, Corneliu Buda, Eric J. Doskocil, Clena M. Abuan, and Jhonathan Romero.  “Measurements as a roadblock to near-term practical quantum advantage in chemistry: resource analysis” (2020).  arXiv:2012.04001.
  * [49] Jarrod R. McClean, Sergio Boixo, Vadim N. Smelyanskiy, Ryan Babbush, and Hartmut Neven.  “Barren plateaus in quantum neural network training landscapes”.  Nat. Commun. 9, 1–6 (2018).
  * [50] M. Hein, W. Dür, J. Eisert, R. Raussendorf, M. Van den Nest, and H.-J. Briegel.  “Entanglement in Graph States and its Applications” (2006).  arXiv:quant-ph/0602096.
  * [51] Maarten Van den Nest, Akimasa Miyake, Wolfgang Dür, and Hans J. Briegel.  “Universal Resources for Measurement-Based Quantum Computation”.  Phys. Rev. Lett. 97, 150504 (2006).
  * [52] Aleks Kissinger and John van de Wetering.  “Universal MBQC with generalised parity-phase interactions and Pauli measurements”.  Quantum 3, 134 (2019).  arXiv:1704.06504v3.
  * [53] Mariami Gachechiladze, Otfried Gühne, and Akimasa Miyake.  “Changing the circuit-depth complexity of measurement-based quantum computation with hypergraph states”.  Phys. Rev. A 99, 052304 (2019).
  * [54] Mikkel V. Larsen, Christopher Chamberland, Kyungjoo Noh, Jonas S. Neergaard-Nielsen, and Ulrik L. Andersen.  “A fault-tolerant continuous-variable measurement-based quantum computation architecture” (2021).  arXiv:2101.03014.
  * [55] R. Raussendorf, J. Harrington, and K. Goyal.  “A fault-tolerant one-way quantum computer” (2005).  arXiv:quant-ph/0510135.
  * [56] Benjamin J. Brown and Sam Roberts.  “Universal fault-tolerant measurement-based quantum computation” (2018).  arXiv:1811.11780.
  * [57] Jared B. Hertzberg, Eric J. Zhang, Sami Rosenblatt, Easwar Magesan, John A. Smolin, Jeng-Bang Yau, Vivekananda P. Adiga, Martin Sandberg, Markus Brink, Jerry M. Chow, et al.  “Laser-annealing Josephson junctions for yielding scaled-up superconducting quantum processors” (2020).  arXiv:2009.00781.
  * [58] Simon Anders and Hans J. Briegel.  “Fast simulation of stabilizer circuits using a graph-state representation”.  Phys. Rev. A 73, 022334 (2006).
  * [59] Julian Schwinger.  “The Theory of Quantized Fields. I”.  Phys. Rev. 82, 914–927 (1951).
  * [60] N. Klco, E. F. Dumitrescu, A. J. McCaskey, T. D. Morris, R. C. Pooser, M. Sanz, E. Solano, P. Lougovski, and M. J. Savage.  “Quantum-Classical Computation of Schwinger Model Dynamics using Quantum Computers” (2018).  arXiv:1803.03326.
  * [61] Dong C. Liu and Jorge Nocedal.  “On the limited memory BFGS method for large scale optimization”.  Math. Program. 45, 503–528 (1989).
  * [62] T. M. R. Byrnes, P. Sriganesh, R. J. Bursill, and C. J. Hamer.  “Density matrix renormalization group approach to the massive Schwinger model”.  Phys. Rev. D 66, 013002 (2002).
  * [63] Youngseok Kim, Andrew Eddins, Sajant Anand, Ken Xuan Wei, Ewout van den Berg, Sami Rosenblatt, Hasan Nayfeh, Yantao Wu, Michael Zaletel, Kristan Temme, et al.  “Evidence for the utility of quantum computing before fault tolerance”.  Nature 618, 500–505 (2023).
  * [64] Qiskit contributors.  “Qiskit: An open-source framework for quantum computing” (2023).
  * [65] Joel J. Wallman and Joseph Emerson.  “Noise tailoring for scalable quantum computation via randomized compiling”.  Phys. Rev. A 94, 052325 (2016).
  * [66] Lorenza Viola and Seth Lloyd.  “Dynamical suppression of decoherence in two-state quantum systems”.  Phys. Rev. A 58, 2733–2744 (1998).
  * [67] Piotr Czarnik, Andrew Arrasmith, Patrick J. Coles, and Lukasz Cincio.  “Error mitigation with Clifford quantum-circuit data”.  Quantum 5, 592 (2021).
  * [68] Géza Tóth and Otfried Gühne.  “Entanglement detection in the stabilizer formalism” (2005).
  * [69] Paul D. Nation, Hwajung Kang, Neereja Sundaresan, and Jay M. Gambetta.  “Scalable mitigation of measurement errors on quantum computers”.  PRX Quantum 2, 040326 (2021).
  * [70] David C. McKay, Ian Hincks, Emily J. Pritchett, Malcolm Carroll, Luke C. G. Govia, and Seth T. Merkel.  “Benchmarking Quantum Processor Performance at Scale” (2023).  arXiv:2311.05933.
  * [71] Riddhi S. Gupta, Ewout van den Berg, Maika Takita, Kristan Temme, and Abhinav Kandala.  “Probabilistic error cancellation for measurement-based quantum circuits” (2023).  arXiv:2310.07825.
  * [72] Dan E. Browne and Hans J. Briegel.  “One-way Quantum Computation - a tutorial introduction” (2006).  arXiv:quant-ph/0603226.
  * [73] Dave Wecker, Matthew B. Hastings, and Matthias Troyer.  “Progress towards practical quantum variational algorithms”.  Phys. Rev. A 92, 042303 (2015).
  * [74] Jeremy C. Adcock, Sam Morley-Short, Axel Dahlberg, and Joshua W. Silverstone.  “Mapping graph state orbits under local complementation”.  Quantum 4, 305 (2020).  arXiv:1910.03969v2.
  * [75] Maarten Van den Nest, Jeroen Dehaene, and Bart De Moor.  “Graphical description of the action of local Clifford transformations on graph states”.  Phys. Rev. A 69, 022316 (2004).
  * [76] Kristan Temme, Sergey Bravyi, and Jay M. Gambetta.  “Error mitigation for short-depth quantum circuits”.  Phys. Rev. Lett. 119, 180509 (2017).
  * [77] Sarmed A Rahman, Randy Lewis, Emanuele Mendicelli, and Sarah Powell.  “Self-mitigating Trotter circuits for SU(2) lattice gauge theory on a quantum computer”.  Phys. Rev. D 106, 074502 (2022).  arXiv:2205.09247.
  * [78] Ewout Van Den Berg, Zlatko K Minev, Abhinav Kandala, and Kristan Temme.  “Probabilistic error cancellation with sparse pauli–lindblad models on noisy quantum processors” (2023).