# Variational Quantum Circuit Decoupling

Ximing Wang<EMAIL_ADDRESS>Nanyang Quantum Hub, School of Physical
and Mathematical Sciences, Nanyang Technological University, Singapore
Chengran Yang<EMAIL_ADDRESS>Centre for Quantum Technologies,
National University of Singapore, Singapore  Mile Gu
<EMAIL_ADDRESS>Nanyang Quantum Hub, School of Physical and
Mathematical Sciences, Nanyang Technological University, Singapore  Centre for
Quantum Technologies, National University of Singapore, Singapore  MajuLab,
CNRS-UNS-NUS-NTU International Joint Research Unit, UMI 3654, Singapore
117543, Singapore

###### Abstract

Decoupling systems into independently evolving components has a long history
of simplifying seemingly complex systems. They enable a better understanding
of the underlying dynamics and causal structures while providing more
efficient means to simulate such processes on a computer. Here we outline a
variational decoupling algorithm for decoupling unitary quantum dynamics –
allowing us to decompose a given $n$-qubit unitary gate into multiple
independently evolving sub-components. We apply this approach to quantum
circuit synthesis - the task of discovering quantum circuit implementations of
target unitary dynamics. Our numerical studies illustrate significant
benefits, showing that variational decoupling enables us to synthesize general
$2$ and $4$-qubit gates to fidelity that conventional variational circuits
cannot reach.

When studying a system of coupled harmonic oscillators, a key approach is to
decouple its dynamics into various normal modes. We can then study each mode
individually, enabling a deeper understanding of underlying dynamics. In the
era of computer simulation, this divide-and-conquer approach has further
operational importance, enabling leverage of parallel processing, and reducing
the computational costs of simulation or optimization [1, 2]. Decoupling
complex systems into simpler components has seen success in diverse settings,
from modeling the motion of human hands to hydraulic simulation [3, 4].

Figure 1: Variational Quantum Circuit Decoupling. Given a target complex
unitary quantum operation $U$, the decoupling of $U$ involves identifying
shallow pre and post-processing operation $V_{0}$ and $V_{1}$, such that
$U\approx V_{1}(U_{A}\otimes U_{B})V_{0}$, for some operators $U_{A}$ and
$U_{B}$ act locally on subsystems $A$ and $B$ respectively. This procedure can
be repeated recursively, breaking down $U_{A}$ and $U_{B}$ into smaller
components, until all subsystems are sufficiently small. Take a $4$-qubit
system for example, the target unitary operator $U$ is first decomposed by
$V_{0}$ and $V_{1}$ into local operators on subsystems $A,B$, and the local
operator $U_{A}$ ($U_{B}$) is further decomposed by $V_{A,0}$ and $V_{A,1}$
($V_{B,0}$ and $V_{B,1}$) into single qubit unitary operators.

_Can decoupling also help us in the discovery of simpler quantum circuits_?
Quantum computing promises immense computational benefits - from solving
classically intractable problems to efficiently simulating quantum
interactions. Yet, such tasks typically require the synthesis of complex
$n$-qubit unitary operations using elementary quantum gates. While systematic
decomposition techniques exist, all such generic solutions require gate counts
that scale exponentially with $n$. To reduce such intractable realizations
into a shallow circuit - even when possible - remains a highly intractable
(NP-Complete) task [5, 6]. Thus, quantum circuit compilation - the capacity to
design a simpler circuit for implementing a given unitary process - is a
pressing task; motivated by recent variation algorithms for quantum circuit
discovery [7, 8].

Here, we proposed variation circuit decoupling - a divide-and-conquer approach
that enhances such existing variational circuit algorithms [7, 8]. The
procedure involves designing a variational decoupling algorithm that first
breaks a many-qubit interaction into smaller components (see figure 1). We can
then optimize these smaller components individually or break them down further
via recursive applications of variational decoupling. We demonstrate the
method for compiling circuits approximating arbitrary two and four-qubit
gates, where it identifies circuits of much higher fidelities than direct
variational methods.

Framework – Here, we adopt the premise of variational quantum circuit
discovery, where we are given black-box access to some unknown $n$-qubit
unitary quantum process $U$ [7, 8]. This could represent a complex quantum
circuit we wish to simplify; some unknown quantum device we wish to reverse-
engineer, or some natural quantum process we wish to simulate. Our goal is to
approximate this process with a sequence of elementary quantum gates - subject
perhaps to constraints on circuit complexity or depth.

Systematic solutions to this problem are clearly intractable. Process
tomography to determine the matrix elements of $U$ alone would scale
exponentially with $n$, as would any general method of decomposing $U$ into
elementary gates. Quantum-aided variational approaches aid in accelerating the
process by use of quantum computers themselves [7, 8]. They typically involve
two components: (a) An ansatz, a family of quantum circuits
$W({\bf\it\theta})$ parameterized by some $k$-dimensional vector
${\bf\it\theta}=(\theta_{0},\dots,\theta_{k-1})$, and (b) A cost function $C$
that that measures the performance loss of each candidate circuit in
approximating $W$. The goal is to identify the parameter set ${\bf\it\theta}$
so that the corresponding circuit $W({\bf\it\theta})$ has a minimal cost.
${\bf\it\theta}$ corresponds to easily adjustable parameters of some proposed
circuit architectures (e.g. magnitude of rotations on various single-qubit
gates), such that knowledge of ${\bf\it\theta}$ allows the physical synthesis
of the associated quantum circuit $W({\bf\it\theta})$. Meanwhile, the cost
function is generally chosen to be normalised (takes a maximum value of $1$)
with the following properties:

  * •

Measurable and Gradient Measurable, such that $C(W)$ and each partial
derivative $\partialderivative{\theta_{i}}C$ can be efficiently estimated.
i.e., they each can be determined to target precision $\varepsilon$ using at
most $\text{poly}(n,1/\varepsilon)$ calls to $W$ and classical computing costs
that scale efficiently with $n$.

  * •

Faithful, such that $C$ is non-negative, and $C(W)=0$ if and only if no
general $n$-qubit quantum circuit are preferred over $W$.

For example, $1-\bar{F}(\hat{U},U)$ is a natural candidate for the cost
function [7], where $\bar{F}(\hat{U},U)$ is the gate fidelity of the
synthesize unitary $\hat{U}$ with respect to the target unitary $U$. This then
allows gradient descent-based methods to find ${\bf\it\theta}$ within the
parameterized circuit to minimize the cost (e.g. Adam [9]). However, the rate
at which variational circuits converge can become severely limited due to
barren plateaus - especially in scenarios where circuits being optimized over
had no constraints [10, 11, 12].

Variational Decoupling – We adopt a divide-and-conquer approach. Instead of
attempting to learn a circuit decomposition for the entirety of $U$, we break
the circuit down into a series of smaller circuits as illustrated in figure 1.
Specifically we first divide $n$-qubit system into two subsystems $A$ and $B$
of approximately equal size (i.e., of size $\lfloor n/2\rfloor$ and $\lceil
n/2\rceil$). We then identify pre-processing unitary $V_{0}$ and post-
processing unitary $V_{1}$ such that $V_{1}^{\dagger}UV_{0}^{\dagger}$ is most
closely approximated by local unitary evolution on $A$ and $B$. That is,
identify $V_{0}$ and $V_{1}$ such that there exists $U_{A}$ on $A$ and $U_{B}$
on $B$ in which $V_{1}^{\dagger}UV_{0}^{\dagger}$ most closely approximates
$U_{A}\otimes U_{B}$.

We document below a variational means to learn gate decomposition for $V_{0}$
and $V_{1}$ without needing any knowledge of unitary operators $U_{A}$ and
$U_{B}$. After which, we may repeat the decoupling method on each of the
localized unitary gates, breaking each of them down into two smaller gates on
$\approx n/4$ qubits. This can proceed until all localized operators are
sufficiently small for conventional variational methods (e.g. a single qubit).
Finally, various sub-problems are recombined to give a full circuit
decomposition of $U$.

The key behind the variational decoupling algorithm is to find an appropriate
cost function. First, let $V_{0}({\bf\it\theta}_{0})$ and
$V_{1}({\bf\it\theta}_{1})$ be the parametrizations of the circuits $V_{0}$
and $V_{1}$ with respective parameters ${\bf\it\theta}_{1}$ and
${\bf\it\theta}_{2}$. Meanwhile set $W=V_{1}^{\dagger}UV_{0}^{\dagger}$ as the
resulting quantum process formed by pre and postprocessing of $U$. Since we
can always engineer $W$ given $U$, $V_{0}$, and $V_{1}$, we can define our
cost function concerning $W$ alone for convenience. Here we desire a
normalized cost function that (i) is faithful, such that $C(W)=0$ when
$U=V_{1}UV_{0}^{{\dagger}}=U_{A}\otimes U_{B}$ or $(U_{A}\otimes U_{B})S$, and
(ii) exhibits both self and gradient measurability. Here we propose the cost
function as the decoupling cost $C_{D}$ defined as

$\displaystyle C_{D}(W)$ $\displaystyle=\iint
D[W(\outerproduct{\psi}{\psi}_{A}\otimes\outerproduct{\phi}{\phi}_{B})W^{\dagger}]\differential\ket{\psi}\differential\ket{\phi},$
(1)

where
$D(\rho_{A,B})=\frac{4^{m}}{(4^{m}-1)}\frac{L(\rho_{A})+L(\rho_{B})}{2}$,
$L(\rho)=1-\Tr[\rho^{2}]$ is the linear entropy and the integration is take
over Haar random initial states $\ket{\psi}_{A}$ on $A$ and $\ket{\Phi}_{B}$
on $B$. Here $m$ is either the number of qubits in $A$ or $B$, whichever is
smaller. The normalization factor $\frac{4^{m}}{4^{m}-1}$ is chosen such that
$D(\rho_{A,B})$ ranges from $0$ to $1$ for all pure state $\rho_{A,B}$. We now
illustrate the following:

######  Theorem 1.

The decoupling cost $C_{D}$ is efficiently measurable, efficiently
differentiable, and faithful.

We illustrate in figure 2 (c) that $C_{D}$ is _efficiently measurable_.
Specifically, the circuit involves $2n$ qubits, a constant-depth overhead from
implementing $V_{1}^{\dagger}UV_{0}^{\dagger}$ Note that while $C_{D}$ is
defined using Haar random initial states, measurement of $C_{D}$ requires only
preparation of random states in the computational basis (see supplementary
material  _Measurements and State Preparation_ for proof).

We establish the _efficiently differentiability_ of $C_{D}$ by generalising
the parameter-shift rule – a noise-resilient, hardware efficient method, and
provides exact gradients through quantum measurement [13, 14]. As the
parameterized circuit $W$ appears twice in evaluating the decoupling cost
$C_{D}$, so does each parameterized gate in $W$, the conventional parameter-
shift rule cannot be applied directly. A parameter-shift rule addressing
multiple occurrences of parameters needs to be considered [15, 16]. We use
$W_{\alpha}$ and $W_{\beta}$ to specify each of the two copies of $W$ used to
evaluate $C_{D}(W)=C_{D}(W_{\alpha},W_{\beta})$ as in figure 2. Given the
ansatzes whose parameterized gates are only Pauli rotations, we show that the
gradient $\partialderivative{\theta_{i}}C_{D}$ for each $\theta_{i}$ in
${\bf\it\theta}$ can be written down as

$\displaystyle\partialderivative{\theta_{i}}C_{D}=$
$\displaystyle\frac{1}{2}C_{D}(W_{\alpha}^{+},W_{\beta})-\frac{1}{2}C_{D}(W_{\alpha}^{-},W_{\beta})$
(2)
$\displaystyle+\frac{1}{2}C_{D}(W_{\alpha},W_{\beta}^{+})-\frac{1}{2}C_{D}(W_{\alpha},W_{\beta}^{-})\
.$

where $W^{+}_{i}$ and $W^{-}_{i}$ are the ansatz with the parameter
$\theta_{i}$ in $W({\bf\it\theta})$ updated to $\theta_{i}+\frac{\pi}{2}$ and
$\theta_{i}-\frac{\pi}{2}$ respectively (see supplementary materials Sec.
III). Each term in (2) can then be directly evaluated by the circuit in figure
2, leading to the efficient measurement of the gradient.

To establish _faithfulness_ , first observe that the linear entropy is used to
quantify the entanglement between two subsystems [17]. In particular, the non-
negativity of the linear entropy guarantees the non-negativity of the
decoupling cost $C_{D}$. Meanwhile, $D(W(\rho_{A}\otimes\rho_{B})W^{\dagger})$
quantifies the entanglement $W$ generates between $A$ and $B$ when applied to
a product state $\rho_{AB}=\rho_{A}\otimes\rho_{B}$. Consequently, our cost
function $C_{D}$ represents the expected entanglement generated by $W$ when
averaged across all pure product inputs $\ket{\psi}_{A}\otimes\ket{\phi}_{B}$.
As such, $C_{D}(W)=0$ if and only if the operator $W$ is equivalent to the
identity or the swap gate up to local unitary gates. In addition, in the
supplementary material Sec.IV, we prove that $C_{D}$ constrains the ultimate
gate fidelity we can achieve after decoupling:

######  Theorem 2.

For a given $n$-qubit unitary operator $W$, the gate fidelity
$\bar{F}(U_{A}\otimes U_{B},W)$ for all $U_{A}$ and $U_{B}$ is bounded by the
decoupling cost $C_{D}$, such that

$\bar{F}_{\max}^{2}\leq\mathrm{min}(1-C_{D}+\frac{3}{2^{n}+1},1)\ .$ (3)

We can then proceed with variational decoupling by choosing appropriate
ansatzes for $V_{0}({\bf\it\theta}_{0})$ and $V_{1}({\bf\it\theta}_{1})$; such
that $W$ is parameterized by the joint vector
${\bf\it\theta}^{*}:={\bf\it\theta}_{0}^{*}\oplus{\bf\it\theta}_{1}^{*}$. For
each candidate $V_{0}({\bf\it\theta}_{0})$ and $V_{1}({\bf\it\theta}_{1})$, we
can construct a realization of $W$, and use above methods to efficiently
measure $C_{D}$ and its various gradients, and thus employ gradient-descent-
based optimization method to find suitable $V_{0}$ and $V_{1}$ that decouples
$U$. Note that, just as in standard circuit compilation, we may also choose to
limit the gate depth of $V_{0}$ and $V_{1}$ should we wish for shallow circuit
approximations of $U$.

Figure 2: _The variational decoupling algorithm._ To decouple an $n$-qubit
circuit, our algorithm begins with two systems of $n/2$-qubits - denoted as
the upper and lower layer in (a), which we label $\alpha$ and $\beta$. Each
layer is further divided into the $2$ subsystems we wish to decouple,
resulting in the $4$ subsystems $\mathcal{H}_{A,\alpha}$,
$\mathcal{H}_{A,\beta}$ of dimensions $d_{A}$ and $\mathcal{H}_{B,\alpha}$,
$\mathcal{H}_{B,\beta}$ of dimensions $d_{B}$. We apply
$W=V_{1}^{\dagger}UV_{0}^{\dagger}$ to each of subsystem $\alpha$ and $\beta$.
The input state is initialized as $\tau_{A}\otimes\tau_{B}$, where
$\tau_{k}=\frac{2P_{s}^{(k)}}{d_{k}^{2}+d_{k}}$, and $P^{(k)}_{s}$ is the
projector to the symmetric subspace of
$\mathcal{H}_{k,\alpha}\otimes\mathcal{H}_{k,\beta}$ for $k\in\\{A,B\\}$. This
is done by first preparing each qubit in $\mathcal{H}_{k,\alpha}$ and
$\mathcal{H}_{k,\beta}$ in a random computational basis state, followed by
qubit-wise application of the Hadamard gate for each $\beta$-layer qubit. Each
qubit is then entangled with a corresponding qubit in $\mathcal{H}_{k,\alpha}$
via a CNOT gate (b). Meanwhile, we can efficiently measure cost function
$C_{D}$ and its gradient using a destructive swap test - which similarly
involves only qubit-wise CNOT and Hadamard gates, followed by projective
measurement (c). This information can then be used to tune $\theta_{0}$ and
$\theta_{1}$ using techniques from variational circuits (d).

Performance Comparisons – We demonstrate the improved efficacy of our
decoupling method in two distinct scenarios:

  * •

_The exact compilation of a general $2$-qubit gate_ \- where the ansatz is
shown figure 3. Here, the circuit family is universal, and can theoretically
synthesize any $2$-qubit unitary operator [18]. Our decoupling algorithm
breaks this into two stages. The first (coloured orange) decouples $U$ into
two single-qubit circuits. The second stage (red) then optimises these
circuits. Note that in this special case, we have set $V_{1}=I$, since this is
already sufficient for compiling an arbitrary $2$-qubit gate.

  * •

_A shallow circuit approximation of an arbitrary $4$-qubit gate_, where the
structure of the ansatz follows the figure 4. For both $V_{0}$ and $V_{1}$, we
utilize four layers of decoupling circuit, where each layer comprises a
shallow circuit and single qubit and control gates. The circuit compilation is
done via three stages. Stage one (orange) decouples the circuit into two
generic $2$-qubit gates, $V_{A}$ and $V_{B}$. The second stage (red) decouples
these 2-qubit gates further into $4$ single-qubit interactions. Finally, stage
$3$ then optimizes each of the four single-qubit gates.

In each setting, we select target $U$ at random according to the Haar measure.
The former scenario represents the case where we have a universal circuit
ansatz and which to exactly compile a unitary. The latter represents the
scenario where we wish to use a shallow circuit with limited expressivity to
approximate an arbitrary $4$-qubit gate.

We benchmark our method against standard variational approaches, where all
circuit parameters are optimized by gradient descent to maximize the gate
fidelity $\bar{F}$ simultaneously. In the standard approach, this optimization
is done by minimizing a cost function $C_{\mathrm{HST}}$ or the localized cost
function $C_{\mathrm{LHST}}$ [7]. Here
$C_{\mathrm{HST}}=\frac{d+1}{d}(1-\bar{F})$ and
$C_{\mathrm{LHST}}=\frac{1}{n}\sum_{i}C_{\mathrm{HST}}^{(i)}$ are faithful
measures who reaches $0$ when $\bar{F}$ approaches $1$. The
$C_{\mathrm{HST}}^{(i)}$ are the the cost function $C_{\mathrm{HST}}$
restricted to the $i$th qubit. For a fair comparison, all methods use the same
circuit parameterization and thus have identical expressivity and all are
trained using the ADAM [9] method with identical hyper-parameters 111The
$\alpha=0.01$, $\beta_{1}=0.8$, $\beta_{2}=0.9$.. The results are shown in
figure 3 (2-qubit) and figure 4 (4-qubit). In both cases, performance is
gauged by how $\bar{F}(U,\hat{U})$ improves, i.e., the fall of
$C_{\mathrm{HST}}$ with the number of training iterations. We see that:

  * •

In $2$-qubit gate decomposition, our decoupling approach converges a lot more
quickly. For example, it achieves a fidelity of $0.9999$ using the same amount
of time where conventional methods approach a fidelity of $0.999$

  * •

In shallow circuit approximation of general $4$-qubit gates, our decoupling
method reaches circuit fidelity around $0.7$, significantly ahead of
conventional methods which achieves a fidelity of around $0.5$. Note that high
fidelity values are not expected here as our ansatz - being shallow - has
limited expressivity. In supplementary materials V, we also include an
analysis of a third scenario where target $4$-qubit unitaries can be expressed
by our shallow circuit. There our decoupling method continues can reach a
circuit fidelity of $0.998$ vs $0.9$ in using conventional methods.

In all cases, conventional variational circuits exhibit steady gate fidelity
gain till some saturation point. Our decoupling method, on the other hand,
only minimizes $C_{\mathrm{LHST}}$ in the final stage. Previous stages
concentrate on decoupling the unitary and do not immediately improve gate
fidelity. However, once decoupled, convergence to a low $C_{\mathrm{HST}}$
occurs very quickly - more than compensating for the delayed start. Moreover,
the final fidelity obtained shows marked improvement for both exact gate
decomposition and shallow circuit approximation.

Figure 3: _Variational Compilation of a general 2-qubit unitary with ADAM
optimization._ The fidelity $\bar{F}$ is compared between the direct
compilation (purple for global cost functions and blue for local cost
functions) and our decoupling method (solid lines). For each method, the
training is repeated $20$ times with different initializations. Our method
divides the task into two steps, each represented by a different color. The
first phase (yellow) decouples the unitary to single-qubit unitary operators,
and the second phase (red) maximizes the fidelities. The phase transition
region is colored orange, where some of the processes are in phase one and the
rest are in phase two. The data of each method are divided into quartiles, and
the lines represent the median of each process. The second and third quartiles
are shaded with the corresponding color. The preprocessing ansatz is chosen to
be the universal two-qubit circuit [18], and the post-processing is set to
identity. We see that the average fidelity does not increase during the
decoupling stage, but greatly enhances training in the second stage by
breaking up the problem into more tractable components. The resulting compiled
circuits have significantly higher fidelity, such that $1-\bar{F}$ is reduced
by a factor of $3$ over the state of the art.  Figure 4: _Variational
Compilation of generic 4-qubit unitary with ADAM optimization._ Similar to the
2-qubit case, the data of each process is collected from $20$ independent
training processes, while the regions between the first and last quartiles are
shaded with the corresponding colors as in FIG 3. Here, the optimisation is
divided into three phases. The circuits are divided into 3 types: 4-qubit
ansatzes (orange), 2-qubit ansatzes (red), and the middle single qubit gates
(green). The layers are repeated for $4$ times for $V_{0},V_{1}$, and the
layers in the 2-qubit ansatzes $V_{A,0},V_{B,0},V_{A,1},V_{B,1}$ repeat twice.
The ansatzs are designed to explore stronger expressive power with a limited
number of gates, which can be generalized to any number of qubits [20]. In
this case, our ansatz – being low depth – is non-universal. Nevertheless, we
see that variation decoupling continues to achieve circuits of higher
fidelity.

Discussion – Here, we outline a variational means to decouple complex quantum
circuits. This is enabled by the proposal of an efficiently measurable cost
function $C_{D}$, that allows us to identify suitable pre- and post-processing
circuits to decouple a $2n$-qubit unitary to a tensor product of two $n$-qubit
unitary operators. Through the recursive application, we illustrated how
variational decoupling enhances existing approaches to circuit compilation – a
key task in the design of quantum circuits in both near-term of future
universal quantum computers. In benchmarks, variational decoupling enabled us
to compile circuits realization of arbitrary two and four-qubit quantum gates
to significantly higher fidelity. By setting the allowed depths of pre-
processing and post-processing circuits, our decoupling method can be adapted
to discovering circuits of varying expressivity, ranging from very shallow
circuits for NISQ devices to deep circuits that represent general unitary
operations.

There are many promising avenues for future research. One is to consider
hybrid digital-analog quantum computing paradigms [21], where pre or post-
processing blocks may include analog evolution that provides efficient means
to generating ansatz of increased expressivity. Meanwhile, the decoupling of
complex interactions has motivations beyond computational advantage. In
classical analogs such as coupled oscillators, identification of normal modes
helped better express underlying dynamics - and thus benefits intrinsic human
understanding. We anticipate a similar advantage in the quantum regime. One
could, for example, envision a seemingly complex many-body quantum system
evolving under some joint Hamiltonian $H$. By setting $V_{0}=V^{\dagger}_{1}$,
our methodologies could also help identify potential sub-spaces where there is
minimal coupling - and thus aid the discovery of underlying causal
restructure. Finally, the minimal mutual information between arbitrary
bipartitions of a many-body system is considered a fundamental measure of
indivisibility – and is remarkably a lot smaller for general quantum systems
due to the potential to decouple in an entangling basis [22]. It would
certainly be interesting to understand if this phenomenon indicates that
decoupling is particularly beneficial in the quantum regime.

###### Acknowledgements.

Acknowledgments — This work is supported by the National Research Foundation,
Singapore, and Agency for Science, Technology and Research (A*STAR) under its
QEP2.0 programme (NRF2021-QEP2-02-P06), the Singapore Ministry of Education
Tier 1 Grant RG77/22 (S) and the FQXi R-710-000-146-720 Grant “Are quantum
agents more energetically efficient at making predictions?” from the
Foundational Questions Institute and Fetzer Franklin Fund (a donor-advised
fund of the Silicon Valley Community Foundation).

Supplementary Material

##  Appendix A Preliminary - Quantum Channels

In the quantum theory, the states of a quantum system are described by the
density operators $\rho$ that act on a Hilbert space $\mathcal{H}$, such that
the operators $\rho$ are positive semidefinite and $\tr[\rho]=1$. A linear map
$\Gamma$ from a system $\mathcal{H}$ to system $\mathcal{Y}$ is called a
_quantum channel_ if it maps a density operator in $\mathcal{H}$ to a density
operator in $\mathcal{Y}$. Such property of the linear maps is usually broken
into two constraints: 1. the map is completely positive (CP), and 2. the map
is trace-preserving (TP). A map $\Gamma:\mathcal{H}\to\mathcal{Y}$ is CP if,
for all ancillary system $\mathcal{A}$, $\Gamma\otimes\mathbb{I}_{A}$ maps
positive semidefinite operators $\rho\in\mathcal{H}\otimes\mathcal{A}$ to
positive semidefinite operators $\Gamma\otimes\mathbb{I}_{A}(\rho)$. A map is
TP if it preserves the trace of operators, such that
$\tr[\Gamma(\rho)]=\tr[\rho]$ for all operators defined on $\mathcal{H}$. For
convenience, we usually investigate these two constraints with the matrix
representations of the linear maps. Choi-Jamiolkowski operator [23, 24] is one
of the most commonly used representations of quantum channels. For each
quantum channel $\Gamma$, its Choi-Jamiolkowski operator $J^{\Gamma}$ is
unique.

######  Definition A.1.

The Choi-Jamiolkowski operator $J^{\Gamma}$ of a linear map
$\Gamma:\mathcal{H}\to\mathcal{Y}$ is defined as

$J^{\Gamma}=\left(\Gamma\otimes\mathbb{I}_{S}\right)\outerproduct{\Psi^{+}}{\Psi^{+}}\
,$ (4)

where
$\ket{\Psi^{+}}=\sum_{i}\ket{i}_{\mathcal{H}}\ket{i}_{\mathcal{H}^{\prime}}$,
$\mathcal{H}^{\prime}$ is a copy of $\mathcal{H}$, and $\ket{i}$ forms a basis
of $\mathcal{H}$.

The properties of CP and TP can be characterized easily with Choi-Jamilkowski
operators [24]:

######  Theorem 3.

A linear map $\Gamma$ is a quantum channel if and only if $J^{\Gamma}$ is
positive semidefinite (CP), and
$\tr_{\mathcal{Y}}[J^{\Gamma}]=\mathbb{I}_{\mathcal{H}}$ (TP).

Choi-Jamiolkowski operator also provides a convenient way to represent the
input states and the measurements on the outputs of the quantum channels [25,
26]:

######  Theorem 4.

Given quantum state $\rho$ defined on $\mathcal{H}$, an observable $O$ defined
on $\mathcal{Y}$, and a quantum channel $\Gamma:\mathcal{H}\to\mathcal{Y}$,
the expectation value of $O$ with respect to $\Gamma(\rho)$ is given by

$\tr[\Gamma(\rho)O]=\tr[(\rho\otimes O)^{\mathsf{T}}J^{\Gamma}]\ .$ (5)

In the scope of this paper, we will focus on the endomorphisms of a system
$\mathcal{H}$, which are those linear maps $\Gamma:\mathcal{H}\to\mathcal{H}$
whose output system is identical to the input system. More specifically, we
will focus on the quantum channels that are induced by unitary operators,
namely unitary channels. Let $\mathcal{U}$ denote the unitary channel with
respect to a unitary operator $U$ acts on $\mathcal{H}$, such that
$\mathcal{U}(\cdot)=U(\cdot)U^{\dagger}$. Then the Choi-Jamiolkowski operator
of $\mathcal{U}$ is given by

$J^{\mathcal{U}}=\quantity(U\otimes\mathbb{I}_{\mathcal{H}})\outerproduct{\Psi^{+}}{\Psi^{+}}\quantity(U^{\dagger}\otimes\mathbb{I}_{\mathcal{H}})\
,$ (6)

which is a rank-one projector. For a given unitary $U$, there is an unique
$\ket{\psi}$ (up to a global phase), such that
$J^{\mathcal{U}}=\outerproduct{\psi}{\psi}$. In the special case that
$U=\mathbb{I}$, the state is the unnormalized maximally entangled state
$\ket{\Psi^{+}}$. According to the TP property of quantum channels,
$\outerproduct{\psi}{\psi}=\tr[J^{\mathcal{U}}]=\tr[\mathbb{I}_{\mathcal{H}}]=d$,
where $d$ is the dimension of $\mathcal{H}$.

##  Appendix B Measurements and State Preparation

It is known that the purity, $\Tr[\rho^{2}]$, of a state $\rho$ can be
measured with swap test efficiently [27]. With the ability to perform a
controlled swap between two copies of $\rho$, the value of $\Tr[\rho^{2}]$ is
proportional to the probability of measuring $0$ in the circuit of figure 5.

$\ket{0}$ & H 2 H
$\rho$ [swap]
$\rho$

Figure 5: Conventional swap test.

$\rho$ & z_1
$\rho$ -1 H z_2

Figure 6: Destructive swap test

Alternatively, the measurement of purity can be done with pair-wise Bell
measurements instead of the controlled swap test [28, 29]. This is done by a
bit-wise bell measurement on a pair of systems as shown in figure 6, which are
called _destructive swap test_. For large quantum systems, the destructive
swap test is more practical than the conventional swap test. In the
conventional scheme, the control qubit must maintain a strong quantum
correlation with all qubits that are been swapped. However, in the destructive
swap test, each pair of qubits is measured separately, and the computation of
purity only requires classical correlations between the measurement outcomes.
In summary,

######  Theorem 5.

The purity of a state $\rho$ can be measured as an observable $S$, where
$\Tr[\rho^{2}]=\Tr[\rho\otimes\rho S]$, such that the evaluation can be
measured with a constant depth quantum circuit and a linear time classical
post-processing.

###### Proof.

The proof starts from the single-qubit case, where $\rho$ acts on
$\mathbb{C}^{2}$. Let
$\ket{\Psi^{+}}:=\frac{1}{\sqrt{2}}\quantity(\ket{00}+\ket{11})$, the
projective measurement in circuit 6 is given by the projectors that project to

$\ket{\Psi_{z_{1},z_{2}}}:=\sigma_{X}^{z_{1}}\otimes\sigma_{Z}^{z_{2}}\ket{\Psi^{+}}\
,$ (7)

where $a$ and $b$ take values from $\quantity{0,1}$, which are the result of
the measurement on each subsystem. This is exactly the Bell basis, and hence
the measurement 6 is commonly known as the Bell measurement. The Bell basis
can be rewritten as

$(-i)^{z_{1}\cdot z_{2}}\sigma_{z_{1},z_{2}}\otimes\mathbb{I}\ket{\Psi^{+}}\
,$ (8)

where
$\sigma_{z_{1},z_{2}}=i^{z_{1},z_{2}}\sigma_{X}^{z_{1}}\sigma_{Z}^{z_{2}}$ are
the Pauli operators:

$\mathbb{I}=\sigma_{0,0};\quad\sigma_{X}=\sigma_{1,0};\quad\sigma_{Z}=\sigma_{0,1};\quad\sigma_{Y}=\sigma_{1,1}\
.$

This alternative form is derived from the identity, where for all operators
$A,B$ acting on $\mathbb{C}^{2}$,

$A\otimes B\ket{\Psi^{+}}=(AB^{\mathsf{T}})\otimes\mathbb{I}\ket{\Psi^{+}}\ .$
(9)

As the result, the probability of obtaining measurement outcome
$(z_{1},z_{2})$ in the destructive swap test 6 is given by

$p(z_{1},z_{2})=\bra{\Psi^{+}}\quantity(\sigma_{z_{1},z_{2}}\rho\sigma_{z_{1},z_{2}})\otimes\rho\ket{\Psi^{+}}\
,$ (10)

which uses the fact that Pauli operators are Hermitian. By applying (9) to the
second copy of $\rho$, together with the definition of $\ket{\Psi^{+}}$,

$p(z_{1},z_{2})=\frac{1}{2}\Tr[\rho\sigma_{z_{1},z_{2}}\rho^{\mathsf{T}}\sigma_{z_{1},z_{2}}]\
.$ (11)

As the transpose is a Hermitian-preserving trace-preserving linear map on
operators, it has a unique affine decomposition in terms of the Pauli
operators:

$\rho^{\mathsf{T}}=\frac{1}{2}\sum_{z_{1},z_{2}}(-1)^{z_{1}\cdot
z_{2}}\sigma_{z_{1},z_{2}}\rho\sigma_{z_{1},z_{2}}\ .$ (12)

Also, since transpose is an involution, we may interchange $\rho$ with
$\rho^{\mathsf{T}}$ in (12). As a result,

$\displaystyle\Tr[\rho^{2}]$
$\displaystyle=\Tr[\rho\frac{1}{2}\sum_{z_{1},z_{2}}(-1)^{z_{1}\cdot
z_{2}}\sigma_{z_{1},z_{2}}\rho^{\mathsf{T}}\sigma_{z_{1},z_{2}}]$ (13)
$\displaystyle=\sum_{z_{1},z_{2}}(-1)^{z_{1}\cdot
z_{2}}\frac{1}{2}\Tr[\rho\sigma_{z_{1},z_{2}}\rho^{\mathsf{T}}\sigma_{z_{1},z_{2}}]$
$\displaystyle=\sum_{z_{1},z_{2}}(-1)^{z_{1}\cdot z_{2}}p(z_{1},z_{2})\ .$

This indicates that the value of $\Tr[\rho^{2}]$ can be obtained with a simple
classical post-processing, where after each measurement, $(-1)^{z_{1}\cdot
z_{2}}$ is computed, whose mean is the value of $\Tr[\rho^{2}]$. This
procedure is equivalent to the evaluation of the expected value of the
observable

$S_{1}:=\sum_{z_{1},z_{2}}(-1)^{z_{1}\cdot
z_{2}}\outerproduct{\Psi_{z_{1},z_{2}}}{\Psi_{z_{1},z_{2}}}\ .$ (14)

This can be easily extended to multi-qubit systems, where the Bell
measurements are performed pairwisely between the two copies of the same
state. In this scenario, the measurement results are given by the Boolean
vectors $\boldsymbol{z}_{1}$ and $\boldsymbol{z}_{2}\in\mathbb{B}^{n}$, where
the $i$th element of each vector corresponds to the measurement outcome of the
$i$th pair of qubits. The multi-qubit Bell states are given by

$\ket{\Psi_{\boldsymbol{z}_{1},\boldsymbol{z}_{2}}}:=\bigotimes_{i}\ket{\Psi_{z_{i,1},z_{i,2}}}\
,$ (15)

where $\ket{\psi_{z_{i,1},z_{i,2}}}$ are the Bell states on $i$th qubit. The
probability of each measurement outcome is given by

$p(\boldsymbol{z}_{1},\boldsymbol{z}_{2})=\bra{\Psi^{+}}\quantity(\sigma_{\boldsymbol{z}_{1},\boldsymbol{z}_{2}}\rho\sigma_{\boldsymbol{z}_{1},\boldsymbol{z}_{2}})\otimes\rho\ket{\Psi^{+}}\
,$ (16)

where
$\sigma_{\boldsymbol{z}_{1},\boldsymbol{z}_{2}}:=\bigotimes_{i}\sigma_{z_{i,1},z_{i,2}}$.
By applying identity (9) to all qubits simultaneously,

$p(\boldsymbol{z}_{1},\boldsymbol{z}_{2})=\frac{1}{2^{n}}\Tr[\rho\sigma_{\boldsymbol{z}_{1},\boldsymbol{z}_{2}}\rho^{\mathsf{T}}\sigma_{\boldsymbol{z}_{1},\boldsymbol{z}_{2}}]\
.$ (17)

Since the transpose of a $n$-qubit state is equivalent to partial transpose
each qubit,

$\displaystyle\rho^{\mathsf{T}}$
$\displaystyle=\sum_{\boldsymbol{z}_{1},\boldsymbol{z}_{2}}\quantity(\prod_{i}\frac{1}{2}(-1)^{z_{i,1}\cdot
z_{i,2}})\sigma_{\boldsymbol{z}_{1},\boldsymbol{z}_{2}}\rho\sigma_{\boldsymbol{z}_{1},\boldsymbol{z}_{2}}$
(18)
$\displaystyle=\frac{1}{2^{n}}\sum_{\boldsymbol{z}_{1},\boldsymbol{z}_{2}}(-1)^{\boldsymbol{z}_{1}\cdot\boldsymbol{z}_{2}}\sigma_{\boldsymbol{z}_{1},\boldsymbol{z}_{2}}\rho\sigma_{\boldsymbol{z}_{1},\boldsymbol{z}_{2}}\
,$

where $\boldsymbol{z}_{1}\cdot\boldsymbol{z}_{2}:=\sum_{i}z_{i_{1}}\cdot
z_{i_{2}}$. The purity can be expressed as

$\Tr[\rho^{2}]=\sum_{\boldsymbol{z}_{1},\boldsymbol{z}_{2}}(-1)^{\boldsymbol{z}_{1}\cdot\boldsymbol{z}_{2}}p(\boldsymbol{z}_{1},\boldsymbol{z}_{2})\
.$ (19)

That is, to measure the purity, one Bell measurements 6 is applied to each
pair of qubits. After the outcomes are obtained, the value
$(-1)^{\boldsymbol{z}_{1}\cdot\boldsymbol{z}_{2}}$ is computed, whose mean is
the value of $\Tr[\rho^{2}]$. As the Bell measurements are independent, all of
them can be done simultaneously within two layers of quantum gates. The post-
processing is a simple parity checking, whose complexity grows linearly with
the number of qubits. The corresponding observables are

$S_{n}:=\sum_{\boldsymbol{z}_{1},\boldsymbol{z}_{2}}(-1)^{\boldsymbol{z}_{1}\cdot\boldsymbol{z}_{2}}\outerproduct{\Psi_{\boldsymbol{z}_{1},\boldsymbol{z}_{2}}}{\Psi_{\boldsymbol{z}_{1},\boldsymbol{z}_{2}}}\
.$ (20)

∎

######  Theorem 6.

The observable $S$ in theorem 5 is the swap operator between the two copies of
$\rho$.

###### Proof.

To check that $S_{n}$ is indeed the swap operator between the two copies of
$\rho$, we first notice that $S_{n}$ can be expressed as two terms:

$S_{n}:=\sum_{\boldsymbol{z}_{1}\cdot\boldsymbol{z}_{2}=0}\outerproduct{\Psi_{\boldsymbol{z}_{1},\boldsymbol{z}_{2}}}{\Psi_{\boldsymbol{z}_{1},\boldsymbol{z}_{2}}}-\sum_{\boldsymbol{z}_{1}\cdot\boldsymbol{z}_{2}=1}\outerproduct{\Psi_{\boldsymbol{z}_{1},\boldsymbol{z}_{2}}}{\Psi_{\boldsymbol{z}_{1},\boldsymbol{z}_{2}}}\
.$ (21)

As Bell states $\ket{\Psi_{\boldsymbol{z}_{1},\boldsymbol{z}_{2}}}$ are
orthogonal to each other, the two terms are (unnormalised) orthogonal
projectors. As discussed in the proof of the theorem 5, the Bell basis can be
expressed as

$\ket{\Psi_{\boldsymbol{z}_{1},\boldsymbol{z}_{2}}}:=(-i)^{\boldsymbol{z}_{1}\cdot\boldsymbol{z}_{2}}\sigma_{\boldsymbol{z}_{1},\boldsymbol{z}_{2}}\otimes\mathbb{I}\ket{\Psi^{+}}\
.$ (22)

By swapping the two subspaces

$\displaystyle S\ket{\Psi_{\boldsymbol{z}_{1},\boldsymbol{z}_{2}}}$
$\displaystyle=(-i)^{\boldsymbol{z}_{1}\cdot\boldsymbol{z}_{2}}\mathbb{I}\otimes\sigma_{\boldsymbol{z}_{1},\boldsymbol{z}_{2}}\ket{\Psi^{+}}$
(23)
$\displaystyle=(-i)^{\boldsymbol{z}_{1}\cdot\boldsymbol{z}_{2}}\sigma^{\mathsf{T}}_{\boldsymbol{z}_{1},\boldsymbol{z}_{2}}\otimes\mathbb{I}\ket{\Psi^{+}}$
$\displaystyle=(-i)^{\boldsymbol{z}_{1}\cdot\boldsymbol{z}_{2}}(-1)^{\boldsymbol{z}_{1}\cdot\boldsymbol{z}_{2}}\sigma_{\boldsymbol{z}_{1},\boldsymbol{z}_{2}}\otimes\mathbb{I}\ket{\Psi^{+}}$
$\displaystyle=(-1)^{\boldsymbol{z}_{1}\cdot\boldsymbol{z}_{2}}\ket{\Psi_{\boldsymbol{z}_{1},\boldsymbol{z}_{2}}}\
.$

That is, $\ket{\Psi_{\boldsymbol{z}_{1},\boldsymbol{z}_{2}}}$ is symmetric if
$\boldsymbol{z}_{1}\cdot\boldsymbol{z}_{2}=0$, and is anti-symmetric if it is
$1$. By counting the dimension of the symmetric subspace, it is easy to show
that those $\ket{\Psi_{\boldsymbol{z}_{1},\boldsymbol{z}_{2}}}$ with
$\boldsymbol{z}_{1}\cdot\boldsymbol{z}_{2}=0$ forms a complete basis of the
symmetric subspace, and
$\Pi_{S}:=\sum_{\boldsymbol{z}_{1}\cdot\boldsymbol{z}_{2}=0}\outerproduct{\Psi_{\boldsymbol{z}_{1},\boldsymbol{z}_{2}}}{\Psi_{\boldsymbol{z}_{1},\boldsymbol{z}_{2}}}$
is the projector to the symmetric subspace. Similarly, those with
$\boldsymbol{z}_{1}\cdot\boldsymbol{z}_{2}=1$ form a complete basis of the
anti-symmetric subspace, and the second term, denoted $\Pi_{A}$, is the
projector to the anti-symmetric subspace. As a result, $S_{n}=\Pi_{S}-\Pi_{A}$
is the swap operator, which preserves the symmetric subspace and provides a
$-1$ phase to the anti-symmetric subspace. ∎

######  Theorem 7.

Given an observable $O$ defined for 2-copies of
$\mathcal{U}(\rho)\in\mathcal{H}$, and consider the expectation value
$E(\rho)$ with respect to a channel $\mathcal{U}$ that
$E=\Tr[\mathcal{U}(\rho)\otimes\mathcal{U}(\rho)O]$. The Haar average of $E$,
$\int\differential\psi E(\outerproduct{\psi}{\psi})$, can be evaluated by
measuring $O$ on a single initial state $\tau\in\mathcal{H}^{\otimes 2}$, such
that $\tau$ can be prepared with a constant depth quantum circuit and a linear
time classical pre-processing.

###### Proof.

The average

$\displaystyle\int\differential\psi E(\outerproduct{\psi}{\psi})$
$\displaystyle=\int\differential\psi\tr[\mathcal{U}^{\otimes
2}(\rho_{\psi}\otimes\rho_{\psi})O]$ (24)
$\displaystyle=\tr[\int\differential\psi\mathcal{U}^{\otimes
2}(\rho_{\psi}\otimes\rho_{\psi})O]$ $\displaystyle=\tr[\mathcal{U}^{\otimes
2}\quantity(\int\differential\psi\rho_{\psi}\otimes\rho_{\psi})O]\ ,$

where $\rho_{\psi}=\outerproduct{\psi}{\psi}$ is distributed according to the
Haar measure. As the input state $\ket{\psi}\ket{\psi}$ is symmetric at all
instances, the Haar average of the input state is a projector state that

$\tau:=\int\differential\psi\rho_{\psi}\otimes\rho_{\psi}=\frac{\Pi_{S}}{\tr[\Pi_{S}]}\
,$ (25)

where $\Pi_{S}$ is invariant under swap [24]. To prepare the projector state
$\tau$, it is sufficient to find a basis of the projected space and then
uniformly random sample the basis states. Thus the preparation of state
$\Pi_{S}/\tr[\Pi_{S}]$ is reduced to uniformly random sample
$\boldsymbol{z}_{1}$ and $\boldsymbol{z}_{2}$ such that
$\boldsymbol{z}_{1}\cdot\boldsymbol{z}_{2}$ is even, and according to each
pair of $(\boldsymbol{z}_{1},\boldsymbol{z}_{2})$, prepare state
$\ket{\Psi_{\boldsymbol{z}_{1},\boldsymbol{z}_{2}}}$. And the states
$\ket{\Psi_{\boldsymbol{z}_{1},\boldsymbol{z}_{2}}}$ can be prepared by apply
the circuit 7 to classical states
$\ket{\boldsymbol{z}_{1}}\ket{\boldsymbol{z}_{2}}$ pairwisely. Similar to the
Bell measurement, the preparation of Bell states only requires two layers of
quantum gates.

$\ket{z_{1}}$ &
$\ket{z_{2}}$ H -1

Figure 7: The circuit that prepares Bell states.

Although some subtle optimization may be used to sample the desired classical
bits $\boldsymbol{z}_{1}$ and $\boldsymbol{z}_{2}$, a naïve rejective sampling
can already uniformly sample the even bits in time linear to the number of
qubits. This can be achieved by uniformly random sampling all bits in
$\boldsymbol{z}_{1}$ and $\boldsymbol{z}_{2}$ independently. Then resample the
bits until $\boldsymbol{z}_{1}\cdot\boldsymbol{z}_{2}$ is even. The reject
rate is less than $1/2$ for all sizes of quantum circuits, as there
$2^{2n-1}+2^{n-1}$ pairs of $\boldsymbol{z}_{1}$ and $\boldsymbol{z}_{2}$ that
$\boldsymbol{z}_{1}\cdot\boldsymbol{z}_{2}$ is even, and the total number of
the configurations is $2^{2n}$. ∎

Combine theorem 5 and 7, we have the average linear entropy $L$ of the output
of a channel $\mathcal{U}$:

$\displaystyle\int\differential\psi
L(\mathcal{U}(\outerproduct{\psi}{\psi}))=$
$\displaystyle\int\differential\psi(1-\tr[\mathcal{U}(\outerproduct{\psi}{\psi})^{2}])$
(26) $\displaystyle=$ $\displaystyle
1-\int\differential\psi\tr[\mathcal{U}^{\otimes
2}(\rho_{\psi}\otimes\rho_{\psi})S]$ $\displaystyle=$ $\displaystyle
1-\tr[\mathcal{U}^{\otimes 2}(\tau)S]\ .$

This argument can be applied to the case where $L$ is defined for a subsystem.
Given the total space $\mathcal{H}$ is decomposed into
$\mathcal{H}^{A}\otimes\mathcal{H}^{B}$, the average linear entropy of the
output of a channel $\mathcal{U}$ on subsystem $A$ is given by

$\displaystyle\iint\differential\psi_{A}\differential\phi_{B}L_{A}:=$
$\displaystyle\iint\differential\psi_{A}\differential\phi_{B}L(\tr_{B}[\mathcal{U}(\outerproduct{\psi}{\psi}_{A}\otimes\outerproduct{\varphi}{\varphi}_{B})])$
(27) $\displaystyle=$ $\displaystyle
1-\iint\differential\psi_{A}\differential\phi_{B}\tr[\mathcal{U}^{\otimes
2}({\rho_{\psi}}_{A}\otimes{\rho_{\psi}}_{A}\otimes{\rho_{\phi}}_{B}\otimes{\rho_{\phi}}_{B})S_{A}\otimes\mathbb{I}_{B}]$
$\displaystyle=$ $\displaystyle 1-\tr[\mathcal{U}^{\otimes
2}(\tau_{A}\otimes\tau_{B})S_{A}\otimes\mathbb{I}_{B}]$ $\displaystyle=$
$\displaystyle 1-\tr_{A}[\tr_{B}[\mathcal{U}^{\otimes
2}(\tau_{A}\otimes\tau_{B})]S_{A}]\ .$

As the purity $\Tr[\rho^{2}]$ is obtained from classical post-processing, the
purity of each subsystem can be obtained simultaneously, with the same set of
measured data. That is, for any partition of the qubits encoding $\rho$, all
of the values of $\Tr[\pqty{\rho^{A}}^{2}]$ and $\Tr[\pqty{\rho^{B}}^{2}]$
together with the $\Tr[\rho^{2}]$ can be obtained with one shot of
measurements on the quantum circuit. This property means that our cost
function

$\displaystyle
C_{D}=\frac{d_{A}^{2}}{d_{A}^{2}-1}\iint\differential\psi_{A}\differential\psi_{B}\frac{L_{A}+L_{B}}{2}$
(28) $\displaystyle\propto$ $\displaystyle 1-\frac{\tr[\mathcal{U}^{\otimes
2}(\tau_{A}\otimes\tau_{B})S_{A}\otimes\mathbb{I}_{B}]+\tr[\mathcal{U}^{\otimes
2}(\tau_{A}\otimes\tau_{B})\mathbb{I}_{A}\otimes S_{B}]}{2}$ $\displaystyle=$
$\displaystyle 1-\frac{\tr[\mathcal{U}^{\otimes
2}(\tau_{A}\otimes\tau_{B})(S_{A}\otimes\mathbb{I}_{B}+\mathbb{I}_{A}\otimes
S_{B})]}{2}$

can be evaluated with a single shot of measurements on the quantum circuit,
and a linear time classical post-processing.

##  Appendix C Parameter Shift Rule

###  C.1 Preliminary

The parameter shift rule [13] is widely used in variational quantum circuits
for gradient-based optimization. It outperforms the finite difference method,
which estimate
$\partialderivative{\theta_{i}}f({\bf\it\theta})\approx\frac{f({\bf\it\theta}+\Delta\theta_{i})-f({\bf\it\theta})}{\Delta\theta_{i}}$,
with a finite small number $\Delta\theta_{i}$. In the finite difference
method, as the denominator $\Delta\theta_{i}$ is small, the difference of $f$
is a small number, which is relatively sensitive to the noises. But, with the
parameter shift rule, the gradient can be estimated directly, which is less
sensitive to perturbations as long as the gradient is non-varnishing.

The usual parameter shift rule is based on the idempotent properties of
Hermitian generators. Let us consider a single-parameterized unitary
$U(\theta_{i})=e^{-i\frac{\theta_{i}}{2}H}$ that is generated by an idempotent
Hermitian operator $H$ that $H^{2}=\mathbb{I}$. The parameter shift rule says

######  Proposition 8.

For all observables $A$ and all initial states $\rho$, the derivative of the
expectation value

$\displaystyle\partialderivative{\theta_{i}}\tr[U(\theta_{i})\rho
U^{\dagger}(\theta_{i})A]=$
$\displaystyle\frac{\tr[U(\theta_{i}+\frac{\pi}{2})\rho
U^{\dagger}(\theta_{i}+\frac{\pi}{2})A]-\tr[U(\theta_{i}-\frac{\pi}{2})\rho
U^{\dagger}(\theta_{i}-\frac{\pi}{2})A]}{2}\ .$ (29)

###### Proof.

The derivatives of the unitary operator and its conjugate are given by
$\partialderivative{\theta_{i}}U(\theta_{i})=-iU(\theta_{i})H/2$, and
$\partialderivative{\theta_{i}}U^{\dagger}(\theta_{i})=iHU^{\dagger}(\theta_{i})/2$.
As a result, for any operator $\rho$,

$\displaystyle\partialderivative{\theta_{i}}U(\theta_{i})\rho
U^{\dagger}(\theta_{i})=$
$\displaystyle\quantity(\partialderivative{\theta_{i}}U(\theta_{i}))\rho
U^{\dagger}(\theta_{i})+U(\theta_{i})\rho\quantity(\partialderivative{\theta}U^{\dagger}(\theta_{i}))$
(30) $\displaystyle=$ $\displaystyle-iU(\theta_{i})H\rho
U^{\dagger}(\theta_{i})/2+iU(\theta_{i})\rho HU^{\dagger}(\theta_{i})/2$
$\displaystyle=$ $\displaystyle
U(\theta_{i})(-i[H,\rho])U^{\dagger}(\theta_{i})/2$

By matching the coefficients of the Taylor series, it can be shown that
$U(\theta_{i})=\cos(\theta_{i}/2)\mathbb{I}-i\sin(\theta_{i}/2)H$, and

$\displaystyle-i[H,\rho]=$ $\displaystyle-iH\rho+i\rho H$ (31)
$\displaystyle=$
$\displaystyle\frac{(\mathbb{I}-iH)\rho(\mathbb{I}+iH)-(\mathbb{I}+iH)\rho(\mathbb{I}-iH)}{2}$
$\displaystyle=$ $\displaystyle e^{-\frac{i\pi}{4}H}\rho
e^{\frac{i\pi}{4}H}-e^{\frac{i\pi}{4}H}\rho e^{-\frac{i\pi}{4}H}$
$\displaystyle=$ $\displaystyle U(\frac{\pi}{2})\rho
U^{\dagger}(\frac{\pi}{2})-U(-\frac{\pi}{2})\rho U^{\dagger}(-\frac{\pi}{2})\
.$

In summary, the derivative of the operator

$\displaystyle\partialderivative{\theta_{i}}U(\theta_{i})\rho
U^{\dagger}(\theta_{i})=$ $\displaystyle\frac{U(\theta_{i}+\frac{\pi}{2})\rho
U^{\dagger}(\theta_{i}+\frac{\pi}{2})-U(\theta_{i}-\frac{\pi}{2})\rho
U^{\dagger}(\theta_{i}-\frac{\pi}{2})}{2}$ (32)

The proposition is the direct result of (32) ∎

###  C.2 Parameter Shift Rule for $C_{D}$

Here we show that a similar parameter shift rule can be derived for our cost
function $C_{D}$. Specifically, the derivative
$\partialderivative{\theta_{i}}C_{D}$ can be evaluated by four terms, each of
which can be evaluated by the same quantum circuit for evaluating $C_{D}$. To
simplify the notation in the following discussion, let
$\mathcal{U}_{\theta_{i}}$ denote the family of unitary channels that
$\mathcal{U}_{\theta_{i}}(\cdot)=U(\theta_{i})\cdot U^{\dagger}(\theta_{i})$.
The parameter shift rule (32) can be rewritten as

$\partialderivative{\theta_{i}}\mathcal{U}_{\theta_{i}}(\rho)=\frac{\mathcal{U}_{\theta_{i}+\frac{\pi}{2}}(\rho)-\mathcal{U}_{\theta_{i}-\frac{\pi}{2}}(\rho)}{2}\
.$ (33)

Our cost function is defined by the expectation value of an observable $O$

$C_{D}(W)=\tr[W^{\otimes 2}\rho{W^{\dagger}}^{\otimes 2}S]\ ,$ (34)

where the initial state $\rho=\tau_{A}\otimes\tau_{B}$, and $W$ is a quantum
circuit parameterized by $\overrightarrow{{\bf\it\theta}}$. In the design of
the ansatz, for each parameter $\theta_{i}$, there is only one Pauli rotation
gate that depends on $\theta_{i}$ in $W(\overrightarrow{{\bf\it\theta}})$. We
may split the circuit $W$ into three parts as in figure 8, where
$W=PU(\theta_{i})Q$. All gates before $U(\theta_{i})$ are collected in $Q$,
and all gates after $U(\theta_{i})$ are collected in $P$. Then

$\displaystyle W^{\otimes 2}=$ $\displaystyle(PU(\theta_{i})Q)^{\otimes 2}$
(35) $\displaystyle=$ $\displaystyle P^{\otimes 2}U(\theta_{i})^{\otimes
2}Q^{\otimes 2}$ $\displaystyle=$ $\displaystyle P^{\otimes
2}(U(\theta_{i})\otimes\mathbb{I})(\mathbb{I}\otimes U(\theta_{i}))Q^{\otimes
2}\ .$

Let $\mathcal{U}^{\prime}_{\theta_{i}}$ and
$\mathcal{U}^{{}^{\prime\prime}}_{\theta_{i}}$ denote the unitary channels
corresponding to $U(\theta_{i})\otimes\mathbb{I}$ and $\mathbb{I}\otimes
U(\theta_{i})$ respectively. And let $\mathcal{P},\mathcal{Q}$ denote the
unitary channels corresponding to $P^{\otimes 2}$ and $Q^{\otimes 2}$. Then
the unitary evolution can be written as the composition of $4$ unitary
channels:

$C_{D}(W)=\tr[(\mathcal{P}\circ\mathcal{U}^{{}^{\prime}}_{\theta_{i}}\circ\mathcal{U}^{{}^{\prime\prime}}_{\theta_{i}}\circ\mathcal{Q})(\rho)O]\
.$ (36)

Figure 8: For each parameter $\theta_{i}$, the parameterized circuit $W$ can
be split into three parts, where $W=PU(\theta_{i})Q$. As there is only one
Pauli rotation gate $U(\theta_{i})$ that depends on $\theta_{i}$, all gates
before $U(\theta_{i})$ are collected in $Q$, and all gates after
$U(\theta_{i})$ are collected in $P$. For convenience, we put all gates
parallel to $U(\theta_{i})$ into $Q$.

According to the product rule of derivatives,

$\partialderivative{\theta_{i}}(\mathcal{U}^{\prime}_{\theta_{i}}\circ\mathcal{U}^{{}^{\prime\prime}}_{\theta_{i}})=(\partialderivative{\theta_{i}}\mathcal{U}^{\prime}_{\theta_{i}})\circ\mathcal{U}^{{}^{\prime\prime}}_{\theta_{i}}+\mathcal{U}^{\prime}_{\theta_{i}}\circ(\partialderivative{\theta_{i}}\mathcal{U}^{{}^{\prime\prime}}_{\theta_{i}})\
.$ (37)

As the Paul rotations $U(\theta_{i})$ are generated by idempotent operators
and satisfies the parameter shift rule (32), the same property holds for
$\mathcal{U}^{\prime}_{\theta_{i}}$ and
$\mathcal{U}^{{}^{\prime\prime}}_{\theta_{i}}$. In conclusion, the derivative
of our cost function is

$\displaystyle\partialderivative{\theta_{i}}C_{D}(W)=$
$\displaystyle\tr[(\mathcal{P}\circ\partialderivative{\theta_{i}}\quantity(\mathcal{U}^{{}^{\prime}}_{\theta_{i}}\circ\mathcal{U}^{{}^{\prime\prime}}_{\theta_{i}})\circ\mathcal{Q})(\rho)O]$
(38) $\displaystyle=$
$\displaystyle\tr[(\mathcal{P}\circ\quantity(\frac{\mathcal{U}^{{}^{\prime}}_{\theta_{i}+\frac{\pi}{2}}-\mathcal{U}^{{}^{\prime}}_{\theta_{i}-\frac{\pi}{2}}}{2})\circ\mathcal{U}^{{}^{\prime\prime}}_{\theta_{i}}\circ\mathcal{Q})(\rho)O]+\tr[(\mathcal{P}\circ\mathcal{U}^{\prime}_{\theta_{i}}\circ\quantity(\frac{\mathcal{U}^{{}^{\prime\prime}}_{\theta_{i}+\frac{\pi}{2}}-\mathcal{U}^{{}^{\prime\prime}}_{\theta_{i}-\frac{\pi}{2}}}{2})\circ\mathcal{Q})(\rho)O]$
$\displaystyle=$
$\displaystyle\frac{1}{2}\tr[(\mathcal{P}\circ\mathcal{U}^{{}^{\prime}}_{\theta_{i}+\frac{\pi}{2}}\circ\mathcal{U}^{{}^{\prime\prime}}_{\theta_{i}}\circ\mathcal{Q})(\rho)O]-\frac{1}{2}\tr[(\mathcal{P}\circ\mathcal{U}^{{}^{\prime}}_{\theta_{i}-\frac{\pi}{2}}\circ\mathcal{U}^{{}^{\prime\prime}}_{\theta_{i}}\circ\mathcal{Q})(\rho)O]$
$\displaystyle+\frac{1}{2}\tr[(\mathcal{P}\circ\mathcal{U}^{\prime}_{\theta_{i}}\circ\mathcal{U}^{{}^{\prime\prime}}_{\theta_{i}+\frac{\pi}{2}}\circ\mathcal{Q})(\rho)O]-\frac{1}{2}\tr[(\mathcal{P}\circ\mathcal{U}^{\prime}_{\theta_{i}}\circ\mathcal{U}^{{}^{\prime\prime}}_{\theta_{i}-\frac{\pi}{2}}\circ\mathcal{Q})(\rho)O]\
.$

This is the sum of $4$ terms, each of which can be evaluated by the same
method of evaluating $C_{D}(W)$ with a “parameter shift”.

##  Appendix D Relating decoupling cost to the gate fidelity

###  D.1 Characteristics of the gate fidelity

The closeness of approximating $U$ with $U_{A}\otimes U_{B}$ is measured by
the gate fidelity between $U$ and $U_{A}\otimes U_{B}$, which is defined by

$\bar{F}:=\int\differential\psi\tr[(U_{A}\otimes
U_{B})^{\dagger}U\outerproduct{\psi}{\psi}U^{\dagger}(U_{A}\otimes
U_{B})\outerproduct{\psi}{\psi}]\ .$ (39)

This Haar average can be contracted to a single quantity that

$\bar{F}=\frac{1}{d+1}+\frac{1}{d(d+1)}\absolutevalue{\langle U_{A}\otimes
U_{B},U\rangle}^{2}\ ,$ (40)

where $d$ is the dimension of the global Hilbert space. Here $\langle
U_{A}\otimes U_{B},U\rangle:=\Tr[(U_{A}\otimes U_{B})^{\dagger}U]$ denotes the
Hilbert-Schmidt inner product between $U_{A}\otimes U_{B}$ and $U$. Note that,
the average fidelity is maximized when $\langle U_{A}\otimes U_{B},U\rangle$
is maximized. Let $\mathcal{U}$ be the unitary channel that
$\mathcal{U}(\cdot)=U(\cdot)U^{\dagger}$, and let $\mathcal{U}_{A}$ and
$\mathcal{U}_{B}$ be the corresponding channels for $U_{A}$ and $U_{B}$.
Denote the Choi-Jamiolkowski matrix of a channel $\mathcal{U}$ by
$J^{\mathcal{U}}$. Then the inner product can be expressed as

$\absolutevalue{\langle U_{A}\otimes
U_{B},U\rangle}^{2}=\Tr[(J^{\mathcal{U}_{A}}\otimes
J^{\mathcal{U}_{B}})J^{\mathcal{U}}]\ .$ (41)

As the Choi rank of unitary channels are all $1$, we may rewrite the Choi
operators as the outer products

$J^{\mathcal{U}}=\outerproduct{\psi}{\psi},\quad
J^{\mathcal{U}_{A}}=\outerproduct{\psi_{A}}{\psi_{A}},\quad
J^{\mathcal{U}_{B}}=\outerproduct{\psi_{B}}{\psi_{B}}\ .$ (42)

Then

$\absolutevalue{\langle U_{A}\otimes
U_{B},U\rangle}^{2}=\absolutevalue{(\bra{\psi_{A}}\otimes\bra{\psi_{B}})\ket{\psi}}^{2}\
.$ (43)

As $\ket{\psi}$ is a vector in the Hilbert space, there exists a Schmidt
decomposition such that

$\ket{\psi}=\sum_{k}\sqrt{p_{k}}\ket{\xi_{k}}\otimes\ket{\phi_{k}}\ ,$ (44)

where $\sum_{k}p_{k}=\innerproduct{\psi}{\psi}=d$ according to the
normalization condition for quantum channels. As the result, the maximum value
of $\absolutevalue{\langle U_{A}\otimes U_{B},U\rangle}^{2}$ is given by

$\max_{U_{A},U_{B}}\absolutevalue{\langle U_{A}\otimes
U_{B},U\rangle}^{2}=\max_{\ket{\psi_{A}},\ket{\psi_{B}}}\absolutevalue{\sum_{k}\sqrt{p_{k}}\innerproduct{\psi_{A}}{\xi_{k}}\otimes\innerproduct{\psi_{B}}{\phi_{k}}}^{2}\
.$ (45)

Let $q_{A,k}:=\innerproduct{\psi_{A}}{\xi_{k}}$ and
$q_{B,k}:=\innerproduct{\psi_{B}}{\phi_{k}}$, we have

$\displaystyle\absolutevalue{\langle U_{A}\otimes U_{B},U\rangle}=$
$\displaystyle\absolutevalue{\sum_{k}\sqrt{p_{k}}q_{A,k}q_{B,k}}$ (46)
$\displaystyle\leq$
$\displaystyle\sum_{k}\sqrt{p_{i}}\absolutevalue{q_{A,k}q_{B,k}}$
$\displaystyle\leq$
$\displaystyle\max{\sqrt{p_{i}}}\sum_{k}\absolutevalue{q_{A,k}q_{B,k}}$
$\displaystyle=$
$\displaystyle\max{\sqrt{p_{i}}}\absolutevalue{\innerproduct{\absolutevalue{p_{A}}}{\absolutevalue{q_{B}}}}$

According to the Cauchy-Schwartz inequality,

$\absolutevalue{\innerproduct{\absolutevalue{q_{A}}}{\absolutevalue{q_{B}}}}^{2}\leq\norm{q_{A}}_{2}^{2}\norm{q_{B}}_{2}^{2}\
.$ (47)

Given $\ket{\xi_{k}}$ and $\ket{\phi_{k}}$ are orthonormal bases,
$\norm{q_{A}}_{2}^{2}=\absolutevalue{\innerproduct{\psi_{A}}{\psi_{A}}}^{2}=d_{A}$
and $\norm{q_{B}}_{2}^{2}=d_{B}$. As above inequalities hold for all
$\ket{\psi_{A}},\ket{\psi_{B}}$,

$\max_{U_{A},U_{B}}\absolutevalue{\langle U_{A}\otimes
U_{B},U\rangle}^{2}\leq\max{q_{i}}d_{A}d_{B}=d\norm{p}_{\infty}\ .$ (48)

where the infinity norm $\norm{p}_{\infty}$ equals to the maximum Schmidt
coefficient of $\ket{\psi}$. The equality holds when $\ket{\psi_{A}}$ and
$\ket{\psi_{B}}$ are proportional to the $\ket{\xi_{k}}$ and $\ket{\phi_{k}}$
that corresponding to the maximum $p_{k}$. However, this might not be
achievable as $\ket{\xi_{k}}$ and $\ket{\phi_{k}}$ do not necessarily
correspond to unitary operators.

In summary, for all $U_{A}\otimes U_{B}$, the gate fidelity is bounded by

$\frac{1}{d+1}\leq\bar{F}(U_{A}\otimes
U_{B},U)\leq\frac{1}{d+1}(\norm{p}_{\infty}+1)\leq 1\ .$ (49)

In other words

$\bar{F}_{\max}:=\max_{U_{A},U_{B}}\bar{F}(U_{A}\otimes
U_{B},U)\leq\frac{1}{d+1}(\norm{p}_{\infty}+1)$ (50)

To fully understand the property of separability, we would like to explore the
gate fidelity with respect to an alternative set. Without loss of generality,
assuming the dimension of the system $A$, $d_{A}$, is not larger than $d_{B}$.
Then we may extend the Hilbert space of $A$ to $A^{\prime}$, whose dimension
is the same as $B$, such that $A^{\prime}=A\oplus C$, where $C$ is a
$d_{B}-d_{A}$ dimensional Hilbert space. We may extend $U$ to construct a
unitary operator in $A^{+}$, such that $U^{\prime}=U\oplus\mathbb{I}_{B\otimes
C}$. As the dimensions of $A^{+}$ and $B$ are the same, we may define the swap
operator $S$ between $A^{+}$ and $B$. Now, we will focus on the gate fidelity

$\max_{U_{A^{+}},U_{B}}\bar{F}(U_{A^{+}}\otimes U_{B},SU^{\prime})\ .$ (51)

Let $\quantity{q_{k}}$ be the Schmidt coefficients of the Choi operator with
respect to $SU^{\prime}$. Then, with similar arguments as above, we have

$\bar{F}_{\max}^{S}:=\max_{U_{A^{+}},U_{B}}\bar{F}(U_{A^{+}}\otimes
U_{B},SU^{\prime})\leq\frac{1}{d_{B}^{2}+1}(\norm{q}_{\infty}+1)\ .$ (52)

Since $d_{B}^{2}\geq d_{A}d_{B}=d$ by assumption,

$\bar{F}_{\max}^{S}\leq\frac{1}{d+1}(\norm{q}_{\infty}+1)\ .$ (53)

This quantity would be useful in the analysis of the decoupling cost.

###  D.2 Characteristics of the decoupling cost

In this section, we show that the maximum gate fidelity $\bar{F}_{\max}$ is
related to the decoupling cost function $C_{D}$, such that

$\bar{F}_{\max}\leq 1-C_{D}+\frac{3}{d+1}\ .$ (54)

The evaluation of $C_{D}$ requires two copies of a target unitary $U$, whose
acts on the system $A\otimes B$. We may label the systems as
$A_{1},A_{2},B_{1},B_{2}$, where one unitary acts on $A_{1}\otimes B_{1}$, and
the other acts on $A_{2}\otimes B_{2}$. In terms of the Choi-Jamiolkowski
operator, the average linear entropy, denoted $\bar{L}$, is given by

$\displaystyle 1-\frac{\tr[\mathcal{U}^{\otimes
2}(\tau_{A}\otimes\tau_{B})S_{A}\otimes\mathbb{I}_{B}]+\tr[\mathcal{U}^{\otimes
2}(\tau_{A}\otimes\tau_{B})\mathbb{I}_{A}\otimes S_{B}]}{2}$ (55)
$\displaystyle=$ $\displaystyle 1-\frac{\tr[\tau_{A}\otimes\tau_{B}\otimes
S_{A^{\prime}}\otimes\mathbb{I}_{B^{\prime}}(J^{\mathcal{U}}\otimes
J^{\mathcal{U}})]}{2}-\frac{\tr[\tau_{A}\otimes\tau_{B}\otimes\mathbb{I}_{A^{\prime}}\otimes
S_{B^{\prime}}(J^{\mathcal{U}}\otimes J^{\mathcal{U}})]}{2}\ ,$

where $S_{A}$ ($S_{B}$) is the swap operator between the output systems
$A_{1}$ and $A_{2}$, (or $B$ systems respectively), and the identity operators
$\mathbb{I}_{A},\mathbb{I}_{B}$ are also defined on the system $A_{1}\otimes
A_{2}$ or $B_{1}\otimes B_{2}$ respectively. This equality comes from theorem
4, where the partial transposes from the formula are omitted, as
$\tau_{k},\mathbb{I}_{k}$ and $S_{k}$ are all invariant under the transpose.
In this Choi representation, we need to distinguish the output systems and
input systems, and thus there are $8$ subsystems in the formula in total. We
may label the subsystems as $A_{1},A_{2},B_{1},B_{2}$ for the input systems,
and $A_{1}^{\prime},A_{2}^{\prime},B_{1}^{\prime},B_{2}^{\prime}$ for the
output systems. Note that, the initial state
$\tau_{k}=\frac{P_{s}}{\tr[P_{s}]}=\frac{1}{2\tr[P_{s}]}(S_{k}+\mathbb{I})$,
and the trace of the projector $tr[P_{S}]$ is $\frac{d_{A}^{2}+d_{A}}{2}$ for
the pair of systems $(A_{1},A_{2})$ and $\frac{d_{B}^{2}+d_{B}}{2}$ for the
pair of systems $(B_{1},B_{2})$, where $d_{A},d_{B}$ are the dimension of
system $A_{i},B_{i}$ respectively. Then each of the two terms in
$2(1-\bar{L})$ is divided into $4$ terms:

$\displaystyle\tr[\tau_{A}\otimes\tau_{B}\otimes
S_{A^{\prime}}\otimes\mathbb{I}_{B^{\prime}}(J^{\mathcal{U}}\otimes
J^{\mathcal{U}})]+\tr[\tau_{A}\otimes\tau_{B}\otimes\mathbb{I}_{A^{\prime}}\otimes
S_{B^{\prime}}(J^{\mathcal{U}}\otimes J^{\mathcal{U}})]$ (56) $\displaystyle=$
$\displaystyle\frac{1}{(d_{A}^{2}+d_{A})(d_{B}^{2}+d_{B})}\Big{(}\tr[\mathbb{I}_{A}\otimes\mathbb{I}_{B}\otimes
S_{A^{\prime}}\otimes\mathbb{I}_{B^{\prime}}(J^{\mathcal{U}}\otimes
J^{\mathcal{U}})]$ $\displaystyle+\tr[S_{A}\otimes\mathbb{I}_{B}\otimes
S_{A^{\prime}}\otimes\mathbb{I}_{B^{\prime}}(J^{\mathcal{U}}\otimes
J^{\mathcal{U}})]+\tr[\mathbb{I}_{A}\otimes S_{B}\otimes
S_{A^{\prime}}\otimes\mathbb{I}_{B^{\prime}}(J^{\mathcal{U}}\otimes
J^{\mathcal{U}})]$ $\displaystyle+\tr[S_{A}\otimes S_{B}\otimes
S_{A^{\prime}}\otimes\mathbb{I}_{B^{\prime}}(J^{\mathcal{U}}\otimes
J^{\mathcal{U}})]+\tr[\mathbb{I}_{A}\otimes\mathbb{I}_{B}\otimes\mathbb{I}_{A^{\prime}}\otimes
S_{B^{\prime}}(J^{\mathcal{U}}\otimes J^{\mathcal{U}})]$
$\displaystyle+\tr[S_{A}\otimes\mathbb{I}_{B}\otimes\mathbb{I}_{A^{\prime}}\otimes
S_{B^{\prime}}(J^{\mathcal{U}}\otimes
J^{\mathcal{U}})]+\tr[\mathbb{I}_{A}\otimes
S_{B}\otimes\mathbb{I}_{A^{\prime}}\otimes
S_{B^{\prime}}(J^{\mathcal{U}}\otimes J^{\mathcal{U}})]$
$\displaystyle+\tr[S_{A}\otimes S_{B}\otimes\mathbb{I}_{A^{\prime}}\otimes
S_{B^{\prime}}(J^{\mathcal{U}}\otimes J^{\mathcal{U}})]\Big{)}\ .$

For convenience, we label each term in the parenthesis as $P_{k}$ in the order
presented in (56), where $k$ ranges from $1$ to $8$. That is

$2(1-\bar{L})=\frac{\sum_{k}P_{k}}{(d_{A}^{2}+d_{A})(d_{B}^{2}+d_{B})}\ .$
(57)

By changing the order of the tensor products and grouping the swap operators,
we may rewrite each $P_{k}$ in the form of
$\tr[S_{\alpha}\otimes\mathbb{I}_{\beta}(J_{\alpha_{1},\beta_{1}}\otimes
J_{\alpha_{2},\beta_{2}})]$ for some partitioning $(\alpha,\beta)$ of the four
pairs the systems $(A_{1},A_{2})$, $(B_{1},B_{2})$,
$(A^{\prime}_{1},A^{\prime}_{2})$, $(B^{\prime}_{1},B^{\prime}_{2})$. This
formula is equivalent to

$\tr[S_{\alpha}\tr_{\beta}[J_{\alpha_{1},\beta_{1}}]\otimes\tr_{\beta}[J_{\alpha_{2},\beta_{2}}]]\
.$ (58)

Given $J^{\mathcal{U}}$ is a rank-$1$ operator, we can write it in its Schmidt
decomposition
$\ket{\psi}=\sum_{k}\sqrt{c_{k}}\ket{\varphi_{k}}_{\alpha}\otimes\ket{\varepsilon_{k}}_{\beta}$.
After the partial trace of the $\beta$ systems,

$\tr[J_{\alpha_{1},\beta_{1}}]\otimes\tr[J_{\alpha_{2},\beta_{2}}]=\quantity(\sum_{k}c_{k}\outerproduct{\varphi_{k}}{\varphi_{k}})\otimes\quantity(\sum_{l}c_{l}\outerproduct{\varphi_{l}}{\varphi_{l}})\
.$ (59)

Then, by applying the swap and the trace

$\tr[S_{\alpha}\tr_{\beta}[J\otimes
J]]=\sum_{k,l}c_{k}c_{l}\innerproduct{\varphi_{l}}{\varphi_{k}}\innerproduct{\varphi_{k}}{\varphi_{l}}=\norm{c}_{2}^{2}\
.$ (60)

This result indicates that each term of the $8$ terms is the 2-norm of the
Schmidt coefficients of $\ket{\psi}$ for some partitioning $(\alpha,\beta)$ of
the system $J^{\mathcal{U}}$ acting on. That is saying, every term $P_{k}$ is
positive and upper bounded by the inner product of $\ket{\psi}$, which is $d$.

Now, we need to analyze each of the terms individually. First notice that each
of the terms is the $2$-norm of the Schmidt coefficients of $\ket{\psi}$,
which only depends on the partitioning of the system. Specifically,

$\tr[S_{\alpha}\tr_{\beta}[J\otimes
J]]=\norm{c}_{2}^{2}=\tr[S_{\beta}\tr_{\alpha}[J\otimes J]]\ .$ (61)

As the result, by interchanging the subsystems $\alpha$ and $\beta$, the $8$
terms can be grouped into $4$ terms:

$P_{1}=P_{8};\quad P_{2}=P_{7};\quad P_{3}=P_{6};\quad P_{4}=P_{5}\ .$ (62)

$P_{2}$ is strongly related to the gate fidelity between $U$ and $U_{A}\otimes
U_{B}$. For $P_{2}$, the partition $(\alpha,\beta)$ matches the partition
$(A,B)$ in the analysis of the fidelity as in (44), which means
$P_{2}=\norm{p}_{2}^{2}$.

$P_{1}$ and $P_{5}$ are equivalent to the expectation value of
$S_{A}\otimes\mathbb{I}_{B}$ and $\mathbb{I}_{A}\otimes S_{B}$ respectively
with completely mixed state as input. That is

$\displaystyle P_{1}$
$\displaystyle=\tr[(S_{A}\otimes\mathbb{I}_{B})\mathcal{U}(\mathbb{I})\otimes\mathcal{U}(\mathbb{I})]$
(63)
$\displaystyle=\tr[(S_{A}\otimes\mathbb{I}_{B})\mathbb{I}\otimes\mathbb{I}]$
$\displaystyle=\tr[(S_{A}\otimes\mathbb{I}_{B})]$
$\displaystyle=d_{A}d_{B}^{2}\ ,$

where $d_{A}$ and $d_{B}$ are the dimensions of the subsystems $A_{i}$ and
$B_{i}$ respectively. Similarly, $P_{5}=d_{A}^{2}d_{B}$.

In summary,

$\displaystyle 1-\bar{L}=$
$\displaystyle\frac{\norm{p}_{2}^{2}+d_{A}d_{B}^{2}+d_{B}d_{A}^{2}+P_{3}}{(d_{A}^{2}+d_{A})(d_{B}^{2}+d_{B})}\
.$ (64)

As the dimension of the whole system $A\otimes B$ is $d=d_{A}d_{B}$, we have

$\bar{L}=-\frac{\norm{p}_{2}^{2}-d^{2}+P_{3}-d}{d(d+1+d_{A}+d_{B})}\ .$ (65)

Which means

$\norm{p}_{2}^{2}=d^{2}-P_{3}+d-d(d+1+d_{A}+d_{B})\bar{L}\ .$ (66)

Now, we will substitute the definition
$C_{D}=\frac{d_{A}^{2}}{d_{A}^{2}-1}\bar{L}$ to (66), where we assume
$d_{A}\leq d_{B}$. Let $K:=\frac{d_{A}^{2}-1}{d_{A}^{2}}$, then
$C_{D}=\frac{\bar{L}}{K}$.

$\norm{p}_{2}^{2}=d^{2}+d-P_{3}-KC_{D}d(d+1+d_{A}+d_{B})\ .$ (67)

Compared to the gate fidelity that

$\displaystyle\bar{F}_{\max}\leq$
$\displaystyle\frac{1}{d+1}+\frac{1}{d+1}\norm{p}_{\infty}$ (68)
$\displaystyle\leq$ $\displaystyle\frac{1}{d+1}+\frac{1}{d+1}\norm{p}_{2}$
$\displaystyle=$
$\displaystyle\frac{1}{d+1}+\frac{1}{d+1}\sqrt{d^{2}+d-P_{3}-KC_{D}d(d+1+d_{A}+d_{B})}$
$\displaystyle\leq$
$\displaystyle\frac{1}{d+1}+\frac{1}{d+1}\sqrt{d^{2}+d-P_{3}-KC_{D}(d^{2}+d)}$
$\displaystyle=$
$\displaystyle\frac{1}{d+1}+\sqrt{\frac{d}{d+1}}\sqrt{1-\frac{P_{3}}{d^{2}+d}-KC_{D}}\
.$

We may organize the terms to get

$\quantity(\bar{F}_{\max}-\frac{1}{d+1})^{2}\leq\frac{d}{d+1}\quantity(1-KC_{D}-\frac{P_{3}}{d^{2}+d})\
.$ (69)

and

$\quantity(\bar{F}_{\max}-\frac{1}{d+1})^{2}+\frac{P_{3}}{(d+1)^{2}}\leq\frac{d}{d+1}\quantity(1-KC_{D})\
.$ (70)

As $d=d_{A}d_{B}\geq d_{A}^{2}$ by assumption, we have,
$K\leq\frac{d^{2}-1}{d^{2}}$, and the above equation can be further simplified
to

$\displaystyle\quantity(\bar{F}_{\max}-\frac{1}{d+1})^{2}+\frac{P_{3}}{(d+1)^{2}}\leq$
$\displaystyle\frac{d}{d+1}\quantity(1-\frac{d^{2}-1}{d^{2}}C_{D})=\frac{d}{d+1}-\frac{d-1}{d}C_{D}\
.$ (71)

The quantity of $P_{3}$ here is related to the extended unitary $U^{\prime}$
as defined in (51). As $J^{\mathcal{U}^{\prime}}=J^{\mathcal{U}}\oplus
J^{\mathbb{I}_{B\otimes C}}$ and $J^{\mathbb{I}_{B\otimes
C}}=\outerproduct{\Psi^{+}}{\Psi^{+}}_{B\otimes C}$, we have

$\displaystyle\tr[S_{A^{+}}\otimes\mathbb{I}_{B}\otimes\mathbb{I}_{{A^{+}}^{\prime}}\otimes
S_{B^{\prime}}(J^{\mathcal{U}^{\prime}}\otimes J^{\mathcal{U}^{\prime}})]$
(72) $\displaystyle=$
$\displaystyle\tr[S_{A}\otimes\mathbb{I}_{B}\otimes\mathbb{I}_{A^{\prime}}\otimes
S_{B^{\prime}}(J^{\mathcal{U}}\otimes
J^{\mathcal{U}})]+\tr[S_{C}\otimes\mathbb{I}_{B}\otimes\mathbb{I}_{C^{\prime}}\otimes
S_{B^{\prime}}(J^{\mathbb{I}_{B\otimes C}}\otimes J^{\mathbb{I}_{B\otimes
C}})]$ $\displaystyle=$
$\displaystyle\tr[S_{A}\otimes\mathbb{I}_{B}\otimes\mathbb{I}_{A^{\prime}}\otimes
S_{B^{\prime}}(J^{\mathcal{U}}\otimes
J^{\mathcal{U}})]+\tr[S_{C}]\tr[S_{B^{\prime}}]$ $\displaystyle=$
$\displaystyle\tr[S_{A}\otimes\mathbb{I}_{B}\otimes\mathbb{I}_{A^{\prime}}\otimes
S_{B^{\prime}}(J^{\mathcal{U}}\otimes J^{\mathcal{U}})]+(d_{B}^{2}-d)$
$\displaystyle=$ $\displaystyle P_{3}+(d_{B}^{2}-d)\ ,$

where the first equality comes from the fact that both $S_{A^{+}}$ and
$\mathbb{I}_{A^{+}}$ are only supported on $A\otimes A$ and $C\otimes C$, but
not $A\otimes C$ and $C\otimes A$, and hence the $J^{\mathcal{U}}\otimes
J^{\mathbb{I}_{B\otimes C}}$ and $J^{\mathbb{I}_{B\otimes C}}\otimes
J^{\mathcal{U}}$ terms are zero. Observe that, similar to the analysis of
$P_{2}$, the $P_{3}$ is the 2-norm of the Schmidt coefficients

$\displaystyle\tr[S_{A^{+}}\otimes\mathbb{I}_{B}\otimes\mathbb{I}_{{A^{+}}^{\prime}}\otimes
S_{B^{\prime}}(J^{\mathcal{U}^{\prime}}\otimes J^{\mathcal{U}^{\prime}})]$
(73) $\displaystyle=$ $\displaystyle\tr[S_{A^{+}}\otimes\mathbb{I}_{B}\otimes
S_{{A^{+}}^{\prime}}\otimes\mathbb{I}_{B^{\prime}}(J^{S\mathcal{U}^{\prime}}\otimes
J^{S\mathcal{U}^{\prime}})]$ $\displaystyle=$ $\displaystyle\norm{q}_{2}^{2}\
,$

where the output systems ${A^{+}}^{\prime}$ and $B^{\prime}$ are swapped in
the first equality. In summary, we have

$\displaystyle P_{3}$
$\displaystyle=\norm{q}_{2}^{2}-(d_{B}^{2}-d)\geq\norm{q}_{\infty}^{2}-(d_{B}^{2}-d)$
(74)
$\displaystyle\geq(d+1)^{2}(\bar{F}^{S}_{\max}-\frac{1}{d+1})^{2}-(d_{B}^{2}-d)\
,$

Where $\bar{F}^{S}_{\max}$ is the maximum gate fidelity of the extended
unitary $SU^{\prime}$ as defined in (51). Substitute this to (71), we have

$\quantity(\bar{F}_{\max}-\frac{1}{d+1})^{2}+\quantity(\bar{F}^{S}_{\max}-\frac{1}{d+1})^{2}\leq\frac{d^{2}+d_{B}^{2}}{(d+1)^{2}}-\frac{d-1}{d}C_{D}\
.$ (75)

In the case $d_{A}=d_{B}$, we have $d=d_{B}^{2}$, and

$\displaystyle\quantity(\bar{F}_{\max}-\frac{1}{d+1})^{2}+\quantity(\bar{F}^{S}_{\max}-\frac{1}{d+1})^{2}\leq\frac{d}{d+1}-\frac{d-1}{d}C_{D}\leq\quantity(1-\frac{1}{d})(1-C_{D})\
,$ (76)

and the extended unitary $U^{\prime}$ is the same as $U$. It shows that the
maximum gate fidelities $\bar{F}_{\max}$ and $\bar{F}^{S}_{\max}$ are jointly
bounded by $1-C_{D}$.

To obtain a neater but looser bound shown in theorem 2 in the main text, we
start from (71), then observe that $P_{3}$ is positive, and
$\bar{F}_{\max}\leq 1$, such that

$\bar{F}_{\max}^{2}-\frac{2}{d+1}+\quantity(\frac{1}{d+1})^{2}\leq\quantity(\bar{F}_{\max}-\frac{1}{d+1})^{2}\leq\frac{d}{d+1}-\frac{d-1}{d}C_{D}\
.$ (77)

By combining the factors, we have

$\displaystyle\bar{F}_{\max}^{2}$
$\displaystyle\leq\frac{2d+1}{(d+1)^{2}}+\frac{d^{2}+d}{(d+1)^{2}}-\frac{d-1}{d}C_{D}$
(78) $\displaystyle\leq\frac{d^{2}+3d+1}{(d+1)^{2}}-\frac{d-1}{d}C_{D}$
$\displaystyle\leq\frac{d^{2}+3d+1}{(d+1)^{2}}-\frac{d-1}{d+1}C_{D}$
$\displaystyle=\frac{d-1}{d+1}(1-C_{D})+\frac{3d+2}{(d+1)^{2}}$
$\displaystyle\leq(1-C_{D})+\frac{3}{d+1}\ ,$

which proves theorem 2 in the main text.

##  Appendix E Extended Numerical Results

In this section, we provide the extended numerical results for the main text.
In Fig. 9, we show that, if the 4-qubit unitary is generated by a circuit with
a similar structure as our ansatz, our method can achieve a higher fidelity.

Figure 9: _Variational Compilation of 4-qubit unitary that is generated by a
spindle-shaped circuit._ In the main text, we compared our method with direct
quantum compilation for Haar randomly generated 4-qubit unitary. However, as
our ansatz is shallow, it is not expected to compile any 4-qubit unitary with
high fidelity. Here we show that, if the 4-qubit unitary is generated by a
circuit with a similar structure as our ansatz, our method can achieve a
higher fidelity. Similar to the ansatz in the main text, the circuit is
divided into 3 types: 4-qubit ansatzes (orange), 2-qubit ansatzes (red), and
the middle single qubit gates (green). However, the ansatzes $V_{0},V_{1}$,
and $V_{A,0},V_{B,0},V_{A,1},V_{B,1}$ are not repeated, and each of them only
contains one layer of CNOT gates.

For a better understanding of our numerical results, we plot the raw data of
Fig. 9 explicitly in Fig. 10. The solid and dashed lines are the global
fidelities, whose mean and the ranges are used to generate Fig. 9. The dotted
lines are the corresponding cost functions used at each phase of the
optimization.

Figure 10: _Raw data for the 4-qubit unitary generated by a spindle-shaped
circuit._

## References

  * [1] Keshav Pingali, Donald Nguyen, Milind Kulkarni, Martin Burtscher, M Amber Hassaan, Rashid Kaleem, Tsung-Hsien Lee, Andrew Lenharth, Roman Manevich, Mario Mendez-Lojo, Dimitrios Prountzos, and Xin Sui.  The Tao of Parallelism in Algorithms.  In 32nd ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 12–25, 2011.
  * [2] P. W. Trinder, K. Hammond, H.-W. Loidl, and S. L. Peyton Jones.  Algorithm + strategy = parallelism.  J. Funct. Prog., 8(1):23–60, January 1998.
  * [3] Ying Wu and Thomas S Huang.  Capturing articulated human hand motion: A divide-and-conquer approach.  In Proceedings of the Seventh IEEE International Conference on Computer Vision, volume 1, pages 606–611. IEEE, 1999.
  * [4] Peng Wang, Bo Yu, Dongxu Han, Dongliang Sun, and Yue Xiang.  Fast method for the hydraulic simulation of natural gas pipeline networks based on the divide-and-conquer approach.  Journal of Natural Gas Science and Engineering, 50:55–63, 2018\.
  * [5] Adi Botea, Akihiro Kishimoto, and Radu Marinescu.  On the Complexity of Quantum Circuit Compilation.  Proceedings of the International Symposium on Combinatorial Search, 9(1):138–142, 2018.
  * [6] Janusz Kusyk, Samah M. Saeed, and Muharrem Umit Uyar.  Survey on Quantum Circuit Compilation for Noisy Intermediate-Scale Quantum Computers: Artificial Intelligence to Heuristics.  IEEE Trans. Quantum Eng., 2:1–16, 2021.
  * [7] Sumeet Khatri, Ryan LaRose, Alexander Poremba, Lukasz Cincio, Andrew T. Sornborger, and Patrick J. Coles.  Quantum-assisted quantum compiling.  Quantum, 3:140, May 2019.
  * [8] Nikita A. Nemkov, Evgeniy O. Kiktenko, Ilia A. Luchnikov, and Aleksey K. Fedorov.  Efficient variational synthesis of quantum circuits with coherent multi-start optimization.  Quantum, 7:993, May 2023.
  * [9] Diederik P. Kingma and Jimmy Ba.  Adam: A Method for Stochastic Optimization, January 2017.
  * [10] Jarrod R. McClean, Sergio Boixo, Vadim N. Smelyanskiy, Ryan Babbush, and Hartmut Neven.  Barren plateaus in quantum neural network training landscapes.  Nat Commun, 9(1):4812, November 2018.
  * [11] Samson Wang, Enrico Fontana, M. Cerezo, Kunal Sharma, Akira Sone, Lukasz Cincio, and Patrick J. Coles.  Noise-induced barren plateaus in variational quantum algorithms.  Nat Commun, 12(1):6961, November 2021.
  * [12] M. Cerezo and Patrick J. Coles.  Higher Order Derivatives of Quantum Neural Networks with Barren Plateaus.  Quantum Sci. Technol., 6(3):035006, July 2021.
  * [13] K. Mitarai, M. Negoro, M. Kitagawa, and K. Fujii.  Quantum circuit learning.  Phys. Rev. A, 98(3):032309, September 2018.
  * [14] Maria Schuld, Ville Bergholm, Christian Gogolin, Josh Izaac, and Nathan Killoran.  Evaluating analytic gradients on quantum hardware.  Phys. Rev. A, 99(3):032331, March 2019.
  * [15] Jun Li, Xiaodong Yang, Xinhua Peng, and Chang-Pu Sun.  Hybrid Quantum-Classical Approach to Quantum Optimal Control.  Phys. Rev. Lett., 118(15):150503, April 2017.
  * [16] Dawei Lu, Keren Li, Jun Li, Hemant Katiyar, Annie Jihyun Park, Guanru Feng, Tao Xin, Hang Li, Guilu Long, Aharon Brodutch, Jonathan Baugh, Bei Zeng, and Raymond Laflamme.  Enhancing quantum control by bootstrapping a quantum processor of 12 qubits.  npj Quantum Inf, 3(1):1–7, October 2017.
  * [17] E. Santos and M. Ferrero.  Linear entropy and Bell inequalities.  Phys. Rev. A, 62(2):024101, July 2000.
  * [18] Vivek V. Shende, Igor L. Markov, and Stephen S. Bullock.  Minimal Universal Two-qubit Quantum Circuits.  Phys. Rev. A, 69(6):062321, June 2004.
  * [19] The $\alpha=0.01$, $\beta_{1}=0.8$, $\beta_{2}=0.9$.
  * [20] Yuxuan Du, Min-Hsiu Hsieh, Tongliang Liu, and Dacheng Tao.  Expressive power of parametrized quantum circuits.  Phys. Rev. Research, 2(3):033125, July 2020.
  * [21] Lucas Lamata, Adrian Parra-Rodriguez, Mikel Sanz, and Enrique Solano.  Digital-analog quantum simulations with superconducting circuits.  Advances in Physics: X, 3(1):1457981, January 2018.
  * [22] Max Tegmark.  Consciousness as a state of matter.  Chaos, Solitons & Fractals, 76:238–270, 2015.
  * [23] A. Jamiołkowski.  Linear transformations which preserve trace and positive semidefiniteness of operators.  Reports on Mathematical Physics, 3(4):275–278, December 1972.
  * [24] John Watrous.  The Theory of Quantum Information.  Cambridge University Press, 1 edition, April 2018.
  * [25] G. Chiribella, G. M. D’Ariano, and P. Perinotti.  Quantum Circuit Architecture.  Phys. Rev. Lett., 101(6):060401, August 2008.
  * [26] Giulio Chiribella, Giacomo Mauro D’Ariano, and Paolo Perinotti.  Theoretical framework for quantum networks.  Phys. Rev. A, 80(2):022339, August 2009.
  * [27] Adriano Barenco, André Berthiaume, David Deutsch, Artur Ekert, Richard Jozsa, and Chiara Macchiavello.  Stabilization of Quantum Computations by Symmetrization.  SIAM J. Comput., 26(5):1541–1557, October 1997.
  * [28] Juan Carlos Garcia-Escartin and Pedro Chamorro-Posada.  The SWAP test and the Hong-Ou-Mandel effect are equivalent.  Phys. Rev. A, 87(5):052330, May 2013.
  * [29] Ryan LaRose, Arkin Tikku, Étude O’Neel-Judy, Lukasz Cincio, and Patrick J. Coles.  Variational quantum state diagonalization.  npj Quantum Inf, 5(1):57, June 2019.