# Benchmarking Multipartite Entanglement Generation with Graph States

René Zander, Colin Kai-Uwe Becker
Fraunhofer Institute for Open Communication Systems (FOKUS)
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

As quantum computing technology slowly matures and the number of available
qubits on a QPU gradually increases, interest in assessing the capabilities of
quantum computing hardware in a scalable manner is growing. One of the key
properties for quantum computing is the ability to generate multipartite
entangled states. In this paper, aspects of benchmarking entanglement
generation capabilities of noisy intermediate-scale quantum (NISQ) devices are
discussed based on the preparation of graph states and the verification of
entanglement in the prepared states. Thereby, we use entanglement witnesses
that are specifically suited for a scalable experiment design. This choice of
entanglement witnesses can detect A) bipartite entanglement and B) genuine
multipartite entanglement for graph states with constant two measurement
settings if the prepared graph state is based on a 2-colorable graph, e.g., a
square grid graph or one of its subgraphs. With this, we experimentally verify
that a fully bipartite entangled state can be prepared on a $127$-qubit IBM
Quantum superconducting QPU, and genuine multipartite entanglement can be
detected for states of up to $23$ qubits with quantum readout error
mitigation.

###### Index Terms:

Quantum computing, Benchmarking, Entanglement, Entanglement Witnesses, Graph
States

##  I Introduction

Experiments for verifying entanglement generation capabilities of gate-based
quantum computers gained traction in the recent years in line with the
availability of QPUs with an increasing number of qubits, which is evident
from various published results. These include showing genuine multipartite
entanglement for a $27$-qubit GHZ state [1], bipartite entanglement for a
$65$-qubit graph state [2], genuine multipartite entanglement on $51$ qubits
[3] and most recently analyzing bipartite and multipartite entanglement for up
to $433$ qubits [4]. Furthermore, defining a benchmarking protocol for
assessing entanglement generation capabilities [5] using the volumetric
benchmarking framework [6] was explored.

Graph states are well-known and researched due to their relevance as a
universal resource state for measurement-based quantum computing [7], and as
graph codes in quantum cryptography applications and quantum error correction
[8]. Recently, graph states were used as encoding scheme for an equivalence
checking algorithm for comparing bit-strings efficiently on gate-based quantum
computers [9]. The main focus of this paper lies in establishing graph states
as a means for efficiently benchmarking and comparing aspects of entanglement
generation capabilities for gate-based quantum computing architectures. For
this, bipartite and genuine multipartite entanglement is detected for graph
states based on a $2$-colorable graph by using different entanglement
witnesses in a scalable experiment design that requires only two measurement
settings. The corresponding measurement results are already sufficient to
verify bipartite and multipartite entanglement not only for the entire graph
state but also for states that correspond to connected subgroups of qubits.
This is done by evaluating expectation values for different entanglement
witnesses that are solely dependent on the obtained measurement results. This
particular choice of entanglement witnesses thereby provides a new approach
adding to the methods from previous publications. We demonstrate our approach
through experiments on three $127$-qubit IBM Quantum QPUs. In particular, we
experimentally verify that a fully bipartite entangled state can be prepared
for $127$ qubits, and genuine multipartite entanglement can be detected for
states of up to $23$ qubits with quantum readout error mitigation. The
proposed experiments are aimed to be used as a benchmark for gate-based QPUs.
The results provide fair performance comparisons for hardware architectures if
the chosen graph states can be natively prepared on each QPU without
limitations imposed by the respective qubit topologies.

The paper is structured as follows. An introduction to the structure of
entanglement for multipartite systems and entanglement witnesses is provided
in Section (II). In Section (III), we start with a brief overview about graph
states and the stabilizer formalism, and discuss the belonging entanglement
witnesses. Here, we also provide novel insights into the analysis of the
structure of entanglement for subgroups of connected qubits. The experiment
design, the obtained results, as well as aspects of benchmarking are discussed
in Section (IV). Finally, we conclude with an outlook based on the experiment
results in Section (V). The Appendix (VI) contains detailed information about
the algorithmic implementation used for conducting the experiments as well as
additional mathematical proofs.

##  II Entanglement

In the following, we briefly discuss the structure of entanglement of
multipartite systems as well as entanglement witnesses. Let $M$ be a set of
qubits and $m=|M|$. An $m$-qubit mixed state $\rho$ is separable if it can be
written as probabilistic mixture of separable pure states with respect to a
fixed bipartition $A,B$ of the set $M$ of qubits. That is,

$\rho=\sum\limits_{k}p_{k}\rho_{k}^{A}\otimes\rho_{k}^{B}$ (1)

where $\rho_{k}^{A}$ and $\rho_{k}^{B}$ are pure states of the subsystems $A$
and $B$, respectively. The coefficients $p_{k}$ define a probability
distribution, that is, they are positive and sum up to one. Denote the set of
separable states by $\mathfrak{S}$. A mixed state is bipartite entangled if it
is not separable with respect to all bipartitions of qubits of the system.

An $m$-qubit mixed state $\rho$ is fully-separable if it can be written as
probabilistic mixture of fully-separable pure states, that is,

$\rho=\sum\limits_{k}p_{k}\rho_{k}^{(1)}\otimes\dotsb\otimes\rho_{k}^{(m)}$
(2)

where $\rho_{k}^{(i)}$ are pure states of qubit $i$. Denote the set of fully-
separable states by $\mathfrak{S}_{f}$. A mixed state is entangled if it is
not fully separable.

An $m$-qubit mixed state $\rho$ is biseparable if it can be written as convex
mixture of separable states, that is,

$\rho=\sum\limits_{k}q_{k}\rho_{k}$ (3)

where $\rho_{k}$ are separable states and may have different bipartitions. The
coefficients $q_{k}$ define a probability distribution. Denote the set of
biseparable states by $\mathfrak{S}_{b}$. A mixed state is genuinely
multipartite entangled (GME) if it is not biseparable. Clearly,
$\mathfrak{S}_{f}\subset\mathfrak{S}\subset\mathfrak{S}_{b}$.

###  II-A Entanglement witnesses

Entanglement witnesses can serve as a helpful tool for experimentally
demonstrating the presence of entanglement in a quantum state. An entanglement
witness for genuine multipartite entanglement is an operator $W$ that has non-
negative expectation on all biseparable states, i.e.,

$\mathrm{tr}(W\rho)\geq 0,\quad\text{for all }\rho\in\mathfrak{S}_{b},$ (4)

and a negative expectation on at least one entangled state
$\tilde{\rho}\notin\mathfrak{S}_{b}$. That is, measuring a negative
expectation for $W$ verifies that a state is genuinely multipartite entangled.
Similarly, one defines entanglement witnesses for detecting, e.g., non-full-
separability (entanglement) or non-separability with respect to certain
bipartitions of the set of qubits.

In an experimental setting, the prepared state deviates from the target state
due to the presence of noise in state-of-the-art NISQ devices. For a given
pure state $\ket{\psi}$, the projector-based witness [10]

$W=c\mathbb{I}-\ket{\psi}\bra{\psi}$ (5)

can detect genuine multipartite entanglement. Here, $c$ is the smallest
constant such that $\mathrm{tr}(W\rho)\geq 0$ for all biseparable states
$\rho\in\mathfrak{S}_{b}$. It can be computed via Schmidt decomposition [11].
The witness (5) detects a state $\rho$ as genuinely multipartite entangled if
the fidelity between $\ket{\psi}$ and $\rho$ is greater than $c$, i.e.,
$\mathcal{F}(\ket{\psi},\rho)>c$.

In general, the number of measurement settings required to evaluate the
operator (5) grows exponentially with the number of qubits. For a scalable
experiment design it is desirable to construct entanglement witnesses that
require only a few measurement settings. For example, for $m$-qubit graph
states there are witnesses of the form [10]:

$W=c_{0}\mathbb{I}-\sum\limits_{k=1}^{m}c_{k}S_{k}$ (6)

where $c_{k}$ are constants and the operators $S_{k}$ are tensor products of
Pauli matrices. Then each $S_{k}$ requires only one measurement setting, so
that $W$ can be evaluated with at most $m$ measurement settings.

##  III Graph states

We provide a brief introduction to graph states [8, 12].

Let $G=(V,E)$ be a graph where $V$ is the set of vertices and $E$ is the set
of edges. Denote the number of vertices $|V|$ by $n$. A graph state
$\ket{G}\in(\mathbb{C}^{2})^{\otimes n}$ can be associated as follows:
vertices represent qubits initialized in the
$\ket{+}=(\ket{0}+\ket{1})/\sqrt{2}$ state, and edges $e=(i,j)$ represent the
controlled $Z$-operation $\mathrm{CZ}^{(i,j)}$ acting on qubits $i$ and $j$.
Recall that

$\mathrm{CZ}^{(i,j)}=\pi_{+}^{i}\otimes\mathbb{I}^{j}+\pi_{-}^{i}\otimes\sigma_{z}^{j}$
(7)

where $\pi_{\pm}^{i}=(\mathbb{I}\pm\sigma_{z}^{i})/2$ are the projectors onto
the eigenspaces of the operator $\sigma_{z}^{i}$ for eigenvalues $+1$ and
$-1$, respectively.

That is, the graph state $\ket{G}$ is defined as

$\ket{G}=\prod_{(i,j)\in E}\mathrm{CZ}^{(i,j)}\ket{+}^{\otimes n}.$ (8)

Define the operators

$S_{i}=\sigma_{x}^{i}\prod\limits_{j\in N_{i}}\sigma_{z}^{j},\quad
i=1,\dotsc,n,$ (9)

where $N_{i}=\\{j\in V\mid(i,j)\in E\\}$ is the set of neighbors of the vertex
$i$. The operators $S_{i}$ commute and generate a set of so-called stabilizer
operators that consists of $2^{n}$ elements,

$\SS=\left\\{\prod\limits_{i=1}^{n}S_{i}^{x_{i}}\mid
x\in\\{0,1\\}^{n}\right\\}.$ (10)

The graph state $\ket{G}$ is the unique state that is an eigenstate to
eigenvalue $+1$ for all $S_{i}$, that is,

$S_{i}\ket{G}=\ket{G},\quad\text{for all }i=1,\dotsc,n.$ (11)

The projector on $\ket{G}$ can be written as product of so-called stabilizer
projectors $(\mathbb{I}+S_{i})/2$ onto the eigenspace of $S_{i}$ with
eigenvalue $+1$, that is,

$\ket{G}\bra{G}=\prod\limits_{i\in V}\dfrac{\mathbb{I}+S_{i}}{2}.$ (12)

For a graph $G=(V,E)$ and a subset $U\subset V$, we define the stabilizer
projector of the subset $U$ as

$P(U,G)=\prod\limits_{i\in U}\frac{\mathbb{I}+S_{i}}{2}.$ (13)

In particular, $\ket{G}\bra{G}=P(V,G)$.

###  III-A Entanglement witnesses for bipartite entanglement

Here, we discuss how to detect bipartite entanglement in a prepared quantum
state $\rho$ with target quantum state $\ket{G}$.

The following entanglement witness can be used to detect non-separability. It
is known that the same witness can be used to rule out full separability [10,
8]. Here, we generalize this result to the weaker assumption of separability.

######  Proposition III.1.

Let $G=(V,E)$ be a graph and $(i,j)\in E$. The operator $W_{ij}$ can witness
non-separability (entanglement),

$W_{ij}=\mathbb{I}-S_{i}-S_{j}$ (14)

with $\langle W_{ij}\rangle\geq 0$ for all states
$\rho\in(\mathbb{C}^{2})^{\otimes n}$ that are separable with respect to any
bipartition $A,B$ with $i\in A$ and $j\in B$.

###### Proof.

This is a reformulation of the necessary condition for separability given in
Proposition (VI.4). ∎

Let $G=(V,E)$ and $\rho\in(\mathbb{C}^{2})^{\otimes n}$ be a density operator
with qubits $V$. For an edge $e=(i,j)$ we define its weight $w(e)=\langle
W_{ij}\rangle$. Let $G^{\prime}=(V,E^{\prime})$ with $E^{\prime}=\\{e\in E\mid
w(e)<0\\}$ be the subgraph of $G$ with all edges deleted that have non-
negative weight. Then the connected components of $G^{\prime}$ correspond to
bipartite entangled subsets of qubits.

###  III-B Entanglement witnesses for multipartite entanglement

In the following, we discuss how to detect multipartite entanglement in a
prepared quantum state $\rho$ with target quantum state $\ket{G}$.

For any graph state $\ket{G}$ the projector-based witness

$W(G)=\frac{1}{2}\mathbb{I}-\ket{G}\bra{G}$ (15)

can detect genuine multipartite entanglement, with $\langle W(G)\rangle\geq 0$
for all biseparable states. This follows from the fact that for any graph
state the fidelity between $\ket{G}$ and any biseparable state $\rho$ is upper
bounded by $1/2$ [13]. It was also shown that this bound is tight in the sense
that there is a biseparable state $\rho$ such that
$\mathrm{tr}(\ket{G}\bra{G}\rho)=1/2$.

To measure the projector $\ket{G}\bra{G}$, one considers the expansion

$\ket{G}\bra{G}=\frac{1}{2^{n}}\sum_{S\in\SS}S$ (16)

which is a weighted sum of all $2^{n}$ stabilizer operators. Therefore, the
number of stabilizer measurements grows exponentially in the number of qubits
and is practically feasible only for small systems.

With Lemma (VI.1) we obtain entanglement witnesses that may require fewer
measurements [13]. Let $\mathcal{V}=\\{V_{1},\dotsc,V_{k}\\}$ be a partition
of the vertex set $V$ into disjoint subsets. Then the operator

$W(\mathcal{V},G)=\left(k-\frac{1}{2}\right)\mathbb{I}-\sum\limits_{l=1}^{k}P(V_{l},G)$
(17)

can detect genuine multipartite entanglement, with $\langle
W(\mathcal{V},G)\rangle\geq 0$ for all biseparable states. Typical choices of
the partition $\mathcal{V}$ are the following: if $\mathcal{V}=\\{V\\}$, we
obtain the projector-based witness $W(\\{V\\},G)=W(G)$. If
$\mathcal{V}=\\{\\{i\\}\\}_{i\in V}$, we obtain (up to a factor of $1/2$) the
stabilizer sum witness [10, 5]

$W^{\mathrm{s}}(G)=(n-1)\mathbb{I}-\sum\limits_{l=1}^{n}S_{l}.$ (18)

Each stabilizer $S_{l}$ is a tensor product of Pauli matrices and hence
requires only one measurement setting. Then $W^{\mathrm{s}}(G)$ can be
evaluated with at most $n$ measurement settings.

Lastly, a map $c\colon V\rightarrow C$, where $C$ is the set of colors, is a
proper vertex coloring if any two vertices that have the same color are not
connected by an edge. A graph is called $k$-colorable if it has a coloring
with $|C|=k$ colors. The minimal number $k$ of colors is called the chromatic
number $\chi$ of the graph. A coloring induces a partition
$\mathcal{V}^{c}=\\{V_{c}\\}_{c\in C}$ of the vertex set $V$ into disjoint
subsets such that any two vertices in the same subset are not connected by an
edge. The case where the partition $\mathcal{V}$ corresponds to such a proper
vertex coloring was investigated for GHZ and $1$-D cluster states [10] and
subsequently proposed as a systematic method for construction of entanglement
witnesses for graph states [13]. We denote the coloring-based witness by
$W^{c}(G)=W(\\{V_{c}\\}_{c\in C},G)$. In this case, the expectation of each
projector $P(V_{c},G)$ can be computed with one measurement setting
$\otimes_{i\in V_{c}}X_{i}\otimes_{j\in V\setminus V_{c}}Z_{j}$. Then the
computation of the expectation of $W^{c}(G)$ requires only $|C|$ measurement
settings. In particular, for graph states corresponding to $2$-colorable
graphs, e.g., $1$-D and $2$-D cluster states, entanglement witnesses that
require only two measurement settings can be found.

In experiments, the prepared state $\rho$ differs from the target graph state
$\ket{G}\in(\mathbb{C}^{2})^{\otimes n}$ due to the presence of noise. The
white noise tolerance is commonly used as indicator of the robustness of a
witness [12]. It is defined as follows. For a state $\tilde{\rho}$ and a
witness $W$, consider the state

$\rho(p)=(1-p)\tilde{\rho}+p\mathbb{I}/2^{n},$ (19)

for $p\in[0,1]$, that is, $\rho(p)$ is a stochastic mixture of the state
$\tilde{\rho}$ and the maximally mixed state. Then the white noise tolerance
is the maximal $p_{\mathrm{tol}}$ such that $\rho(p)$ is detected by the
witness $W$, i.e., $\mathrm{tr}(W\rho(p))<0$ for all
$p\in[0,p_{\mathrm{tol}})$. For the witnesses $W(\mathcal{V},G)$, for some
partition of the vertex set $\mathcal{V}=\\{V_{1},\dotsc,V_{k}\\}$, we have
$1/k\geq p_{\mathrm{tol}}>1/(2k)$ [13]. In fact, for certain graph states,
e.g., $1$-D and $2$-D cluster states, one can construct witnesses such that
their white noise tolerance approaches one as the number of qubits increases.
That is, under the presence of white noise the fidelity between the prepared
state $\rho$ and the target graph state $\ket{G}$ can decrease exponentially
with the number of qubits, but the state $\rho$ is still genuinely
multipartite entangled and can be detected by a witness [12]. Yet, as these
witnesses are an augmentation of the projector-based witness $W(G)$, the
number of local measurement settings grows exponentially with the number of
qubits.

Finally, a partition
$\widetilde{\mathcal{V}}=\\{\widetilde{V}_{1},\dotsc,\widetilde{V}_{l}\\}$ is
a refinement of the partition $\mathcal{V}=\\{V_{1},\dotsc,V_{k}\\}$ if for
all $i\in\\{1,\dotsc,l\\}$ there is a $j\in\\{1,\dotsc,k\\}$ such that
$\widetilde{V}_{i}\subset V_{j}$. Then with Lemma (VI.1), we see that

$W(\widetilde{\mathcal{V}},G)\geq W(\mathcal{V},G).$ (20)

Here, for Hermitian operators $A,B$, we write $A\geq B$ indicating that
$(A-B)$ is positive semidefinite. In particular, the witness
$W(\widetilde{\mathcal{V}},G)$ has a lower white noise tolerance. In Appendix
(VI-A), it is shown that considering witnesses corresponding to refinements of
a partition $\mathcal{V}$ can still be useful, specifically in the context of
quantum readout error mitigation.

###  III-C Entanglement witnesses for subgraphs

Given sampled measurement results corresponding to a prepared state $\rho$
with target graph state $\ket{G}$, we discuss how to obtain information on the
ability of the QPU to generate multipartite entangled states that correspond
to subgraphs $G^{\prime}\subset G$.

Let $G=(V,E)$ be a graph and $G^{\prime}=(V^{\prime},E^{\prime})\subset G$ be
a subgraph with $E^{\prime}=\\{(i,j)\in E\mid i,j\in V^{\prime}\\}$. That is,
$G^{\prime}$ is the subgraph induced by the subset of vertices
$V^{\prime}\subset V$. Let the neighborhood $N(V^{\prime})\subset V$ be the
subset of all vertices in $G\setminus G^{\prime}$ that are adjacent to at
least one vertex in $G^{\prime}$. Let $\widetilde{E}\subset E$ be the subset
of edges that connect $G^{\prime}$ with $G\setminus G^{\prime}$. This is
illustrated in Figure (1).

Consider the stabilizer projectors

$\displaystyle P(V^{\prime},G)$ $\displaystyle=$
$\displaystyle\prod\limits_{v\in V^{\prime}}\frac{1}{2}(\mathbb{I}+S_{v}),$
(21) $\displaystyle P(V^{\prime},G^{\prime})$ $\displaystyle=$
$\displaystyle\prod\limits_{v\in
V^{\prime}}\frac{1}{2}(\mathbb{I}+S_{v}^{\prime})$ (22)

where $S_{v}$ and $S_{v}^{\prime}$ are the stabilizers of $\ket{G}$ and
$\ket{G^{\prime}}$, respectively. Clearly,
$P(V^{\prime},G^{\prime})=\ket{G^{\prime}}\bra{G^{\prime}}$. The operator
$P(V^{\prime},G^{\prime})$ is obtained from $P(V^{\prime},G)$ by replacing all
Pauli operators acting on the qubits in $G\setminus G^{\prime}$ with
identities.

One could aim to compute the expectation of the projector-based witness
$W(\\{V^{\prime}\\},G^{\prime})$ with respect to the graph state $\ket{G}$.
For example, consider the $1$-D cluster state $\rho=\ket{G}\bra{G}$ on four
qubits defined by the graph $G=(V,E)$ with $V=\\{0,1,2,3\\}$,
$E=\\{(0,1),(1,2),(2,3)\\}$, and let $G^{\prime}=(V^{\prime},E^{\prime})$ with
$V^{\prime}=\\{1,2\\}$, $E^{\prime}=\\{(1,2)\\}$ be a subgraph. In this case,
a straightforward computation shows that the reduced density operator
$\rho^{\\{1,2\\}}$ of the subsystem of qubits $\\{1,2\\}$ is given by
$\rho^{\\{1,2\\}}=\mathrm{tr}_{\\{0,3\\}}\rho=(1/4)\mathbb{I}_{2}\otimes\mathbb{I}_{2}$.
That is, the reduced state $\rho^{\\{1,2\\}}$ is separable! Accordingly, we
have $\langle W(V^{\prime},G^{\prime})\rangle\geq 0$.

More generally, given an entangled state $\rho$ on qubits $V$, the reduced
state $\rho^{V^{\prime}}$ with respect to the subset of qubits
$V^{\prime}\subset V$ might not be entangled.

Instead, we propose measuring the projector $P(V^{\prime},G)$ to obtain
information on the ability of the QPU to generate a multipartite entangled
state that corresponds to the subgraph $G^{\prime}\subset G$. An
interpretation of $P(V^{\prime},G)$ is given by the following result.

######  Lemma III.2.

The following identity holds:

$P(V^{\prime},G)=\prod\limits_{(i,j)\in\widetilde{E}}CZ^{(i,j)}\ket{G^{\prime}}\bra{G^{\prime}}\otimes\mathbb{I}\prod\limits_{(i,j)\in\widetilde{E}}CZ^{(i,j)}.$
(23)

###### Proof.

Recall that $\ket{G^{\prime}}\bra{G^{\prime}}=\prod_{v\in
V^{\prime}}(\mathbb{I}+S_{v}^{\prime})/2$. Let $(i,j)\in\widetilde{E}$. The
unitary $\mathrm{CZ}^{(i,j)}$ commutes with all stabilizer operators
$S_{v}^{\prime}$ for $v\notin\\{i,j\\}$. There is exactly one vertex $v\in
V^{\prime}$ such that $v\in\\{i,j\\}$. Without loss of generality, let $v=i$.
Then using (7) and the relation $\sigma_{x}\pi_{\pm}=\pi_{\mp}\sigma_{x}$, we
find

$\mathrm{CZ}^{(i,j)}S_{i}^{\prime}\mathrm{CZ}^{(i,j)}=\mathrm{CZ}^{(i,j)}(\pi_{-}^{i}\otimes\mathbb{I}^{j}+\pi_{+}^{i}\otimes\sigma_{z}^{j})S_{i}^{\prime}=\sigma_{z}^{j}S_{i}^{\prime}.$
(24)

The last equation follows from a straightforward calculation using the
identities $\pi_{\pm}^{2}=\pi_{\pm}$, $\pi_{+}\pi_{-}=\pi_{-}\pi_{+}=0$ and
$\pi_{+}+\pi_{-}=\mathbb{I}$ for the projectors $\pi_{\pm}$. Then the claim
follows by induction on the set of edges $\widetilde{E}$. ∎

######  Proposition III.3.

The following identity holds:

$\mathrm{tr}(P(V^{\prime},G)\rho)=\mathrm{tr}(\ket{G^{\prime}}\bra{G^{\prime}}\hat{\rho}^{V^{\prime}})$
(25)

where

$\hat{\rho}=\prod\limits_{(i,j)\in\widetilde{E}}CZ^{(i,j)}\rho\prod\limits_{(i,j)\in\widetilde{E}}CZ^{(i,j)}.$

###### Proof.

With equation (23) and the cyclic property of the trace we find
$\mathrm{tr}(P(V^{\prime},G)\rho)=\mathrm{tr}(\ket{G^{\prime}}\bra{G^{\prime}}\otimes\mathbb{I}\hat{\rho})$.
Then the claim follows from the properties of the partial trace. ∎

That is, the state $\hat{\rho}$ is obtained from the state $\rho$ by applying
controlled-$Z$ operations to all pairs of qubits $(i,j)\in\widetilde{E}$. If
$\rho=\ket{G}\bra{G}$, this amounts to removing all edges connecting
$G^{\prime}$ with $G\setminus G^{\prime}$. Then the resulting graph state
$\hat{\rho}=\ket{G^{\prime}}\bra{G^{\prime}}\otimes\ket{G\setminus
G^{\prime}}\bra{G\setminus G^{\prime}}$ is a product of the graph states for
the two subgraphs. In this case, we have
$\mathrm{tr}(\ket{G^{\prime}}\bra{G^{\prime}}\hat{\rho})=1$.

In the language of entanglement witnesses this can be stated as follows:

######  Proposition III.4.

Let $\mathcal{V}^{\prime}$ be a partition of the vertex set $V^{\prime}$. The
operator $W(\mathcal{V}^{\prime},G)$ as defined in (17) can detect genuine
multipartite entanglement, with $\langle W(\mathcal{V}^{\prime},G)\rangle\geq
0$ for all states $\rho$ on the system $V$ such that $\hat{\rho}^{V^{\prime}}$
is biseparable.

###### Proof.

For $\mathcal{V}^{\prime}=\\{V^{\prime}\\}$ this is a consequence of
Proposition (III.3) and the fact that
$W=\frac{1}{2}\mathbb{I}-\ket{G^{\prime}}\bra{G^{\prime}}$ is an entanglement
witness for $\ket{G^{\prime}}$. Then the claim for arbitrary partitions
follows from Lemma (VI.1). ∎

Let $G_{1},G_{2}\subset G$ be disjoint subgraphs such that $G_{1}\cup G_{2}$
is connected, and let $\mathcal{V}_{1},\mathcal{V}_{2}$ be partitions of the
set of vertices $V_{1},V_{2}$ of the subgraphs $G_{1},G_{2}$, respectively.
Then we have

$W(\mathcal{V}_{1}\cup\mathcal{V}_{2},G)=\frac{1}{2}\mathbb{I}+W(\mathcal{V}_{1},G)+W(\mathcal{V}_{2},G).$
(26)

In experiments, the state $\hat{\rho}^{V^{\prime}}$ differs from
$\ket{G^{\prime}}\bra{G^{\prime}}$ due to the presence of noise. In
particular, it is also affected by non-local noise acting on qubits in the
neighborhood $N(V^{\prime})$. Therefore, we assume that $\langle
W(\mathcal{V}^{\prime},G)\rangle_{\rho}\geq\langle
W(G^{\prime})\rangle_{\rho^{\prime}}$ where $\rho$ and $\rho^{\prime}$ are the
prepared states corresponding to the graph states $\ket{G}$ and
$\ket{G^{\prime}}$, respectively. In this sense, evaluating an entanglement
witness $W(\mathcal{V}^{\prime},G)$ on the prepared state $\rho$ yields
information on the ability of the QPU to prepare the graph state
$\ket{G^{\prime}}$.

123456789111 Figure 1: The $2$-D cluster graph $\mathrm{Cl}_{3\times 4}$.
Consider the subgraph $G^{\prime}=(V^{\prime},E^{\prime})$ with
$V^{\prime}=\\{1,2,4,5\\}$ and $E^{\prime}=\\{(1,2),(1,4),(2,5),(4,5)\\}$.
Then $N(V^{\prime})=\\{3,6,7,8\\}$ and, as indicated by the red lines,
$\widetilde{E}=\\{(2,3),(4,7),(5,6),(5,8)\\}$.

##  IV Experiments

###  IV-A Experiment Design

####  IV-A1 State preparation

We prepare the native graph state $G=(V,E)$, i.e., the graph state
corresponding to the graph defined by the coupling map of the device, on the
$127$-qubit IBM Quantum superconducting devices ibm_brisbane, ibm_sherbrooke
and ibm_cusco. All three devices have the same so-called heavy-hex layout, as
shown in Figure (2). All qubits are prepared in the
$\ket{+}=(\ket{0}+\ket{1})/\sqrt{2}$ state by applying a Hadamard gate to
their initial $\ket{0}$ state. Then the controlled-$Z$ gates corresponding to
the edges are applied in three layers. Within each layer, the controlled-$Z$
gates are executed in parallel.

Figure 2: A visualization of the heavy-hex layout of the $127$-qubit IBM
devices. The edge coloring (red, green, blue) corresponds to three layers of
controlled-$Z$ gates. Within each layer, the controlled-$Z$ gates can be
executed in parallel. The shape of the nodes (round, rectangular) corresponds
to a vertex coloring of the graph.

####  IV-A2 Measurements

Since the heavy-hex graph is $2$-colorable, we measure the prepared graph
state in two measurement settings $\otimes_{i\in V_{1}}X_{i}\otimes_{j\in
V_{2}}Z_{j}$ and $\otimes_{i\in V_{2}}X_{i}\otimes_{j\in V_{1}}Z_{j}$, where
$\\{V_{1},V_{2}\\}$ is the partition of the vertex set $V$ corresponding to
the coloring as indicated in Figure (2). For each measurement setting,
$N=30000$ shots are executed. In the following, these measurement results are
used to calculate expectations of stabilizers projectors and with this,
entanglement witnesses for bipartite and multipartite entanglement.

####  IV-A3 QREM

Quantum readout error mitigation aims to correct measurement errors by a
classical post-processing of the measurement outcomes [14, 15]. Measurement
noise for a system of $M$ qubits can be characterized classically by the
relation

$p_{\mathrm{noisy}}=A\cdot p_{\mathrm{ideal}}$ (27)

where $p_{\mathrm{noisy}}$ is the $2^{M}$-dimensional probability vector
describing the distribution of the measurement outcomes in the presence of
measurement errors, and $p_{\mathrm{ideal}}$ is the $2^{M}$-dimensional
probability vector describing the distribution of measurement outcomes in the
absence of measurement errors (but still including, e.g., gate errors), and
$A$ is a $2^{M}\times 2^{M}$-dimensional stochastic matrix. The entry $A_{ij}$
is the probability of observing the outcome $i\in\\{0,\dotsc,2^{M}-1\\}$
provided that the ideal outcome is $j\in\\{0,\dotsc,2^{M}-1\\}$. Then equation
(27) can be solved for $p_{\mathrm{ideal}}$. Note that the result is not
necessarily a probability distribution but a quasiprobability distribution: it
may contain negative values but still sums up to one. This quasiprobability
distribution can be used to compute an unbiased estimate for the expectation
of an observable [14].

In the tensor product noise model [14], we assume that the noise acts
independently on each qubit, i.e.,

$A=\bigoplus\limits_{k=0}^{M-1}A^{(k)}.$ (28)

Here, $A^{(k)}$ is the calibration matrix for qubit $k$ in the computational
basis, defined as

$A^{(k)}=\begin{pmatrix}1-P_{0,1}^{(k)}&P_{1,0}^{(k)}\\\
P_{0,1}^{(k)}&1-P_{1,0}^{(k)}\end{pmatrix}$ (29)

where $P_{i,j}^{(k)}$ is the probability of measuring qubit $k$ in state
$i\in\\{0,1\\}$ if the prepared state is $j\in\\{0,1\\}$. The error rates
$p_{i,j}^{(k)}$ are obtained from $\mathcal{O}(M)$ calibration circuits.

In general, this error mitigation method scales only to a small number of
qubits $M$. However, it can be utilized for large systems when expectations of
$m$-local observables (for a small number $m$) are computed. Recall that an
observable is $m$-local if it can be decomposed as $\sum_{l}O_{l}$ where each
term $O_{l}$ is a Hermitian operator acting on at most $m$ qubits. In this
case, the expectation for each observable $O_{l}$ can be computed from the
marginal distribution with respect to at most $m$ qubits. The $2^{m}\times
2^{m}$-dimensional calibration matrices for mitigating the marginal
distributions are the tensor products of the calibration matrices for the
respective qubits. We apply this method to calculate mitigated expectations of
stabilizer projectors and thereby entanglement witnesses. In particular, this
approach is suitable for evaluating the stabilizer sum witness for graph
states if the belonging graph has a low maximum vertex degree, e.g., for
heavy-hex graphs. It may occur that the readout error mitigation yields non-
physical values $\braket{P(U,G)}>1$. Therefore, we cap the expectations of
stabilizer projectors at $1$. Details on the implementation of evaluating
entanglement witnesses with the described readout error mitigation method are
given in Appendix (VI-A).

###  IV-B Results

We evaluate bipartite entanglement witnesses, and multipartite entanglement
witnesses for subgraphs.

####  IV-B1 Bipartite entanglement

We compute expectations of the bipartite entanglement witnesses

$W_{ij}=\mathbb{I}-S_{i}-S_{j}$ (30)

for all edges $e=(i,j)$ in the graph $G$. Negative expectations $\langle
W_{ij}\rangle<0$ show that the system is not separable with respect to the
pair of qubits $i$ and $j$. That is, there is no bipartition $A,B$ with $i\in
A$, $j\in B$ of the set of qubits $V$ such that the prepared state is
separable with respect to the bipartition $A,B$. The connected subgraphs
induced by the edges with negative expectations correspond to bipartite
entangled regions of the device.

The results are illustrated in Figures (LABEL:fig:brisbane),
(LABEL:fig:sherbrooke) and (LABEL:fig:cusco) for the devices ibm_brisbane,
ibm_sherbrooke and ibm_cusco, respectively. Notably, for ibm_brisbane full
$127$-qubit bipartite entanglement can be detected when QREM is applied.

Finally, note that similar results on bipartite entanglement were presented
for the (now retired) devices ibmq_rochester ($52$ qubits) and ibmq_manhattan
($65$ qubits) [2], and most recently also for ibm_washington ($127$ qubits)
and ibm_seattle ($433$ qubits) [4]. Information on bipartite entanglement was
obtained by performing full quantum state tomography (QST) on every pair of
connected qubits and their nearest neighbors, and then computing the
negativity between every pair of connected qubits. In general, QST on $n$
qubits requires $3^{n}$ measurement settings. If QST is performed for each
pair of connected qubits, the total number of measurement settings scales
linearly in the number of these pairs. As shown recently, this scaling can be
reduced to a constant factor by performing QST in parallel [4]. In contrast,
in this work we show that bipartite entanglement can be characterized by
measuring the prepared graph state in only two measurement settings (for
$2$-colorable graphs) and calculating the bipartite entanglement witnesses
(30).

####  IV-B2 Multipartite entanglement

We compute expectations of multipartite entanglement witnesses with respect to
subgraphs $G^{\prime}=(V^{\prime},E^{\prime})\subset G$. Denote the number of
vertices $|V^{\prime}|$ by $n^{\prime}$. The following entanglement witnesses
can be evaluated with only two measurement settings:

(i) the stabilizer sum witnesses (SSW)

$W^{\mathrm{s}}(G^{\prime},G)=(n^{\prime}-1)\mathbb{I}-\sum\limits_{l=1}^{n^{\prime}}S_{l}.$
(31)

The main advantage in utilizing this witness is that it can be computed
efficiently by summing up the previously calculated expectations of the
stabilizers for the qubits in $V^{\prime}$. However, it comes with a
theoretical disadvantage of having the lowest white noise tolerance
$p_{\mathrm{tol}}=1/n^{\prime}$ among all witnesses of the form (17).

Here, the SSW is utilized as follows.

First, we evaluate the SSW for all subgraphs $G^{\prime}\subset G$ that are
isomorphic to the $1$-D cluster graph $\mathrm{Cl}_{n}$, for $n=2,\dotsc,30$.
If $\braket{W^{\mathrm{s}}(G^{\prime},G)}<0$ for a subgraph $G^{\prime}$, this
indicates that the graph state $\ket{G^{\prime}}$ can be prepared on the
device and verified as GME. In the following, we say that the state
$\ket{G^{\prime}}$ can be verified as GME. For each number of qubits $n$, we
identify the subgraph $G^{*}_{n}\subset G$ that minimizes the expectation
$\braket{W^{\mathrm{s}}(G^{\prime},G)}$ over all subgraphs $G^{\prime}$ that
are isomorphic to $\mathrm{Cl}_{n}$. Expectations are calculated with and
without QREM.

The results are illustrated in Figure (LABEL:fig:cluster). For the devices
ibm_brisbane, ibm_sherbrooke and ibm_cusco, the results indicate that a
$23$-qubit, $21$-qubit and $21$-qubit $1$-D cluster state can be verified as
genuinely multipartite entangled when QREM is applied, respectively.

Secondly, we calculate the SSW for all $12$-qubit heavy-hex unit cells in the
graph. Expectations are calculated with and without QREM.

The results are illustrated in Figures (LABEL:fig:brisbane),
(LABEL:fig:sherbrooke) and (LABEL:fig:cusco). For the devices ibm_brisbane,
ibm_sherbrooke and ibm_cusco, the results indicate that $8$, $4$ and $1$
heavy-hex unit cells can be verified as genuinely multipartite entangled when
QREM is applied, respectively.

Notably, the size of the largest $1$-D cluster state that can be verified as
GME is similar for all three devices. In contrast, there is a remarkable
difference in the number of heavy-hex unit cells that can be verified as GME,
e.g., $8$ for ibm_brisbane and $1$ for ibm_cusco. This shows that the ability
to generate multipartite entangled states is spread more evenly across the
device for ibm_brisbane. Therefore, for applications that require a larger
number of qubits one would expect that ibm_brisbane yields better results. In
general, evaluating multipartite entanglement witnesses for different types of
subgraphs can lead to more expressive results that can be interpreted in the
context of practical applications. For example, for simulations of a
Heisenberg model on a $1$-D lattice, the size of the largest $1$-D cluster
state verified as GME could be a suitable metric. When considering, e.g., a
Kagome lattice, the size of the largest heavy-hex subgraph verified as GME
could be a suitable metric.

(ii) The coloring-based witness (CBW)

$W^{c}(G^{\prime},G)=\frac{3}{2}\mathbb{I}-P(V_{1}^{\prime},G)-P(V_{2}^{\prime},G)$
(32)

where $\mathcal{V}^{\prime}=\\{V_{1}^{\prime},V_{2}^{\prime}\\}$ is the
partition of the set of vertices $V^{\prime}$ of $G^{\prime}$ induced by the
coloring of the graph. This witness has a higher white noise tolerance
$p_{\mathrm{tol}}>1/4$. However, as the operator (32) cannot be decomposed as
a sum of $m$-local observables for a fixed $m$ independent of the number of
qubits $n^{\prime}$, its expectation cannot be efficiently computed with the
QREM described in Section (IV-A3). This can be remedied by considering a
refinement of (32), that is, the operator $W(\widetilde{V}^{\prime},G)$ (17)
for a refinement $\widetilde{\mathcal{V}}^{\prime}$ of the partition
$\mathcal{V}^{\prime}$. For $1$-D cluster states, the refinement is chosen by
subdividing the state in groups of $5$ connected qubits and $\leq 5$ qubits in
the remaining group. This construction is ambiguous: depending on the order of
the qubits it yields two different refinements of the CBW. Therefore, we
choose the minimum of both evaluated witnesses. Compared to the SSW such a
refinement of the CBW still has a higher white noise tolerance, e.g.,
$p_{\mathrm{tol}}=1.54/n^{\prime}$ if $n^{\prime}$ is a multiple of $5$
(Appendix (VI-B)).

Here, the CBW is utilized as follows. We evaluate the CBW for the subgraphs
isomorphic to $\mathrm{Cl}_{n}$, for $n=2,\dotsc,30$, that minimize the SSW
without QREM. Furthermore, we evaluate the refinement of the CBW for the
subgraphs isomorphic to $\mathrm{Cl}_{n}$, for $n=2,\dotsc,30$, that minimize
the SSW with QREM.

The results are illustrated in Figure (LABEL:fig:cluster). For the devices
ibm_brisbane, ibm_sherbrooke and ibm_cusco, the results indicate that a
$9$-qubit, $11$-qubit and $9$-qubit $1$-D cluster state can be verified as
genuinely multipartite entangled without QREM, respectively. This is
comparable to the results for the SSW. Notably, the difference between the
expectations of the SSW and CBW increases with the number of qubits.

When QREM is applied, the results indicate that a $25$-qubit, $27$-qubit and
$27$-qubit $1$-D cluster state can be verified as genuinely multipartite
entangled for ibm_brisbane, ibm_sherbrooke and ibm_cusco, respectively.

For ibm_brisbane, the expectations of the SSW and the refinement of the CBW
are almost identical independent of the number of qubits, despite its higher
white noise tolerance. This indicates that the white noise tolerance is not a
sufficient metric to assess the robustness of an entanglement witness under
realistic experimental conditions. An avenue for future research could be the
investigation of the robustness of entanglement witnesses under more realistic
noise models. Also note that in some cases the expectation of the CBW is
larger than the expectation of the SSW. On first sight, this seems
contradictory to the fact that $W^{\mathrm{s}}(G^{\prime},G)\geq
W^{c}(G^{\prime},G)$, as the SSW is a refinement of the CBW. Yet, this
translates to a similar relation for the expectations, i.e.,
$\braket{W^{\mathrm{s}}(G^{\prime},G)}\geq\braket{W^{c}(G^{\prime},G)}$, only
if they are evaluated for probability distributions. With QREM we obtain
quasiprobability distributions that may include negative probabilities.

For ibm_sherbrooke and ibm_cusco, the expectations of the SSW and CBW are
comparable, yet, the expectations of the CBW are consistently lower. At this
point, it is not sufficiently investigated if this is a reliable result. This
difference could very well be attributed to the QREM method: for the
evaluation of witnesses we cap expectations of projectors $P(U)=P(U,G)$ at
$1$. For the SSW, the projectors are evaluated for each qubit separately. For
the refinement of the CBW, the projectors correspond to subsets of $2$ or $3$
qubits. Then, for example, if one considers a projector for a subset of $2$
qubits $P(\\{i,j\\})$ with $\braket{P(\\{i\\})}>1$ (before capping) and
$\braket{P(\\{j\\})}<1$ , it may occur that $\braket{P(\\{i,j\\})}\geq 1$.
After capping we have $\braket{P(\\{i\\})}=1$, $\braket{P(\\{j\\})}<1$ and
$\braket{P(\\{i,j\\})}=1$, so that in this case the CBW is lower than the SSW.
This phenomenon should be further investigated, e.g, by comparing the findings
for different readout error mitigation methods.

###  IV-C Benchmarking

In the following, the experiments are considered with regard to various
aspects of benchmarking [16] such as scalability, verifiability and
comparability.

####  IV-C1 Architecture-specific benchmarks

By performing benchmarks with graph states that correspond to the native qubit
topology of the QPU under test, computational overhead for classical
preprocessing with circuit optimization and qubit routing is reduced without
introducing additional SWAP gates. Furthermore, the execution of CZ gates can
be straightforwardly parallelized with respect to the qubit topology as is
shown in Figure (2). For $2$-colorable graphs, only two measurement settings -
independent of the number of qubits - are needed. Prominent examples apart
from IBM Quantum devices that have $2$-colorable coupling graphs are shown in
Figure (LABEL:fig:nisq_topologies). Note that especially for ion trap based
QPUs, all-to-all connectivity can be achieved in the NISQ era. With this,
every graph state can be natively implemented without introducing additional
SWAP gates.

The whole QPU can be benchmarked for A) bipartite entanglement so that regions
of connected qubits that are bipartite entangled are found. Ideally, all
benchmarked qubits are bipartite entangled such as shown in
(LABEL:fig:brisbane_qrem). With the same measurement results, the QPU can be
benchmarked for B) genuine multipartite entanglement so that regions of
connected qubits that are genuinely multipartite entangled are found. That is,
the graph state induced by such a subset of qubits can be prepared on the QPU
and verified as GME. Realistically, for NISQ devices, these subsets correspond
to smaller subgraphs such as shown for the heavy-hex unit cells in Figure
(LABEL:fig:brisbane_qrem) and the subgraphs isomorphic to $1$-D cluster states
in Figure (LABEL:fig:cluster). Based on our observations, we advise using the
stabilizer sum witness for performing the benchmarks as it can be evaluated
efficiently in a scalable manner also with readout error mitigation. The
coloring-based witness is more costly to evaluate (especially with readout
error mitigation) and has not shown a significant advantage in detecting GME.

With our method, the capability of generating entangled states based on
natively implementable graph states can be assessed and compared to the
results from different suitable architectures. If the comparison is done
between hardware platforms where one platform can only implement the graph
state by using SWAP operations, the comparison is not straightforward anymore.
If the results of said benchmarks would be worse on this platform, it is not
clear if this can only be explained with the CNOT gate overhead introduced by
the additional SWAP gates, or if the device would also perform worse
independent of this gate overhead. Only if such a device performs better
despite an additional SWAP overhead, the results can be interpreted
comparatively with other devices in the sense that it performs better in said
entanglement generation tasks. Hence, we advise using this as an architecture-
specific benchmark.

####  IV-C2 Architecture-independent benchmarks

Multipartite entanglement generation for 1-D cluster states can be benchmarked
on every hardware topology, hence generating the longest chain of qubits that
exhibits GME can be seen as an architecture-independent benchmark. The context
is important here: if entanglement for a $1$-D cluster state is verified as
part of a larger experiment that probes an overarching graph state, then these
results are not necessarily comparable to just verifying entanglement for such
a cluster state, mainly due to increased (non-local) noise from the additional
gate executions surrounding this subgraph.

##  V Outlook

In summary, we discussed a scalable method for benchmarking the entanglement
generation capabilities of NISQ devices using entanglement witnesses. This
method was tested on different IBM QPUs for analyzing bipartite entanglement
over all qubits and the ability to generate GME for $1$-D cluster states and
heavy-hex unit cells. In addition, we discussed the implications of using this
method as a benchmark. Finally, based on the results presented, we list
potential further approaches that can be pursued in future research endeavors.

  1. 1.

Benchmarking different QPUs: Since the developed method can be executed
efficiently on several NISQ devices, performing additional benchmarks on these
QPUs will provide insightful data. Based on this, comparisons between
different devices with the criteria discussed in Section (IV-C) can be drawn.

  2. 2.

Maintaining Entanglement: Measuring the duration for which verified bipartite
entanglement for a graph state or GME for a subet of qubits can be maintained
on a QPU under test is an interesting extension for the proposed benchmark.
For this, the experiments can be augmented by delayed measurements with an
incremental increase in delay time in order to obtain time-dependent data.
Similar experiments were performed based on different entanglement
verification criteria [4] and can be compared with the presented method.

  3. 3.

Parallel Circuit Execution: The verification of entanglement in specific
subgraphs could potentially be used for the evaluation of parallelization
possibilities on a QPU. The simultaneous execution of multiple spatially
separated quantum circuits on a single QPU (often called multi programming) is
an active field of research and several compilers that perform such parallel
scheduling tasks were proposed such as palloq [17], QuMC [18] and
QuCloud/QuCloud+ [19]. The analysis of regions on a QPU that show good
entanglement generation capabilities could be used for more efficient
scheduling implementations. A possible choice for such regions are given by
the heavy-hex unit cells that can be verified as GME in Section (IV).

## Acknowledgments

This work was funded by the Federal Ministry for Economic Affairs and Climate
Action (German: Bundesministerium für Wirtschaft und Klimaschutz) under the
project funding number 01MQ22007A. The authors are responsible for the content
of this publication.

##  VI Appendix

###  VI-A Evaluation of entanglement witnesses

Subsequently, we discuss the main aspects of implementing the evaluation of
entanglement witnesses and readout error mitigation (IV-A3).

In our setting, we consider a graph $G=(V,E)$ and a partition
$\mathcal{V}=\\{V_{1},\dotsc,V_{k}\\}$ of the set of vertices $V$
corresponding to a vertex coloring of $G$ with $k$ colors (here, $k=2$). The
measurement results for the prepared state $\rho$ with respect to the graph
state $\ket{G}$ are given by a set of probability distributions
$\Delta=\\{\Delta_{1},\dotsc,\Delta_{k}\\}$. Each probability distribution
$\Delta_{l}=\\{(x,p(x))\mid x\in\\{0,1\\}^{n},p(x)\neq 0\\}$ contains
measurement results in the measurement setting $\otimes_{i\in
V_{l}}X_{i}\otimes_{j\in V\setminus V_{l}}Z_{j}$. For readout error mitigation
we utilize the calibration matrices $(A^{(i)})_{i\in V}$. Then entanglement
witnesses are evaluated as follows.

####  VI-A1 Coloring-based witness

Algorithm (1) computes the coloring-based witness for a subgraph
$G^{\prime}=(U,E^{\prime})$. More specifically, let
$\mathcal{U}=\\{U_{1},\dotsc,U_{k}\\}$ be the partition of $U$ induced by the
coloring of the graph $G$, i.e., we have $U_{l}=V_{l}\cap U$. Then we compute
the expectation of the operator

$W(\mathcal{U},G)=\left(k-\frac{1}{2}\right)\mathbb{I}-\sum\limits_{l=1}^{k}P(U_{l},G).$
(33)

Note that each stabilizer projector $P(U_{l},G)$ acts non-trivially on all
qubits in $U_{l}$ and their neighbors $N(U_{l})$ in the graph $G$. Then the
QREM as described in Section (IV-A3) scales exponentially in the number of
these qubits. Hence, it can only be applied for small subsets of qubits. For
larger subsets of qubits, one can compute a (refinement of the) coloring-based
witness with QREM by subdividing the set of qubits $U$ into smaller subsets
and computing the witnesses for each subset. For example, for a subdivision
$U=A\cup B$ consider the partitions $\mathcal{A}=\\{U_{1}\cap
A,\dotsc,U_{l}\cap A\\}$ and $\mathcal{B}=\\{U_{1}\cap B,\dotsc,U_{l}\cap
B\\}$ of the sets $A$ and $B$, respectively. Then the partition
$\mathcal{A}\cup\mathcal{B}$ is a refinement of the partition $\mathcal{U}$ of
the set $U=A\cup B$. With equations (20) and (26), we find

$W(\mathcal{U},G)\leq
W(\mathcal{A}\cup\mathcal{B},G)=\mathbb{I}/2+W(\mathcal{A},G)+W(\mathcal{B},G).$
(34)

The witnesses $W(\mathcal{A},G)$ and $W(\mathcal{B},G)$ act non-trivially on a
smaller number of qubits.

Algorithm 1 $\mathrm{witness}$

Input: A graph $G=(V,E)$, a partition $\mathcal{V}$ of $V$, distributions
$\Delta_{\mathcal{V}}$, a subset of qubits $U\subset V$, calibration matrices
$(A^{(i)})_{i\in V}$, and a Boolean $qrem$.

Output: Expectation of witness $W=\braket{W(\mathcal{U},G)}$.

$\Delta=\Delta_{\mathcal{V}}$

$\Sigma=\\{\\}$ $\triangleright$ Stabilizers

for $j$ in $U$ do

$\Sigma[j]=S_{j}$

$\mathcal{U}=\\{\\}$ $\triangleright$ Partition
$\mathcal{U}=\\{U_{1},\dotsc,U_{k}\\}$

for $l=1$ to $k$ do

$\mathcal{U}[l]=V_{l}\cap U$

if $qrem$ then $\triangleright$ Readout error mitigation

$\Delta,\Sigma={\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathrm{qrem}}(G,\Delta_{\mathcal{V}},\Sigma,(A^{(i)})_{i\in
V},\mathcal{U})$

$W=k-\frac{1}{2}$

for $l=1$ to $k$ do

if $\mathcal{U}[l]\neq\emptyset$ then

$P=0$ $\triangleright$ Evaluate projector $P(U_{l})$

for $(x,p(x))$ in $\Delta[l]$ do

$temp=1$ $\triangleright$ Evaluate $\braket{x}{P(U_{l})}{x}$

for $i$ in $\mathcal{U}[l]$ do

$temp=temp\cdot\dfrac{1+\braket{x}{\Sigma[i]}{x}}{2}$

$P=P+p(x)\cdot temp$

$W=W-\min(P,1)$ $\triangleright$ Cap projector at $1$

else

$W=W-1$ $\triangleright$ $P(\emptyset)=1$

return: $W$

This algorithm computes the expectation of the coloring-based witness (33) for
a subset $U$ of qubits, and the expectation of the stabilizer $S_{i}$ if
$U=\\{i\\}$, for $i\in V$. For this, we compute the expectation of the
stabilizer projectors for each color. The expectation of the projector
$P(U_{l})=P(U_{l},G)$ is calculated from the distribution $\Delta_{l}$ of
measurement outcomes in measurement setting $\oplus_{i\in V_{l}}\oplus_{j\in
V\setminus V_{l}}Z_{j}$. This corresponds to a change of basis such that in
this basis the stabilizers $S_{i}$, for $i\in V_{l}$, are a product of
$\mathbb{I}$ and Pauli-$Z$ operators. Thus, the projector $P(U_{l})$ is a
product of diagonal operators. Therefore, calculating its expectation on a
computational basis state $\ket{x}$ is accomplished by taking the product of
the expectations of the diagonal operators $(\mathbb{I}+S_{i})/2$.

####  VI-A2 Stabilizer sum witness

If the set $U$ consists of exactly one qubit, i.e., $U=\\{i\\}$, for $i\in V$,
equation (33) simplifies to

$W(\mathcal{U},G)=\frac{1}{2}-P(\\{i\\},G)=-\frac{S_{i}}{2}.$ (35)

Here, we use that $P(\emptyset,G)=1$. Thus, we can apply Algorithm (1) to
compute the expectations of all stabilizers $S_{i}$, for $i\in V$. In our
experiments, each such stabilizer acts non-trivially only on at most $4$
qubits since the maximum vertex degree of a heavy-hex graph is $3$. Therefore,
readout error mitigation as described in Section (IV-A3) can be utilized. The
(mitigated) expectations of the stabilizers can further be used to calculate
stabilizer sum witnesses for subgraphs.

####  VI-A3 QREM

The quantum readout error mitigation described in Section (IV-A3) is
implemented as shown in Algorithm (2). For this, we assume that the following
functions are given:

  * •

$\mathrm{sort}$: Input: set of integers. Output: sorted list of integers.

  * •

$\mathrm{reduce}$: Input: stabilizer, (sorted) list of positions. Output:
reduced stabilizers with respect to the given positions. For example, for a
stabilizer $Z_{7}X_{8}Z_{9}$ and positions $\pi=(7,8,9)$, the reduced
stabilizer is $Z_{0}X_{1}Z_{2}$.

  * •

$\mathrm{marginal}$: Input: distribution, (sorted) list of positions. Output:
marginal distributions with respect to the given positions.

  * •

$\mathrm{mitigate}$: Input: distribution, list of calibration matrices.
Output: mitigated distribution.

Algorithm 2 $\mathrm{qrem}$

Input: A graph $G$, distributions $\Delta_{\mathcal{V}}$, stabilizers
$\Sigma$, calibration matrices $(A^{(i)})_{i\in V}$, and a partition
$\mathcal{U}$ of $U$.

Output: Mitigated distributions $\Delta_{\mathcal{U}}$ and reduced stabilizers
$\Sigma_{\mathcal{U}}$.

$\Delta_{\mathcal{U}}=\\{\\}$

$\Sigma_{\mathcal{U}}=\\{\\}$

for $l=1$ to $k$ do

if $\mathcal{U}[l]\neq\emptyset$ then

$\pi=\mathrm{sort}(U_{l}\cup N(U_{l}))$

for $i$ in $U_{l}$ do $\triangleright$ Reduced stabilizers

$\Sigma_{\mathcal{U}}[i]=\mathrm{reduce}(\Sigma[i],\pi)$

$\Delta_{\mathcal{U}}[l]=\mathrm{marginal}(\Delta_{\mathcal{V}}[l],\pi)$

$\Delta_{\mathcal{U}}[l]=\mathrm{mitigate}(\Delta_{\mathcal{U}}[l],(A^{(\pi_{1})},\dotsc,A^{(\pi_{k})}))$

return: $\Delta_{\mathcal{U}}$, $\Sigma_{\mathcal{U}}$

This algorithm computes the reduced stabilizers and the mitigated (marginal)
distribution with respect to a subset $U$ of qubits.

###  VI-B White noise tolerance

From the definition of the white noise tolerance for a graph state $\ket{G}$
and a witness $W$ we find

$p_{\mathrm{tol}}=\left(1-\frac{\mathrm{tr}(W)}{2^{n}\mathrm{tr}(W\ket{G}\bra{G})}\right)^{-1}.$
(36)

For a witness $W$ of the form (5) we have $\mathrm{tr}(W\ket{G}\bra{G})=-1/2$.
It remains to calculate

$\mathrm{tr}(W)=2^{n}\left(k-\frac{1}{2}\right)-2^{n}\sum\limits_{l=1}^{k}2^{-n_{l}}$
(37)

where $n_{l}=|V_{l}|$ is the number of qubits in each vertex set of the
partition $\mathcal{V}$, and we use that
$\mathrm{tr}(P(V_{l},G))=2^{n-n_{l}}$. Then we obtain

$p_{\mathrm{tol}}=\frac{1}{2}\left(k-\sum\limits_{l=1}^{k}2^{-n_{l}}\right)^{-1}>\frac{1}{2k}.$
(38)

In particular, for the stabilizer sum witness, i.e.,
$\mathcal{V}=\\{\\{i\\}\\}_{i\in V}$, we find $p_{\mathrm{tol}}=1/n$.

In Section (IV-B), we consider a refinement of the coloring-based witness for
$1$-D cluster states. This refinement is obtained by subdividing a state in
groups of $5$ connected qubits and $\leq 5$ qubits in the remaining group.
This corresponds to a partition $\mathcal{V}=\\{V_{0},\dotsc,V_{\lceil
n/5\rceil-1}\\}$, where $V_{2i},V_{2i+1}$, for $i=0,\dotsc,\lceil
n/5\rceil-1$, are the sets of qubits of the $i$-th group for each color. Then
we have $k=2\lceil n/5\rceil$. If $n$ is a multiple of $5$, we can assume that
$|V_{2i}|=2$ and $|V_{2i+1}|=3$. In this case, we have

$p_{\mathrm{tol}}=\frac{1}{2}\left(\frac{2n}{5}-\frac{n}{5}\left(\frac{1}{4}+\frac{1}{8}\right)\right)^{-1}=\frac{20}{13n}\approx
1.54n^{-1}.$ (39)

The values of $c(n)=n\cdot p_{\mathrm{tol}}$, for $n=1,\dotsc,24$, are shown
in Table (I).

$n$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$
---|---|---|---|---|---|---|---|---
$c(n)$ | $1.0$ | $1.0$ | $1.2$ | $1.33$ | $1.54$ | $1.41$ | $1.33$ | $1.39$
$n$ | $9$ | $10$ | $11$ | $12$ | $13$ | $14$ | $15$ | $16$
$c(n)$ | $1.44$ | $1.54$ | $1.47$ | $1.41$ | $1.44$ | $1.47$ | $1.54$ | $1.49$
$n$ | $17$ | $18$ | $19$ | $20$ | $21$ | $22$ | $23$ | $24$
$c(n)$ | $1.45$ | $1.47$ | $1.49$ | $1.54$ | $1.5$ | $1.47$ | $1.48$ | $1.5$
$n$ | $25$ | $26$ | $27$ | $28$ | $29$ | $30$ |  |
$c(n)$ | $1.54$ | $1.51$ | $1.48$ | $1.49$ | $1.51$ | $1.54$ |  |
TABLE I: The factors $c(n)=n\cdot p_{\mathrm{tol}}$, for $n=1,\dotsc 30$.

###  VI-C Properties of projectors

For Hermitian operators $A,B$ on a finite-dimensional Hilbert space
$\mathcal{H}$, we use the notation $A\geq B$ indicating that $(A-B)$ is
positive semidefinite. The following result was shown in [13] (Proof of
Proposition 2).

######  Lemma VI.1.

Let $P_{1},\dotsc,P_{k}$ be commuting Hermitian operators on a finite-
dimensional Hilbert space $\mathcal{H}$ with all eigenvalues in $\\{0,1\\}$.
Then we have

$\prod\limits_{l=1}^{k}P_{l}\geq\sum\limits_{l=1}^{k}P_{l}-(k-1)\mathbb{I}.$
(40)

###  VI-D A necessary condition for separability

We prove a necessary condition for separability that can be used to construct
entanglement witnesses for bipartite entanglement.

######  Remark VI.2.

We write $\sigma_{i}$ for $i=0,1,2,3$, where $\sigma_{0}=\mathbb{I}$ is the
identity, and $\sigma_{1}=\sigma_{x}$, $\sigma_{2}=\sigma_{y}$,
$\sigma_{3}=\sigma_{z}$ are the three Pauli matrices. Consider the Hilbert
space $\mathcal{H}=(\mathbb{C}^{2})^{\otimes n}$. We write
$\mathbf{i}=(i_{1},\dotsc,i_{n})$ for a multi-index. The set of matrices
$E_{\mathbf{i}}=\sigma_{i_{1}}\otimes\dotsb\otimes\sigma_{i_{n}}$ is
orthogonal with respect to the Hilbert-Schmidt inner product, that is,
$(E_{\mathbf{i}},E_{\mathbf{j}})=\mathrm{tr}(E_{\mathbf{i}}^{{\dagger}}E_{\mathbf{j}})=2^{n}\delta_{\mathbf{i}\mathbf{j}}$,
and forms a basis of the real vector space of Hermitian matrices in
$\mathcal{H}$. Then any density operator may be represented as

$\rho=\frac{1}{2^{n}}\left(\mathbb{I}+\sum\limits_{\mathbf{i}\neq
0}\lambda_{\mathbf{i}}\sigma_{i_{1}}\otimes\dotsb\otimes\sigma_{i_{d}}\right)$
(41)

where $\lambda_{\mathbf{i}}$ are real numbers. Equation (41) does not include
the non-negativity condition.

######  Proposition VI.3.

Let $S,S^{\prime}$ be Pauli product operators of the form:

$S=\prod\limits_{m\in M}\sigma(m),\qquad S^{\prime}=\prod\limits_{m\in
M}\sigma^{\prime}(m)$ (42)

where
$\sigma(m),\sigma^{\prime}(m)\in\\{\mathbb{I},\sigma_{x},\sigma_{y},\sigma_{z}\\}$
are Pauli operators acting on qubit $m$. Let $A,B$ be a partition of M.
Suppose that the state $\rho\in(\mathbb{C}^{2})^{\otimes|M|}$ is separable
with respect to $A,B$, that is,
$\rho=\sum_{k}p_{k}\rho_{k}^{A}\otimes\rho_{k}^{B}$. Consider the Pauli
product operators

$S_{K}=\prod\limits_{m\in M\cap K}\sigma(m),\quad
S_{K}^{\prime}=\prod\limits_{m\in M\cap K}\sigma^{\prime}(m),$ (43)

for $K\in\\{A,B\\}$. The operators $S_{K}$ and $S_{K}^{\prime}$ are obtained
from $S$ and $S^{\prime}$, respectively, by replacing all Pauli operators
acting on qubits in $M\setminus K$ to identities. If the anti-commutation
relations

$\\{S_{K},S_{K}^{\prime}\\}=0,\quad\text{for }K\in\\{A,B\\},$ (44)

are satisfied, then we have

$\langle S\rangle+\langle S^{\prime}\rangle\leq 1.$ (45)

###### Proof.

We consider the case $\rho=\rho^{A}\otimes\rho^{B}$. Then we have

$\langle S\rangle+\langle S^{\prime}\rangle=\langle S_{A}\rangle\langle
S_{B}\rangle+\langle S_{A}^{\prime}\rangle\langle S_{B}^{\prime}\rangle.$ (46)

Define the Hermitian operators

$O_{K}(\theta)=\cos(\theta)S_{K}+\sin(\theta)S_{K}^{\prime},$ (47)

for $K\in\\{A,B\\}$. The operators $O_{K}(\theta)$ have all eigenvalues in
$\\{-1,1\\}$: we have

$\displaystyle\begin{split}(O_{K}(\theta))^{2}=&(\cos(\theta))^{2}S_{K}^{2}+\cos(\theta)\sin(\theta)(S_{K}S_{K}^{\prime}+S_{K}^{\prime}S_{K})\\\
&+(\sin(\theta))^{2}S_{K}^{\prime 2}=\mathbb{I}.\end{split}$ (48)

The Pauli products $S_{K},S_{K}^{\prime}$ are of the form
$E_{\mathbf{i}}=\sigma_{i_{1}}\otimes\dotsb\otimes\sigma_{i_{n}}$, for some
indexes $\mathbf{i}=\mathbf{i}_{K},\mathbf{i}_{K}^{\prime}$. Then with (41) we
may write

$\rho^{K}=\frac{1}{2^{|K|}}\left(\mathbb{I}+r_{K}O_{K}(\theta_{K})+\smashoperator[]{\sum_{\mathbf{i}\neq
0,\mathbf{i}_{K},\mathbf{i}_{K}^{\prime}}^{}}\lambda_{\mathbf{i}}^{K}\sigma_{i_{0}}\otimes\dotsb\otimes\sigma_{i_{|K|}}\right),$
(49)

for real numbers $\lambda_{\mathbf{i}}^{K}$ and $r_{K}\geq 0$,
$\theta_{K}\in[0,2\pi)$. Then with (46) we find

$\displaystyle\begin{split}\langle S\rangle+\langle
S^{\prime}\rangle&=r_{A}r_{B}(\cos(\theta_{A})\cos(\theta_{B})+\sin(\theta_{A})\sin(\theta_{B}))\\\
&=r_{A}r_{B}\cos(\theta_{A}-\theta_{B})\leq r_{A}r_{B}.\end{split}$ (50)

In the following we show that $r_{K}\leq 1$ for $K\in\\{A,B\\}$: on the one
hand we have
$\mathrm{tr}(\rho^{K}O_{K}(\theta_{K}))=r_{K}(\cos^{2}(\theta_{K})+\sin^{2}(\theta_{K}))=r_{K}$.
On the other hand the Hermitian operator $O_{K}(\theta_{K})$ has a spectral
decomposition $\sum_{l}\lambda_{l}\ket{v_{l}}\bra{v_{l}}$, where $\lambda_{l}$
are the real eigenvalues of $O_{K}(\theta_{K})$ and the vectors $\ket{v_{l}}$
form an orthonormal basis. Then we have:

$\mathrm{tr}(\rho^{K}O_{K}(\theta_{K}))=\sum\limits_{l}\lambda_{l}\mathrm{tr}(\rho^{K}\ket{v_{l}}\bra{v_{l}})\leq\max\limits_{l}\lambda_{l}=1.$
(51)

Here, we used that the density operator $\rho^{K}$ is positive and has trace
equal to one. This finishes the proof for the case
$\rho=\rho^{A}\otimes\rho^{B}$. Then the claim follows from the linearity of
expectations. ∎

As a special case, we obtain the following necessary condition for
separability in the context of graph states. This is a generalization of a
similar condition for full separability [10, 8].

######  Proposition VI.4.

Let $G=(V,E)$ be a graph and $(i,j)\in E$. Consider the stabilizer operators

$S_{i}=\sigma_{x}^{i}\prod\limits_{l\in N_{i}}\sigma_{z}^{l},\qquad
S_{j}=\sigma_{x}^{j}\prod\limits_{l\in N_{j}}\sigma_{z}^{l}.$ (52)

Let $A,B$ be a partition of $V$ with $i\in A$ and $j\in B$. Suppose that the
state $\rho\in(\mathbb{C}^{2})^{\otimes n}$ is separable with respect to
$A,B$, that is, $\rho=\sum_{k}p_{k}\rho_{k}^{A}\otimes\rho_{k}^{B}$. Then we
have

$\langle S_{i}\rangle+\langle S_{j}\rangle\leq 1.$ (53)

###### Proof.

With $S=S_{i}$ and $S^{\prime}=S_{j}$ we find that

$\displaystyle S_{A}$ $\displaystyle=\sigma_{x}^{i}\prod\limits_{l\in
N_{i}\cap A}\sigma_{z}^{l},$ $\displaystyle S_{A}^{\prime}$
$\displaystyle=\sigma_{z}^{i}\prod\limits_{l\in N_{j}\setminus\\{i\\}\cap
A}\sigma_{z}^{l},$ (54) $\displaystyle S_{B}$
$\displaystyle=\sigma_{z}^{j}\prod\limits_{l\in N_{i}\setminus\\{j\\}\cap
B}\sigma_{z}^{l},$ $\displaystyle S_{B}^{\prime}$
$\displaystyle=\sigma_{x}^{j}\prod\limits_{l\in N_{j}\cap B}\sigma_{z}^{l}.$
(55)

Clearly, the anti-commutation relations (44) are satisfied. Then the claim
follows from Proposition (VI.3). ∎

## References

  * [1] G. J. Mooney, G. A. White, C. D. Hill _et al._ , “Generation and verification of 27-qubit Greenberger-Horne-Zeilinger states in a superconducting quantum computer,” _Journal of Physics Communications_ , vol. 5, no. 9, p. 095004, 2021.
  * [2] ——, “Whole-Device Entanglement in a 65-Qubit Superconducting Quantum Computer,” _Advanced Quantum Technologies_ , vol. 4, no. 10, p. 2100061, 2021.
  * [3] S. Cao, B. Wu, F. Chen _et al._ , “Generation of genuine entanglement up to 51 superconducting qubits,” _Nature_ , vol. 619, pp. 738–742, 2023.
  * [4] J. F. Kam, H. Kang, C. D. Hill _et al._ , “Generation and preservation of large entangled states on physical quantum devices,” _arXiv preprint arXiv:2312.15170_ , 2023.
  * [5] K. E. Hamilton, N. Laanait, A. Francis _et al._ , “An entanglement-based volumetric benchmark for near-term quantum hardware,” _arXiv preprint arXiv:2209.00678_ , 2022.
  * [6] R. Blume-Kohout and K. C. Young, “A volumetric framework for quantum computer benchmarks,” _Quantum_ , vol. 4, p. 362, 2020.
  * [7] R. Raussendorf and H. J. Briegel, “A One-Way Quantum Computer,” _Physcal Review Letters_ , vol. 86, pp. 5188–5191, 2001\.
  * [8] M. Hein, W. Dür, J. Eisert _et al._ , “Entanglement in graph states and its applications,” _arXiv preprint quant-ph/0602096_ , 2006.
  * [9] P. Gokhale, E. R. Anschuetz, C. Campbell _et al._ , “SupercheQ: Quantum Advantage for Distributed Databases,” 2022.
  * [10] G. Tóth and O. Gühne, “Detecting genuine multipartite entanglement with two local measurements,” _Physical Review Letters_ , vol. 94, p. 060501, 2005.
  * [11] M. Bourennane, M. Eibl, C. Kurtsiefer _et al._ , “Experimental Detection of Multipartite Entanglement using Witness Operators,” _Physical Review Letters_ , vol. 92, p. 087902, 2004.
  * [12] B. Jungnitsch, T. Moroder, and O. Gühne, “Entanglement witnesses for graph states: General theory and examples,” _Physical Review A_ , vol. 84, p. 032310, 2011.
  * [13] Y. Zhou, Q. Zhao, X. Yuan _et al._ , “Detecting multipartite entanglement structure with minimal resources,” _npj Quantum Information_ , vol. 5, no. 1, p. 83, 2019.
  * [14] S. Bravyi, S. Sheldon, A. Kandala _et al._ , “Mitigating measurement errors in multiqubit experiments,” _Physical Review A_ , vol. 103, p. 042605, 2021.
  * [15] P. D. Nation, H. Kang, N. Sundaresan _et al._ , “Scalable mitigation of measurement errors on quantum computers,” _PRX Quantum_ , vol. 2, p. 040326, 2021.
  * [16] C. K.-U. Becker, N. Tcholtchev, I.-D. Gheorghe-Pop _et al._ , “Towards a Quantum Benchmark Suite with Standardized KPIs,” in _2022 IEEE 19th International Conference on Software Architecture Companion (ICSA-C)_ , 2022, pp. 160–163.
  * [17] Y. Ohkura, T. Satoh, and R. Van Meter, “Simultaneous Execution of Quantum Circuits on Current and Near-Future NISQ Systems,” _IEEE Transactions on Quantum Engineering_ , vol. 3, pp. 1–10, 2022.
  * [18] S. Niu and A. Todri-Sanial, “Enabling Multi-programming Mechanism for Quantum Computing in the NISQ Era,” _Quantum_ , vol. 7, p. 925, 2023.
  * [19] L. Liu and X. Dou, “QuCloud+: A Holistic Qubit Mapping Scheme for Single/Multi-programming on 2D/3D NISQ Quantum Computers,” _arXiv preprint arXiv:2207.14483_ , 2022.