In this paper we study the universal V-basis gate sets, which have also been shown to be fault tolerant. Our methods and results can be applied to arbitrary dimensional basis gates, but we explicitly state results for basis gates for SU(2) and SU(4). We also include Cliffords, as done in earlier works. We introduce generating sets in order to represent any unitary implementable by these gate sets and with these we derive a bound on the V count of arbitrary multiqubit unitaries. We analyze the channel representation of the generating set elements, with the help of which we infer that none of these basis gates can be implemented exactly with the other universal fault-tolerant gate sets like Clifford+T, Clifford+CS, Clifford+Toffoli. Also T, CS, and Toffoli cannot be exactly implemented in the V basis. In fact, basis unitaries in dimension four cannot be implemented exactly with those in dimension two. We develop V-count-optimal synthesis algorithms for both approximately and exactly implementable multiqubit unitaries. With the help of these we show that two basis unitaries in dimension four are required to implement each basis unitary in dimension two. The space and time complexities of our provable algorithms are exponential in V count. But for the special case of one-qubit unitaries we achieve a complexity that is linear in V count. Both space and time complexities of our heuristic algorithms are polynomial in V count.
In this paper we study the universal V-basis gate sets, which have also been shown to be fault tolerant. Our methods and results can be applied to arbitrary dimensional basis gates, but we explicitly state results for basis gates for SU(2) and SU(4). We also include Cliffords, as done in earlier works. We introduce generating sets in order to represent any unitary implementable by these gate sets and with these we derive a bound on the V count of arbitrary multiqubit unitaries. We analyze the channel representation of the generating set elements, with the help of which we infer that none of these basis gates can be implemented exactly with the other universal fault-tolerant gate sets like Clifford+T, Clifford+CS, Clifford+Toffoli. Also T, CS, and Toffoli cannot be exactly implemented in the V basis. In fact, basis unitaries in dimension four cannot be implemented exactly with those in dimension two. We develop V-count-optimal synthesis algorithms for both approximately and exactly implementable multiqubit unitaries. With the help of these we show that two basis unitaries in dimension four are required to implement each basis unitary in dimension two. The space and time complexities of our provable algorithms are exponential in V count. But for the special case of one-qubit unitaries we achieve a complexity that is linear in V count. Both space and time complexities of our heuristic algorithms are polynomial in V count.
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.
Abstract We study two-qubit circuits over the Clifford+CS gate set, which consists of the Clifford gates together with the controlled-phase gate CS = diag(1, 1, 1, i). The Clifford+CS gate set is universal for quantum computation and its elements can be implemented fault-tolerantly in most error-correcting schemes through magic state distillation. Since non-Clifford gates are typically more expensive to perform in a fault-tolerant manner, it is often desirable to construct circuits that use few CS gates. In the present paper, we introduce an efficient and optimal synthesis algorithm for two-qubit Clifford+CS operators. Our algorithm inputs a Clifford+CS operator U and outputs a Clifford+CS circuit for U, which uses the least possible number of CS gates. Because the algorithm is deterministic, the circuit it associates to a Clifford+CS operator can be viewed as a normal form for that operator. We give an explicit description of these normal forms and use this description to derive a worst-case lower bound of 5log2(ϵ1)+O(1) 5 log 2 ( 1 ϵ ) + O ( 1 ) on the number of CS gates required to ϵ-approximate elements of SU(4). Our work leverages a wide variety of mathematical tools that may find further applications in the study of fault-tolerant quantum circuits.
Fault-tolerant gate sets whose generators belong to the Clifford hierarchy form the basis of many protocols for scalable quantum computing architectures. At the beginning of the decade, number-theoretic techniques were employed to analyze circuits over these gate sets on single qubits, providing the basis for a number of state-of-the-art quantum compiling algorithms. In this dissertation, I further this program by employing number-theoretic techniques for higher-dimensional gate sets on both qudit and multi-qubit circuits. First, I introduce canonical forms for single qutrit Clifford+T circuits and prove that every single-qutrit Clifford+T operator admits a unique such canonical form. I show that these canonical forms are T-optimal and describe an algorithm which takes as input a Clifford+T circuit and outputs the canonical form for that operator. The algorithm runs in time linear in the number of gates of the circuit. Our results provide a higher-dimensional generalization of prior work by Matsumoto and Amano who introduced similar canonical forms for single-qubit Clifford+T circuits. Finally, we show that a similar extension of these normal forms to higher dimensions exists, but do not establish uniqueness. Moving to multi-qubit circuits, I provide number-theoretic characterizations for certain restricted Clifford+T circuits by considering unitary matrices over subrings of Z[1/√2, i]. We focus on the subrings Z[1/2], Z[1/√2], Z[1/√−2], and Z[1/2, i], and we prove that unitary matrices with entries in these rings correspond to circuits over well-known universal gate sets. In each case, the desired gate set is obtained by extending the set of classical reversible gates {X, CX, CCX} with an analogue of the Hadamard gate and an optional phase gate. I then establish the existence and uniqueness of a normal form for one of these gate sets, the two-qubit gate set of Clifford+Controlled Phase gate CS. This normal form is optimal in the number of CS gates, making it the first normal form that is non-Clifford optimal for a fault tolerant universal multi-qubit gate set. We provide a synthesis algorithm that runs in a time linear in the gate count and outputs the equivalent normal form. In proving the existence and uniqueness of the normal form, we likewise establish the generators and relations for the two-qubit Clifford+CS group. Finally, we demonstrate that a lower bound of 5 log2 (1/ε) + O(1) CS gates are required to ε-approximate any 4 × 4 unitary matrix. Lastly, using the characterization of circuits over the Clifford+CS gate set and the existence of an optimal normal form, I provide an ancilla-free inexact synthesis algorithm for two-qubit unitaries using the Clifford+SC gate set for Pauli-rotations. These operators require 6 log2 (1/ε) + O(1) CS gates to synthesize in the typical case and 8 log2 (1/ε) + O(1) in the worst case.
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.
We consider quantum circuits composed of Clifford and T gates. In this context the T gate has a special status since it confers universal computation when added to the (classically simulable) Clifford gates. However it can be very expensive to implement fault-tolerantly. We therefore view this gate as a resource which should be used only when necessary. Given an n-qubit unitary U we are interested in computing a circuit that implements it using the minimum possible number of T gates (called the T-count of U). A related task is to decide if the T-count of U is less than or equal to m; we consider this problem as a function of N=2^n and m. We provide a classical algorithm which solves it using time and space both upper bounded as O(N^m poly(m,N)). We implemented our algorithm and used it to show that any Clifford+T circuit for the Toffoli or the Fredkin gate requires at least 7 T gates. This implies that the known 7 T gate circuits for these gates are T-optimal. We also provide a simple expression for the T-count of single-qubit unitaries.
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.