This issue's SIGEST paper, from the SIAM Journal on Computing (SICOMP), takes SIAM readers into the world of quantum computing, a world with its roots in physics that still probably is better known to many physicists and theoretical computer scientists than to a good portion of SIAM readers. Quantum computation is a form of computing based upon quantum mechanics, rather than the classical physics that conventional computers utilize. The distinction between conventional and quantum computers starts to become apparent at the most basic level of bits: whereas standard computers utilize binary bits that may have either the state 0 or 1, quantum computers are based upon “qubits” (quantum binary digits) that may have the state 0, 1, or a superposition of these two states with a complex number that specifies the probability for being in each state. Mathematically, the state of a quantum computer can change through a sequence of unitary transformations to the initial state. One reason for the great interest in quantum computation is that it has been shown that quantum computers can solve some important problems, such as the factorization of very large integers (which has important implications for cryptography), far more efficiently than we currently are able to solve these problems on conventional computers. The selected paper, “Adiabatic Quantum Computation Is Equivalent to Standard Quantum Computation” by Dorit Aharonov, Wim van Dam, Julia Kempe, Zeph Landau, Seth Lloyd, and Oded Regev, which was originally published in SICOMP in 2007, establishes an important theoretical result in the field of quantum computation. As the title indicates, it involves adiabatic quantum computation, a form of quantum computing that has attracted interest in recent years in part because it may offer promise in the effort to build effective quantum computers. Adiabatic quantum computation is distinctly different from standard quantum computation. In the standard model, computations are represented similarly to classical circuits, except that the circuits carry qubits instead of bits. In contrast, the adiabatic model is inspired by the adiabatic theorem in quantum mechanics which states that a system in its lowest energy or ground state will remain in that state if it is subjected to conditions that change sufficiently slowly. It already was known that standard quantum computers can efficiently simulate adiabatic quantum computers. The key contribution of this paper is to show the reverse: that adiabatic quantum computation can efficiently simulate standard quantum computation. In the words of the SICOMP editorial board in nominating this paper, “This is a surprising result that continues to be very influential.” It established that the two forms of quantum computation are theoretically equivalent, one implication of which is to bolster the potential practical importance of adiabatic quantum computation. The paper by Aharonov et al. is very nicely suited to SIGEST—it is important in its field, it is nicely and accessibly written, it offers a glimpse into an area of applied mathematics and computation that is of growing importance, and it touches on many areas of applied mathematics, including linear algebra, Markov chains, and optimization. We hope it will provide SIAM readers a glimpse of current theoretical research that may, some day, help lead to a brave new world of practical computation.
This issue's SIGEST paper, from the SIAM Journal on Computing (SICOMP), takes SIAM readers into the world of quantum computing, a world with its roots in physics that still probably is better known to many physicists and theoretical computer scientists than to a good portion of SIAM readers. Quantum computation is a form of computing based upon quantum mechanics, rather than the classical physics that conventional computers utilize. The distinction between conventional and quantum computers starts to become apparent at the most basic level of bits: whereas standard computers utilize binary bits that may have either the state 0 or 1, quantum computers are based upon “qubits” (quantum binary digits) that may have the state 0, 1, or a superposition of these two states with a complex number that specifies the probability for being in each state. Mathematically, the state of a quantum computer can change through a sequence of unitary transformations to the initial state. One reason for the great interest in quantum computation is that it has been shown that quantum computers can solve some important problems, such as the factorization of very large integers (which has important implications for cryptography), far more efficiently than we currently are able to solve these problems on conventional computers. The selected paper, “Adiabatic Quantum Computation Is Equivalent to Standard Quantum Computation” by Dorit Aharonov, Wim van Dam, Julia Kempe, Zeph Landau, Seth Lloyd, and Oded Regev, which was originally published in SICOMP in 2007, establishes an important theoretical result in the field of quantum computation. As the title indicates, it involves adiabatic quantum computation, a form of quantum computing that has attracted interest in recent years in part because it may offer promise in the effort to build effective quantum computers. Adiabatic quantum computation is distinctly different from standard quantum computation. In the standard model, computations are represented similarly to classical circuits, except that the circuits carry qubits instead of bits. In contrast, the adiabatic model is inspired by the adiabatic theorem in quantum mechanics which states that a system in its lowest energy or ground state will remain in that state if it is subjected to conditions that change sufficiently slowly. It already was known that standard quantum computers can efficiently simulate adiabatic quantum computers. The key contribution of this paper is to show the reverse: that adiabatic quantum computation can efficiently simulate standard quantum computation. In the words of the SICOMP editorial board in nominating this paper, “This is a surprising result that continues to be very influential.” It established that the two forms of quantum computation are theoretically equivalent, one implication of which is to bolster the potential practical importance of adiabatic quantum computation. The paper by Aharonov et al. is very nicely suited to SIGEST—it is important in its field, it is nicely and accessibly written, it offers a glimpse into an area of applied mathematics and computation that is of growing importance, and it touches on many areas of applied mathematics, including linear algebra, Markov chains, and optimization. We hope it will provide SIAM readers a glimpse of current theoretical research that may, some day, help lead to a brave new world of practical computation.
Information is a physical. Physical systems register and process information. These facts generated enormus interest in the development of novel quantum tecnologies, especially because the construction of smaller electronic devices ultimately leads to a consideration of quantum mechanical effects in electronic and computer desingns. The notion of the classical bit of information theory was formally pushed into the realm of the quanta with the introduction of the quantum bit or qubit, in the seminal works of Deutsch (Deutsch, 1985) and Shor (Shor, 1994). They demostrated that, indeed, controlled multipartite qubit interference effects could provide the means for a radical new way of computing, allowing the computation of many intractable computational problems, such as the factoring of large number or exact simulation of large quantum systems. The field of experimental and theoretical research in quantum information and computation has emerged as very important player in the understanding of quantum phenomena the both the basic and technological levels. This has attracted the attention of numerous researchers with backgrounds ranging from computer science, mathematics and engineerin, to the physical sciences, and we now have an interdisciplinary field where great efforts are being made in order to build devices that allow the progressing of information at a quantum level. A concise introduction to the field of quantum information and quantum computation is presented. This stars with the bassic definitions of bits, quantum registers, through to the universal gate-set for building the universal quantum computer, from a quantum network model of computation. The work shows how two-qubit gates suffice for quantum computation, emphasing the power of the quantum circuit representation for entagling and disentagling quantum states. This leads to the “no-cloning theorem”, which leads us to many interesting applications, such as quantum cryptography. Two alternative approaches or performing quantum computation are also described i) the one-way or measurement based quantum computer method, and ii) holonomic or geometric quantum computation. Following this, quantum entaglement quantification is highlighted, particulary its usefulness as a communication resource, in order to describe some of its most celebrated practical applications to date: quantum teleportation, cryptography, dens coding, and data compression. Deutsch’s concept of quantum parallelism is enphasized in order to gain insight into the potential for efficiently solving certain classically intratable algorithms. A subject central to the field of QIP- quantum decoherence- is then introduced.. Possible ways to overcome it, in particular quantum error correction, are discussed. A descriptios of some of the currently available hardware of the practical implementation of quantum computation is provided with a discussion of the main physical quantum bits that are currently employed (or proposed) for a such a purpose.
The rapid evolution of computers in the half century since their invention has resulted in dramatically smaller and faster computers. However, from a computational point of view, all these computers look alike; for example, they are built out of simple logic gates. A fundamental thesis of computer science---the modern form of the Church--Turing thesis---asserts that this is inevitable in a deep sense. Any computer can be simulated with at most a polynomial factor slowdown by a probabilistic Turing machine. Quantum computation poses the first credible challenge to this thesis. It goes back to a suggestion by Feynman [4], who pointed out that there appears to be no efficient way of simulating a quantum mechanical system on a computer, and suggested that, perhaps, a computer based on quantum physical principles might be able to carry out the simulation efficiently. Two formal models for quantum computers---the quantum Turing machine [2] and quantum computational networks [3]---were defined by Deutsch. The first three papers in this issue describe efficient quantum algorithms for computational tasks that we do not know how to solve classically. In "Quantum Complexity Theory," Bernstein and Vazirani give the first formal evidence that quantum computers violate the modern form of the Church--Turing thesis. They show that a certain problem---the recursive Fourier sampling problem---can be solved in polynomial time on a quantum Turing machine, but relative to an oracle, requires superpolynomial time on a classical probabilistic Turing machine. Simon, in the paper "On the Power of Quantum Computation" introduces a fundamental projection technique and uses it to design an efficient quantum algorithm to determine whether a certain type of function is 2-1 or 1-1. He further shows that, relative to an oracle, this problem requires exponential time on a classical probabilistic Turing machine. In the paper "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer," Shor gives remarkable polynomial time quantum algorithms for two of the most famous problems in computer science: factoring and discrete log. Since the computational hardness of these problems is the basis of several famous cryptosystems, Shor's paper very dramatically underlines the power of quantum computers. To understand the computational power of quantum computers, it is helpful to consider a quantum mechanical system of n particles, each of which can be in one of two states, labeled ∣0⟩ and ∣1⟩. If this were a classical system, then its instantaneous state could be described by n bits. However, in quantum physics, the system is allowed to be in a linear superposition of configurations, and indeed the instantaneous state of the system is described by a unit vector in the 2n dimensional vector space, whose basis vectors correspond to all the2n classical configurations. Therefore, to describe the instantaneous state of the system, we must specify 2n complex numbers. Nature must update 2n complex numbers at each instant to evolve the system in time. This is an extraordinary amount of effort, since even for n = 200, 2n is larger than estimates of the number of elementary particles in the visible universe. Nonetheless, there are limits to the power of quantum computers. In "Strengths and Weaknesses of Quantum Computing," Bennett, Bernstein, Brassard, and Vazirani show that, relative to a random oracle, with probability 1, the class NP cannot be solved on a quantum Turing machine in time o(2n/2). This bound is tight, since recent work of Grover [5] has shown how to accept any language in NP in time O(2n/2) on a quantum Turing machine. Quantum computers are necessarily time reversible. Indeed, Bennett's work [1] on reversible computation inspired early work on quantum computation that preceded Feynman's paper [4]. The reversibility requirement makes it quite complex to implement even basic computational primitives such as looping or composition. In "Quantum Complexity Theory," Bernstein and Vazirani show how to implement quantum programming primitives and give a construction for an efficient universal quantum Turing machine. The structure of the universal quantum Turing machine is quite simple: it consists of a deterministic Turing machine with a single "quantum coin flip." In "Quantum Computability," Adleman, DeMarrais, and Huang greatly simplify this further by showing that a very simple type of coin flip is sufficient---a rotation by an angle θ such that sinθ=3/5. Making quantum computers robust against noise and decoherence is an important and challenging problem. In "Stabilization of Quantum Computations by Symmetrization," Barenco, Berthiaume, Deutsch, Ekert, Jozsa, and Macchiavello show how to use the quantum watchdog effect to stabilize a quantum computation against noise. Their method is based on running several copies of the quantum computer in parallel and projecting its state into the symmetric subspace at frequent intervals. They show that the quantum watchdog effect results in the suppression of errors that lie outside the symmetric subspace. Quantum computation touches upon the foundations of both computer science and quantum physics. It is not unlikely that the issues raised by quantum computation will stimulate further research into the foundations of quantum physics. I wish to express my gratitude to several people who made this special section possible. Oded Goldreich acted as editor for two of the papers in the issue and dealt with them with his characteristic efficiency and judgment. The editorial staff at SIAM, most notably Lisa Dougherty, Beth Gallagher, Deidre Wunderlich, and Sam Young, were extremely helpful, patient, and resourceful. Finally, I would like to thank a number of referees whose careful and timely reviews were critical to putting together this issue. Umesh Vazirani
Quantum computing has emerged as one of the most transformative technological developments of the twenty-first century. By exploiting the fundamental principles of quantum mechanics—namely superposition, entanglement, and measurement—quantum computers offer the potential to address problems that are beyond the practical reach of classical computing systems. As the field advances from theoretical exploration to real-world implementation, the demand for clear, structured, and comprehensive educational resources continues to grow. This book presents a systematic and accessible introduction to quantum computing, beginning with the essential concepts of classical information and computation and progressively advancing toward modern quantum algorithms and communication protocols. The initial chapters establish a strong foundation in classical bits, logic gates, Boolean algebra, reversible logic, and computational complexity, providing the conceptual bridge necessary to understand quantum computation. The discussion then moves to the quantum bit (qubit), examining its behavior through superposition, measurement, Bloch sphere representation, and physical realization. Special emphasis is placed on linear algebra as the mathematical framework underpinning quantum computing. Through this approach, readers are guided to develop an intuitive yet rigorous understanding of quantum states, quantum gates, and circuit-based computation. The text further extends these ideas to multi-qubit systems, quantum entanglement, universal gate sets, and quantum error correction, integrating theoretical principles with practical insights. To support experiential learning, the book incorporates hands-on exposure to leading quantum programming platforms, including IBM Quantum, OpenQASM, and Qiskit. These sections connect theory with practice, enabling readers to design, simulate, and execute quantum circuits on both simulators and real quantum hardware. Subsequent chapters explore key quantum communication protocols such as superdense coding, quantum teleportation, and quantum key distribution, followed by an in-depth treatment of foundational quantum algorithms including Deutsch–Jozsa, Grover’s search, Simon’s algorithm, and Shor’s factoring algorithm. This text is intended for undergraduate and postgraduate students, research scholars, and industry professionals seeking a coherent and structured pathway into quantum computing. No prior knowledge of quantum mechanics is assumed, although familiarity with linear algebra and classical computation will enhance comprehension. Each chapter is carefully organized to promote conceptual clarity, supported by illustrative examples, circuit diagrams, and concise summaries. Beyond explaining the principles and mechanisms of quantum computation, this book aims to inspire readers to engage with the future of the field—whether through academic research, industrial application, or interdisciplinary innovation. As quantum technologies continue to evolve, it is hoped that this text will serve as a dependable guide and a meaningful entry point into the quantum era.
Quantum computing has emerged as one of the most transformative technological developments of the twenty-first century. By exploiting the fundamental principles of quantum mechanics—namely superposition, entanglement, and measurement—quantum computers offer the potential to address problems that are beyond the practical reach of classical computing systems. As the field advances from theoretical exploration to real-world implementation, the demand for clear, structured, and comprehensive educational resources continues to grow. This book presents a systematic and accessible introduction to quantum computing, beginning with the essential concepts of classical information and computation and progressively advancing toward modern quantum algorithms and communication protocols. The initial chapters establish a strong foundation in classical bits, logic gates, Boolean algebra, reversible logic, and computational complexity, providing the conceptual bridge necessary to understand quantum computation. The discussion then moves to the quantum bit (qubit), examining its behavior through superposition, measurement, Bloch sphere representation, and physical realization. Special emphasis is placed on linear algebra as the mathematical framework underpinning quantum computing. Through this approach, readers are guided to develop an intuitive yet rigorous understanding of quantum states, quantum gates, and circuit-based computation. The text further extends these ideas to multi-qubit systems, quantum entanglement, universal gate sets, and quantum error correction, integrating theoretical principles with practical insights. To support experiential learning, the book incorporates hands-on exposure to leading quantum programming platforms, including IBM Quantum, OpenQASM, and Qiskit. These sections connect theory with practice, enabling readers to design, simulate, and execute quantum circuits on both simulators and real quantum hardware. Subsequent chapters explore key quantum communication protocols such as superdense coding, quantum teleportation, and quantum key distribution, followed by an in-depth treatment of foundational quantum algorithms including Deutsch–Jozsa, Grover’s search, Simon’s algorithm, and Shor’s factoring algorithm. This text is intended for undergraduate and postgraduate students, research scholars, and industry professionals seeking a coherent and structured pathway into quantum computing. No prior knowledge of quantum mechanics is assumed, although familiarity with linear algebra and classical computation will enhance comprehension. Each chapter is carefully organized to promote conceptual clarity, supported by illustrative examples, circuit diagrams, and concise summaries. Beyond explaining the principles and mechanisms of quantum computation, this book aims to inspire readers to engage with the future of the field—whether through academic research, industrial application, or interdisciplinary innovation. As quantum technologies continue to evolve, it is hoped that this text will serve as a dependable guide and a meaningful entry point into the quantum era.
This manuscript is intended for readers who have a general interest in the subject of quantum computation and provides an overview of the most significant developments in the field. It begins by introducing foundational concepts from quantum mechanics—such as superposition, entanglement, and the no-cloning theorem—that underpin quantum computation. The primary computational models are discussed, including gate-based (circuit) quantum computing, adiabatic quantum computing, measurement-based quantum computing and the quantum Turing machine. A selection of significant quantum algorithms are reviewed, notably Grover’s search algorithm, Shor’s factoring algorithm, and Quantum Singular Value Transformation (QSVT), which enables efficient solutions to linear algebra problems on quantum devices. To assess practical performance, we compare quantum and classical implementations of support vector machines (SVMs) using several synthetic datasets. These experiments offer insight into the capabilities and limitations of near-term quantum classifiers relative to classical counterparts. Finally, we review leading quantum programming platforms—including Qiskit, PennyLane, and Cirq—and discuss their roles in bridging theoretical models with real-world quantum hardware. The paper aims to provide a concise yet comprehensive guide for those looking to understand both the theoretical foundations and applied aspects of quantum computing.
This chapter provides a basic overview of Quantum Computers (QCs) used in Quantum Computing (Quacomp) applications. Classical computers utilize silicon-based semiconductor devices. In recent years integrated circuit lateral feature sizes have been reduced to 10 nm, increasing chip density; however, as these sizes progress to be reduced to 5 nm and smaller, silicon-based circuits become impractical. QCs make use of quantum phenomena such as entanglement and superposition to increase and improve the computation speed as compared to classical computers, enabling them to solve some computationally complex problems in practical time windows. At this juncture QCs are not able to act as replacements for general- purpose computers, but they can outperform classical computers in a set of specific computational problems, such as optimization problems or for identifying the best solution from a set of feasible solutions. This chapter covers three QC approaches: the circuit model (or gate model), the adiabatic quantum computation model, and the categorical quantum model. Quacomp has experienced relatively rapid development in recent years, starting with the basic ideation in the early 1980s, then continuing with early proof of concepts for hardware in the next two decades, and now, in the 2020s, with QC hardware that can implement over one-thousand qubits (e.g., [ TIL22 ], [ FEY82 ], [ LEU00 ], [ NEG06 ], [ PLA07 ], [ MON11 ], [ MON16 ], [ CAS23 ]). Figure 5.1 (courtesy of IBM) depicts recent illustrative achievements in practical QC development at IBM, a key player in this arena (in the fall of 2023, IBM® announced the Condor prototype, the world’s first universal QC with 1,121 qubits 1 ). The generation of QCs at the time of this writing is known as Noisy-Intermediate Scale Quantum (NISQ) devices (some proponents cite this as being the third generation). These NISQ QCs are typically cooled to cryogenic temperatures (around −273° C) in order to operate efficiently; these environmental conditions are challenging to maintain in other than laboratory settings. In practical terms, QCs remain of somewhat limited and specialized functionality and are prone to computational errors. Considering these limitations, Hybrid QC (HQC) 170 171 172 arrangements and Hybrid Quantum Applications (HQApps) endeavor to combine classical and QC systems in order to undertake calculations directed at various (but specific) optimization or related use cases; tasks such as preparing inputs for quantum algorithms, storing data, or interacting with the user are typically still performed using classical computers. The number of operations in a QC typically equates with the number of quantum gates and the number of qubits supported; however, the larger the number of gates, the more likely it is that errors, including decoherence, are introduced into the quantum state. NISQ entails a somewhat limited number of logical qubits and associated physical qubits to support error correction schemes. Fortunately, a category of algorithms running on NISQ devices can proceed with only a small number of qubits and exhibit some degree of noise resilience; typically, they are hybrid algorithms, with a portion of the computational steps performed on a quantum device and with other computational steps running on a conventional computer. The bottom line is that with NISQ devices, the number of operations is typically moderate at this juncture, thus the scope and type of algorithms that can be implemented is relatively limited. However, there is research that shows that even these QCs can outperform conventional computers on a set of mathematical problems (e.g., [ PRE18 ], [ BRO19 ], [ MAD22 ]). The next step in the evolution is the interconnection of QCs over a distance network, as discussed in Chapter 6 . A classification of fundamental QC technologies has been proposed the European standards body CEN-CENELEC, specifically the Focus Group on Quantum Technologies (FGQT), which was established in June 2020 to coordinate and support the development of standards relevant for European industry and research [ OVA22 ]. See Table 5.1 .