Abstract Many quantum algorithms can be written as a composition of unitaries, some of which can be exactly synthesized by a universal fault-tolerant gate set like Clifford+T, while others can be approximately synthesized. One task of a quantum compiler is to synthesize each approximately synthesizable unitary up to some approximation error, such that the error of the overall unitary remains bounded by a certain amount. In this paper we consider the case when the errors are measured in the global phase invariant distance. Apart from deriving a relation between this distance and the Frobenius norm, we show that this distance composes. If a unitary is written as a composition (product and tensor product) of other unitaries, we derive bounds on the error of the overall unitary as a function of the errors of the composed unitaries. Our bound is better than the sum-of-error bound, derived by Bernstein- Vazirani(1997), for the operator norm. This builds the intuition that working with the global phase invariant distance might give us a lower resource count while synthesizing quantum circuits. Next we consider the following problem. Suppose we are given a decomposition of a unitary, that is, the unitary is expressed as a composition of other unitaries. We want to distribute the errors in each component such that the resource-count (specifically T-count) is optimized. We consider the specific case when the unitary can be decomposed such that the R z (θ) gates are the only approximately synthesizable component. We prove analytically that for both the operator norm and global phase invariant distance, the error should be distributed equally among these components (given some approximations). The optimal number of T-gates obtained by using the global phase invariant distance is less than what is obtained using the operator norm. Furthermore, we show that in case of approximate Quantum Fourier Transform, the error obtained by pruning rotation gates is less when measured in this distance, rather than the operator norm.
Abstract Many quantum algorithms can be written as a composition of unitaries, some of which can be exactly synthesized by a universal fault-tolerant gate set like Clifford+T, while others can be approximately synthesized. One task of a quantum compiler is to synthesize each approximately synthesizable unitary up to some approximation error, such that the error of the overall unitary remains bounded by a certain amount. In this paper we consider the case when the errors are measured in the global phase invariant distance. Apart from deriving a relation between this distance and the Frobenius norm, we show that this distance composes. If a unitary is written as a composition (product and tensor product) of other unitaries, we derive bounds on the error of the overall unitary as a function of the errors of the composed unitaries. Our bound is better than the sum-of-error bound, derived by Bernstein- Vazirani(1997), for the operator norm. This builds the intuition that working with the global phase invariant distance might give us a lower resource count while synthesizing quantum circuits. Next we consider the following problem. Suppose we are given a decomposition of a unitary, that is, the unitary is expressed as a composition of other unitaries. We want to distribute the errors in each component such that the resource-count (specifically T-count) is optimized. We consider the specific case when the unitary can be decomposed such that the R z (θ) gates are the only approximately synthesizable component. We prove analytically that for both the operator norm and global phase invariant distance, the error should be distributed equally among these components (given some approximations). The optimal number of T-gates obtained by using the global phase invariant distance is less than what is obtained using the operator norm. Furthermore, we show that in case of approximate Quantum Fourier Transform, the error obtained by pruning rotation gates is less when measured in this distance, rather than the operator norm.
Abstract An important part of reaping computational advantage from a quantum computer is to reduce the quantum resources needed to implement a desired quantum algorithm. Quantum algorithms that are too large to be practical on noisy intermediate scale quantum devices will require fault-tolerant error correction. This work focuses on reducing the physical cost of implementing quantum algorithms when using the state-of-the-art fault-tolerant quantum error correcting codes, in particular, those for which implementing the T gate consumes vastly more resources than the other gates in the gate set. More specifically, in this paper we consider the group of unitaries that can be exactly implemented by a quantum circuit consisting of the Clifford + T gate set. The Clifford + T gate set is a universal gate set and in this group, using state-of-the-art surface codes, the T gate is by far the most expensive component to implement fault-tolerantly. So it is important to minimize the number of T gates necessary for a fault-tolerant implementation. Our primary interest is to compute a circuit for a given n -qubit unitary U , using the minimum possible number of T gates (called the T-count of unitary U ). We consider the problem COUNT-T, the optimization version of which aims to find the T-count of U . In its decision version the goal is to decide if the T-count is at most some positive integer m . Given an oracle for COUNT-T, we can compute a T-count-optimal circuit in time polynomial in the T-count and dimension of U . We give a provable classical algorithm that solves COUNT-T (decision) in time O N 2 ( c − 1 ) ⌈ m c ⌉ p o l y ( m , N ) and space O N 2 ⌈ m c ⌉ p o l y ( m , N ) , where N = 2 n and c ⩾ 2. This gives a space-time trade-off for solving this problem with variants of meet-in-the-middle techniques. We also introduce an asymptotically faster multiplication method that shaves a factor of N 0.7457 off of the overall complexity. Lastly, beyond our improvements to the rigorous algorithm, we give a heuristic algorithm that outputs a T-count-optimal circuit and has space and time complexity poly( m , N ), under some assumptions. In our heuristic algorithm we developed a novel way of pruning the search space. While our heuristic method still scales exponentially with the number of qubits (though with a lower exponent), there is a large improvement by going from exponential to polynomial scaling with m . We implemented our heuristic algorithm with up to 4 qubit unitaries and obtained a significant improvement in time. For all benchmark and random unitaries we studied, the T-count returned by our algorithm is at most the T-count of their circuits shown in previous papers.
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.
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.
Synthesizing arbitrary n-qubit unitaries using as few non-Clifford gates as possible is a central problem in fault-tolerant quantum compilation. We present a Clifford+T quantum circuit construction that approximately implements any classically specified unitary to within error ε and achieves a worst-case T-count with leading exponential scaling of 25n/4 whenever log(1/ε)=poly(n). This improves upon the best previous 24n/3 scaling. The key innovation lies in treating the target unitary as a single block-encoded object rather than a long product of simpler operations. A technique of block flattening controls the normalization while preserving an efficient implementation of the block encoding; subsequently, quantum singular value transformation maps its common singular value to one, thereby recovering the target unitary.
We consider a global phase-invariant distance in the projective unitary group PUn, relevant for universal quantum computing. We obtain the volume and measure of small metric ball in PUn and derive the Gilbert-Varshamov and Hamming bounds in PUn. In addition, we provide upper and lower bounds for the kissing radius of the codebooks in PUn as a function of the minimum distance. Using the lower bound of the kissing radius, we find a tight Hamming bound. Also, we establish bounds on the distortion-rate function for quantizing a source uniformly distributed over PUn. As example codebooks in PUn we consider the projective, Pauli and Clifford groups, as well as the projective group of diagonal gates in the Clifford hierarchy, and find their minimum distances. Finally, we verify the analytical results by simulation.
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.