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.
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.
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.
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 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].
Around 1900, physicists started to discover particles like electrons, protons, and neutrons, and with these discoveries believed they could predict the internal behavior of the atom. However, once their predictions were compared to the results of experiments in the real world, it became clear that the principles of classical physics and mechanics were far from capable of explaining phenomena on the atomic scale. With this realization came the advent of quantum physics, one of the most important intellectual movements in human history. Today, quantum physics is everywhere: it explains how our computers work, how lasers transmit information across the Internet, and allows scientists to predict accurately the behavior of nearly every particle in nature. Its application continues to be fundamental in the investigation of the most expansive questions related to our world and the universe. However, while the field and principles of quantum physics are known to have nearly limitless applications, the fundamental reasons why this is the case are far less understood. In Quantum Physics: What Everyone Needs to Know, quantum physicist Michael G. Raymer distills the basic principles of such an abstract field, and addresses the many ways quantum physics is a key factor in today's science and beyond. The book tackles questions as broad as the meaning of quantum entanglement and as specific and timely as why governments worldwide are spending billions of dollars developing quantum technology research. Raymer's list of topics is diverse, and showcases the sheer range of questions and ideas in which quantum physics is involved. From applications like data encryption and quantum computing to principles and concepts like "quantum nonlocality" and Heisenberg's uncertainty principle, Quantum Physics: What Everyone Needs to Know is a wide-reaching introduction to a nearly ubiquitous scientific topic.
Graph-theoretic structures play a central role in the description and analysis of quantum systems. In this work, we introduce a new class of quantum states, called Aα-graph states, which are constructed from either unweighted or weighted graphs by taking the normalised convex combination of the degree matrix D and the adjacency matrix AG of a graph G. The constructed states are different from the standard graph states arising from stabiliser formalism. Our approach is also different from the approach used by Braunstein et al. This class of states depend on a tunable mixing parameter α∈(0,1]. We first establish the conditions under which the associated operator ραAG is positive semidefinite and hence represents a valid quantum state. We then derive a positive partial transposition (PPT) condition for Aα-graph states in terms of graph parameters. This PPT condition involves only the Frobenius norm of the adjacency matrix of the graph, the degrees of the vertices and the total number of vertices. For simple graphs, we obtain the range of the parameter α for which the Aα-graph states represent a class of entangled states. We then develop a graph-theoretic formulation of a moments-based entanglement detection criterion, focusing on the recently proposed p3-PPT criterion, which relies on the second and third moments of the partial transposition. Since the estimation of these moments is experimentally accessible via randomised measurements, swap operations, and machine-learning-based protocols, our approach provides a physically relevant framework for detecting entanglement in structured quantum states derived from graphs. This work bridges graph theory and moments-based entanglement detection, offering a new perspective on the role of combinatorial structures in quantum correlations.