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:1310.7290

Logic Synthesis for Fault-Tolerant Quantum Computers

N. Cody Jones

Published Oct 28, 2013• 14 citations
arXivHTMLPDF

Abstract

Efficient constructions for quantum logic are essential since quantum computation is experimentally challenging. This thesis develops quantum logic synthesis as a paradigm for reducing the resource overhead in fault-tolerant quantum computing. The model for error correction considered here is the surface code. After developing the theory behind general logic synthesis, the resource costs of magic-state distillation for the $T = \exp(i π(I-Z)/8)$ gate are quantitatively analyzed. The resource costs for a relatively new protocol distilling multi-qubit Fourier states are calculated for the first time. Four different constructions of the fault-tolerant Toffoli gate, including two which incorporate error detection, are analyzed and compared. The techniques of logic synthesis reduce the cost of fault-tolerant quantum computation by one to two orders of magnitude, depending on which benchmark is used. Using resource analysis for $T$ gates and Toffoli gates, several proposals for constructing arbitrary quantum gates are compared, including "Clifford+$T$" sequences, $V$-basis sequences, phase kickback, and programmable ancilla rotations. The application of arbitrary gates to quantum algorithms for simulating chemistry is discussed as well. Finally, the thesis examines the techniques which lead to efficient constructions of quantum logic, and these observations point to even broader applications of logic synthesis.

DOI
10.48550/arxiv.1310.7290

Related papers

Unified framework for magic state distillation and multiqubit gate synthesis with reduced resource cost

Earl T. Campbell, Mark Howard

The standard approach to fault-tolerant quantum computation is to store information in a quantum error correction code, such as the surface code, and process information using a strategy that can be summarized as distill then synthesize. In the distill step, one performs several rounds of distillation to create high-fidelity logical qubits in a magic state. Each such magic state provides one good $T$ gate. In the synthesize step, one seeks the optimal decomposition of an algorithm into a sequence of many $T$ gates interleaved with Clifford gates. This gate-synthesis problem is well understood for multiqubit gates that do not use any Hadamards. We present an in-depth analysis of a unified framework that realizes one round of distillation and multiqubit gate synthesis in a single step. We call these synthillation protocols, and show they lead to a large reduction in resource overheads. This is because synthillation can implement a general class of circuits using the same number of $T$ states as gate synthesis, yet with the benefit of quadratic error suppression. This general class includes all circuits primarily dominated by control-control-$Z$ gates, such as adders and modular exponentiation routines used in Shor's algorithm. Therefore, synthillation removes the need for a costly round of magic state distillation. We also present several additional results on the multiqubit gate-synthesis problem. We provide an efficient algorithm for synthesizing unitaries with the same worst-case resource scaling as optimal solutions. For the special case of synthesizing controlled unitaries, our techniques are not just efficient but exactly optimal. We observe that the gate-synthesis cost, measured by $T$ count, is often strictly subadditive. Numerous explicit applications of our techniques are also presented.

arXiv:1606.01904•Physical Review A•Feb 9, 2017•91 citations

Resource optimization for fault-tolerant quantum computing

Adam Paetznick

In this thesis we examine a variety of techniques for reducing the resources required for fault-tolerant quantum computation. First, we show how to simplify universal encoded computation by using only transversal gates and standard error correction procedures, circumventing existing no-go theorems. We then show how to simplify ancilla preparation, reducing the cost of error correction by more than a factor of four. Using this optimized ancilla preparation, we develop improved techniques for proving rigorous lower bounds on the noise threshold. Additional overhead can be incurred because quantum algorithms must be translated into sequences of gates that are actually available in the quantum computer. In particular, arbitrary single-qubit rotations must be decomposed into a discrete set of fault-tolerant gates. We find that by using a special class of non-deterministic circuits, the cost of decomposition can be reduced by as much as a factor of four over state-of-the-art techniques, which typically use deterministic circuits. Finally, we examine global optimization of fault-tolerant quantum circuits under physical connectivity constraints. We adapt techniques from VLSI in order to minimize time and space usage for computations in the surface code, and we develop a software prototype to demonstrate the potential savings.

arXiv:1410.5124•Oct 19, 2014•4 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.

arXiv:2005.05581•Quantum•Feb 15, 2021•6 citations

Architectures for fault-tolerant quantum computation

Joe O’Gorman

Quantum computing has enormous potential, but this can only be realised if quantum errors can be controlled sufficiently to allow quantum algorithms to be completed reliably. However, quantum-error-corrected logical quantum bits (qubits) which can be said to have achieved meaningful error suppression have not yet been demonstrated. This thesis reports research on several topics related to the challenge of designing fault-tolerant quantum computers. The first topic is a proposal for achieving large-scale error correction with the surface code in a silicon donor based quantum computing architecture. This proposal relaxes some of the stringent requirements in donor placement precision set by previous ideas from the single atom level to the order of 10 nm in some regimes. This is shown by means of numerical simulation of the surface code threshold. The second topic then follows, it is the development of a method for benchmarking and assessing the performance of small error correcting codes in few-qubit systems, introducing a metric called 'integrity' - closely linked to the trace distance -- and a proposal for experiments to demonstrate various stepping stones on the way to 'strictly superior' quantum error correction. Most quantum error correcting codes, including the surface code, do not allow for fault-tolerant universal computation without the addition of extra gadgets. One method of achieving universality is through a process of distilling and then consuming high quality 'magic states'. This process adds additional overhead to quantum computation over and above that incurred by the use of the base level quantum error correction. The latter parts of this thesis report an investigation into how many physical qubits are needed in a `magic state factory' within a surface code quantum computer and introduce a number of techniques to reduce the overhead of leading magic state techniques. It is found that universal quantum computing is achievable with ∼ 16 million qubits if error rates across a device are kept below 10-4. In addition, the thesis introduces improved methods of achieving magic state distillation for unconventional magic states that allow for logical small angle rotations, and show that this can be more efficient than synthesising these operations from the gates provided by traditional magic states.

•Jan 1, 2017•0 citations

Low-overhead constructions for the fault-tolerant Toffoli gate

Cody Jones

We present two constructions for the Toffoli gate which substantially reduce resource costs in fault-tolerant quantum computing. The first contribution is a Toffoli gate requiring Clifford operations plus only four $T=\mathrm{exp}(i\ensuremath{\pi}{\ensuremath{\sigma}}^{z}/8)$ gates, whereas conventional circuits require seven $T$ gates. An extension of this result is that adding $n$ control inputs to a controlled gate requires $4n$ $T$ gates, whereas the best prior result was $8n$. The second contribution is a quantum circuit for the Toffoli gate which can detect a single ${\ensuremath{\sigma}}^{z}$ error occurring with probability $p$ in any one of eight $T$ gates required to produce the Toffoli gate. By postselecting circuits that did not detect an error, the posterior error probability is suppressed to lowest order from $4p$ (or $7p$, without the first contribution) to $28{p}^{2}$ for this enhanced construction. In fault-tolerant quantum computing, this construction can reduce the overhead for producing logical Toffoli gates by an order of magnitude.

arXiv:1212.5069•Physical Review A•Feb 20, 2013•204 citations

Magic state distillation and cost analysis in fault-tolerant universal quantum computation

Yiting Liu, Zhi Ma, Lan Luo +5 more

Abstract Magic states have been widely studied in recent years as resource states that help quantum computers achieve fault-tolerant universal quantum computing. The fault-tolerant quantum computing requires fault-tolerant implementation of a set of universal logical gates. Stabilizer code, as a commonly used error correcting code with good properties, can apply the Clifford gates transversally which is fault tolerant. But only Clifford gates cannot realize universal computation. Magic states are introduced to construct non-Clifford gates that combine with Clifford operations to achieve universal quantum computing. Since the preparation of quantum states is inevitably accompanied by noise, preparing the magic state with high fidelity and low overhead is the crucial problem to realizing universal quantum computation. In this paper, we survey the related literature in the past 20 years and introduce the common types of magic states, the protocols to obtain high-fidelity magic states, and overhead analysis for these protocols. Finally, we discuss the future directions of this field.

Quantum Science and Technology•Jul 12, 2023•9 citations
Efficient constructions for quantum logic are essential since quantum computation is experimentally challenging. This thesis develops quantum logic synthesis as a paradigm for reducing the resource overhead in fault-tolerant quantum computing. The model for error correction considered here is the surface code. After developing the theory behind general logic synthesis, the resource costs of magic-state distillation for the T=exp⁡(iπ(I−Z)/8)T = \exp(i π(I-Z)/8)T=exp(iπ(I−Z)/8) gate are quantitatively analyzed. The resource costs for a relatively new protocol distilling multi-qubit Fourier states are calculated for the first time. Four different constructions of the fault-tolerant Toffoli gate, including two which incorporate error detection, are analyzed and compared. The techniques of logic synthesis reduce the cost of fault-tolerant quantum computation by one to two orders of magnitude, depending on which benchmark is used. Using resource analysis for TTT gates and Toffoli gates, several proposals for constructing arbitrary quantum gates are compared, including "Clifford+TTT" sequences, VVV-basis sequences, phase kickback, and programmable ancilla rotations. The application of arbitrary gates to quantum algorithms for simulating chemistry is discussed as well. Finally, the thesis examines the techniques which lead to efficient constructions of quantum logic, and these observations point to even broader applications of logic synthesis.
The standard approach to fault-tolerant quantum computation is to store information in a quantum error correction code, such as the surface code, and process information using a strategy that can be summarized as distill then synthesize. In the distill step, one performs several rounds of distillation to create high-fidelity logical qubits in a magic state. Each such magic state provides one good TTT gate. In the synthesize step, one seeks the optimal decomposition of an algorithm into a sequence of many TTT gates interleaved with Clifford gates. This gate-synthesis problem is well understood for multiqubit gates that do not use any Hadamards. We present an in-depth analysis of a unified framework that realizes one round of distillation and multiqubit gate synthesis in a single step. We call these synthillation protocols, and show they lead to a large reduction in resource overheads. This is because synthillation can implement a general class of circuits using the same number of TTT states as gate synthesis, yet with the benefit of quadratic error suppression. This general class includes all circuits primarily dominated by control-control-ZZZ gates, such as adders and modular exponentiation routines used in Shor's algorithm. Therefore, synthillation removes the need for a costly round of magic state distillation. We also present several additional results on the multiqubit gate-synthesis problem. We provide an efficient algorithm for synthesizing unitaries with the same worst-case resource scaling as optimal solutions. For the special case of synthesizing controlled unitaries, our techniques are not just efficient but exactly optimal. We observe that the gate-synthesis cost, measured by TTT count, is often strictly subadditive. Numerous explicit applications of our techniques are also presented.
In this thesis we examine a variety of techniques for reducing the resources required for fault-tolerant quantum computation. First, we show how to simplify universal encoded computation by using only transversal gates and standard error correction procedures, circumventing existing no-go theorems. We then show how to simplify ancilla preparation, reducing the cost of error correction by more than a factor of four. Using this optimized ancilla preparation, we develop improved techniques for proving rigorous lower bounds on the noise threshold. Additional overhead can be incurred because quantum algorithms must be translated into sequences of gates that are actually available in the quantum computer. In particular, arbitrary single-qubit rotations must be decomposed into a discrete set of fault-tolerant gates. We find that by using a special class of non-deterministic circuits, the cost of decomposition can be reduced by as much as a factor of four over state-of-the-art techniques, which typically use deterministic circuits. Finally, we examine global optimization of fault-tolerant quantum circuits under physical connectivity constraints. We adapt techniques from VLSI in order to minimize time and space usage for computations in the surface code, and we develop a software prototype to demonstrate the potential savings.
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.
Quantum computing has enormous potential, but this can only be realised if quantum errors can be controlled sufficiently to allow quantum algorithms to be completed reliably. However, quantum-error-corrected logical quantum bits (qubits) which can be said to have achieved meaningful error suppression have not yet been demonstrated. This thesis reports research on several topics related to the challenge of designing fault-tolerant quantum computers. The first topic is a proposal for achieving large-scale error correction with the surface code in a silicon donor based quantum computing architecture. This proposal relaxes some of the stringent requirements in donor placement precision set by previous ideas from the single atom level to the order of 10 nm in some regimes. This is shown by means of numerical simulation of the surface code threshold. The second topic then follows, it is the development of a method for benchmarking and assessing the performance of small error correcting codes in few-qubit systems, introducing a metric called 'integrity' - closely linked to the trace distance -- and a proposal for experiments to demonstrate various stepping stones on the way to 'strictly superior' quantum error correction. Most quantum error correcting codes, including the surface code, do not allow for fault-tolerant universal computation without the addition of extra gadgets. One method of achieving universality is through a process of distilling and then consuming high quality 'magic states'. This process adds additional overhead to quantum computation over and above that incurred by the use of the base level quantum error correction. The latter parts of this thesis report an investigation into how many physical qubits are needed in a `magic state factory' within a surface code quantum computer and introduce a number of techniques to reduce the overhead of leading magic state techniques. It is found that universal quantum computing is achievable with ∼ 16 million qubits if error rates across a device are kept below 10-4. In addition, the thesis introduces improved methods of achieving magic state distillation for unconventional magic states that allow for logical small angle rotations, and show that this can be more efficient than synthesising these operations from the gates provided by traditional magic states.
We present two constructions for the Toffoli gate which substantially reduce resource costs in fault-tolerant quantum computing. The first contribution is a Toffoli gate requiring Clifford operations plus only four $T=\mathrm{exp}(i\ensuremath{\pi}{\ensuremath{\sigma}}^{z}/8)$ gates, whereas conventional circuits require seven TTT gates. An extension of this result is that adding nnn control inputs to a controlled gate requires 4n4n4n TTT gates, whereas the best prior result was 8n8n8n. The second contribution is a quantum circuit for the Toffoli gate which can detect a single ${\ensuremath{\sigma}}^{z}$ error occurring with probability ppp in any one of eight TTT gates required to produce the Toffoli gate. By postselecting circuits that did not detect an error, the posterior error probability is suppressed to lowest order from 4p4p4p (or 7p7p7p, without the first contribution) to 28p228{p}^{2}28p2 for this enhanced construction. In fault-tolerant quantum computing, this construction can reduce the overhead for producing logical Toffoli gates by an order of magnitude.
Abstract Magic states have been widely studied in recent years as resource states that help quantum computers achieve fault-tolerant universal quantum computing. The fault-tolerant quantum computing requires fault-tolerant implementation of a set of universal logical gates. Stabilizer code, as a commonly used error correcting code with good properties, can apply the Clifford gates transversally which is fault tolerant. But only Clifford gates cannot realize universal computation. Magic states are introduced to construct non-Clifford gates that combine with Clifford operations to achieve universal quantum computing. Since the preparation of quantum states is inevitably accompanied by noise, preparing the magic state with high fidelity and low overhead is the crucial problem to realizing universal quantum computation. In this paper, we survey the related literature in the past 20 years and introduce the common types of magic states, the protocols to obtain high-fidelity magic states, and overhead analysis for these protocols. Finally, we discuss the future directions of this field.