Computer science and physics have been closely linked since the birth of modern computing. This book is about that link. John von Neumann’s original design for digital computing in the 1940s was motivated by applications in ballistics and hydrodynamics, and his model still underlies today’s hardware architectures. Within several years of the invention of the first digital computers, the Monte Carlo method was developed, putting these devices to work simulating natural processes using the principles of statistical physics. It is difficult to imagine how computing might have evolved without the physical insights that nurtured it. It is impossible to imagine how physics would have evolved without computation. While digital computers quickly became indispensable, a true theoretical understanding of the efficiency of the computation process did not occur until twenty years later. In 1965, Hartmanis and Stearns [227] as well as Edmonds [139, 140] articulated the notion of computational complexity, categorizing algorithms according to how rapidly their time and space requirements grow with input size. The qualitative distinctions that computational complexity draws between algorithms form the foundation of theoretical computer science. Chief among these distinctions is that of polynomial versus exponential time. A combinatorial problem belongs in the complexity class P (polynomial time) if there exists an algorithm guaranteeing a solution in a computation time, or number of elementary steps of the algorithm, that grows at most polynomially with input size. Loosely speaking, such problems are considered computationally feasible. An example might be sorting a list of n numbers: even a particularly naive and inefficient algorithm for this will run in a number of steps that grows as O(n2), and so sorting is in the class P. A problem belongs in the complexity class NP (non-deterministic polynomial time) if it is merely possible to test, in polynomial time, whether a specific presumed solution is correct. Of course, P ⊆ NP: for any problem whose solution can be found in polynomial time, one can surely verify the validity of a presumed solution in polynomial time.
Computer science and physics have been closely linked since the birth of modern computing. This book is about that link. John von Neumann’s original design for digital computing in the 1940s was motivated by applications in ballistics and hydrodynamics, and his model still underlies today’s hardware architectures. Within several years of the invention of the first digital computers, the Monte Carlo method was developed, putting these devices to work simulating natural processes using the principles of statistical physics. It is difficult to imagine how computing might have evolved without the physical insights that nurtured it. It is impossible to imagine how physics would have evolved without computation. While digital computers quickly became indispensable, a true theoretical understanding of the efficiency of the computation process did not occur until twenty years later. In 1965, Hartmanis and Stearns [227] as well as Edmonds [139, 140] articulated the notion of computational complexity, categorizing algorithms according to how rapidly their time and space requirements grow with input size. The qualitative distinctions that computational complexity draws between algorithms form the foundation of theoretical computer science. Chief among these distinctions is that of polynomial versus exponential time. A combinatorial problem belongs in the complexity class P (polynomial time) if there exists an algorithm guaranteeing a solution in a computation time, or number of elementary steps of the algorithm, that grows at most polynomially with input size. Loosely speaking, such problems are considered computationally feasible. An example might be sorting a list of n numbers: even a particularly naive and inefficient algorithm for this will run in a number of steps that grows as O(n2), and so sorting is in the class P. A problem belongs in the complexity class NP (non-deterministic polynomial time) if it is merely possible to test, in polynomial time, whether a specific presumed solution is correct. Of course, P ⊆ NP: for any problem whose solution can be found in polynomial time, one can surely verify the validity of a presumed solution in polynomial time.
A computer is a physical device that helps us process information by executing algorithms. An algorithm is a well-defined procedure, with finite description, for realizing an information-processing task. An information-processing task can always be translated into a physical task. When designing complex algorithms and protocols for various information-processing tasks, it is very helpful, perhaps essential, to work with some idealized computing model. However, when studying the true limitations of a computing device, especially for some practical reason, it is important not to forget the relationship between computing and physics. Real computing devices are embodied in a larger and often richer physical reality than is represented by the idealized computing model. Quantum information processing is the result of using the physical reality that quantum theory tells us about for the purposes of performing tasks that were previously thought impossible or infeasible. Devices that perform quantum information processing are known as quantum computers. In this book we examine how quantum computers can be used to solve certain problems more efficiently than can be done with classical computers, and also how this can be done reliably even when there is a possibility for errors to occur. In this first chapter we present some fundamental notions of computation theory and quantum physics that will form the basis for much of what follows. After this brief introduction, we will review the necessary tools from linear algebra in Chapter 2, and detail the framework of quantum mechanics, as relevant to our model of quantum computation, in Chapter 3. In the remainder of the book we examine quantum teleportation, quantum algorithms and quantum error correction in detail. We are often interested in the amount of resources used by a computer to solve a problem, and we refer to this as the complexity of the computation. An important resource for a computer is time. Another resource is space, which refers to the amount of memory used by the computer in performing the computation. We measure the amount of a resource used in a computation for solving a given problem as a function of the length of the input of an instance of that problem.
In principle, it is possible to model any physical system exactly using quantum mechanics; in practice, it quickly becomes infeasible. Recognising this, Richard Feynman suggested that quantum systems be used to model quantum problems [1]. For example, the fundamental problem faced in quantum chemistry is the calculation of molecular properties, which are of practical importance in fields ranging from materials science to biochemistry. Within chemical precision, the total energy of a molecule as well as most other properties, can be calculated by solving the Schrödinger equation. However, the computational resources required to obtain exact solutions on a conventional computer generally increase exponentially with the number of atoms involved [1, 2]. In the late 1990’s an efficient algorithm was proposed to enable a quantum processor to calculate molecular energies using resources that increase only polynomially in the molecular size [2–4]. Despite the many different physical architectures that have been explored experimentally since that time—including ions, atoms, superconducting circuits, and photons—this appealing algorithm has not been demonstrated to date.
Quantum computing is a prolific research area, halfway between physics and computer science [27, 29, 52]. Most likely, its origins may be dated back to 70's, when some works on quantum information began to appear (see, e.g., [34, 37]). In early 80's, R.P. Feynman suggested that the computational power of quantum mechanical processes might be beyond that of traditional computation models [25]. Almost at the same time, P. Benioff already proved that such processes are at least as powerful as Turing machines [9]. In 1985, D. Deutsch [22] proposed the notion of a quantum Turing machine as a physically realizable model for a quantum computer. From the point of view of structural complexity, E. Bernstein and U. Vazirani introduced in [20] the class BQP of problems solvable in polynomial time on quantum Turing machines, focusing attention on relations with the corresponding deterministic and probabilistic classes P and BPP, respectively. Several works in the literature explored classical issues in complexity theory from the quantum paradigm perspective (see, e.g., [7, 60, 61]).
Heisenberg's uncertainty principle states that it is not possible to compute both the position and momentum of an electron with absolute certainty. However, this computational limitation, which is central to quantum mechanics, has no counterpart in theoretical computer science. Here, I will show that we can distinguish between the complexity classes P and NP when we consider intrinsic uncertainty in our computations, and take uncertainty about whether a bit belongs to the program code or machine input into account. Given intrinsic uncertainty, every output is uncertain, and computations become meaningful only in combination with a confidence level. In particular, it is impossible to compute solutions with absolute certainty as this requires infinite run-time. Considering intrinsic uncertainty, I will present a function that is in NP but not in P, and thus prove that P is a proper subset of NP. I will also show that all traditional hard decision problems have polynomial-time algorithms that provide solutions with confidence under uncertainty.
Finding the ground state of an Ising spin glass on general graphs belongs to the class of NP-hard problems, widely believed to have no efficient polynomial-time algorithms to solve them. An approach developed in computer science for dealing with such problems is to devise approximation algorithms; these are algorithms, whose run time scales polynomially with the input size, that provide solutions with provable guarantees on their quality in terms of the optimal unknown solution. Recently, several algorithms for the Ising spin-glass problem on a bounded degree graph that provide different approximation guarantees were introduced. D-Wave, a Canadian-based company, has constructed a physical realization of a quantum annealer and has enabled researchers and practitioners to access it via their cloud service. D-Wave is particularly suited for computing an approximation for the ground state of an Ising spin glass on its Chimera and Pegasus graphs-both with a bounded degree. To assess the quality of D-Wave's solution, it is natural to compare it to classical approximation algorithms specifically designed to solve the same problem. In this work, we compare the performance of a recently developed approximation algorithm to solve the Ising spin-glass problem on graphs of bounded degree against the performance of the D-Wave computer. We also compared the performance of D-Wave's computer in the Chimera architecture against the performance of a heuristic tailored specifically to handle the Chimera graph. We found that the D-Wave computer was able to find better approximations for all the random instances of the problem we studied-Gaussian weights, uniform weights, and discrete binary weights. Furthermore, the convergence times of D-Wave's computer were also significantly better. These results indicate the merit of D-Wave's computer under certain specific instances. More broadly, our method is relevant to a wider class of performance comparison studies, and we suggest that it is important to compare the performance of quantum computers not only against exact classical algorithms with exponential run-time scaling, but also against approximation algorithms with polynomial run-time scaling and a provable guarantee of performance.
In this section, we discuss a broadly applicable quantum algorithm that provides a polynomial speed-up over the best-known classical algorithms for a wide class of important problems. The quantum search algorithm performs a generic search for a solution to a very wide range of problems. Consider any problem where one can efficiently recognize a good solution and wishes to search through a list of potential solutions in order to find a good one. For example, given a large integer N, one can efficiently recognize whether an integer p is a non-trivial factor of N, and thus one naive strategy for finding non-trivial factors of N is to simply search through the set {2, 3, 4, . . . , ⌊√N⌋} until a factor is found. The factoring algorithm we described in Chapter 7 is not such a naive algorithm, as it makes profound use of the structure of the problem. However, for many interesting problems, there are no known techniques that make much use of the structure of the problem, and the best-known algorithm for solving these problems is to naively search through the potential solutions until one is found. Typically the number of potential solutions is exponential in the size of the problem instance, and so the naive algorithm is not efficient. Often the best-known classical search makes some very limited use of the structure of the problem, perhaps to rule out some obviously impossible candidates, or to prioritize some more likely candidates, but the overall complexity of the search is still exponential. Quantum searching is a tool for speeding up these sorts of generic searches through a space of potential solutions. It is worth noting that having a means of recognizing a solution to a problem, and knowing the set of possible solutions, means that in some sense one ‘knows’ the solution. However, one cannot necessarily efficiently produce the solution. For example, it is easy to recognize the factors of a number, but finding those factors can take a long time. We give this problem a more general mathematical structure as follows.