This thesis covers the topic of Quantum Computation, in both its theoretical and experimental aspects. The Theory of Quantum Computing is an extension of the standard Theory of Computation inspired by the principles of Quantum Mechanics. The discovery of efficient quantum algorithms for problems for which no efficient classical algorithms are known challenges the Strong Church-Turing Thesis, which states that all computational models are essentially equivalent in terms of what they can compute and how efficiently they can do so.
In Part I of this thesis, we study the nature of this difference. We first introduce a general and simplified framework for characterising the essence of a quantum theory, in contrast with a deterministic or a probabilistic theory. We put forth the thesis that the most fundamental axioms are those related to measurement, from which these differences emanate. We cover some variations on these theories, and show some interesting structural relationships between them. For example, the only models which can be simultaneously quantum and probabilistic are the deterministic ones.
We then use this meta-model to re-introduce in a succinct and uniform manner the deterministic, probabilistic and quantum versions of the Turing Machine and circuit computational models. Moreover, we generalise the circuit model on arbitrary semirings. We thus succeed in providing a new classification of existing complexity classes by varying the semirings and vector norms with which their vector space of states is defined. In particular, the standard models of deterministic, probabilistic, and quantum computing can be characterised (with the same norm) by defining circuits on the boolean algebra, the positive rational or reals, and the rational or reals, respectively. We further explore this model with other non-standard semirings. We show that quaternion based models are equivalent to quantum computation. Finally, we strengthen this “algebraic hierarchy” by using the tensor formula formalism to construct a family of complete (or promise complete) problems for the corresponding complexity classes.
Part II concerns experimental Quantum Computing by Nuclear Magnetic Resonance (NMR). An important obstacle in this approach is the inability to properly initialise the quantum register, which is related to the signal-to-noise problem in NMR spectroscopy. One of the most promising techniques to solve it is Algorithmic Cooling, a generalisation of the polarisation transfer techniques already used by NMR spectroscopists. We discuss the traditional adiabatic approaches and their limitations. We describe a variation on this technique, the non-adiabatic approach, which uses the environment in order to cool beyond these limits. In particular, we provide a new, efficient non-adiabatic cooling algorithm which could achieve near-zero spin temperatures in liquid-state NMR already with more reasonably sized registers (30–60 spins). Finally, we report on the successful laboratory realisation of the first ever non-adiabatic cooling experiment. This constitutes, we hope, the first step towards the fully fledged development of this promising technique, with applications far beyond NMR-based Quantum Computing.
The rapid evolution of computers in the half century since their invention has resulted in dramatically smaller and faster computers. However, from a computational point of view, all these computers look alike; for example, they are built out of simple logic gates. A fundamental thesis of computer science---the modern form of the Church--Turing thesis---asserts that this is inevitable in a deep sense. Any computer can be simulated with at most a polynomial factor slowdown by a probabilistic Turing machine. Quantum computation poses the first credible challenge to this thesis. It goes back to a suggestion by Feynman [4], who pointed out that there appears to be no efficient way of simulating a quantum mechanical system on a computer, and suggested that, perhaps, a computer based on quantum physical principles might be able to carry out the simulation efficiently. Two formal models for quantum computers---the quantum Turing machine [2] and quantum computational networks [3]---were defined by Deutsch. The first three papers in this issue describe efficient quantum algorithms for computational tasks that we do not know how to solve classically. In "Quantum Complexity Theory," Bernstein and Vazirani give the first formal evidence that quantum computers violate the modern form of the Church--Turing thesis. They show that a certain problem---the recursive Fourier sampling problem---can be solved in polynomial time on a quantum Turing machine, but relative to an oracle, requires superpolynomial time on a classical probabilistic Turing machine. Simon, in the paper "On the Power of Quantum Computation" introduces a fundamental projection technique and uses it to design an efficient quantum algorithm to determine whether a certain type of function is 2-1 or 1-1. He further shows that, relative to an oracle, this problem requires exponential time on a classical probabilistic Turing machine. In the paper "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer," Shor gives remarkable polynomial time quantum algorithms for two of the most famous problems in computer science: factoring and discrete log. Since the computational hardness of these problems is the basis of several famous cryptosystems, Shor's paper very dramatically underlines the power of quantum computers. To understand the computational power of quantum computers, it is helpful to consider a quantum mechanical system of n particles, each of which can be in one of two states, labeled
∣0⟩ and
∣1⟩. If this were a classical system, then its instantaneous state could be described by n bits. However, in quantum physics, the system is allowed to be in a linear superposition of configurations, and indeed the instantaneous state of the system is described by a unit vector in the 2n dimensional vector space, whose basis vectors correspond to all the2n classical configurations. Therefore, to describe the instantaneous state of the system, we must specify 2n complex numbers. Nature must update 2n complex numbers at each instant to evolve the system in time. This is an extraordinary amount of effort, since even for n = 200, 2n is larger than estimates of the number of elementary particles in the visible universe. Nonetheless, there are limits to the power of quantum computers. In "Strengths and Weaknesses of Quantum Computing," Bennett, Bernstein, Brassard, and Vazirani show that, relative to a random oracle, with probability 1, the class NP cannot be solved on a quantum Turing machine in time o(2n/2). This bound is tight, since recent work of Grover [5] has shown how to accept any language in NP in time O(2n/2) on a quantum Turing machine. Quantum computers are necessarily time reversible. Indeed, Bennett's work [1] on reversible computation inspired early work on quantum computation that preceded Feynman's paper [4]. The reversibility requirement makes it quite complex to implement even basic computational primitives such as looping or composition. In "Quantum Complexity Theory," Bernstein and Vazirani show how to implement quantum programming primitives and give a construction for an efficient universal quantum Turing machine. The structure of the universal quantum Turing machine is quite simple: it consists of a deterministic Turing machine with a single "quantum coin flip." In "Quantum Computability," Adleman, DeMarrais, and Huang greatly simplify this further by showing that a very simple type of coin flip is sufficient---a rotation by an angle
θ such that
sinθ=3/5. Making quantum computers robust against noise and decoherence is an important and challenging problem. In "Stabilization of Quantum Computations by Symmetrization," Barenco, Berthiaume, Deutsch, Ekert, Jozsa, and Macchiavello show how to use the quantum watchdog effect to stabilize a quantum computation against noise. Their method is based on running several copies of the quantum computer in parallel and projecting its state into the symmetric subspace at frequent intervals. They show that the quantum watchdog effect results in the suppression of errors that lie outside the symmetric subspace. Quantum computation touches upon the foundations of both computer science and quantum physics. It is not unlikely that the issues raised by quantum computation will stimulate further research into the foundations of quantum physics. I wish to express my gratitude to several people who made this special section possible. Oded Goldreich acted as editor for two of the papers in the issue and dealt with them with his characteristic efficiency and judgment. The editorial staff at SIAM, most notably Lisa Dougherty, Beth Gallagher, Deidre Wunderlich, and Sam Young, were extremely helpful, patient, and resourceful. Finally, I would like to thank a number of referees whose careful and timely reviews were critical to putting together this issue. Umesh Vazirani
In this paper, we show the following two results on the relationships between quantum computers and NP-complete problems. First, we develop a theory of bulk quantum computation such as NMR (Nuclear Magnetic Resonance) quantum computation. For this purpose, we first define bulk quantum Turing machine (BQTM for short) as a model of bulk quantum computation. Then, we show that BQTMs can solve certain instances of NP-complete problems efficiently. Next, we show that the algorithm designed by Abrams and Lloyd can be simulated by a deterministic Turing machine in polynomial space. This suggests that their algorithm, which is based on non-standard quantum mechanics, can be simulated by a standard QTM with exponential time slow down.
This work presents a comprehensive and rigorous examination of quantum computing, spanning its mathematical foundations, physical principles, algorithmic developments, hardware architectures, and philosophical implications. Beginning with linear algebra over Hilbert spaces and the postulates of quantum mechanics, the manuscript develops the formal structure of quantum information theory, including qubits, entanglement, quantum channels, and noise models. The work provides in-depth treatments of the quantum circuit model, alternative computation paradigms such as measurement-based, adiabatic, and topological quantum computation, and the theoretical framework of quantum error correction, including stabilizer and surface codes. Foundational and modern quantum algorithms are analysed in detail, including Shor’s factoring algorithm, Grover’s search, variational quantum eigensolvers, QAOA, and emerging quantum machine learning approaches. Beyond algorithms and implementations, the manuscript addresses scalability challenges, fault tolerance, computational complexity limits, and the implications of quantum computing for cryptography and the extended Church–Turing thesis. The concluding sections explore philosophical questions concerning interpretation, measurement, and the relationship between computation and physical reality. This work is intended as both a reference text and a research-level synthesis for advanced students, researchers, and practitioners in quantum computing, theoretical computer science, and quantum physics.
In this paper we study quantum computation from a complexity theoretic viewpoint. Our first result is the existence of an efficient universal quantum Turing machine in Deutsch's model of a quantum Turing machine (QTM) [Proc. Roy. Soc. London Ser. A, 400 (1985), pp. 97--117]. This construction is substantially more complicated than the corresponding construction for classical Turing machines (TMs); in fact, even simple primitives such as looping, branching, and composition are not straightforward in the context of quantum Turing machines. We establish how these familiar primitives can be implemented and introduce some new, purely quantum mechanical primitives, such as changing the computational basis and carrying out an arbitrary unitary transformation of polynomially bounded dimension. We also consider the precision to which the transition amplitudes of a quantum Turing machine need to be specified. We prove that
O(logT) bits of precision suffice to support a T step computation. This justifies the claim that the quantum Turing machine model should be regarded as a discrete model of computation and not an analog one. We give the first formal evidence that quantum Turing machines violate the modern (complexity theoretic) formulation of the Church--Turing thesis. We show the existence of a problem, relative to an oracle, that can be solved in polynomial time on a quantum Turing machine, but requires superpolynomial time on a bounded-error probabilistic Turing machine, and thus not in the class $\BPP$. The class $\BQP$ of languages that are efficiently decidable (with small error-probability) on a quantum Turing machine satisfies $\BPP \subseteq \BQP \subseteq \Ptime^{\SP}$. Therefore, there is no possibility of giving a mathematical proof that quantum Turing machines are more powerful than classical probabilistic Turing machines (in the unrelativized setting) unless there is a major breakthrough in complexity theory.
There is strong evidence that computers based upon the principles of quantum physics represent an inherently new and more powerful model of computation. Such computers violate the modern form of the Church-Turing thesis (which lies at the foundations of computer science). This thesis can be informally summarized as follows: all physical implementations of computing devices can be described by the same abstract model of computation-the probabilistic Turing Machine or the equivalent random access machine. In this paper, we will describe two formal models for quantum computers: quantum circuits and quantum Turing Machines, introduced by Deutsch [1985].
This chapter introduces the basic principles of quantum computation. We shall adhere to the quantum circuit model of computation, with which it is easy to work and which is close to physical implementations. We shall not discuss the more abstract quantum Turing machine model, which, however, has been shown to be equivalent to the circuit model. The elementary unit of quantum information and the basic building block of quantum computation is the qubit, a two-level quantum system that can be prepared, manipulated and measured in a controlled way. A quantum computer can be seen as a collection of n qubits and therefore its wave function resides in a 2 n -dimensional complex Hilbert space. As far as coupling to the environment may be neglected, its evolution in time is unitary and governed by the Schrödinger equation. A quantum computation is composed of three basic steps: preparation of the input state, implementation of the desired unitary transformation acting on this state and measurement of the output state. The output of the measurement process is inherently probabilistic and the probabilities of the different possible outputs are set by the basic postulates of quantum mechanics. Therefore, in a quantum algorithm we must, in general, repeat several times the algorithm to obtain the correct solution of our problem with probability as close to one as desired. In this sense, quantum algorithms are analogous to classical probabilistic algorithms. However, the superposition principle and quantum entanglement open up new possibilities for computation. Quantum computers are potentially more powerful than classical (deterministic or probabilistic) computers due to quantum interference and entanglement. We show that, analogously to classical computation, there exists a small set of gates that are universal, that is, any unitary transformation can be decomposed into a sequence of these gates. We then discuss the implementation of the basic Boolean functions and arithmetic operations on a quantum computer.