# Quantum-assisted quantum compiling

Sumeet Khatri  Theoretical Division, Los Alamos National Laboratory, Los
Alamos, NM USA.  Hearne Institute for Theoretical Physics and Department of
Physics and Astronomy, Louisiana State University, Baton Rouge, LA USA.  Ryan
LaRose  Theoretical Division, Los Alamos National Laboratory, Los Alamos, NM
USA.  Department of Computational Mathematics, Science, and Engineering and
Department of Physics and Astronomy, Michigan State University, East Lansing,
MI USA.  Alexander Poremba  Theoretical Division, Los Alamos National
Laboratory, Los Alamos, NM USA.  Computing and Mathematical Sciences,
California Institute of Technology, Pasadena, CA USA.  Lukasz Cincio
Theoretical Division, Los Alamos National Laboratory, Los Alamos, NM USA.
Andrew T. Sornborger  Information Sciences, Los Alamos National Laboratory,
Los Alamos, NM USA.  Patrick J. Coles  Theoretical Division, Los Alamos
National Laboratory, Los Alamos, NM USA.

###### Abstract

Compiling quantum algorithms for near-term quantum computers (accounting for
connectivity and native gate alphabets) is a major challenge that has received
significant attention both by industry and academia. Avoiding the exponential
overhead of classical simulation of quantum dynamics will allow compilation of
larger algorithms, and a strategy for this is to evaluate an algorithm’s cost
on a quantum computer. To this end, we propose a variational hybrid quantum-
classical algorithm called quantum-assisted quantum compiling (QAQC). In QAQC,
we use the overlap between a target unitary $U$ and a trainable unitary $V$ as
the cost function to be evaluated on the quantum computer. More precisely, to
ensure that QAQC scales well with problem size, our cost involves not only the
global overlap ${\rm Tr}(V^{\dagger}U)$ but also the local overlaps with
respect to individual qubits. We introduce novel short-depth quantum circuits
to quantify the terms in our cost function, and we prove that our cost cannot
be efficiently approximated with a classical algorithm under reasonable
complexity assumptions. We present both gradient-free and gradient-based
approaches to minimizing this cost. As a demonstration of QAQC, we compile
various one-qubit gates on IBM’s and Rigetti’s quantum computers into their
respective native gate alphabets. Furthermore, we successfully simulate QAQC
up to a problem size of 9 qubits, and these simulations highlight both the
scalability of our cost function as well as the noise resilience of QAQC.
Future applications of QAQC include algorithm depth compression, black-box
compiling, noise mitigation, and benchmarking.

##  1 Introduction

Factoring [1], approximate optimization [2], and simulation of quantum systems
[3] are some of the applications for which quantum computers have been
predicted to provide speedups over classical computers. Consequently, the
prospect of large-scale quantum computers has generated interest from various
sectors, such as the financial and pharmaceutical industries. Currently
available quantum computers are not large-scale but rather have been called
noisy intermediate-scale quantum (NISQ) computers [4]. A proof-of-principle
demonstration of quantum supremacy with a NISQ device may be coming soon [5,
6]. Nevertheless, demonstrating the practical utility of NISQ computers
appears to be a more difficult task.

While improvements to NISQ hardware are continuously being made by
experimentalists, quantum computing theorists can contribute to the utility of
NISQ devices by developing software. This software would aim to adapt textbook
quantum algorithms (e.g., for factoring or quantum simulation) to NISQ
constraints. NISQ constraints include: (1) limited numbers of qubits, (2)
limited connectivity between qubits, (3) restricted (hardware-specific) gate
alphabets, and (4) limited circuit depth due to noise. Algorithms adapted to
these constraints will likely look dramatically different from their textbook
counterparts.

These constraints have increased the importance of the field of quantum
compiling. In classical computing, a compiler is a program that converts
instructions into assembly language so that they can be read and executed by a
computer. Similarly, a quantum compiler would take a high-level algorithm and
convert it into a lower-level form that could be executed on a NISQ device.
Already, a large body of literature exists on classical approaches for quantum
compiling, e.g., using temporal planning [7, 8], machine learning [9], and
other techniques [10, 11, 12, 13, 14, 15, 16, 17].

A recent exciting idea is to use quantum computers themselves to train
parametrized quantum circuits, as proposed in Refs. [2, 18, 19, 20, 21, 22,
23, 24, 25]. The cost function to be minimized essentially defines the
application. For example, in the variational quantum eigensolver (VQE) [18]
and the quantum approximate optimization algorithm (QAOA) [2], the application
is ground state preparation, and hence the cost is the expectation value of
the associated Hamiltonian. Another example is training error-correcting codes
[19], where the cost is the average code fidelity. In light of these works, it
is natural to ask: what is the relevant cost function for the application of
quantum compiling?

In this work, we introduce quantum-assisted quantum compiling (QAQC,
pronounced “Quack”). The goal of QAQC is to compile a (possibly unknown)
target unitary to a trainable quantum gate sequence. A key feature of QAQC is
the fact that the cost is computed directly on the quantum computer. This
leads to an exponential speedup (in the number of qubits involved in the gate
sequence) over classical methods to compute the cost, since classical
simulation of quantum dynamics is exponentially slower than quantum
simulation. Consequently, one should be able to optimally compile larger-scale
gate sequences using QAQC, whereas classical approaches to optimal quantum
compiling will be limited to smaller gate sequences.111We note that classical
compilers may be applied to large-scale quantum algorithms, but they are
limited to local compiling. We thus emphasize the distinction between
translating the algorithm to the native alphabet with simple, local compiling
and optimal compiling. Local compiling may reach partial optimization but in
order to discover the shortest circuit one may need to use a holistic
approach, where the entire algorithm is considered, which requires a quantum
computer for compiling.

We carefully define a cost function for QAQC that satisfies the following
criteria:

  1. 1.

It is faithful (vanishing if and only if the compilation is exact);

  2. 2.

It is efficient to compute on a quantum computer;

  3. 3.

It has an operational meaning;

  4. 4.

It scales well with the size of the problem.

A potential candidate for a cost function satisfying these criteria is the
Hilbert-Schmidt inner product between a target unitary $U$ and a trainable
unitary $V$:

$\displaystyle\langle V,U\rangle={\rm Tr}(V^{\dagger}U).$ (1)

It turns out, however, that this cost function does not satisfy the last
criterion. We thus use Eq. (1) only for small-scale problems. For general,
large-scale problems, we define a cost function satisfying all criteria. This
cost involves a weighted average of the global overlap in (1) with localized
overlaps, which quantify the overlap between $U$ and $V$ with respect to
individual qubits.

We prove that computing our cost function is $\mathsf{DQC1}$-hard, where
$\mathsf{DQC1}$ is the class of problems that can be efficiently solved in the
one-clean-qubit model of computation [26]. Since $\mathsf{DQC1}$ is
classically hard to simulate [27], this implies that no classical algorithm
can efficiently compute our cost function. We remark that an alternative cost
function might be a worst-case distance measure (such as diamond distance),
but such measures are known to be $\mathsf{QIP}$-complete [28] and hence would
violate criterion 2 in our list above. In this sense, our cost function
appears to be ideal.

Furthermore, we present novel short-depth quantum circuits for efficiently
computing the terms in our cost function. Our circuits achieve short depth by
avoiding implementing controlled versions of $U$ and $V$, and by implementing
$U$ and $V$ in parallel. We also present, in Appendix F, circuits that compute
the gradient of our cost function. One such circuit is a generalization of the
well-known Power of One Qubit [26] that we call the Power of Two Qubits.

As a proof-of-principle, we implement QAQC on both IBM’s and Rigetti’s quantum
computers, and we compile various one-qubit gates to the native gate alphabets
used by these hardwares. To our knowledge, this is the first compilation of a
target unitary with cost evaluation on actual NISQ hardware. In addition, we
successfully implement QAQC on both a noiseless and noisy simulator for
problems as large as 9-qubit unitaries. These larger scale implementations
illustrate the scalability of our cost function, and in the case of the noisy
simulator, show a somewhat surprising resilience to noise.

Figure 1: Potential applications of QAQC. Here,  denotes the $z$-rotation gate
$R_{z}(\theta)$, while  represents the $\pi/2$-pulse given by the $x$-rotation
gate $R_{x}(\pi/2)$. Both gates are natively implemented on commercial
hardware [29, 30]. (a) Compressing the depth of a given gate sequence $U$ to a
shorter-depth gate sequence $V$ in terms of native hardware gates. (b)
Uploading a black-box unitary. The black box could be an analog unitary
$U=e^{-i\mathcal{H}t}$, for an unknown Hamiltonian $\mathcal{H}$, that one
wishes to convert into a gate sequence to be run on a gate-based quantum
computer. (c) Training algorithms in the presence of noise to learn noise-
resilient algorithms (e.g., via gates that counteract the noise). Here, the
unitary $U$ is performed on high-quality, pristine qubits and $V$ is performed
on noisy ones. (d) Benchmarking a quantum computer by compiling a unitary $U$
on noisy qubits and learning the gate sequence $V$ on high-quality qubits.

In what follows, we first discuss several applications of interest for QAQC.
Section 3 provides a general outline of the QAQC algorithm. Section 4 presents
our short-depth circuits for cost evaluation on a quantum computer. Section 5
states that our cost function is classically hard to simulate. Sections 6 and
7, respectively, present small-scale and larger-scale implementations of QAQC.

##  2 Applications of QAQC

Figure 1 illustrates four potential applications of QAQC. Suppose that there
exists a quantum algorithm to perform some task, but its associated gate
sequence is longer than desired. As shown in Fig. 1(a), it is possible to use
QAQC to shorten the gate sequence by accounting for the NISQ constraints of
the specific computer. This depth compression goes beyond the capabilities of
classical compilers.

As a simple example, consider the quantum Fourier transform on $n$ qubits. Its
textbook algorithm is written in terms of Hadamard gates and controlled-
rotation gates [31], which may need to be compiled into the native gate
alphabet. The number of gates in the textbook algorithm is $O(n^{2})$, so one
could use a classical compiler to locally compile each gate. But this could
lead to a sub-optimal depth since the compilation starts from the textbook
structure. In contrast, QAQC is unbiased with respect to the structure of the
gate sequence, taking a holistic approach to compiling as opposed to a local
one. Hence, in principle, it can learn the optimal gate sequence for given
hardware. Note that classical compilers cannot take this holistic approach for
large $n$ due to the exponential scaling of the matrix representations of the
gates.

Alternatively, consider the problem of simulating the dynamics of a given
quantum system with an unknown Hamiltonian $\mathcal{H}$ (via
$e^{-i\mathcal{H}t}$) on a quantum computer. We call this problem black-box
uploading because by simulating the black-box, i.e., the unitary
$e^{-i\mathcal{H}t}$, we are “uploading” the unitary onto the quantum
computer. This scenario is depicted in Fig. 1(b). QAQC could be used to
convert an analog black-box unitary into a gate sequence on a digital quantum
computer.

Finally, we highlight two additional applications that are the opposites of
each other. These two applications can be exploited when the quantum computer
has some pristine qubits (qubits with low noise) and some noisy qubits. We
emphasize that, in this context, “noisy qubits” refers to coherent noise such
as systematic gate biases, where the gate rotation angles are biased in a
particular direction. In contrast, we consider incoherent noise (e.g., $T_{1}$
and $T_{2}$ noise) later in this article, see Section 7.2.

Consider Fig. 1(c). Here, the goal is to implement a CNOT gate on two noisy
qubits. Due to the noise, to actually implement a true CNOT, one has to
physically implement a dressed CNOT, i.e., a CNOT surrounded by one-qubit
unitaries. QAQC can be used to learn the parameters in these one-qubit
unitaries. By choosing the target unitary $U$ to be a CNOT on a pristine
(i.e., noiseless) pair of qubits, it is possible to learn the unitary $V$ that
needs to be applied to the noisy qubits in order to effectively implement a
CNOT. We call this application noise-tailored algorithms, since the learned
algorithms are robust to the noise process on the noisy qubits.

Figure 1(d) depicts the opposite process, which is benchmarking. Here, the
unitary $U$ acts on a noisy set of qubits, and the goal is to determine what
the equivalent unitary $V$ would be if it were implemented on a pristine set
of qubits. This essentially corresponds to learning the noise model, i.e.,
benchmarking the noisy qubits.

##  3 The QAQC Algorithm

###  3.1 Approximate compiling

The goal of QAQC is to take a (possibly unknown) unitary $U$ and return a gate
sequence $V$, executable on a quantum computer, that has approximately the
same action as $U$ on any given input state (up to possibly a global phase
factor). The notion of approximate compiling [32, 33, 34, 35, 36, 37] requires
an operational figure-of-merit that quantifies how close the compilation is to
exact. A natural candidate is the probability for the evolution under $V$ to
mimic the evolution under $U$. Hence, consider the overlap between
${\left|{\psi(U)}\right\rangle}\coloneqq U{\left|{\psi}\right\rangle}$ and
${\left|{\psi(V)}\right\rangle}\coloneqq V{\left|{\psi}\right\rangle}$,
averaged over all input states ${\left|{\psi}\right\rangle}$. This is the
fidelity averaged over the Haar distribution,

$\overline{F}(U,V)\coloneqq\int_{\psi}|\langle\psi(V)|\psi(U)\rangle|^{2}~{}\text{d}\psi\,.$
(2)

We call $V$ an exact compilation of $U$ if $\overline{F}(U,V)=1$. If
$\overline{F}(U,V)\geqslant 1-\varepsilon$, where $\varepsilon\in[0,1]$, then
we call $V$ an $\varepsilon$-approximate compilation of $U$, or simply an
approximate compilation of $U$.

As we will see, the quantity $\overline{F}(U,V)$ has a connection to our cost
function, defined below, and hence our cost function has operational relevance
to approximate compiling. Minimizing our cost function is related to
maximizing $\overline{F}(U,V)$, and thus is related to compiling to a better
approximation.

QAQC achieves approximate compiling by training a gate sequence $V$ of a fixed
length $L$, which may even be shorter than the length required to exactly
compile $U$. As one increases $L$, one can further minimize our cost function.
The length $L$ can therefore be regarded as a parameter that can be tuned to
obtain arbitrarily good approximate compilations of $U$.

Figure 2: Outline of our variational hybrid quantum-classical algorithm, in
which we optimize over gate structures and continuous gate parameters in order
to perform QAQC for a given input unitary $U$. We take two approaches towards
structure optimization: (a) For small problem sizes, we allow the gate
structure to vary for a given gate sequence length $L$, which in general leads
to an approximate compilation of $U$. To obtain a better approximate
compilation, the best structure obtained can be concatenated with a new
sequence of a possibly different length, whose structure can vary. For each
iteration of the continuous parameter optimization, we calculate the cost
using the Hilbert-Schmidt Test (HST); see Sec. 4.1. (b) For large problem
sizes, we fix the gate structure using an ansatz consisting of layers of two-
qubit gates. By increasing the number of layers, we can obtain better
approximate compilations of $U$. For each iteration of the continuous
parameter optimization, we calculate the cost using the Local Hilbert-Schmidt
Test (LHST); see Sec. 4.2.

###  3.2 Discrete and continuous parameters

The gate sequence $V$ should be expressed in terms of the native gates of the
quantum computer being used. Consider an alphabet
$\mathcal{A}=\\{G_{k}(\alpha)\\}_{k}$ of gates $G_{k}(\alpha)$ that are native
to the quantum computer of interest. Here, $\alpha\in\mathbb{R}$ is a
continuous parameter, and $k$ is a discrete parameter that identifies the type
of gate and which qubits it acts on. For a given quantum computer, the problem
of compiling $U$ to a gate sequence of length $L$ is to determine

$(\boldsymbol{\alpha}_{\text{opt}},\boldsymbol{k}_{\text{opt}})\coloneqq\operatorname*{arg\,min}_{(\boldsymbol{\alpha},\boldsymbol{k})}C(U,V_{\boldsymbol{k}}(\boldsymbol{\alpha})),$
(3)

where

$V_{\boldsymbol{k}}(\boldsymbol{\alpha})=G_{k_{L}}(\alpha_{L})G_{k_{L-1}}(\alpha_{L-1})\dotsb
G_{k_{1}}(\alpha_{1})$ (4)

is the trainable unitary. Here, $V_{\boldsymbol{k}}(\boldsymbol{\alpha})$ is a
function of the sequence $\boldsymbol{k}=(k_{1},\dotsc,k_{L})$ of parameters
describing which gates from the native gate set are used and of the continuous
parameters $\boldsymbol{\alpha}=(\alpha_{1},\dotsc,\alpha_{L})$ associated
with each gate. The function $C(U,V_{\boldsymbol{k}}(\boldsymbol{\alpha}))$ is
the cost, which quantifies how close the trained unitary is to the target
unitary. We define the cost below to have the properties: $0\leqslant
C(U,V)\leqslant 1$ for all unitaries $U$ and $V$, and $C(U,V)=0$ if and only
if $U=V$ (possibly up to a global phase factor).

The optimization in (3) contains two parts: discrete optimization over the
finite set of gate structures parameterized by $\boldsymbol{k}$, and
continuous optimization over the parameters $\boldsymbol{\alpha}$
characterizing the gates within the structure. Our quantum-classical hybrid
strategy to perform the optimization in (3) is illustrated in Fig. 2. In the
next subsection, we present a general, ansatz-free approach to optimizing our
cost function, which may be useful for systems with a small number of qubits.
In the subsection following that, we present an ansatz-based approach that
would allow the extension to larger system sizes. In each case, we perform the
continuous parameter optimization using gradient-free methods as described in
Appendix E. We also discuss a method for gradient-based continuous parameter
optimization in Appendix F.

###  3.3 Small problem sizes

Suppose $U$ and $V$ act on a $d$-dimensional space of $n$ qubits, so that
$d=2^{n}$. To perform the continuous parameter optimization in (3), we define
the cost function

$\displaystyle C_{\text{HST}}(U,V)$ $\displaystyle\coloneqq
1-\frac{1}{d^{2}}\left|\left<V,U\right>\right|^{2}$ (5)
$\displaystyle=1-\frac{1}{d^{2}}|{\rm Tr}(V^{\dagger}U)|^{2},$

where HST stands for “Hilbert-Schmidt Test” and refers to the circuit used to
evaluate the cost, which we introduce in Sec. 4.1. Note that the quantity
$\frac{1}{d^{2}}\left|\left<V,U\right>\right|^{2}$ is simply the fidelity
between the pure states obtained by applying $U$ and $V$ to one half of a
maximally entangled state. Consequently, it has an operational meaning in
terms of $\overline{F}(U,V)$. Indeed, it can be shown [38, 39] that

$C_{\text{HST}}(U,V)=\frac{d+1}{d}\left(1-\overline{F}(U,V)\right)\,.$ (6)

Also note that for any two unitaries $U$ and $V$, $C_{\text{HST}}(U,V)=0$ if
and only if $U$ and $V$ differ by a global phase factor, i.e.,
$V=e^{i\varphi}U$ for some $\varphi\in\mathbb{R}$. By minimizing
$C_{\text{HST}}$, we thus learn an equivalent unitary $V$ up to a global
phase.

Now, to perform the optimization over gate structures in (3), one strategy is
to search over all possible gate structures for a gate sequence length $L$,
which can be allowed to vary during the optimization. As the set of gate
structures grows exponentially with the number of gates $L$, such a brute
force search over all gate structures in order to obtain the best one is
intractable in general. To efficiently search through this exponentially large
space, we adopt an approach based on simulated annealing. (An alternative
approach is genetic optimization, which has been implemented previously to
classically optimize quantum gate sequences [40].)

Our simulated annealing approach starts with a random gate structure, then
performs continuous optimization over the parameters $\boldsymbol{\alpha}$
that characterize the gates in order to minimize the cost function. We then
perform a structure update that involves randomly replacing a subset of gates
in the sequence with new gates (which can be done in a way such that the
sequence length can increase or decrease) and re-optimizing the cost function
over the continuous parameters $\boldsymbol{\alpha}$. If this structure change
produces a lower cost, then we accept the change. If the cost increases, then
we accept the change with probability decreasing exponentially in the
magnitude of the cost difference. We iterate this procedure until the cost
converges or until a maximum number of iterations is reached.

With a fixed gate sequence length $L$, the approach outlined above will in
general lead to an approximate compilation of $U$, which in many cases is
sufficient. One strategy for obtaining better and better approximate
compilations of $U$ is a layered approach illustrated in Fig. 2(a). In this
approach, we consider a particular gate sequence length $L$ and perform the
full structure optimization, as outlined above, to obtain an (approximate)
length-$L$ compilation of $U$. The optimal gate sequence structure thus
obtained can then be concatenated with a new sequence of a possibly different
(but fixed) length, whose structure can vary. By performing the continuous
parameter optimization over the entire longer gate sequence, and performing
the structure optimization over the new additional segment of the gate
sequence, we can obtain a better approximate compilation of $U$. Iterating
this procedure can then lead to increasingly better approximate compilations
of $U$.

###  3.4 Large problem sizes

We emphasize two potential issues with scaling the above approach to large
problem sizes.

First, one may want a guarantee that there exists an exact compilation of $U$
within a polynomial size search space for $V$. When performing full structure
optimization, as above, the search space size grows exponentially in the
length $L$ of the gate sequence. This implies that the search space size grows
exponentially in $n$, if one chooses $L$ to grow polynomially in $n$. Indeed,
one would typically require $L$ to grow polynomially in $n$ if one is
interested in exact compilation, since the number of gates in $U$ itself grows
polynomially in $n$ for many applications. (Note that this issue arises if one
insists on exact, instead of approximate, compiling.)

Second, and arguably more importantly, the cost $C_{\text{HST}}(U,V)$ is
exponentially fragile. The inner product between $U$ and $V$ will be
exponentially suppressed for random choices of $V$, which means that
$C_{\text{HST}}(U,V)$ will be very close to one for most unitaries $V$. Hence,
for random unitaries $V$, the number of calls to the quantum computer needed
to resolve differences in the cost $C_{\text{HST}}(U,V)$ to a given precision
will grow exponentially.

The first issue can be addressed with an efficiently parameterized ansatz for
$V$. With an ansatz, only the continuous parameters $\boldsymbol{\alpha}$ need
to be optimized in $V$. The $\boldsymbol{k}$ parameters are fixed, which means
that structure updates are not required. This fixed structure approach is
depicted in Fig. 2(b). One can choose an ansatz such that the number of
parameters needed to represent the target unitary $U$ is only a polynomial
function of $n$. Hence, one should allow the ansatz $A(U)$ to be application
specific, i.e., to be a function of $U$. As an example, if
$U=e^{-i\mathcal{H}t}$ for a local Hamiltonian $\mathcal{H}$, one could choose
the ansatz to involve a polynomial number of local interactions. Due to the
application-specific nature of the ansatz, the problem is a complex one, hence
we leave the issue of finding efficient ansatzes for future work.

Nevertheless, we show a concrete example of a potential ansatz for $V$ in Fig.
3. The ansatz is defined by a number $\ell$ of layers, with each layer being a
gate sequence of depth two consisting of two-qubit gates acting on neighboring
qubits. Consider the following argument. In QAQC, the unitary $U$ to be
compiled is executed on the quantum computer, so it must be efficiently
implementable, i.e., the gate count is polynomial in $n$. Next, note that the
gate sequence used to implement $U$ can be compiled into in the ansatz in Fig.
3 with only polynomial overhead. This implies that the ansatz in Fig. 3 could
exactly describe $U$ in only a polynomial number of layers and would hence
eliminate the need to search through an exponentially large space. We remark
that the ansatz in Fig. 3 may be particularly useful for applications
involving compiling quantum simulations of physically relevant systems, as the
structure resembles that of the Suzuki-Trotter decomposition [41] for nearest-
neighbor Hamiltonians.

Figure 3: (a) One layer of the ansatz for the trainable unitary $V$ in the
case of four qubits. The gate sequence in the layer consists of a two-qubit
gate acting on the first and second qubits, the third and fourth qubits, the
second and third qubits, and the first and fourth qubits. (b) The full ansatz
defining the trainable unitary $V$ consists of a particular number $\ell$ of
the layer in (a). Shown is two layers in the case of four qubits.

Let us now consider the second issue mentioned above: the exponentially
suppressed inner product between $U$ and $V$ for large $n$. To address this,
we propose an alternative cost function involving a weighted average between
the function in (5) and a “local” cost function:

$C_{q}(U,V)\coloneqq qC_{\text{HST}}(U,V)+(1-q)C_{\text{LHST}}(U,V),$ (7)

where $0\leqslant q\leqslant 1$ and

$C_{\text{LHST}}(U,V)\coloneqq\frac{1}{n}\sum_{j=1}^{n}C_{\text{LHST}}^{(j)}(U,V)=1-\overline{F_{e}}.$
(8)

Here, LHST stands for “Local Hilbert-Schmidt Test”, referring to the circuit
discussed in Sec. 4.2 that is used to compute this function. Also,
$\overline{F_{e}}\coloneqq\frac{1}{n}\sum_{j=1}^{n}F_{e}^{(j)}$, where the
quantities $F_{e}^{(j)}$ are entanglement fidelities (hence the notation
$F_{e}$) of local quantum channels $\mathcal{E}_{j}$ defined in Sec. 4.2.
Hence, $C_{\text{LHST}}(U,V)$ is a sum of local costs, where each local cost
is written as a local entanglement fidelity:
$C_{\text{LHST}}^{(j)}(U,V)=1-F_{e}^{(j)}$. Expressing the overall cost as sum
of local costs is analogous to what is done in the variational quantum
eigensolver [18], where the overall energy is expressed as a sum of local
energies. The functions $C_{\text{LHST}}^{(j)}$ are local in the sense that
only two qubits need to be measured in order to calculate each one of them.
This is unlike the function $C_{\text{HST}}$, whose calculation requires the
simultaneous measurement of $2n$ qubits.

The cost function $C_{q}$ in (7) is a weighted average between the “global”
cost function $C_{\text{HST}}$ and the local cost function $C_{\text{LHST}}$,
with $q$ representing the weight given to the global cost function. The weight
$q$ can be chosen according to the size of the problem: for a relatively small
number of qubits, we would let $q=1$. As the number of qubits increases, we
would slowly decrease $q$ to mitigate the suppression of the inner product
between $U$ and $V$.

To see why $C_{\text{LHST}}$ can be expected to deal with the issue of an
exponentially suppressed inner product for large $n$, consider the following
example. Suppose the unitary $U$ to be compiled is the tensor product
$U=U_{1}\otimes U_{2}\otimes\dotsb\otimes U_{n}$ of unitaries $U_{j}$ acting
on qubit $j$, and suppose we take the tensor product $V=V_{1}\otimes
V_{2}\otimes\dotsb\otimes V_{n}$ as the trainable unitary. We get that
$C_{\text{HST}}(U,V)=1-\prod_{j=1}^{n}r_{j}$, where $r_{j}=(1/4)|{\rm
Tr}(V_{j}^{\dagger}U_{j})|^{2}$. Since each $r_{j}$ will likely be less than
one for a random choice of $V_{j}$, then their product will be small for large
$n$. Consequently a very large portion of the cost landscape will have
$C_{\text{HST}}(U,V)\approx 1$ and hence will have a vanishing gradient.
However, the cost function $C_{\text{LHST}}$ is defined such that
$C_{\text{LHST}}(U,V)=1-\frac{1}{n}\sum_{j=1}^{n}r_{j}$, so that we obtain an
average of the $r_{j}$ quantities rather than a product. Taking the average
instead of the product leads to a gradient that is not suppressed for large
$n$.

More generally, for any $U$ and $V$, the quantity $\overline{F_{e}}$, which is
responsible for the variability in $C_{\text{LHST}}$, can be made non-
vanishing by adding local unitaries to $V$. In particular, for a given $U$ and
$V$, it is straightforward to show that for all $j\in\\{1,2,\dotsc,n\\}$ there
exists a unitary $V_{j}$ acting on qubit $j$ such that
$F_{e}^{(j)}\geqslant\frac{1}{4}$ for the gate sequence given by
$V^{\prime}=V_{j}V$. In other words, there exists a local unitary $V_{j}$ that
can be added to the trainable gate sequence $V$ such that
$C_{\text{LHST}}^{(j)}(U,V_{j}V)\leqslant\frac{3}{4}$. This implies that, with
the appropriate local unitary applied to each qubit at the end of the
trainable gate sequence, the local cost function $C_{\text{LHST}}$ can always
be decreased to no greater than $\frac{3}{4}$. Note that local unitaries
cannot be used in this way to decrease the global cost function
$C_{\text{HST}}$, i.e., to make the second term in (5) non-vanishing.

Finally, one can show (See Appendix C) that
$C_{\text{LHST}}\geqslant(1/n)C_{\text{HST}}$. Combining this with Eq. (6)
gives

$\displaystyle C_{q}(U,V)$
$\displaystyle\geqslant\left(\frac{1-q+nq}{n}\right)\left(\frac{d+1}{d}\right)(1-\overline{F}(U,V))\,,$
(9)

which implies that

$\overline{F}(U,V)\geqslant
1-\left(\frac{n}{1-q+nq}\right)\left(\frac{d}{d+1}\right)C_{q}(U,V).$ (10)

Hence, the cost function $C_{q}$ retains an operational meaning for the task
of approximate compiling, since it provides a bound on the average fidelity
between $U$ and $V$.

###  3.5 Special case of a fixed input state

An important special case of quantum compiling is when the target unitary $U$
happens to appear at the beginning of one’s quantum algorithm, and hence the
state that one inputs to $U$ is fixed. For many quantum computers, this input
state is ${\left|{\psi_{0}}\right\rangle}={\left|{0}\right\rangle}^{\otimes
n}$. We emphasize that many use cases of QAQC do not fall under this special
case, since one is often interested in compiling unitaries that do not appear
at the beginning of one’s algorithm. For example, one may be interested in the
optimal compiliation of a controlled-unitary, but such a unitary would never
appear at the beginning of an algorithm since its action would be trivial.
Nevertheless we highlight this special case because QAQC can potentially be
simplified in this case. In addition, this special case was very recently
explored in Ref. [42] after the completion of our article.

In this special scenario, a natural cost function would be

$C_{\text{fixed
input}}=1-|\langle\psi_{0}|UV^{\dagger}|\psi_{0}\rangle|^{2}\,.$ (11)

This could be evaluated on a quantum computer in two possible ways. One way is
to apply $U$ and then $V^{\dagger}$ to the ${\left|{\psi_{0}}\right\rangle}$
state and then measure the probability to be in the
${\left|{\psi_{0}}\right\rangle}$ state. Another way is to apply $U$ to one
copy of ${\left|{\psi_{0}}\right\rangle}$ and $V$ to another copy of
${\left|{\psi_{0}}\right\rangle}$, and then measure the overlap [9, 43]
between these two states.

However, this cost function would not scale well for the same reason discussed
above that our $C_{\text{HST}}$ cost does not scale well, i.e., its gradient
can vanish exponentially. Again, one can fix this issue with a local cost
function. Assuming
${\left|{\psi_{0}}\right\rangle}={\left|{0}\right\rangle}^{\otimes n}$, this
local cost can take the form:

$C_{\text{fixed
input}}^{\text{local}}=1-\frac{1}{n}\sum_{j=1}^{n}p_{0}^{(j)}\,,$ (12)

where

$p_{0}^{(j)}={\rm
Tr}[({\left|{0}\right\rangle}\\!{\left\langle{0}\right|}_{j}\otimes\mathbbm{1})V^{\dagger}U{\left|{\psi_{0}}\right\rangle}\\!{\left\langle{\psi_{0}}\right|}U^{\dagger}V]$
(13)

is the probability to obtain the zero measurement outcome on qubit $j$ for the
state $V^{\dagger}U{\left|{\psi_{0}}\right\rangle}$.

We remark that the two cost functions in (11) and (12) can each be evaluated
with quantum circuits on only $n$ qubits. This is in contrast to
$C_{\text{HST}}$ and $C_{\text{LHST}}$, whose evaluation involves quantum
circuits with $2n$ qubits (see the next section for the circuits). This
reduction in resource requirements is the main reason why we highlight this
special case.

##  4 Cost evaluation circuits

In this section, we present short-depth circuits for evaluating the functions
in (5) and (8) and hence for evaluating the overall cost in (7). We note that
these circuits are also interesting outside of the scope of QAQC, and they
likely have applications in other areas.

In addition, in Appendix F, we present circuits for computing the gradient of
the cost function, including a generalization of the Power-of-one-qubit
circuit [26] that computes both the real and imaginary parts of $\langle
U,V\rangle$.

###  4.1 Hilbert-Schmidt Test

Consider the circuit in Fig. 4(a). Below we show that this circuit computes
$|{\rm Tr}(V^{\dagger}U)|^{2}$, where $U$ and $V$ are $n$-qubit unitaries. The
circuit involves $2n$ qubits, where we call the first (second) $n$-qubit
system $A$ ($B$).

The first step in the circuit is to create a maximally entangled state between
$A$ and $B$, namely, the state

$\displaystyle{\left|{\Phi^{+}}\right\rangle}_{AB}=\frac{1}{\sqrt{d}}\sum_{\boldsymbol{j}}{\left|{\boldsymbol{j}}\right\rangle}_{A}\otimes{\left|{\boldsymbol{j}}\right\rangle}_{B}\,,$
(14)

where $\boldsymbol{j}=(j_{1},j_{2},...,j_{n})$ is a vector index in which each
component $j_{k}$ is chosen from $\\{0,1\\}$. The first two gates in Fig.
4(a)—the Hadamard gates and the CNOT gates (which are performed in parallel
when acting on distinct qubits)—create the ${\left|{\Phi^{+}}\right\rangle}$
state.

The second step is to act with $U$ on system $A$ and with $V^{*}$ on system
$B$. ($V^{*}$ is the complex conjugate of $V$, where the complex conjugate is
taken in the standard basis.) Note that these two gates are performed in
parallel. This gives the state

$\displaystyle(U\otimes
V^{*}){\left|{\Phi^{+}}\right\rangle}_{AB}=\frac{1}{\sqrt{d}}\sum_{\boldsymbol{j}}U{\left|{\boldsymbol{j}}\right\rangle}_{A}\otimes
V^{*}{\left|{\boldsymbol{j}}\right\rangle}_{B}\,.$ (15)

We emphasize that the unitary $V^{*}$ is implemented on the quantum computer,
not $V$ itself. (See Appendix A for elaboration on this point.)

The third and final step is to measure in the Bell basis. This corresponds to
undoing the unitaries (the CNOTs and Hadamards) used to prepare
${\left|{\Phi^{+}}\right\rangle}$ and then measuring in the standard basis. At
the end, we are only interested in estimating a single probability: the
probability for the Bell-basis measurement to give the
${\left|{\Phi^{+}}\right\rangle}$ outcome, which corresponds to the all-zeros
outcome in the standard basis. The amplitude associated with this probability
is

$\displaystyle\langle\Phi^{+}\hskip 1.0pt|U\otimes V^{*}|\hskip
1.0pt\Phi^{+}\rangle$ $\displaystyle=\langle\Phi^{+}\hskip
1.0pt|UV^{\dagger}\otimes\mathbbm{1}|\hskip 1.0pt\Phi^{+}\rangle$ (16)
$\displaystyle=\frac{1}{d}{\rm Tr}(V^{\dagger}U)\,.$ (17)

To obtain the first equality we used the ricochet property:

$\mathbbm{1}\otimes
X{\left|{\Phi^{+}}\right\rangle}=X^{T}\otimes\mathbbm{1}{\left|{\Phi^{+}}\right\rangle},$
(18)

which holds for any operator $X$ acting on a $d$-dimensional space. The
probability of the ${\left|{\Phi^{+}}\right\rangle}$ outcome is then the
absolute square of the amplitude, i.e., $(1/d^{2})|{\rm
Tr}(V^{\dagger}U)|^{2}$. Hence, this probability gives us the absolute value
of the Hilbert-Schmidt inner product between $U$ and $V$. We therefore call
the circuit in Fig. 4(a) the Hilbert-Schmidt Test (HST).

Consider the depth of this circuit. Let $D(G)$ denote the depth of a gate
sequence $G$ for a fully-connected quantum computer whose native gate alphabet
includes the CNOT gate and the set of all one-qubit gates. Then, for the HST,
we have

$\displaystyle D(\text{HST})=4+\max\\{D(U),D(V^{*})\\}\,.$ (19)

The first term of 4 is associated with the Hadamards and CNOTs in Fig. 4(a),
and this term is negligible when the depth of $U$ or $V^{*}$ is large. The
second term results from the fact that $U$ and $V^{*}$ are performed in
parallel. Hence, whichever unitary, $U$ or $V^{*}$, has the larger depth will
determine the overall depth of the HST.

Figure 4: (a) The Hilbert-Schmidt Test. For this circuit, the probability to
obtain the measurement outcome in which all $2n$ qubits are in the
${\left|{0}\right\rangle}$ state is equal to $(1/d^{2})|{\rm
Tr}(V^{\dagger}U)|^{2}$. Hence, this circuit computes the magnitude of the
Hilbert-Schmidt inner product, $|\langle V,U\rangle|$, between $U$ and $V$.
(b) The Local Hilbert-Schmidt Test, which is the same as the Hilbert-Schmidt
Test except that only two of the $2n$ qubits are measured at the end. Shown is
the measurement of the qubits $A_{1}$ and $B_{1}$, and the probability that
both qubits are in the state ${\left|{0}\right\rangle}$ is given by (25) with
$j=1$.

###  4.2 Local Hilbert-Schmidt Test

Let us now consider a slightly modified form of the HST, shown in Fig. 4(b).
We call this the Local Hilbert-Schmidt Test (LHST) because, unlike the HST in
Fig. 4(a), only two of the total number $2n$ of qubits are measured: one qubit
from system $A$, say $A_{j}$, and the corresponding qubit $B_{j}$ from system
$B$, where $j\in\\{1,2,\dotsc,n\\}$.

The state of systems $A$ and $B$ before the measurements is given by Eq. (15).
Using the ricochet property in (18) as before, we obtain

$\displaystyle(U\otimes V^{*}){\left|{\Phi^{+}}\right\rangle}_{AB}$
$\displaystyle=(UV^{\dagger}\otimes\mathbbm{1}){\left|{\Phi^{+}}\right\rangle}_{AB}$
(20)
$\displaystyle=(W\otimes\mathbbm{1}){\left|{\Phi^{+}}\right\rangle}_{AB},$
(21)

where $W:=UV^{\dagger}$. Let $\bar{A_{j}}$ denote all systems $A_{k}$ except
for $A_{j}$, and let $\bar{B_{j}}$ denote all systems $B_{k}$ except for
$B_{j}$. Taking the partial trace over $\bar{A_{j}}$ and $\bar{B_{j}}$ on the
state in (21) gives us the following state on the qubits $A_{j}$ and $B_{j}$
that are being measured:

$\displaystyle{\rm
Tr}_{\bar{A_{j}}\bar{B_{j}}}((W_{A}\otimes\mathbbm{1}_{B}){\left|{\Phi^{+}}\right\rangle}{\left\langle{\Phi^{+}}\right|}_{AB}(W_{A}^{\dagger}\otimes\mathbbm{1}_{B}))$
$\displaystyle\quad={\rm
Tr}_{\bar{A_{j}}}\left((W_{A}\otimes\mathbbm{1}_{B_{j}})\left({\left|{\Phi^{+}}\right\rangle}{\left\langle{\Phi^{+}}\right|}_{A_{j}B_{j}}\otimes\frac{\mathbbm{1}_{\bar{A_{j}}}}{2^{n-1}}\right)\right.$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad\left.\times(W_{A}^{\dagger}\otimes\mathbbm{1}_{B_{j}})\right)$
(22)
$\displaystyle\quad=(\mathcal{E}_{j}\otimes\mathcal{I}_{B_{j}})({\left|{\Phi^{+}}\right\rangle}{\left\langle{\Phi^{+}}\right|}_{A_{j}B_{j}})\,.$
(23)

In (22), ${\left|{\Phi^{+}}\right\rangle}_{A_{j}B_{j}}$ is a 2-qubit maximally
entangled state of the form in (14). In (23), we have defined the channel
$\mathcal{E}_{j}$ by

$\mathcal{E}_{j}(\rho_{A_{j}})\coloneqq{\rm
Tr}_{\bar{A_{j}}}\left(W_{A}\left(\rho_{A_{j}}\otimes\frac{\mathbbm{1}_{\bar{A_{j}}}}{2^{n-1}}\right)W_{A}^{\dagger}\right).$
(24)

The probability of obtaining the $(0,0)$ outcome in the measurement of $A_{j}$
and $B_{j}$ is the overlap of the state in (23) with the
${\left|{\Phi^{+}}\right\rangle}_{A_{j}B_{j}}$ state, given by

$F_{e}^{(j)}:={\rm
Tr}\left({\left|{\Phi^{+}}\right\rangle}{\left\langle{\Phi^{+}}\right|}_{A_{j}B_{j}}(\mathcal{E}_{j}\otimes\mathcal{I}_{B_{j}})({\left|{\Phi^{+}}\right\rangle}{\left\langle{\Phi^{+}}\right|}_{A_{j}B_{j}})\right).$
(25)

Note that this is the entanglement fidelity of the channel $\mathcal{E}_{j}$.
We use these entanglement fidelities (for each $j$) to define the local cost
function $C_{\text{LHST}}(U,V)$ as

$C_{\text{LHST}}(U,V)=\frac{1}{n}\sum_{j=1}^{n}C_{\text{LHST}}^{(j)}(U,V),$
(26)

where

$\displaystyle C_{\text{LHST}}^{(j)}(U,V)$ $\displaystyle\coloneqq
1-F_{e}^{(j)}\,.$ (27)

Note that for all $j\in\\{1,2,\dotsc,n\\}$, the maximum value of $F_{e}^{(j)}$
is one, which occurs when $\mathcal{E}_{j}$ is the identity channel. This
means that the minimum value of $C_{\text{LHST}}(U,V)$ is zero. In Appendix B,
we show that $C_{\text{LHST}}$ is indeed a faithful cost function:

######  Proposition 1.

For all unitaries $U$ and $V$, it holds that $C_{\text{LHST}}(U,V)=0$ if and
only if $U=V$ (up to a global phase).

The cost function $C_{\text{LHST}}$ is simply the average of the probabilities
that the two qubits $A_{j}B_{j}$ are not in the ${\left|{00}\right\rangle}$
state, while the cost function $C_{\text{HST}}$ is the probability that all
qubits are not in the ${\left|{0}\right\rangle}^{\otimes 2n}$ state. Since the
probability of an intersection of events is never greater than the average of
the probabilities of the individual events, we find that

$C_{\text{LHST}}(U,V)\leqslant C_{\text{HST}}(U,V)$ (28)

for all unitaries $U$ and $V$. Furthermore, we can also formulate a bound in
the reverse direction

$nC_{\text{LHST}}(U,V)\geqslant C_{\text{HST}}(U,V).$ (29)

In Appendix C, we offer a proof for the above bounds.

######  Proposition 2.

Let $U$ and $V$ be $2^{n}\times 2^{n}$ unitaries. Then,

$C_{\text{LHST}}(U,V)\leqslant C_{\text{HST}}(U,V)\leqslant
nC_{\text{LHST}}(U,V)\,.$

The depth of the circuit in Fig. 4(b) used to compute the cost function
$C_{\text{LHST}}$ is the same as the depth of the circuit in Fig. 4(a) used to
compute $C_{\text{HST}}$, namely,

$D(\text{LHST})=4+\max\\{D(U),D(V^{*})\\}.$ (30)

##  5 Computational complexity of cost evaluation

In this section, we state impossibility results for the efficient classical
evaluation of both of our costs, $C_{\text{HST}}$ and $C_{\text{LHST}}$. To
show this, we analyze our circuits in the framework of deterministic quantum
computation with one clean qubit ($\mathsf{DQC1}$) [26]. We then make use of
known hardness results for the class $\mathsf{DQC1}$, and establish that the
efficient classical approximation of our cost functions is impossible under
reasonable complexity assumptions.

###  5.1 One-clean-qubit model of computation.

The complexity class $\mathsf{DQC1}$ consists of all problems that can be
efficiently solved with bounded error in the one-clean-qubit model of
computation. Inspired by the early implementations of NMR quantum computing
[26], in the one-clean-qubit model of computation the input is specified by a
single “clean qubit”, together with a maximally mixed state on $n$ qubits:

$\rho=|\hskip 1.0pt0\rangle\langle 0\hskip
1.0pt|\otimes(\mathbbm{1}/2)^{\otimes{n}}.$ (31)

A computation is then realized by applying a $\operatorname{poly}(n)$-sized
quantum circuit $Q$ to the input. We then measure the clean qubit in the
standard basis and consider the probability of obtaining the outcome “0”,
i.e.,

$\displaystyle{\rm Tr}[(|\hskip 1.0pt0\rangle\langle 0\hskip
1.0pt|\otimes\mathbbm{1}^{\otimes{n}})Q\rho Q^{\dagger}].$ (32)

The $\mathsf{DQC1}$ model of computation has been widely studied, and several
natural problems have been found to be complete for $\mathsf{DQC1}$. Most
notably, Shor and Jordan [44] showed that the problem of trace estimation for
$2^{n}\times 2^{n}$ unitary matrices that specify
$\operatorname{poly}(n)$-sized quantum circuits is $\mathsf{DQC1}$-complete.
Moreover, Fujii et al. [27] showed that classical simulation of
$\mathsf{DQC1}$ is impossible, unless the polynomial hierarchy collapses to
the second level. Specifically, it is shown that an efficient classical
algorithm that is capable of weakly simulating the output probability
distribution of any $\mathsf{DQC1}$ computation would imply a collapse of the
polynomial hierarchy to the class of Arthur-Merlin protocols, which is not
believed to be true. Rather, it is commonly believed that the class
$\mathsf{DQC1}$ is strictly contained in $\mathsf{BQP}$, and thus provides a
sub-universal model of quantum computation that is hard to simulate
classically. Finally, we point out that the complexity class $\mathsf{DQC1}$
is known to give rise to average-case distance measures, whereas worst-case
distance measures (such as the diamond distance) are much harder to
approximate, and known to be $\mathsf{QIP}$-complete [28]. Currently, it is
not known whether there exists a distance measure that lies between the
average-case and worst-case measures in $\mathsf{DQC1}$ and $\mathsf{QIP}$,
respectively. However, we conjecture that only average-case distance measures
are feasible for practical purposes. We leave the task of finding a distance
measure whose approximation is complete for the class $\mathsf{BQP}$ as an
interesting open problem.

Our contributions are the following. We adapt the proofs in [44, 27] and show
that the problem of approximating our cost functions, $C_{\text{HST}}$ or
$C_{\text{LHST}}$, up to inverse polynomial precision is $\mathsf{DQC1}$-hard.
Our results build on the fact that evaluating either of our cost functions is,
in some sense, as hard as trace estimation. Using the results from [27], it
then immediately follows that no classical algorithm can efficiently
approximate our cost functions under certain complexity assumptions.

###  5.2 Approximating $C_{\text{HST}}$ is $\mathsf{DQC1}$-hard

In Appendix D, we prove the following:

######  Theorem 1.

Let $U$ and $V$ be $\operatorname{poly}(n)$-sized quantum circuits specified
by $2^{n}\times 2^{n}$ unitary matrices, and let
$\epsilon=O(1/\operatorname{poly}(n))$. Then, the problem of approximating
$C_{\mathsf{HST}}(U,V)$ up to $\epsilon$-precision is $\mathsf{DQC1}$-hard.

###  5.3 Approximating $C_{\text{LHST}}$ is $\mathsf{DQC1}$-hard

In Appendix D, we also prove the following:

######  Theorem 2.

Let $U$ and $V$ be $\operatorname{poly}(n)$-sized quantum circuits specified
by $2^{n}\times 2^{n}$ unitary matrices, and let
$\epsilon=O(1/\operatorname{poly}(n))$. Then, the problem of approximating
$C_{\mathsf{LHST}}(U,V)$ up to $\epsilon$-precision is $\mathsf{DQC1}$-hard.

As a consequence of these results, it then follows from [27] that there is no
classical algorithm to efficiently approximate our cost functions,
$C_{\text{HST}}$ or $C_{\text{LHST}}$, with inverse polynomial precision,
unless the polynomial hierarchy collapses to the second level.

##  6 Small-scale implementations

This section presents the results of implementing QAQC, as described in Sec.
3, for well-known one- and two-qubit unitaries. Some of these implementations
were done on actual quantum hardware, while others were on a simulator. In
each case, we performed gradient-free continuous parameter optimization in
order to minimize the cost function $C_{\text{HST}}$ in (5), evaluating this
cost function using the circuit in Fig. 4(a). For full details on the
optimization procedure, see Appendix E.

###  6.1 Quantum hardware

We implement QAQC on both IBM’s and Rigetti’s quantum computers. In what
follows, the depth of a gate sequence is defined relative to the native gate
alphabet of the quantum computer used.

####  6.1.1 IBM’s quantum computers

Here, we consider the 5-qubit IBMQX4 and the 16-qubit IBMQX5. For these
quantum computers, the native gate set is

$\displaystyle\mathcal{A}_{\text{IBM}}=\\{R_{x}(\pi/2),R_{z}(\theta),\text{CNOT}_{ij}\\}$
(33)

where the single-qubit gates $R_{x}(\pi/2)$ and $R_{z}(\theta)$ can be
performed on any qubit and the two-qubit CNOT gate can be performed between
any two qubits allowed in the topology; see [45] for the topology of IBMQX4
and [46] for the topology of IBMQX5.

To compile a given unitary $U$, we use the general procedure outlined in Sec.
3.3. Specifically, our initial gate structure, given by
$V_{\boldsymbol{k}}(\boldsymbol{\alpha})$, is selected at random from the gate
alphabet in (33). We then calculate the cost
$C_{\text{HST}}(U,V_{\boldsymbol{k}}(\boldsymbol{\alpha}))$ by executing the
HST shown in Fig. 4(a) on the quantum computer. To perform the continuous
parameter optimization over the angles $\theta$ of the $R_{z}$ gates, we make
use of Algorithm 2 outlined in Appendix E.1. This method is designed to limit
the number of objective function calls to the quantum computer, which is an
important consideration when using queue-based quantum computers like IBMQX4
and IBMQX5 since these can entail a significant amount of idle time in the
queue.

In essence, our method in Algorithm 2 discretizes the continuous parameter
space of angles $\theta$ to perform the continuous optimization. These angles
are selected uniformly over the unit circle and the grid spacing between them
decreases in the number of iterations. See Appendix E.1 for full details. If
the cost of the new sequence is less than the cost of the previous sequence,
then we accept the change. Otherwise, we accept the change with a probability
that decreases exponentially in the magnitude of the difference in cost. This
change in cost defines one iteration.

In Fig. 5(a), we show results for compiling single-qubit gates on IBMQX4. All
gates ($\mathbbm{1}$, $T$, $X$, and $H$) converge to a cost below 0.1, but no
gate achieves a cost below our tolerance of $10^{-2}$. As elaborated upon in
Sec. 8, this is due to a combination of finite sampling, gate fidelity,
decoherence, and readout error on the device. The single-qubit gates compile
to the following gate sequences:

  1. 1.

$\mathbbm{1}$ gate: $R_{z}(\theta)$, with $\theta\approx 0.01\pi$.

  2. 2.

$T$ gate: $R_{z}(\theta)$, with $\theta\approx 0.30\pi$.

  3. 3.

$X$ gate: $R_{x}(\pi/2)R_{x}(\pi/2)$.

  4. 4.

$H$ gate: $R_{z}(\theta_{1})R_{x}(\pi/2)R_{z}(\theta_{2})$, with
$\theta_{1}=\theta_{2}=0.50\pi$.

Figure 5(b) shows results for compiling the same single-qubit gates as above
on IBMQX5. The gate sequences have the same structure as listed above for
IBMQX4. The optimal angles achieved are $\theta=-0.03\pi$ for the
$\mathbbm{1}$ gate and $\theta=0.23\pi$ for the $T$ gate. The $X$ gate
compiles to $R_{x}(\pi/2)R_{x}(\pi/2)$, and the Hadamard gate $H$ compiles to
$R_{x}(\pi/2)R_{z}(\pi/2)R_{x}(\pi/2)$.

In our data collection, we performed on the order of 10 independent
optimization runs for each target gate above. The standard deviations of the
angles $\theta$ were on the order of $0.05\pi$, and this can be viewed as the
error bars on the average values quoted above.

Figure 5: Compiling the one-qubit gates $\mathbbm{1}$, $X$, $H$, and $T$ using
the gradient-free optimization technique described in Appendix E. The plots
show the cost $C_{\text{HST}}$ as a function of the number of iterations,
where an iteration is defined by an accepted update to the gate structure; see
Sec. 3.3 for a description of the procedure. The insets display the minimum
cost achieved by optimizing over gate sequences with a fixed depth, where the
depth is defined relative to the native gate alphabet of the quantum computer
used. (a) Compiling on the IBMQX4 quantum computer, in which we took $8,000$
samples to evaluate the cost for each run of the Hilbert-Schmidt Test. (b)
Compiling on the IBMQX5 quantum computer, in which we again took $8,000$
samples to evaluate the cost for each run of the Hilbert-Schmidt Test. (c)
Compiling on Rigetti’s 8Q-Agave quantum computer. In the plot, each iteration
uses 50 cost function evaluations to perform the continuous optimization. For
each run of the Hilbert-Schmidt Test to evaluate the cost, we took $10,000$
samples (calls to the quantum computer).

####  6.1.2 Rigetti’s quantum computer

The native gate set of Rigetti’s 8Q-Agave 8-qubit quantum computer is

$\mathcal{A}_{\text{Rigetti}}=\\{R_{x}(\pm\pi/2),R_{z}(\theta),\text{CZ}_{ij}\\}$
(34)

where the single-qubit gates $R_{x}(\pm\pi/2)$ and $R_{z}(\theta)$ can be
performed on any qubit and the two-qubit CZ gate can be performed between any
two qubits allowed in the topology; see [47] for the topology of the 8Q-Agave
quantum computer.

As with the implementation on IBM’s quantum computers, for the implementation
on Rigetti’s quantum computer we make use of the general procedure outlined in
Sec. 3.3. Specifically, we perform random updates to the gate structure
followed by continuous optimization over the parameters $\theta$ of the
$R_{z}$ gates using the gradient-free stochastic optimization technique
described in Algorithm 1 in Appendix E. In this optimization algorithm, we use
fifty cost function evaluations to perform the continuous optimization over
parameters. (That is, each iteration in Fig. 5(c) and Fig. 6 uses fifty cost
function evaluations, and each cost function evaluation uses $10,000$ calls to
the quantum computer for finite sampling.) We take the cost error tolerance
(the parameter $\varepsilon^{\prime}$ in Algorithm 1) to be $10^{-2}$, and for
each run of the Hilbert-Schmidt Test, we take $10,000$ samples in order to
estimate the cost. Our results are shown in Fig. 5(c). As described in
Algorithm 1, we define an iteration to be one accepted update in gate
structure followed by a continuous optimization over the internal gate
parameters.

The gates compiled in Fig. 5(c) have the following optimal decompositions. The
same decompositions also achieve the lowest cost in the cost vs. depth plot in
the inset.

  1. 1.

$\mathbbm{1}$ gate: $R_{z}(\theta)$, with $\theta\approx 0$.

  2. 2.

$T$ gate: $R_{z}(\theta)$, with $\theta\approx 0.342\pi$.

  3. 3.

$X$ gate: $R_{x}(-\pi/2)R_{x}(-\pi/2)$.

  4. 4.

$H$ gate: $R_{z}(\theta_{1})R_{x}(\pi/2)R_{z}(\theta_{2})$, with
$\theta_{1}\approx 0.50\pi$ and $\theta_{2}\approx 0.49\pi$.

As with the results on IBM’s quantum computers, none of the gates achieve a
cost less than $10^{-2}$, due to factors such as finite sampling, gate
fidelity, decoherence, and readout error. In addition, similar to the IBM
results, the standard deviations of the angles $\theta$ here were on the order
of $0.05\pi$, which can be viewed as the error bars on the average values
(over 10 independent runs) quoted above.

Figure 6: Compiling one- and two-qubit gates on Rigetti’s quantum virtual
machine with the gate alphabet in (35) using the gradient-free optimization
technique described in Algorithm 1 in Appendix E. (a) The minimum cost
achieved by optimizing over gate sequences with a fixed depth. (b) The cost as
a function of the number of iterations of the full gate structure and
continuous parameter optimization; see Sec. 3.3 for a description of the
procedure. Note that each iteration uses 50 cost function evaluations, and
each cost function evaluation uses $10,000$ samples (calls to the quantum
computer). (c) Shortest-depth decompositions of the two-qubit controlled-$Z$,
controlled-Hadamard, and quantum Fourier transform gates as determined by the
compilation procedure. The equalities indicated are true up to a global phase
factor. Here,  denotes the rotation gate $R_{z}(\theta)$, while  represents
the rotation gate $R_{x}(\pi/2)$.

###  6.2 Quantum simulator

We now present our results on executing QAQC for single-qubit and two-qubit
gates using a simulator. We use the gate alphabet

$\mathcal{A}=\\{R_{x}(\pi/2),R_{z}(\theta),\text{CNOT}_{ij}\\},$ (35)

which is the gate alphabet defined in Eq. (33) except with full connectivity
between the qubits. We again use the gradient-free optimization method
outlined in Appendix E to perform the continuous parameter optimization. The
simulations are performed assuming perfect connectivity between the qubits, no
gate errors, and no decoherence.

Using Rigetti’s quantum virtual machine [29], we compile the controlled-
Hadamard (CH) gate, the CZ gate, the SWAP gate, and the two-qubit quantum
Fourier transform $\text{QFT}_{2}$ by adopting the gradient-free continuous
optimization procedure in Algorithm 1. We also compile the single-qubit gates
$X$ and $H$. For each run of the Hilbert-Schmidt Test to determine the cost,
we took $20,000$ samples. Our results are shown in Fig. 6. For the SWAP gate,
we find that circuits of depth one and two cannot achieve zero cost, but there
exists a circuit with depth three for which the cost vanishes. The circuit
achieving this zero cost is the well-known decomposition of the SWAP gate into
three CNOT gates. While our compilation procedure reproduces the known
decomposition of the SWAP gate, it discovers a decomposition of both the CZ
and the $\text{QFT}_{2}$ gates that differs from their conventional “textbook”
decompositions, as shown in Fig. 6(c). In particular, these decompositions
have shorter depths than the conventional decompositions when written in terms
of the gate alphabet in (35).

In Appendix F, we likewise implement QAQC for one- and two-qubit gates on a
simulator, but instead using a gradient-based continuous parameter
optimization method outlined therein.

##  7 Larger-scale implementations

While in the previous section we considered one- and two-qubit unitaries, in
this section we explore larger unitaries, up to nine qubits. The purpose of
this section is to see how QAQC scales, and in particular, to study the
performance of our $C_{\text{HST}}$ and $C_{\text{LHST}}$ cost functions as
the problem size increases. We consider two different examples.

######  Example 1.

In the first example, we let $U$ be a tensor product of one-qubit unitaries.
Namely we consider

$U=\bigotimes_{j=1}^{n}R_{z}(\theta_{j})$ (36)

where the $\theta_{j}$ are randomly chosen, and $R_{z}(\theta)$ is a rotation
about the $z$-axis of the Bloch sphere by angle $\theta$. Similarly, our
ansatz for $V$ is of the same form,

$V=\bigotimes_{j=1}^{n}R_{z}(\phi_{j})$ (37)

where the initial values of the angles $\phi_{j}$ are randomnly chosen.

######  Example 2.

In the second example, we go beyond the tensor-product situation and explore a
unitary that entangles all the qubits. The target unitary has the form
$U=U_{4}(\boldsymbol{\theta}^{\prime})U_{3}U_{2}U_{1}(\boldsymbol{\theta})$,
with

$\displaystyle U_{1}(\boldsymbol{\theta})$
$\displaystyle=\bigotimes_{j=1}^{n}R_{z}(\theta_{j}),\quad
U_{2}=...\text{CNOT}_{34}\text{CNOT}_{12}$ (38) $\displaystyle U_{3}$
$\displaystyle=...\text{CNOT}_{45}\text{CNOT}_{23},\quad
U_{4}(\boldsymbol{\theta}^{\prime})=\bigotimes_{j=1}^{n}R_{z}(\theta_{j}^{\prime})\,.$
(39)

Here, $\text{CNOT}_{kl}$ denotes a CNOT with qubit $k$ the control and qubit
$l$ the target, while $\boldsymbol{\theta}=\\{\theta_{j}\\}$ and
$\boldsymbol{\theta}^{\prime}=\\{\theta^{\prime}_{j}\\}$ are $n$-dimensional
vectors of angles. Hence $U_{2}$ and $U_{3}$ are layers of CNOTs where the
CNOTs in $U_{3}$ are shifted down by one qubit relative to those in $U_{2}$.
Our ansatz for the trainable unitary $V$ has the same form as $U$ but with
different angles, i.e.,
$V=U_{4}(\boldsymbol{\phi}^{\prime})U_{3}U_{2}U_{1}(\boldsymbol{\phi})$ where
$\boldsymbol{\phi}$ and $\boldsymbol{\phi}^{\prime}$ are randomly initialized.

In what follows we discuss our implementations of QAQC for these two examples.
We first discuss the implementation on a simulator without noise, and then we
move onto the implementation on a simulator with a noise model.

###  7.1 Noiseless implementations

We implemented Examples 1 and 2 on a noiseless simulator. In each case,
starting with the ansatz for $V$ at a randomly chosen set of angles, we
performed the continuous parameter optimization over the angles using a
gradient-based approach. We made use of Algorithm 4 in Appendix F.3, which is
a gradient descent algorithm that explicitly evaluates the gradient using the
formulas provided in Appendix F.3. For each run of the HST and LHST, we took
1000 samples in order to estimate the value of the cost function. The results
of this implementation are shown in Figs. 7 and 8.

Figure 7: Results of performing continuous parameter optimization using the
HST and the LHST for the scenario described in Example 1. We make use of the
gradient-based optimization algorithm given by Algorithm 4 in Appendix F. The
curves “HST via LHST” are given by evaluating $C_{\text{HST}}$ using the
angles obtained during the optimization iterations of $C_{\text{LHST}}$. For
each run of the HST and LHST, we use 1000 samples to estimate the cost
function.

In the case of Example 1 (Fig. 7), both the $C_{\text{HST}}$ and
$C_{\text{LHST}}$ cost functions converge to the desired global minimum up to
5 qubits. However, for $n=$ 6, 7, 8, and 9 qubits, we find cases in which the
$C_{\text{HST}}$ cost function does not converge to the global minimum but the
$C_{\text{LHST}}$ cost function does. Specifically, the cost $C_{\text{HST}}$
stays very close to one, with a gradient value smaller than the pre-set
threshold of $10^{-3}$ for four consecutive iterations, causing the gradient
descent algorithm to declare convergence. Interestingly, even in the cases
that the $C_{\text{HST}}$ cost does not converge to the global minimum,
training with the $C_{\text{LHST}}$ cost allows us to fully minimize the
$C_{\text{HST}}$ cost. (See the green curves labelled “HST via LHST” in Fig.
7, in which we evaluate the $C_{\text{HST}}$ cost at the angles obtained
during the optimization of the $C_{\text{LHST}}$ cost.) This fascinating
feature implies that, for $n\geqslant 6$ qubits in Example 1, training our
$C_{\text{LHST}}$ cost is better at minimizing the $C_{\text{HST}}$ cost than
is directly attempting to train the $C_{\text{HST}}$ cost.

Figure 8: Results of performing continuous parameter optimization using the
HST and the LHST for the scenario described in Example 2. We make use of the
gradient-based optimization algorithm given by Algorithm 4 in Appendix F, in
which each iteration can involve several calls to the quantum computer. The
curves “HST via LHST” are given by evaluating $C_{\text{HST}}$ using the
angles obtained during the optimization iterations of $C_{\text{LHST}}$. For
each run of the HST and LHST, we use 1000 samples to estimate the cost
function.

We find very similar behavior for Example 2 (Fig. 8). In particular, for
$n\geqslant 6$ qubits, we were unable to directly train the $C_{\text{HST}}$
cost. However, the $C_{\text{LHST}}$ cost converges to the global minimum for
$n=$ 6 and 8 qubits. Furthermore, as with Example 1, we find that minimizing
the $C_{\text{LHST}}$ cost also minimizes the $C_{\text{HST}}$ cost.

###  7.2 Noisy implementations

We implemented Examples 1 and 2 on IBM’s noisy simulator, where the noise
model matches that of the 16-qubit IBMQX5 quantum computer. This noise model
accounts for $T_{1}$ noise, $T_{2}$ noise, gate errors, and measurement
errors. We emphasize that these are realistic noise parameters since they
simulate the noise on currently available quantum hardware. (Note that when
our implementations required more than 16 qubits, we applied similar noise
parameters to the additional qubits as those for the 16 qubits of the IBMQX5.)
We used the same training algorithm as the one we used in the noiseless case
above. The results of these implementations are shown in Figs. 9 and 10.

Figure 9: Results of performing continuous parameter optimization using the
HST and the LHST, in the presence of noise, for the scenario described in
Example 1. The noise model used matches that of the IBMQX5 quantum computer.
We make use of the gradient-based optimization algorithm given by Algorithm 4
in Appendix F. The curves “Noiseless HST via LHST” are given by evaluating
$C_{\text{HST}}$ (without noise) using the angles obtained during the
optimization iterations of $C_{\text{LHST}}$. For each run of the HST and
LHST, we use 1000 samples to estimate the cost function.

Similar to the noiseless case, for Example 1 (Fig. 9) and for Example 2 (Fig.
10), we find that both the $C_{\text{HST}}$ and $C_{\text{LHST}}$ cost
functions converge up to a problem size of 5 qubits. Due to the noise, as
expected, both cost functions converge to a value greater than zero. For
$n\geqslant 6$ qubits, however, we find that the $C_{\text{HST}}$ cost
function does not converge to a local minimum. Specifically, this cost stays
very close to one with a gradient value smaller than the pre-set threshold of
$10^{-3}$ for four consecutive iterations, causing the gradient descent
algorithm to declare convergence. The local cost, on the other hand, converges
to a local minimum in every case.

Remarkably, despite the noise in the simulation, we find that the angles
obtained during the iterations of the $C_{\text{LHST}}$ optimization
correspond to the optimal angles in the noiseless case. This result is
indicated by the green curves labeled “Noiseless HST via LHST”. One can see
that the green curves go to zero for the local minima found by training the
noisy $C_{\text{LHST}}$ cost function. Hence, in these examples, training the
noisy $C_{\text{LHST}}$ cost function can be used to minimize the noiseless
$C_{\text{HST}}$ cost function to the global minimum. This intriguing behavior
suggests that the noise has not affected the location (i.e., the value for the
angles) of the global minimum. We thus find evidence of the robustness of QAQC
to the kind of noise present in actual devices. We elaborate on this point in
the next section.

Figure 10: Results of performing continuous parameter optimization using the
HST and the LHST, in the presence of noise, for the scenario described in
Example 2. The noise model used matches that of the IBMQX5 quantum computer.
We make use of the gradient-based optimization algorithm given by Algorithm 4
in Appendix F. The curves “Noiseless HST via LHST” are given by evaluating
$C_{\text{HST}}$ (without noise) using the angles obtained during the
optimization iterations of $C_{\text{LHST}}$. For each run of the HST and
LHST, we use 1000 samples to estimate the cost function.

##  8 Discussion

On both IBM’s and Rigetti’s quantum hardware, we were able to successfully
compile one-qubit gates with no a priori assumptions about gate structure or
gate parameters. We also successfully implemented QAQC for simple 9-qubit
gates on both a noiseless and noisy simulator. These implementations
highlighted two important issues, (1) barren plateuas in cost landscape and
(2) the effect of hardware noise, which we discuss further now.

###  8.1 Barren Plateaus

Recent results [48, 49] on gradient-based optimization with random quantum
circuits suggest that the probability of observing non-zero gradients tends to
become exponentially small as a function of the number of qubits. That work
showed that a hardware-efficient ansatz leads to vanishing gradients as the
ansatz’s depth becomes deeper (and hence begins to look more like a random
unitary). This is an important issue for many variational hybrid algorithms,
including QAQC, and motivates the need to avoid a deep, random ansatz.
Strategies to address this “barren plateau” issue for QAQC include restricting
to a short-depth ansatz, or alternatively employing an application-specific
ansatz that takes into account some information about the target unitary $U$.
We intend to explore application-specific ansatze in future work to address
this issue. There may be other strategies based on the fact that similar
issues have been identified in classical deep learning [50]. For instance,
recent work [51] shows that gradient descent with momentum (GDM) using an
adaptive (multiplicative) integration step update, called resilient
backpropagation (rProp), can help with convergence. But, this is an active
research area and will likely be important to the success of variational
hybrid algorithms.

Interestingly, in this work, we identified another barren plateau issue that
is completely independent and distinct from the issue raised in Refs. [48,
49]. Namely, we found that our operationally meaningful cost function,
$C_{\text{HST}}$, can have barren plateaus even when the ansatz is a depth-one
circuit. The gradient of $C_{\text{HST}}$ can vanish exponentially in $n$ even
when the ansatz has only a single parameter. This issue became apparent in our
implementations (see Figs. 7 through 10), where we were unable to directly
train the $C_{\text{HST}}$ cost for $n\geqslant 6$ qubits. Fortunately, we
fixed this issue by introducing the $C_{\text{LHST}}$ cost, which successfully
trained in all cases we attemped (we attempted up to $n=9$ qubits). Although
$C_{\text{LHST}}$ is not directly operationally meaningful, it is indirectly
related to $C_{\text{HST}}$ via Eqs. (28) and (29). Hence it can be used to
indirectly train $C_{\text{HST}}$, as shown in Figs. 7 through 10. We believe
this barren plateau issue will show up in other variational hybrid algorithms.
For example, we encountered the same issue in a recently introduced
variational algorithm for state diagonalization [52].

###  8.2 Effect of Hardware Noise

The impact of hardware noise, such as decoherence, gate infidelity, and
readout error, is important to consider. This is especially true since QAQC is
aimed at being a useful algorithm in the era of NISQ computers, although we
remark that QAQC may also be useful for fault-tolerant quantum computing.

On the one hand, we intuitively expect noise to significantly affect the HST
and LHST cost evaluation circuits. On the other hand, we see empirical
evidence of noise resilience in Figs. 9 and 10. Let us elaborate on both our
intuition and our empirical observations now.

A qualitative noise analysis of the HST circuit in Fig. 4(a) is as follows. To
compile a unitary $U$ acting on $n$ qubits, a circuit with $2n$ qubits is
needed. Preparing the maximally-entangled state $|\Phi^{+}\rangle$ in the
first portion of the circuit requires $n$ CNOT gates, which are significantly
noisier than one-qubit gates and propagate errors to other qubits through
entanglement. In principle, all Hadamard and CNOT gates can be implemented in
parallel, but on near-term devices this may not be the case. Additionally, due
to limited connectivity of NISQ devices, it is generally not possible to
directly implement CNOTs between arbitrary qubits. Instead, the CNOTs need to
be “chained” between qubits that are connected, a procedure that can
significantly increase the depth of the circuit.

The next level of the circuit involves implementing $U$ in the top $n$-qubit
register and $V^{*}$ in the bottom $n$-qubit register. Here, the noise of the
computer on $V^{*}$ is not necessarily undesirable since it could allow us to
compile noise-tailored algorithms that counteract the noise of the specific
computer, as described in Sec. 2. Nevertheless, the depth of $V^{*}$ and/or of
$U$ essentially determines the overall circuit depth as noted in (19), and
quantum coherence decays exponentially with the circuit depth. Hence,
compiling larger gate sequences involves additional loss of coherence on NISQ
computers.

The final level of the HST circuit involves making a Bell measurement on all
qubits and is the reverse of the first part of the circuit. As such, the same
noise analysis of the first portion of the circuit applies here. Readout
errors can be significant on NISQ devices [53], and our HST circuit involves a
number of measurements that scales linearly in the number of qubits. Hence,
compiling larger unitaries can increase overall readout error.

A similar qualitative noise analysis holds for the LHST circuit in Fig. 4(b),
except we note that to calculate the functions $C_{\text{LHST}}^{(j)}$ in (26)
we require only one CNOT gate in the last portion of the LHST circuit before
the measurement. Furthermore, we measure only two qubits regardless of the
total number of qubits.

With that said, we observed a (somewhat surprising) noise resilience in Figs.
9 and 10. In these implementations, we imported the noise model of the IBMQX5
quantum computer, which is a currently available cloud quantum computer.
Hence, we considered realistic noise parameters for decoherence, gate
infedility, and readout error. This noise affected all circuit elements of the
LHST circuit in Fig. 4(b). Yet we still obtained the correct unitary $V$ via
QAQC, as shown by the green curves going to zero in Figs. 9 and 10.

Naturally, we plan to investigate this noise resilience in full detail in
future work. But it is worth emphasizing the following point here. The value
of the cost could be significantly affected by noise without shifting the
location of the global minimum in parameter space. In fact, one can see in
Figs. 9 and 10 that the value of the $C_{\text{LHST}}$ cost is significantly
affected by noise. Namely, note that the red curves in these plots do not go
to zero for larger iterations. However, the green curves do go to zero, which
means that QAQC found the correct parameters for $V$ despite the noisy cost
values.

We could speculate reasons for why the global minimum appears not shift in
parameter space with noise. For example, it could be due to the nature of our
cost functions. These cost functions can be thought of as entanglement
fidelities and hence are related to Hilbert-space averages of input-output
fidelities, see Eq. (6). By averaging the input-output fidelity over the whole
Hilbert space, the effect of noise could essentially be averaged away. This is
just speculation at this point, and we will perform a detailed analysis of the
effect of noise in future work. Regardless, our preliminary results in Figs. 9
and 10 suggest that QAQC may indeed be useful in the NISQ era.

##  9 Conclusions

Quantum compiling is crucial in the era of NISQ devices, where constraints on
NISQ computers (such as limited connectivity, limited circuit depth, etc.)
place severe restrictions on the quantum algorithms that can be implemented in
practice. In this work, we presented a methodology for quantum compilation
called quantum-assisted quantum compiling (QAQC), whereby a quantum computer
provides an exponential speedup in evaluating the cost of a gate sequence,
i.e., how well the gate sequence matches the target. In principle, QAQC should
allow for the compiling of larger algorithms than standard classical methods
for quantum compiling due to this exponential speedup. As a proof-of-
principle, we implemented QAQC on IBM’s and Rigetti’s quantum computers to
compile various one-qubit gates to their native gate alphabets. To our
knowledge, this is the first time NISQ hardware has been used to compile a
target unitary. In addition, we successfully implemented QAQC on a noiseless
and noisy simulator for simple 9-qubit unitaries.

Our main technical results were the following. First, we carefully chose a
cost function (which involved global and local overlaps between a target
unitary $U$ and a trainable unitary $V$) and proved that it satisfied four
criteria: it is faithful, it is efficient to compute on a quantum computer, it
has an operational meaning, and it scales well with the size of the problem.
Second, we presented short-depth circuits (see Sections 4.1 and 4.2) for
computing our cost function. Third, we proved that evaluating our cost
function is $\mathsf{DQC1}$-hard, and hence no classical algorithm can
efficiently evaluate our cost function, under reasonable complexity
assumptions. This established a rigorous proof for the difficulty of
classically simulating QAQC. We also remark that, in the Appendix, we detailed
our gradient-free and gradient-based methods for optimizing our cost function.
This included a circuit for gradient computation that generalizes the famous
Power of One Qubit [26] and hence is likely of interest to a broader
community.

As elaborated in the Discussion section, our noisy implementations of QAQC
showed a surprising resilience to noise. While simulating realistic noise
parameters based on a currently available cloud quantum computer (IBMQX5), we
were able to run QAQC on a 9-qubit unitary and obtain the correct parameters
for $V$. We plan to investigate this intriguing noise resilience in future
work.

QAQC is a novel variational hybrid algorithm, similar to other well-known
variational hybrid algorithms such as VQE [18] and QAOA [2]. Variational
hybrid algorithms are likely to provide some of the first real applications of
quantum computers in the NISQ era. In the case of QAQC, it is an algorithm
that makes other algorithms more efficient to implement, via algorithm depth
compression. We note that the ability to compress algorithm depth will also be
useful (to reduce the run-time of quantum circuits) in the era of fault-
tolerant quantum computing. The central application of QAQC is thus to make
quantum computers more useful.

## Acknowledgements

We thank IBM and Rigetti for providing access to their quantum computers. The
views expressed in this paper are those of the authors and do not reflect
those of IBM or Rigetti. SK, RL, and AP acknowledge support from the U.S.
Department of Energy through a quantum computing program sponsored by the LANL
Information Science & Technology Institute. RL acknowledges support from an
Engineering Distinguished Fellowship through Michigan State University. AP is
partially supported by AFOSR YIP award number FA9550-16-1-0495 and the
Institute for Quantum Information and Matter, an NSF Physics Frontiers Center
(NSF Grant PHY-1733907) and the Kortschak Scholars program. LC was supported
by the U.S. Department of Energy through the J. Robert Oppenheimer fellowship.
ATS and PJC were supported by the LANL ASC Beyond Moore’s Law project. LC,
ATS, and PJC were also supported by the LDRD program at LANL. We thank
Alexandru Gheorghiu and Thomas Vidick for useful discussions.

## References

  * Shor [1997] P. Shor,  _Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer,_SIAM Journal on Computing 26, 1484 (1997).
  * Farhi  _et al._ [2014] E. Farhi, J. Goldstone, and S. Gutmann,  _A quantum approximate optimization algorithm,_arXiv:1411.4028 (2014).
  * Feynman [1982] R. P. Feynman,  _Simulating physics with computers,_International Journal of Theoretical Physics 21, 467 (1982).
  * Preskill [2018] J. Preskill,  _Quantum computing in the NISQ era and beyond,_Quantum 2, 79 (2018).
  * Preskill [2012] J. Preskill,  _Quantum computing and the entanglement frontier,_arXiv:1203.5813 (2012).
  * Neill  _et al._ [2018] C. Neill, P. Roushan, K. Kechedzhi, S. Boixo, S. V. Isakov, V. Smelyanskiy, _et al._ ,  _A blueprint for demonstrating quantum supremacy with superconducting qubits,_Science 360, 195 (2018).
  * Venturelli  _et al._ [2018] D. Venturelli, M. Do, E. Rieffel, and J. Frank,  _Compiling quantum circuits to realistic hardware architectures using temporal planners,_Quantum Science and Technology 3, 025004 (2018).
  * Booth  _et al._ [2018] K. E. C. Booth, M. Do, J. C. Beck, E. Rieffel, D. Venturelli, and J. Frank,  _Comparing and integrating constraint programming and temporal planning for quantum circuit compilation,_arXiv:1803.06775 (2018).
  * Cincio  _et al._ [2018] L. Cincio, Y. Subaşı, A. T. Sornborger, and P. J. Coles,  _Learning the quantum algorithm for state overlap,_New Journal of Physics 20, 113022 (2018).
  * Maslov  _et al._ [2008] D. Maslov, G. W. Dueck, D. M. Miller, and C. Negrevergne,  _Quantum circuit simplification and level compaction,_IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 27, 436 (2008).
  * Fowler [2011] A. G. Fowler,  _Constructing arbitrary Steane code single logical qubit fault-tolerant gates,_Quantum Information and Computation 11, 867 (2011).
  * Booth Jr [2012] J. Booth Jr,  _Quantum compiler optimizations,_arXiv:1206.3348 (2012).
  * Nam  _et al._ [2018] Y. Nam, N. J. Ross, Y. Su, A. M. Childs, and D. Maslov,  _Automated optimization of large quantum circuits with continuous parameters,_npj Quantum Information 4, 23 (2018).
  * Chong  _et al._ [2017] F. T. Chong, D. Franklin, and M. Martonosi,  _Programming languages and compiler design for realistic quantum hardware,_Nature 549, 180 (2017).
  * Heyfron and Campbell [2018] L. E. Heyfron and E. T. Campbell,  _An efficient quantum compiler that reduces T count,_Quantum Science and Technology 4, 015004 (2018).
  * Häner  _et al._ [2018] T. Häner, D. S. Steiger, K. Svore, and M. Troyer,  _A software methodology for compiling quantum programs,_Quantum Science and Technology 3, 020501 (2018).
  * Oddi and Rasconi [2018] A. Oddi and R. Rasconi, in  _International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research_ (Springer, 2018) pp. 446–461.
  * Peruzzo  _et al._ [2014] A. Peruzzo, J. McClean, P. Shadbolt, M.-H. Yung, X.-Q. Zhou, P. J. Love, A. Aspuru-Guzik, and J. L. O’Brien,  _A variational eigenvalue solver on a photonic quantum processor,_Nature Communications 5, 4213 (2014).
  * Johnson  _et al._ [2017] P. D. Johnson, J. Romero, J. Olson, Y. Cao, and A. Aspuru-Guzik,  _QVECTOR: an algorithm for device-tailored quantum error correction,_arXiv:1711.02249 (2017).
  * Benedetti  _et al._ [2018a] M. Benedetti, D. Garcia-Pintos, O. Perdomo, V. Leyton-Ortega, Y. Nam, and A. Perdomo-Ortiz,  _A generative modeling approach for benchmarking and training shallow quantum circuits,_arXiv:1801.07686 (2018a).
  * Mitarai  _et al._ [2018] K. Mitarai, M. Negoro, M. Kitagawa, and K. Fujii,  _Quantum circuit learning,_Physical Review A 98, 032309 (2018).
  * Verdon  _et al._ [2018] G. Verdon, J. Pye, and M. Broughton,  _A Universal Training Algorithm for Quantum Deep Learning,_arXiv:1806.09729 (2018).
  * Romero  _et al._ [2017] J. Romero, J. P. Olson, and A. Aspuru-Guzik,  _Quantum autoencoders for efficient compression of quantum data,_Quantum Science and Technology 2, 045001 (2017).
  * Romero  _et al._ [2018] J. Romero, J. P. Olson, and A. Aspuru-Guzik,  _Quantum autoencoders for short depth quantum circuit synthesis,_GitHub article (2018).
  * Dive  _et al._ [2018] B. Dive, A. Pitchford, F. Mintert, and D. Burgarth,  _In situ upgrade of quantum simulators to universal computers,_Quantum 2, 80 (2018).
  * Knill and Laflamme [1998] E. Knill and R. Laflamme,  _Power of one bit of quantum information,_Physical Review Letters 81, 5672 (1998).
  * Fujii  _et al._ [2018] K. Fujii, H. Kobayashi, T. Morimae, H. Nishimura, S. Tamate, and S. Tani,  _Impossibility of Classically Simulating One-Clean-Qubit Model with Multiplicative Error,_Physical Review Letters 120, 200502 (2018).
  * Rosgen and Watrous [2005] B. Rosgen and J. Watrous, in  _20th Annual IEEE Conference on Computational Complexity (CCC’05)_ (2005) pp. 344–354.
  * Smith  _et al._ [2016] R. S. Smith, M. J. Curtis, and W. J. Zeng,  _A practical quantum instruction set architecture,_arXiv:1608.03355 (2016).
  * Cross  _et al._ [2017] A. W. Cross, L. S. Bishop, J. A. Smolin, and J. M. Gambetta,  _Open Quantum Assembly Language,_arXiv:1707.03429 (2017).
  * Nielsen and Chuang [2000] M. A. Nielsen and I. L. Chuang,  _Quantum Computation and Quantum Information_ (Cambridge University Press, 2000).
  * Kitaev [1997] A. Kitaev,  _Quantum computations: algorithms and error correction,_Russian Mathematical Surveys 52, 1191 (1997).
  * Dawson and Nielsen [2006] C. M. Dawson and M. A. Nielsen,  _The Solovay-Kitaev algorithm,_Quantum Information and Compututation 6, 81 (2006).
  * Pham  _et al._ [2013] T. T. Pham, R. Van Meter, and C. Horsman,  _Optimization of the Solovay-Kitaev algorithm,_Physical Review A 87, 052332 (2013).
  * Kliuchnikov  _et al._ [2013] V. Kliuchnikov, D. Maslov, and M. Mosca,  _Asymptotically optimal approximation of single qubit unitaries by Clifford and T circuits using a constant number of ancillary qubits,_Physical Review Letters 110, 190502 (2013).
  * Kliuchnikov  _et al._ [2014] V. Kliuchnikov, A. Bocharov, and K. M. Svore,  _Asymptotically optimal topological quantum compiling,_Physical Review Letters 112, 140504 (2014).
  * Zhiyenbayev  _et al._ [2018] Y. Zhiyenbayev, V. M. Akulin, and A. Mandilara,  _Quantum compiling with diffusive sets of gates,_Physical Review A 98, 012325 (2018).
  * Horodecki  _et al._ [1999] M. Horodecki, P. Horodecki, and R. Horodecki,  _General teleportation channel, singlet fraction, and quasidistillation,_Physical Review A 60, 1888 (1999).
  * Nielsen [2002] M. A. Nielsen,  _A simple formula for the average gate fidelity of a quantum dynamical operation,_Physics Letters A 303, 249 (2002).
  * Gepp and Stocks [2009] A. Gepp and P. Stocks,  _A review of procedures to evolve quantum algorithms,_Genetic Programming and Evolvable Machines 10, 181 (2009).
  * Suzuki [1990] M. Suzuki,  _Fractal decomposition of exponential operators with applications to many-body theories and monte carlo simulations,_Physics Letters A 146, 319 (1990).
  * Jones and Benjamin [2018] T. Jones and S. C. Benjamin,  _Quantum compilation and circuit optimisation via energy dissipation,_arXiv:1811.03147 (2018).
  * Garcia-Escartin and Chamorro-Posada [2013] J. C. Garcia-Escartin and P. Chamorro-Posada,  _Swap test and Hong-Ou-Mandel effect are equivalent,_Physical Review A 87, 052330 (2013).
  * Shor and Jordan [2008] P. W. Shor and S. P. Jordan,  _Estimating jones polynomials is a complete problem for one clean qubit,_Quantum Information & Computation 8, 681 (2008).
  * IBM [2018a] IBM Q 5 Tenerife backend specification,  (2018a).
  * IBM [2018b] IBM Q 16 Rueschlikon backend specification,  (2018b).
  * rig [2018] Rigetti 8Q-Agave specification v.2.0.0.dev0,  (2018).
  * McClean  _et al._ [2018] J. R. McClean, S. Boixo, V. N. Smelyanskiy, R. Babbush, and H. Neven,  _Barren plateaus in quantum neural network training landscapes,_Nature Communications 9, 4812 (2018).
  * Day  _et al._ [2019] A. G. R. Day, M. Bukov, P. Weinberg, P. Mehta, and D. Sels,  _Glassy phase of optimal quantum control,_Physical Review Letters 122, 020601 (2019).
  * Glorot and Bengio [2010] X. Glorot and Y. Bengio, in  _In Proceedings of the International Conference on Artificial Intelligence and Statistics_ (2010) pp. 249–256.
  * Benedetti  _et al._ [2018b] M. Benedetti, D. Garcia-Pintos, O. Perdomo, V. Leyton-Ortega, Y. Nam, and A. Perdomo-Ortiz,  _A generative modeling approach for benchmarking and training shallow quantum circuits,_arXiv:1801.07686 (2018b).
  * LaRose  _et al._ [2018] R. LaRose, A. Tikku, É. O’Neel-Judy, L. Cincio, and P. J. Coles,  _Variational quantum state diagonalization,_arXiv:1810.10506 (2018).
  * Kandala  _et al._ [2018] A. Kandala, K. Temme, A. D. Corcoles, A. Mezzacapo, J. M. Chow, and J. M. Gambetta,  _Extending the computational reach of a noisy superconducting quantum processor,_Nature 567, 491 (2018).
  * sci [2018a] Scikit-optimize,  (2018a).
  * Močkus [1975] J. Močkus, in  _Optimization Techniques IFIP Technical Conference Novosibirsk, July 1–7, 1974_ (Springer Berlin Heidelberg, Berlin, Heidelberg, 1975) pp. 400–404.
  * Osborne  _et al._ [2009] M. A. Osborne, R. Garnett, and S. J. Roberts, in  _3rd International Conference on Learning and Intelligent Optimization (LION3) 2009_ (2009).
  * Rebentrost  _et al._ [2016] P. Rebentrost, M. Schuld, L. Wossnig, F. Petruccione, and S. Lloyd,  _Quantum gradient descent and Newton’s method for constrained polynomial optimization,_arXiv:1612.01789 (2016).
  * Kerenidis and Prakash [2017] I. Kerenidis and A. Prakash,  _Quantum gradient descent for linear systems and least squares,_arXiv:1704.04992 (2017).
  * [59] A. Gilyén, S. Arunachalam, and N. Wiebe, Optimizing quantum optimization algorithms via faster quantum gradient computation, in  _Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms_, pp. 1425–1444.
  * Sousa and Ramos [2007] P. B. M. Sousa and R. V. Ramos,  _Universal quantum circuit for $n$-qubit quantum gate: A programmable quantum gate, _Quantum Information and Computation 7, 228 (2007).
  * Vatan and Williams [2004] F. Vatan and C. Williams,  _Optimal quantum circuits for general two-qubit gates,_Physical Review A 69, 032315 (2004).
  * sci [2018b] Scipy optimization and root finding,  (2018b).
  * Zhou  _et al._ [2011] X.-Q. Zhou, T. C. Ralph, P. Kalasuwan, M. Zhang, A. Peruzzo, B. P. Lanyon, and J. L. O’Brien,  _Adding control to arbitrary unknown quantum operations,_Nature Communications 2, 413 (2011).

##  Appendix A Remark on implementation of $V^{*}$

As mentioned in Sec. 4, a subtle point about evaluating the cost functions
$C_{\mathsf{HST}}(U,V_{\boldsymbol{k}}(\boldsymbol{\alpha}))$ and
$C_{\mathsf{LHST}}(U,V_{\boldsymbol{k}}(\boldsymbol{\alpha}))$ is that the
complex conjugate $V_{\boldsymbol{k}}(\boldsymbol{\alpha})^{*}$ must be
executed on the quantum computer, not
$V_{\boldsymbol{k}}(\boldsymbol{\alpha})$ itself. The complex conjugate of a
unitary corresponding to a gate sequence can be obtained by taking the complex
conjugate of each unitary in the gate sequence. However, if each gate in the
sequence comes from a gate alphabet $\mathcal{A}$, it is possible that the
complex conjugate of a gate in the sequence is not contained in the alphabet;
for example, if $\mathcal{A}=\\{R_{x}(\pi/2),R_{z}(\theta)\\}$, then the
complex conjugate of $R_{x}(\pi/2)$, which is $R_{x}(-\pi/2)$, is not
contained in $\mathcal{A}$. But the unitary $R_{z}(\pi)R_{x}(\pi/2)R_{z}(\pi)$
is equal (up to a global phase) to $R_{x}(-\pi/2)$. There are thus two ways to
proceed when performing the compilation procedure: during the optimization
over the continuous parameters, directly run the gate sequence corresponding
to $V_{\boldsymbol{k}}(\boldsymbol{\alpha})$, expressing it in terms of the
native gate alphabet of the quantum computer, then at the end establish the
complex conjugate of the optimal unitary as the unitary to which $U$ has been
compiled. This would involve translating the complex conjugate of each gate in
the optimal sequence into the native gate alphabet of the quantum computer. An
alternative is to first take the complex conjugate
$V_{\boldsymbol{k}}(\boldsymbol{\alpha})^{*}$ by translating the complex
conjugate of each gate in the sequence into the native gate alphabet, then
execute the resulting sequence on the quantum computer. In each case, we allow
for a small-scale classical compiler that can perform the simple translation
of the complex conjugate of a gate sequence into the native gate alphabet of
the quantum computer. Note that this small-scale classical compiler does not
come with exponential overhead because it is only compiling one- and two-qubit
gates.

Also, observe that if a gate alphabet is not closed under complex conjugation,
then the depth of a gate sequence from that alphabet can increase by taking
its complex conjugate. This is true for the example given above, in which the
complex conjugate $R_{x}(-\pi/2)$ of $R_{x}(\pi/2)$ has a depth of three under
the alphabet $\mathcal{A}=\\{R_{x}(\pi/2),R_{z}(\theta)\\}$, while the
original gate has a depth of only one. However, in general, note that the
final depth increases by at most a constant factor relative to the original
depth.

##  Appendix B Faithfulness of LHST cost function

See 1

Proof: First, we note that since $0\leqslant
C_{\text{LHST}}^{(j)}(U,V)\leqslant 1$ for all $j\in\\{1,2,\dotsc,n\\}$, we
get that $C_{\text{LHST}}(U,V)=0$ if and only if
$C_{\text{LHST}}^{(j)}(U,V)=0$, i.e., $F_{e}^{(j)}=1$, for all
$j\in\\{1,2,\dotsc,n\\}$. Next, since $F_{e}^{(j)}$ is by definition the
entanglement fidelity of the channel $\mathcal{E}_{j}$, we have that
$F_{e}^{(j)}=1$ if and only if $\mathcal{E}_{j}$ is the identity channel
$\mathcal{I}$. Finally, the condition $U=V$ is equivalent to $W\coloneqq
UV^{\dagger}=\mathbbm{1}$. Therefore, it suffices to prove that
$W=\mathbbm{1}$ if and only if $\mathcal{E}_{j}$ is the identity channel for
all $j\in\\{1,2,\dotsc,n\\}$. The implication
$W=\mathbbm{1}\Rightarrow\mathcal{E}_{j}=\mathcal{I}$ for all
$j\in\\{1,2,\dotsc,n\\}$ is immediate. We now prove the converse.

Let $j=1$, and suppose that $W$ has the following operator Schmidt
decomposition under the bipartite cut $A_{1}|A_{2}\dotsb A_{n}$:

$W=\sum_{i=1}^{r}\sqrt{\sigma_{i}}X_{i}^{A_{1}}\otimes Y_{i}^{A_{2}\dotsb
A_{n}},$ (40)

where $\\{X_{i}\\}_{i=1}^{r}$ and $\\{Y_{i}\\}_{i=1}^{r}$ are orthonormal sets
of operators, $\sigma_{i}>0$ are the Schmidt coefficients of $W$, and $r$ is
the Schmidt rank of $W$. Since $W$ is unitary, we have

$W^{\dagger}W=\sum_{i,i^{\prime}=1}^{r}\sqrt{\sigma_{i}\sigma_{i^{\prime}}}X_{i}^{\dagger}X_{i^{\prime}}\otimes
Y_{i}^{\dagger}Y_{i^{\prime}}=\mathbbm{1}_{A_{1}\dotsb A_{n}},$ (41)

which implies that

${\rm Tr}_{A_{2}\dotsb
A_{n}}(W^{\dagger}W)=\sum_{i=1}^{r}\sigma_{i}X_{i}^{\dagger}X_{i}=2^{n-1}\mathbbm{1}_{A_{1}}.$
(42)

Plugging in the Schmidt decomposition of $W$ into the definition of
$\mathcal{E}_{1}$ in (24), we get

$\displaystyle\mathcal{E}_{1}(\rho)$
$\displaystyle=\sum_{i=1}^{r}\frac{1}{2^{n-1}}\sigma_{i}X_{i}\rho
X_{i}^{\dagger}.$ (43)

The operators $K_{i}:=\sqrt{\frac{\sigma_{i}}{2^{n-1}}}X_{i}$ can therefore be
regarded as Kraus operators for $\mathcal{E}_{1}$. Indeed, they satisfy the
following condition for trace preservation:

$\displaystyle\sum_{i=1}^{r}K_{i}^{\dagger}K_{i}$
$\displaystyle=\frac{1}{2^{n-1}}\sum_{i=1}^{r}\sigma_{i}X_{i}^{\dagger}X_{i}$
(44) $\displaystyle=\frac{1}{2^{n-1}}{\rm Tr}_{A_{2}\dotsb
A_{n}}(W^{\dagger}W)$ (45) $\displaystyle=\mathbbm{1}_{A_{1}},$ (46)

where to obtain the second equality we used (42).

Now, we assume that $\mathcal{E}_{1}$ is the identity channel, meaning that
$\mathcal{E}_{1}(\rho)=\sum_{i=1}^{r}\frac{\sigma_{i}}{2^{n-1}}X_{i}\rho
X_{i}^{\dagger}=\rho$ for all states $\rho$. By the non-uniqueness of Kraus
representations of quantum channels, there exists an isometry $V$ relating the
Kraus operators $\\{K_{i}\\}_{i=1}^{r}$ to another set $\\{N_{j}\\}_{j=1}^{s}$
of Kraus operators according to $K_{i}=\sum_{j=1}^{s}V_{i,j}N_{j}$. Since one
Kraus representation of the identity channel is the one consisting of only the
identity operator $\mathbbm{1}$, we let the set $\\{N_{j}\\}_{j=1}^{s}$
consist of only the identity operator. The isometry $V$ is then a $r\times 1$
matrix, so that $V_{i,1}=\alpha_{i}\in\mathbb{C}$ for all
$i\in\\{1,2,\dotsc,r\\}$. This implies that
$K_{i}=\sqrt{\frac{\sigma_{i}}{2^{n-1}}}X_{i}=\alpha_{i}\mathbbm{1}_{A_{1}}$
for all $i\in\\{1,2,\dotsc,r\\}$. Therefore,

$\displaystyle W_{A_{1}\dotsb A_{n}}$
$\displaystyle=\sum_{i=1}^{r}\sqrt{\sigma_{i}}X_{i}^{A_{1}}\otimes
Y_{i}^{A_{2}\dotsb A_{n}}$ (47)
$\displaystyle=\sum_{i=1}^{r}\sqrt{\sigma_{i}}\left(\sqrt{\frac{2^{n-1}}{\sigma_{i}}}\alpha_{i}\mathbbm{1}_{A_{1}}\right)\otimes
Y_{i}^{A_{2}\dotsb A_{n}}$ (48)
$\displaystyle=\mathbbm{1}_{A_{1}}\otimes\sqrt{2^{n-1}}\sum_{i=1}^{r}\alpha_{i}Y_{i}^{A_{2}\dotsb
A_{n}}$ (49) $\displaystyle=:\mathbbm{1}_{A_{1}}\otimes
W^{\prime}_{A_{2}\dotsb A_{n}},$ (50)

where in the last line we have defined the unitary $W^{\prime}_{A_{2}\dotsb
A_{n}}=\sqrt{2^{n-1}}\sum_{i=1}^{r}\alpha_{i}Y_{i}^{A_{2}\dotsb A_{n}}$.

Now, given the assumption that $\mathcal{E}_{1}=\mathcal{I}$, so that $W$ has
the form in (50), we get that

$\mathcal{E}_{2}(\rho)={\rm Tr}_{A_{3}\dotsb
A_{n}}\left(W^{\prime}\left(\rho\otimes\frac{\mathbbm{1}_{A_{3}\dotsb
A_{n}}}{2^{n-2}}\right)(W^{\prime})^{\dagger}\right).$ (51)

Therefore, applying the procedure above for $j=2$ by taking the bipartite cut
in the operator Schmidt decomposition of $W^{\prime}$ to be $A_{2}|A_{3}\dotsb
A_{n}$, we get that if $\mathcal{E}_{2}$ is the identity channel, then
$W=\mathbbm{1}_{A_{1}}\otimes\mathbbm{1}_{A_{2}}\otimes W^{\prime\prime}$ for
some unitary $W^{\prime\prime}$ acting on $A_{3}\dotsb A_{n}$. Continuing in
this manner for all $j$ up to $j=n$, assuming in each case that
$\mathcal{E}_{j}$ is the identity channel, we ultimately obtain
$W=\mathbbm{1}_{A_{1}}\otimes\mathbbm{1}_{A_{2}}\otimes\dotsb\otimes\mathbbm{1}_{A_{n}}$,
which implies that $U=V$, as required. $\square$

##  Appendix C Relation between $C_{\text{LHST}}$ and $C_{\text{HST}}$

See 2

Proof: First we rewrite the global cost function:

$\displaystyle C_{\text{HST}}(U,V)$ $\displaystyle=1-\frac{1}{d^{2}}\left|{\rm
Tr}[V^{\dagger}U]\right|^{2}$ (52) $\displaystyle=1-{\rm
Tr}[{\left|{\Phi^{+}}\right\rangle}{\left\langle{\Phi^{+}}\right|}_{AB}$
$\displaystyle\quad\times(W\otimes\mathbbm{1}_{B}){\left|{\Phi^{+}}\right\rangle}{\left\langle{\Phi^{+}}\right|}_{AB}(W^{\dagger}\otimes\mathbbm{1}_{B})],$

where $W=UV^{\dagger}$. Also, for the local cost function, we have

$C_{\text{LHST}}(U,V)\coloneqq\frac{1}{n}\sum_{j=1}^{n}C_{\text{LHST}}^{(j)}(U,V),$
(53)

where

$\displaystyle C_{\text{LHST}}^{(j)}(U,V)$ (54) $\displaystyle=1-{\rm
Tr}[\Pi_{j}(W\otimes\mathbbm{1}_{B}){\left|{\Phi^{+}}\right\rangle}{\left\langle{\Phi^{+}}\right|}_{AB}(W^{\dagger}\otimes\mathbbm{1})]$

and we have defined

$\Pi_{j}\coloneqq\mathbbm{1}_{A_{1}B_{1}}\otimes\dotsb\otimes{\left|{\Phi^{+}}\right\rangle}{\left\langle{\Phi^{+}}\right|}_{A_{j}B_{j}}\otimes\dotsb\otimes\mathbbm{1}_{A_{n}B_{n}},$
(55)

which are projectors that all mutually commute. Let

$\rho\coloneqq(W\otimes\mathbbm{1}_{B}){\left|{\Phi^{+}}\right\rangle}{\left\langle{\Phi^{+}}\right|}_{AB}(W^{\dagger}\otimes\mathbbm{1}_{B}).$
(56)

Then, we can write $C_{\text{HST}}(U,V)$ as

$C_{\text{HST}}(U,V)=1-{\rm Tr}[\Pi_{n}\dotsb\Pi_{1}\rho],$ (57)

and we can write $C_{\text{LHST}}^{(j)}(U,V)$ as

$C_{\text{LHST}}^{(j)}(U,V)=1-{\rm Tr}[\Pi_{j}\rho]$ (58)

for all $1\leqslant j\leqslant n$. If we associate the events $E_{j}$ with the
projectors $\Pi_{j}$, so that $\Pr[E_{j}]={\rm Tr}[\Pi_{j}\rho]$, then, ${\rm
Tr}[\Pi_{n}\dotsb\Pi_{1}\rho]=\Pr\left[\bigcap_{i=1}^{n}E_{i}\right]$.

To prove (28), namely $C_{\text{LHST}}(U,V)\leqslant C_{\text{HST}}(U,V)$, we
recall a basic inequality in probability theory. For any set
$\\{A_{1},A_{2},\dotsc,A_{n}\\}$ of events, it holds that

$\Pr\left[\bigcup_{i=1}^{n}A_{i}\right]\geqslant\frac{1}{n}\sum_{i=1}^{n}\Pr[A_{i}].$
(59)

Let us take $A_{i}=\overline{E_{i}}$ in (59). Then,

$\displaystyle\Pr\left[\bigcup_{i=1}^{n}\overline{E_{i}}\right]$
$\displaystyle\geqslant\frac{1}{n}\sum_{i=1}^{n}\Pr[\overline{E_{i}}]$ (60)
$\displaystyle\Rightarrow 1-\Pr\left[\bigcap_{i=1}^{n}E_{i}\right]$
$\displaystyle\geqslant\frac{1}{n}\sum_{i=1}^{n}(1-\Pr[E_{i}]).$ (61)

By definition of the events $E_{i}$, the last equality is precisely
$C_{\text{HST}}(U,V)\geqslant C_{\text{LHST}}(U,V)$, as required.

To prove (29), we make use of the union bound:

$\displaystyle\Pr\left[\bigcup_{i=1}^{n}\overline{E_{i}}\right]$
$\displaystyle\leqslant\sum_{i=1}^{n}\Pr[\overline{E_{i}}]$ (62)
$\displaystyle\Rightarrow 1-\Pr\left[\bigcap_{i=1}^{n}E_{i}\right]$
$\displaystyle\leqslant\sum_{i=1}^{n}(1-\Pr[E_{i}])$ (63)
$\displaystyle=nC_{\text{LHST}}(U,V).$ (64)

Given that the left-hand side of the above inequality is precisely
$C_{\text{HST}}(U,V)$, we have that $C_{\text{HST}}(U,V)\leqslant
nC_{\text{LHST}}(U,V)$, as required. $\square$

##  Appendix D Proofs of complexity theorems

See 1

Proof: We show that the problem of approximating the cost
$C_{\mathsf{HST}}(U,V)$ is hard for $\mathsf{DQC1}$. In other words, we have
to show that any problem in $\mathsf{DQC1}$ reduces to an instance of
approximating $C_{\mathsf{HST}}(U,V)$ for some
$\epsilon=O(1/\operatorname{poly}(n))$. Recall that, given as input a
$\operatorname{poly}(n)$-sized unitary $Q$ on $n$-qubits, any problem in
$\mathsf{DQC1}$ requires us to estimate the acceptance probability
$p_{\text{acc}}$ when measuring the outcome “$0$” on input $\rho=|\hskip
1.0pt0\rangle\langle 0\hskip 1.0pt|\otimes\mathbbm{1}/{2^{n}}$, i.e.

$\displaystyle p_{\text{acc}}={\rm Tr}[(|\hskip 1.0pt0\rangle\langle 0\hskip
1.0pt|\otimes\mathbbm{1})Q\rho Q^{\dagger}].$ (65)

Note that, since the above equation describes a probability via the positive
semi-definite operator $|\hskip 1.0pt0\rangle\langle 0\hskip
1.0pt|\otimes\mathbbm{1}$, the trace will result in a non-negative real
number. Let us re-write Eq. (65) as follows:

$\displaystyle p_{\text{acc}}=\frac{1}{2^{n}}\big{|}{\rm Tr}[(|\hskip
1.0pt0\rangle\langle 0\hskip 1.0pt|\otimes\mathbbm{1})Q(|\hskip
1.0pt0\rangle\langle 0\hskip 1.0pt|\otimes\mathbbm{1})Q^{\dagger}]\big{|}.$
(66)

Figure 11: The trace of the unitary $U^{\prime}$ defined by the circuit above
is equal to the trace of the non-unitary operator $(|\hskip
1.0pt0\rangle\langle 0\hskip 1.0pt|\otimes\mathbbm{1})Q(|\hskip
1.0pt0\rangle\langle 0\hskip 1.0pt|\otimes\mathbbm{1})Q^{\dagger}$ up to a
factor of $4$ [44].

When letting $U^{\prime}$ as in Fig. 11, we can also write

$\displaystyle{\rm Tr}[(|\hskip 1.0pt0\rangle\langle 0\hskip
1.0pt|\otimes\mathbbm{1})Q(|\hskip 1.0pt0\rangle\langle 0\hskip
1.0pt|\otimes\mathbbm{1})Q^{\dagger}]={\rm Tr}[U^{\prime}]/4,$ (67)

hence the problem is equivalent to approximating the absolute value of the
trace of a unitary $U^{\prime}$. In fact, given our choice of $U^{\prime}$ and
when taking $V$ to be the identity, the problem reduces to an instance of
approximating the cost $C_{\mathsf{HST}}(U^{\prime},\mathbbm{1})$ up to some
precision $\epsilon=O(1/\operatorname{poly}(n))$ via a simple reduction.
Therefore, we have shown that the problem of approximating
$C_{\mathsf{HST}}(U,V)$ up to $\epsilon$-precision is $\mathsf{DQC1}$-hard.
$\square$

See 2

Proof: We show that any problem in $\mathsf{DQC1}$ reduces to an instance of
approximating $C_{\mathsf{LHST}}(U,V)$ via a reduction. We are given as input
a $\operatorname{poly}(n)$-sized unitary $Q$ on $n$-qubits, and the task is to
estimate the acceptance probability of outputting $``0"$. Our proof strategy
is to show that one can efficiently extract ${\rm Tr}(U^{\prime})$, the trace
of an $n$-qubit unitary $U^{\prime}$, from two distinct evaluations of
$C_{\mathsf{LHST}}$ and elementary post-processing. This implies that
computing $C_{\mathsf{LHST}}$ is hard for $\mathsf{DQC1}$, since all problems
in $\mathsf{DQC1}$ can be seen as estimating the real part of ${\rm
Tr}(U^{\prime})$ via Eq. (66) and Eq. (67).

The two cost function evaluations that we consider are
$C_{\mathsf{LHST}}(U_{1},\mathbbm{1})$ and
$C_{\mathsf{LHST}}(U_{2},\mathbbm{1})$, where

$\displaystyle U_{1}$ $\displaystyle=U^{\prime}$ (68) $\displaystyle U_{2}$
$\displaystyle=C_{U^{\prime}}\,.$ (69)

Here, $C_{U^{\prime}}$ denotes controlled-$U^{\prime}$ operation.

First, consider $U_{2}$ and let the $j=n+1$ qubit correspond to the control
qubit for the $C_{U^{\prime}}$ controlled unitary. Then one can show that

$\displaystyle C_{\mathsf{LHST}}^{(j)}(U_{2},\mathbbm{1})$
$\displaystyle=\frac{1}{2}C_{\mathsf{LHST}}^{(j)}(U_{1},\mathbbm{1})\quad\forall
j\in\\{1,...,n\\}\,,$ (70) $\displaystyle
C_{\mathsf{LHST}}^{(n+1)}(U_{2},\mathbbm{1})$
$\displaystyle=\frac{1}{2}-\frac{1}{2^{n+1}}\text{Re}({\rm
Tr}(U^{\prime}))\,.$ (71)

This gives

$\displaystyle C_{\mathsf{LHST}}(U_{2},\mathbbm{1})=\frac{1}{2(n+1)}$
$\displaystyle\bigg{(}1+nC_{\mathsf{LHST}}(U_{1},\mathbbm{1})$
$\displaystyle-\frac{\text{Re}({\rm Tr}(U^{\prime}))}{2^{n}}\bigg{)}\,.$ (72)

For notational simplicity, let $B(U):=1-C_{\mathsf{LHST}}(U,\mathbbm{1})$.
Then, we can rewrite Eqs. (D) as

$\displaystyle B(U_{2})$
$\displaystyle=\frac{1}{2}\left(1+\frac{2^{-n}}{n+1}\text{Re}({\rm
Tr}(U^{\prime}))+\frac{n}{n+1}B(U_{1})\right)\,.$ (73)

Hence, we have that

$\displaystyle\text{Re}({\rm Tr}(U^{\prime}))$
$\displaystyle=2^{n}\left((n+1)(2B(U_{2})-1)-nB(U_{1})\right)\,.$ (74)

By choosing $U^{\prime}$ according to Fig. 11, one can see from Eq. (66) and
Eq. (67) that the problem is equivalent to $\epsilon$-approximating our local
cost function for some $\epsilon=O(1/\operatorname{poly}(n))$. Hence, any
$\mathsf{DQC1}$ problem can be efficiently solved for by computing a simple
linear combination of two instances of $C_{\mathsf{LHST}}$. Therefore, we have
shown that the problem of approximating the cost $C_{\mathsf{LHST}}(U,V)$ is
hard for $\mathsf{DQC1}$. $\square$

##  Appendix E Gradient-free optimization method

We now outline our approach to gradient-free optimization of over the
continuous gate parameters $\boldsymbol{\alpha}$ in the trainable unitary
$V_{\boldsymbol{k}}(\boldsymbol{\alpha})$. This approach was used to obtain
the results in Sec. 6. Given that this is an implementation for small problem
size, we employ the cost function
$C_{\text{HST}}(U,V_{\boldsymbol{k}}(\boldsymbol{\alpha}))$. However, we note
that one can replace $C_{\text{HST}}$ with our general cost function $C_{q}$
for larger problem sizes.

Input: Unitary $U$ to be compiled; trainable unitary
$V_{\boldsymbol{k}}(\boldsymbol{\alpha})$ of a given structure; error
tolerance $\varepsilon^{\prime}\in(0,1)$; maximum number of starting points
$N$; maximum number of iterations $N_{\text{iter}}$ for gp_minimize; sample
precision $\delta>0$.

Output: Parameters $\boldsymbol{\alpha}_{\text{opt}}$ such that at best
$C_{\text{HST}}(U,V_{\boldsymbol{k}}(\boldsymbol{\alpha}_{\text{opt}}))\leqslant\varepsilon^{\prime}$.

Init: $\boldsymbol{\alpha}_{\text{opt}}\leftarrow 0;\texttt{cost}\leftarrow 1$

1 repeat

2 choose an initial parameter $\boldsymbol{\alpha}^{(0)}$ at random;

3 run gp_minimize with $\boldsymbol{\alpha}^{(0)}$ and $N_{\text{iter}}$ as
input and $\boldsymbol{\alpha}_{\min}$ as output; whenever the cost is called
upon for some $\boldsymbol{\alpha}$, run the HST on
$V_{\boldsymbol{k}}(\boldsymbol{\alpha})^{*}$ and $U$ approximately
$1/\delta^{2}$ times to estimate the cost
$C_{\text{HST}}(U,V_{\boldsymbol{k}}(\boldsymbol{\alpha}))$;

4 if  _${\texttt{cost}}\geqslant
C_{\text{HST}}(U,V_{\boldsymbol{k}}(\boldsymbol{\alpha}_{\min}))$_ then

5 ${\texttt{cost}}\leftarrow
C_{\text{HST}}(U,V_{\boldsymbol{k}}(\boldsymbol{\alpha}_{\min}))$;
$\boldsymbol{\alpha}_{\text{opt}}\leftarrow\boldsymbol{\alpha}_{\min}$

6

7until  _$\texttt{cost}\leqslant\varepsilon^{\prime}$ , at most $N$ times._

8return _$\boldsymbol{\alpha}_{\textnormal{opt}},{\texttt{cost}}$_

Algorithm 1 Gradient-free Continuous
Optimization for QAQC via the HST

Recall that we compute the cost function
$C_{\text{HST}}(U,V_{\boldsymbol{k}}(\boldsymbol{\alpha}))$ using the Hilbert-
Schmidt Test (HST), as described in Sec. 4.1 and illustrated in Fig. 4(a). For
a given set of gate structure parameters $\boldsymbol{k}$, the calculation of
the cost on a quantum computer (as well as on a simulator) is affected by the
fact that, due to finite sampling, the HST allows us to obtain only an
estimate of the magnitude of the Hilbert-Schmidt inner product. Noise within
the quantum computer itself also affects the calculation of the cost.
Therefore, in order to perform gradient-free optimization over the continuous
gate parameters $\boldsymbol{\alpha}$, we make use of stochastic optimization
techniques that are designed to optimize noisy functions. Specifically, we
make use of the gp_minimize routine in the scikit-optimize Python library
[54], which is a gradient-free optimization routine that performs Bayesian
optimization using Gaussian processes [55, 56]. See Algorithm 1 for a general
overview of the optimization procedure. Note that with this algorithm, we
obtain an $\varepsilon$-approximate compilation of $U$, with

$\varepsilon=\left(\frac{d}{d+1}\right)\varepsilon^{\prime}\,.$ (75)

In the small-scale quantum computer implementations of Fig. 5(c) and Fig. 6,
we use 50 objective function evaluations in gp_minimize per iteration. Note
that evaluating the objective function involves running the quantum circuit
many times in order to sample from the output distribution of the circuit.

For large problem sizes, as described in Sec. 3.4, we propose using the cost
function $C_{q}=qC_{\text{HST}}+(1-q)C_{\text{LHST}}$. The gradient-free
continuous parameter optimization algorithm for $C_{q}$ is similar to the one
for $C_{\text{HST}}$ in Algorithm 1, except that in addition to running the
HST we run the LHST for every qubit $j\in\\{1,2,\dotsc,n\\}$ in order to
compute the local cost $C_{\text{LHST}}$. In this case, the algorithm provides
an $\varepsilon$-approximate compilation of $U$, with

$\varepsilon=\left(\frac{n}{1-q+nq}\right)\left(\frac{d}{d+1}\right)\varepsilon^{\prime}\,.$
(76)

We emphasize that our approach to gradient-free optimization avoids the
exponential overhead of evaluating the cost function classically, yet at the
same time makes use of fast and efficient classical heuristics for
optimization. In fact, using the HST, Algorithm 1 requires only
$O(1/\delta^{2})$ calls to the quantum computer in order to evaluate the cost,
where $\delta=1/\sqrt{n_{\text{shots}}}$ is the sample precision, which is
related to the number of samples $n_{\text{shots}}$ taken from the device.

###  E.1 Alternative method for gradient-free optimization

Here we propose an alternative algorithm for gradient-free optimization that,
on average, significantly reduces the number of times the objective function
is evaluated. As a result, it is more suitable for cloud computing under a
queue submission system (e.g., IBM’s Quantum Experience). This algorithm
performs a “multi-scale bisection” of the parameter space based on simulated
annealing. We implement this method in Sec. 6.1.1 specifically for the
hardware of IBM because the queue submission system can require a significant
amount of time to make many calls to the quantum computer.

This alternative approach to performing gradient-free continuous parameter
optimization is outlined in Algorithm 2. We start with four angles spread
uniformly in the interval $[0,2\pi)$—namely $0,\pi/2,\pi,$ and $3\pi/2$. This
significantly reduces the size of the search space and allows us to get close
to, or find exactly, an optimal gate sequence. Once the optimal structure is
reached from this step, we then bisect the angles for each gate
$R_{z}(\alpha)$ by evaluating the cost with a new circuit containing
$R_{z}(\alpha\pm\pi/2^{t+1})$, where $t=1,2,\dots,t_{\max}$ is determined by
the iteration in the procedure. Although we do not explore all angles in the
interval, the runtime is logarithmically faster than a continuous search due
to the bisection procedure. An additional advantage of this approach is that
many gates have angles that are simple fractions of $\pi$, e.g.,
$T=R_{z}(\pi/4)$ and $H=R_{z}(\pi/2)R_{x}(\pi/2)R_{z}(\pi/2)$. In a noiseless
environment, the two steps above are sufficient. On actual devices, we
implement a third step of stochastic optimization by evaluating the cost for
the new circuit with each gate $R_{z}(\alpha)$ replaced by
$R_{z}(\alpha\pm\Delta(t))$ for some small value $\Delta(t)\ll 1$ decreasing
monotonically with the iteration $t$. This allows us to compile for a given
device by accounting for noise and gate errors. This can be thought of as a
“fine-grained” angular optimization in contrast to the previous “coarse-
grained” angular optimization.

Input: Unitary $U$ to be compiled; trainable unitary
$V_{\boldsymbol{k}}(\boldsymbol{\alpha})$ of a given structure and gate
alphabet $\mathcal{A}$; error tolerance $\varepsilon^{\prime}\in(0,1)$;
maximum number of iterations $N$; maximum number of bisections $t_{\max}$ of
the unit circle; sample precision $\delta>0$.

Output: Parameters $\boldsymbol{\alpha}_{\text{opt}}$ such that at best
$C_{\text{HST}}(U,V_{\boldsymbol{k}}(\boldsymbol{\alpha}_{\text{opt}}))\leqslant\varepsilon^{\prime}$.

Init: Restrict all gates in $\mathcal{A}$ with continuous parameters to
discrete angles in the set $\Omega_{0}=\\{0,\pi/2,\pi,3\pi/2\\}$;
$\alpha_{\text{opt}}\leftarrow 0;\texttt{cost}\leftarrow 1$

1 for  _$t=1,2,\dots,t_{\max}$_ do

2 repeat

3 anneal over all possible bisected angles in the set
$\Omega_{t}:=\\{\alpha\pm\pi/2^{t+1}\,|\,\text{for
}\alpha\in\Omega_{0}\\}\cup\Omega_{t-1}$;

4 whenever the cost is called upon for some $\alpha\in\Omega_{t}$, run the HST
on $V_{\boldsymbol{k}}(\boldsymbol{\alpha})^{*}$ and $U$ approximately
$1/\delta^{2}$ times to estimate the cost
$C_{\text{HST}}(U,V_{\boldsymbol{k}}(\boldsymbol{\alpha}))$;

5 if  _${\texttt{cost}}\geqslant
C_{\text{HST}}(U,V_{\boldsymbol{k}}(\boldsymbol{\alpha}))$_ then

6 ${\texttt{cost}}\leftarrow
C_{\text{HST}}(U,V_{\boldsymbol{k}}(\boldsymbol{\alpha}))$;

7

8 until  _$\texttt{cost}\leqslant\varepsilon^{\prime}$ at most $N$ times._

9 repeat

10 minimize the cost over all small continuous increments $\Delta(t)\ll 1$
within the set of bisected angles $\Omega_{t}$; whenever the cost is called
upon for some $\alpha+\Delta(t)$, with $\alpha\in\Omega_{t}$, run the HST on
$V_{\boldsymbol{k}}(\alpha+\Delta(t))^{*}$ and $U$ approximately
$1/\delta^{2}$ times to estimate the cost
$C_{\text{HST}}(U,V_{\boldsymbol{k}}(\alpha+\Delta(t)))$;

11 if  _${\texttt{cost}}\geqslant
C_{\text{HST}}(U,V_{\boldsymbol{k}}(\alpha+\Delta(t)))$_ then

12 ${\texttt{cost}}\leftarrow
C_{\text{HST}}(U,V_{\boldsymbol{k}}(\alpha+\Delta(t)))$;
$\boldsymbol{\alpha}_{\text{opt}}\leftarrow\alpha+\Delta(t)$

13

14 until  _$\texttt{cost}\leqslant\varepsilon^{\prime}$ at most $N$ times._

15return _$\boldsymbol{\alpha}_{\textnormal{opt}},{\texttt{cost}}$_

Algorithm 2 Gradient-free Optimization
using Bisection for QAQC

##  Appendix F Gradient-based optimization method

We now describe a gradient-based approach to performing the optimization over
the continuous parameters in the trainable gate sequence
$V_{\boldsymbol{k}}(\boldsymbol{\alpha})$. In Sec. F.1, we define a new cost
function for this purpose, and we introduce a quantum circuit to calculate
this cost function on a quantum computer. In Sec. F.2, we present the results
of implementing this method on a quantum simulator. In Sec. F.3, we briefly
describe how the original cost functions $C_{\text{HST}}$ and
$C_{\text{LHST}}$ can also be optimized using a gradient-based method.

While recent work on gradient descent continuous optimization has shown vast
quantum speedups over classical variants [57, 58, 59], the majority of
proposals still appear to be out of reach for implementations on NISQ devices,
mainly due to their use of certain algorithmic techniques, such as quantum
random-access memory, the quantum Fourier transform, and the Grover search
algorithm, which have high resource requirements. Instead, we focus on
continuous optimization procedures that are feasible on current quantum
computers and leave improvements to our algorithms as an open problem.

The gradient with respect to $\boldsymbol{\alpha}$ of the gate sequence
$V_{\boldsymbol{k}}(\boldsymbol{\alpha})$ given by

$V_{\boldsymbol{k}}(\boldsymbol{\alpha})=G_{k_{L}}(\alpha_{L})G_{k_{L-1}}(\alpha_{L-1})\dotsb
G_{k_{1}}(\alpha_{1}),$ (77)

is defined by

$\nabla_{\boldsymbol{\alpha}}V_{\boldsymbol{k}}(\boldsymbol{\alpha})=\left(\frac{\partial
V_{\boldsymbol{k}}(\boldsymbol{\alpha})}{\partial\alpha_{1}},\dotsc,\frac{\partial
V_{\boldsymbol{k}}(\boldsymbol{\alpha})}{\partial\alpha_{L}}\right),$ (78)

where the $(i,j)$ matrix element of the $\ell$-th component is

$\left(\frac{\partial
V_{\boldsymbol{k}}(\boldsymbol{\alpha})}{\partial\alpha_{\ell}}\right)_{i,j}=\frac{\partial
V_{\boldsymbol{k}}(\boldsymbol{\alpha})_{i,j}}{\partial\alpha_{\ell}}.$ (79)

For example, consider the rotation gate
$R_{z}(\alpha)=e^{-i\alpha\sigma_{z}/2}$, which is parametrized by the angle
$\alpha$. Then, the derivative with respect to $\alpha$ can be written as

$\frac{\partial}{\partial\alpha}R_{z}(\alpha)=-\frac{i}{2}\sigma_{z}R_{z}(\alpha)\
,$ (80)

which follows from the Taylor series expansion of the exponent.

Now, evaluating the gradient on a quantum computer is possible due to the fact
that for the gate alphabets we consider in this paper, only the single-qubit
gates are parameterized, and these gates are simply rotation gates. In fact,
any unitary gate can be decomposed into circuits in which only the single-
qubit rotation gates are present. This is illustrated in Fig. 12. Furthermore,
the circuits in Fig. 12(a) and Fig. 12(b) are universal for one- and two-qubit
gates, respectively (see [60], which also contains universal circuits for
$n$-qubit gates). This means that our gradient-based approach can be applied
to any $n$-qubit unitary without explicitly searching over gate structures,
though the compilations obtained in this manner will generally have sub-
optimal depth.

Figure 12:  (a) Any single-qubit gate $U$ can be decomposed into three
elementary rotations (up to a global phase). Given appropriate parameters
$\boldsymbol{\alpha}=(\alpha_{z_{1}},\alpha_{y},\alpha_{z_{2}})$, $U$ can be
written as
$V(\boldsymbol{\alpha})=e^{-i\alpha_{z_{2}}\sigma_{z}/2}e^{-i\alpha_{y}\sigma_{y}/2}e^{-i\alpha_{z_{1}}\sigma_{z}/2}$.
(b) Any two-qubit gate $U_{AB}$ can be decomposed into three CNOT gates as
well as $15$ elementary single-qubit gates, where each unitary
$U_{j}(\boldsymbol{\alpha}^{(j)})$ can be written as in (a). This
decomposition is known to be optimal [61], i.e., it uses the least number of
continuous parameters and CNOT gates. General universal quantum circuits for
$n$-qubit gates are discussed in [60].

###  F.1 The Power of Two Qubits

Consider the following cost function based on the normalized Hilbert-Schmidt
distance between the unitaries $U$ and $V$:

$\displaystyle C_{\text{POTQ}}(U,V)$
$\displaystyle\coloneqq\frac{1}{2d}|\\!|U-V|\\!|_{\text{HS}}^{2}$ (81)
$\displaystyle=1-\frac{1}{d}\text{Re}\left[{\rm Tr}(V^{\dagger}U)\right],$

where POTQ stands for “Power of Two Qubits” and refers to the circuit used to
evaluate it, which we present below. Note that $C_{\text{POTQ}}(U,V)$ is zero
if and only if $U=V$. Contrary to the cost function $C_{\text{HST}}(U,V)$,
which is defined using the magnitude of the inner product $\langle
V,U\rangle$, this cost function is defined using the real part of the inner
product. Consequently, it does not vanish if $U$ and $V$ differ only by a
global phase. Indeed, if $V=e^{i\varphi}U$, then
$C_{\text{POTQ}}(U,V)=1-\cos(\varphi)$.

Before discussing the circuit used to evaluate the cost function
$C_{\text{POTQ}}(U,V)$, let us review the Power of One Qubit (POOQ) [26],
shown in Fig. 13(a), which is a circuit for computing the trace of a
$d$-dimensional unitary $U$. This circuit acts on a $d$-dimensional system
$A$, initially in the maximally mixed state, $\mathbbm{1}/d$, and on a single-
qubit ancilla $Q$ initially in the ${\left|{0}\right\rangle}$ state. After
applying a Hadamard gate to $Q$ and a controlled-$U$ gate to $QA$ (with $Q$
the control system), the reduced density matrix $\rho_{Q}$ has its off-
diagonal elements proportional to ${\rm Tr}(U)$. Hence, one can measure $Q$ in
the $X$ and $Y$ bases, respectively, to read off the real and imaginary parts
of ${\rm Tr}(U)$.

We now introduce a circuit for computing the real and imaginary parts of
$\langle V,U\rangle$ that generalizes the POOQ and is called the Power of Two
Qubits (POTQ), depicted in Fig. 13(b). As the name suggests, the POTQ employs
two single-qubit ancillas, $Q$ and $Q^{\prime}$, each initially in the
${\left|{0}\right\rangle}$ state. In addition, two $d$-dimensional systems,
$A$ and $B$, are initially prepared in the Bell state
${\left|{\Phi^{+}}\right\rangle}$ defined in Eq. (14). (Although not shown in
Fig. 13(b), this Bell state is prepared with a depth-two circuit, as shown in
Fig. 4.)

The first step in the POTQ is to prepare the two-qubit maximally entangled
state
$\frac{1}{\sqrt{2}}({\left|{0}\right\rangle}{\left|{0}\right\rangle}+{\left|{1}\right\rangle}{\left|{1}\right\rangle})$
between $Q$ and $Q^{\prime}$, using the Hadamard and CNOT gates as shown in
Fig. 13(b). The second step is to apply a controlled-$U$ gate between $Q$ and
$A$ (with $Q$ the control system). In parallel with this gate, the
anticontrolled-$V^{T}$ gate is applied to $Q^{\prime}B$, with $Q^{\prime}$ the
control system, where anticontrolled means that the roles of the
${\left|{0}\right\rangle}$ and ${\left|{1}\right\rangle}$ states on the
control system are reversed in comparison to a controlled gate. This results
in the state:

$\displaystyle\frac{1}{\sqrt{2}}({\left|{0}\right\rangle}_{Q}{\left|{0}\right\rangle}_{Q^{\prime}}(\mathbbm{1}_{A}\otimes
V^{T}){\left|{\Phi^{+}}\right\rangle}$ $\displaystyle\hskip
10.0pt+{\left|{1}\right\rangle}_{Q}{\left|{1}\right\rangle}_{Q^{\prime}}(U\otimes\mathbbm{1}_{B}){\left|{\Phi^{+}}\right\rangle})$
$\displaystyle=\frac{1}{\sqrt{2}}({\left|{0}\right\rangle}_{Q}{\left|{0}\right\rangle}_{Q^{\prime}}(V\otimes\mathbbm{1}_{B}){\left|{\Phi^{+}}\right\rangle}$
$\displaystyle\hskip
10.0pt+{\left|{1}\right\rangle}_{Q}{\left|{1}\right\rangle}_{Q^{\prime}}(U\otimes\mathbbm{1}_{B}){\left|{\Phi^{+}}\right\rangle}),$
(82)

where to obtain the equality we used the ricochet property in Eq. (18). As in
the HST, note that $V$ itself is not implemented. In this case, its transpose
is implemented.

Finally, a CNOT gate is applied to $QQ^{\prime}$, with $Q$ the control system.
This results in the reduced state on $Q$ being

$\displaystyle\rho_{Q}=\frac{1}{2}\left({\left|{0}\right\rangle}{\left\langle{0}\right|}+{\rm
Tr}(V^{\dagger}U){\left|{0}\right\rangle}{\left\langle{1}\right|}\right.$
$\displaystyle\qquad\quad\left.+{\rm
Tr}(U^{\dagger}V){\left|{1}\right\rangle}{\left\langle{0}\right|}+{\left|{1}\right\rangle}{\left\langle{1}\right|}\right).$
(83)

By inspection of $\rho_{Q}$, one can see that measuring $Q$ in the $X$ and $Y$
bases, respectively, gives the real and imaginary parts of ${\rm
Tr}(V^{\dagger}U)$.

Figure 13: (a) The Power of One Qubit (POOQ) [26]. This can be used to compute
the trace of a unitary $U$ acting on a $d$-dimensional space. The $R$ gate
represents either $H$, in which case the circuit computes $\text{Re}[{\rm
Tr}(U)]$, or the $S$ gate followed by $H$, in which case the circuit computes
$\text{Im}[{\rm Tr}(U)]$. (b) The Power of Two Qubits (POTQ). This is a
generalization of the POOQ, as can be seen by setting $V=\mathbbm{1}$. The
POTQ can be used to compute the Hilbert-Schmidt inner product ${\rm
Tr}(V^{\dagger}U)$ between two unitaries $U$ and $V$ acting on a
$d$-dimensional space. As with the POOQ, $R=H$ leads to $\text{Re}[{\rm
Tr}(V^{\dagger}U)]$, while $R=HS$ leads to $\text{Im}[{\rm
Tr}(V^{\dagger}U)]$.

Interestingly, if we set $V$ to the identity in the POTQ, then since the CNOT
gate commutes with the controlled-$U$ gate and the reduced state of
${\left|{\Phi^{+}}\right\rangle}$ is the maximally mixed state
$\mathbbm{1}/d$, we recover the POOQ. The POTQ is therefore a generalization
of the POOQ.

Note that while the POOQ can also be used to determine ${\rm
Tr}(V^{\dagger}U)$, the POTQ has the advantage that the controlled gates for
$U$ and $V$ can be executed in parallel, while in the POOQ they would have to
be executed in series. This makes the POTQ better suited for NISQ devices,
where short depth is crucial. Consider the depth of the POTQ. Denoting the
controlled-$U$ and the anticontrolled-$V^{T}$ as $C_{U}$ and
$\overline{C}_{V^{T}}$ respectively, the overall depth is

$\displaystyle D(\text{POTQ})=4+\max\\{D(C_{U}),D(\overline{C}_{V^{T}})\\}$
(84)

Note the similarity here to Eq. (19). The overall depth is essentially
determined by whichever controlled gate has the largest depth.

###  F.2 Gradient-based optimization via the POTQ

The gradient with respect to $\boldsymbol{\alpha}$ of
$C_{\text{POTQ}}(U,V_{\boldsymbol{k}}(\boldsymbol{\alpha}))$ can be computed
using the POTQ. This is due to the fact that

$\frac{\partial}{\partial\alpha_{\ell}}\text{Re}\left[{\rm
Tr}(V_{\boldsymbol{k}}(\boldsymbol{\alpha})^{\dagger}U)\right]=\frac{1}{2}\text{Re}\left[{\rm
Tr}\left(\widetilde{V}_{\boldsymbol{k}}^{(\ell)}(\boldsymbol{\alpha})^{\dagger}U\right)\right],$
(85)

where

$\displaystyle\widetilde{V}_{\boldsymbol{k}}^{(\ell)}(\boldsymbol{\alpha})$
$\displaystyle\coloneqq G_{k_{L}}(\alpha_{L})\dotsb
G_{k_{\ell+1}}(\alpha_{\ell+1})(-i\sigma_{k_{\ell}})$ (86)
$\displaystyle\quad\quad\times
G_{k_{\ell}}(\alpha_{\ell})G_{k_{\ell-1}}(\alpha_{\ell-1})\dotsb
G_{k_{1}}(\alpha_{1})$

is the original gate sequence $V_{\boldsymbol{k}}(\boldsymbol{\alpha})$ except
with an additional Pauli gate $\sigma_{k_{\ell}}$ corresponding to the
variable with respect to which the derivative is taken. (Note that for the
gate alphabets that we consider in this paper, only the single-qubit gates are
parameterized, and these gates are simply rotation gates. The derivative of
any one-qubit rotation gate is analogous to the expression in (80) for the
derivative of the rotation gate $R_{z}(\alpha)$.) This means that to compute
the gradient of $C_{\text{POTQ}}(U,V_{\boldsymbol{k}}(\boldsymbol{\alpha}))$,
we simply add the appropriate local Pauli gate to the original gate sequence
and run the POTQ on this new gate sequence.

Input: Unitary $U$ to be compiled; a trainable unitary
$V_{\boldsymbol{k}}(\boldsymbol{\alpha})$ of a given structure, where
$\boldsymbol{\alpha}$ is a continuous circuit parameter of dimension $L$;
maximum number of iterations $N$; error tolerance
$\varepsilon^{\prime}\in(0,1)$; learning rate $\eta>0$; sample precision
$\delta>0$.

Output: Parameters $\boldsymbol{\alpha}_{\text{opt}}$ such that at best
$C_{\text{POTQ}}(U,V_{\boldsymbol{k}}(\boldsymbol{\alpha_{\text{opt}}}))\leqslant\varepsilon^{\prime}$.

Init: $\boldsymbol{\alpha}_{\text{opt}}\leftarrow 0;\texttt{cost}\leftarrow 1$

1 repeat

2 choose initial parameters $\boldsymbol{\alpha}^{(0)}$ at random

3 for  _$\tau=1,2,\dots,T$_ do

4 for  _$i=1,2,\dots,L$_ do

5 run the POTQ on
$\partial_{\alpha_{i}}V_{\boldsymbol{k}}(\boldsymbol{\alpha}^{(\tau-1)})^{T}$
and $U$ approximately $1/{\delta^{2}}$ times to estimate $\text{Re}\left({\rm
Tr}\left[\partial_{\alpha_{i}}V_{\boldsymbol{k}}(\boldsymbol{\alpha}^{(\tau-1)})^{\dagger}U\right]\right)$

6 update
$\boldsymbol{\alpha}^{(\tau)}\leftarrow\boldsymbol{\alpha}^{(\tau-1)}-\eta\,\nabla_{\boldsymbol{\alpha}}C_{\text{POTQ}}(U,V_{\boldsymbol{k}}(\boldsymbol{\alpha}^{(\tau-1)}))$

7

8 run the POTQ on $V_{\boldsymbol{k}}(\boldsymbol{\alpha}^{(\tau)})^{T}$ and
$U$ approximately $1/{\delta^{2}}$ times to estimate the cost
$C_{\text{POTQ}}(U,V_{\boldsymbol{k}}(\boldsymbol{\alpha}^{(\tau)}))$

9 if  _${\texttt{cost}}\geqslant
C_{\text{POTQ}}(U,V_{\boldsymbol{k}}(\boldsymbol{\alpha}^{(\tau)}))$_ then

10 ${\texttt{cost}}\leftarrow
C_{\text{POTQ}}(U,V_{\boldsymbol{k}}(\boldsymbol{\alpha}^{(\tau)}))$;
$\boldsymbol{\alpha}_{\text{opt}}\leftarrow\boldsymbol{\alpha}^{(\tau)}$

11

12until  _${\texttt{cost}}\leqslant\varepsilon^{\prime}$ , at most $N$ times_

13return _$\boldsymbol{\alpha}_{\textnormal{opt}},{\texttt{cost}}$_

Algorithm 3 Gradient-based Continuous
Optimization for QAQC via the POTQ

Our gradient-based optimization procedure is outlined in Algorithm 3. Given an
arbitrary unitary $U$ as input, Algorithm 3 compiles $U$ to a unitary
$V_{\boldsymbol{k}}(\boldsymbol{\alpha}_{\text{opt}})$ of a given structure
$\boldsymbol{k}$ that minimizes the cost $C_{\text{POTQ}}$. The gradient is