Everyone has lost their marbles! Anonymous Before we formally present quantum mechanics in all its wonders, we shall spend time providing some basic intuitions behind its core methods and ideas. Realizing that computer scientists feel comfortable with graphs and matrices, we shall cast quantum mechanical ideas in graph-theoretic and matrix-theoretic terms. Everyone who has taken a class in discrete structures knows how to represent a (weighted) graph as an adjacency matrix. We shall take this basic idea and generalize it in several straightforward ways. While doing this, we shall present a few concepts that are at the very core of quantum mechanics. In Section 3.1, the graphs are without weights. This will model classical deterministic systems. In Section 3.2, the graphs are weighted with real numbers. This will model classical probabilistic systems. In Section 3.3, the graphs are weighted with complex numbers and will model quantum systems. We conclude Section 3.3 with a computer science/graph-theoretic version of the double-slit experiment. This is perhaps the most important experiment in quantum mechanics. Section 3.4 discusses ways of combining systems to yield larger systems. Throughout this chapter, we first present an idea in terms of a toy model, then generalize it to an abstract point, and finally discuss its connection with quantum mechanics, before moving on to the next idea.
Everyone has lost their marbles! Anonymous Before we formally present quantum mechanics in all its wonders, we shall spend time providing some basic intuitions behind its core methods and ideas. Realizing that computer scientists feel comfortable with graphs and matrices, we shall cast quantum mechanical ideas in graph-theoretic and matrix-theoretic terms. Everyone who has taken a class in discrete structures knows how to represent a (weighted) graph as an adjacency matrix. We shall take this basic idea and generalize it in several straightforward ways. While doing this, we shall present a few concepts that are at the very core of quantum mechanics. In Section 3.1, the graphs are without weights. This will model classical deterministic systems. In Section 3.2, the graphs are weighted with real numbers. This will model classical probabilistic systems. In Section 3.3, the graphs are weighted with complex numbers and will model quantum systems. We conclude Section 3.3 with a computer science/graph-theoretic version of the double-slit experiment. This is perhaps the most important experiment in quantum mechanics. Section 3.4 discusses ways of combining systems to yield larger systems. Throughout this chapter, we first present an idea in terms of a toy model, then generalize it to an abstract point, and finally discuss its connection with quantum mechanics, before moving on to the next idea.
Scope of this book Quantum mechanics is a difficult subject, and this book is intended to help the reader overcome the main difficulties in the way to understanding it. The first part of the book, Chs. 2–16, contains a systematic presentation of the basic principles of quantum theory, along with a number of examples which illustrate how these principles apply to particular quantum systems. The applications are, for the most part, limited to toy models whose simple structure allows one to see what is going on without using complicated mathematics or lengthy formulas. The principles themselves, however, are formulated in such a way that they can be applied to (almost) any nonrelativistic quantum system. In the second part of the book, Chs. 17–25, these principles are applied to quantum measurements and various quantum paradoxes, subjects which give rise to serious conceptual problems when they are not treated in a fully consistent manner. The final chapters are of a somewhat different character. Chapter 26 on decoherence and the classical limit of quantum theory is a very sketchy introduction to these important topics along with some indication as to how the basic principles presented in the first part of the book can be used for understanding them. Chapter 27 on quantum theory and reality belongs to the interface between physics and philosophy and indicates why quantum theory is compatible with a real world whose existence is not dependent on what scientists think and believe, or the experiments they choose to carry out. The Bibliography contains references for those interested in further reading or in tracing the origin of some of the ideas presented in earlier chapters.
Reality is that which, when you stop believing in it, does not go away. Philip K. Dick In Chapters 1 and 2 we developed the necessary mathematical apparatus and terminology that will be used throughout this book. Chapter 3 has provided some heuristics and gently led us to the threshold of quantum mechanics. It is now time to open the door, introduce the basic concepts and tools of the trade, and continue our journey to quantum computing. In Section 4.1 we spend a few words on the motivations behind quantum mechanics. We then introduce quantum states and how they are distinguishable from one another through observations. Section 4.2 describes observable physical quantities within the quantum framework. How observable quantities are measured is the topic of Section 4.3. The dynamics of quantum systems, i.e., their evolution in time, is the focus of Section 4.4. Finally, in Section 4.5, we revisit the tensor product and show how it describes the way in which larger quantum systems are assembled from smaller ones. In the process, we meet the crucial notion of entanglement, a feature of the quantum world that pops up again in the chapters ahead. QUANTUM STATES Why quantum mechanics? To answer this question, we have to hearken back in time to the dawn of the twentieth century. Classical mechanics still dominated the scene, with its double-pronged approach: particles and waves .
The early twentieth century was a revolutionary time in the history of physics. People often think of Einstein's special theory of relativity of 1905, which changed our conceptions of time and space. But among physicists, quantum mechanics is usually regarded as an even more radical change in our thinking about the physical world. Quantum mechanics, which was developed between 1900 and 1926, began as a theory of atoms and light but has now become the framework in terms of which all basic physical theories are expected to be cast. We need quantum ideas not only to understand atoms, molecules, and elementary particles, but also to understand the electronic properties of solids and even certain astronomical phenomena such as the stability of white dwarf stars. The theory was radical in part because it introduced probabilistic behavior as a fundamental aspect of the world, but even more because it seems to allow mutually exclusive situations to exist simultaneously in a “quantum superposition.” We will see later that the possibility of quantum superposition is largely responsible for a quantum computer's distinctive advantage over an ordinary computer. The present chapter is devoted to introducing the basic principles of quantum mechanics. There are essentially four components of the mathematical structure of quantum mechanics. We need to know how to represent (i) states, (ii) measurements, (iii) reversible transformations, and (iv) composite systems. We will develop the first three in stages, starting with a very simple case – linear polarization of photons – and working toward the most general case.
The mathematical formalism of quantum theory in terms of vectors and operators in infinite-dimensional complex vector spaces is very abstract. The definitions of many mathematical quantities used do not seem to have an intuitive meaning, which makes it difficult to appreciate the mathematical formalism and understand quantum mechanics. This book provides intuition and motivation to the mathematics of quantum theory, introducing the mathematics in its simplest and familiar form, for instance, with three-dimensional vectors and operators, which can be readily understood. Feeling confident about and comfortable with the mathematics used helps readers appreciate and understand the concepts and formalism of quantum mechanics. This book is divided into four parts. Part I is a brief review of the general properties of classical and quantum systems. A general discussion of probability theory is also included which aims to help in understanding the probability theories relevant to quantum mechanics. Part II is a detailed study of the mathematics for quantum mechanics. Part III presents quantum mechanics in a series of postulates. Six groups of postulates are presented to describe orthodox quantum systems. Each statement of a postulate is supplemented with a detailed discussion. To make them easier to understand, the postulates for discrete observables are presented before those for continuous observables. Part IV presents several illustrative applications, which include harmonic and isotropic oscillators, charged particle in external magnetic fields and the Aharonov–Bohm effect. For easy reference, definitions, theorems, examples, comments, properties and results are labelled with section numbers. Various symbols and notations are adopted to distinguish different quantities explicitly and to avoid misrepresentation. Self-contained both mathematically and physically, the book is accessible to a wide readership, including astrophysicists, mathematicians and philosophers of science who are interested in the foundations of quantum mechanics.
The edge connectivity of a simple graph is the least number of edges whose removal disconnects the graph. We study the quantum query complexity of computing the edge connectivity of a simple graph with n vertices and m edges in both the adjacency matrix and adjacency array models. For classical randomized algorithms, Ω(n2) and Ω(m) lower bounds are known for these models, respectively, showing that the trivial algorithm is optimal in terms of query complexity for both cases. In contrast, we show upper bounds of O~(n3/2) and O~(mn) on the quantum query complexity of computing edge connectivity in the adjacency matrix and adjacency array models, respectively. Our upper bound is tight up to logarithmic factors for the adjacency matrix model, while for the adjacency array model the best quantum query lower bound we know is Ω(n). Our upper bounds follow by combining a lemma on the structure of near-minimum cuts due to Rubinstein, Schramm and Weinberg (ITCS 2018) with a quantum sparsification algorithm by Apers and de Wolf (FOCS 2020).
For a weighted graph, instead of edge connectivity the relevant notion is the weight of a minimum cut, i.e. the minimum total weight of a set of edges whose removal disconnects the graph. For weighted graphs we show that in the worst case Ω(n2) queries can be needed to compute the weight of a minimum cut by a quantum algorithm in both the adjacency matrix and adjacency array models, thus no quantum speedup is possible in this case.
To obtain a basic understanding of how and why quantum computing works, one needs to understand quantum theory. In this book we treat quantum mechanics as an axiomatic theory, with some interpretations where possible. The implications of quantum mechanics are often counter intuitive, or rather, beyond intuition, since we have no direct experience of the quantum world as we do the classical. We assume no prior knowledge of quantum mechanics, and will develop all the basic tools and ideas necessary for a sound grasp of the fundamentals of the theory, especially what is relevant for two-state systems that we’ll use as qubits. For a more detailed picture, the reader is referred to standard texts on quantum mechanics, such as the books by J. J. Sakurai [60], R. Shankar [62], C. Cohen-Tannoudji [20], E. Merzbacher [49] etc. or the Feynman Lectures on Physics Vol III [34].