For numerous applications of quantum theory it is desirable to be able to apply arbitrary unitary operations on a given quantum system. However, in particular situations only a subset of unitary operations is easily accessible. This raises the question of what additional unitary gates should be added to a given gate set in order to attain physical universality, i.e., to be able to perform arbitrary unitary transformation on the relevant Hilbert space. In this work, we study this problem for three paradigmatic cases of naturally occurring restricted gate sets: (A) particle-number preserving bosonic linear optics, (B) particle-number preserving fermionic linear optics, and (C) general (not necessarily particle-number preserving) fermionic linear optics. Using tools from group theory and control theory, we classify, in each of these scenarios, what sets of gates are generated, if an additional gate is added to the set of allowed transformations. This allows us to solve the universality problem completely for arbitrary number of particles and for arbitrary dimensions of the single-particle Hilbert space.
For numerous applications of quantum theory it is desirable to be able to apply arbitrary unitary operations on a given quantum system. However, in particular situations only a subset of unitary operations is easily accessible. This raises the question of what additional unitary gates should be added to a given gate set in order to attain physical universality, i.e., to be able to perform arbitrary unitary transformation on the relevant Hilbert space. In this work, we study this problem for three paradigmatic cases of naturally occurring restricted gate sets: (A) particle-number preserving bosonic linear optics, (B) particle-number preserving fermionic linear optics, and (C) general (not necessarily particle-number preserving) fermionic linear optics. Using tools from group theory and control theory, we classify, in each of these scenarios, what sets of gates are generated, if an additional gate is added to the set of allowed transformations. This allows us to solve the universality problem completely for arbitrary number of particles and for arbitrary dimensions of the single-particle Hilbert space.
In 1994, Reck et al. showed how to realize any linear-optical unitary transformation using a product of beamsplitters and phaseshifters. Here we show that any single beamsplitter that nontrivially mixes two modes, also densely generates the set of m × m unitary transformations (or orthogonal transformations, in the real case) on m ≥ 3 modes. (We prove the same result for any 2-mode real optical gate, and for any 2-mode optical gate combined with a generic phaseshifter.) Experimentally, this means that one does not need tunable beamsplitters or phaseshifters for universality: any nontrivial beamsplitter is universal. Theoretically, it means that one cannot produce “intermediate” models of quantum-optical computation (analogous to the Clifford group for qubits) by restricting the allowed beamsplitters and phaseshifters: there is a dichotomy; one either gets a trivi al set or else a universal set. No similar classification theorem for gates acting on qubits is currently know n. We leave open the problem of classifying optical gates that act on 3 or more modes.
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.
Simulating physical systems on near-term quantum computers often requires preparing states within constrained subspaces, like those with fixed particle number or spin. We use Lie algebraic techniques to prove that hardware-efficient gates are universal for state preparation in these subspaces. The key mechanism is Pauli Z dressing: commutators of overlapping gates produce Pauli Z operators on shared qubits, acting as spectator projectors that decompose multi-plane rotations into single-plane generators spanning the full so(w) algebra, where w is the dimension of the constrained subspace, thereby guaranteeing universality for real state preparation. Adding independent complex phases extends this to su(w), enabling arbitrary complex state preparation. We provide a computationally efficient Jacobian criterion for verifying that a circuit can explore any direction on the target manifold from almost any parameter configuration. Our findings are applicable to many problem areas, including Fermi-Hubbard models, Bose-Hubbard models, and molecular electronic structure. We apply our framework to two physical settings: we prove the completeness of the binary encoded multi-level particles ansatz on the conserved-particle-number subspace, and we construct symmetry-preserving circuits for the fuzzy sphere regularisation of the 3D Ising conformal field theory (CFT). For the latter, we variationally prepare the ground and excited states and extract some CFT data.
Universal gate sets for quantum computing have been known for decades, yet no universal gate set has been proposed for particle-conserving unitaries, which are the operations of interest in quantum chemistry. In this work, we show that controlled single-excitation gates in the form of Givens rotations are universal for particle-conserving unitaries. Single-excitation gates describe an arbitrary U ( 2 ) rotation on the two-qubit subspace spanned by the states | 01 ⟩ , | 10 ⟩ , while leaving other states unchanged – a transformation that is analogous to a single-qubit rotation on a dual-rail qubit. The proof is constructive, so our result also provides an explicit method for compiling arbitrary particle-conserving unitaries. Additionally, we describe a method for using controlled single-excitation gates to prepare an arbitrary state of a fixed number of particles. We derive analytical gradient formulas for Givens rotations as well as decompositions into single-qubit and CNOT gates. Our results offer a unifying framework for quantum computational chemistry where every algorithm is a unique recipe built from the same universal ingredients: Givens rotations.
We examine the following problem: given a collection of Clifford gates, describe the set of unitaries generated by circuits composed of those gates. Specifically, we allow the standard circuit operations of composition and tensor product, as well as ancillary workspace qubits as long as they start and end in states uncorrelated with the input, which rule out common "magic state injection" techniques that make Clifford circuits universal. We show that there are exactly 57 classes of Clifford unitaries and present a full classification characterizing the gate sets which generate them. This is the first attempt at a quantum extension of the classification of reversible classical gates introduced by Aaronson et al., another part of an ambitious program to classify all quantum gate sets. The classification uses, at its center, a reinterpretation of the tableau representation of Clifford gates to give circuit decompositions, from which elementary generators can easily be extracted. The 57 different classes are generated in this way, 30 of which arise from the single-qubit subgroups of the Clifford group. At a high level, the remaining classes are arranged according to the bases they preserve. For instance, the CNOT gate preserves the X and Z bases because it maps X-basis elements to X-basis elements and Z-basis elements to Z-basis elements. The remaining classes are characterized by more subtle tableau invariants; for instance, the T_4 and phase gate generate a proper subclass of Z-preserving gates.
An important result in the theory of quantum control is the "universality" of 2-local unitary gates, i.e. the fact that any global unitary evolution of a system of L qudits can be implemented by composition of 2-local unitary gates. Surprisingly, recent results have shown that universality can break down in the presence of symmetries: in general, not all globally symmetric unitaries can be constructed using k-local symmetric unitary gates. This also restricts the dynamics that can be implemented by symmetric local Hamiltonians. In this paper, we show that obstructions to universality in such settings can in general be understood in terms of superoperator symmetries associated with unitary evolution by restricted sets of gates. These superoperator symmetries lead to block decompositions of the operator Hilbert space, which dictate the connectivity of operator space, and hence the structure of the dynamical Lie algebra. We demonstrate this explicitly in several examples by systematically deriving the superoperator symmetries from the gate structure using the framework of commutant algebras, which has been used to systematically derive symmetries in other quantum many-body systems. We clearly delineate two different types of non-universality, which stem from different structures of the superoperator symmetries, and discuss its signatures in physical observables. In all, our work establishes a comprehensive framework to explore the universality of unitary circuits and derive physical consequences of its absence.