In this chapter we explore some of the principles of quantum algorithm design, together with a discussion of some of the (chronologically) first algorithms providing evidence of a quantum speedup of some type. These algorithms are not directly useful for optimization, but they serve the purpose of familiarizing the reader with, and building intuition on, the analysis of quantum algorithms; for this purpose, it is generally helpful to start from simple algorithms.
In this chapter we explore some of the principles of quantum algorithm design, together with a discussion of some of the (chronologically) first algorithms providing evidence of a quantum speedup of some type. These algorithms are not directly useful for optimization, but they serve the purpose of familiarizing the reader with, and building intuition on, the analysis of quantum algorithms; for this purpose, it is generally helpful to start from simple algorithms.
In this chapter we will describe some of the early quantum algorithms. These algorithms are simple and illustrate the main ingredients behind the more useful and powerful quantum algorithms we describe in the subsequent chapters. Since quantum algorithms share some features with classical probabilistic algorithms, we will start with a comparison of the two algorithmic paradigms. Classical probabilistic algorithms were introduced in Chapter 1. In this section we will see how quantum computation can be viewed as a generalization of probabilistic computation. We begin by considering a simple probabilistic computation. Figure 6.1 illustrates the first two steps of such a computation on a register that can be in one of the four states, labelled by the integers 0, 1, 2, and 3. Initially the register is in the state 0. After the first step of the computation, the register is in the state j with probability p0,j . For example, the probability that the computation is in state 2 after the first step is p0,2. In the second step of the computation, the register goes from state j to state k with probability qj,k. For example, in the second step the computation proceeds from state 2 to state 3 with probability q2,3. Suppose we want to find the total probability that the computation ends up in state 3 after the second step. This is calculated by first determining the probability associated with each computation ‘path’ that could end up at the state 3, and then by adding the probabilities for all such paths. There are four computation paths that can leave the computation in state 3 after the first step. The computation can proceed from state 0 to state j and then from state j to state 3, for any of the four j ∊ {0, 1, 2, 3}. The probability associated with any one of these paths is obtained by multiplying the probability p0,j of the transition from state 0 to state j, with the probability qj,3 of the transition from state j to state 3.
Optimisation and AI: What are companies doing today?The earlier chapter on quantum applications discussed whether quantum computers can offer practical speedups for optimisation and AI.We concluded that this is a subtle case and that it is still unclear how much utility quantum computers can provide in these fields.Still, a large body of literature claims some form of near-term speedup in specific quantum applications.What's really going on here?This chapter aims to build a more detailed intuition of how different organisations are exploring quantum applications.We will assess some example research papers, examine the problems they tackle, and analyse how convincingly they point to quantum utility.Moreover, we will look at the most fruitful directions for finding new and useful quantum algorithms.But before we dive into these details, let's take a step back and ask ourselves: what must a quantum algorithm do to be a genuine improvement over its classical counterpart?
Introduction While it might appear that the nineteenth-century physics presented in this chapter has no place in a topic as quantum mechanically oriented as atomic physics, this is simply not the case. The purpose of this first chapter is to try to convince the readers that the material learned in their early years of studying physics is not disjoint from modern topics, but in fact can provide a foundation for their further understanding. Other examples will occur later. The reader may be a bit surprised to see that the results of the classical description turn out to be so close to the quantum mechanical results. Where there are significant disagreements between classical and quantum descriptions, it is necessary to explain why these occur. The correspondence principle requires that in the limit of large quantum numbers the complete quantum mechanical description must agree with the classical one. It is always better to need fewer of these explanations and to be able to treat physics as a coherent whole instead of a collection of topics. The consequences of classical physics are intuitively familiar, and this is often most helpful in gaining deeper understanding. In fact, the approach taken in very many of the chapters in this book is to start with a purely classical description of a topic, and then transport it directly into the Schrödinger equation. Radiation from an accelerated charge, as treated here in the harmonic case, provides an ideal setting for such pedagogy. Even though classical mechanics is used in place of quantum mechanics, for the case of harmonic motion, the results are quite compatible. The early history of atomic physics contains many topics that are well worth reading about, especially the experimental facilities. For example, there were no electric motors, wire was not readily available, and making even a crude vacuum was an experimental tour de force. Very many textbooks have discussions of these topics, and so they will not be presented here. But the reader is warned that certain oft-repeated modern descriptions are simply wrong. Perhaps the most important notion to be gained from this chapter is that the classical description of a harmonically bound electron provides quite accurate results about the interaction between atoms and light. Of course, the utility of this description is limited because the classical harmonic oscillator has no internal structure, is infinitely deep, and has a continuous energy spectrum.
Quantum computing represents a transformative approach to computation that exploits the principles of quantum mechanics to process information in fundamentally different ways from classical computers. Over the past few decades, the field has evolved from a primarily theoretical discipline into an active area of research spanning computer science, mathematics, physics, information theory, and engineering. As quantum technologies continue to develop, understanding the fundamental computational principles underlying quantum algorithms has become increasingly important. Foundations of Quantum Computing: The Query Model Perspective presents a systematic introduction to quantum computing with particular emphasis on the query model, a powerful framework for studying the computational complexity of quantum algorithms. The query model provides a clean and mathematically tractable setting in which the number of queries made to an unknown function or oracle can be used as the primary measure of computational cost. This perspective offers valuable insights into the capabilities and limitations of quantum computation and provides a natural foundation for understanding quantum speedups. The book introduces the fundamental concepts required to study quantum computation, including quantum states, quantum gates, quantum circuits, measurement, superposition, entanglement, and quantum algorithms. These concepts are developed alongside the query-complexity framework, enabling readers to understand how quantum algorithms exploit interference and other quantum phenomena to reduce the number of queries required to solve computational problems. Particular attention is given to important quantum query algorithms and complexity results. Classical and quantum query complexities are discussed comparatively to illustrate the sources and significance of quantum advantages. Well-known examples such as the Deutsch–Jozsa algorithm, Grover's search algorithm, and related oracle-based problems provide concrete illustrations of how quantum procedures can outperform their classical counterparts. The discussion also introduces lower-bound techniques and fundamental principles that help establish the limitations of quantum query algorithms. The query model is not only useful for understanding individual algorithms but also serves as an important bridge between quantum algorithms and computational complexity theory. By focusing on query complexity, many problems can be examined independently of the details of a particular physical implementation. This abstraction makes the framework especially useful for developing rigorous proofs, comparing computational resources, and identifying the fundamental sources of quantum advantage. This book is intended for students, researchers, educators, and professionals interested in quantum computing and theoretical computer science. It can serve as an introductory reference for readers with a background in discrete mathematics, linear algebra, algorithms, or theoretical computer science, while also providing a foundation for readers who wish to pursue more advanced studies in quantum complexity theory and quantum algorithms. The chapters have been organized to progress from foundational concepts toward more advanced aspects of the quantum query model. Mathematical formulations are accompanied by explanations and examples to help readers connect abstract theoretical ideas with computational intuition. The broader objective is to provide readers with the tools necessary not only to understand existing quantum algorithms but also to reason about new problems from a query-complexity perspective. As quantum computing continues to mature, the ability to distinguish genuine computational advantages from implementation-specific effects will become increasingly significant. The query model provides one of the clearest theoretical environments for making this distinction. By studying quantum computation through this lens, readers can develop a deeper appreciation of both the power and the limitations of quantum algorithms It is hoped that Foundations of Quantum Computing: The Query Model Perspective will serve as a useful resource for learning, teaching, and research, and will encourage further exploration into the rapidly evolving landscape of quantum computation and quantum complexity theory.