When can a quantum system of finite dimension be used to simulate another quantum system of finite dimension? What restricts the capacity of one system to simulate another? In this paper we complete the program of studying what simulations can be done with entangling many-qudit Hamiltonians and local unitary control. By entangling we mean that every qudit is coupled to every other qudit, at least indirectly. We demonstrate that the only class of finite-dimensional entangling Hamiltonians that are not universal for simulation is the class of entangling Hamiltonians on qubits whose Pauli operator expansion contains only terms coupling an odd number of systems, as identified by Bremner et al. [Phys. Rev. A 69, 012313 (2004)]. We show that in all other cases entangling many-qudit Hamiltonians are universal for simulation.
When can a quantum system of finite dimension be used to simulate another quantum system of finite dimension? What restricts the capacity of one system to simulate another? In this paper we complete the program of studying what simulations can be done with entangling many-qudit Hamiltonians and local unitary control. By entangling we mean that every qudit is coupled to every other qudit, at least indirectly. We demonstrate that the only class of finite-dimensional entangling Hamiltonians that are not universal for simulation is the class of entangling Hamiltonians on qubits whose Pauli operator expansion contains only terms coupling an odd number of systems, as identified by Bremner et al. [Phys. Rev. A 69, 012313 (2004)]. We show that in all other cases entangling many-qudit Hamiltonians are universal for simulation.
When can one quantum system be used to simulate another? What aspects of a quantum system restrict its capacity to simulate other systems? Understanding the limitations and possibilities of such simulations is a key issue at the intersection of physics and computer science. In this thesis we determine what physical systems can be simulated by finite-dimensional quantum systems with entangling Hamiltonians and complete local unitary control. By an entangling Hamiltonian we mean each of the system's subsystems are coupled, either directly or indirectly. This very broad class of Hamiltonians is applicable to a wide range of important physical systems in Nature.Our key motivation for studying such simulation problems is quantum computing. It can be shown that a locally controllable Hamiltonian system must be entangling if it is to be used to make a quantum computer. By characterizing the simulation properties of entangling Hamiltonian systems, we identify necessary (and in some cases sufficient) properties for such systems to be used in the implementation of a quantum computer.We perform our categorization of entangling Hamiltonian systems by determining the Lie algebras they can generate with local unitary control. We find that the key to this categorization is given by simple properties of the structure of the system Hamiltonian. Our main result is a complete characterization of all entangling Hamiltonian systems based on the set of Hamiltonians that they can generate with local unitary control.
What interactions are sufficient to simulate arbitrary quantum dynamics in a composite quantum system? Dodd et al. [Phys. Rev. A 65, 040301(R) (2002)] provided a partial solution to this problem in the form of an efficient algorithm to simulate any desired two-body Hamiltonian evolution using any fixed two-body entangling N-qubit Hamiltonian, and local unitaries. We extend this result to the case where the component systems are qudits, that is, have D dimensions. As a consequence we explain how universal quantum computation can be performed with any fixed two-body entangling N-qudit Hamiltonian, and local unitaries.
What interactions are sufficient to simulate arbitrary quantum dynamics in a composite quantum system? It has been shown that all two-body Hamiltonian evolutions can be simulated using any fixed two-body entangling n-qubit Hamiltonian and fast local unitaries. By entangling we mean that every qubit is coupled to every other qubit, if not directly, then indirectly via intermediate qubits. We extend this study to the case where interactions may involve more than two qubits at a time. We find necessary and sufficient conditions for an arbitrary n-qubit Hamiltonian to be dynamically universal, that is, able to simulate any other Hamiltonian acting on n qubits, possibly in an inefficient manner. We prove that an entangling Hamiltonian is dynamically universal if and only if it contains at least one coupling term involving an even number of interacting qubits. For odd entangling Hamiltonians, i.e., Hamiltonians with couplings that involve only an odd number of qubits, we prove that dynamic universality is possible on an encoded set of $n\ensuremath{-}1$ logical qubits. We further prove that an odd entangling Hamiltonian can simulate any other odd Hamiltonian and classify the algebras that such Hamiltonians generate. Thus, our results show that up to local unitary operations, there are only two fundamentally different types of entangling Hamiltonian on n qubits. We also demonstrate that, provided the number of qubits directly coupled by the Hamiltonian is bounded above by a constant, our techniques can be made efficient.
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.
Abstract A family of quantum Hamiltonians is said to be universal if any other finite-dimensional Hamiltonian can be approximately encoded within the low-energy space of a Hamiltonian from that family. If the encoding is efficient, universal families of Hamiltonians can be used as universal analogue quantum simulators and universal quantum computers, and the problem of approximately determining the ground-state energy of a Hamiltonian from a universal family is QMA-complete. One natural way to categorise Hamiltonians into families is in terms of the interactions they are built from. Here we prove universality of some important classes of interactions on qudits (d-level systems): We completely characterise the k-qudit interactions which are universal, if augmented with arbitrary Hermitian 1-local terms. We find that, for all k⩾2 k ⩾ 2 and all local dimensions d⩾2 d ⩾ 2 , almost all such interactions are universal aside from a simple stoquastic class. We prove universality of generalisations of the Heisenberg model that are ubiquitous in condensed-matter physics, even if free 1-local terms are not provided. We show that the SU(d) and SU(2) Heisenberg interactions are universal for all local dimensions d⩾2 d ⩾ 2 (spin ⩾1/2 ⩾ 1 / 2 ), implying that a quantum variant of the Max-d-Cut problem is QMA-complete. We also show that for d=3 d = 3 all bilinear-biquadratic Heisenberg interactions are universal. One example is the general AKLT model. We prove universality of any interaction proportional to the projector onto a pure entangled state.
Any quantum computation consists of a sequence of unitary evolutions described by a finite set of Hamiltonians. For the case where this set consists of only products of Pauli operators, known as Pauli strings, we provide a necessary and sufficient condition for it to generate su(2n), i.e., to be universal for quantum computation on n qubits. When combining Pauli strings with a general Hamiltonian, we show a sufficient (and in certain circumstances even necessary) condition for universality based on the Pauli-basis expansion of the Hamiltonian. As an application of these results, we prove two corollaries: (i) a necessary and sufficient condition for the universality of a general Hamiltonian given arbitrary single-qubit control on all qubits, and (ii) the universality of an XYZ Heisenberg Hamiltonian with local control of just two adjacent qubits.