The Toffoli gate is an important universal quantum gate, and will alongside the Clifford gates be available in future fault-tolerant quantum computing hardware. Many quantum algorithms rely on performing arbitrarily small single-qubit rotations for their function, and these rotations may also be used to construct any unitary from a limited (but universal) gate set. How to carry out such rotations is then of significant interest. In this work, we evaluate the performance of a recently proposed single-qubit rotation algorithm using the Clifford plus Toffoli gate set by implementation of a one-shot version on both a real and a simulated quantum computer. We test the algorithm under various simulated noise levels using a per-qubit depolarizing error noise model and examine how the probabilities and process fidelities are affected. We then conduct live runs and find that the results reasonably match the simulated results. We also attempt to model the hardware noise by combining a number of noise models, matching the results to results of the live runs to approximate the hardware noise. Our results suggest that the algorithm will perform well for up to 1 % noise under the noise models we chose. We further posit the use of our algorithm as a benchmark for quantum processing units, given that it has a low complexity that is easy to fine-tune in small steps. We provide details for how to do this.
The Toffoli gate is an important universal quantum gate, and will alongside the Clifford gates be available in future fault-tolerant quantum computing hardware. Many quantum algorithms rely on performing arbitrarily small single-qubit rotations for their function, and these rotations may also be used to construct any unitary from a limited (but universal) gate set. How to carry out such rotations is then of significant interest. In this work, we evaluate the performance of a recently proposed single-qubit rotation algorithm using the Clifford plus Toffoli gate set by implementation of a one-shot version on both a real and a simulated quantum computer. We test the algorithm under various simulated noise levels using a per-qubit depolarizing error noise model and examine how the probabilities and process fidelities are affected. We then conduct live runs and find that the results reasonably match the simulated results. We also attempt to model the hardware noise by combining a number of noise models, matching the results to results of the live runs to approximate the hardware noise. Our results suggest that the algorithm will perform well for up to 1 % noise under the noise models we chose. We further posit the use of our algorithm as a benchmark for quantum processing units, given that it has a low complexity that is easy to fine-tune in small steps. We provide details for how to do this.
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
Arbitrarily accurate fault-tolerant (FT) universal quantum computation can be carried out using the Clifford gates Z, S, CNOT plus the non-Clifford T gate. Moreover, a recent improvement of the Solovay-Kitaev theorem by Kuperberg implies that to approximate any single-qubit gate to an accuracy of ε>0 requires O(logc[1/ε]) quantum gates with c>1.44042. Can one do better? That was the question asked by Nielsen and Chuang in their quantum computation textbook. Specifically, they posted a challenge to efficiently approximate single-qubit gate, fault-tolerantly or otherwise, using Ω(log[1/ε]) gates chosen from a finite set. Here I give a partial answer to this question by showing that this is possible using O(log[1/ε]loglog[1/ε]logloglog[1/ε]⋯) FT gates chosen from a finite set depending on the value of ε. The key idea is to construct an approximation of any phase gate in a FT way by recursion to any given accuracy ε>0. This method is straightforward to implement, easy to understand, and interestingly does not involve the Solovay-Kitaev theorem.
Clifford+T synthesis of rotation gates is an important routine in fault-tolerant quantum compilation. While Clifford+T synthesis is scalable, it has a high overhead of tens of T gates per rotation in practice, translating to high resource estimates for many fault-tolerant algorithms. However, these well-known results, including those using probabilistic mixtures [Quantum 7, 1208 (2023)], are independent of the rotation angle θ, requiring O(log1/δ) T gates. We show that it is possible to do much better for small angles, reducing the T cost to O~(θ2/δ), and returning to existing O(log1/δ) results in the worst case. This is particularly important since many algorithms, such as Trotterization, are dominated by small-angle rotations. Further, we perform a detailed theoretical and numerical study of quasi-probabilities, which can further reduce the total T cost of large circuits by orders of magnitude with only a small overhead in sample complexity. We also develop a scheme based on quasi-probability mixtures of Clifford+T fallback channels. We derive new θ-dependent formulas that can be used for resource estimation of fault-tolerant quantum algorithms. As an application of our results, we show that the gate cost of Trotterization circuits compiled to a Clifford+T gate set is constant in the small Trotter step size limit, and can be reduced by orders of magnitude even for large step sizes. The cost of fault-tolerant Trotterization for a variety of applications should be re-examined in light of these results. Our work dispels the widely-stated claim that Clifford+T rotation synthesis has a high cost independent of θ, and further develops a scalable quasi-probability method for rotation synthesis. We also expect our results to bring forward useful early fault-tolerant quantum computing by reducing required magic state resources.
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.
We study the resources required to achieve universal quantum computing via the gate sets that provide the fundamental instructions from which quantum algorithms are built. While single-gate universal sets are known, they rely on precisely tuned irrational rotations, making them difficult to realize on near-term devices. We find that the controlled-V gate, an elementary two-qubit interaction directly implementable on leading hardware, is universal and capable of simulating standard universal gate sets with minimal overhead. Specifically, we use catalytic embeddings to develop a constant-overhead algorithm that simulates standard universal gate sets, including Clifford+T and Clifford+Toffoli. We combine this simulation algorithm with existing synthesis results to yield exact and approximate synthesis algorithms for unitaries with and without number-theoretic restrictions. The results highlight how full quantum computational power, complete with algorithms for synthesis and simulation, can emerge from unexpectedly simple ingredients.
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.