If you progressed up to this point, it should be easy for you to make the quantum leap. Several steps we've already made prepared the ground to discuss Quantum Computing. In previous chapters, we introduced the representation of bits as vectors in a vector space, and we generalized from two to a continuum of possible values, introducing concepts and notations that will ease our understanding. Now we will see what a quantum system is, then what a quantum computer is. We will see that quantum computations admit greater relativity of computation and have greater ambiguity than classical computations.
If you progressed up to this point, it should be easy for you to make the quantum leap. Several steps we've already made prepared the ground to discuss Quantum Computing. In previous chapters, we introduced the representation of bits as vectors in a vector space, and we generalized from two to a continuum of possible values, introducing concepts and notations that will ease our understanding. Now we will see what a quantum system is, then what a quantum computer is. We will see that quantum computations admit greater relativity of computation and have greater ambiguity than classical computations.
In everyday life, practically all the information which is processed, exchanged or stored is coded in the form of discrete entities called bits , which take two values only, by convention 0 and 1. With the present technology for computers and optical fibers, bits are carried by electrical currents and electromagnetic waves corresponding to macroscopic fluxes of electrons and photons, and they are stored in memories of various kinds, for example, magnetic memories. Although quantum physics is the basic physics which underlies the operation of a transistor (Chapter 6) or of a laser (Chapter 4), each exchanged or processed bit corresponds to a large number of elementary quantum systems, and its behavior can be described classically due to the strong interaction with the environment (Chapter 9). For about thirty years, physicists have learned to manipulate with great accuracy individual quantum systems: photons, electrons, neutrons, atoms, and so forth, which opens the way to using two-state quantum systems, such as the polarization states of a photon (Chapter 2) or the two energy levels of an atom or an ion (Chapter 4) in order to process, exchange or store information. In § 2.3.2, we used the two polarization states of a photon, vertical ( V ) and horizontal ( H ), to represent the values 0 and 1 of a bit and to exchange information. In what follows, it will be convenient to use Dirac’s notation (see Appendix A.2.2 for more details), where a vertical polarization state is denoted by | V 〉 or |0〉 and a horizontal one by | H 〉 or |1〉, while a state with arbitrary polarization will be denoted by |ψ〉. The polarization states of a photon give one possible realization of a quantum bit , or for short a qubit . Thanks to the properties of quantum physics, quantum computers using qubits, if they ever exist, would outperform classical computers for some specific, but very important, problems. In Sections 8.1 and 8.2, we describe some typical quantum algorithms and, in order to do so, we shall not be able to avoid some technical developments. However, these two sections may be skipped in a first reading, as they are not necessary for understanding the more general considerations of Sections 8.3 and 8.4.
Summary form only given, as follows. Gives a system theoretic approach to the concept of quantum computing. A quantum computer is envisaged to be a system of quantum circuits, acting on a state space, which is a finite-say 2/sup n/-dimensional-complex Hilbert space. The circuitry is a sequence of unitary transforms U/sub t/ /spl epsiv/ SU(2/sup n/) followed by a measurement. These transforms, so-called quantum gates, are controlled by a classical computer, usually especially electromagnetic fields. The state space of a quantum computer has the structure of a Hermitian vector space. Thus it allows "simultaneous" superposition of orthogonal basis states (corresponding to classical states) with the possibility of constructive and destructive interference between different paths of computation. This principle allows the usage of so-called entangled states by preparing the superposition of special "bent" configurations of basis vectors in the product Hilbert space, e.g., as they are known from error control and cryptography. This latter "entanglement" not only promises to make a quantum computer much more powerful than a probabilistic one, but it also allows a method of parallelism. The reason for this lies not only in the fact that the 2/sup n/ dimensional Hilbert space is the n-fold tensor product of 2-dimensional spaces as it is given by spin-1/2-particles, like photons, representing a quantum bit. First of all, we shall address the fact that the power of quantum computing lies in the properties of entangled states as opposed to those of separable states which essentially would resemble classical circuits without giving the feature of exponential speed-up. We shall briefly describe possible physical realisations of quantum (optic, electronic, magnetic,...) devices allowing the engineering of Hamiltonians needed for quantum systems. Basic quantum gates, especially the quantum Horner-Toffoli gate will be discussed to display the principles and methodology for designing quantum circuits. An outlook towards the possible availability of nano- and mesoscopic technologies supporting this new architecture in future generations concludes based on a speculative worst/best case forecast of possible applications, e.g., in public key and conventional cryptography.
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.
Abstract With this chapter, we begin to transit from digital information processing to quantum information processing. However, to be able to master this transition, we first need to familiarize ourselves with quantum mechanical principles and the mathematics used to describe them. Since we already know about abstract state spaces, tensor products, and Hamiltonian operators and their eigenvectors and eigenvalues, this should not be too difficult or too alien. And yet, there remain a few challenges: Mathematical descriptions of quantum states usually involve the Dirac notation, require complex linear algebra in high dimensional spaces, and encode unintuitive probabilistic interpretations. Rising to these challenges, we briefly study the notion of Hilbert spaces, introduce the Dirac notation, and discuss the axioms of quantum mechanics and some of their consequences. All this will admittedly be dense and abstract but prepare us for everything that is still to follow. Our main goal is to emphasize that quantum mechanics and therefore quantum computing is just complex linear algebra in very high dimensional spaces so that quantum computing needs a different kind of thinking than we are used to in digital computing.
Abstract After a quick review of Chapter 2’s bits and gates, Bob and Alice introduce Cardy to several concepts and symbolic representations that will be of crucial importance in understanding quantum computing: state vectors, pictorial representations of state vectors, and simple mathematical forms that help us manipulate and reason about state vectors. State vectors may be represented by arrows in a state space diagram. States may also be represented more abstractly using Dirac notation symbols |⟩. Logic gates, critically important for carrying out computational work, can be represented by mathematical objects called matrices. States are represented by column vectors. Everything you need to know about matrices is presented over just a few pages.