We present a criterion that serves as the basis for a polynomial-time algorithm to decide whether a finite set of qudit gates exponentiated by some Hamiltonians is universal. Our approach formulates universality in Lie algebraic terms and applies Borel--de Siebenthal theory with a diagonal generator having incommensurate spectrum. In this framework, nonuniversality is detected by invariant subspaces, equivalently by a graph-connectivity obstruction, while universality is repaired by adding generators that couple disconnected components. We further prove that two generators are sufficient for universal control. Our work reveals a profound link between qudit universality and irreducibility of Lie algebra representations.
We present a criterion that serves as the basis for a polynomial-time algorithm to decide whether a finite set of qudit gates exponentiated by some Hamiltonians is universal. Our approach formulates universality in Lie algebraic terms and applies Borel--de Siebenthal theory with a diagonal generator having incommensurate spectrum. In this framework, nonuniversality is detected by invariant subspaces, equivalently by a graph-connectivity obstruction, while universality is repaired by adding generators that couple disconnected components. We further prove that two generators are sufficient for universal control. Our work reveals a profound link between qudit universality and irreducibility of Lie algebra representations.
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.
In the conventional theory of quantum computation, universality is discussed in terms of properties of unitary gate sets. In many experimental setups, however, we instead have access to a parametrized set of Hamiltonians, which can be exponentiated for any desired time. Accordingly, we formulate a continuous analogue of universality, where adding one expensive Hamiltonian control to a cheap set of local control operators allows for universal computation. We find several concrete sets of 1- or 2-local Pauli generators S and n-qubit ``magic" Hamiltonians H that together generate the full Lie algebra su(2n), with a special focus on the Ising Hamiltonian J. We propose a method to directly implement any unitary by exponentiating these generator sets, and give bounds on the needed time of application of the magic Hamiltonian H. We find that the number of applications of H needed to approximate any unitary up to accuracy ε scales exponentially in the number of qubits as expected from the standard application of the Solovay-Kitaev theorem. We also find phase transitions in the size of the generated Lie algebras as the parameters of the Ising Hamiltonian are varied. We find an algorithmic application of the Chow/Rashevskii technique to implement unitaries corresponding to iterated commutators.
We establish a relationship between the notion of universal quantum gates and the notion of unitary t-designs. We show that a set of qudit gates $\mathcal{S}\ensuremath{\subset}U(d)$ is universal if and only if S forms a $\ensuremath{\delta}$-approximate t(d)-design, where $\ensuremath{\delta}<1, t(2)=6$, and t(d)=4 for $d\ensuremath{\ge}3$. Moreover, we argue that from the application point of view sets S with the $\ensuremath{\delta}$ close to 1 should be regarded as nonuniversal. We also provide a second, more algebraic, criterion for the universality verification. It says that $\mathcal{S}\ensuremath{\subset}U(d)$ is universal if and only if the matrices that commute with ${{U}^{\ensuremath{\bigotimes}t(d)}\ensuremath{\bigotimes}{\overline{U}}^{\ensuremath{\bigotimes}t(d)}|U\ensuremath{\in}\mathcal{S}}$ commute also with ${{U}^{\ensuremath{\bigotimes}t(d)}\ensuremath{\bigotimes}{\overline{U}}^{\ensuremath{\bigotimes}t(d)}|U\ensuremath{\in}U(d)}$, where t(2)=3, and t(d)=2 for $d\ensuremath{\ge}3$. Finally, we show that the complexity of checking this algebraic criterion scales polynomially with the dimension d.
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 nonuniversality, 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.
Consider a compact connected Lie group G and the corresponding Lie algebra L. Let {X1,...,Xm} be a set of generators for the Lie algebra L. We prove that G is uniformly finitely generated by {X1,...,Xm}. This means that every element K∈G can be expressed as K=eXt1eXt2⋅⋅⋅eXtl, where the indeterminates X are in the set {X1,...,Xm}, $t_i \in \RR$, i=1,...,l, and the number l is uniformly bounded. This extends a previous result by F. Lowenthal in that we do not require the connected one dimensional Lie subgroups corresponding to the Xi, i=1,...,m, to be compact. We discuss the consequence of this result to the question of universality of quantum gates in quantum computing.
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.