Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1612.01011 · Quantum Information and Computation

Turning gate synthesis errors into incoherent errors

Matthew B. Hastings

Published Apr 1, 2017• 46 citations
arXivHTMLPDF

Abstract

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.

DOI
10.26421/qic17.5-6-7

Related papers

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.

arXiv:2005.05581•Quantum•Feb 15, 2021•7 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.

arXiv:1606.01906•Physical Review Letters•Feb 9, 2017•60 citations

Aspects of Fault-Tolerant Quantum Computation

Joseph K. Iverson

This thesis is concerned with fault-tolerant quantum information processing using quantum error-correcting codes. It contains two major pieces of work. The first is a study of coherent noise in the context of stabilizer error-correcting codes. The second is a proposed scheme for a universal set of fault-tolerant logical gates in a particular code family built out of the 3D toric code. Chapter 1 provides an introduction to quantum computation and fault tolerance. Many basic concepts in error-correcting codes are defined. Special attention is paid to the set of code properties that are most likely to determine how easily a given fault-tolerant scheme might be implemented on a physical device. These include the fault-tolerant noise threshold and the overhead. In Chapters 2 and 3 we study the effectiveness of quantum error correction against coherent noise. Coherent errors (for example, unitary noise) can interfere constructively, so that in some cases the average infidelity of a quantum circuit subjected to coherent errors may increase quadratically with the circuit size; in contrast, when errors are incoherent (for example, depolarizing noise), the average infidelity increases at worst linearly with circuit size. We consider the performance of quantum stabilizer codes against a noise model in which a unitary rotation is applied to each qubit, where the axes and angles of rotation are nearly the same for all qubits. In Chapter 2 we introduce coherent noise and incoherent noise and a number of methods that are useful for the study of coherent noise. We study the repetition code as a basic example, and we also study a correlated noise model. In Chapter 3 we show that for the toric code subject to such independent coherent noise, and for minimal-weight decoding, the logical channel after error correction becomes increasingly incoherent as the length of the code increases, provided the noise strength decays inversely with the code distance. A similar conclusion holds for weakly correlated coherent noise. Our methods can also be used for analyzing the performance of other codes and fault-tolerant protocols against coherent noise. However, our result does not show that the coherence of the logical channel is suppressed in the more physically relevant case where the noise strength is held constant as the code block grows, and we recount the difficulties that prevented us from extending the result to that case. Nevertheless our work supports the idea that fault-tolerant quantum computing schemes will work effectively against coherent noise, providing encouraging news for quantum hardware builders who worry about the damaging effects of control errors and coherent interactions with the environment. Chapter 4 is connected to another aspect of fault tolerance, fault-tolerant logical gates. The toric code is a promising candidate for fault-tolerant quantum computation because of its high threshold and low-weight stabilizers. A universal gate set in the toric code generally requires magic state distillation, which can incur a significant qubit overhead. In this work we construct an error-correcting code in three dimensions based on the toric code that features a fault-tolerant T gate with no magic state distillation required. We further describe a subsystem version of our code which supports a universal set of fault-tolerant gates. This code can be converted into the stabilizer version using gauge-fixing. We also argue that our code can be converted to a (2+1)-D protocol, where a 2D lattice undergoes a measurement-based protocol over time. In this way, a fault-tolerant logical T gate can be realized in a 2D toric code structure.

•Jun 1, 2020•2 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.

arXiv:1612.02689•Physical Review A•Apr 5, 2017•76 citations

Reducing T Gates with Unitary Synthesis

Tianyi Hao, Amanda Xu, Swamit Tannu

Quantum error correction is essential for achieving practical quantum computing but has a significant computational overhead. Among fault-tolerant (FT) gate operations, non-Clifford gates, such as T, are particularly expensive due to their reliance on magic state distillation. These costly T gates appear frequently in FT circuits as many quantum algorithms require arbitrary single-qubit rotations, such as Rx and Rz gates, which must be decomposed into a sequence of T and Clifford gates. In many quantum circuits, Rx and Rz gates can be fused to form a single U3 unitary. However, existing synthesis methods, such as gridsynth, rely on indirect decompositions, requiring separate Rz decompositions that result in a threefold increase in T count.

arXiv:2503.15843•International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS)•Mar 10, 2026•21 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$.

quant-pharXiv:2603.14202•Mar 17, 2026•1 citation
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.
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.
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.
This thesis is concerned with fault-tolerant quantum information processing using quantum error-correcting codes. It contains two major pieces of work. The first is a study of coherent noise in the context of stabilizer error-correcting codes. The second is a proposed scheme for a universal set of fault-tolerant logical gates in a particular code family built out of the 3D toric code. Chapter 1 provides an introduction to quantum computation and fault tolerance. Many basic concepts in error-correcting codes are defined. Special attention is paid to the set of code properties that are most likely to determine how easily a given fault-tolerant scheme might be implemented on a physical device. These include the fault-tolerant noise threshold and the overhead. In Chapters 2 and 3 we study the effectiveness of quantum error correction against coherent noise. Coherent errors (for example, unitary noise) can interfere constructively, so that in some cases the average infidelity of a quantum circuit subjected to coherent errors may increase quadratically with the circuit size; in contrast, when errors are incoherent (for example, depolarizing noise), the average infidelity increases at worst linearly with circuit size. We consider the performance of quantum stabilizer codes against a noise model in which a unitary rotation is applied to each qubit, where the axes and angles of rotation are nearly the same for all qubits. In Chapter 2 we introduce coherent noise and incoherent noise and a number of methods that are useful for the study of coherent noise. We study the repetition code as a basic example, and we also study a correlated noise model. In Chapter 3 we show that for the toric code subject to such independent coherent noise, and for minimal-weight decoding, the logical channel after error correction becomes increasingly incoherent as the length of the code increases, provided the noise strength decays inversely with the code distance. A similar conclusion holds for weakly correlated coherent noise. Our methods can also be used for analyzing the performance of other codes and fault-tolerant protocols against coherent noise. However, our result does not show that the coherence of the logical channel is suppressed in the more physically relevant case where the noise strength is held constant as the code block grows, and we recount the difficulties that prevented us from extending the result to that case. Nevertheless our work supports the idea that fault-tolerant quantum computing schemes will work effectively against coherent noise, providing encouraging news for quantum hardware builders who worry about the damaging effects of control errors and coherent interactions with the environment. Chapter 4 is connected to another aspect of fault tolerance, fault-tolerant logical gates. The toric code is a promising candidate for fault-tolerant quantum computation because of its high threshold and low-weight stabilizers. A universal gate set in the toric code generally requires magic state distillation, which can incur a significant qubit overhead. In this work we construct an error-correcting code in three dimensions based on the toric code that features a fault-tolerant T gate with no magic state distillation required. We further describe a subsystem version of our code which supports a universal set of fault-tolerant gates. This code can be converted into the stabilizer version using gauge-fixing. We also argue that our code can be converted to a (2+1)-D protocol, where a 2D lattice undergoes a measurement-based protocol over time. In this way, a fault-tolerant logical T gate can be realized in a 2D toric code structure.
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/21/21/2 reduction in worst-case resource costs.
Quantum error correction is essential for achieving practical quantum computing but has a significant computational overhead. Among fault-tolerant (FT) gate operations, non-Clifford gates, such as T, are particularly expensive due to their reliance on magic state distillation. These costly T gates appear frequently in FT circuits as many quantum algorithms require arbitrary single-qubit rotations, such as Rx and Rz gates, which must be decomposed into a sequence of T and Clifford gates. In many quantum circuits, Rx and Rz gates can be fused to form a single U3 unitary. However, existing synthesis methods, such as gridsynth, rely on indirect decompositions, requiring separate Rz decompositions that result in a threefold increase in T count.
We study the Clifford+T synthesis of quantum multiplexers U=⨁i=12nUiU=\bigoplus_{i=1}^{2^n}U_iU=⨁i=12n​Ui​: an nnn-qubit control register selects which single-qubit gate Ui∈SU(2)U_i\in\mathrm{SU}(2)Ui​∈SU(2) acts on the target qubit. For each block UiU_iUi​, consider the minimum even T-count needed to approximate it within diamond distance ε\varepsilonε without ancillae, and let mmm be the largest of these costs. For an arbitrary multiplexer UUU, we construct an approximation of UUU within the same distance using at most m+O(2n(m+1))m+O(\sqrt{2^n(m+1)})m+O(2n(m+1)​) TTT gates. With one control qubit, the cost is m+O(1)m+O(1)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 nnn and independent Haar-random blocks, the minimum T-count among these circuits lies between (3−δ)log⁡2(1/ε)(3-δ)\log_2(1/\varepsilon)(3−δ)log2​(1/ε) and (3+δ)log⁡2(1/ε)(3+δ)\log_2(1/\varepsilon)(3+δ)log2​(1/ε) for every fixed δ>0δ>0δ>0, except with probability O(εcn,δ)O(\varepsilon^{c_{n,δ}})O(εcn,δ​) as ε→0\varepsilon\rightarrow0ε→0. The optimal leading coefficient is therefore the same as for a single Haar-random SU(2)\mathrm{SU}(2)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 ε2\varepsilon^2ε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 SU(4)\mathrm{SU}(4)SU(4) gates within diamond distance ε\varepsilonε, using at most (9+δ)log⁡2(1/ε)(9+δ)\log_2(1/\varepsilon)(9+δ)log2​(1/ε) TTT gates for every fixed δ>0δ>0δ>0, except with probability O(εcδ)O(\varepsilon^{c_δ})O(εcδ​) with cδ>0c_δ>0cδ​>0.