A well-known theorem states that the Clifford+T gate set is universal for quantum computing. The theorem combines approximation using a distance measure on unitary matrices with equality up to global phase. Previous proofs combine these two notions for specific distance measures, but do not identify the properties that govern how they work together. Which properties are sufficient to state and prove the theorem?
We answer this question by defining projective distance measures using four axioms. We prove that the universality theorem holds for every distance measure satisfying these axioms. Thus, our formulation of the theorem is independent of any particular choice of distance measure. We show that the Hilbert-Schmidt distance is already a projective distance measure. We also develop a general construction that transforms a large class of distance measures into projective distance measures and apply it to obtain projective versions of the operator-norm distance, the Frobenius distance, and the trace distance. Finally, we formalize the proof of the universality theorem in Lean.
AI Summary
The paper asks which properties of a distance measure suffice to formulate and prove Clifford+$T$ universality while identifying unitaries that differ only by global phase. It defines a projective distance measure through four axioms: zero self-distance, invariance under independent global phases, subadditivity under multiplication, and continuity along Hermitian-generated one-parameter unitary families. Symmetry and separation of distinct projective unitaries are not required.
The main theorem states that, for every such measure $d$, every $n$-qubit unitary $U$, and every $\epsilon>0$, a circuit $C$ over $\{\mathrm{CX},H,T\}$ exists with $d(U,C)<\epsilon$. The proof combines an exact Clifford+$R_z$ decomposition up to global phase with approximation of arbitrary $R_z$ rotations. The latter uses two Clifford+$T$-derived rotations about orthogonal axes, generalized Euler decomposition, irrationality of their rotation angle, and density of positive-integer powers. Subadditivity distributes the error budget across substituted gates. The exact decomposition uses $O(4^n)$ gates; no approximation-length or $T$-count bound is supplied.
The normalized trace-overlap distance $\sqrt{1-|\operatorname{Tr}(U^\dagger V)/2^n|^2}$ satisfies the axioms directly. For a broader class of distances, the paper proves that phase minimization, $\widehat d(U,V)=\min_\theta d(U,e^{i\theta}V)$, produces a projective distance measure, including projective versions of operator-norm, Frobenius, and trace-norm distances. Compactness establishes existence of the minimizing phase. The universality proof is also formalized in Lean.
Little sign of AI-generated textAI use disclosedIncrementalUnclear novelty
We used AI to help convince ourselves that the gate $G_1$ is a good choice for our proof, write drafts of some of the cases of the proofs in the appendices
Error found: The universality proof unjustifiably uses single-qubit approximation errors to bound n-qubit circuit error, although the axioms impose no compatibility across dimensions and the stated Frobenius and trace examples acquire dimension-dependent factors under embedding.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
A well-known theorem states that the Clifford+T gate set is universal for quantum computing. The theorem combines approximation using a distance measure on unitary matrices with equality up to global phase. Previous proofs combine these two notions for specific distance measures, but do not identify the properties that govern how they work together. Which properties are sufficient to state and prove the theorem?
We answer this question by defining projective distance measures using four axioms. We prove that the universality theorem holds for every distance measure satisfying these axioms. Thus, our formulation of the theorem is independent of any particular choice of distance measure. We show that the Hilbert-Schmidt distance is already a projective distance measure. We also develop a general construction that transforms a large class of distance measures into projective distance measures and apply it to obtain projective versions of the operator-norm distance, the Frobenius distance, and the trace distance. Finally, we formalize the proof of the universality theorem in Lean.
The paper asks which properties of a distance measure suffice to formulate and prove Clifford+T universality while identifying unitaries that differ only by global phase. It defines a projective distance measure through four axioms: zero self-distance, invariance under independent global phases, subadditivity under multiplication, and continuity along Hermitian-generated one-parameter unitary families. Symmetry and separation of distinct projective unitaries are not required.
The main theorem states that, for every such measure d, every n-qubit unitary U, and every ϵ>0, a circuit C over {CX,H,T} exists with d(U,C)<ϵ. The proof combines an exact Clifford+Rz decomposition up to global phase with approximation of arbitrary Rz rotations. The latter uses two Clifford+T-derived rotations about orthogonal axes, generalized Euler decomposition, irrationality of their rotation angle, and density of positive-integer powers. Subadditivity distributes the error budget across substituted gates. The exact decomposition uses O(4n) gates; no approximation-length or T-count bound is supplied.
The normalized trace-overlap distance 1−∣Tr(U†V)/2n∣2 satisfies the axioms directly. For a broader class of distances, the paper proves that phase minimization, d(U,V)=minθd(U,eiθV), produces a projective distance measure, including projective versions of operator-norm, Frobenius, and trace-norm distances. Compactness establishes existence of the minimizing phase. The universality proof is also formalized in Lean.
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 In this chapter, we describe the circuit model of quantum computation, focusing on the initialization of a set of qubits, their unitary evolution, and final projective measurement. We outline Di Vincenzo’s criteria for constructing a functional quantum computer. We describe single-qubit gates and measurements, and we present two-qubit gates. We prove that single-qubit gates and a particular two-qubit gate, the CNOT gate, are universal for quantum computation. In the last part of the chapter, we present the Clifford group of unitary transformations that stabilize the Pauli group, and the Gottesman-Knill theorem.
We consider the problem of deciding if a set of quantum one-qudit gates S={g1,…,gn}⊂G is universal, i.e. if <S> is dense in G, where G is either the special unitary or the special orthogonal group. To every gate g in S we assign the orthogonal matrix Adg that is image of g under the adjoint representation Ad:G→SO(g) and g is the Lie algebra of G. The necessary condition for the universality of S is that the only matrices that commute with all Adgi ’s are proportional to the identity. If in addition there is an element in <S> whose Hilbert–Schmidt distance from the centre of G belongs to ]0,21[ , then S is universal. Using these we provide a simple algorithm that allows deciding the universality of any set of d-dimensional gates in a finite number of steps and formulate a general classification theorem.
A quantum computer is similar to an ordinary computer, except that instead of bits it uses two-level quantum systems (qubits), and the usual logical operations on bits are replaced with noiseless quantum dynamics in the form of unitary gates or Hamiltonian interactions. Many sets of resources that are universal for quantum computation (that is, capable of implementing any quantum computation) have been found, but general conditions for universality are still only partially understood. Improving our understanding of these conditions contributes to two broad goals. On the one hand, understanding what class of physical systems is suitable for quantum computation allows us choose the systems that are most easily controlled or built in the laboratory. On the other hand, identifying the unifying characteristics of such a class provides insight into the fundamental physics responsible for the much greater computational power of quantum computers. The original results presented in this thesis are a contribution to our understanding of the physical requirements for universal quantum computation. These results lead to the identification of a new, large class of universal dynamics. More specifically, the main problem that is addressed is the following: consider a physical system that is made up of a finite number of qubits that are subject to a natural, fixed interaction described by a two-body Hamiltonian. Suppose we have the ability to control the system only by applying fast one-qubit operations. Under what conditions is this system capable of universal quantum computation? The first original result of the thesis is to prove that universal quantum computation is possible under these conditions given the single extra constraint that the Hamiltonian must entangle, or connect, all of the qubits. In other words, since a two-body Hamiltonian is expressible as a sum of coupling terms each of which acts nontrivially on a pair of qubits, consider the graph whose vertices correspond to qubits and whose edges connect qubits that are coupled by a term in the Hamiltonian. Then this Hamiltonian, together with fast one-qubit unitaries, is universal for quantum computation precisely when the corresponding graph is connected. This result suggests many potential generalizations, three of which are explored in this thesis. The first generalization is to show that the same result holds for a two-body Hamiltonian that acts on D-dimensional quantum systems (qudits), given fast one-qudit unitaries. A second extension is to the case of a many-body Hamiltonian, that is, a Hamiltonian that has coupling terms that act on more than two qubits. Again, we find that under mild restrictions, such Hamiltonians are universal provided they are connected and that arbitrary one-qubit unitaries are available. We also discover and explore some surprising structure in many-body Hamiltonians that is associated with the parity of the couplings. A third related problem that is addressed is the question of what two-qubit unitaries are universal for quantum computation. This problem was originally solved by J.-L. and R. Brylinski [BB02], who gave a technical proof of the universality of any two-qudit gate that is not the swap gate or a product of one-qudit unitaries, given one-qudit unitaries as a free resource. We develop an elementary and constructive proof for the case of qubits, and prove that our construction is very close to optimal in the number of uses of the two-qubit gate. Given a qualitative understanding of what dynamical resources are universal for quantum computation, it is natural to consider developing a quantitative measure of the usefulness of quantum dynamics for quantum information processing. This is done in the final chapter of the thesis, in which the beginnings of a quantitative theory of quantum dynamics are developed.
We show that single-qudit universality in Clifford-based gate sets follows a trichotomy determined by the prime factorization of the local dimension d. For prime d, any gate outside the Clifford group is universal. For prime-power dimensions d=pm with m≥2, not every non-Clifford gate is universal, but it can be achieved by suitable members of a family of diagonal phase gates, generalizing the qubit T gate, as well as by permutations as simple as swapping ∣0⟩ and ∣1⟩ while leaving all other basis states unchanged. When d decomposes into pairwise coprime prime powers, generalized CNOT-type gates between the corresponding factors already suffice for universality. In this composite case, universality can be obtained without introducing an explicit diagonal magic gate. Our results split non-Clifford resources for high-dimensional systems into two broad mechanisms: CNOT-type (permutations) or T-type (diagonal phases) gates.
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.