We show that a set of gates that consists of all one-bit quantum gates [U(2)] and the two-bit exclusive-OR gate [that maps Boolean values (x,y) to (x,x\ensuremath{\bigoplus}y)] is universal in the sense that all unitary operations on arbitrarily many bits n [U(
2n)] can be expressed as compositions of these gates. We investigate the number of the above gates required to implement other gates, such as generalized Deutsch-Toffoli gates, that apply a specific U(2) transformation to one input bit if and only if the logical and of all remaining input bits is satisfied. These gates play a central role in many proposed constructions of quantum computational networks. We derive upper and lower bounds on the exact number of elementary gates required to build up a variety of two- and three-bit quantum gates, the asymptotic number required for n-bit Deutsch-Toffoli gates, and make some observations about the number required for arbitrary n-bit unitary operations.
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.
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.
In quantum mechanics,the evolution of a quantum state is a unitary evolution,the evolution process can be described by an action of a unitary operator on the quantum state and the process is time reversible.Based on this fundamental fact,Gerard t Hooft has introduced the concept of equivalence classes of quantum states and described the unitary evolutions of quantum states by unitary transformation between two equivalence classes.In the present paper,we will use the concept of equivalence classes and their transformations to construct universal quantum logic gates in the quantum information theory and give their generalized forms.In the end of this paper we will show that these quantum logic gates can be realized by some intrinsic interaction Hamiltonian of the system.
Much of the current understanding of logic gates for quantum computation relies on the application of one- and two-qubit gates in order to implement a universal set of logic gates, as well as other gates. Such ideas stem from the notion that the Hamiltonians available for quantum computation are one or two-body processes. However, present day NMR implementations of quantum information processing (QIP) rely on the internal Hamiltonian of a liquid state system in which there are many two-body processes that occur simultaneously. Such use of the internal Hamiltonian allows for the creation of `multiqubit' logic gates, i.e. logic gates that operate on many qubits simultaneously and are more efficient than a sequence of one- and two-qubit rotations that effect the same operation. Such larger qubit operations offer a universal set of gates (even when not all couplings within the internal Hamiltonian are readily accessible) as well as more convenient and efficient implementations of the Hadamard transform, the controlled-NOT gate, and a quantum Fourier transform that scales linearly (assuming all couplings can be turned on and off at will).