[ beforeskip=.5em plus 1pt,pagenumberformat=]toclinesection

††thanks: This work was supported by the CDT in Cyber Security at the
University of Oxford (EP/P00881X/1) and the Additional Funding Programme for
Mathematical Sciences, delivered by EPSRC (EP/V521917/1) and the Heilbronn
Institute for Mathematical Research.

# Shorter quantum circuits

Vadym Kliuchnikov  Microsoft Quantum, Redmond, WA, US  Microsoft Quantum,
Toronto, ON, CA  Kristin Lauter  Facebook AI Research, Seattle, WA, US  Romy
Minko  University of Oxford, Oxford, UK  Heilbronn Institute for Mathematical
Research, University of Bristol, Bristol, UK  Adam Paetznick  Microsoft
Quantum, Redmond, WA, US  Christophe Petit  University of Birmingham,
Birmingham, UK  Université Libre de Bruxelles, Brussels, Belgium

###### Abstract

We give a novel procedure for approximating general single-qubit unitaries
from a finite universal gate set by reducing the problem to a novel magnitude
approximation problem, achieving an immediate improvement in sequence length
by a factor of 7/9. Extending the work of [Hastings2017, Campbell2017], we
show that taking probabilistic mixtures of channels to solve fallback
[BRS2015] and magnitude approximation problems saves factor of two in
approximation costs. In particular, over the Clifford+$\sqrt{\textnormal{T}}$
gate set we achieve an average non-Clifford gate count of
$0.23\log_{2}(1/\varepsilon)+2.13$ and T-count
$0.56\log_{2}(1/\varepsilon)+5.3$ with mixed fallback approximations for
diamond norm accuracy $\varepsilon$.

This paper provides a holistic overview of gate approximation, in addition to
these new insights. We give an end-to-end procedure for gate approximation for
general gate sets related to some quaternion algebras, providing pedagogical
examples using common fault-tolerant gate sets (V, Clifford+T and
Clifford+$\sqrt{\textnormal{T}}$). We also provide detailed numerical results
for Clifford+T and Clifford+$\sqrt{\textnormal{T}}$ gate sets. In an effort to
keep the paper self-contained, we include an overview of the relevant
algorithms for integer point enumeration and relative norm equation solving.
We provide a number of further applications of the magnitude approximation
problems, as well as improved algorithms for exact synthesis, in the
Appendices.

###### Contents

  1. 1 Introduction
    1. 1.1 Fault tolerant gate sets
  2. 2 Summary of main results
    1. 2.1 Example: V basis diagonal approximation of $e^{i\frac{\pi}{4}Z}$
  3. 3 Connections to cryptography and hash functions
  4. 4 Approximation problems
    1. 4.1 Magnitude approximation
    2. 4.2 Diagonal unitary approximation
    3. 4.3 Fallback approximation
    4. 4.4 Mixed diagonal unitary approximation
    5. 4.5 Mixed fallback approximation
    6. 4.6 Mixed magnitude approximation
    7. 4.7 Geometric interpretations
  5. 5 Solutions to approximation problems for common gate sets
    1. 5.1 V basis

##  1 Introduction

In the quantum circuit model, quantum algorithms are expressed as sequences of
unitary operations and measurements. Any $n$-qubit unitary can be implemented
by a circuit of elementary gates, comprising controlled-NOT (CNOT) gates and
single-qubit gates [Barenco1995]. Fault tolerant quantum computers require
that the single-qubit gates belong to a finite set. Such a set is called
universal if it generates a dense covering of $SU(2)$. That is, if any unitary
$U\in SU(2)$ can be approximated to any accuracy by a finite sequence of gates
from the set. Of particular interest is the subject of approximating single-
qubit diagonal unitaries, as a Euler decomposition guarantees that any single-
qubit unitary can be decomposed into diagonal $R_{z}$\- and $R_{x}$-rotations.
In addition, diagonal $R_{z}$ rotations are directly used in many quantum
algorithm.

The cost of an approximation is quantified by the gate complexity, or gate
cost. Associating each gate $g_{i}$ in a sequence with a weight $w_{i}$, the
gate cost of that sequence is $\sum_{i}w_{i}$. The gate cost of approximating
$U$ to within $\varepsilon$ is then taken as the minimum gate cost of all
possible approximating sequences. Note that select gates, such as the Pauli or
Clifford gates, are considered cheap to implement and so take zero weight.
Typically, expensive gates will be given a weight of 1, so that the gate cost
of an approximation corresponds to the number of expensive gates in the
sequence. Consequently, minimizing the length of an approximating sequence is
a problem integral to the subject of gate synthesis. A fundamental and general
result is the Solovay-Kitaev theorem, which states that a universal gate-set
$G$ can approximate any unitary $U\in SU(2)$ to accuracy $\varepsilon$ by a
finite sequence of gates from $G$ of length $O(\log^{c}(1/\varepsilon))$,
where $c$ is a constant. Significant progress has been made since Solovay-
Kitaev for specific gate-sets associated with fault-tolerant quantum
computers. Bourgain and Gamburd [bourgain2011spectral] showed that universal
gate-sets of unitaries with algebraic entries give approximating sequences
with lengths $O(\log(1/\varepsilon))$. This result was quickly applied to find
efficient constructive algorithms for the Clifford$+$T gate set [A3, Selinger]
and, later, the V basis [BGS]. Constructive algorithms for optimal diagonal
approximations for both gate sets followed soon thereafter [RossSelinger2014,
Ross2015, Blass2015]. Many of these algorithms adopted a common framework of
integer point enumeration followed by a solving a norm equation. Measurements
were also introduced to aid gate synthesis [paetznick2013repeat], culminating
in the fall-back circuit [BocharovRoettelerSvore2014], although this work was
a departure from the common framework. Sarnak [sarnak2637letter] noted a
connection between gate synthesis and quaternion algebras in his letter to
Aaronson and Pollington, which has been used to build frameworks for both
exact [Kliuchnikov2015a]111This work has been developed independently of
[sarnak2637letter]. and approximate synthesis [Kliuchnikov2015b]. The letter
also characterizes ‘golden gate sets’, of which the Clifford$+$T and V gates
are examples, that achieve optimal sequence lengths. For approximations of
diagonal unitaries, this is shown to be $3\log_{\ell}(1/\varepsilon)$. These
results are further expanded and generalizations of two-step approach to
diagonal approximations from [RossSelinger2014] to other gate sets also
discussed in [Parzanchevski]. Recent research [Campbell2017, Hastings2017]
shows that approximation with quantum channels, rather than unitaries,
achieves quadratic improvement in $\varepsilon$ and reduces the length by
factor of two.

The quality of an approximation $V$ for some desired unitary $U$ is captured
by the accuracy parameter $\varepsilon$. The distance between two unitaries is
computed by evaluating some norm of $U-V$. Typically, this is the operator (or
spectral) norm, where
$\mathopen{}\left\|A\right\|\mathclose{}=\max{\lambda_{k}}$, where
$\lambda_{k}$ are the singular values of $A$. In order to measure distance for
quantum channels, that is, completely-positive trace-preserving linear maps on
density matrices, we refer to the diamond norm. For quantum channels
$\mathcal{U}$ and $\mathcal{V}$ corresponding to unitaries $U$ and $V$, the
diamond norm of their difference is defined by

$\mathopen{}\left\|\mathcal{U}-\mathcal{V}\right\|\mathclose{}_{\diamond}=\max\limits_{\rho}\mathopen{}\left\\{\mathopen{}\left\|((\mathcal{U}-\mathcal{V})\otimes\mathcal{I}_{d})\mathopen{}\left(\rho\right)\mathclose{}\right\|\mathclose{}_{1}\right\\}\mathclose{},\text{
where
}\mathopen{}\left\|A\right\|\mathclose{}_{1}=\mathrm{Tr}\sqrt{A^{\dagger}A}$
(1)

and $\mathcal{I}_{d}$ is the identity map, and the maximum is taken over all
probability density matrices $\rho$. The diamond norm thus allows for accurate
measurement of errors in unitaries constituting a quantum algorithm,
independent of the algorithm itself.

We consider three universal gate sets associated with fault-tolerant quantum
computation: the V basis, the Clifford+T basis and the
Clifford+$\sqrt{\text{T}}$ basis. The Clifford+T gate set is commonly used for
fault tolerant quantum computation, and is known to be efficiently universal
[Selinger], with gate cost depending solely on the number of $T$ gates used.
The V basis was shown to be efficiently universal in [harrow2002efficient],
and provides a simple pedagogical example of approximation. The
Clifford$+\sqrt{\text{T}}$ gate set is an alternative to the Clifford$+$T gate
set for fault tolerant computing. The merits of these gate sets with regard to
fault tolerant computing are discussed in greater detail in Section 1.1.

The rest of this paper is organized as follows. Section 2 summarizes our main
results. In Section 3, we briefly discuss connections between gate synthesis
and cryptography. Section 4 defines the five approximation problems that are
the focus of this paper. We detail a complete method for solving these
problems in Section 5, with examples for the V, Clifford$+$T and Clifford
$+\sqrt{\text{T}}$ gate sets, in addition to a general solution. We provide
extensive numerical results for our method in Section LABEL:sec:numerical-
results for Clifford$+$T and Clifford$+\sqrt{\text{T}}$. Section
LABEL:sec:point-enum and Section LABEL:sec:normeqsolv recall algorithms for
solving two problems that arise in our solution method: integer point
enumeration and norm equation solving.

###  1.1 Fault tolerant gate sets

Unitary synthesis translates the description of a quantum algorithm into a
sequence of operations (”gates”) that can be implemented on the target quantum
computer. The set of operations permitted by a particular quantum computing
platform are limited by physical constraints and may not match the operations
prescribed in the algorithm. Moreover, even if the operations offered by the
quantum computer match the operations in the algorithm, the accuracy to which
the quantum computer can perform each operation is likely to be limited.
Loosely speaking, existing quantum computing systems offer single-qubit
unitary operations with accuracy up to $10^{-4}$ (see Fig. S.17 in
[Supremacy2019] for the accuracy of one and two qubit gates) whereas useful
quantum algorithms require accuracy of $10^{-10}$ or better (see Table I in
[Catalysis2021] for the typical number of gates in useful quantum algorithms).

Fault-tolerant quantum computation bridges the accuracy gap by encoding many
physical qubits into a smaller number of logical qubits. To guarantee
accuracy, logical qubits must be encoded at all times. Operations of the
quantum algorithm must be performed on the logical qubits _while_ they are
encoded. Each logical operation must both preserve the code structure and
carefully limit the spread of errors. Those requirements restrict the
available set of logical quantum operations.

The cheapest form of logical operations involves executing the same physical
operation to each of the physical qubits in the code. For example, some codes
admit the logical Hadamard operation by executing the physical Hadamard
operation to each physical qubit. Unfortunately, these so-called ”transversal”
gates can yield only a sparse discrete set within a single quantum code
[EastinKnill, BravyiKonig, WebsterBartlett].

Stabilizer codes, the most widely studied class of quantum error correcting
codes, typically admit transversal implementation of some or all of the
Clifford group—the group generated by {$H$, $S$, CNOT}. A broad and widely
studied subset of stabilizer codes called CSS support transversal
implementation of the CNOT operation, for example.222CSS is an initialism that
comes from the three authors that first defined the codes: Calderbank, Shor
and Steane. Circuits composed of Clifford group operations have the added
benefit of being efficiently simulable, an essential feature for the study of
fault tolerant quantum computing schemes.

At least one operation outside of the Clifford group is required for universal
quantum computation (see Theorem 6.7.3 in [Nebe2006]). In most fault-tolerant
quantum computing proposals, that non-Clifford operation is the $T$ gate. The
logical $T$ operation is typically implemented by ”distillation” which
combines many (noisy) physical $T$ gates with (less noisy) logical Clifford
operations [BravyiKitaevDistillation]. Distillation is regarded as the most
efficient known technique for non-Clifford gates, but remains roughly an order
of magnitude more expensive than transversal operations despite much study
[BeverlandDistillation]. Distillation can be used to construct other
operations, but known distillation protocols are limited to operations that
belong to the so-called ”Clifford hierarchy” introduced in [Gottesman1999]. Of
the known distillation techniques the most cost competitive operations are $T$
and the three qubit double-controlled-Z (CCZ) [Gidney2019].

To the best of our knowledge, there are no operations outside of the Clifford
hierarchy that admit implementation through distillation of the corresponding
resource states. However, by including measurement it is possible to construct
other kinds of circuits out of fault tolerant Clifford+$T$ gates. For example,
$V_{Z}=(I+2iZ)/\sqrt{5}$ can be implemented with the circuit shown in Figure
1. The idea then is to approximate a unitary $U$ with a sequence of
Clifford+$V_{Z}$ gates then substitute Figure 1 for each $V_{Z}$ in the
sequence. Unfortunately, that strategy yields higher number of $T$ gates than
synthesis with Clifford+$T$ alone. The strategy could be redeemed with cheaper
Clifford+$T$ implementations of $V_{Z}$ or similar non-Clifford gates. But
finding such circuits is difficult,and the best known circuits do not produce
better resource requirements overall. Though we consider the $V$-basis gate
set in this paper, it is largely for instructional purposes.

Incorporation of measurements into Clifford+$T$ circuits can be used to
emulate other gates _within_ the Clifford hierarchy, as well. For example, the
gate $\sqrt{T}$ can be implemented with Clifford+$T$ and measurements
[LowerBounds2020]. Approximations with the set Clifford+$\sqrt{T}$, through
emulation, use the the same number of $T$ gates as direct Clifford+$T$
sequences. Using Clifford+$\sqrt{T}$ gates, however, yields approximating
sequences that are half the length of corresponding Clifford+$T$ sequences,
offering an advantage when rotations must be executed as fast as possible.

Figure 1:  A Clifford+$T$ circuit implementation of $V_{Z}=(I+2iZ)/\sqrt{5}$
proposed in [Paetznick2013b]. Conditioned on $X$-basis measurement outcomes of
zero on the top two qubits, the circuit outputs $V_{Z}|\psi\rangle$. For any
other measurement outcome the circuit outputs $|\psi\rangle$. Repeating the
circuit until obtaining the 00 measurement outcome yields $V_{Z}|\psi\rangle$
using approximately $5.26$ $T$ gates, in expectation.

##  2 Summary of main results

Table 1:  Scaling of the approximation cost for random angles. Approximation accuracy $\varepsilon$ is measured using diamond distance. Linear fit of the cost is based on the numerical results reported in Figure 2 and Figure LABEL:fig:clifford-root-t-random. Mixed diagonal rows contain results for our new and improved version of a mixed diagonal approximation protocol first introduced in [Campbell2017, Hastings2017]. Results from [Campbell2017, Hastings2017] apply to any gate set for which diagonal approximation is available. Fallback rows correspond to our improved and generalized fallback synthesis method (Figure 7) first introduced in [BRS2015]. For power cost, the cost of $T$ is two and the cost of $T^{1/2},T^{3/2}$ is three. Our algorithms are optimal with respect to this cost. For gate count cost, the cost of $T$, $T^{1/2},T^{3/2}$ is one. For $T$-count cost, the cost of $T$ is one and the cost of $T^{1/2},T^{3/2}$ is four. Clifford gate costs are always zero. Different costs are discussed in LABEL:sec:numerical-results. Heuristic cost estimates are discussed in LABEL:sec:cost-scaling. Applications of magnitude approximation are illustrated in Table 2.  Gate set | Approximation |  Linear fit of the cost ($\varepsilon<10^{-4}$) | Heuristic | Novelty
---|---|---|---|---
(cost) | protocol | Mean | Max | cost estimate |
|  Diagonal [RossSelinger2014] | $3.02\log_{2}(1/\varepsilon)+1.77$ | $3.02\log_{2}(1/\varepsilon)+9.19$ | $3.0\log_{2}(1/\varepsilon)+O(1)$ | Known
|  Fallback [BocharovRoettelerSvore2014] | $1.03\log_{2}(1/\varepsilon)+5.75$ | $1.05\log_{2}(1/\varepsilon)+11.83$ | $1.0\log_{2}(1/\varepsilon)+O(1)$ | Improved
Clifford+$T$ | Magnitude | – | – | $1.0\log_{2}(1/\varepsilon)+O(1)$ | New
($T$-count) | Mixed diagonal | $1.52\log_{2}(1/\varepsilon)-0.01$ | $1.54\log_{2}(1/\varepsilon)+6.85$ | $1.5\log_{2}(1/\varepsilon)+O(1)$ | Improved
Figure 2 | Mixed fallback | $0.53\log_{2}(1/\varepsilon)+4.86$ | $0.57\log_{2}(1/\varepsilon)+8.83$ | $0.5\log_{2}(1/\varepsilon)+O(1)$ | New
| Mixed magnitude | – | – | $0.5\log_{2}(1/\varepsilon)+O(1)$ | New
| Diagonal | $3.02\log_{2}(1/\varepsilon)+2.80$ | $3.01\log_{2}(1/\varepsilon)+8.53$ | $3.0\log_{2}(1/\varepsilon)+O(1)$ | New
| Fallback | $1.04\log_{2}(1/\varepsilon)+6.61$ | $1.02\log_{2}(1/\varepsilon)+11.83$ | $1.0\log_{2}(1/\varepsilon)+O(1)$ | New
Clifford+$\sqrt{T}$ | Magnitude | – | – | $1.0\log_{2}(1/\varepsilon)+O(1)$ | New
(power) | Mixed diagonal | $1.53\log_{2}(1/\varepsilon)+1.06$ | $1.58\log_{2}(1/\varepsilon)+4.98$ | $1.5\log_{2}(1/\varepsilon)+O(1)$ | New*
LABEL:fig:clifford-root-t-random-power | Mixed fallback | $0.56\log_{2}(1/\varepsilon)+5.32$ | $0.62\log_{2}(1/\varepsilon)+7.66$ | $0.5\log_{2}(1/\varepsilon)+O(1)$ | New
| Mixed magnitude | – | – | $0.5\log_{2}(1/\varepsilon)+O(1)$ | New
| Diagonal | $1.21\log_{2}(1/\varepsilon)+1.18$ | $1.26\log_{2}(1/\varepsilon)+3.86$ | $1.2\log_{2}(1/\varepsilon)+O(1)$ | New
| Fallback | $0.42\log_{2}(1/\varepsilon)+2.68$ | $0.44\log_{2}(1/\varepsilon)+5.13$ | $0.4\log_{2}(1/\varepsilon)+O(1)$ | New
Clifford+$\sqrt{T}$ | Magnitude | – | – | $0.4\log_{2}(1/\varepsilon)+O(1)$ | New
(gate count) | Mixed diagonal | $0.61\log_{2}(1/\varepsilon)+0.43$ | $0.64\log_{2}(1/\varepsilon)+2.52$ | $0.6\log_{2}(1/\varepsilon)+O(1)$ | New*
LABEL:fig:clifford-root-t-random-rcount | Mixed fallback | $0.23\log_{2}(1/\varepsilon)+2.13$ | $0.25\log_{2}(1/\varepsilon)+3.85$ | $0.2\log_{2}(1/\varepsilon)+O(1)$ | New
| Mixed magnitude | – | – | $0.2\log_{2}(1/\varepsilon)+O(1)$ | New
| Diagonal | $3.03\log_{2}(1/\varepsilon)+2.48$ | $3.25\log_{2}(1/\varepsilon)+14.40$ | $3.0\log_{2}(1/\varepsilon)+O(1)$ | New
| Fallback | $1.04\log_{2}(1/\varepsilon)+6.43$ | $1.18\log_{2}(1/\varepsilon)+14.01$ | $1.0\log_{2}(1/\varepsilon)+O(1)$ | New
Clifford+$\sqrt{T}$ | Magnitude | – | – | $1.0\log_{2}(1/\varepsilon)+O(1)$ | New
($T$ count) | Mixed diagonal | $1.53\log_{2}(1/\varepsilon)+1.02$ | $1.68\log_{2}(1/\varepsilon)+7.30$ | $1.5\log_{2}(1/\varepsilon)+O(1)$ | New*
LABEL:fig:clifford-root-t-random-tcount | Mixed fallback | $0.56\log_{2}(1/\varepsilon)+5.30$ | $0.67\log_{2}(1/\varepsilon)+9.85$ | $0.5\log_{2}(1/\varepsilon)+O(1)$ | New
| Mixed magnitude | – | – | $0.5\log_{2}(1/\varepsilon)+O(1)$ | New
Figure 2:  Cost of approximating a set of random diagonal rotation gates with Clifford+$T$ gates using four approximation protocols. Diagonal rotation angles are random angles drawn from the uniform distribution on $[0,2\pi]$. We fix a set of approximation accuracy values. For each value in the set we compute mean cost over all target angles. Vertical bars show the cost standard deviation for the given accuracy value. Shaded regions indicate range of costs from min to max over all angles for the given accuracy value. For the diagonal approximation protocol the cost for a given angle and given accuracy is equal to number of $T$ gates in the approximating sequence. For the other protocols the cost is the expectation of $T$-count. For example, if the first step of fall-back protocol requires 10 $T$ gates and fails with probability 0.01 and the step to correct failure requires 30 $T$ gates, the expected cost is 10.3. In all reported fallback protocols the probability of fallback is at most $0.01$.  Table 2:  Examples of problems that benefit from magnitude approximation. The case of a general qubit unitary approximation is described in Section 4.1 and Section 4.6. Solutions to qubit approximation and general $\mathrm{SU}(4)$ approximation are outlined in LABEL:app:magnitude-approx-applications. More generally, the magnitude approximation problem can be used when compiling $\mathrm{CNOT}$ and rotation circuits for isometries produced by UniversalQCompiler [Iten2016, Iten2021, Malvetti2021] for fault-tolerant quantum computers.  Problems that benefit from | Qubit state |  General $\mathrm{SU}(2)$ |  General $\mathrm{SU}(4)$
---|---|---|---
magnitude approximation | preparation | approximation | approximation
| Number of real parameters | 2 | 3 | 15
Problem | Number of magnitude | 1 | 1 | 6
properties | approximation instances |  |  |
| Number of diagonal | 1 | 2 | 9
| approximation instances |  |  |
Gate set | Approximation method |  Heuristic T-count scaling with diamond norm accuracy $\varepsilon$
| Diagonal (known) | $6\log_{2}(1/\varepsilon)+O(1)$ | $9\log_{2}(1/\varepsilon)+O(1)$ | $45\log_{2}(1/\varepsilon)+O(1)$
Clifford+T | Diagonal + Magnitude (new) | $4\log_{2}(1/\varepsilon)+O(1)$ | $7\log_{2}(1/\varepsilon)+O(1)$ | $33\log_{2}(1/\varepsilon)+O(1)$
| Mixed Diagonal (improved) | $3\log_{2}(1/\varepsilon)+O(1)$ | $4.5\log_{2}(1/\varepsilon)+O(1)$ | $22.5\log_{2}(1/\varepsilon)+O(1)$
| Mixed Diag. + Mag. (new) | $2\log_{2}(1/\varepsilon)+O(1)$ | $3.5\log_{2}(1/\varepsilon)+O(1)$ | $11.5\log_{2}(1/\varepsilon)+O(1)$

In Section 4 we define six approximation problems: diagonal unitary
approximation, fallback approximation, magnitude approximation and their
versions with probabilistic mixing. The first two of these problems have been
the subject of research for some time, with many results pertaining to
specific gate sets [RossSelinger2014, KliuchnikovMaslovMosca2013,
Bocharov2013, BocharovRoettelerSvore2014, Kliuchnikov2015a, Kliuchnikov2015b].
The magnitude approximation problem is new. One of its applications is solving
the general unitary approximation problem, which exploits the connection
between unitary approximation and LPS graphs (See Section 3). Explicitly, we
adapt the path-finding algorithm of Carvalho Pinto and Petit [pinto2018better]
to the quantum setting, requiring only two diagonal approximations and one
more efficient magnitude approximation. The sequence costs obtained using our
method improve on the standard Euler decomposition, which requires three
diagonal approximations, by roughly one-third. Stier [stier] has concurrently
and independently produced a similar result. We discuss additional
applications of the magnitude approximation problem in LABEL:app:magnitude-
approx-applications.

The latter three problems are defined by applying the concept of channel
mixing to diagonal, fallback and magnitude approximation, expanding on the
ideas of [Campbell2017, Hastings2017]. Channel mixing employs a probabilistic
combination of sequences of unitaries to approximate the target. The key idea
is to use probabilistic combination of under-rotated and over-rotated
approximations of a given target. We combine channel mixing with fallback and
magnitude approximation to achieve a roughly two-fold improvement in cost
compared to non-mixed problem variants. To account for the fact that we are
approximating with channels rather than unitaries, we use the diamond norm to
measure the accuracy of approximation. We introduce the use of diagonal
Clifford twirling, which ensures that the difference between the ideal and
approximating channel is a Pauli channel. Because of this, we obtain a closed-
form expression for the diamond distance which improves on analysis in
[Campbell2017, Hastings2017] and results in lower approximation costs. The
method in [Campbell2017] uses diagonal approximation algorithms as black-boxes
and finds under-rotations and over-rotations by modifying target rotation
angle. In contrast, we modify synthesis algorithms to directly find under and
over-rotated approximations and further reduce approximations costs.

We provide a uniform approach to the six approximation problems and various
gate sets. For each problem, we show that a constraint on the diamond norm can
be reduced to a constraint on a single complex number. In contrast to
[BRS2015], our approach to fallback approximation ensures desired success
probability and approximation accuracy. The set of feasible solutions is
represented geometrically as a region in $\mathbb{R}^{2}$, illustrated in
Section 4. Figure 13 compares the areas of the regions associated to the
approximation problems with respect to varying approximation accuracy
$\varepsilon$ and success probability $q$. The scaling of the region area with
epsilon determines the scaling of the approximation sequence cost with
accuracy $\varepsilon$, as illustrated in Table 1. To establish dependence
between region area scaling and cost scaling we use several heuristic
assumptions as discussed in LABEL:sec:cost-scaling. We also provide
experimental justification of relation between the cost and region scaling.

The results of our numerical experiments for Clifford+$T$ and
Clifford+$\sqrt{T}$ gate sets are summarized in Table 1. More detailed
numerical results for Clifford+$T$ are provided in Figure 2, in particular
they show that linear fits for cost scaling with accuracy are well justified.
Even more detailed results for Clifford+$T$ and for Clifford+$\sqrt{T}$ are in
Section LABEL:sec:numerical-results. We show numerical results for
approximating uniformly random diagonal rotations and angles and rotations by
Fourier angles $\pi/2^{k}$. The study of uniformly random diagonal rotations
is motivated by the use of diagonal rotations in quantum algorithm for
chemistry, material science applications [TheoryOfTrotterError] and the
rotations used in Quantum Signal Processing [QuantumSignalProcessing];
rotations by Fourier angles appear in the Quantum Fourier Transform [Nam2020]
and preparation of Phase Gradient states [Gidney2018].

We find that Clifford+$\sqrt{T}$ is a promising gate-set for approximation
when executing rotations as fast impossible. In this case the execution speed
is limited by the gate count, in particular when executing rotations using a
circuit from Figure 33 in [GameOfSurfaceCodes]. We achieve average gate-count
scaling $0.23\log_{2}(1/\varepsilon)+2.13$ when using mixed fallback protocol
with Clifford+$\sqrt{T}$ and T-count similar to Clifford+$T$ approximations.
We assume that each $\sqrt{T}$ gate requires four $T$ gates, which is
justified in LABEL:sec:cost-scaling. These are the first numerical studies of
approximation cost scaling for Clifford+$\sqrt{T}$ gates that include additive
constants, which are practically important because the
$\log_{2}(1/\varepsilon)$ prefactor is small. These are also the first
numerical results for mixed fallback and mixed diagonal approximations for
Clifford+${T}$. We also provide more detail on approximate synthesis for
general gate sets than the high-level approach outlined in [Parzanchevski].

In Section 5 we describe a complete method for solving the six approximation
problems, restricting the scope to considering gate sets that can be
represented by quaternion algebras. The general solution method is described
in Section LABEL:sec:approximation-problems:general, and includes a process
for constructing quaternion gate sets, as defined in [A11]. To summarize, a
gate set is defined by a complex field $L$, its maximal totally real subfield
$K$ and a fixed set of elements in $K$. A solution to an approximation problem
involves finding a matrix $M=\left(\begin{smallmatrix}m_{1}&-m_{2}^{\ast}\\\
m_{2}&m_{1}^{\ast}\end{smallmatrix}\right)$ with entries in the integer ring
of $L$. Our approach to finding $M$ can be summarized in two steps: point
enumeration in a region defined by the approximation problem to find $m_{1}$,
followed by solving a relative norm equation to recover $m_{2}$. To guide the
reader, we work through three pedagogical examples: the V basis (Section 5.1),
the Clifford$+$T basis (Section LABEL:sec:approximation-solutions-clifford-t),
and the Clifford$+\sqrt{\textnormal{T}}$ basis (Section
LABEL:sec:approximation-solutions-clifford-root-t). A worked example for the V
basis is given here in Section 2.1.

###  2.1 Example: V basis diagonal approximation of $e^{i\frac{\pi}{4}Z}$

We use the notation $I,X,Y,Z$ for Pauli matrices:

$I=\mathopen{}\left(\begin{array}[]{cc}1&0\\\
0&1\end{array}\right)\mathclose{},\,X=\mathopen{}\left(\begin{array}[]{cc}0&1\\\
1&0\end{array}\right)\mathclose{},\,Y=\mathopen{}\left(\begin{array}[]{cc}0&-i\\\
i&0\end{array}\right)\mathclose{},\,Z=\mathopen{}\left(\begin{array}[]{cc}1&0\\\
0&-1\end{array}\right)\mathclose{}.$

Recall that the V basis consists of the following six matrices:

$\displaystyle V_{\pm Z}$ $\displaystyle=\frac{1}{\sqrt{\ell}}\left(I\pm
2iZ\right),$ $\displaystyle V_{\pm Y}$
$\displaystyle=\frac{1}{\sqrt{\ell}}\left(I\pm 2iY\right),$ $\displaystyle
V_{\pm X}$ $\displaystyle=\frac{1}{\sqrt{\ell}}\left(I\pm 2iX\right),$

where $\ell=5$. Let $\theta=\frac{\pi}{4}$ and suppose we want to approximate
$U=e^{i\theta Z}=\left(\begin{smallmatrix}e^{i\pi/4}&0\\\
0&e^{-i\pi/4}\end{smallmatrix}\right)$ using the V basis within accuracy
$\varepsilon=0.1$ with respect to the diamond norm. In other words, we look
for $V$, a product of unitaries from the V basis, which satisfies
$\mathopen{}\left\|\mathcal{Z}_{\theta}-\mathcal{V}\right\|\mathclose{}_{\diamond}\leq\varepsilon,$
where $\mathcal{Z}_{\theta}$ and $\mathcal{V}$ are the channels333The channel
induced by a unitary $U$ is an action of $U$ on a density matrix $\rho$:
$\mathcal{U}(\rho)=U\rho U^{\dagger}$. Channels and density matrices are
defined fully in Section 4. induced by $e^{i\theta Z}$ and $V$, respectively.

Writing $V$ as $\left(\begin{smallmatrix}u&-v^{\ast}\\\
v&u^{\ast}\end{smallmatrix}\right)$, with $u,v\in\mathbb{C}$, we obtain the
following:

$\mathopen{}\left|\mathrm{Re}(ue^{-i\pi/4})\right|\mathclose{}\geq
1-\varepsilon^{2}/8\implies\mathopen{}\left\|\mathcal{Z}_{\pi/4}-\mathcal{V}\right\|\mathclose{}_{\diamond}\leq\varepsilon.$
(2)

For the full derivation of this constraint see Problem 4.4, Section 4. The
constraint on $u$ is represented geometrically by the region in Figure 3.

Figure 3: Geometric interpretation of constraint on complex number $u$ in
Equation (2). The region with the red boundary contains candidate points
$(a,b)\in\mathbb{Z}^{2}$, such that $u=a+ib$ and
$\mathopen{}\left|\mathrm{Re}(ue^{-i\pi/4})\right|\mathclose{}\geq
1-(0.1)^{2}/8$.

Since $V$ is a product of V basis matrices, there exists $N\in\mathbb{N}$ such
that
$V=\frac{1}{\sqrt{5^{N}}}\left(\begin{smallmatrix}u^{\prime}&-(v^{\prime})^{\ast}\\\
v^{\prime}&(u^{\prime})^{\ast}\end{smallmatrix}\right)$, with
$u^{\prime},v^{\prime}\in\mathbb{Z}[i]$. It follows that
$u=u^{\prime}/\sqrt{5^{N}}$ and $v=v^{\prime}/\sqrt{5^{N}}$. Hence, we scale
the region in Figure 3 by $\sqrt{5^{N}}$ and look for integer points
$(a,b)\in\mathbb{Z}^{2}$, each corresponding to a candidate $u^{\prime}=a+ib.$
We initialize $N:=1$, and iterate over $N$ until a solution is found.

We find that there are no integer solutions for $N=1,2,3,4$. At $N=5$, there
are four candidates for $u^{\prime}$, namely
$\\{38+41i,39+40i,40+39i,41+38i\\}$, shown in Figure 4. Since $V$ is unitary,
we require $\det(V)=uu^{\ast}+vv^{\ast}=1$ or, equivalently,
$u^{\prime}(u^{\prime})^{\ast}+v^{\prime}(v^{\prime})^{\ast}=5^{5}=3125.$ So
we must have $0\leq
v^{\prime}(v^{\prime})^{\ast}=3125-u^{\prime}(u^{\prime})^{\ast}.$ Then,

$\displaystyle u^{\prime}=38+41i$ $\displaystyle\implies$ $\displaystyle
u^{\prime}(u^{\prime})^{\ast}=38^{2}+41^{2}=3125$ (3) $\displaystyle
u^{\prime}=39+40i$ $\displaystyle\implies$ $\displaystyle
u^{\prime}(u^{\prime})^{\ast}=39^{2}+40^{2}=3121$ (4) $\displaystyle
u^{\prime}=40+39i$ $\displaystyle\implies$ $\displaystyle
u^{\prime}(u^{\prime})^{\ast}=3121$ (5) $\displaystyle u^{\prime}=41+38i$
$\displaystyle\implies$ $\displaystyle u^{\prime}(u^{\prime})^{\ast}=3125.$
(6)

Figure 4: Geometric interpretation of the constraint on complex number
$u^{\prime}$, such that
$V=\frac{1}{\sqrt{5^{5}}}\left(\begin{smallmatrix}u^{\prime}&-(v^{\prime})^{\ast}\\\
v^{\prime}&(u^{\prime})^{\ast}\end{smallmatrix}\right)$ approximates
$e^{i\frac{\pi}{4}Z}$ to accuracy $\varepsilon=0.1$. The region with the red
boundary contains four candidate complex numbers satisfying
$\mathopen{}\left|\mathrm{Re}(u^{\prime}e^{-i\pi/4})\right|\mathclose{}\geq\sqrt{5^{5}}(1-(0.1)^{2}/8)$.

Let $v^{\prime}=c+id,$ so

$v^{\prime}(v^{\prime})^{\ast}=c^{2}+d^{2}=5^{5}-(a^{2}+b^{2}).$ (7)

For Equations (3) and (6), we have $v^{\prime}(v^{\prime})^{\ast}=0$ so $v=0$
is the only solution. Equations (4) and (5) yield
$v^{\prime}(v^{\prime})^{\ast}=4,$ so $c^{2}+d^{2}=4=2^{2}$ then either $c=\pm
2,d=0$ or $c=0,d=\pm 2$. The two corresponding values for $v^{\prime}$ are
$\pm 2$ and $\pm 2i$. In general, Equation (7) admits a solution for
$v\in\mathbb{Z}[i]$ if and only if all terms $p^{k}$ in the prime
factorization of $5^{5}-(a^{2}+b^{2})$, with $p\equiv 3\bmod{4}$, have even
exponent $k$. Each candidate pair $(u^{\prime},v^{\prime})$ defines an
approximation unitary
$V=\frac{1}{\sqrt{3125}}\left(\begin{smallmatrix}u^{\prime}&-(v^{\prime})^{\ast}\\\
v^{\prime}&(u^{\prime})^{\ast}\end{smallmatrix}\right)$, which is factorized
over the V basis. These factorizations are given in Table 3.

$u^{\prime}$ | $v^{\prime}$ | V basis factorization
---|---|---
$41+38i$ | 0 | $(V_{-Z})^{5}$
$38+41i$ | 0 | $iZ\cdot(V_{+Z})^{5}$
$39+40i$ | $2i$ | $e^{i\pi}\cdot V_{-X}V_{-Y}V_{+X}V_{+Y}V_{-X}$
| $2$ | $e^{i\pi}\cdot V_{+Y}V_{-X}V_{-Y}V_{+X}V_{+Y}$
| $-2i$ | $e^{i\pi}\cdot V_{+X}V_{+Y}V_{-X}V_{-Y}V_{+X}$
| $-2$ | $e^{i\pi}\cdot V_{-Y}V_{+X}V_{+Y}V_{-X}V_{-Y}$
$40+39i$ | $2i$ | $-iZ\cdot V_{-Y}V_{-X}V_{+Y}V_{+X}V_{-Y}$
| $2$ | $-iZ\cdot V_{+X}V_{-Y}V_{-X}V_{+Y}V_{+X}$
| $-2i$ | $-iZ\cdot V_{+Y}V_{+X}V_{-Y}V_{-X}V_{+Y}$
| $-2$ | $-iZ\cdot V_{-X}V_{+Y}V_{+X}V_{-Y}V_{-X}$
Table 3: V basis factorizations of unitaries
$V:=\frac{1}{\sqrt{5^{5}}}\left(\begin{smallmatrix}u^{\prime}&-(v^{\prime})^{\ast}\\\
v^{\prime}&(u^{\prime})^{\ast}\end{smallmatrix}\right)$, satisfying
$\mathopen{}\left\|e^{i\frac{\pi}{4}Z}-V\right\|\mathclose{}_{\diamond}\leq\varepsilon=0.1$.

##  3 Connections to cryptography and hash functions

In this section we will recall some definitions and results about
cryptographic hash functions. In particular, we explain the connection between
the Charles, Goren and Lauter hash construction [charles2009cryptographic],
built from LPS graphs, to unitary synthesis problems.

A _hash function_ $h:\\{0,1\\}^{\ast}\rightarrow\\{0,1\\}^{m}$ is a function
which takes bitstrings of arbitrary length as inputs, and outputs bitstrings
of fixed length. A hash function is required to be preimage resistant; that
is, given a value $y\in\\{0,1\\}^{m}$ in the image of $h$, it must be
computationally infeasible to find a bitstring $x$ which hashes to that value.
This is formalized in Problem 3.1.

######  Problem 3.1 (Preimage Finding Problem).

Given a hash function $h$ and a value $y\in\mathrm{Im}(h)$, find $x$ such that
$h(x)=y$.

There are several constructions of hash functions built on Cayley graphs.
Given a group $\mathcal{G}$ with generating set $S=\\{s_{0},\dots,s_{k}\\}$,
the corresponding Cayley graph has vertices associated with elements $g$ in
$\mathcal{G}$ and directed edges $(g,h)$ if and only if $gh^{-1}\in S$.
Writing a message $m=m_{1}m_{2}\dots m_{k}$ with $m_{i}\in\\{0,\dots,k\\}$,
the hash function is defined by $H(m)=s_{m_{1}}s_{m_{2}}\dots s_{m_{n}}$. For
such constructions, called Cayley hash functions, Problem 3.1 can be
reformulated as the group theoretic problem below.

######  Problem 3.2 (Constructive Membership Problem).

Let $\mathcal{G}$ be a group with generating set $S=\\{s_{1},\dots,s_{k}\\}$
and let $N\in\mathbb{Z}$ be small. Given an element $g\in\mathcal{G}$, find a
sequence $m_{1},\dots,m_{N}$ such that $g=\prod_{i}s_{m_{i}}.$

In [charles2009cryptographic], Charles, Goren and Lauter (CGL) proposed a
Cayley hash function based on LPS graphs. LPS graphs were introduced by
Lubotsky, Phillips and Sarnak in [lubotzky1988ramanujan]. Let $p,\ell$ be
distinct primes congruent to $1\bmod 4$, where
$\left(\frac{\ell}{p}\right)=1$. Let $\mathbb{F}_{p}$ denote the finite field
with $p$ elements and let $\iota$ such that $\iota^{2}=-1\mod p$. An LPS graph
$X_{p,\ell}$ is the Cayley graph with $\mathcal{G}=PSL(2,\mathbb{F}_{p})$, the
projective special linear group of $2\times 2$ matrices over $\mathbb{F}_{p}$,
and generating set $S=\left\\{\left(\begin{smallmatrix}a+\iota b&c+\iota d\\\
-c+\iota d&a-\iota
b\end{smallmatrix}\right):a^{2}+b^{2}+c^{2}+d^{2}=\ell\right\\}$, where $a>0$
and $b,c,d$ even. We can write $g\in\mathcal{G}$ as
$\left(\begin{smallmatrix}a+\iota b&c+\iota d\\\ -c+\iota d&a-\iota
b\end{smallmatrix}\right)$ with $a,b,c,d\in\mathbb{F}_{p}$ and define the norm
function $n(g)=a^{2}+b^{2}+c^{2}+d^{2}.$ The preimage problem for the CGL hash
function amounts to path finding on an LPS graph. Since these are Cayley
graphs, the preimage problem is equivalent to Problem 3.2.

Recall that the unitary synthesis problem is the search for a circuit, or
sequence, of unitaries from a specified gate set that is equivalent to some
target unitary. Clearly, this problem is highly related to Problem 3.2.
Unitaries are represented by matrices over $\mathbb{C}$ and vertices in
$X_{p,\ell}$ correspond to matrices over $\mathbb{F}_{p}$, and both problems
look for ‘short’ sequences in a subset of matrices. Remarkably, algorithms
developed independently to solve the constructive membership problem for LPS
graphs [petit2008full, sardari2017complexity] and the quantum unitary
synthesis problem [Ross2015, BlassEtAl2015] have many similarities. Petit,
Lauter and Quisquater [petit2008full] proposed an algorithm for finding short
paths in LPS graphs in which a matrix from the group $\mathcal{G}$ is
decomposed into the product of four diagonal matrices with square determinant
and graph generators, up to multiplication by a unit. Each diagonal matrix is
factorized into elements from $S$ using an extension of the Tillich-Zémor
algorithm [tillich2008collisions] for collision finding in an LPS graph. This
diagonal decomposition method is reminiscent of the Euler decomposition method
for unitary synthesis, described in greater detail in Section 4, in which the
target unitary is decomposed into the product of $Z$-axis rotations. Notably,
$Z$-axis rotations can be expressed as diagonal matrices. Carvalho Pinto and
Petit [pinto2018better] later improved upon the algorithm in [petit2008full],
by decomposing the target matrix into the product of two diagonal matrices and
a third non-diagonal, easily-factorizable matrix, resulting in path lengths of
$7\log_{\ell}(p)$. In Section 4 we translate the algorithm to the continuous
setting of general unitary approximation, achieving a similar improvement in
sequence length. We obtain an additional constant factor improvement by
implementing approximation via quantum channel mixing.

We deal with the problem of approximating unitaries to some chosen accuracy
$\varepsilon$. The algorithms described in [petit2008full] and
[pinto2018better] both involve ‘lifting’ a matrix $M\in PSL(2,\mathbb{F}_{p})$
to a matrix $M^{\prime}\in GL(\mathbb{Z}[i])$, such that the corresponding
entries of each matrix are congruent modulo $p$. In other words, for some
well-defined p-adic norm the distance between $M$ and $M^{\prime}$ is
$O(p^{-1})$. The matrix $M^{\prime}$ is then factorized over
$GL(\mathbb{Z}[i])$, with some conditions regarding the determinant size, with
each factor mapped back to $PSL(2,\mathbb{F}_{p})$ via a group homomorphism.
The lifting step is analogous to approximation in the quantum setting, using
$p^{-1}$ as a measure of accuracy. Clearly, $p^{-1}$ is analogous to
$\varepsilon.$ Of course, in the LPS hash setting $p$ is fixed, whereas in the
quantum setting we have some control over the value $\varepsilon$. The length
of a sequence indicates the cost of approximating the target unitary in the
context of gate synthesis. For the CGL hash function, the sequence length will
equal the length of the corresponding path in the LPS graph, and is similarly
used as measure of performance for path-finding algorithms. The length of a
sequence is determined by taking the norm of the target matrix. For matrices
over $\mathbb{C}$, we can use some some complex matrix norm, while matrices in
$PSL(2,\mathbb{F}_{p})$ use some $p$-adic norm. For instance, the six unitary
approximation problems defined in Section 4 use the diamond norm to measure
accuracy. Note, however, that despite the similarities just described, not all
of these approximation problems have natural analogues in cryptography. In
particular, those problems that utilize fall-back and channel mixing
techniques do not translate to the classical setting. Moreover, the other
properties required of cryptographic hash functions - collision resistance and
second preimage resistance - do not yet have quantum approximation analogues,
either.

The gate sets considered in this paper are quaternion gate sets, so-called due
to their relationship to quaternion algebras (see Section
LABEL:sec:approximation-problems:general). Sarnak first observed the
connection between LPS graphs, quaternion orders and quantum gate sets in his
letter to Aaronson and Pollington on the Solvay-Kitaev Theorem and golden
gates [sarnak2637letter]. For instance, synthesis over the $V$ basis is
analogous to path finding in an LPS graph $X_{p,\ell}$, where $p\equiv 1\bmod
4$ and $\ell=5$. We return to the V basis in Section 5, as an example of a
quaternion gate set, along with the Clifford $+T$ basis and the
Clifford$+\sqrt{\text{T}}$ basis.

##  4 Approximation problems

In this section we introduce six problems that address the approximation of
qubit unitaries. Recall that in this paper we follow a two-step approach to
solving approximation problems. First, in this section, we relate each problem
to one-dimensional or two-dimensional regions. Second, in Section 5, we find
sequences of gates $g_{1},\ldots,g_{n}$ over gate-set $G$ such that for a
unitary computed by the sequence $g_{1}\ldots
g_{n}=\mathopen{}\left(\begin{smallmatrix}u&-v^{\ast}\\\
v&u^{\ast}\end{smallmatrix}\right)\mathclose{}$ the top-left entry $u$ belongs
to a two-dimensional region of the complex plain, or the absolute values $|u|$
belongs to an interval, that is one-dimensional region. In this section we
also show that these sequences $g_{1},\ldots,g_{n}$ then can be used to
construct solutions to the approximation problems.

We begin by establishing some notation and key definitions [Kaye2007,
nielsen00, Watrous2018]. An arbitrary two-by-two unitary matrix with
determinant one (i.e., a special unitary matrix) can be written as:

$U=\mathopen{}\left(\begin{array}[]{cc}u&-v^{\ast}\\\
v&u^{\ast}\end{array}\right)\mathclose{},\text{ for }u,v\in\mathbb{C}\text{
such that
}\mathopen{}\left|u\right|\mathclose{}^{2}+\mathopen{}\left|v\right|\mathclose{}^{2}=1$

Using the polar form of complex numbers we can write
$u=r_{1}\exp\mathopen{}\left(i\psi_{1}\right)\mathclose{}$ and
$v=ir_{2}\exp\mathopen{}\left(i\psi_{2}\right)\mathclose{}$. Let us introduce
$r_{1}=\cos(\theta)$ and $r_{2}=\sin(\theta)$ for some $\theta\in[0,\pi/2]$
because $r_{1}^{2}+r_{2}^{2}=1$. The unitary $U$ can then be expressed as

$U=\cos(\theta)e^{i\psi_{1}Z}+\sin(\theta)iXe^{i\psi_{2}Z}\text{ for
}\psi_{1},\psi_{2},\theta\in\mathbb{R}$ (8)

We will interchangeably use both parameterizations of a special unitary $U$.
We denote the special unitary group, that is the group of all two by two
unitary matrices with determinant equal to 1, by $\mathrm{SU}(2).$ We will
also frequently use the fact that Pauli matrices are Hermitian and equal to
their inverses.

A probabilistic ensemble of pure quantum states is represented as a trace-one
positive semidefinite operator called a _density matrix_. The most general
type of transformation on quantum state is a _channel_ , a linear completely
positive trace-preserving map on the space of density matrices. The action of
a unitary $U$ on density matrix $\rho$ is given by

$\mathcal{U}(\rho)=U\rho U^{\dagger}$ (9)

and we refer to $\mathcal{U}$ as the “channel induced by $U$”. For diagonal
unitaries of the form $e^{i\phi Z},e^{i\theta X}$ we denote the induced
channel by

$\mathcal{Z}_{\phi}(\rho)=e^{i\phi Z}\rho e^{-i\phi
Z},\,\mathcal{X}_{\theta}(\rho)=e^{i\theta X}\rho e^{-i\theta X}$ (10)

To measure the distance between channels we use the diamond norm

$\mathopen{}\left\|\Phi\right\|\mathclose{}_{\diamond}:=\max_{\rho}\mathopen{}\left\|\left(\Phi\otimes\mathcal{I}\right)(\rho)\right\|\mathclose{}_{1}$
(11)

where $\mathcal{I}$ is the channel induced by the identity matrix. For
additional discussion and facts about the diamond norm see Appendix
LABEL:app:diamond-norm-properties.

Our main goal in this paper is to solve single-qubit unitary approximation
problems. The most general form is:

######  Problem 4.1 (General qubit unitary approximation).

Given:

  * •

target unitary $U\in\mathrm{SU}(2)$,

  * •

gate set $G$, a finite set of unitary matrices with determinant one

  * •

accuracy $\varepsilon$,444The parameter $\varepsilon$ is commonly referred to
as the precision in the literature. Since we use $\varepsilon$ as a measure of
approximation error from a target, we believe the term accuracy is more
appropriate. a positive real number

Find a channel $\mathcal{V}$ implemented using elements of $G$ and
computational basis measurements such that

$\mathopen{}\left\|\mathcal{U}-\mathcal{V}\right\|\mathclose{}_{\diamond}\leq\varepsilon,$

where $\mathcal{U}$ is the channel induced by $U$.

In a simpler case, when channel $\mathcal{V}$ corresponds to unitary $V$ equal
to the product $g_{1}\ldots g_{n}$ of two-by-two matrices from gate set $G$,
the diamond norm is tightly bounded by twice the minimum spectral norm
distance between $\pm U$ and $V$ (see LABEL:cor:diamond-distance-between-
general). To avoid frequent explicit references to channels $\mathcal{U}$ and
$\mathcal{V}$ induced by unitaries $U$ and $V$ we introduce distance between
unitaries $U$ and $V$ as:

$\mathcal{D}_{\diamond}\mathopen{}\left(U,V\right)\mathclose{}=\mathopen{}\left\|\mathcal{U}-\mathcal{V}\right\|\mathclose{}_{\diamond}.$
(12)

Of particular interest is the case where $U$ is a diagonal unitary, namely
$U=e^{i\phi Z}$ for real $\phi$. This case is very common in many quantum
algorithms. In addition, the state-of-the-art way of solving the general
unitary approximation problem is to use _Euler angle decomposition_ to reduce
the problem to three diagonal unitary approximation problems. Recall that
$e^{i\theta
X}=\cos\mathopen{}\left(\theta\right)\mathclose{}I+i\sin\mathopen{}\left(\theta\right)\mathclose{}X$.
Euler decomposition is performed by solving for $\phi_{1},\phi_{2}$ in the
equation below:

$U=\cos(\theta)e^{i\psi_{1}Z}+\sin(\theta)iXe^{i\psi_{2}Z}=e^{i\phi_{1}Z}e^{i\theta
X}e^{i\phi_{2}Z}=\cos\mathopen{}\left(\delta\right)\mathclose{}e^{i\mathopen{}\left(\phi_{1}+\phi_{2}\right)\mathclose{}Z}+\sin\mathopen{}\left(\theta\right)\mathclose{}iXe^{i\mathopen{}\left(\phi_{2}-\phi_{1}\right)\mathclose{}Z}$
(13)

To obtain the last equality we used the fact that $e^{i\phi Z}X=Xe^{-i\phi
Z}$, since $XZX=-Z$ and for any invertible matrix $A$ and any matrix $B$, it
is the case that $Ae^{B}A^{-1}=e^{ABA^{-1}}$.

In this section, we demonstrate how the general unitary approximation problem
reduces to two diagonal approximations and a search for elements in a one-
dimensional (1D) region, that we call magnitude approximation problem,
improving on the traditional Euler angle decomposition approach. We then
introduce a series of four problems for approximating diagonal unitaries,
corresponding to the combinations of using probabilistic mixing (or not) and
using fallback protocols [Bocharov2014] (or not). For each problem we give a
reduction to the search for elements in two-dimensional (2D) regions. We
conclude the section with applying mixing to the magnitude approximation.
Table 4 summarizes this section.

Table 4:  Summary of the qubit unitary approximation protocols. Each protocol corresponds to a ”key problem” for which the top-left entry of matrix $\mathopen{}\left(\begin{smallmatrix}u&-v^{\ast}\\\ v&u^{\ast}\end{smallmatrix}\right)\mathclose{}$ belongs to a two-dimensional region of complex plain, or the absolute value $|u|$ belongs to a one-dimensional interval. Some approximation protocols use others as sub-protocols. Combining the solution to the key problem(s) with the sub-protocols is described by the statements in ”Full protocol analysis” column. Comparisons of the geometric regions are given in Section 4.7, Table 5 and Figure 12. For cost scaling see Table 1 and Table 2.  Approximation |  | Target | Key | Key | Full | Sub-
---|---|---|---|---|---|---
protocol | Section | unitary | problem | problem | protocol | protocols
|  |  | definition | region | analysis |
General | Section 4.1 | $\mathrm{SU}(2)$ | 4.2 | 4.2 | 4.3 | Diagonal or
unitary |  |  | (magnitude) | Figure 5 |  | Fallback
Mixed general | Section 4.6 | $\mathrm{SU}(2)$ | 4.18 | 4.20 | 4.21 | Mixed diagonal
unitary |  |  | (magnitude) | Figure 11 |  | or mixed fallback
Diagonal | Section 4.2 | $e^{i\varphi Z}$ | 4.4 | 4.6 | 4.6 | -
unitary |  |  | (diagonal) | Figure 6 |  |
Mixed | Section 4.4 | $e^{i\varphi Z}$ | 4.10 | 4.12 | 4.12 | -
diagonal unitary |  |  | (diagonal) | Figure 9 |  |
Fallback | Section 4.3 | $e^{i\varphi Z}$ | 4.7 | 4.8 | 4.9 | Diagonal
(Figure 7) |  |  | (projective) | Figure 8 |  |
Mixed | Section 4.5 | $e^{i\varphi Z}$ | 4.15 | 4.17 | 4.16 | Mixed diagonal
fallback |  |  | (projective) | Figure 10 |  |

###  4.1 Magnitude approximation

In the general unitary approximation problem (Problem 4.1), the task is to
approximate an arbitrary unitary $U$. The standard approximation strategy is
to use the Euler angle decomposition $U=e^{i\phi_{1}Z}e^{i\theta
X}e^{i\phi_{2}Z}$ and independently approximate the three elements of the
product. Our new approach is to first approximate $e^{i\theta X}$ up to
phases, that is finding a unitary $V$ equal to
$e^{i\phi^{\prime}_{1}Z}e^{i\theta^{\prime}X}e^{i\phi^{\prime}_{2}Z}$ such
that $\theta$ and $\theta^{\prime}$ are close. In other words only magnitudes
of entries of $U$ and $V$ are close, and phases $\phi^{\prime}_{1}$ and
$\phi^{\prime}_{2}$ are arbitrary. We then re-express $U$ as:

$U=e^{i(\phi_{1}-\phi^{\prime}_{1})Z}\underline{e^{i\phi^{\prime}_{1}Z}e^{i\theta
X}e^{i\phi^{\prime}_{2}Z}}e^{i(\phi_{2}-\phi^{\prime}_{2})Z}.$ (14)

The underlined middle part of the product is approximated by $V$, so it
remains to approximate two diagonal $Z$ rotations.

The first main insight behind this strategy is that magnitude approximations
have lower cost (see Table 1 and LABEL:sec:cost-scaling) and are easier to
find than diagonal approximations. The second insight is that, for a random
angle $\theta$, the approximation cost of a diagonal unitary $e^{i\theta Z}$
is independent of $\theta$ (see Figure 2 and LABEL:sec:numerical-results).
Therefore, we may freely adjust the angles of the $Z$-axis rotations in the
Euler decomposition in order to compensate for phase inaccuracy of the
$X$-axis rotation. This results in a circuit that is approximately one-third
shorter, in terms of gate-count, than the solution resulting directly from
Euler decomposition. An analogous strategy was developed by Carvalho Pinto and
Petit in [pinto2018better] for path finding in LPS graphs, and they noted that
their method could be adapted to the quantum setting. This was also confirmed
by Stier [stier], concurrent to the work done in this paper. To construct $V$,
we use the following proposition, which determines the approximate synthesis
of any unitary by imposing the condition that the norm of its upper left
element lies in a given interval.

######  Proposition 4.2 (Magnitude approximation condition).

Let $\theta$ be from $[0,\pi/2]$ and $\varepsilon$ be a positive real number.
Suppose that we have found a special unitary $V$

$V=g_{1}\ldots g_{n}=\mathopen{}\left(\begin{array}[]{cc}u&-v^{\ast}\\\
v&u^{\ast}\end{array}\right)\mathclose{}$

over gate set $G$ such that $|u|$ belongs to the interval
$\left\\{\cos(\theta^{\prime\prime}):\theta^{\prime\prime}\in[0,\pi/2],|\theta^{\prime\prime}-\theta|\leq\delta\right\\}$
for $\delta=\arcsin(\varepsilon/2)$.

Then unitary $V$ satisfies the inequality
$\mathcal{D}_{\diamond}\mathopen{}\left(V,e^{i\phi_{1}^{\prime}Z}\underline{e^{i\theta
X}}e^{i\phi_{1}^{\prime}Z}\right)\mathclose{}\leq\varepsilon$, for
$\phi_{1}^{\prime}$ and $\phi^{\prime}_{2}$ defined by the equality
$V=e^{i\phi_{1}^{\prime}Z}e^{i\theta^{\prime}X}e^{i\phi_{1}^{\prime}Z}$ with
$\theta^{\prime}\in[0,\pi/2]$. We call such $V$ a magnitude
$\varepsilon$-approximation of $e^{i\theta X}$. For a geometric interpretation
of the constraint see Figure 5.

###### Proof.

By unitary invariance property of the diamond norm (see LABEL:prop:diamond-
norm-unitary-invariance), distance
$\mathcal{D}_{\diamond}\mathopen{}\left(V,e^{i\phi_{1}^{\prime}Z}\underline{e^{i\theta
X}}e^{i\phi_{1}^{\prime}Z}\right)\mathclose{}$ is equal to
$\mathcal{D}_{\diamond}\mathopen{}\left(e^{i\theta^{\prime}X},e^{i\theta
X}\right)\mathclose{}$. Now we use the the fact that diamond norm distance
between unitaries $U$ and $V$ is equal to the diameter of the smallest disc
containing eigenvalues of $U^{\dagger}V$ (see LABEL:thm:diamond-distance-
between-unitary-channels). The eigenvalues of $e^{i(\theta^{\prime}-\theta)X}$
are $e^{\pm i(\theta-\theta^{\prime})}$ because Hadamard diagonalizes
$e^{i\phi X}=He^{i\phi Z}H$. Because we only have two eigenvalues, the
diameter of the disc containing them is equal to distance
$|e^{i(\theta-\theta^{\prime})}-e^{-i(\theta-\theta^{\prime})}|$, which is
equal to $2|\sin(\theta-\theta^{\prime})|$. It remain to upper-bound this
quantity. By definition of $\theta^{\prime}$,
$|u|=\cos\mathopen{}\left(\theta^{\prime}\right)\mathclose{}$. This implies
that $|\theta^{\prime}-\theta|\leq\delta$ because cosine is a bijection from
$[0,\pi/2]$ onto $[0,1]$. Using $\sin(\delta)=\varepsilon/2$ we get the
required bound.

∎

Figure 5:  Geometric interpretation of the constraint on complex number $u$
appearing in Proposition 4.2. Possible absolute values $|u|$ belong to the
interval
$\left\\{\cos(\theta^{\prime\prime}):\theta^{\prime\prime}\in[0,\pi/2],|\theta^{\prime\prime}-\theta|\leq\delta\right\\}$
for $\delta=\arcsin(\varepsilon/2)$ and are shown as blue and dashed blue
segments on the horizontal axis.

Note that when
$\arcsin(\varepsilon/2)\leq\theta\leq\pi/2-\arcsin(\varepsilon/2)$, the
absolute value $|u|$ must simply belong to interval
$[\cos(\theta-\arcsin(\varepsilon/2),\cos(\theta+\arcsin(\varepsilon/2))]$.

A simple way to leverage Proposition 4.2 for general unitary approximation is
to split the accuracy $\varepsilon$ evenly among the three factors of the
Euler decomposition. Then, use Proposition 4.2 to find a magnitude
$\epsilon/3$-approximation of the $X$-axis rotation. Finally, find
$\varepsilon/3$-approximations of the two remaining $Z$-axis rotations,
adjusting the angles to compensate for the phase inaccuracy of the $X$-axis
rotation. This strategy is captured formally in the following proposition.

######  Proposition 4.3 (General unitary approximation).

Suppose we are given a target unitary $U=e^{i\phi_{1}Z}e^{i\theta
X}e^{i\phi_{2}Z}$ and target accuracy $\varepsilon$. Let $V$ be a magnitude
$\varepsilon_{0}$-approximation of $e^{i\theta X}$ (see 4.2) and let
$V=e^{i\phi^{\prime}_{1}Z}e^{i\theta^{\prime}X}e^{i\phi^{\prime}_{2}Z}$. Let
channels $\Psi_{k}$ be within diamond norm distance $\varepsilon_{k}$ from
unitary $e^{i(\phi_{k}-\phi^{\prime}_{k})Z}$, for $k=1,2$, and let
$\varepsilon\geq\varepsilon_{0}+\varepsilon_{1}+\varepsilon_{2}$.

Then channel $\mathcal{U}$ induced by $U$ and composition
$\Psi_{1}\mathcal{V}\Psi_{2}$ satisfy

$\mathopen{}\left\|\mathcal{U}-\Psi_{1}\mathcal{V}\Psi_{2}\right\|\mathclose{}_{\diamond}\leq\varepsilon\text{,
where }\mathcal{V}\text{ is the channel induced by }V.$

###### Proof.

Let us write $U$ as a product $U_{1}U_{0}U_{2}$, where
$U_{k}=e^{i(\phi_{k}-\phi^{\prime}_{k})Z}$ and
$U_{0}=e^{i\phi^{\prime}_{1}Z}e^{i\theta X}e^{i\phi^{\prime}_{2}Z}$. We then
write channel $\mathcal{U}$ as composition of channels
$\mathcal{U}_{1}\mathcal{U}_{0}\mathcal{U}_{2}$, where $\mathcal{U}_{k}$ is
the channel induced by $U_{k}$. Using the chain rule for diamond norm we have:

$\mathopen{}\left\|\mathcal{U}-\Psi_{1}\mathcal{V}\Psi_{2}\right\|\mathclose{}_{\diamond}=\mathopen{}\left\|\mathcal{U}_{1}\mathcal{U}_{0}\mathcal{U}_{2}-\Psi_{1}\mathcal{V}\Psi_{2}\right\|\mathclose{}_{\diamond}\leq\mathopen{}\left\|\mathcal{U}_{1}-\Psi_{1}\right\|\mathclose{}_{\diamond}+\mathopen{}\left\|\mathcal{U}_{0}-\mathcal{V}\right\|\mathclose{}_{\diamond}+\mathopen{}\left\|\mathcal{U}_{2}-\Psi_{2}\right\|\mathclose{}_{\diamond}$
(15)

By 4.2
$\mathopen{}\left\|\mathcal{U}_{0}-\mathcal{V}\right\|\mathclose{}_{\diamond}\leq\varepsilon_{0}$.
Combining this bound with Equation 15 completes the proof. ∎

One can optimize the choices of $\varepsilon_{k}$ in the above 4.3. For random
diagonal approximation, the cost scales as $3\log_{2}(1/\varepsilon)+O(1)$ and
for random magnitude approximation the cost scales as
$\log_{2}(1/\varepsilon)+O(1)$ (see Table 1). To minimize overall sequence
length one can choose $\varepsilon_{1}=\varepsilon_{2}=0.43\varepsilon$ and
$\varepsilon_{0}=0.14\varepsilon$, however this improves the sequence length
only by a small additive constant $0.95$ in comparison to distributing errors
equally.

###  4.2 Diagonal unitary approximation

The Euler angle decomposition Equation 13 describes a qubit unitary as a
product of two diagonal unitaries of the form $e^{i\theta Z}$ and one $X$
rotation of the form $e^{i\theta X}$. Proposition 4.2 further reduces the $X$
rotation to a one-dimensional search problem, leaving just the diagonal
unitaries. Therefore, the special case of diagonal unitary approximation is
relevant to the general unitary approximation problem. In this section we
recall some of the known results regarding the diagonal approximation problem.

######  Problem 4.4 (Diagonal unitary approximation).

Given:

  * •

target angle $\theta$, a real number,

  * •

gate set $G$, a finite set of two by two unitary matrices with determinant
one,

  * •

accuracy $\varepsilon$, a positive real number,

Find a sequence $g_{1},\ldots,g_{n}$ of elements of $G$ such that

$\mathcal{D}_{\diamond}\left(\exp(i\theta Z),g_{1}\dots
g_{n}\right)\leq\varepsilon.$

Observe that Problem 4.4 is a special case of the general unitary
approximation problem, where the target unitary is diagonal and approximating
channel $\mathcal{V}$ is induced by unitary $g_{1}\dots g_{n}$. The diagonal
unitary approximation problem is easier to solve because it admits the
following bound on the diamond norm that depends only on the top left entry of
$V=g_{1}\ldots g_{n}.$

######  Lemma 4.5 (Diamond difference from a diagonal unitary).

Given an angle $\theta$ and a unitary

$V=\mathopen{}\left(\begin{array}[]{cc}u&-v^{\ast}\\\
v&u^{\ast}\end{array}\right)\mathclose{},$

the distance

$\mathcal{D}_{\diamond}(e^{i\theta
Z},V)=2\sqrt{1-\left(\mathrm{Re}(ue^{-i\phi})\right)^{2}}\leq
2\sqrt{2-2|\mathrm{Re}\mathopen{}\left(ue^{-i\theta}\right)\mathclose{}|}.$

Proof of this bound is in LABEL:cor:diamond-distance-between-general-and-
diaognal in Appendix LABEL:app:diamond-norm-properties. Lemma 4.5 immediately
suggests a simple condition for solutions of the diagonal approximation
problem.

######  Proposition 4.6 (Diagonal approximation condition).

Let $g_{1},\dots,g_{n}$ be a sequence of gates from a gate set $G$ and let

$g_{1}\dots g_{n}=\mathopen{}\left(\begin{array}[]{cc}u&-v^{\ast}\\\
v&u^{\ast}\end{array}\right)\mathclose{}.$

Then $g_{1},\dots,g_{n}$ is a solution to the diagonal approximation problem
for target angle $\theta$, gate set $G$ and accuracy $\varepsilon$ if

$\mathopen{}\left|\mathrm{Re}\left(ue^{-i\theta}\right)\right|\mathclose{}\geq\sqrt{1-\varepsilon^{2}/4}.$
(16)

For a geometric interpretation of the constraints see Figure 6.

###### Proof.

Let $\mathcal{V}$ be the channel induced by unitary $V=g_{1}\dots g_{n}$. Then
by Lemma 4.5

$\mathopen{}\left\|\mathcal{Z}_{\theta}-\mathcal{V}\right\|\mathclose{}_{\diamond}=2\sqrt{1-|\mathrm{Re}(ue^{-i\theta})|^{2}}\leq
2\sqrt{\varepsilon^{2}/4}=\varepsilon.$ (17)

∎

Figure 6:  Geometric interpretation of constraints on complex number $u$
appearing in Proposition 4.6. The region with red boundary contains complex
numbers $u$ that satisfy constraints
$\mathrm{Re}\mathopen{}\left(ue^{-i\theta}\right)\mathclose{}\geq\sqrt{1-\varepsilon^{2}/4}$
and $\mathopen{}\left|u\right|\mathclose{}\leq 1$. Note that the segment spans
points with angular coordinates $[\theta-\delta,\theta+\delta]$ for
$\delta=\arcsin(\varepsilon/2)$. Constraints in Proposition 4.6 lead to two
regions: one with segment spanning points with angular coordinates
$[\theta-\delta,\theta+\delta]$ and another one with
$[\pi+\theta-\delta,\pi+\theta+\delta]$.

###  4.3 Fallback approximation

Fallback protocols [BRS2015] offer a more efficient way to approximate
diagonal unitaries by incorporating measurements. A fallback protocol is a
non-deterministic single-qubit quantum channel consisting of two steps: a
projective rotation and a conditional fallback. The projective rotation and
fallback steps may be implemented in a variety of ways. We limit our
discussion to fallback protocols with the form illustrated in Figure 7.

Figure 7:  A fallback protocol circuit [BRS2015]. The circuit is composed of
two steps, a projective rotation step and a fallback step. The projective
rotation step effects one of two diagonal rotations on the input
$\mathopen{}\left|\psi\right\rangle\mathclose{}$ depending on the $Z$-basis
measurement outcome of the top ancilla qubit. The two rotation angles are
determined by the matrix entries of the unitary $V$. If the measurement
outcome is one, then a Pauli $Y$ is applied followed by the fallback step
$\mathcal{B}$.

For a fixed single-qubit unitary

$V=\left(\begin{array}[]{cc}u&-v^{\ast}\\\ v&u^{\ast}\end{array}\right)$ (18)

the corresponding projective rotation effects one of two diagonal rotations on
$\mathopen{}\left|\psi\right\rangle\mathclose{}$ depending on the measurement
outcome. With probability $|u|^{2}$ the measurement outcome is zero, the
projective rotation is said to have “succeeded” and the input state undergoes
the transformation

$\mathopen{}\left|\psi\right\rangle\mathclose{}\mapsto
e^{i\theta_{0}Z}\mathopen{}\left|\psi\right\rangle\mathclose{}=e^{i\mathrm{Arg}(u)Z}\mathopen{}\left|\psi\right\rangle\mathclose{}.$
(19)

otherwise, the measurement outcome is one, the projective rotation is said to
have “failed” and

$\mathopen{}\left|\psi\right\rangle\mathclose{}\mapsto
e^{i\theta_{1}Z}\mathopen{}\left|\psi\right\rangle\mathclose{}=e^{i\mathrm{Arg}(v)Z}\mathopen{}\left|\psi\right\rangle\mathclose{}.$
(20)

The projective rotation is intended to approximate a target diagonal unitary
$e^{i\theta Z}$ so that $\theta_{0}\approx\theta$. The constraints necessary
to achieve that goal are captured by the following problem.

######  Problem 4.7 (Projective approximation).

Given:

  * •

target angle $\theta$, a real number,

  * •

success probability $q$, a positive real number between $0$ and $1$,

  * •

gate set $G$, a finite set of two by two unitary matrices with determinant
one,

  * •

accuracy $\varepsilon$, a positive real number,

find a sequence $g_{1},\ldots,g_{n}$ of elements in $G$, such that for $u,v$
defined via $g_{1}\ldots g_{n}=\left(\begin{array}[]{cc}u&-v^{\ast}\\\
v&u^{\ast}\end{array}\right)$ the following holds:

  * •

$|u|^{2}\geq q$, and

  * •

$\mathcal{D}_{\diamond}\left(e^{i\theta
Z},e^{i\mathrm{Arg}(u)Z}\right)\leq\varepsilon$.

Figure 8:  Geometric interpretation of constraint on complex number $u$
appearing in Proposition 4.8. The region with red boundary contains complex
numbers $u$ that satisfy constraints
$\mathrm{Arg}\mathopen{}\left(u\right)\mathclose{}\in[\theta-\delta,\theta+\delta]$
and $\mathopen{}\left|u\right|\mathclose{}\geq q$, where
$\delta=\arcsin(\varepsilon/2)$. Constraints in Proposition 4.8 lead to two
regions: one with
$\mathrm{Arg}\mathopen{}\left(u\right)\mathclose{}\in[\theta-\delta,\theta+\delta]$
and another one with
$\mathrm{Arg}\mathopen{}\left(u\right)\mathclose{}\in[\pi+\theta-\delta,\pi+\theta+\delta]$

Much like the case of the diagonal approximation problem (4.4), solutions to
Problem 4.7 can be characterized entirely by conditions on the complex value
$u$ at the top-left entry of the circuit unitary $g_{1}\ldots g_{n}$. These
conditions are, however, less restrictive than those prescribed by Proposition
4.6. For the detailed comparison of the conditions see Section 4.7 and Figure
12.

######  Proposition 4.8 (Projective approximation condition).

Let $g_{1},\dots,g_{n}$ be a sequence of gates from a gate set $G$ and
$g_{1}\ldots g_{n}=\mathopen{}\left(\begin{smallmatrix}u&-v^{\ast}\\\
v&u^{\ast}\end{smallmatrix}\right)\mathclose{}$. Then $g_{1},\dots,g_{n}$ is a
solution to the projective approximation problem (Problem 4.7) if $u$
satisfies

$\mathopen{}\left|u\right|\mathclose{}\geq\sqrt{q}\mathrm{\leavevmode\nobreak\
and\leavevmode\nobreak\
}\left(\sin\mathopen{}\left|\mathrm{Arg}(u)-\theta\right|\mathclose{}\leq\varepsilon/2\mathrm{\leavevmode\nobreak\
or\leavevmode\nobreak\
}\sin\mathopen{}\left|\mathrm{Arg}(u)-(\theta+\pi)\right|\mathclose{}\leq\varepsilon/2\right)$

For a geometric interpretation of these constraints see Figure 8.

###### Proof.

The condition $|u|\geq\sqrt{q}$ is equivalent to $|u|^{2}\geq q$ from Problem
4.7.

It remains to show that
$\mathopen{}\left\|\mathcal{Z}_{\theta}-\mathcal{Z}_{\mathrm{Arg}(u)}\right\|\mathclose{}_{\diamond}\leq\varepsilon$.
According to LABEL:cor:diamond-distance-between-diaognal, we have
$\mathopen{}\left\|\mathcal{Z}_{\theta}-\mathcal{Z}_{\mathrm{Arg}(u)}\right\|\mathclose{}_{\diamond}\leq
2\sin|\mathrm{Arg(u)}-\theta|$. This immediately implies that the channels are
$\varepsilon$-close when
$\sin\mathopen{}\left|\mathrm{Arg}(u)-\theta\right|\mathclose{}\leq\varepsilon/2$.
Because $\mathcal{Z}_{\theta}=\mathcal{Z}_{\theta+\pi}$ inequality
$\sin\mathopen{}\left|\mathrm{Arg}(u)-(\theta+\pi)\right|\mathclose{}\leq\varepsilon/2$
also ensures
$\mathopen{}\left\|\mathcal{Z}_{\theta}-\mathcal{Z}_{\mathrm{Arg}(u)}\right\|\mathclose{}_{\diamond}\leq\varepsilon$.
∎

[BRS2015] constructs a solution to Problem 4.7 by first approximating the
target phase factor $e^{i\theta}$ with a cyclotomic rational of the form
$z^{\ast}/z$, then searching for a real-valued modifier to achieve the desired
success probability $q$. The characterization of the fallback approximation
problem given by Proposition 4.8 differs by addressing accuracy
($\varepsilon$) and success probability ($q$) conditions simultaneously,
resulting in an intuitive geometric description as illustrated in Figure 8.

Any solution to the diagonal approximation problem is also a solution to the
corresponding projective approximation problem. The projective problem admits
additional and possibly cheaper solutions.

Problem 4.7 constrains the action of a successful projective rotation but
ignores the failure case. The difference $\theta-\theta_{1}$ between the
target and failure angles may be large, in general. Therefore, in the case of
failure (measurement outcome one), the fallback step is applied in order to
recover and approximate the target rotation.

The problem of constructing a fallback step can be treated independently of
the projective rotation. In [BRS2015], the fallback step is a unitary
$B\approx e^{i(\theta-\theta_{1})Z}$ chosen so that the net effect of the
failure case is

$\mathopen{}\left|\psi\right\rangle\mathclose{}\mapsto
Be^{i\theta_{1}Z}\mathopen{}\left|\psi\right\rangle\mathclose{}\approx
e^{i\theta Z}\mathopen{}\left|\psi\right\rangle\mathclose{}.$ (21)

This choice corresponds directly to the diagonal approximation 4.4 defined
earlier. A complete fallback protocol of this form may be constructed by first
solving Problem 4.7 and then solving Problem 4.4 for appropriate values of
$\varepsilon$. This is captured by the following proposition that follows from
standard properties of the diamond norm (see LABEL:app:diamond-norm-
properties).

######  Proposition 4.9 (Fallback approximation).

Suppose we are given:

  * •

target angle $\theta$, a real number,

  * •

success probability $q$, a positive real number between $0$ and $1$,

  * •

gate set $G$, a finite set of two by two unitary matrices with determinant one

and

  * •

real numbers $\varepsilon_{1},\varepsilon_{2}$

  * •

$g_{1}\ldots g_{n}=\left(\begin{array}[]{cc}u&-v^{\ast}\\\
v&u^{\ast}\end{array}\right)$, a solution to Problem 4.7 for
$\\{\theta,q,G,\varepsilon_{1}\\}$, and

  * •

$b_{1}\ldots b_{m}=B$, a solution to Problem 4.4 for
$\\{\theta-\mathrm{Arg}(v),G,\varepsilon_{2}\\}$

then overall fallback protocol accuracy is

$\mathopen{}\left\|\mathcal{Z}_{\theta}-|u|^{2}\mathcal{Z}_{\mathrm{Arg}(u)}-|v|^{2}\mathcal{B}\mathcal{Z}_{\mathrm{Arg}(v)}\right\|\mathclose{}_{\diamond}\leq\varepsilon_{1}+|v|^{2}\varepsilon_{2}$
(22)

where $\mathcal{B}(\rho):=B\rho B^{\dagger}$.

A simple approach to solving the above problem is to choose
$\varepsilon_{1}=\varepsilon/2$, solve 4.7, then choose
$\varepsilon_{2}=\varepsilon/2/|v|^{2}$ and then solve the corresponding
instance of 4.4.

4.9 can be generalized to admit an arbitrary quantum channel (denoted by
$\mathcal{B}$ in Figure 7) as the fallback step. For example, the fallback may
be simply to repeat the projective rotation until success is achieved
[Paetznick2013b, Bocharov2014]. In Section 4.5 we consider fallbacks that are
probabilistic mixtures of unitaries.

The cost of of fallback protocol is a random variable. When success
probability is $q=1-p$ for small $p$, the average cost is equal to the cost of
the projective rotation step plus $p$ times the cost of the fallback step,
which is the cost of a diagonal approximation. The worst case cost is the sum
of the costs of the projective and the diagonal approximation. High worst case
cost might become a problem when using $N$ fallback approximations in
parallel, however we can always ensure that the probability of at least one of
them requiring a fallback step is $p$ by choosing the success probability of
each of them $q=1-p/N$.

###  4.4 Mixed diagonal unitary approximation

4.4 describes synthesis of a qubit unitary by construction and application of
a deterministic sequence of elementary gates. An alternative approach,
proposed by [Campbell2017] and [Hastings2017], is to construct several
sequences of elementary gates and apply one of them according to a probability
distribution. Given the correct probabilistic mixture of unitaries the overall
error of the approximation is reduced quadratically, cutting the approximation
cost roughly in half. In this paper, we introduce the use of diagonal Clifford
twirling to construct these sequences, which ensures that the difference
between the ideal and approximating channel is a Pauli channel. Because of
this, we obtain a closed-form expression for the diamond distance (see 4.14)
which improves on analysis in [Campbell2017, Hastings2017] and results in
lower approximation costs. Method in [Campbell2017] uses diagonal
approximation algorithms as black-boxes and finds under-rotations and over-
rotations by modifying target rotation angle. In contrast, we modify synthesis
algorithms to directly find under and over-rotated approximations and further
reduce approximations costs.

######  Problem 4.10 (Diagonal unitary approximation by unitary mixing).

Given:

  * •

target angle $\theta$, a real number,

  * •

gate set $G$, a finite set of two by two unitary matrices with determinant
one,

  * •

accuracy $\varepsilon$, a positive real number,

Find

  * •

$G_{1},\ldots,G_{n}$, a sequence of sequences $G_{k}$ of elements of $G$ and

  * •

$p_{1},\ldots,p_{n}$, a probability distribution

such that

$\left\|\mathcal{Z}_{\theta}-\sum_{k=1}^{n}p_{k}\mathcal{G}_{k}\right\|_{\diamond}\leq\varepsilon$

where $\mathcal{G}_{k}$ is the channel obtained by applying the sequence
$G_{k}$.

This problem generalizes Problem 4.4 by allowing a random choice among
multiple gate sequences.

[Campbell2017] gives an algorithm for constructing the mixture by “Z twirling”
two unitary approximations: an under-rotation and an over-rotation. The
_twirl_ of a unitary $U$ over generators $\mathcal{G}$ is a channel obtained
by uniformly selecting a random element $V$ over the set generated by
$\mathcal{G}$ and then applying $VUV^{\dagger}$. For example, the twirl of $U$
over $\\{Z,S=e^{-i\pi Z/4}\\}$ which we denote by $\mathcal{T}_{U}$ is given
by

$\mathcal{T}_{U}(\rho)=\frac{1}{4}\sum_{V\in\\{I,Z,S,S^{\dagger}\\}}\left(VUV^{\dagger}\right)\rho\left(V^{\dagger}U^{\dagger}V\right).$
(23)

We show that by twirling over the set $\\{Z,S\\}$, instead of $Z$ alone, the
approximation error of the unitary mixture is a probabilistic mixture of Pauli
operators—i.e., a Pauli channel. This allows for an alternative proof of
[Campbell2017] and [Hastings2017] and yields a simple expression for the
approximation error in terms of diamond distance.

The procedure is as follows. Find two unitaries (defined formally below):
$U_{1}$ an under-rotation and $U_{2}$ an over-rotation. Calculate a
probability $p$ (also defined below) that depends on $U_{1}$ and $U_{2}$. With
probability $p$ select $U_{1}$ and otherwise select $U_{2}$. Then apply the
$\\{Z,S\\}$ twirl to that selection. The resulting channel
$p\mathcal{T}_{U_{1}}+(1-p)\mathcal{T}_{U_{2}}$ approximates a diagonal
unitary $e^{i\theta Z}$ with an accuracy given by the following theorem.

######  Theorem 4.11 (Diamond difference of a twirled mixture).

Let $\theta$ be an angle and let unitaries

$U_{1}=\left(\begin{array}[]{cc}r_{1}e^{i(\theta+\delta_{1})}&v_{1}^{*}\\\
v_{1}&r_{1}e^{-i(\theta+\delta_{1})}\end{array}\right)$ (24)
$U_{2}=\left(\begin{array}[]{cc}r_{2}e^{i(\theta+\delta_{2})}&v_{2}^{*}\\\
v_{2}&r_{2}e^{-i(\theta+\delta_{2})}\end{array}\right)$ (25)

for real values $r_{1},r_{2}$ and $\sin(\delta_{1})<0<\sin(\delta_{2})$.
Define probability

$p=\frac{r_{2}^{2}\sin(2\delta_{2})}{r_{2}^{2}\sin(2\delta_{2})-r_{1}^{2}\sin(2\delta_{1})}.$
(26)

Then

$||p\mathcal{T}_{U_{1}}+(1-p)\mathcal{T}_{U_{2}}-\mathcal{Z}_{\theta}||_{\diamond}=2\left(1-pr_{1}^{2}\cos^{2}(\delta_{1})-(1-p)r_{2}^{2}\cos^{2}(\delta_{2})\right).$
(27)

The proof of the theorem in given in LABEL:sec:diamond-difference-twirled-
mixture. A simple way to leverage 4.11 is by splitting an approximation error
$\varepsilon$ evenly between $U_{1}$ and $U_{2}$ so that

$\displaystyle 1-r_{1}^{2}\cos^{2}(\delta_{1})$
$\displaystyle\leq\varepsilon/2$ (28) $\displaystyle
1-r_{2}^{2}\cos^{2}(\delta_{2})$ $\displaystyle\leq\varepsilon/2.$

The synthesis task then is to find two unitary approximations, an “under
rotation” $U_{1}$ and “over rotation” $U_{2}$ each such that

$|r_{k}\cos(\delta_{k})|\geq\sqrt{1-\varepsilon/2}=1-\varepsilon/4-\varepsilon^{2}/32+o(\varepsilon^{2}),\text{
for }k=1,2.$ (29)

This strategy is captured in the following Proposition.

######  Proposition 4.12 (Diagonal mixing approximation condition).

Suppose we are given sequences $g_{1},\dots,g_{n}$ and $h_{1},\dots,h_{m}$ of
gates from a gate set $G$. Define $u_{k},v_{k}$ from the equations below

$g_{1}\dots g_{n}=\mathopen{}\left(\begin{array}[]{cc}u_{1}&-v_{1}^{\ast}\\\
v_{1}&u_{1}^{\ast}\end{array}\right)\mathclose{},h_{1}\dots
h_{m}=\mathopen{}\left(\begin{array}[]{cc}u_{2}&-v_{2}^{\ast}\\\
v_{2}&u_{2}^{\ast}\end{array}\right)\mathclose{}.$

Then

  * •

sequence $G_{1},\ldots,G_{4},H_{1},\ldots,H_{4}$, where
$G_{k}=\sigma_{k},g_{1},\dots,g_{m},\sigma_{k}^{\dagger}$,
$H_{k}=\sigma_{k},h_{1},\dots,h_{m},\sigma_{k}^{\dagger}$, and
$\sigma_{1},\sigma_{2},\sigma_{3},\sigma_{4}=I,S,Z,S^{\dagger}$.

  * •

probability distribution $p/4,p/4,p/4,p/4,(1-p)/4,(1-p)/4,(1-p)/4,(1-p)/4$

is a solution to the diagonal unitary approximation Problem 4.10 with accuracy
$\varepsilon$ and target angle $\theta$ if

  * •

$u_{1}$ satisfies
$\mathopen{}\left|\mathrm{Re}\mathopen{}\left(u_{1}e^{-i\theta}\right)\mathclose{}\right|\mathclose{}\geq\sqrt{1-\varepsilon/2}$,
$\mathrm{Im}\mathopen{}\left(u_{1}e^{-i\theta}\right)\mathclose{}<0$, and

  * •

$u_{2}$ satisfies
$\mathopen{}\left|\mathrm{Re}\mathopen{}\left(u_{2}e^{-i\theta}\right)\mathclose{}\right|\mathclose{}\geq\sqrt{1-\varepsilon/2}$,
$\mathrm{Im}\mathopen{}\left(u_{2}e^{-i\theta}\right)\mathclose{}>0$.

For a geometric interpretation of these constraints see Figure 9.

###### Proof.

First, note that the sequences $G_{1},G_{2},G_{3},G_{4}$ along with
probabilities $\\{p/4,p/4,p/4,p/4\\}$ corresponds to the $\\{Z,S\\}$ twirl of
$U_{1}=g_{1}\dots g_{n}$ with probability $p$,

$p\mathcal{T}_{U_{1}}(\rho)=\frac{p}{4}\sum_{\sigma\in\\{I,Z,S,S^{\dagger}\\}}\mathopen{}\left(\sigma
U_{1}\sigma^{\dagger}\right)\mathclose{}\rho\mathopen{}\left(\sigma^{\dagger}U_{1}^{\dagger}\sigma\right)\mathclose{}.$
(30)

Similarly, the sequences $H_{1},H_{2},H_{3},H_{4}$ along with probabilities
$\\{(1-p)/4,(1-p)/4,(1-p)/4,(1-p)/4\\}$ corresponds to the $\\{Z,S\\}$ twirl
of $U_{2}=h_{1}\dots h_{m}$ with probability $(1-p)$,

$(1-p)\mathcal{T}_{U_{2}}(\rho)=\frac{1-p}{4}\sum_{\sigma\in\\{I,Z,S,S^{\dagger}\\}}\mathopen{}\left(\sigma
U_{2}\sigma^{\dagger}\right)\mathclose{}\rho\mathopen{}\left(\sigma^{\dagger}U_{2}^{\dagger}\sigma\right)\mathclose{}.$
(31)

We therefore seek to show that
$\mathopen{}\left\|p\mathcal{T}_{U_{1}}+(1-p)\mathcal{T}_{U_{2}}-\mathcal{Z}_{\theta}\right\|\mathclose{}_{\diamond}\leq\varepsilon.$
Let $r_{1}=|u_{1}|,\delta_{1}=\mathrm{Arg}(u_{1})-\theta$ and similarly
$r_{2}=\mathopen{}\left|u_{2}\right|\mathclose{},\delta_{2}=\mathrm{Arg}(u_{2})-\theta$.
Then
$\mathrm{Im}\mathopen{}\left(u_{1}e^{-i\theta}\right)\mathclose{}=\sin(\delta_{1})<0$
and
$\mathrm{Im}\mathopen{}\left(u_{2}e^{-i\theta}\right)\mathclose{}=\sin(\delta_{2})>0$.
Substituting $U_{1}=\mathopen{}\left(\begin{smallmatrix}u_{1}&-v_{1}^{\ast}\\\
v_{1}&u_{1}^{\ast}\end{smallmatrix}\right)\mathclose{}$,
$U_{2}=\mathopen{}\left(\begin{smallmatrix}u_{2}&-v_{2}^{\ast}\\\
v_{2}&u_{2}^{\ast}\end{smallmatrix}\right)\mathclose{}$ into Theorem 4.11 and
using
$\mathopen{}\left|\mathrm{Re}(u_{1}e^{-i\theta})\right|\mathclose{}\geq\sqrt{1-\varepsilon/2}$,
$\mathopen{}\left|\mathrm{Re}(u_{2}e^{-i\theta})\right|\mathclose{}\geq\sqrt{1-\varepsilon/2}$,
we obtain

$\displaystyle\mathopen{}\left\|p\mathcal{T}_{U_{1}}+(1-p)\mathcal{T}_{U_{2}}-\mathcal{Z}_{\theta}\right\|\mathclose{}_{\diamond}$
$\displaystyle=2\mathopen{}\left(1-pr_{1}^{2}\cos^{2}(\delta_{1})-(1-p)r_{2}^{2}\cos^{2}(\delta_{2})\right)\mathclose{}$
(32)
$\displaystyle=2\mathopen{}\left(1-p\mathrm{Re}\mathopen{}\left(u_{1}e^{-i\theta}\right)\mathclose{}^{2}-(1-p)\mathrm{Re}\mathopen{}\left(u_{2}e^{-i\theta}\right)\mathclose{}^{2}\right)\mathclose{}$
$\displaystyle\leq
2\mathopen{}\left(1-p(1-\varepsilon/2)-(1-p)(1-\varepsilon/2)\right)\mathclose{}$
$\displaystyle=\varepsilon.$

∎

Figure 9:  Geometric interpretation of constraints on complex numbers $u_{1}$
and $u_{2}$ appearing in Proposition 4.12. The region with blue boundary
contains complex numbers $u$ that satisfy constraints
$\mathrm{Re}\mathopen{}\left(ue^{-i\theta}\right)\mathclose{}\geq\sqrt{1-\epsilon/2}$
and $\mathopen{}\left|u\right|\mathclose{}\leq 1$. This region is split into
two parts, an under-rotation region for $u_{1}$ with angular coordinates
spanning $[\theta-\tilde{\delta},\theta]$ and an over-rotation region for
$u_{2}$ with angular coordinates spanning $[\theta,\theta+\tilde{\delta}]$ for
$\tilde{\delta}=\arcsin(\sqrt{\varepsilon/2})$.

As observed by [Campbell2017, Hastings2017], the constraints imposed by
Proposition 4.12 admit quadratically better scaling in $\varepsilon$ as
compared to approximation without mixing (Proposition 4.6), which would
require $|r\cos(\delta)|\geq\sqrt{1-\varepsilon^{2}/4}$.

Evenly splitting the error as in Proposition 4.12 does not yield optimal
solutions in general. A better approach is to first find a cheap (but possibly
poor) approximation of the target. With the first approximation fixed, a
search region for the second approximation can be defined. In particularly,
this is useful when identity is a sufficiently good under-rotated or over-
rotated approximation to the target rotation. This happens in practice when
approximating Fourier angles. See LABEL:appendix:optimal-mixing-solutions for
a detailed treatment.

The main technical component of 4.11 is to show that the twirled mixture
$p\mathcal{T}_{U_{1}}(\rho)+(1-p)\mathcal{T}_{U_{2}}(\rho)$ is equal to the
target rotation $e^{i\theta Z}$ followed by a Pauli channel error.

######  Lemma 4.13 (Twirled mixture yields Pauli channel error).

Let $\theta$ be an angle, $U_{1},U_{2}$ be unitaries as in Equation 24 and $p$
be a probability as in Equation 26. Then

$p\mathcal{T}_{U_{1}}(\rho)+(1-p)\mathcal{T}_{U_{2}}(\rho)=\mathcal{E}(\mathcal{Z}_{\theta}(\rho))$
(33)

where $\mathcal{E}$ is a qubit Pauli channel

$\mathcal{E}(\rho)=p\mathcal{P}_{r_{1},\delta_{1}}(\rho)+(1-p)\mathcal{P}_{r_{2},\delta_{2}}(\rho)$
(34)

and

$\mathcal{P}_{r,\delta}(\rho)=r^{2}\cos^{2}(\delta)\rho+\frac{1-r^{2}}{2}(X\rho
X+Y\rho Y)+r^{2}\sin^{2}(\delta)Z\rho Z.$ (35)

This lemma can be proved by calculating the four by four process matrices for
channels induced by $U_{1}$, $U_{2}$, channels $\mathcal{T}_{U_{k}}$ and
$\mathcal{E}$. Recall that for a qubit channel $\Psi$ the process matrix
$\chi$ is given by

$\Psi(\rho)=\sum_{P,Q\in\\{I,X,Y,Z\\}}\chi_{P,Q}P\rho Q.$

The $\\{Z,S\\}$ twirl eliminates all but two off-diagonal elements and the
mixture with probability $p$ eliminates the remaining off-diagonal elements.
We then see that the process matrix of $\mathcal{E}$ is a diagonal matrix and
therefore $\mathcal{E}$ is a Pauli channel. Finally we apply the following
result from Section V.A in [Magesan2012] to get a closed form expression for
the diamond norm distance between $\mathcal{E}$ and the identity channel:

######  Theorem 4.14 (Diamond norm distance between Pauli channels).

Suppose $\mathcal{E}_{1}$, $\mathcal{E}_{2}$ are $n$-qubit Pauli channels,
that is

$\mathcal{E}_{1}(\rho)=\sum_{P\in\\{I,X,Y,Z\\}^{\otimes n}}q_{P}P\rho
P^{\dagger},\,\mathcal{E}_{2}(\rho)=\sum_{P\in\\{I,X,Y,Z\\}^{\otimes
n}}r_{P}P\rho P^{\dagger},$

then
$\mathopen{}\left\|\mathcal{E}_{1}-\mathcal{E}_{2}\right\|\mathclose{}_{\diamond}=\sum_{P\in\\{I,X,Y,Z\\}^{\otimes
n}}|q_{P}-r_{P}|$.

Detailed proofs of 4.13 and 4.11 are given in LABEL:sec:diamond-difference-
twirled-mixture.

###  4.5 Mixed fallback approximation

The results of [Campbell2017, Hastings2017] halve the cost of qubit unitary
approximation by taking probabilistic mixtures of unitaries. We show that an
additional factor of two improvement in cost can be obtained by taking
probabilistic mixtures of _channels_. In particular, we demonstrate a
procedure for mixing fallback protocols (see Section 4.3). The basic idea is
to apply at random one of two projective rotations, one that approximates
$e^{i\theta Z}$ by over-rotation and one that approximates $e^{i\theta Z}$ by
under-rotation. If the projective rotation fails, then a corresponding
fallback channel is applied.

######  Problem 4.15 (Diagonal unitary approximation by projective rotation
mixing).

Given:

  * •

target angle $\theta$, a real number,

  * •

success probability $q$, a positive real number between $0$ and $1$,

  * •

gate set $G$, a finite set of two by two unitary matrices with determinant
one,

  * •

accuracy $\varepsilon$, a positive real number.

Find

  * •

$G_{1},\ldots,G_{n}$, a sequence of sequences of elements of $G$ and

  * •

$p_{1},\ldots,p_{n}$, a probability distribution

such that

  * •

$|u_{k}|^{2}\geq q$ for all $k\in[n]$, and

  * •

the diamond norm of the channel below is at most $\varepsilon$

$\sum_{k=1}^{n}p_{k}|u_{k}|^{2}\left(\mathcal{Z}_{\mathrm{Arg}(u_{k})}-\mathcal{Z}_{\theta}\right)$

where $u_{k}$ is the top-left entry of the unitary
$\mathopen{}\left(\begin{smallmatrix}u_{k}&-v_{k}^{\ast}\\\
v_{k}&u_{k}^{\ast}\end{smallmatrix}\right)\mathclose{}$ corresponding to
sequence $G_{k}$.

In analogy to Problem 4.10, this problem generalizes the projective rotation
approximation problem (Problem 4.7) by allowing multiple projective rotation
circuits in convex combination. Note that the elements of the probability
distribution $p_{1},\ldots,p_{n}$ are distinct from the success probabilities
of the projective rotations.

In the analysis of the fall-back protocol in 4.9 we considered only unitary
fallback steps. We now consider fallbacks that are probabilistic mixtures of
unitaries. The channel $\mathcal{F}$ for a fallback protocol has the form

$\mathcal{F}(\rho)=q\mathcal{Z}_{\theta_{0}}(\rho)+(1-q)\mathcal{B^{\prime}}(\rho)$
(36)

where $\mathcal{B^{\prime}}$ is the composition of the failure rotation
$e^{i\theta_{1}Z}$ and the fallback step $\mathcal{B}$ and $q$ is the
probability of success (measurement outcome of zero).

The following theorem provides a simple closed form bound for the diamond
distance of a mixture of fallback protocols, similar to the expression
obtained from 4.11 for unitary mixtures. The proof is provided in
LABEL:sec:diamond-distance-fallback-mixture.

######  Theorem 4.16 (Diamond distance of a fallback mixture).

Let $\theta$ be an angle and let fallback channels

$\mathcal{F}_{1}(\rho)=q_{1}\mathcal{Z}_{\theta+\delta_{1}}(\rho)+(1-q_{1})\mathcal{B}_{1}(\rho)$
(37)
$\mathcal{F}_{2}(\rho)=q_{2}\mathcal{Z}_{\theta+\delta_{2}}(\rho)+(1-q_{2})\mathcal{B}_{2}(\rho)$
(38)

where $\sin(\delta_{1})\leq 0\leq\sin(\delta_{2})$. Define probability

$p=\frac{q_{2}\sin(2\delta_{2})}{q_{2}\sin(2\delta_{2})-q_{1}\sin(2\delta_{1})}.$
(39)

Then

$\mathopen{}\left\|pq_{1}\left(\mathcal{Z}_{\theta+\delta_{1}}-\mathcal{Z}_{\theta}\right)+(1-p)q_{2}\left(\mathcal{Z}_{\theta+\delta_{2}}-\mathcal{Z}_{\theta}\right)\right\|\mathclose{}_{\diamond}=2\left(pq_{1}\sin^{2}(\delta_{1})+(1-p)q_{2}\sin^{2}(\delta_{2})\right)$
(40)

and the total accuracy of the mixed fall-back approximation protocol is

$\displaystyle||p\mathcal{F}_{1}+(1-p)\mathcal{F}_{2}-\mathcal{Z}_{\theta}||_{\diamond}\leq$
$\displaystyle\,2\left(pq_{1}\sin^{2}(\delta_{1})+(1-p)q_{2}\sin^{2}(\delta_{2})\right)$
(41)
$\displaystyle+p(1-q_{1})||\mathcal{B}_{1}-\mathcal{Z}_{\theta}||_{\diamond}+(1-p)(1-q_{2})||\mathcal{B}_{2}-\mathcal{Z}_{\theta}||_{\diamond}.$

The goal of a synthesis algorithm then is to bound Equation 41555When the
composition $\mathcal{B}_{k}\mathcal{Z}_{-\theta}$ is a Pauli channel, we can
replace inequality in Equation 41 by an exact value by an approximation error
$\varepsilon$. We have some flexibility in bounding the accuracy of the
components of the two fallback protocols. We may set the accuracy of each term
separately

$\displaystyle
2\left(pq_{1}\sin^{2}(\delta_{1})+(1-p)q_{2}\sin^{2}(\delta_{2})\right)$
$\displaystyle=\varepsilon_{1}$ (42) $\displaystyle
p(1-q_{1})||\mathcal{B}_{1}-\mathcal{Z}_{\theta}||_{\diamond}$
$\displaystyle=\varepsilon_{2}$
$\displaystyle(1-p)(1-q_{2})||\mathcal{B}_{2}-\mathcal{Z}_{\theta}||_{\diamond}$
$\displaystyle=\varepsilon_{3}$
$\displaystyle\varepsilon_{1}+\varepsilon_{2}+\varepsilon_{3}$
$\displaystyle\leq\varepsilon.$

The first condition is ensured by solving 4.15. The second two conditions are
ensured by solving the mixed diagonal approximation problems. Note that for
the two fallback terms $||\mathcal{B}_{1}-\mathcal{Z}_{\theta}||_{\diamond}$
and $||\mathcal{B}_{2}-\mathcal{Z}_{\theta}||_{\diamond}$, the accuracy is
scaled by $1-q_{1}$ and $1-q_{2}$ thereby reducing the fallback step
approximation T-count on average by $1.5\log_{2}(1/(p(1-q_{1})))$ and
$1.5\log_{2}(1/(1-p)/(1-q_{2}))$ when using mixed diagonal approximation with
Clifford+$T$ gate set. This is in comparison to the cost of mixed diagonal
approximation with Clifford+$T$ gate set of accuracy $\varepsilon$. As in
previous sections, 4.15 is solved by finding gate sequences with certain
constraints on the top-left entry of the unitaries they compute.

######  Proposition 4.17 (Projective rotation mixing approximation condition).

Suppose that we are given two sequences $G=g_{1},\dots,g_{n}$ and
$H=h_{1},\dots,h_{m}$ from a gate set $G$. Define

$g_{1}\dots g_{n}=\mathopen{}\left(\begin{array}[]{cc}u_{1}&-v_{1}^{\ast}\\\
v_{1}&u_{1}^{\ast}\end{array}\right)\mathclose{},h_{1}\dots
h_{n}=\mathopen{}\left(\begin{array}[]{cc}u_{2}&-v_{2}^{\ast}\\\
v_{2}&u_{2}^{\ast}\end{array}\right)\mathclose{}.$

Suppose that for angle $\theta$ and accuracy $\varepsilon$

  * •

$u_{1}$ satisfies $\mathopen{}\left|u_{1}\right|\mathclose{}\geq\sqrt{q}$,
$-\sqrt{\varepsilon/2}\leq\sin\mathopen{}\left(\mathrm{Arg}(u_{1})-\theta\right)\mathclose{}\leq
0$, and

  * •

$u_{2}$ satisfies $\mathopen{}\left|u_{2}\right|\mathclose{}\geq\sqrt{q}$,
$0\leq\sin\mathopen{}\left(\mathrm{Arg}(u_{2})-\theta\right)\mathclose{}\leq\sqrt{\varepsilon/2}$.

Then sequence $G,H$ and probability distribution $p,1-p$ for

$p=\frac{q_{2}\sin(2\delta_{2})}{q_{2}\sin(2\delta_{2})-q_{1}\sin(2\delta_{1})},\text{
where }q_{k}=|u_{k}|^{2},\delta_{k}=\mathrm{Arg}(u_{k})-\theta$ (43)

is a solution to the projective rotation mixing approximation Problem 4.15.
For a geometric interpretation of the constraints on $u_{1},u_{2}$ see Figure
10.

###### Proof.

The conditions $|u_{1}|\geq\sqrt{q}$, $|u_{2}|\geq\sqrt{q}$ trivially ensure
success probability conditions of Problem 4.15. We need to bound diamond
distance of the channel

$p|u_{1}|^{2}\left(\mathcal{Z}_{\mathrm{Arg}(u_{1})}-\mathcal{Z}_{\theta}\right)+(1-p)|u_{2}|^{2}\left(\mathcal{Z}_{\mathrm{Arg}(u_{2})}-\mathcal{Z}_{\theta}\right).$

By Theorem 4.16 it is equal to

$\displaystyle
2\left(p|u_{1}|^{2}\sin^{2}(\delta_{1})+(1-p)|u_{2}|^{2}\sin^{2}(\delta_{2})\right)\leq
2\left(p\sin^{2}(\delta_{1})+(1-p)\sin^{2}(\delta_{2})\right)$ (44)
$\displaystyle\leq\varepsilon$

∎

Figure 10:  A geometric interpretation of constraints on the projective
rotations given by Proposition 4.17. The sector with blue boundary contains
complex numbers $u$ that satisfy constraints
$\mathrm{Arg}\mathopen{}\left(u\right)\mathclose{}\in[\theta-\tilde{\delta},\theta+\tilde{\delta}]$
and $\mathopen{}\left|u\right|\mathclose{}\geq\sqrt{q}$, where
$\tilde{\delta}=\arcsin(\sqrt{\varepsilon/2})$. This sector is split into two
parts, an over-rotation sector for one projective rotation and an under-
rotation sector for the other projective rotation.

The conditions $|\sin(\delta_{k})|\leq\sqrt{\varepsilon/2}$ imposed by
Proposition 4.17 are quadratically looser than the equivalent condition for
projective rotations without mixing (4.8) which requires
$|\sin(\delta)|\leq\varepsilon/2$. When combined with unitary mixing for the
fallback step, this yields a quadratic improvement in $\varepsilon$ for the
entire fallback protocol. The gate cost of a fallback protocol scales as
$C\log_{2}(1/\varepsilon)+O(1)$. Thus the quadratic improvement in
$\varepsilon$ translates to a roughly two times savings in expected gate cost
over conventional fallback protocols. For the more detailed cost comparisons
see Table 1.

For reasonable ranges of $\varepsilon$ the $\log(1/\varepsilon)$ term is well
below $100$, making additive constants and higher order terms an important
consideration. In that sense, solutions obtained by Proposition 4.17 are sub-
optimal. The overall cost can be optimized by a more careful assignment of
$\varepsilon_{1},\varepsilon_{2}$ and $\varepsilon_{3}$ in Equation 42. This
is discussed further in LABEL:appendix:optimal-mixing-solutions.

###  4.6 Mixed magnitude approximation

We have shown that taking a probabilistic mixture of channels leads to
improvement in accuracy for diagonal approximations with and without the
fallback protocol. It is natural to then question whether a similar
improvement can be achieved for general unitary approximation. We show that
this is indeed the case, following the same strategy of finding approximations
corresponding to under- and over- rotations of a target angle.

We begin by defining the following problem for approximating an arbitrary
X-rotation up to phases.

######  Problem 4.18 (Magnitude approximation by mixing).

Given:

  * •

target angle $\theta$,

  * •

gate set $G$, a finite set of two by two unitary matrices with determinant
one,

  * •

accuracy $\varepsilon$, a positive real number.

Find

  * •

$G_{1},\ldots,G_{n}$, a sequence of sequences of elements of $G$ and

  * •

$p_{1},\ldots,p_{n}$, a probability distribution on these sequences

such that

$\left\|\sum_{k=1}^{n}p_{k}\mathcal{X}_{\arccos(\mathopen{}\left|u_{k}\right|\mathclose{})}-\mathcal{X}_{\theta}\right\|_{\diamond}\leq\varepsilon.$

where $u_{k}$ is the top-left entry of the matrix corresponding to sequence
$G_{k}$ and $\mathcal{X}_{\theta}$ is the channel induced by $e^{i\theta X}$.

As in Problem 4.10 and Problem 4.15, Problem 4.18 allows for a solution
comprising a probabilistic mixture of channels. We can further assume without
loss of generality that $\mathopen{}\left|\cos(\theta)\right|\mathclose{}\geq
1/\sqrt{2}$, by the following remark.

######  Remark 4.19.

Let $g_{1}\dots g_{n}$ be a solution to Problem 4.18 for target angle
$\theta$. Then $iX\cdot g_{n}^{\dagger}\dots g_{1}^{\dagger}$ is a solution
for target angle $\frac{\pi}{2}-\theta$, since $iX\cdot g_{n}^{\dagger}\dots
g_{1}^{\dagger}=iXe^{-i\phi_{2}Z}(-iX)iXe^{-i\theta
X}e^{-i\phi_{1}Z}=e^{i\phi_{2}Z}e^{i(\pi/2-\theta)X}e^{i\phi_{1}Z}.$

Hence, if $\mathopen{}\left|\cos(\theta)\right|\mathclose{}<1/\sqrt{2}$ we can
simply apply magnitude approximation to $\pi/2-\theta$, noting that
$\cos(\pi/2-\theta)=\sin(\theta)\geq 1/\sqrt{2}$.

The following proposition shows that the error bound on the diamond norm in
Problem 4.18 induces a constraint on the top-left entries of the matrices
corresponding to sequences $G_{k}$. Our approach is to again find
X-approximations corresponding to under- and over-rotations of the angle
$\delta$.

######  Proposition 4.20 (Mixed magnitude approximation condition).

Suppose we are given sequences $g_{1},\dots,g_{n}$ and $h_{1},\dots,h_{m}$ of
gates from a gate set. Define complex numbers $u_{k},v_{k}$

$g_{1}\dots g_{n}=\mathopen{}\left(\begin{array}[]{cc}u_{1}&-v_{1}^{\ast}\\\
v_{1}&u_{1}^{\ast}\end{array}\right)\mathclose{},h_{1}\dots
h_{m}=\mathopen{}\left(\begin{array}[]{cc}u_{2}&-v_{2}^{\ast}\\\
v_{2}&u_{2}^{\ast}\end{array}\right)\mathclose{}$

Suppose that for accuracy $\varepsilon$ and target angle $\theta$

  * •

$\mathopen{}\left|u_{1}\right|\mathclose{}\in\\{\cos(\theta^{\prime\prime}):\theta^{\prime\prime}\in[0,\pi/2],0\leq\theta-\theta^{\prime\prime}\leq\arcsin\sqrt{\varepsilon/2}\\}$,
and

  * •

$\mathopen{}\left|u_{2}\right|\mathclose{}\in\\{\cos(\theta^{\prime\prime}):\theta^{\prime\prime}\in[0,\pi/2],0\leq\theta^{\prime\prime}-\theta\leq\arcsin\sqrt{\varepsilon/2}\\}$.

Define

$p=\frac{\sin(2\delta_{2})}{\sin(2\delta_{2})-\sin(2\delta_{1})},\text{ where
}\delta_{k}=\mathrm{arccos}(u_{k})-\theta$

The the sequences $g_{1},\dots,g_{n}$ and $h_{1},\dots,h_{m}$ and probability
distribution $p,1-p$ is a a solution to the magnitude mixing approximation
Problem 4.18 with $n=2$, accuracy $\varepsilon$ and target angle $\theta$. For
a geometric interpretation of the constraints on $|u_{k}|$ see Figure 11.

###### Proof.

Let $g_{1}\dots g_{n}=e^{i\phi_{1}Z}e^{i\theta_{u}X}e^{i\phi_{2}Z}$ with
$\theta_{u}=\theta+\delta_{1}$ and $h_{1}\dots
h_{m}=e^{i\psi_{1}Z}e^{i\theta_{o}X}e^{i\psi_{2}Z}$ with
$\theta_{u}=\theta+\delta_{2}$. Then

$\displaystyle\mathopen{}\left\|p\mathcal{X}_{\theta_{u}}+(1-p)\mathcal{X}_{\theta_{o}}-\mathcal{X}_{\theta}\right\|\mathclose{}_{\diamond}=\mathopen{}\left\|p\mathcal{Z}_{\theta_{u}}+(1-p)\mathcal{Z}_{\theta_{o}}-\mathcal{Z}_{\theta}\right\|\mathclose{}_{\diamond}.$
(45)

using the identity $He^{i\theta Z}H=e^{i\theta X}$ and unitary invariance of
the diamond norm (LABEL:prop:diamond-norm-unitary-invariance). The norm on the
right hand side and the expression for $p$ are of the form required for
Theorem 4.11, so we can conclude
$\mathopen{}\left\|p\mathcal{X}_{\theta_{u}}+(1-p)\mathcal{X}_{\theta_{o}}-\mathcal{X}_{\theta}\right\|\mathclose{}_{\diamond}\leq\varepsilon$
when $2p(\sin^{2}(\delta_{1}))+2(1-p)(\sin^{2}(\delta_{2}))\leq\varepsilon$.
It remain to show that $\sin^{2}(\delta_{k})\leq\varepsilon/2$.

Consider the under-rotated case. By definition
$\mathopen{}\left|u_{1}\right|\mathclose{}=\cos(\theta_{u})$ and so
$\theta-\theta_{u}\leq\arcsin\sqrt{\varepsilon/2}$. So we have
$\sin^{2}(\delta_{1})\leq\varepsilon/2$ as required, and analogously for
$\mathopen{}\left|u_{2}\right|\mathclose{}$. ∎

Figure 11:  A geometric interpretation of constraints given by Proposition
4.20. Absolute values $\mathopen{}\left|u\right|\mathclose{}$ belonging to the
interval
$\\{\cos(\delta^{\prime\prime}):\delta^{\prime\prime}\in[0,\frac{\pi}{2}],\mathopen{}\left|\delta^{\prime\prime}-\theta\right|\mathclose{}\leq\sqrt{\tilde{\delta}}\\}$,
for $\tilde{\delta}=\arcsin\sqrt{\varepsilon/2}$ are shown on the vertical
axis. This interval is split into two parts, an over-rotation interval (blue)
and an under-rotation interval (purple).

In comparison to Proposition 4.2, the constraint on the top-left matrix
entries in Proposition 4.20 is quadratically looser, thus admitting a greater
possible number of candidate values. Analogously to the unmixed case, mixed
magnitude approximations can be extended to approximations of arbitrary
unitaries.

######  Proposition 4.21 (General unitary approximation with mixing).

Let $U=e^{i\alpha Z}e^{i\theta X}e^{i\beta Z}$ be an arbitrary unitary in
$SU(2)$. Let $g_{1},\dots,g_{n}$ and $h_{1},\dots,h_{m}$ be sequences from a
gate set $G$ that satisfy the constraints of Proposition 4.20. Let probability
$p$ be defined as in Proposition 4.20. Define angles $\phi_{k},\psi_{k}$ from
equations $g_{1}\dots g_{n}=e^{i\phi_{1}Z}e^{i\theta_{u}X}e^{i\phi_{2}Z}$ and
$h_{1}\dots h_{m}=e^{i\psi_{1}Z}e^{i\theta_{o}X}e^{i\psi_{2}Z}$. Suppose
$\Phi_{1},\Phi_{2},\Psi_{1}$ and $\Psi_{2}$ are $\varepsilon$-approximations
of
$\mathcal{Z}_{\alpha-\phi_{1}},\mathcal{Z}_{\beta-\phi_{2}},\mathcal{Z}_{\alpha-\psi_{1}}$
and $\mathcal{Z}_{\beta-\psi_{2}}$, respectively. Then

$\mathopen{}\left\|p\Phi_{1}\mathcal{G}\Phi_{2}+(1-p)\Psi_{1}\mathcal{H}\Psi_{2}-\mathcal{U}\right\|\mathclose{}_{\diamond}\leq
3\varepsilon,$

where $\mathcal{G}$ and $\mathcal{H}$ are channels induced by products
$g_{1}\cdots g_{n}$ and $h_{1}\cdots h_{m}$.

###### Proof.

Using the Euler decomposition of $U$ we have
$\mathcal{U}=\mathcal{Z}_{\alpha}\mathcal{X}_{\theta}\mathcal{Z}_{\beta}$ and
so

$\mathopen{}\left\|p\Phi_{1}\mathcal{G}\Phi_{2}+(1-p)\Psi_{1}\mathcal{H}\Psi_{2}-\mathcal{U}\right\|\mathclose{}_{\diamond}=\mathopen{}\left\|p\Phi_{1}\mathcal{G}\Phi_{2}+(1-p)\Psi_{1}\mathcal{H}\Psi_{2}-\mathcal{Z}_{\alpha}\mathcal{X}_{\theta}\mathcal{Z}_{\beta}\right\|\mathclose{}_{\diamond}.$

Applying the triangle inequality, we bound this norm from above by

$p\mathopen{}\left\|\Phi_{1}\mathcal{G}\Phi_{2}-\mathcal{Z}_{\alpha}\mathcal{X}_{\theta_{u}}\mathcal{Z}_{\beta}\right\|\mathclose{}_{\diamond}+(1-p)\mathopen{}\left\|\Psi_{1}\mathcal{H}\Psi_{2}-\mathcal{Z}_{\alpha}\mathcal{X}_{\theta_{o}}\mathcal{Z}_{\beta}\right\|\mathclose{}_{\diamond}+\mathopen{}\left\|\mathcal{Z}_{\alpha}(p\mathcal{X}_{\theta_{u}}+(1-p)\mathcal{X}_{\theta_{o}}-\mathcal{X}_{\theta})\mathcal{Z}_{\beta}\right\|\mathclose{}_{\diamond}.$

Now, using unitary invariance of the diamond norm with $e^{-i\alpha Z}$ and
$e^{-i\beta Z}$, we can simplify the three terms in the expression above and
bound each by an accuracy measure. Concretely, we obtain the following set of
equations

$\displaystyle
p\mathopen{}\left\|\Phi_{1}\mathcal{G}\Phi_{2}-\mathcal{Z}_{\alpha}\mathcal{X}_{\theta_{u}}\mathcal{Z}_{\beta}\right\|\mathclose{}_{\diamond}=p\mathopen{}\left\|\Phi_{1}\underline{\mathcal{G}}\Phi_{2}-\mathcal{Z}_{\alpha}\mathcal{Z}_{-\phi_{1}}\underline{\mathcal{Z}_{\phi_{1}}\mathcal{X}_{\theta_{u}}\mathcal{Z}_{\phi_{2}}}\mathcal{Z}_{-\phi_{2}}\mathcal{Z}_{\beta}\right\|\mathclose{}_{\diamond}=\varepsilon_{1}$
$\displaystyle(1-p)\mathopen{}\left\|\Psi_{1}\mathcal{H}\Psi_{2}-\mathcal{Z}_{\alpha}\mathcal{X}_{\theta_{o}}\mathcal{Z}_{\beta}\right\|\mathclose{}_{\diamond}=(1-p)\mathopen{}\left\|\Psi_{1}\underline{\mathcal{H}}\Psi_{2}-\mathcal{Z}_{\alpha}\mathcal{Z}_{-\psi_{1}}\underline{\mathcal{Z}_{\psi_{1}}\mathcal{X}_{\theta_{o}}\mathcal{Z}_{\psi_{2}}}\mathcal{Z}_{-\psi_{2}}\mathcal{Z}_{\beta}\right\|\mathclose{}_{\diamond}=\varepsilon_{2}$
$\displaystyle\mathopen{}\left\|\mathcal{Z}_{\alpha}(p\mathcal{X}_{\theta_{u}}+(1-p)\mathcal{X}_{\theta_{o}}-\mathcal{X}_{\theta})\mathcal{Z}_{\beta}\right\|\mathclose{}_{\diamond}=\varepsilon_{3}.$

such that the claim holds if
$\varepsilon_{1}+\varepsilon_{2}+\varepsilon_{3}\leq 3\varepsilon.$ Consider
the first norm
$\mathopen{}\left\|\Phi_{1}\mathcal{G}\Phi_{2}-\mathcal{Z}_{\alpha}\mathcal{X}_{\theta_{u}}\mathcal{Z}_{\beta}\right\|\mathclose{}_{\diamond}$
and apply the chain rule

$\displaystyle\mathopen{}\left\|\Phi_{1}\underline{\mathcal{G}}\Phi_{2}-\mathcal{Z}_{\alpha}\mathcal{Z}_{-\phi_{1}}\underline{\mathcal{Z}_{\phi_{1}}\mathcal{X}_{\theta_{u}}\mathcal{Z}_{\phi_{2}}}\mathcal{Z}_{-\phi_{2}}\mathcal{Z}_{\beta}\right\|\mathclose{}_{\diamond}\leq\mathopen{}\left\|\Phi_{1}-\mathcal{Z}_{\alpha-\phi_{1}}\right\|\mathclose{}_{\diamond}+$
(46)
$\displaystyle\mathopen{}\left\|\mathcal{G}-\mathcal{Z}_{\phi_{1}}\mathcal{X}_{\theta_{u}}\mathcal{Z}_{\phi_{2}}\right\|\mathclose{}_{\diamond}+\mathopen{}\left\|\Phi_{2}-\mathcal{Z}_{\beta-\phi_{2}}\right\|\mathclose{}_{\diamond}\leq
2\varepsilon$

The same argument applies _mutatis mutandis_ to
$\mathopen{}\left\|\Psi_{1}\mathcal{H}\Psi_{2}-\mathcal{Z}_{\alpha}\mathcal{X}_{\theta_{o}}\mathcal{Z}_{\beta}\right\|\mathclose{}_{\diamond}$.
Since the sequences $g_{1},\dots,g_{n}$ and $h_{1},\dots,h_{m}$ and $p$
satisfy Proposition 4.20 we also have

$\mathopen{}\left\|\mathcal{Z}_{\alpha}(p\mathcal{X}_{\theta_{u}}+(1-p)\mathcal{X}_{\theta_{o}}-\mathcal{X}_{\theta})\mathcal{Z}_{\beta}\right\|\mathclose{}_{\diamond}=\mathopen{}\left\|p\mathcal{X}_{\theta_{u}}+(1-p)\mathcal{X}_{\theta_{o}}-\mathcal{X}_{\theta})\right\|\mathclose{}\leq\varepsilon.$

Therefore $\varepsilon_{1}+\varepsilon_{2}+\varepsilon_{3}\leq 2\varepsilon
p+2\varepsilon(1-p)+\varepsilon=3\varepsilon$.

∎

###  4.7 Geometric interpretations

In the sections above, we defined two methods for approximating diagonal
unitaries: by direct unitary sequences (Problem 4.4), or by fallback protocols
(4.7). Both of these methods can be extended by using probabilistic mixtures
(Problem 4.10 and Problem 4.15). Each of these problems involves finding one
or more sequences of gates that induce two-by-two unitary matrices of the form
$\left(\begin{smallmatrix}u&-v^{*}\\\ v&u^{*}\end{smallmatrix}\right)$. In
each case, solutions can be described by conditions on the top-left entry $u$.
See Proposition 4.6, Proposition 4.8, Proposition 4.12, and Proposition 4.17.
Those conditions can be illustrated geometrically by regions on the complex
plane: Figure 6 and Figure 8.

Figure 12 shows these regions overlayed one on top of another. This geometric
illustration makes clear the progressive increase in solution space going from
unitary approximation, to fallback approximation and then to probabilistic
mixtures. The region areas for each approximation problem can be quickly
computed using basic formulas for the areas of sectors and triangles. For
instance, for diagonal approximation without mixing the region area is given
by

$\delta-\frac{1}{2}\sin(2\delta)$

where $\delta$ is the angle subtending the minimal sector containing the
region. The region areas are given to leading order of $\varepsilon$ in Table
5.

The projective approximation region encloses the unitary approximation region,
provided that the probability of success $q$ satisfies a modest $q\leq
1-\varepsilon^{2}/4$. Loosely speaking, the condition $q=1-\varepsilon^{2}/4$
can be interpreted as the point at which the projection failure may be treated
deterministically as an approximation error and no longer needs a fallback
step.

Except for large values of $\varepsilon$, the unitary mixture region also
encloses the (non-mixing) unitary approximation region. Finally, the
projective mixing approximation region encloses all of the other regions,
provided that $q\leq 1-\varepsilon/2$.

Indeed, for the chosen value of $\varepsilon=0.1$, the illustration in Figure
12 under-represents the relative difference in region sizes. Practical values
of $\varepsilon$ are typically several orders of magnitude smaller, for which
the relative difference in region sizes is dramatically larger. Figure 13
shows the areas of each of the approximation regions as a function of
$\varepsilon$ and $q$.

(a) Unitary region (Proposition 4.6) with area in $O(\varepsilon^{3})$

(b) Unitary mixing regions (Proposition 4.12) with area in
$O(\varepsilon^{3/2})$

(c) Projective rotation region (Proposition 4.8) with area in $O(\varepsilon)$

(d) Projective rotation mixing regions (Proposition 4.17) with area in
$O(\varepsilon^{1/2})$

Figure 12:  Approximation regions for target diagonal unitary $e^{i\theta Z}$. The figures above show close-ups of a section of the unit circle on the complex plane. Each colored highlight indicates a region of valid solutions for the corresponding approximation problem. For illustration, we have used (an impractical) approximation accuracy $\varepsilon=0.1$ and projective rotation success probability $q=0.9$. The unitary (a) and projective rotation (c) regions (without mixing) shown in red each subtend an angle of $2\delta=2\arcsin(\varepsilon/2)$. The unitary mixing (b) and projective rotation mixing (d) regions shown in blue each subtend an angle of $2\tilde{\delta}=2\arcsin(\sqrt{\varepsilon/2})$. The unitary mixing regions (b) fully encompasses the unitary region (a). Likewise, the projective rotation mixing region (d) fully encompasses the projective rotation region (c). For $q\leq 1-\varepsilon^{2}/4$, the projective rotation region (c) encompasses the unitary region (a). For $q\leq 1-\varepsilon/2$ the mixed projective regions encompasses all other regions.  Figure 13:  Areas of the solution regions prescribed by Proposition 4.6 (unitary), Proposition 4.12 (mixed unitary), Proposition 4.8 (projective) and Proposition 4.17 (mixed projective). Each curve shows the area of the region in the complex plane as a function of approximation accuracy $\varepsilon$ and success probability $q$. The unitary and projective areas, highlighted in red, scale quadratically with $\varepsilon$. The mixed unitary and mixed projective areas, highlighted in blue, scale linearly with $\varepsilon$. For all values of $\varepsilon$ and $q$ the mixed unitary (resp. projective) region has larger area than the corresponding non-mixed unitary (resp. projective) region, thereby admitting more candidate solutions. Except for large values of $\varepsilon$ and $q$, the projective and mixed projective regions have larger area then their respective unitary and mixed unitary regions.  Table 5:  Region areas for unitary approximation problems with and without mixing. The geometric regions associated with each problem are illustrated in Figure 12. The diagonal and projective approximation problems result in two-dimensional regions, while the magnitude approximation problem results in a one-dimensional interval. In the latter case, _Region area_ refers to the length of the interval. In all cases, it can be seen that the mixed version of the problem corresponds to a larger approximation region.  Approximation Problem | Region area (big-O) | Region area (with pre-factors)
---|---|---
Diagonal unitary approximation | $O(\varepsilon^{3})$ | $\varepsilon^{3}/12+O(\varepsilon^{5})$
Mixed diagonal approximation | $O(\varepsilon^{3/2})$ | $(2/3)(\varepsilon/2)^{3/2}+O(\varepsilon^{5/2})$
Projective rotation approximation | $O(\varepsilon)$ | $(1-q)\varepsilon/2+O(\varepsilon^{3})$
Mixed projective approximation | $O(\varepsilon^{1/2})$ | $(1-q)(\varepsilon/2)^{1/2}+O(\varepsilon^{3/2})$
Magnitude approximation | $O(\varepsilon)$ | $\varepsilon/\sqrt{2}+O(\varepsilon^{3})$
Mixed magnitude approximation | $O(\varepsilon^{1/2})$ | $\varepsilon^{1/2}+O(\varepsilon^{3/2})$

##  5 Solutions to approximation problems for common gate sets

In Section 4, we related solutions to various approximation problems to
specific geometric regions. In this section, we specialize these results to a
few specific gate sets. Unitaries that can be synthesized exactly with these
gate sets define discrete subsets within the above convex bodies, and this
naturally leads to an enumeration strategy to solve approximation problems. We
first describe this approach for the V basis, the Clifford$+T$ basis and the
Clifford$+\sqrt{T}$ basis, and we then generalize it to a family of gate sets
introduced by [Kliuchnikov2015b] for diagonal approximation problems.

Throughout this section, we introduce the following notation to highlight
common methodology across our three illustrative examples. We use $L$ to
denote the field in which the entries of the unitaries defining a gate set
lie, and $O_{L}$ to denote the integer ring of $L$. We associate a _gate set
determinant_ $\ell\in K$ to each gate set, such that any element generated by
the gate set can be written as
$\frac{1}{\sqrt{\ell^{N}}}\left(\begin{smallmatrix}u&-v^{*}\\\
v&u^{*}\end{smallmatrix}\right)$ with $u,v\in O_{L}$ and $N\in\mathbb{Z}$. The
determinant of a unitary with elements in $L$ lies in the maximal totally real
subfield, which we denote by $K$. We have $L=K(i)$, where $i^{2}=-1$. The norm
of an element in $L$ is a mapping from $L$ to $K$ defined by taking the
product of an element of $L$ with its complex conjugate. We denote the ring of
integers of $K$ by $O_{K}$.

###  5.1 V basis

####  5.1.1 Quaternion maximal order

We recall that the V basis consists of the following six matrices:

$\displaystyle V_{\pm Z}$
$\displaystyle=\frac{1}{\sqrt{\ell}}\begin{pmatrix}1\pm 2i&0\\\ 0&1\mp
2i\end{pmatrix},$ $\displaystyle V_{\pm Y}$
$\displaystyle=\frac{1}{\sqrt{\ell}}\begin{pmatrix}1&\mp 2\\\ \pm
2&1\end{pmatrix},$ $\displaystyle V_{\pm X}$
$\displaystyle=\frac{1}{\sqrt{\ell}}\begin{pmatrix}1&\pm 2i\\\ \pm
2i&1\end{pmatrix},$

where $\ell=5$. Let $K=\mathbb{Q}$ and let
$L=\mathbb{Q}(i)=\\{a_{0}+ia_{1}:a_{0},a_{1}\in\mathbb{Q}\\}$, where
$i^{2}=-1$. Let $O_{K}=\mathbb{Z}$ and
$O_{L}=\mathbb{Z}[i]=\\{a_{0}+ia_{1}:a_{0},a_{1}\in\mathbb{Z}\\}$ be the rings
of integers of $K$ and $L$ respectively. Any element $t=a_{0}+ia_{1}\in O_{L}$
can be written as a 2-dimensional vector over $O_{K}$, namely $(a_{0},a_{1})$.
There are two homomorphisms of $L$ into $\mathbb{C}$ related by complex
conjugation. Denote by $\sigma$ the homomorphism such that $\sigma(i)=i$.

Let $M_{2}(L)$ be the algebra of all $2\times 2$ matrices with entries in $L$,
and let $\mathcal{O}$ be an order in $M_{2}(L)$ that contains all the $V$
basis elements scaled by $\sqrt{\ell}$. For concreteness we will set

$\mathcal{O}:=\mathbb{Z}\cdot I+\mathbb{Z}\cdot iX+\mathbb{Z}\cdot
iY+\mathbb{Z}\cdot iZ.$ (47)

We extend $\sigma$ over $\mathcal{O}$ in a natural way, namely for
$M\in\mathcal{O}$ we define $\sigma(M)$ as the matrix whose elements are the
images of the elements of $M$ under $\sigma$. As observed in [Bocharov2013,
Kliuchnikov2015b], elements of $\mathcal{O}$ with determinant $\ell^{N}$
correspond to unitaries that can be expressed as a product of $N$ matrices
from the V gate set via the map
$\sigma^{\prime}(M)=\frac{1}{\sqrt{\ell^{N}}}\sigma(M)$.

######  Example 5.1.

Let $V=V_{Z}\cdot V_{X}=\frac{1}{5}\left(\begin{smallmatrix}1+2i&2i-4\\\
2i+4&1-2i\end{smallmatrix}\right)$. Then,
$M_{V}=\left(\begin{smallmatrix}1+2i&2i-4\\\
2i+4&1-2i\end{smallmatrix}\right)=I+2\cdot iX-4\cdot iY+2\cdot
iZ\in\mathcal{O}$ and $\sigma^{\prime}(M_{V})=V.$ Since $\det{(M_{V})}=5^{2},$
we have $N=2$ as expected, as $V$ is the product of two $V$ basis matrices.
Note that the sequence $V_{Z}V_{X}$ cannot be simplified (over the V basis) so
$N$ is minimal.