 First edition cover | |
| Author | Eleanor Rieffel, Wolfgang Polak |
|---|---|
| Subject | Quantum computing |
| Genre | Textbook |
| Publisher | MIT Press |
Publication date | 2011 |
Quantum Computing: A Gentle Introduction is a textbook on quantum computing. It was written by Eleanor Rieffel and Wolfgang Polak, and published in 2011 by the MIT Press.
Although the book approaches quantum computing through the model of quantum circuits, [1] [2] it is focused more on quantum algorithms than on the construction of quantum computers. [2] It has 13 chapters, divided into three parts: "Quantum building blocks" (chapters 1–6), "Quantum algorithms" (chapters 7–9), and "Entangled subsystems and robust quantum computation" (chapters 10–13). [3]
After an introductory chapter overviewing related topics including quantum cryptography, quantum information theory, and quantum game theory, chapter 2 introduces quantum mechanics and quantum superposition using polarized light as an example, also discussing qubits, the Bloch sphere representation of the state of a qubit, and quantum key distribution. Chapter 3 introduces direct sums, tensor products, and quantum entanglement, and chapter 4 includes the EPR paradox, Bell's theorem on the impossibility of local hidden variable theories, as quantified by Bell's inequality. Chapter 5 discusses unitary operators, quantum logic gates, quantum circuits, and functional completeness for systems of quantum gates. Chapter 6, the final chapter of the building block section, discusses (classical) reversible computing, and the conversion of arbitrary computations to reversible computations, a necessary step to performing them on quantum devices. [2] [3]
In the section of the book on quantum algorithms, chapter 7 includes material on quantum complexity theory and the Deutch algorithm, Deutsch–Jozsa algorithm, Bernstein–Vazirani algorithm, and Simon's algorithm, algorithms devised to prove separations in quantum complexity by solving certain artificial problems faster than could be done classically. It also covers the quantum Fourier transform. Chapter 8 covers Shor's algorithm for integer factorization, and introduces the hidden subgroup problem. Chapter 9 covers Grover's algorithm and the quantum counting algorithm for speeding up certain kinds of brute-force search. The remaining chapters return to the topic of quantum entanglement and discuss quantum decoherence, quantum error correction, and its use in designing robust quantum computing devices, with the final chapter providing an overview of the subject and connections to additional topics. Appendices provide a graphical approach to tensor products of probability spaces, and extend Shor's algorithm to the abelian hidden subgroup problem. [2] [3]
The book is suitable as an introduction to quantum computing for computer scientists, mathematicians, and physicists, requiring of them only a background in linear algebra and the theory of complex numbers, [2] [3] although reviewer Donald L. Vestal suggests that additional background in the theory of computation, abstract algebra, and information theory would also be helpful. [4] Prior knowledge of quantum mechanics is not required. [2]
Reviewer Kyriakos N. Sgarbas has some minor notational quibbles with the book's presentation, and complains that the level of difficulty is uneven and that it lacks example solutions. [2] However, reviewer Valerio Scarani calls the book "a masterpiece", particularly praising it for its orderly arrangement, its well-thought-out exercises, the self-contained nature of its chapters, and its inclusion of material warning readers against falling into common pitfalls. [1]
There are many other textbooks on quantum computing; [2] for instance, Scarani lists Quantum Computer Science: An Introduction by N. David Mermin (2007), An Introduction to Quantum Computing by Kaye, Laflamme, and Mosca (2007), and A Short Introduction to Quantum Information and Quantum Computation by Michel Le Bellac (2006). [1] Sgarbas lists in addition Quantum Computing Explained by D. McMahon (2008) and Quantum Computation and Quantum Information by M. A. Nielsen and I. L. Chuang (2000). [2]
A quantum computer is a computer that exploits quantum mechanical phenomena. On small scales, physical matter exhibits properties of both particles and waves, and quantum computing leverages this behavior using specialized hardware. Classical physics cannot explain the operation of these quantum devices, and a scalable quantum computer could perform some calculations exponentially faster than any modern "classical" computer. Theoretically a large-scale quantum computer could break some widely used encryption schemes and aid physicists in performing physical simulations; however, the current state of the art is largely experimental and impractical, with several obstacles to useful applications.
Quantum information is the information of the state of a quantum system. It is the basic entity of study in quantum information theory, and can be manipulated using quantum information processing techniques. Quantum information refers to both the technical definition in terms of Von Neumann entropy and the general computational term.
In quantum computing, a qubit or quantum bit is a basic unit of quantum information—the quantum version of the classic binary bit physically realized with a two-state device. A qubit is a two-state quantum-mechanical system, one of the simplest quantum systems displaying the peculiarity of quantum mechanics. Examples include the spin of the electron in which the two levels can be taken as spin up and spin down; or the polarization of a single photon in which the two spin states can also be measured as horizontal and vertical linear polarization. In a classical system, a bit would have to be in one state or the other. However, quantum mechanics allows the qubit to be in a coherent superposition of multiple states simultaneously, a property that is fundamental to quantum mechanics and quantum computing.
Shor's algorithm is a quantum algorithm for finding the prime factors of an integer. It was developed in 1994 by the American mathematician Peter Shor. It is one of the few known quantum algorithms with compelling potential applications and strong evidence of superpolynomial speedup compared to best known classical (non-quantum) algorithms. On the other hand, factoring numbers of practical significance requires far more qubits than available in the near future. Another concern is that noise in quantum circuits may undermine results, requiring additional qubits for quantum error correction.
This is a timeline of quantum computing.
Theoretical computer science is a subfield of computer science and mathematics that focuses on the abstract and mathematical foundations of computation.
In quantum computing, a quantum algorithm is an algorithm that runs on a realistic model of quantum computation, the most commonly used model being the quantum circuit model of computation. A classical algorithm is a finite sequence of instructions, or a step-by-step procedure for solving a problem, where each step or instruction can be performed on a classical computer. Similarly, a quantum algorithm is a step-by-step procedure, where each of the steps can be performed on a quantum computer. Although all classical algorithms can also be performed on a quantum computer, the term quantum algorithm is generally reserved for algorithms that seem inherently quantum, or use some essential feature of quantum computation such as quantum superposition or quantum entanglement.
Quantum Information Science is a field that combines the principles of quantum mechanics with information theory to study the processing, analysis, and transmission of information. It covers both theoretical and experimental aspects of quantum physics, including the limits of what can be achieved with quantum information. The term quantum information theory is sometimes used, but it does not include experimental research and can be confused with a subfield of quantum information science that deals with the processing of quantum information.
In quantum information theory, a quantum circuit is a model for quantum computation, similar to classical circuits, in which a computation is a sequence of quantum gates, measurements, initializations of qubits to known values, and possibly other actions. The minimum set of actions that a circuit needs to be able to perform on the qubits to enable quantum computation is known as DiVincenzo's criteria.
In quantum computing and specifically the quantum circuit model of computation, a quantum logic gate is a basic quantum circuit operating on a small number of qubits. Quantum logic gates are the building blocks of quantum circuits, like classical logic gates are for conventional digital circuits.
Quantum programming is the process of designing or assembling sequences of instructions, called quantum circuits, using gates, switches, and operators to manipulate a quantum system for a desired outcome or results of a given experiment. Quantum circuit algorithms can be implemented on integrated circuits, conducted with instrumentation, or written in a programming language for use with a quantum computer or a quantum processor.
Quantum neural networks are computational neural network models which are based on the principles of quantum mechanics. The first ideas on quantum neural computation were published independently in 1995 by Subhash Kak and Ron Chrisley, engaging with the theory of quantum mind, which posits that quantum effects play a role in cognitive function. However, typical research in quantum neural networks involves combining classical artificial neural network models with the advantages of quantum information in order to develop more efficient algorithms. One important motivation for these investigations is the difficulty to train classical neural networks, especially in big data applications. The hope is that features of quantum computing such as quantum parallelism or the effects of interference and entanglement can be used as resources. Since the technological implementation of a quantum computer is still in a premature stage, such quantum neural network models are mostly theoretical proposals that await their full implementation in physical experiments.
The Pattern on the Stone: The Simple Ideas that Make Computers Work is a book by W. Daniel Hillis, published in 1998 by Basic Books (ISBN 0-465-02595-1). The book attempts to explain concepts from computer science in layman's terms by metaphor and analogy. It aims to demystify computer science by demonstrating that complex processes can be broken down into simple, repeated patterns. The book emphasizes the underlying simplicity and elegance of computer science, encouraging readers to see the beauty in the patterns that power the technology that permeates our lives.
Quantum complexity theory is the subfield of computational complexity theory that deals with complexity classes defined using quantum computers, a computational model based on quantum mechanics. It studies the hardness of computational problems in relation to these complexity classes, as well as the relationship between quantum complexity classes and classical complexity classes.
In reversible computing, ancilla bits are extra bits being used to implement irreversible logical operations. In classical computation, any memory bit can be turned on or off at will, requiring no prior knowledge or extra complexity. However, this is not the case in quantum computing or classical reversible computing. In these models of computing, all operations on computer memory must be reversible, and toggling a bit on or off would lose the information about the initial value of that bit. For this reason, in a quantum algorithm there is no way to deterministically put bits in a specific prescribed state unless one is given access to bits whose original state is known in advance. Such bits, whose values are known a priori, are known as ancilla bits in a quantum or reversible computing task.
IBM Quantum Platform is an online platform allowing public and premium access to cloud-based quantum computing services provided by IBM. This includes access to a set of IBM's prototype quantum processors, a set of tutorials on quantum computation, and access to an interactive textbook. As of February 2021, there are over 20 devices on the service, six of which are freely available for the public. This service can be used to run algorithms and experiments, and explore tutorials and simulations around what might be possible with quantum computing.
In quantum computing, quantum supremacy or quantum advantage is the goal of demonstrating that a programmable quantum computer can solve a problem that no classical computer can solve in any feasible amount of time, irrespective of the usefulness of the problem. The term was coined by John Preskill in 2012, but the concept dates to Yuri Manin's 1980 and Richard Feynman's 1981 proposals of quantum computing.
Eleanor Gilbert Rieffel is a mathematician interested in quantum computing, computer vision, and cryptography. She is a senior research scientist at NASA's Ames Research Center.
This glossary of quantum computing is a list of definitions of terms and concepts used in quantum computing, its sub-disciplines, and related fields.