gates; for a generic such unitary, any finite sequence of gates only approximates the desired target. In this case, errors in the gate can add coherently so that, roughly, the error

ε

in the unitary of each gate must scale as

ε\lesssim 1/N

, where

N

is the number of gates. If, however, one has the option of synthesizing one of several unitaries near the desired target, and if an average of these options is closer to the target, we give some elementary bounds showing cases in which the errors can be made to add incoherently by averaging over random choices, so that, roughly, one needs

ε\lesssim 1/\sqrt{N}

. We remark on one particular application to distilling magic states where this effect happens automatically in the usual circuits.

DOI: 10.48550/arxiv.1612.01011

Related papers

Turning gate synthesis errors into incoherent errors

Matthew B. Hastings

Using error correcting codes and fault tolerant techniques, it is possible, at least in theory, to produce logical qubits with significantly lower error rates than the underlying physical qubits. Suppose, however, that the gates that act on these logical qubits are only approximation of the desired gate. This can arise, for example, in synthesizing a single qubit unitary from a set of Clifford and T gates; for a generic such unitary, any finite sequence of gates only approximates the desired target. In this case, errors in the gate can add coherently so that, roughly, the error epsilon in the unitary of each gate must scale as epsilon < 1/N, where N is the number of gates. If, however, one has the option of synthesizing one of several unitaries near the desired target, and if an average of these options is closer to the target, we give some elementary bounds showing cases in which the errors can be made to add incoherently by averaging over random choices, so that, roughly, one needs epsilon < 1/ √ N. We remark on one particular application to distilling magic states where this effect happens automatically in the usual circuits.Using error correcting codes and fault tolerant techniques, it is possible, at least in theory, to produce logical qubits with significantly lower error rates than the underlying physical qubits. Suppose, however, that the gates that act on these logical qubits are only approximation of the desired gate. This can arise, for example, in synthesizing a single qubit unitary from a set of Clifford and T gates; for a generic such unitary, any finite sequence of gates only approximates the desired target. In this case, errors in the gate can add coherently so that, roughly, the error epsilon in the unitary of each gate must scale as epsilon < 1/N, where N is the number of gates. If, however, one has the option of synthesizing one of several unitaries near the desired target, and if an average of these options is closer to the target, we give some elementary bounds showing cases in which the errors can be made to add incoherently by averaging over random choices, so that, roughly, one needs epsilon < 1/ √ N. We remark on one particular application to distilling magic states where this effect happens automatically in the usual circuits.

Quantum Information and ComputationApr 1, 201712 citations

Cost-optimal single-qubit gate synthesis in the Clifford hierarchy

Gary J. Mooney, Charles D. Hill, Lloyd C. L. Hollenberg

For universal quantum computation, a major challenge to overcome for practical implementation is the large amount of resources required for fault-tolerant quantum information processing. An important aspect is implementing arbitrary unitary operators built from logical gates within the quantum error correction code. A synthesis algorithm can be used to approximate any unitary gate up to arbitrary precision by assembling sequences of logical gates chosen from a small set of universal gates that are fault-tolerantly performable while encoded in a quantum error-correction code. However, current procedures do not yet support individual assignment of base gate costs and many do not support extended sets of universal base gates. We analysed cost-optimal sequences using an exhaustive search based on Dijkstra’s pathfinding algorithm for the canonical Clifford+ T set of base gates and compared them to when additionally including Z -rotations from higher orders of the Clifford hierarchy. Two approaches of assigning base gate costs were used. First, costs were reduced to T -counts by recursively applying a Z -rotation catalyst circuit. Second, costs were assigned as the average numbers of raw (i.e. physical level) magic states required to directly distil and implement the gates fault-tolerantly. We found that the average sequence cost decreases by up to 54±3% when using the Z -rotation catalyst circuit approach and by up to 33±2% when using the magic state distillation approach. In addition, we investigated observed limitations of certain assignments of base gate costs by developing an analytic model to estimate the proportion of sets of Z -rotation gates from higher orders of the Clifford hierarchy that are found within sequences approximating random target gates.For universal quantum computation, a major challenge to overcome for practical implementation is the large amount of resources required for fault-tolerant quantum information processing. An important aspect is implementing arbitrary unitary operators built from logical gates within the quantum error correction code. A synthesis algorithm can be used to approximate any unitary gate up to arbitrary precision by assembling sequences of logical gates chosen from a small set of universal gates that are fault-tolerantly performable while encoded in a quantum error-correction code. However, current procedures do not yet support individual assignment of base gate costs and many do not support extended sets of universal base gates. We analysed cost-optimal sequences using an exhaustive search based on Dijkstra’s pathfinding algorithm for the canonical Clifford+ T set of base gates and compared them to when additionally including Z -rotations from higher orders of the Clifford hierarchy. Two approaches of assigning base gate costs were used. First, costs were reduced to T -counts by recursively applying a Z -rotation catalyst circuit. Second, costs were assigned as the average numbers of raw (i.e. physical level) magic states required to directly distil and implement the gates fault-tolerantly. We found that the average sequence cost decreases by up to 54±3% when using the Z -rotation catalyst circuit approach and by up to 33±2% when using the magic state distillation approach. In addition, we investigated observed limitations of certain assignments of base gate costs by developing an analytic model to estimate the proportion of sets of Z -rotation gates from higher orders of the Clifford hierarchy that are found within sequences approximating random target gates.

arXiv:2005.05581QuantumFeb 15, 20216 citations

Constructing arbitrary single-qubit fault-tolerant gates

Austin G. Fowler

We present a method for constructing optimal fault-tolerant approximations of arbitrary unitary gates using an arbtrary discrete universal gate set. The method presented is numerical and scales exponentially with the number of gates used in the approximation, however, for the specific case of arbitrary single-qubit gates and the fault-tolerant gates permitted by the 7-qubit Steane code, it is shown that the longest practical gates sequences can be found. We also analyse the practicality of the fault-tolerant approximations of the phase rotation gates used in Shor’s algorithm and find that simple non-fault-tolerant phase rotations are more robust for realistic error rates. A general scaling law of how rapidly these fault-tolerant approximations converge to arbitrary single-qubit gates is also determined. In large-scale quantum computation, every qubit of data is encoded across multiple physical qubits to form a logical qubit permitting quantum error correctionWe present a method for constructing optimal fault-tolerant approximations of arbitrary unitary gates using an arbtrary discrete universal gate set. The method presented is numerical and scales exponentially with the number of gates used in the approximation, however, for the specific case of arbitrary single-qubit gates and the fault-tolerant gates permitted by the 7-qubit Steane code, it is shown that the longest practical gates sequences can be found. We also analyse the practicality of the fault-tolerant approximations of the phase rotation gates used in Shor’s algorithm and find that simple non-fault-tolerant phase rotations are more robust for realistic error rates. A general scaling law of how rapidly these fault-tolerant approximations converge to arbitrary single-qubit gates is also determined. In large-scale quantum computation, every qubit of data is encoded across multiple physical qubits to form a logical qubit permitting quantum error correction

arXiv:quant-ph/0411206Nov 30, 20046 citations

Shorter gate sequences for quantum computing by mixing unitaries

Earl T. Campbell

Fault-tolerant quantum computers compose elements of a discrete gate set in order to approximate a target unitary. The problem of minimizing the number of gates is known as gate synthesis. The approximation error is a form of coherent noise, which can be significantly more damaging than comparable incoherent noise. We show how mixing over different gate sequences can convert this coherent noise into an incoherent form. As measured by diamond distance, the postmixing noise is quadratically smaller than before mixing, without increasing resource cost upper bounds. Equivalently, we can look for shorter gate sequences that achieve the same precision as unitary gate synthesis. For a broad class of problems this gives a factor $1/2$ reduction in worst-case resource costs.Fault-tolerant quantum computers compose elements of a discrete gate set in order to approximate a target unitary. The problem of minimizing the number of gates is known as gate synthesis. The approximation error is a form of coherent noise, which can be significantly more damaging than comparable incoherent noise. We show how mixing over different gate sequences can convert this coherent noise into an incoherent form. As measured by diamond distance, the postmixing noise is quadratically smaller than before mixing, without increasing resource cost upper bounds. Equivalently, we can look for shorter gate sequences that achieve the same precision as unitary gate synthesis. For a broad class of problems this gives a factor $1/2$ reduction in worst-case resource costs.

arXiv:1612.02689Physical Review AApr 5, 201755 citations

Multi-qubit controlled gate synthesis without T-count overhead in the small-error limit

Soichiro Yamazaki, Seiseki Akibue, Kaoru Sano

We study the Clifford+T synthesis of quantum multiplexers $U=\bigoplus_{i=1}^{2^n}U_i$ : an $n$ -qubit control register selects which single-qubit gate $U_i\in\mathrm{SU}(2)$ acts on the target qubit. For each block $U_i$ , consider the minimum even T-count needed to approximate it within diamond distance $\varepsilon$ without ancillae, and let $m$ be the largest of these costs. For an arbitrary multiplexer $U$ , we construct an approximation of $U$ within the same distance using at most $m+O(\sqrt{2^n(m+1)})$ $T$ gates. With one control qubit, the cost is $m+O(1)$ and no ancillae are required. We also prove a lower bound that allows the Clifford+T circuit to use any number of clean ancillae initialized to zero and returned exactly to zero. For fixed $n$ and independent Haar-random blocks, the minimum T-count among these circuits lies between $(3-δ)\log_2(1/\varepsilon)$ and $(3+δ)\log_2(1/\varepsilon)$ for every fixed $δ>0$ , except with probability $O(\varepsilon^{c_{n,δ}})$ as $\varepsilon\rightarrow0$ . The optimal leading coefficient is therefore the same as for a single Haar-random $\mathrm{SU}(2)$ gate. In the lower-bound proof, unitarity forces pairs of off-diagonal blocks describing transitions in opposite directions to satisfy cancellation relations with residuals of order $\varepsilon^2$ . We combine these relations with the arithmetic of Clifford+T circuits to bound the Haar measure of targets compatible with each pair of off-diagonal blocks. As an application, we obtain ancilla-free approximations of Haar-random $\mathrm{SU}(4)$ gates within diamond distance $\varepsilon$ , using at most $(9+δ)\log_2(1/\varepsilon)$ $T$ gates for every fixed $δ>0$ , except with probability $O(\varepsilon^{c_δ})$ with $c_δ>0$ .We study the Clifford+T synthesis of quantum multiplexers $U=\bigoplus_{i=1}^{2^n}U_i$: an $n$-qubit control register selects which single-qubit gate $U_i\in\mathrm{SU}(2)$ acts on the target qubit. For each block $U_i$, consider the minimum even T-count needed to approximate it within diamond distance $\varepsilon$ without ancillae, and let $m$ be the largest of these costs. For an arbitrary multiplexer $U$, we construct an approximation of $U$ within the same distance using at most $m+O(\sqrt{2^n(m+1)})$ $T$ gates. With one control qubit, the cost is $m+O(1)$ and no ancillae are required. We also prove a lower bound that allows the Clifford+T circuit to use any number of clean ancillae initialized to zero and returned exactly to zero. For fixed $n$ and independent Haar-random blocks, the minimum T-count among these circuits lies between $(3-δ)\log_2(1/\varepsilon)$ and $(3+δ)\log_2(1/\varepsilon)$ for every fixed $δ>0$, except with probability $O(\varepsilon^{c_{n,δ}})$ as $\varepsilon\rightarrow0$. The optimal leading coefficient is therefore the same as for a single Haar-random $\mathrm{SU}(2)$ gate. In the lower-bound proof, unitarity forces pairs of off-diagonal blocks describing transitions in opposite directions to satisfy cancellation relations with residuals of order $\varepsilon^2$. We combine these relations with the arithmetic of Clifford+T circuits to bound the Haar measure of targets compatible with each pair of off-diagonal blocks. As an application, we obtain ancilla-free approximations of Haar-random $\mathrm{SU}(4)$ gates within diamond distance $\varepsilon$, using at most $(9+δ)\log_2(1/\varepsilon)$ $T$ gates for every fixed $δ>0$, except with probability $O(\varepsilon^{c_δ})$ with $c_δ>0$.

quant-pharXiv:2603.14202Mar 17, 20260 citations

Unifying Gate Synthesis and Magic State Distillation

Earl T. Campbell, Mark Howard

The leading paradigm for performing a computation on quantum memories can be encapsulated as distill-then-synthesize. Initially, one performs several rounds of distillation to create high-fidelity magic states that provide one good T gate, an essential quantum logic gate. Subsequently, gate synthesis intersperses many T gates with Clifford gates to realize a desired circuit. We introduce a unified framework that implements one round of distillation and multiquibit gate synthesis in a single step. Typically, our method uses the same number of T gates as conventional synthesis but with the added benefit of quadratic error suppression. Because of this, one less round of magic state distillation needs to be performed, leading to significant resource savings.The leading paradigm for performing a computation on quantum memories can be encapsulated as distill-then-synthesize. Initially, one performs several rounds of distillation to create high-fidelity magic states that provide one good T gate, an essential quantum logic gate. Subsequently, gate synthesis intersperses many T gates with Clifford gates to realize a desired circuit. We introduce a unified framework that implements one round of distillation and multiquibit gate synthesis in a single step. Typically, our method uses the same number of T gates as conventional synthesis but with the added benefit of quadratic error suppression. Because of this, one less round of magic state distillation needs to be performed, leading to significant resource savings.

arXiv:1606.01906Physical Review LettersFeb 9, 201753 citations

T

gates; for a generic such unitary, any finite sequence of gates only approximates the desired target. In this case, errors in the gate can add coherently so that, roughly, the error

ε

in the unitary of each gate must scale as

ε\lesssim 1/N

, where

N

ε\lesssim 1/\sqrt{N}

. We remark on one particular application to distilling magic states where this effect happens automatically in the usual circuits.

1/2

reduction in worst-case resource costs.

We study the Clifford+T synthesis of quantum multiplexers

U=\bigoplus_{i=1}^{2^n}U_i

: an

n

-qubit control register selects which single-qubit gate

U_i\in\mathrm{SU}(2)

acts on the target qubit. For each block

U_i

, consider the minimum even T-count needed to approximate it within diamond distance

\varepsilon

without ancillae, and let

m

be the largest of these costs. For an arbitrary multiplexer

U

, we construct an approximation of

U

within the same distance using at most

m+O(\sqrt{2^n(m+1)})

T

gates. With one control qubit, the cost is

m+O(1)

and no ancillae are required. We also prove a lower bound that allows the Clifford+T circuit to use any number of clean ancillae initialized to zero and returned exactly to zero. For fixed

n

and independent Haar-random blocks, the minimum T-count among these circuits lies between

(3-δ)\log_2(1/\varepsilon)

and

(3+δ)\log_2(1/\varepsilon)

for every fixed

δ>0

, except with probability

O(\varepsilon^{c_{n,δ}})

\varepsilon\rightarrow0

. The optimal leading coefficient is therefore the same as for a single Haar-random

\mathrm{SU}(2)

gate. In the lower-bound proof, unitarity forces pairs of off-diagonal blocks describing transitions in opposite directions to satisfy cancellation relations with residuals of order

\varepsilon^2

. We combine these relations with the arithmetic of Clifford+T circuits to bound the Haar measure of targets compatible with each pair of off-diagonal blocks. As an application, we obtain ancilla-free approximations of Haar-random

\mathrm{SU}(4)

gates within diamond distance

\varepsilon

, using at most

(9+δ)\log_2(1/\varepsilon)

T

gates for every fixed

δ>0

, except with probability

O(\varepsilon^{c_δ})

with

c_δ>0