Tailoring many-body interactions among a proper quantum system endows it with computing ability by means of static quantum computation in the sense that some of the physical degrees of freedom can be used to store binary information and the corresponding binary variables satisfy some given logic relations if and only if the system is in the ground state. Two theorems are proved showing that the universal static quantum computer can encode the solutions for any P and NP problem into its ground state using only polynomial number (in the problem input size) of logic gates. The second step is to read out the solutions by relaxing the system. The time complexity is relevant when one tries to read out the solution by relaxing the system, therefore our model of static quantum computation provides a new connection between the computational complexity and the dynamics of a complex system.
Tailoring many-body interactions among a proper quantum system endows it with computing ability by means of static quantum computation in the sense that some of the physical degrees of freedom can be used to store binary information and the corresponding binary variables satisfy some given logic relations if and only if the system is in the ground state. Two theorems are proved showing that the universal static quantum computer can encode the solutions for any P and NP problem into its ground state using only polynomial number (in the problem input size) of logic gates. The second step is to read out the solutions by relaxing the system. The time complexity is relevant when one tries to read out the solution by relaxing the system, therefore our model of static quantum computation provides a new connection between the computational complexity and the dynamics of a complex system.
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.
Superconducting rings with exactly Φ0/2 magnetic flux threading are analogous of Ising spins having two degenerate states which can be used to store binary information. When brought close these rings interact by means of magnetic coupling. If the interactions are properly tailored, a system of such superconducting rings can accomplish static quantum logic in the sense that the states of the rings interpreted as Boolean variables satisfy the desired logic relations when and only when the whole system is in the ground state. Such static logic is essential to carry out the static quantum computation [1,2].
In the last few years, theoretical study of quantum systems serving as computational devices has achieved tremendous progress. We now have strong theoretical evidence that quantum computers, if built, might be used as a dramatically powerful computational tool. This review is about to tell the story of theoretical quantum computation. I left out the developing topic of experimental realizations of the model, and neglected other closely related topics which are quantum information and quantum communication. As a result of narrowing the scope of this paper, I hope it has gained the benefit of being an almost self contained introduction to the exciting field of quantum computation. The review begins with background on theoretical computer science, Turing machines and Boolean circuits. In light of these models, I define quantum computers, and discuss the issue of universal quantum gates. Quantum algorithms, including Shor's factorization algorithm and Grover's algorithm for searching databases, are explained. I will devote much attention to understanding what the origins of the quantum computational power are, and what the limits of this power are. Finally, I describe the recent theoretical results which show that quantum computers maintain their complexity power even in the presence of noise, inaccuracies and finite precision. I tried to put all results in their context, asking what the implications to other issues in computer science and physics are. In the end of this review I make these connections explicit, discussing the possible implications of quantum computation on fundamental physical questions, such as the transition from quantum to classical physics.
The physics and the mathematics of computation are examined to provide a foundation and perspective for the investigation of the quantum mechanics of computation. Our purpose is to explore the fundamental limits and constraints imposed on computation by Nature through the laws of physics and the mathematics of computational complexity. Inasmuch as information storage and transmission are an integral part of computation, their physical bounds are considered. The computer is viewed both physically and mathematically as a dynamical system, and is depicted in terms of the basic Turing machine paradigm. Three fundamental classes of the Turing machine are defined; the deterministic, stochastic and quantum Turing machines. Hamiltonian models and physical realizations of quantum computing are described. Quantum computers can perform some tasks which have no classical analogue, but they cannot compute functions that are non-computable by classical means. Some classically intractable problems can be solved with quantum computers.
Quantum propositional logic, introduced by Birkhoff and von Neumann, formalizes reasoning about experimental propositions in quantum mechanics through closed subspaces of Hilbert spaces. We provide a comprehensive complexity analysis of the satisfiability problem for quantum logic formulas over the connectives conjunction, disjunction, and negation. Distinguishing between weak satisfiability (evaluation to a nonzero subspace) and strong satisfiability (evaluation to the full space), we establish that both notions coincide with Boolean satisfiability for dimension one, are classically NP complete for dimension two, and become complete for the Blum Shub Smale class NP_R when dimension d >= 3 is fixed. Our principal contribution is twofold. First, we present two alternative constructive reductions from quantum logic satisfiability to the Existential Theory of the Reals (ETR): a realification based encoding that explicitly handles the complex to real translation through commutant characterizations, and a rank one column encoding with orthogonal splitting gadgets. Both reductions yield polynomial size systems of quadratic equations for fixed dimension, proving membership in the complexity class existsR and hence in PSPACE via Cannys algorithm. Second, we provide detailed size bounds distinguishing weak and strong satisfiability: weak satisfiability encodes with O(n D^2 + N_v D) scalar variables where n is the number of atoms, D the real dimension, and N_v the number of disjunctions, while strong satisfiability requires O(n D^2 + N_v D^2) variables due to basis vector witnesses. When dimension is part of the input, strong satisfiability becomes polynomial time equivalent to feasibility of noncommutative integer polynomial equations. These results position quantum logic satisfiability precisely between classical NP and existsR, highlighting dimension as a fundamental complexity parameter.
Many-body systems are well known throughout physics to be hard problems to exactly solve, but much of this is folklore resulting from the lack of an analytic solution to these systems. This thesis attempts to classify the complexity inherent in many of these systems, and give quantitative results for why the problems are hard. In particular, we analyze the many-particle system corresponding to a multi-particle quantum walk, showing that the time evolution of such systems on a polynomial sized graph is universal for quantum computation, and thus determining how a particular state evolves is as hard as an arbitrary quantum computation. We then analyze the ground energy properties of related systems, showing that for bosons, bounding the ground energy of the same Hamiltonian with a fixed number of particles is QMA-complete. Similar techniques provide a novel proof that quantum walk is universal for quantum computing, and constructs a QMA-complete problem that does not reference quantum mechanics.