# Scalability enhancement of quantum computing under limited connectivity
through distributed quantum computing

Shao-Hua Hu  Department of Physics, Tamkang University, New Taipei 25137,
Taiwan, ROC  George Biswas  Department of Physics, Tamkang University, New
Taipei 25137, Taiwan, ROC  Center for Advanced Quantum Computing, Tamkang
University, New Taipei 25137, Taiwan, ROC  Jun-Yi Wu<EMAIL_ADDRESS>Department of Physics, Tamkang University, New Taipei 25137, Taiwan, ROC
Center for Advanced Quantum Computing, Tamkang University, New Taipei 25137,
Taiwan, ROC  Physics Division, National Center for Theoretical Sciences,
Taipei 10617, Taiwan, ROC

###### Abstract

We employ quantum-volume random-circuit sampling to benchmark the two-QPU
entanglement-assisted distributed quantum computing (DQC), and compare it with
single-QPU quantum computing. We first specify a single-qubit depolarizing
noise model in the random circuit. Based on this error model, we show the one-
to-one correspondence of three figures of merits, namely average gate
fidelity, heavy output probability, and linear cross-entropy. We derive an
analytical approximation of the average gate fidelity under the specified
noise model, which is shown to align with numerical simulations. The
approximation is calculated based on an allocation matrix obtained from the
extended connectivity graph of a DQC device. In numerical simulation, we
unveil the scalability enhancement in DQC for the QPUs with limited
connectivity. Furthermore, we provide a simple formula to estimate the average
gate fidelity, which also provides us with a heuristic method to evaluate the
scalability enhancement in DQC, and a guide to optimize the structure of a DQC
configuration.

Keywords

##  I Introduction

In noisy intermediate-scale quantum (NISQ) computing, the imperfection on
quantum processing units (QPUs) can not yet be corrected. The defects on a
single QPU are much more difficult to suppress as the number of qubits
increases, which limits the scalability of quantum computers. A solution for
scaling up quantum computers is distributed quantum computing (DQC) [1, 2], in
which one implements global quantum circuits over multiple high-quality small-
size QPUs.

The ultimate goal of DQC is to scale up quantum computing by connecting
multiple QPUs. Explicitly, one aims to implement a global unitary assisted by
classical and quantum communication across different QPUs, rather than direct
nonlocal gates. In general, DQC can be classified into two types according to
the principle of connections between two QPUs. The first type of DQC employs
only local operations and classical communication (LOCC), which is called
circuit knitting [3, 4, 5, 6, 7]. The second type of DQC is called
entanglement-assisted DQC, which employs quantum communication to share
entanglement between QPUs and implement entanglement-assisted LOCC, such as
state teleportation [8] or telegating [9, 10, 11, 12, 13, 14, 15, 16]. In this
paper, we consider the entanglement-assisted DQC, since the circuit knitting,
has the problem of the computational overhead.

To verify the enhancement of computation power in DQC, one needs to benchmark
and compare the quantum computing power of multi-QPU DQC devices and single-
QPU devices. The corresponding figures of merits include average gate fidelity
(AGF)[17], heavy output probability (HOP)[18], and linear cross-entropy
(LXE)[19]. The quality of the quantum computing on a quantum processor can be
then quantified by averaging these figures of merits over a random sampling of
quantum circuits. In [18], a randomized benchmarking based on HOP is
introduced to quantify the maximum scale of a subcollection of qubits of a QPU
that allows quantum advantage, which is called the quantum volume (QV) of a
QPU. The original approach of QV benchmarking is a heavy output generation
test [20] based on QV random circuits.

In this paper, we adopt different figures of merits (AGF, HOP, and LXE) to the
QV random-circuit sampling, and extend it to two-QPU DQC. The extended
benchmarking allows us to reveal the scalability enhancement of quantum
computing in DQC. To verify scalability enhancement in DQC, we simulate and
compare the QV benchmarking for both single-QPU quantum computing and two-QPU
DQC. By definition, the average gate fidelity quantifies the faithfulness of
the quantum operations implemented by a quantum device, while the heavy output
probability and linear cross entropy only indicate the closeness of the
measurement outputs and the ideal ones. However, since the measurement
complexity of average gate fidelity increases exponentially with the system
size [21], it is even experimentally impossible to evaluate average gate
fidelity on a quantum computer. In contrast, the evaluation of heavy output
probability and linear cross-entropy can be experimentally implemented with
random circuit samplings.

In this paper, we show the one-to-one correspondence among average AGF
$\bar{F}$, HOP $\bar{H}$, and LXE $\bar{\chi}$ in the QV random-circuit
benchmarking under an approximated error model

$\bar{F}\;\;\underset{\text{QV
random}}{\longleftrightarrow}\;\;\bar{H}\;\;\underset{\text{QV
random}}{\longleftrightarrow}\;\;\bar{\chi}.$ (1)

This result allows us to estimate average gate fidelity from heavy output
probability or linear cross-entropy in numerical simulation, and vice versa
calculate heavy output probability and linear cross-entropy via average gate
fidelity. Employing average AGF $\bar{F}$ as the figure of merit, we derive an
approximated formula of $\bar{F}$ for the QV random-circuit benchmarking of
multi-QPU DQC devices under arbitrary connectivity described by extended
connectivity graphs. The theory of error model approximation is supported by
numerical simulations on qiskit. Our numerical simulations also show evidence
of better average AGF of two-QPU DQC devices surpassing single-QPU devices

$\bar{F}_{DQC}\geq\bar{F}_{single}.$ (2)

It therefore shows the scalability enhancement of DQC under limited qubit
connectivity in QPUs.

The paper is constructed as follows. In Section II, we review the concept of
entanglement-assisted DQC, random-circuit benchmarking, and qubit
connectivity. In Section III, we model the noises in random-circuit sampling
by an approximation with single-qubit depolarizing channels, show the one-to-
one correspondence among AGF, HOP, and LXE, and derive an analytical formula
for average AGF. In Section IV, we implement numerical simulations of the QV
random-circuit benchmarking and unveil the evidence for the scalability
enhancement of two-QPU DQC with limited connectivity. In the end, we discuss
our results in Section V and conclude the paper in Section VI.

##  II Preliminary

###  II.1 Entanglement-assisted DQC

Figure 1: Implementation of a global unitary $U$ over two QPUs $Q_{A}$ and
$Q_{B}$ through local unitaries $U_{A}$ and $U_{B}$, with the help of pre-
shared entangled pairs $e_{AB}$ (wiggly line) and classical communications
(double line).

In two-QPU entanglement-assisted DQC, one aims to execute a large quantum
circuit over two small-size QPUs through local operations assisted by
classical communication and pre-shared entangled pairs, i.e. entanglement-
assisted LOCC, as shown in Figure 1.

A promising tool for achieving this is Quantum state teleportation. Quantum
state teleportation is a special quantum operation that transfers a quantum
state from one location to another using an entangled pair (also known as a
Bell state) and local operations with classical communication (LOCC) [22].
Instead of directly sending the quantum state, it exploits entanglement and
classical communication to transfer the state. Expanding on this concept,
there’s a similar idea called gate teleportation or telegate [9, 13]. This
proposes that the CNOT gate, a crucial quantum gate, can be executed locally
using an entangled pair and LOCC. Specifically, a protocol known as the EJPP
protocol (named after its creators) was introduced for this purpose [9].

The EJPP protocol’s circuit, depicted in Figure 2, illustrates how this
telegating protocol works in practice. It enables the execution of CNOT gates
across different QPUs through the clever use of entanglement and classical
communication, allowing for the distributed execution of quantum circuits.

Figure 2: Implementation of a non-local CNOT gate using the EJPP protocol. The
two central qubits are auxiliary qubits that share a maximally entangled pair
represented by a wiggly line. Here we use the Bell state
$|\Phi^{+}\rangle\equiv\frac{1}{\sqrt{2}}(|00\rangle+|11\rangle)$.

It is known that the CNOT gate is the only two-qubit gate in the universal
set. Therefore, with the EJPP protocol, universal quantum computing can be
implemented across multiple QPUs.

In our study, we aim to enhance quantum computer capabilities through DQC. We
assume local QPUs have unlimited access to entangled pairs, although creating
them remains challenging. Therefore, while our focus is on maximizing
computational power, we also recognize the importance of minimizing entangled
pair usage in circuit implementation, a topic deserving its discussion [15].

###  II.2 Benchmarking via random-circuit sampling

To validate quantum computational power, one needs a systematic benchmarking
method to verify the computation on a quantum computing device. One such
benchmarking method relies on random circuit sampling, demonstrating quantum
advantage by comparing outcome distributions between theoretical predictions
and experimental results [20]. Ideally, one would sample circuits randomly
over the Haar measure [23], representing a unitary invariant uniform
distribution of unitary transformation. In a practical randomized benchmarking
protocol, we need random circuits that are approximately random unitaries
under Haar measure. Prominent examples include quantum volume (QV)
benchmarking[18] and cross-entropy (LXE) benchmarking[19].

Figure 3: An N-qubit random circuit in quantum volume benchmarking. Each layer
$u_{i}$ consists of a random permutation gate $\pi$ and several $2$-qubit Haar
random $SU(4)$ gates.

In the QV benchmarking, which is illustrated in Fig. 3, an $N$-qubit
benchmarking circuit is constituted by $N$ layers of gates. Each layer
comprises an random permutation gate $\pi$ and random $2$-qubit $SU(4)$ gates
sampled under the Haar measure. To avoid unnecessary noises introduced by
permutation gates, one can randomly reposition the $SU(4)$ gates instead of
random permutation gates.

For a $U$ generated from a randomly sampled circuit,

$U=u_{N}.u_{N-1}\cdots u_{2}.u_{1},$ (3)

one calculates the theoretical distribution of outputs
$q_{U}(x)\equiv|\braket{x}{U}{0}|^{2}$ on classical computers, and labels an
output $x$ as heavy, if its probability $p_{U}(x)$ is greater than the median
of the distribution. We denote the set of heavy outputs as $X_{U}$, which
contains $2^{N-1}$ elements. The HOP $H_{U}$ is then defined as the summation
of the probabilities of all heavy outputs:

$\displaystyle H_{U}\equiv\sum_{x\in X_{U}}q_{U}(x),\;X_{U}\equiv\left\\{x\
\text{is heavy output of}\ U\right\\}.$ (4)

The average HOP converges to $\frac{1+\ln{2}}{2}$ ($\approx 0.85$), for the
ideal devices and it is $0.5$ for the completely depolarized devices.

In the linear cross-entropy benchmarking, we calculate the linear cross-
entropy $\chi_{U}$ between the ideal probability distribution $q_{U}(x)$ and
the tested probability distribution $p_{U}(x)$ measured from the testing
device, which is defined as follows,

$\displaystyle\chi_{U}\equiv 2^{N}\sum_{x\in\\{0,1\\}^{N}}p_{U}(x)q_{U}(x)-1.$
(5)

Besides HOP and LXE, the average gate fidelity (AGF) $F(U,\Lambda)$ [17]
between the target unitary $U$ and its implementation $\Lambda_{U}$ on a real
device is another figure of merit for quantifying the performance of QPUs,
which is defined as follows

$F(U,\Lambda_{U})=\int_{\Psi}d\psi\braket{\psi}{U^{\dagger}\,\Lambda_{U}(\ket{\psi}\bra{\psi})\,U}{\psi},$
(6)

where $\Psi$ is the set of pure states under the Haar measure. The
vectorization representation of a quantum state [24] is convenient for the
calculation of AFG. In the vectorization representation, one defines a
vectorized state of a density matrix $\rho$ as follows,

$\displaystyle|\rho\rangle\rangle\equiv(\rho\otimes\mathbb{I})\sum_{i}|i\rangle\otimes|i\rangle.$
(7)

For a pure state $\rho=|\psi\rangle\langle\psi|$, its vectorization is
$|\psi\rangle\rangle\equiv|\psi\rangle\otimes|\psi\rangle^{*}$. In such
vectorization presentation, a unitary operator becomes

$\widehat{U}\equiv U\otimes U^{*}.$ (8)

With such vectorization the AGF of $U$ is

$\displaystyle
F(U,\Lambda_{U})\equiv\int_{\Psi}d\psi\;\;\langle\langle\psi|\;\widehat{U}^{\dagger}\widetilde{\Lambda}_{U}\;|\psi\rangle\rangle,$
(9)

where $\widetilde{\Lambda}_{U}$ is the noise quantum channel of the
implementation of the target unitary $U$. Note that, in this paper, we employ
the “hat” and “tilde” symbols to indicate the vectorization representation of
a unitary and a quantum channel, respectively. In randomized benchmarking, the
circuits are sampled from a set of random circuits $\mathbb{U}_{RC}$, one
therefore should further average the AGF $F(U,\Lambda_{U})$ over all the
possible circuits as follows,

$\displaystyle\bar{F}\equiv\int_{\mathbb{U}_{RC}}dUF(U,\Lambda_{U}).$ (10)

We will employ these three figures of merit to evaluate the performance of DQC
in the QV random-circuit-sampling test.

###  II.3 Connectivity of QPUs

The connectivity constraint is a common limitation for a QPU, which prevents
direct implementation of a two-qubit gate on arbitrary pairs of qubit due to
lack of direct physical coupling. The connectivity of a QPU can be represented
by a graph with its edge indicating allowed two-qubit couplings. For a DQC
device, which is composed of multiple QPUs, one can establish quantum channels
sharing entanglement among qubits across the QPUs. The topology of quantum
channels in DQC device can be also represented as a graph, in which a wiggly
edge indicates a pair of shared entanglement. We extend the connectivity graph
for single-QPU device to multi-QPU DQC device by combining local connectivity
(solid lines) and the cross-QPU quantum channels (wiggly lines) in Fig. 4.

Figure 4: The extended connectivity graph of a two-QPU DQC device, which has
two local QPUs with $4$ qubits on each. The solid lines denote direct physical
couplings in local QPUs, while the wiggly lines stand for quantum channels
across QPUs.

On a single QPU, to overcome local connectivity limitations, a common approach
is to apply additional swap gates, as illustrated in Figure 5. For high-
quality performance of quantum computation under connectivity limitation, one
needs to reduce the additional noises through the minimization of the swapping
gates in the compilation of quantum circuits. Such a minimization process is
called qubit allocation or assignment [25]. However, even with the optimal
qubit allocation, for some types of physical qubits such as superconducting
qubits, the average steps of swapping among qubits in the connectivity graph
of a single QPU increases very quickly as the number of qubits gets larger.

Figure 5: The implementation of a two-qubit gate on two non-connected qubits
$q_{1}$ and $q_{3}$ with two additional swapping gates.

One benefit of multi-QPU DQC is that it changes and enhances the connectivity
of quantum computing devices, as we can use entangled pairs shared in the
quantum channels between two QPUs to reshape the connectivity graph. The
effect of such connectivity changes in DQC will be discussed in details in the
remaining sections.

##  III The error model for random-circuit benchmarking

Establishing a noise model is essential for the characterization of errors in
quantum devices. In the QV random-circuit sampling, the two-qubit gates are
sampled from Haar random unitaries. We can therefore adopt the depolarizing
channel as our fundamental noise model. Two two extreme scenarios of
depolarizing noises can be employed to approximate the QV random-circuit
sampling, which are visualized in Figure 6. In the case of strong cross-talk
between qubits, the global depolarizing noise applies, in which the
depolarizing channel impacts all qubits together (see Section III.1). In the
other situation where cross-talk among qubits is negligible, the single-qubit
depolarizing noise is applicable (see Section III.2). For the single-qubit
depolarizing noise, the depolarizing channel affects each qubit individually.
In the QV benchmarking, which necessitates the random permutation of qubits,
these two approximations are shown to be equivalent in Section III.2.

(a)

(b)

Figure 6: (a) The global depolarizing channel (blue ellipse) coming after
every layer of the random gates $u_{i}$ and acts on all the qubits globally.
(b) The single-qubit depolarizing channels (blue ellipse) coming after every
layer of the random gates $u_{i}$ and acts on each qubit individually.

With these error models, one can evaluate the benchmarking of QV random-
circuit sampling employing either the average gate fidelity, heavy output
probability, or linear cross-entropy as the figure of merit. Under the single-
qubit error model, we show the one-to-one correspondence of these three
metrics in the QV random-circuit sampling. Such a correspondence enables us to
treat heavy output probability and linear cross-entropy as the function of the
average gate fidelity, which benefits us in two folds. Namely, it provides us
an analytical tool for studying HOP and LXE through the calculation of AGF, as
well as the potential to estimate the AVG from experimental data of HOP or
LXE.

###  III.1 Global depolarizing noise

In the vectorization representation, the effect of the N-qubits depolarizing
channel acting on N-qubits state $|\rho\rangle\rangle$ is

$\displaystyle\widetilde{D}_{P}^{(N)}|\rho\rangle\rangle=P|\rho\rangle\rangle+\frac{(1-P)}{2^{N}}|\mathbb{I}_{2^{N}}\rangle\rangle,$
(11)

where we call $P$ the preserving factor of the depolarizing channel. For
$P=1$, one has perfect identity operator, while for $P=0$, one obtains a
complete depolarizing channel. As shown in Fig. 6 (a), the quantum circuit
implementation of $U=u_{N}.\cdots.u_{1}$ under the global depolarizing noise
is then given as follows,

$\displaystyle\widetilde{U}$
$\displaystyle=\widetilde{u}_{N}.\cdots.\widetilde{u}_{2}.\widetilde{u}_{1}$
$\displaystyle=\widetilde{D}_{P_{N}}^{(N)}.\hat{u}_{N}.\cdots.\widetilde{D}_{P_{2}}^{(N)}.\hat{u}_{2}.\widetilde{D}_{P_{1}}^{(N)}.\hat{u}_{1}.$
(12)

Since the global depolarizing channel commutes with all other channels, we can
simplify Eq. (12) by moving all depolarizing channels to the end of the
circuit and retaining only one depolarizing channel with an effective global
preserving factor $\wp$,

$\widetilde{U}=\widetilde{D}_{\wp}^{(N)}.\hat{U},\;\;\text{with
}\wp=\prod_{j}P_{j}.$ (13)

Under this global depolarizing noise approximation, the average gate fidelity
for a given random circuit $U$ can be then expressed a function of the
effective preserving factor,

$\displaystyle F_{U}(\wp)$
$\displaystyle=\int_{\Psi}d\psi\;\;\langle\langle\psi|\widehat{U}^{\dagger}\widetilde{D}_{\wp}^{(N)}\widehat{U}|\psi\rangle\rangle$
$\displaystyle=\wp+\frac{1}{2^{N}}(1-\wp).$ (14)

Similarly, we can determine the HOP as a function of the preserving factor:

$\displaystyle H_{U}(\wp)$ $\displaystyle=\sum_{x\in X_{U}}\langle\langle
x|\widetilde{D}_{\wp}^{(N)}\widehat{U}|0^{N}\rangle\rangle$
$\displaystyle=H_{U}^{ideal}\wp+\frac{1}{2}(1-\wp).$ (15)

Here, $H_{U}^{\text{ideal}}$ is the ideal HOP for the circuit $U$, and the
$X_{U}$ is the set of heavy outputs of $U$. Regarding the linear cross-
entropy, we can write it as

$\displaystyle\chi_{U}$ $\displaystyle=2^{N}\sum_{x}\langle\langle
x|\widetilde{D}_{\wp}^{(N)}\widehat{U}|0^{N}\rangle\rangle\langle\langle
x|\widehat{U}|0^{N}\rangle\rangle-1$ $\displaystyle=\chi_{U}^{ideal}\;\wp.$
(16)

Although this approximation seems rough, later analysis reveals its
effectiveness in illuminating the relationship between average gate fidelity,
HOP, and linear cross-entropy.

###  III.2 Single-qubit depolarizing noise

In the single-qubit error approximation, we apply two single-qubit
depolarizing channels after each two-qubit gate. As shown in Fig. 6 (b), in
the vectorization presentation, the quantum channel of a random circuit under
single-qubit depolarizing noises can be written as

$\displaystyle\widetilde{U}$
$\displaystyle=\widetilde{D}_{\vec{P}_{N}}.\widehat{u}_{N}\,.\,\cdots\,.\,\widetilde{D}_{\vec{P}_{2}}.\widehat{u}_{2}\,.\,\widetilde{D}_{\vec{P}_{1}}.\widehat{u}_{1},$
(17)

where $\widetilde{D}_{\vec{P}}$ is the tensor product of the single qubit
depolarizing channels and $\vec{P}=(P_{q_{1}},P_{q_{2}},...,P_{q_{N}})$ is a
vector, whose $q$ component $P_{q}$ is the preserving factor of the single-
qubit deodorizing channel acting on the qubit $q$,

$\widetilde{D}_{\vec{P}}\equiv\bigotimes_{q\in\mathbb{Q}}\widetilde{D}_{P_{q}}^{(1)}.$
(18)

Here, the $\mathbb{Q}=\\{q_{1},q_{2},...,q_{N}\\}$ is the set of qubits of a
QPU.

Unlike the global depolarizing channel, the single-qubit depolarizing channel
typically does not commute with other channels. However, in the present
scenario, our unitary operators are sampled randomly from the Haar uniform
distribution. Such a random sampling allow us to make an assumption that
$\widetilde{D}_{\vec{P}}\,.\,\widehat{u}=\widehat{u}\,.\,\widetilde{D}_{\vec{P}}$
holds for all unitary channels. We arrived at this assumption by considering
the behavior of a random SU(4) gate generated according to the Haar uniform
distribution in relation to the single-qubit depolarizing channel.
Specifically, we observed that, on average, the random SU(4) gate commutes
with the single-qubit depolarizing channel. Mathematically, this can be
expressed as

$\displaystyle\int_{U\in
SU(4)}dU\;\;[\widehat{U},\widehat{\mathbb{I}}\otimes\widetilde{D}_{P}^{(1)}]=0,\;\;\forall
P\in[0,1].$ (19)

A detailed proof of this commutation relation is provided in Appendix A. In
this single-qubit depolarizing-noise model, our channel only contains two-
qubit gates and single-depolarising channels. We can therefore rearrange the
order of operations by moving all depolarizing channels to the end of the
circuit,

$\widetilde{U}=\widetilde{D}_{\vec{P}}\,.\,\widehat{U}$ (20)

Note that this effects of noises are independent of the circuit. The the
measurement statistics $p_{U}(n)$ under the single-qubit depolarizing noise
model is then given by

$p_{U}(n)\equiv\langle\langle
n|\widetilde{D}_{\vec{P}}.\widehat{U}|0^{N}\rangle\rangle,$ (21)

which can be formulated as a Markov chain acting on the ideal outcome
distribution.

$\displaystyle p_{U}(n)$ $\displaystyle=\sum_{m\in\\{0,1\\}^{N}}\langle\langle
n|\widetilde{D}_{\vec{P}}|m\rangle\rangle\langle\langle
m|\widehat{U}|0^{N}\rangle\rangle$
$\displaystyle=\sum_{m\in\\{0,1\\}^{N}}D_{\vec{P}}(n|m)q_{U}(m).$ (22)

Here, $q_{U}(m)=\langle\langle m|\widehat{U}|0^{N}\rangle\rangle$ is the ideal
probability. The probability vector $\bm{p}_{U}\equiv\\{p_{U}(n)\\}_{n}$ is
therefore obtain from the Markov matrix of the transfer probability
$D_{\vec{P}}(n|m)$:

$\displaystyle D_{\vec{P}}$ $\displaystyle\equiv\\{D_{\vec{P}}(n|m)\\}_{n,m}$
$\displaystyle=\bigotimes_{q\in\mathbb{Q}}\left(P_{q}\begin{bmatrix}1&0\\\
0&1\end{bmatrix}+\frac{1-P_{q}}{2}\begin{bmatrix}1&1\\\
1&1\end{bmatrix}\right)$ (23)

In this formulation, the average gate fidelity is the diagonal element of the
Markov matrix,

$\displaystyle F_{U}(\vec{P})$
$\displaystyle=\int_{\Psi}d\psi\;\;\langle\langle\psi|\widehat{U}^{\dagger}\widetilde{D}_{\vec{P}}\widehat{U}|\psi\rangle\rangle=\langle\langle
0^{N}|\widetilde{D}_{\vec{P}}|0^{N}\rangle\rangle$
$\displaystyle=\prod_{q\in\mathbb{Q}}\frac{1+P_{q}}{2}.$ (24)

Note that the average gate fidelity is independent of $U$, hence we obtain the
average AGF $\bar{F}=F_{U}(\vec{P})$. It can be also expressed by an effective
global preserving factor $\wp$

$\bar{F}=\wp+\frac{1}{2^{N}}(1-\wp).,\;\;\;\wp\equiv\frac{\prod_{q\in\mathbb{Q}}(1+P_{q})^{2}-1}{2^{N}-1}$
(25)

The determination of the vector of effective preserving factor
$\vec{P}=(P_{q_{1}},...,P_{q_{N}})$ will be discussed in the next section.

To calculate the heavy output probability, we first express it as the inner
product between the probability vector and the heavy output vector
$\bm{h}^{U}$.

$\displaystyle H_{ideal}^{U}$
$\displaystyle=\sum_{n\in\\{0,1\\}^{N}}h^{U}_{n}\,p_{U}(n)$ (26)
$\displaystyle h^{U}_{n}$ $\displaystyle=\begin{cases}1\;\;if\;n\in X_{U}\\\
0\;\;if\;n\notin X_{U}\end{cases}$ (27)

We then define the average probability vector $\bar{\bm{p}}$ by rearranging
the probability vector in descending order.

$\displaystyle\bar{\bm{p}}=\int_{U}dU\;\Pi_{U}\bm{p}_{U}$ (28)

The average HOP is then obtained by summing the probabilities of the top half
of the average probability vector $\bar{\bm{h}}=\\{\bar{h}_{n}\\}_{n}$, and
replace the binary index $n$ with decimal index.

$\displaystyle\bar{H}_{ideal}$ $\displaystyle=\sum_{n}\bar{h}_{n}\bar{p}_{n}$
(29) $\displaystyle with\;\;\bar{h}_{n}$
$\displaystyle=\begin{cases}1\;\;if\;n<2^{N-1}\\\ 0\;\;if\;n\geq
2^{N-1}\end{cases}$

Although predicting the set of heavy outputs $X_{U}$ for different $U$ is
generally challenging, the random circuit’s structure offers insights. With
uniform random permutations among qubits and SU(4) gates under the Haar
measure, the probability of obtaining a specific heavy output remains
constant. Therefore, we can approximate the average heavy output probability,
accounting for errors, by utilizing the Markov matrix outlined in Eq. (22),
considering the average over all permutations,

$\displaystyle\bar{H}(\vec{P})$
$\displaystyle=\frac{1}{2^{N}!}\sum_{\Pi\in\mathbf{S}_{2^{N}}}\bar{\bm{h}}^{T}\,.\,\Pi^{T}D(\vec{P})\Pi\,.\,\bar{\bm{p}},$
$\displaystyle\equiv\bar{\bm{h}}^{T}\,.\,\bar{D}(\vec{P})\,.\,\bar{\bm{p}},$
(30)

where $\Pi$ is the permutation matrix and $\mathbf{S}_{2^{N}}$ is the
permutation group. After averaging over permutations, one obtains an effective
Markov matrix $\bar{D}(\vec{P})$,

$\bar{D}(\vec{P})\equiv\sum_{\Pi\in\mathbf{S}_{2^{N}}}\Pi^{T}D(\vec{P})\Pi.$
(31)

The diagonal element of $\bar{D}(\vec{P})$ is the average of all diagonal
elements of $D(\vec{P})$, while the off-diagonal elements of
$\bar{D}(\vec{P})$ is the average of all off-diagonal elements of
$D(\vec{P})$. The diagonal elements in $\bar{D}(\vec{P})$ is therefore equal
to $\bar{F}$. Since $\bar{D}(\vec{P})$ is a symmetric Markov matrix, we deduce
that all off-diagonal elements are equal to $\frac{1-\bar{F}}{2^{N}-1}$.

$\displaystyle\bar{D}(\vec{P})$
$\displaystyle=\frac{1}{2^{N}!}\sum_{\Pi\in\mathbf{S}_{2^{N}}}\Pi^{T}D(\vec{P})\Pi$
$\displaystyle=\begin{bmatrix}\bar{F}&\frac{1-\bar{F}}{2^{N}-1}&\dots&\frac{1-\bar{F}}{2^{N}-1}\\\
\frac{1-\bar{F}}{2^{N}-1}&\bar{F}&\dots&\frac{1-\bar{F}}{2^{N}-1}\\\
\vdots&\vdots&\ddots&\vdots\\\
\frac{1-\bar{F}}{2^{N}-1}&\frac{1-\bar{F}}{2^{N}-1}&\dots&\bar{F}\end{bmatrix}.$
(32)

From Eq. (32), one can see that $\bar{D}(\vec{P})$ is a Markov matrix under
the global depolarizing-noise model, which implies that averaging over
permutations leads us back to the global depolarizing approximation.

Consequently, we arrive at the average HOP $\bar{H}$ as a functions of the
average AGF $\bar{F}$, which are them given by the effective global preserving
factor $\wp$,

$\displaystyle\bar{H}(\vec{P})$
$\displaystyle=\bar{H}_{ideal}\frac{2^{N}\bar{F}-1}{2^{N}-1}+(1-\bar{F})\frac{2^{N-1}}{2^{N}-1}$
$\displaystyle=\bar{H}_{ideal}\;\wp+\frac{1}{2}(1-\wp)$ (33)

The same result holds for and the LXE

$\displaystyle\bar{\chi}(\vec{P})$
$\displaystyle=\frac{2^{N}\bar{F}-1}{2^{N}-1}\bar{\chi}_{ideal}=\bar{\chi}_{ideal}\;\wp$
(34)

A linear relation between linear cross-entropy benchmarking and heavy output
testing can be then derived,

$\displaystyle\bar{H}(\vec{P})=\frac{1}{2}+\frac{1}{2}\ln
2\frac{\bar{\chi}(\vec{P})}{\bar{\chi}_{ideal}}.$ (35)

This two equations implies the one-to-one correspondence among average HOP,
LXE and average AGF. This one-to-one correspondence is exact the same as the
their relation in global depolarizing-noise model. It implies the equivalence
between global depolarizing noise and single-qubit depolarizing noise in the
random-circuit benchmarking. In the large size limit ($2^{N}\gg 1$), this one-
to-one correspondence can be simplified to

$\displaystyle\bar{H}(\vec{P})\approx\frac{1+\bar{F}\ln{2}}{2},\;\;\;\;\bar{\chi}(\vec{P})$
$\displaystyle\approx\bar{F}\;\bar{\chi}_{ideal}.$ (36)

In the quantum volume benchmarking, if devices pass the test, then we must
have $\bar{H}(\vec{P})>\frac{2}{3}$. So the threshold for the linear cross-
entropy, by the suggestion of the quantum volume benchmarking, is
$\bar{\chi}(\vec{P})>\frac{1}{3\ln{2}}\bar{\chi}_{ideal}$, and similar for the
average gate fidelity. Another important consequence of Eq. (III.2) and Eq.
(34) is that now HOP and LXE are the linear functions of the average gate
fidelity for arbitrary two QPUs with $\vec{P}_{\mathbb{Q}}$ and
$\vec{P}_{\mathbb{Q}^{\prime}}$, we had:

$\displaystyle\bar{F}(\vec{P}_{\mathbb{Q}})\geq\bar{F}(\vec{P}_{\mathbb{Q}^{\prime}})$
$\displaystyle\Leftrightarrow\bar{H}(\vec{P}_{\mathbb{Q}})\geq\bar{H}(\vec{P}_{\mathbb{Q}^{\prime}})$
$\displaystyle\Leftrightarrow\bar{\chi}(\vec{P}_{\mathbb{Q}})\geq\bar{\chi}(\vec{P}_{\mathbb{Q}^{\prime}})$
(37)

As a result of Eq. (37), we only need to employ average gate fidelity to
evaluate the performance of QPUs, which is our main focus in the next section.

###  III.3 The error model for DQC under connectivity constraints

In the previous section, we derive a one-to-one correspondence relation among
different metrics QV random-circuit benchmarking, which allows us to employ
average AGF to evaluate quantum computing device. According Eq. (24) and (25),
the average AGF is determined by the effective preserving factors
$\vec{P}=(P_{q_{1}},...,P_{q_{N}})$. In this section, we will establish a
theory for determining the vector $\vec{P}$ under connectivity constraints.

(a)  (b)  (c)

Figure 7: Extended connectivity graph. The distinction between graphs (b) and
(c) is the positioning of the auxiliary memory qubits. Notably, the graphs (a)
and (c) coincide if the auxiliary memory qubits are replaced with a coupling
between $q_{1}$ and $q_{2}$. (a) A 1D connectivity graph of a single QPU with
$8$ qubits. (b) A two-1D-QPU DQC connectivity graph with $8$ working qubits in
total. The memory qubit on each QPU stores an entangled pair between the two
QPUs. (c) A two-1D-QPU DQC connectivity graph resulting a new extended 1D
connectivity graph.

We start our analysis with the fully connected single-QPU device, which is the
simplest case. An $N$-qubit quantum volume circuit has N layers of gates. In
each layer, there are $\lfloor\frac{N}{2}\rfloor$ SU(4) gates acting on N
qubits. In the single-qubit depolarizing noise model, each SU(4) gate is
followed by two single-qubit depolarizing channels. There are in total
$2N\lfloor\frac{N}{2}\rfloor$ depolarizing channels acting on the $N$ qubits.
Here, we assume the preserving factor $P_{q}$ of a single-qubit depolarizing
channel is a constant for a qubit $q$, independent of layers. The average gate
fidelity can be then estimated by the following formula,

$\displaystyle\bar{F}=\prod_{q\in\mathbb{Q}}\frac{1+P_{q}^{2\lfloor\frac{N}{2}\rfloor}}{2},$
(38)

where the $\mathbb{Q}$ is the set of qubits representing a QPU.

For a QPU with limited connectivity, additional swapping gates are needed. For
multi-QPU DQC, one needs auxiliary qubits for telegating. Both processes
introduce additional noises to the implementation of quantum computing. To
assess the average AGF of multi-QPU DQC with limited connectivity one needs to
incorporate the noises introduced by swapping gates and the telegating
processes into the effective preserving factors $\bar{P}_{q}$. We achieve this
by introducing an allocation matrix
$\\{A_{q,q^{\prime}}\\}_{q,q^{\prime}\in\mathbb{Q}}$ modeled with the single-
qubit depolarizing noises. Each element $A_{q,q^{\prime}}$ of the allocation
matrix describes the average number of single-qubit depolarizing channels
propagating from the qubit $q^{\prime}$ to the qubit $q$, when one implements
a random two-qubit SU(4) gate on $q$. The effective preserving factor
$\bar{P}_{q}$ for a qubit $q$ in multi-QPU DQC is therefore given by

$\displaystyle\bar{P}_{q}$
$\displaystyle=\prod_{q^{\prime}\in\mathbb{Q}}P_{q^{\prime}}^{A_{q,q^{\prime}}},$
(39)

where $\mathbb{Q}$ is the set of all qubits on the composited QPUs. For
example, in the DQC device represented by the extended connectivity graphs
shown in Fig. 7 (b) and (c), the complete qubit set
$\mathbb{Q}=\mathbb{Q}_{w}\cup\mathbb{Q}_{m}$ includes the set of working
qubits $\mathbb{Q}_{w}=\\{q_{1},...,q_{8}\\}$ and the set of memory qubits
$\mathbb{Q}_{m}=\\{m_{A},m_{B}\\}$. Note that, the preserving parameter
$P_{q}$ quantifies the quality of a direct two-qubit gate acting on two
connected qubits, while the allocation matrix $A_{q,q^{\prime}}$ characterizes
the connectivity topology and the memory allocation of a multi-QPU DQC device,
which are represented by an extended connectivity graph. Since the
benchmarking only evaluates the measurement readouts of the working qubits,
the average AGF is solely determined by the effective preserving factors
$\bar{P}_{q}$ of the working qubits $q\in\mathbb{Q}_{w}$. One therefore
arrives at the following formula for the average AGF in a multi-QPU DQC
device,

$\displaystyle\bar{F}$
$\displaystyle=\prod_{q\in\mathbb{Q}_{w}}\frac{1+\bar{P}_{q}^{2\lfloor\frac{N}{2}\rfloor}}{2}.$
(40)

Figure 8: From extended connectivity graph to cost matrices. (a) An extended
connectivity graph with the working qubits
$\mathbb{Q}_{w}=\\{q_{1},q_{2},q_{3},q_{4}\\}$ and the memory auxiliary qubits
$\mathbb{Q}_{m}=\\{m_{a},m_{b}\\}$. (b) A random two-qubit gate $u_{n}$ acts
on the qubit $\\{q_{1},q_{2}\\}$. (c) An implementation of $u_{n}$ with
single-qubit depolarizing noises. (d) Moving all single-qubit depolarizing
noises to the end of the circuit.

To determine the allocation matrix for a given extended connectivity graph, we
analyze the implementation cost of a random two-qubit gate between two qubits
$q$ and $q^{\prime}$. The cost that one needs to pay is the single-qubit
depolarizing channels introduced by additional swapping gates under limited
connectivity of $\mathbb{Q}_{w}$ and telegating across the auxiliary qubits
$\mathbb{Q}_{m}$. For the example shown in Fig. 8, in the $n$-th layer of a QV
random-circuit benchmarking, one randomly chooses a two-qubit unitary $u_{n}$
acting on the qubits $\\{q_{1},q_{3}\\}$, as shown in Fig. 8 (b). Under the
extended connectivity of the two-QPU DQC device shown in Fig. 8 (a), the
implementation of $u_{n}$ introduces depolarizing channels, which are depicted
as the circles in Fig. 8 (c). Taking the average over the QV random-circuit
sampling, the one can approximately moving all single-qubit depolarizing
channels to the end of circuit with the effective preserving factors shown in
Fig. 8 (d). For the implementation of $u_{n}$ on $\\{q_{1},q_{3}\\}$ under the
extended connectivity graph, one can a cost matrix $C(q_{1},q_{3})$ as
follows,

$C(q_{1},q_{3})=\begin{bmatrix}1&2&0&0&\frac{1}{3}&\frac{1}{3}\\\
1&1&0&0&0&0\\\ 0&0&1&0&\frac{1}{3}&\frac{1}{3}\\\ 0&0&0&0&0&0\end{bmatrix}.$
(41)

Each element $C_{n,m}(q_{1},q_{3})$ of the cost matrix counts the number of
depolarizing channels originated from the qubit $q_{m}$ and acting on the
working qubit $q_{n}$. Note that a cost matrix $C(q,q^{\prime})$ contain $N$
rows of working qubits and $N+M$ columns of working and auxiliary memory
qubits. The detailed steps and examples of calculating this cost matrix are
provided in Appendix B.

Finally, we define the allocation matrix $A$ by aggregating the cost matrices
of all pairs of working qubits,

$\displaystyle
A\equiv\frac{1}{2(N-1)}\sum_{q,q^{\prime}\in\mathbb{Q}_{w}}C(q,q^{\prime})$
(42)

Here, the cost matrices are divided by $2(N-1)$ to ensure that the allocation
matrix of a fully connected QPU is normalized to
$A_{q,q^{\prime}}=\delta_{q,q^{\prime}}$, such that Eq. (38) aligns with Eq.
(40) as a special case.

##  IV Numerical simulation of benchmarking

In this section, we employ numerical simulation to scrutinize the one-to-one
correspondence among HOP, LXE, and AGF in our single-qubit depolarizing
approximation outlined in the preceding section. We adopt the average AGF as
the figure of merit for the two-QPU DQC benchmarking, and show a performance
improvement of DQC under limited connectivity, which indicates the enhancement
of scalability of quantum computing through DQC.

We employ the same random circuit structure utilized in quantum volume
benchmarking to compute both the HOP and linear cross-entropy. However, it
should be noted that the specific random circuit structure chosen should not
undermine our results, given that they all effectively approximate the Haar
uniform unitaries. To reduce the total number of gates and the efficiency of
the circuit compiling, we replace the permutation gates in QV random circuits
by repositioning the SU(4) gates. The SU(4) gates are samples through the KAK
decomposition, in which any SU(4) gate can be expressed as a sequence of
single-qubit operations and three CNOT gates.

For global SU(4) gates acting across the two local QPUs, we apply the EJPP
protocol to these CNOT gates. We then can implement all the non-local SU(4)
gates through DQC, as depicted in Fig. 9. It is worth noting that this
approach necessitates three entangled pairs to implement a single SU(4) gate.
Alternatively, utilizing quantum state teleportation reduces this requirement
to two entangled pairs (one for sending the state and one for returning it).
However, adopting quantum state teleportation entails the addition of one more
qubit to each local QPU. The utility of the EJPP telegating protocol minimizes
the number of auxiliary memory qubits to one within each local QPU, and hence
maximize the number of working qubits.

Figure 9: Implementation of a non-local SU(4) gate using the EJPP protocol.
The diagram illustrates the application of three independent EJPP protocols to
realize the SU(4) gate via DQC.

In our simulation, we select six types of connectivity, which can be
categorized into two groups. The first group comprises devices utilizing a
single QPU, while the second group consists of DQC-composited devices equipped
with two local QPUs. Within each group, the local QPUs exhibit three types of
connectivity graphs, namely fully connected graph, 1D (line) graph, and 2D
(grid) graph, respectively. Fig. 10 illustrates the extended connectivity
graphs of our simulation devices. Solid lines denote the coupling between
physical qubits, while wavy lines represent the sharing of entangled pairs
between auxiliary memory qubits. For the two-QPU DQC devices, each local QPU
contains only one auxiliary memory qubit. The allocation of the auxiliary
memory qubit is chosen as the hub qubit, which improves the connectivity to
the greatest extent. [Explain, fix topology for local QPUs]

Figure 10: Extended connectivity graphs for simulation. The first column is
the group of single-QPU devices, where the blue vertices represent the working
qubits that are responsible for the computing, and the black edges identify
the direct coupling between qubits. The second column is the group of two-QPU
DQC devices, where the blue and orange vertices represent the working qubits
of the local QPUs, and the yellow vertices denote the auxiliary memory qubits.
Each auxiliary memory qubit can either store the shared entangled state or
facilitate the passage of additional swapping gates.

(a)  (b)

(c)  (d)

(e)  (f)

(g)  (h)

Figure 11:  (a),(c),(e),(g) Average gate fidelity of $5$-qubit devices with
different types of connectivity. The data points represent the average gate
fidelity obtained from numerical simulation for different error rates. The
lines show the theoretical prediction of average gate fidelity derived from
Eq. (40). (b),(d),(f),(h) Comparison between the error rate specified in the
qiskit noise model and the error rate estimated through our average gate
fidelity formula in Eq. (40). The markers represent the data points obtained
from our simulation, while the lines represent the linear fitting of our data.

We employ qiskit to simulate the QV random benchmarking under the single-qubit
depolarizing noise model. With Eq. (34), we employ linear cross-entropy for
measuring average gate fidelity. The simulation is conducted as follows. In
the first run, we set a constant error rate $\epsilon=0.05\%$ ($\epsilon\equiv
1-P$) across all qubits in qiskit, and conduct QV random-circuit sampling on
different types of connectivity for $n$-qubit devices, where $n=5,...,8$. For
simplicity, we assumed that all entangled pairs were perfect. In the next
runs, we vary the error rates $\epsilon$ from $0.05\%$ to $0.5\%$ and
implement the same QV random-circuit sampling. We sampled over $1000$ random
circuits for each connectivity graph and error rate, and executed $10,000$
shots for each sampled circuit. After the sampling, for each connectivity
graph and error rate, we obtain an average AGF $\bar{F}$, which are plotted by
different markers in Fig. 11 (a,c,e,g).

To verify the result in Eq. (40), we calculate the effective preserving factor
$P_{\text{eff}}$, as well as the effective error rate
$\epsilon_{\text{eff}}\equiv 1-P_{\text{eff}}$ from each average AGF data
according to Eq. (40). In Fig. 11 (b,d,f,h), the effective error rates
$\epsilon_{\text{eff}}$ are compared with the initial inputs
$\epsilon_{\text{in}}$ of the qiskit function. From the simulation, we observe
that the effective error rates are linearly proportional to the input error
rates with a ratio $r_{G,n}$ around $0.8\sim 1$ varying with different types
of connectivity $G$ and qubit numbers $n$,

$\epsilon_{\text{eff}}=r_{G,n}\epsilon_{\text{in}}.$ (43)

Ideally, one expects $r_{G,n}=1$, however, a small distinction arises. This
discrepancy stems from the difference between our error model and the
compilation in qiskit. In our error model, we treat every SU(4) gate as a
fundamental building block and assume that all the errors are single-qubit
depolarizing noises. On the other hand, in qiskit, an SU(4) gate is decomposed
into a sequence of single-qubit gates and CNOT gates, which are subject to
single-qubit and two-qubit depolarizing channels, respectively. [The strong
linearity between $\epsilon_{\text{eff}}$ and $\epsilon_{\text{in}}$ provides
a compelling evidence for the validity of Eq. (40).]

Due to the lack of knowledge about the detailed compilation in qiskit, we
should use the ratio $r_{G,n}$ fitted in Fig. 11 (b,d,f,h) to calibrate the
effective preserving factor from Eq. (39),

$\bar{P}_{q}=\prod_{q^{\prime}\in\mathbb{Q}}(1-r_{G,n}+r_{G,n}P_{\text{in}})^{A_{q,q^{\prime}}}.$
(44)

Employing this calibrated effective preserving factor, we plot the theoretical
prediction of Eq. (40) for different connectivities by lines in Fig. 11
(a,c,e,g). One can observe that the theoretical predictions in Eq. (40) and
the simulate results evaluated through the AGF-HOP correspondence in Eq.
(III.2), align with each other very well. It verifies both the AGF-HOP
correspondence in Eq. (III.2) and our error model in Eq. (40).

Figure 12: Average AGF of 1D connectivity graph shown in Fig. 7 for different
error rates. The two-QPU DQC device in Fig. 7(b) featuring memory qubits
positioned in the middle, which exhibits a significant advantage over the
single-QPU device. However, the two-QPU DQC device with memory qubits at the
edges does not offer any advantage. Therefore, the strategic selection of the
auxiliary memory qubit’s positions on each local QPU emerges as a critical
condition for scalability enhancement.

Besides, in Fig. 11 (a,c,e,g), one can also observe that single fully
connected QPU exhibits the highest average gate fidelity among the different
connectivity graphs, which is expected as there are no additional gates
introduced. Its corresponding two-QPU DQC devices perform slightly worse, as
additional gates for telegating applied. On the contrary, for 1D and 2D
connectivity, the two-QPU DQC devices outperform the single-QPU device for all
$n$-qubit devices, which show the enhancement of scalability in two-QPU DQC
under limited connectivity. The condition for such scalability enhancement
depends on the connectivity of QPUs. To confirm this assertion, we conduct
another simulation for $1D$ connectivity, where we relocate the auxiliary
memory qubit in each QPU to the end of the line graph, as illustrated in Fig.
7 (c). In this configuration, the two-QPU DQC device resembles a single-QPU
device with a line graph topology. Since the implementation of DQC does not
enhance the connectivity, and meanwhile there will be additional error costs
introduced by telegating, we expect no scalability enhancement for this
configuration, which aligns with in the simulation results plotted in Fig. 12.

(a)

(b)

Figure 13:  QV random-circuit benchmarking for $n$-qubit devices with
different types of connectivity. Here the size of devices ranges from $3$ to
$10$. (a) HOP-LXE correspondence. (b) HOP for different sizes and
connectivity.

To further support the AGF-HOP-LXE correspondence and scalability enhancement
of DQC, we conduct additional simulations, in which we fix the error rate
$\epsilon_{\text{in}}=0.15\%$ for all qubits, and benchmark both single-QPU
and two-QPU devices from $3$-qubit to $10$-qubit. Under this setting, we
sample over $2000$ random circuits for all sizes and take $10000$ shots for
each random circuit. For each configuration of connectivity graph $G$ and
qubit number $n$, we evaluate the measurement outputs with both average HOP
and LXE, and plot them in Fig. 13(a). One can clearly verify the HOP-LXE
correspondence derived in Eq. (35) with these simulated data as a general
property independent of device size and connectivity.

Employing the obtained data, we evaluate the quantum volume of different
devices in Fig. 13(b), which offer insights into the scalability of device
architecture by illustrating how the HOP decreases with increasing device
size. It shows that, for a fully connected QPU, the DQC configuration doesn’t
offer advantage over a single-QPU setup. Note that this statement is only made
for the situation when the error rates of multiple small-size QPUs are the
same as the error rate of a large-size single QPU. However, in practice, the
error rate of a small-size QPU is usual smaller than the one of a large-size
QPU.

Besides the fully connectivity, for the devices with 1D and 2D connectivity
graphs, we observe that the two-QPU DQC devices exhibits superior HOP compared
to the single-QPU configuration. Especially for 1D connectivity, we observe
the increase of quantum volume from $2^{7}$ to $2^{9}$ through DQC. These
observations suggest that the connectivity of the devices plays a pivotal role
in the scalability analysis of multi-QPU DQC under the QV random-circuit
benchmarking scheme.

##  V Results and discussion

Our theoretical calculation and numerical simulation of QV random-circuit
benchmarking show that the scalability enhancement in DQC strongly depends on
the connectivity of QPUs, the choice of the auxiliary memory qubits for
establishing a quantum communication channel, and the quality of entanglement
distribution.

First, for fully connected devices shown in Fig. 11 and Fig. 13 (b), DQC does
not improve the scaling of quantum computing, if the error rate of a QPU of a
larger size is the same as a smaller-size QPU. The underlying reason is the
additional gates in the EJPP protocol that cause additional gate errors and
lower the circuit’s average gate fidelity.

$\bar{F}_{\text{DQC}}\underset{\text{fully
connected}}{<}\bar{F}_{\text{single}}.$ (45)

Under the same reason, a more general observation is that the multi-QPU DQC
configurations that preserve the topology of single QPUs should not have
advantage over single-QPU device, if we assume the same error rate of quantum
gates on each QPU regardless of their size in qubit numbers. However, in
practice, the gate error rate on a single QPU should increase as the number of
qubits increases. Under this consideration, the utility of DQC with small-size
QPUs, which have a lower error rate, can also enhance the scalability. For
example, according to benchmarking data is plotted in Fig. 12, for the
configuration shown in Fig. 8 (c), if the error rate of two $5$-qubit QPUs is
$\epsilon=0.1\%$, one would expect an average AGF around $\bar{F}=0.55$, which
is greater than the average AGF $\bar{F}=0.43$ of the single-QPU device with
$\epsilon=0.15\%$. In this regard, even without changes of connectivity
topology, one can still expect scalability enhancement.

Second, for devices with limited connectivity, DQC can change the connectivity
and reduce the number of swapping gates utilized for the implementation of
two-qubit gates on two non-neighboring qubits. To improve connectivity in the
best way, the auxiliary memory qubits for sharing an entangled Bell pair
should be chosen as the qubit that has the highest degree of neighboring
qubits. Such an enhancement in connectivity can compensate for and even
overcome the additional errors introduced by telegating, so that one can
enhance quantum computing performance by scaling up the system through multi-
QPU DQC, as it is shown in Fig. 11 and Fig. 13 (b).

$\bar{F}_{\text{DQC}}\underset{\text{1D or 2D}}{>}\bar{F}_{\text{single}}.$
(46)

For large-size QPUs with more complicated connectivity graphs, it is not
efficient to try all possible choices of auxiliary memory qubit to find the
best DQC configuration for scalability enhancement employing Eq. (40). To
provide an efficient analytical tool, we introduce further approximation of
average AGF for large-size and high-fidelity QPUs,

$\displaystyle\bar{F}_{\mathbb{Q}}(\epsilon)$
$\displaystyle\approx\exp(-\frac{N\mathcal{A}_{\mathbb{Q}}}{2}\epsilon),$ (47)

where the error rate for every qubit is a constant $\epsilon$, and the
_characteristic cost_ $\mathcal{A}_{\mathbb{Q}}$ of a connectivity
configuration $\mathbb{Q}$ is the sum of all elements of the allocation matrix
$A_{q,q^{\prime}}$

$\mathcal{A}_{\mathbb{Q}}\equiv\sum_{q\in\mathbb{Q}_{w},q^{\prime}\in\mathbb{Q}}A_{q,q^{\prime}}.$
(48)

Here $\mathbb{Q}_{w}$ is the set of working qubits and $\mathbb{Q}$ is the set
of all qubits including auxiliary qubits for telegating (for detailed
derivation see Appendix D). Eq. (47) can be employed as a heuristic method for
evaluating connectivity configurations of DQC devices. Fig. 17 is the
comparison between Eq. (40) and Eq. (47) for different extended connectivity.
and it shows that the approximation works well for $\bar{F}\gtrapprox 0.6$,
which is around the threshold of QV benchmarking. This implies that this
approximation is sufficient for evaluating quantum computing performance in QV
random-circuit benchmarking. Moreover, we can also use the approximated
formula in Eq. (47) to decide the position of the auxiliary memory qubits on
local QPU by minimizing the _characteristic cost_ $\mathcal{A}_{\mathbb{Q}}$
over all possible allocation.

Figure 14: Robustness of scalability enhancement against the imperfection in
entanglement.

Third, there is another implicit requirement for scalability enhancement, that
is high-quality entangled pairs shared between local auxiliary memory qubits.
In previous analysis and simulation, we assume perfect entangled pairs are
distributed among QPUs and only the noises of local gates involved in the EJPP
processes contribute errors in telegating. However, the fidelity of entangled
pairs strongly affects the capability of telegating for improving the
connectivity. If the entanglement is too noisy, telegating will not be capable
to enhance the scalability. With a small extension (see Appendix E), the
theory of fidelity estimation in Eq. (40) can be employed to analyze the
robustness of scalability enhancement in a DQC configuration against the noise
$\epsilon_{E}$ in entanglement, where the noise is described as the
depolarizing channel with an error rate $\epsilon_{E}$ and a preserving factor
$p_{E}=1-\epsilon_{E}$,

$D_{p_{E}}(\Phi)=(1-\epsilon_{E})\ket{\Phi}\bra{\Phi}+\epsilon_{E}\frac{1}{4}\widehat{\operatorname{\mathbbold{1}}},$
(49)

and $\ket{\Phi}$ is one of the Bell states. In Fig. 14, we simulate the effect
of noise in entanglement on the average gate fidelity and compare them with
theoretical prediction. Our theory predicts that the DQC scalability
enhancement for $1D$ and $2D$ connectivity is robust against the noise
$\epsilon_{E}$ up to $0.65\%$ and $1.63\%$, respectively, which are lower
bounds on the simulated results. We can therefore determine the essential
requirement on entangled pairs for DQC scalability enhancement employing Eq.
(40).

##  VI Conclusion

In this work, we employ average gate fidelity, heavy output probability, and
linear cross-entropy as the figures of merits to benchmark the performance of
DQC through random circuit sampling, and compare them with single-QPU quantum
computing. Under an approximation using a single-qubit depolarizing error
model, we show the one-to-one correspondence among these three figures of
merits in Eq. (III.2), (34), and (35). This relation allows us to obtain a
unified evaluation of the performance of quantum computing devices in the
random-circuit benchmarking.

The theoretical evaluation according to our theory in Eq. (40) agrees with the
simulation results, which show the scalability enhancement in DQC for QPUs
with limited connectivity, such as 1D and 2D graphs shown in Fig. 11 and 13.
The results suggest that the condition of scaling up quantum computing using
DQC is to choose a good qubit that is connected to a large number of neighbors
as the auxiliary memory qubit on each local QPU for the quantum communication
channel. And for given local QPUs, we can find the best position for the
auxiliary memory qubit, with the help of the allocation matrix $A$ introduced
in Eq. (42), and a heuristics method of finding the best position is through
the minimization of the characteristic value $\mathcal{A}_{\mathbb{Q}}$.

In the future, one may generalize the theory in three directions. The first is
to consider multipartite DQC-composited devices with more than two local QPUs.
The second is to increase the number of auxiliary memory qubits for the
quantum communication channel on each local QPU. For example, if there are two
auxiliary memory qubits on each local QPU, the DQC-composed device can support
the advanced embedding-enhanced distributing processes proposed in [15, 16].
The embedding-enhanced distributing techniques can enhance the efficiency of
quantum communication channels and hence improve the average gate fidelity of
the telegating implementation. The last is to incorporate qubit allocation in
the random circuit benchmarking, which will reduce the number of swapping
gates and entangled pairs, and hence improve the quantum computing
performance. These three directions are highly related to each other and all
play important roles in the development of DQC.

###### Acknowledgements.

This work is supported by NSTC under the Grant No. 111-2923-M-032-002-MY5,
112-2112-M-032-008-MY3, 112-2811-M-032-005-MY2, 112-2119-M-008-007, and
113-2119-M-008-010.

##  Appendix A The commutative hypothesis

In Section III.2, we proposed a hypothesis asserting the commutativity of the
SU(4) gate with the single-qubit depolarizing channel. This hypothesis stems
from the observation that, under the Haar measure, a random SU(4) gate tends
to commute with the single-qubit depolarizing channel, expressed as:

$\displaystyle\int_{U\in
SU(4)}dU\;\;[\hat{U},\hat{\mathbb{I}}\otimes\widetilde{D}_{P}^{(1)}]=0\;\;\forall
P\in[0,1]$ (50)

To substantiate this claim, we draw upon an essential lemma from reference
[26], which states that the average unitary transformation under the Haar
measure for all linear operators in $\mathcal{H}^{d}$ is:

$\displaystyle\int_{U\in
SU(d)}dU\;UXU^{\dagger}=\frac{tr(X)}{d}\mathbb{I}_{d}$ (51)

By vectorization, we reformulate this lemma as:

$\displaystyle\int_{U\in SU(d)}dU\;\hat{U}|X\rangle\rangle$
$\displaystyle=\frac{tr(X)}{d}|\mathbb{I}_{d}\rangle\rangle=\frac{1}{d}|\mathbb{I}_{d}\rangle\rangle\langle\langle\mathbb{I}_{d}|X\rangle\rangle\;\;\forall|X\rangle\rangle$
(52) $\displaystyle\Leftrightarrow$ $\displaystyle\int_{U\in
SU(d)}dU\;\hat{U}=\frac{1}{d}|\mathbb{I}_{d}\rangle\rangle\langle\langle\mathbb{I}_{d}|$
(53)

Consequently, for the two-qubit scenario, we have:

$\displaystyle\int_{U\in
SU(4)}dU\;\hat{U}=\frac{1}{4}|\mathbb{I}_{4}\rangle\rangle\langle\langle\mathbb{I}_{4}|=\widetilde{D}_{0}^{(2)}=\widetilde{D}_{0}^{(1)}\otimes\widetilde{D}_{0}^{(1)}$
(54)

Utilizing the property of the depolarizing channel that
$\widetilde{D}^{(N)}_{P}\circ\widetilde{D}^{(N)}_{P^{\prime}}=\widetilde{D}^{(N)}_{P^{\prime}}\circ\widetilde{D}^{(N)}_{P}=\widetilde{D}^{(N)}_{PP^{\prime}}$,
we derive:

$\displaystyle[\widetilde{D}_{0}^{(1)}\otimes\widetilde{D}_{0}^{(1)},\hat{\mathbb{I}}_{2}\otimes\widetilde{D}^{(1)}_{P}]=0\;\forall
P\in[0,1]$ (55) $\displaystyle\Leftrightarrow\int_{U\in
SU(4)}dU\;\;[\hat{U},\hat{\mathbb{I}}\otimes\widetilde{D}_{P}^{(1)}]=0\;\forall
P\in[0,1]$ (56)

This completes the proof.

##  Appendix B Examples of calculating cost matrix and allocation matrix

For the swapping gates, we introduce two single-qubit depolarizing channels
after each swapping gate. As is customary, we aim to position depolarizing
channels at the end of the gate sequence. Although swapping gates do not
commute with single-qubit depolarizing channels, a swapping gate after a
single-qubit depolarizing channel moves the noise to another qubit, which
allows us to directly position the depolarizing channels at the end of the
circuit. Note that one may reduce the number of applied swapping gates, if one
does not swap the qubits back to their original place. However, in our
analysis, we adopt the approach that one immediately swaps the qubits back to
their original position after the implementation of the two-qubit gate as
shown in Fig. 5. This will keep the qubit allocation unchanged and let the
additional swap gates form a closed swapping path.

For a multi-QPU DQC device, we incorporate a non-local telegate employing the
EJPP protocol. In that case, we need to transfer the effects of noises from
auxiliary qubits to the working qubits. To this end, We introduce single-qubit
depolarizing channels on both sides of the working qubits, characterized by an
preserving factor of $(P_{a}P_{a^{\prime}})^{\frac{1}{3}}$, where $P_{a}$ and
$P_{a^{\prime}}$ represent the preserving factors of the auxiliary qubits $a$
and $a^{\prime}$, respectively. The proof of this noise shifting phenomenon is
provided in Appendix C.

For devices comprising M auxiliary qubits and N working qubits, the cost
matrix $C(q,q^{\prime})$ for a gate can be determined through the following
steps:

  1. 1.

Identify the swapping path as per the device compiler.

  2. 2.

For the swapping path that involves the EJPP protocol, eliminate the
depolarizing channel on the auxiliary qubits and introduce depolarizing
channels with an error parameter $(P_{a}P_{a^{\prime}})^{\frac{1}{3}}$ on both
sides of the working qubit, where $P_{a}$ and $P_{a^{\prime}}$ represent the
error parameters of the auxiliary qubits.

  3. 3.

Put all the depolarizing channels at the end of the swapping path.

  4. 4.

The resulting cost matrix is an $N+M$ by $N+M$ matrix, where the component
$C_{n,m}(q,q^{\prime})$ denotes the number of the depolarizing channel with an
error perimeter $P_{m}$ acting on the qubit $n$, Fractions are permissible in
the case of non-local gates.

To illustrate, we provide two examples of computing the cost matrix for a
given swapping path. Figure 15 outlines the process for calculating the cost
matrix for a local gate, with the corresponding cost matrix described by Eq.
(57) and Fig. 16 outlines the process for calculating the cost matrix for a
non-local gate, with the corresponding cost matrix described by Eq. (57). Note
that, it is obvious that, the cost matrix is zero when $q=q^{\prime}$.

Figure 15: Figure in the upper panel illustrates a swapping path from qubit 1
to qubit 4, as provided by the compiler, and figure in the lower panel depicts
the consolidation of all depolarizing channels at the end of the swapping
path. By counting the depolarizing channels on each qubit labeled with
different error parameters, we determine the cost matrix $C(1,4)$, as
described by Eq. (57).

$\displaystyle C(1,4)=\begin{bmatrix}1&2&2&0&0\\\ 1&1&0&0&0\\\ 0&1&1&0&0\\\
0&0&0&1&0\\\ 0&0&0&0&0\end{bmatrix}$ (57)

Figure 16: The figure in the top panel illustrates a swapping path from qubit
1 to qubit 3 involving EJPP protocol, the figure in the middle panel
demonstrates the error shifting process from auxiliary qubits to working
qubits, and the figure in the bottom panel depicts the consolidation of all
depolarizing channels at the end of the swapping path. Through this process,
we derive the cost matrix $C(1,3)$, as described by Eq. (58)

$\displaystyle C(1,3)=\begin{bmatrix}\frac{1}{3}&\frac{1}{3}&1&2&0\\\
0&0&1&1&0\\\ \frac{1}{3}&\frac{1}{3}&0&0&1\end{bmatrix}$ (58)

We define the allocation matrix $A$ as the average of the cost matrix of all
possible gates:

$\displaystyle A\equiv\frac{1}{2(N-1)}\sum_{q,q^{\prime}\in
Q_{w}}C(q,q^{\prime})$ (59)

The connectivity of the devices and the allocation algorithm of the compiler
are encapsulated within the allocation matrix $A_{q,q^{\prime}}$.

##  Appendix C Error shifting in the EJPP protocol

When considering the depolarizing channel acting on the auxiliary qubits, one
can first shift it to the beginning of the circuit, resulting in the entangled
state:

$\displaystyle\rho_{\Phi^{+}}(F_{e})=F_{e}|\Phi^{+}\rangle\langle\Phi^{+}|+\frac{1-F_{e}}{4}\mathbb{I}_{4}$
(60)

where the $F_{e}=P_{a}P_{a}^{\prime}$, Consequently, the channel of the EJPP
protocol circuit can be treated as a convex combination with a perfect part
($|\Phi^{+}\rangle\langle\Phi^{+}|$) and a completely mixed part
($\frac{1}{4}\mathbb{I}_{4}$). The perfect part yields the desired CONT gate,
while the channel of the completely mixed part is given by:

$\displaystyle\widetilde{CX}=(\frac{1}{2}\hat{\sigma}_{0}+\frac{1}{2}\hat{\sigma}_{3})\otimes(\frac{1}{2}\hat{\sigma}_{0}+\frac{1}{2}\hat{\sigma}_{1})$
(61)

Where $\\{\sigma_{i}\\}_{i}$ is the set of the Pauli operators. With the
consideration of the KAK decomposition, if one commutes the channel of the
completely mixed part with the local unitary gates, the $\hat{\sigma}_{0}$
remains unchanged, but the $\hat{\sigma}_{n}$ ($n=1$ or $3$) changes
direction, becoming a linear combination of the Pauli operator, i.e.,
$u{\sigma}_{i}u^{\dagger}=\vec{n}\cdot\vec{\sigma}$. Consequently, after
averaging the possible unitaries, we obtain:

$\displaystyle\widetilde{\sigma}_{avg}$
$\displaystyle=\int_{U}du\;\hat{u}\circ\hat{\sigma}_{i}\circ\hat{u}^{\dagger}=\int_{|n|^{2}=1}dn\;\vec{n}\cdot\vec{\sigma}\otimes\vec{n}\cdot\vec{\sigma}^{*}$
$\displaystyle=\frac{1}{3}\sum_{i=1}^{3}\hat{\sigma}_{i}$ (62)
$\displaystyle\widetilde{CX}_{avg}$
$\displaystyle=\iint_{U_{a},U_{b}}du_{a}du_{b}\;(\hat{u}_{a}\otimes\hat{u}_{b})\circ\widetilde{CX}\circ(\hat{u}_{a}^{\dagger}\otimes\hat{u}_{b}^{\dagger})$
$\displaystyle=(\frac{1}{3}\hat{\sigma}_{0}+\frac{2}{3}(\frac{\sum_{i=0}^{3}\hat{\sigma}_{i}}{4}))^{\otimes
2}$
$\displaystyle=(\frac{1}{3}\hat{\sigma}_{0}+\frac{2}{3}\widetilde{D}(0))^{\otimes
2}$ (63)

Here we used a relation that
$\widetilde{D}_{P}^{(1)}=P\hat{\sigma}_{0}+\frac{(1-P)}{4}\sum_{i=0}^{3}\hat{\sigma}_{i}$.
Therefore, the total error channels should be equal to:

$\displaystyle\widetilde{\Lambda}(F)$
$\displaystyle=F\hat{\sigma}_{0}^{\otimes
2}+(1-F)(\frac{1}{3}\hat{\sigma}_{0}+\frac{2}{3}\widetilde{D}(0))^{\otimes 2}$
(64)

Then by imposing the condition of making the error separable, one gets the
separable noise channel:

$\displaystyle\widetilde{\Lambda}(F)$
$\displaystyle\approx((\sqrt{F}+\frac{1-\sqrt{F}}{3})\hat{\sigma}_{0}+\frac{2(1-\sqrt{F})}{3}\widetilde{D}(0))^{\otimes
2}$ $\displaystyle=\widetilde{D}(\frac{1+2\sqrt{F}}{3})^{\otimes 2}$ (65)

By definition $F=P_{1}P_{2}=(1-\epsilon_{1})(1-\epsilon_{2})$. Since we are
dealing with nearly perfect cases ($\epsilon_{1,2}\ll 1\%$), we can simplify
this to:

$\displaystyle\sqrt{F}=$
$\displaystyle\sqrt{(1-\epsilon_{1})(1-\epsilon_{2})}\approx(1-\frac{\epsilon_{1}}{2})(1-\frac{\epsilon_{1}}{2})$
(66) $\displaystyle\frac{1+2\sqrt{F}}{3}$ $\displaystyle\approx
1-\frac{\epsilon_{1}}{3}-\frac{\epsilon_{2}}{3}\approx(1-\epsilon_{1})^{\frac{1}{3}}(1-\epsilon_{2})^{\frac{1}{3}}$
$\displaystyle=P_{1}^{\frac{1}{3}}P_{2}^{\frac{1}{3}}$ (67)

Here we calculate the error for a single EJPP protocol circuit, and for a
SU(4) gate, three EJPP protocol circuits are required. However, in our earlier
discussion, we included one depolarizing channel after each two-qubit gate.
Moreover, in our implementation of the local SU(4) gate, we still need to
decompose it with three CNOT gates. Therefore, we have already taken into
account the effect of the three EJPP protocol circuits.

Furthermore, to account for the imperfections in the pre-shared entanglement
pairs, one can set the input entangled state as given in Eq. (60) with a
parameter $F$. Similarly, this error can be transferred to the working qubit
by introducing depolarizing channels with an error parameter
$F^{\frac{1}{3}}$, on each side. Regarding the allocation matrix, an
additional column is required to represent the error cost caused by the non-
perfect entanglement pairs.

##  Appendix D Approximation of average gate fidelity

(a) Single-QPU devices with size = 6 (b) Two-QPU DQC devices with size = 6

(c) Single-QPU devices with size = 8 (d) Two-QPU DQC devices with size = 8

(e) Single-QPU devices with size = 10 (f) Two-QPU DQC devices with size = 10

Figure 17: The green curves stand for the original function, and the blue
curves stand for the function under approximation. For size 6, although the
size is not large, still we had a good match and the high-fidelity region
($\bar{F}\gtrapprox 0.6$). For the larger size, the approximation gets closer
to the original formula.

According to Eq. (39), for a small error $\epsilon_{q^{\prime}}$, the
effective preserving factor is approximately given by

$\displaystyle\bar{P}_{q}$
$\displaystyle=\prod_{q^{\prime}\in\mathbb{Q}}(1-\epsilon_{q^{\prime}})^{A_{q,q^{\prime}}}\approx
1-\sum_{q^{\prime}\in\mathbb{Q}}A_{q,q^{\prime}}\epsilon_{q^{\prime}}.$ (68)

The average error rate $\epsilon$ is determined as

$\braket{\epsilon}=\frac{1}{N}\sum_{q\in\mathbb{Q}_{w}}(1-\bar{P}_{q})=\frac{1}{N}\sum_{q,q^{\prime}\in\mathbf{Q_{w}},\mathbb{Q}}A_{q,q^{\prime}}\epsilon_{q^{\prime}}.$
(69)

The average gate fidelity is then

$\bar{F}\approx\prod_{q\in\mathbf{Q_{w}}}1-\frac{N}{2}\braket{\epsilon}\approx\exp(-\frac{N^{2}}{2}\braket{\epsilon}).$
(70)

This leads to

$\bar{F}=\exp(-\frac{N}{2}\sum_{q,q^{\prime}\in\mathbf{Q_{w}},\mathbb{Q}}A_{q,q^{\prime}}\epsilon_{q^{\prime}}).$
(71)

By further assuming that the error rate for each qubit as the same value
$\epsilon$, we get a simple formula with a characteristic value
$\mathcal{A}_{\mathbb{Q}}\equiv\sum_{q,q^{\prime}\in\mathbb{Q}_{w},\mathbb{Q}}A_{q,q^{\prime}}$
for a given QPU. In the end, the average gate fidelity is approximately given
by

$\displaystyle\bar{F}_{\mathbb{Q}}(\epsilon)$
$\displaystyle\approx\exp(-\frac{N\mathcal{A}_{\mathbb{Q}}}{2}\epsilon).$ (72)

##  Appendix E Extension of fidelity estimation theory for imperfect
entanglement

To incorporate the entanglement noises, one extend the construction of cost
matrices by introducing single-qubit depolarizing channel $D_{P_{E}}$ after
the entangled state on $\\{m_{a},m_{b}\\}$, as shown in Fig. 18 (a). The
effective preserving factor on $m_{a}$ and $m_{b}$ is then $p_{E}p_{a}$ and
$p_{E}p_{b}$, respectively. Employing the same method derived in Appendix B,
the depolarizing channel $D_{P_{E}}$ is then shifted to the end of particular
outputs in Fig. 18 (b). The cost matrix of the example is then extended by
adding an additional column associated with the depolarizing channels
originate from the entanglement pairs, which is given by

$C(q_{1},q_{3})=\begin{bmatrix}1&2&0&0&\frac{1}{3}&\frac{1}{3}&\frac{1}{3}\\\
1&1&0&0&0&0&0\\\ 0&0&1&0&\frac{1}{3}&\frac{1}{3}&\frac{1}{3}\\\
0&0&0&0&0&0&0\end{bmatrix}.$ (73)

Figure 18: Cost matrix with entanglement noise. The red circles are the
depolarizing noises of the entangled pair.

## References

  * [1] M. Caleffi, M. Amoretti, D. Ferrari, D. Cuomo, J. Illiano, A. Manzalini, and A. S. Cacciapuoti.  Distributed quantum computing: a survey, 2022.
  * [2] D. Barral, F. J. Cardama, G. Díaz, D. Faílde, I. F. Llovo, M. M. Juane, J. Vázquez-Pérez, J. Villasuso, C. Piñeiro, N. Costas, J. C. Pichel, T. F. Pena, and A. Gómez.  Review of distributed quantum computing. from single qpu to high performance quantum computing, 2024.
  * [3] T. Peng, A. W. Harrow, M. Ozols, and X. Wu.  Simulating large quantum circuits on a small quantum computer.  Phys. Rev. Lett., 125:150504, 2020.
  * [4] K. Mitarai and K. Fujii.  Overhead for simulating a non-local channel with local channels by quasiprobability sampling.  Quantum, 5:388, 2021.
  * [5] K. Mitarai and K. Fujii.  Constructing a virtual two-qubit gate by sampling single-qubit operations.  23(2):023021.
  * [6] C. Piveteau, D. Sutter, and S. Woerner.  Quasiprobability decompositions with reduced sampling overhead.  8(1).
  * [7] C. Piveteau and D. Sutter.  Circuit knitting with classical communication.  IEEE Transactions on Information Theory, 70(4):2734 – 2745, 2024\.
  * [8] D. Gottesman and I. L. Chuang.  Demonstrating the viability of universal quantum computation using teleportation and single-qubit operations.  Nature, 402:390–393, 1999.
  * [9] J. Eisert, K. Jacobs, P. Papadopoulos, and M. B. Plenio.  Optimal local implementation of nonlocal quantum gates.  Physical Review A, 62:052317, 2000.
  * [10] S. F. Huelga, J. A. Vaccaro, A. Chefles, and M. B. Plenio.  Quantum remote control: Teleportation of unitary operations.  Physical Review A, 63:042303, 2001.
  * [11] S. F. Huelga, M. B. Plenio, and J. A. Vaccaro.  Remote control of restricted sets of operations: Teleportation of angles.  Physical Review A, 65:042316, 2002.
  * [12] L. Jiang, J. M. Taylor, A. S. Sørensen, and M. D. Lukin.  Distributed quantum computation based on small quantum registers.  Physical Review A, 76:062323, 2007.
  * [13] R. V. Meter, W. Munro, K. Nemoto, and K. M. Itoh.  Arithmetic on a distributed-memory quantum multicomputer.  ACM Journal on Emerging Technologies in Computing Systems (JETC), 3(4):1–23, 2008.
  * [14] R. G. Sundaram, H. Gupta, and C. R. Ramakrishnan.  Efficient Distribution of Quantum Circuits.  In 35th International Symposium on Distributed Computing (DISC 2021), volume 209 of Leibniz International Proceedings in Informatics (LIPIcs), pages 41:1–41:20, Dagstuhl, Germany, 2021.
  * [15] J.-Y. Wu, K. Matsui, T. Forrer, A. Soeda, P. Andrés-Martínez, D. Mills, L. Henaut, and M. Murao.  Entanglement-efficient bipartite-distributed quantum computing.  Quantum, 7:1196, 2023.
  * [16] P. Andres-Martinez, T. Forrer, D. Mills, J.-Y. Wu, L. Henaut, K. Yamamoto, M. Murao, and R. Duncan.  Distributing circuits over heterogeneous, modular quantum computing network architectures.  arXiv:2305.14148.
  * [17] K. Życzkowski and H.-J. Sommers.  Average fidelity between random quantum states.  Physical Review A, 71:032313, 2005.
  * [18] A. W. Cross, L. S. Bishop, S. Sheldon, P. D. Nation, and J. M. Gambetta.  Validating quantum computers using randomized model circuits.  Physical Review A, 100:032328, 2019.
  * [19] F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S. Humble, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, J. Kelly, P. V. Klimov, S. Knysh, A. Korotkov, F. Kostritsa, D. Landhuis, M. Lindmark, E. Lucero, D. Lyakh, S. Mandrà, J. R. McClean, M. McEwen, A. Megrant, X. Mi, K. Michielsen, M. Mohseni, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Y. Niu, E. Ostby, A. Petukhov, J. C. Platt, C. Quintana, E. G. Rieffel, P. Roushan, N. C. Rubin, D. Sank, K. J. Satzinger, V. Smelyanskiy, K. J. Sung, M. D. Trevithick, A. Vainsencher, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, and J. M. Martinis.  Quantum supremacy using a programmable superconducting processor.  Nature, 574(7779):505–510, 2019.
  * [20] S. Aaronson and L. Chen.  Complexity-theoretic foundations of quantum supremacy experiments.  In Proceedings of the 32nd Computational Complexity Conference, CCC ’17, Dagstuhl, DEU, 2017. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
  * [21] M. A. Nielsen.  A simple formula for the average gate fidelity of a quantum dynamical operation.  303(4):249–252.
  * [22] C. H. Bennett, G. Brassard, C. Crépeau, R. Jozsa, A. Peres, and W. K. Wootters.  Teleporting an unknown quantum state via dual classical and einstein-podolsky-rosen channels.  Physical Review Letters, 70:1895–1899, 1993.
  * [23] A. A. Mele.  Introduction to Haar Measure Tools in Quantum Information: A Beginner’s Tutorial.
  * [24] G. M. D’Ariano, G. Chiribella, and P. Perinotti.  Quantum Theory from First Principles: An Informational Approach.  Cambridge University Press, 2017.
  * [25] Y. Mao, Y. Liu, and Y. Yang.  Qubit allocation for distributed quantum computing.  In IEEE INFOCOM 2023 - IEEE Conference on Computer Communications. IEEE.
  * [26] R. Kukulski, I. Nechita, u. Pawela, Z. Puchała, and K. Życzkowski.  Generating random quantum channels.  62(6):062201.