Principles of Quantum Computation and Information

The following sections are included:

• Dedication
• About the Cover
• Preface
• Contents

Since its dawn at the beginning of the twentieth century, quantum mechanics has had an outstanding technological and societal impact. To appreciate this fact, it is sufficient to consider the invention of the transistor, perhaps the most remarkable among the countless other applications of quantum mechanics. On the other hand, the enormous impact of computers on everyday life is on the eye of the beholder. Their importance is such that it is appropriate to say that we are now living in the information age. Needless to say, this information revolution became possible thanks to the invention of the transistor, that is, thanks to the synergy between computer science and quantum physics…

This chapter introduces the basic concepts of computer science that are necessary for an understanding of quantum computation and information. We discuss the Turing machine, the fundamental model of computation since it formalizes the intuitive notion of an algorithm: if there exists an algorithm to solve a given problem, then this algorithm can be run on a Turing machine. We then introduce the circuit model of computation, which is equivalent to the Turing machine model but is nearer to real computers. In this model, the information is carried by wires and a small set of elementary logical operations (gates) allows implementation of any complex computation. It is important to find the minimum resources (computer memory, time and energy) required to solve a given problem with the best possible algorithm. This is the task of computational complexity, for which we provide a quick glance at the key concepts. We also examine the energy resources necessary to perform computations. Here we discuss the relation between energy and information, which was explained by Landauer and Bennett in their solution of Maxwell’s demon paradox. In particular, Landauer’s principle sets the minimum energy requirements for irreversible computation. On the other hand, it turns out that it is, in principle, possible to perform any complex computation by means of reversible gates, without energy dissipation. A concrete model of reversible computation, the so-called billiard-ball computer, is briefly discussed. Finally, we address the problem of energy dissipation in a real computation and show how it may be managed using reversible computation techniques.

At the end of nineteenth century it became clear that classical physics led to predictions in disagreement with experiment. This gave rise to a profound change in the basic concepts of our understanding of Nature. A new theory, known as quantum mechanics, was constructed. This theory describes the phenomena of the microscopic world in satisfactory agreement with all present experimental data…

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ⁿ-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.

In this chapter, we focus on quantum algorithms and the techniques underlying their construction. These algorithms take advantage of the basic properties of quantum mechanics, from the superposition principle to entanglement and interference effects, to solve certain computational problems much more efficiently than a classical computer. This includes basic problems of computer science: from the search of a marked item in an unstructured database (Grover’s algorithm) to integer factoring (Shor’s algorithm). The latter case provides a striking exponential speedup over the best known classical algorithms. After that, we discuss a third relevant class of quantum algorithms, the simulation of physical systems.

In this chapter, we show that the basic properties of quantum mechanics can be put to practical use in the transmission of information. The most spectacular application is in the field of cryptography, the art of secret communication. After a short overview of classical cryptography, we discuss the unique contribution of quantum mechanics to cryptography. Quantum cryptography enables two communicating parties, named Alice (the sender) and Bob (the receiver ), to detect whether the transmitted message has been intercepted by Eve (an eavesdropper). This is a consequence of a basic property of quantum mechanics, the “no-cloning theorem”: an unknown quantum state cannot be cloned. Then we illustrate two remarkable applications of quantum mechanics: dense coding and quantum teleportation. Dense coding uses entanglement to enhance the communication of classical information. If Alice and Bob share an entangled EPR pair of qubits, Alice can operate on her member of the pair and then send it to Bob: this single qubit carries two bits of classical information. Quantum teleportation again exploits entanglement and allows Alice to transmit a quantum bit to Bob by sending him only classical bits. Finally, after providing the necessary background, we discuss the extension of quantum cryptography from discrete to continuous variables, and hence from finite to infinite dimensional Hilbert spaces.

The presence of correlations shared among the subparts of a given physical system, and which do not have a classical counterpart, is a clear signature of non-classicality for a quantum state. As we saw in Chap. 2, such correlations can be captured by entanglement, one of the most intriguing features predicted by quantum theory, which points directly to a violation of the Bell’s inequalities. In this chapter we provide a rigorous definition of entanglement, and review its basic properties together with the general framework that is needed to quantify it for bipartite states. We present the common criteria that are used to detect whether a state is entangled or not, and discuss the most common entanglement quantifiers in the bipartite context. The latter follow an introduction of the cornerstone concepts of classical Shannon entropy and quantum von Neumann entropy. Subsequently, the multipartite scenario is briefly addressed. Although entanglement is the most remarkable among non-classical correlations, even some separable (not entangled) mixed states can exhibit a non-classical behaviour. In this wider context we discuss the quantum discord, which is expressed as the difference between two entropic quantities and is extractable by performing a local measure on one of the subsystems. This, and other related quantifiers, enlighten the impossibility of recovering the information contained in a composite quantum system after the measurement process. A special-topic section on the different definitions of entropy used in physics closes the chapter.

In practice, any quantum system is open; namely, it is never perfectly isolated from the environment. The word decoherence, used in its broader meaning, denotes any quantum-noise process due to the unavoidable coupling of the system to the environment. Decoherence theory has a fundamental interest beyond quantum information science since it provides explanations of the emergence of classicality in a world governed by the laws of quantum mechanics. The core of the problem is the superposition principle, according to which any superposition of quantum states is an acceptable quantum state. This entails consequences that are absurd according to classical intuition, such as the superposition of “live cat” and “dead cat” considered in Schrödinger’s well-known cat paradox. The interaction with the environment can destroy the coherence between the states appearing in a superposition (for instance, the “live-cat” and “dead-cat” states).

In quantum information processing, decoherence is a threat to the actual implementation of any quantum computation or communication protocol. Indeed, decoherence invalidates the quantum superposition principle, which lies at the heart of the potential power of any quantum algorithm. On the other hand, decoherence is also an essential ingredient for quantum information processing, which must end up with a measurement by converting quantum states into classical outcomes. We shall see that decoherence plays a key role in the quantum measurement process.

In this chapter, we shall describe decoherence using various tools, from the quantum-operation formalism to the master-equation and the quantum-trajectory approaches. General results will be illustrated by means of concrete examples, including single-qubit noise models and the damped quantum harmonic oscillator.

Classical information theory deals with the transmission of messages (say, binary strings) over communication channels. Its fundamental questions are: How much can a message be compressed and still be transmitted reliably? Can we protect this message against errors that will appear in noisy communication channels? In this chapter, we discuss the first questions in the light of quantum mechanics, which opens up new possibilities for information theory, while the second question will be postponed to Chap. 9, devoted to error correction…

In this chapter we discuss how to protect quantum information from errors. The use of error-correcting codes to fight the effect of noise is a well developed technique in classical information processing. The key ingredient to protect information against errors is redundancy…

The great challenge of quantum computation is to experimentally realize a large scale quantum computer. The requirements that must be fulfilled to achieve this imposing objective are summarized in DiVincenzo (2000a):

• (1) A scalable system with well characterized qubits.
• (2) The ability to initialize (‘reset’) the state of the qubits to a fiducial state (such as |0 ⋯ 0〉).
• (3) Long significant decoherence times, much longer than the gate operation time.
• (4) An experimentally feasible universal set of quantum gates.
• (5) A high-fidelity readout method

This final chapter is devoted to an application of basic quantum information theory concepts in the context of strongly correlated systems and, more in general, of condensed matter physics. Recent groundbreaking experiments in the spirit of Feynman’s idea of quantum simulators enabled to manipulate certain quantum many-body systems in a very accurate and controlled way, thus paving the way for a tremendously increasing theoretical activity in this field. We will see that a closer look to the intimate entanglement structure of typical many-body wave functions may reveal itself extremely helpful to understand the physics of such systems. Indeed, on this basis, it has been possible to conceive powerful analytical and numerical methods to uniquely characterize the thermodynamical properties of a wide class of complex quantum systems…

Quantum information has literally invaded all the fields of science, from cosmology to biophysics. Concepts and tools from quantum information find applications in various fields, including many-body physics (as discussed in Chap. 11), quantum gravity, quantum thermodynamics, and quantum biology, to name but a few. Understanding the connections between all these fields may provide fruitful cross-fertilization of ideas. Furthermore, quantum information and more generally quantum mechanics impact on our perception of nature and life, including philosophical speculations on determinism, free will, and human consciousness. The legacy of quantum information is too broad to be covered in this textbook and many relevant issues were neglected. We wish to conclude our presentation by giving a flavour of some of them, and outlining possible short- and long-term developments in the field of quantum information.

The following sections are included:

• Appendix A Elements of linear algebra
  • Finite-dimensional vector spaces
    • Basic properties of vector spaces
    • Inner product and norm of a vector
    • Linear independence and the notion of basis
    • Linear operators
    • Tensor product
    • Matrix decompositions
    • Symplectic decompositions
  • Infinite-dimensional vector spaces
    • Discrete and continuous bases
    • The Dirac delta function
    • Orthonormality and completeness relations
    • Position and momentum representations
    • Position and momentum operators
• Appendix B Solutions to the exercises
  • Chapter 1
  • Chapter 2
  • Chapter 3
  • Chapter 4
  • Chapter 5
  • Chapter 6
  • Chapter 7
  • Chapter 8
  • Chapter 9
  • Chapter 10
  • Chapter 11
  • Appendix A

The following sections are included:

• Bibliography
• Index