We present an algorithm for efficiently approximating of qubit unitaries over gate sets derived from totally definite quaternion algebras. It achieves ε-approximations using circuits of length O(log(1/ε)), which is asymptotically optimal. The algorithm achieves the same quality of approximation as previously-known algorithms for Clifford+T [arXiv:1212.6253], V-basis [arXiv:1303.1411] and Clifford+π/12 [arXiv:1409.3552], running on average in time polynomial in O(log(1/ε)) (conditional on a number-theoretic conjecture). Ours is the first such algorithm that works for a wide range of gate sets and provides insight into what should constitute a "good" gate set for a fault-tolerant quantum computer. Joint work with Alex Bocharov, Martin Roetteler, Jon Yard: http://arxiv.org/abs/1510.03888
We present an algorithm for efficiently approximating of qubit unitaries over gate sets derived from totally definite quaternion algebras. It achieves ε-approximations using circuits of length O(log(1/ε)), which is asymptotically optimal. The algorithm achieves the same quality of approximation as previously-known algorithms for Clifford+T [arXiv:1212.6253], V-basis [arXiv:1303.1411] and Clifford+π/12 [arXiv:1409.3552], running on average in time polynomial in O(log(1/ε)) (conditional on a number-theoretic conjecture). Ours is the first such algorithm that works for a wide range of gate sets and provides insight into what should constitute a "good" gate set for a fault-tolerant quantum computer. Joint work with Alex Bocharov, Martin Roetteler, Jon Yard: http://arxiv.org/abs/1510.03888
We present an algorithm for efficiently approximating of qubit unitaries over gate sets derived from totally definite quaternion algebras. It achieves ε-approximations using circuits of length O(log(1/ε)), which is asymptotically optimal. The algorithm achieves the same quality of approximation as previously-known algorithms for Clifford+T [arXiv:1212.6253], V-basis [arXiv:1303.1411] and Clifford+π/12 [arXiv:1409.3552], running on average in time polynomial in O(log(1/ε)) (conditional on a number-theoretic conjecture). Ours is the first such algorithm that works for a wide range of gate sets and provides insight into what should constitute a "good" gate set for a fault-tolerant quantum computer.
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 works \cite{Hastings2017} and \cite{Campbell2017}, we show that taking probabilistic mixtures of channels to solve fallback \cite{BRS2015} and magnitude approximation problems saves factor of two in approximation costs. In particular, over the Clifford+ T gate set we achieve an average non-Clifford gate count of 0.23 log 2 ( 1 / ε ) + 2.13 and T-count 0.56 log 2 ( 1 / ε ) + 5.3 with mixed fallback approximations for diamond norm accuracy ε .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+ T ). We also provide detailed numerical results for Clifford+T and Clifford+ 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.
Resource-efficient and high-precision approximate synthesis of quantum circuits expressed in the Clifford+T gate set is vital for Fault-Tolerant quantum computing.Efficient optimal methods are known for single-qubit R Z unitaries, otherwise the problem is generally intractable.Search-based methods, like simulated annealing, empirically generate low resource cost approximate implementations of general multi-qubit unitaries so long as low precision (Hilbert-Schmidt distances of ε ≥ 10 -2 ) can be tolerated.These algorithms build up circuits that directly invert target unitaries.We instead leverage search-based methods to first approximately diagonalize a unitary, then perform the inversion analytically.This lets difficult continuous rotations be bypassed and handled in a postprocessing step.Our approach improves both the implementation precision and run time of synthesis algorithms by orders of magnitude when evaluated on unitaries from real quantum algorithms.On benchmarks previously synthesizable only with analytical techniques like the Quantum Shannon Decomposition, diagonalization uses an average of 95% fewer non-Clifford gates.
Quantum computation is of current ubiquitous interest in physics, computer science, and the public interest. In the not-so-distant future, quantum computers will be relatively common pieces of research equipment. Eventually, one can expect an actively quantum computer to be a common feature of life. In this work, I study the approximation efficiency of several common universal quantum gate sets at short sequence lengths using an implementation of the Solovay-Kitaev algorithm. I begin by developing from almost nothing the relevant formal mathematics to rigorously describe what one means by the terms universal gate set and covering efficiency. I then describe some interesting results on the asymptotic covering properties of certain classes of universal gate sets and discuss the theorem which the Solovay-Kitaev algorithm is based on. Moving from mathematical introduction to experimental method, I then describe how sets will be compared. I use the commonly studied sets H+T, Pauli+V, V, and Clifford+T to determine which is the most efficient at approximating randomly generated unitaries. By doing so, we get an understanding of how well each set would perform in the context of a general quantum computer processor. This was accomplished by using the same implementation of the Solovay-Kitaev algorithm throughout, with roughly equal-sized preprocessed libraries formed from each gate set, over approximations for 10,000 randomly generated unitary matrices at algorithm depth n=5. Ultimately, the Pauli+V and V sets were the most efficient and had similar performance qualities. On average the Pauli+V set produced approximations of length 15,491 and accuracy 0.0002686. The V basis produced approximations of average sequence length 16,403 and accuracy 0.0001465. This performance is about equal given this particular implementation of the Solovay-Kitaev algorithm. We conclude that this result is somewhat surprising as the general behavior and efficiency of these particular choices of gate set are expected to be similar. It is possible though that the asymptotic efficiencies of these gate sets vary by a relatively wide margin and this has effected the experiment. It is also possible that some aspect of a naive implementation of the Solovay-Kitaev algorithm resulted in the Hadamard gate based sets performing more poorly than the V basis sets overall. Due to constraints on computational power, this result could also be limited to this particular accuracy regime and could even out as tolerance 𝜀 is taken to be arbitrarily small. Further possibilities of this result as well as further work are then discussed.
Building generic gates from a restricted gate set is a difficult but important problem, especially in the noisy regime where only a limited set of noise-resistant gates are available, e.g., fault-tolerant Clifford gates (generated by Hadamard, phase, and gates) and fault-tolerant Toffoli gates. The Toffoli is also often used as a building block of many algorithms and will need to be constructed if not directly available. This makes Clifford + Toffoli an attractive gate set for building generic gates. In this Letter we give a simple and efficient algorithm for building an approximate single-qubit rotation using only Clifford + Toffoli , which in turn enables any generic single-qubit unitary. An important difference compared to earlier attempts is that the use of the Toffoli allows us to use simple rounding as opposed to a complicated approximation algorithm. The resulting gate array does not rely on repeatedly applying a fixed rotation, but immediately applies a rotation R θ * that is ε -close to the desired rotation R θ , with a success probability strictly greater than 1 / 2 . It can be rerun upon failure, giving an expected number of repetitions strictly less than 2, an expected Toffoli count strictly less than 4 ⌈ log 1 ε ⌉ , an expected gate depth strictly less than 4 ⌈ log 1 ε ⌉ + 6 , and uses 2 ⌈ log 1 ε ⌉ ancillas. The small circuit depth of our construction enables low-noise gates on existing quantum computational devices, and allows for arbitrary precision using a very modest number of ancillas. Published by the American Physical Society 2024
Abstract In quantum computing there are quite a few universal gate sets, each having their own characteristics. In this paper we study the Clifford+CS universal fault-tolerant gate set. The CS gate is used is many applications and this gate set is an important alternative to Clifford+T. We introduce a generating set in order to represent any unitary implementable by this gate set and with this we derive a bound on the CS-count of arbitrary multi-qubit unitaries. Analysing the channel representation of the generating set elements, we infer JnCS⊂JnT J n CS ⊂ J n T , where JnCS J n CS and JnT J n T are the set of unitaries exactly implementable by the Clifford+CS and Clifford+T gate sets, respectively. We develop CS-count optimal synthesis algorithms for both approximately and exactly implementable multi-qubit unitaries. With the help of these we derive a CS-count-optimal circuit for Toffoli, implying JnTof=JnCS J n Tof = J n CS , where JnTof J n Tof is the set of unitaries exactly implementable by the Clifford+Toffoli gate set. Such conclusions can have an important impact on resource estimates of quantum algorithms.