Quantum algorithms for query problems

Steven Herbert

Published Dec 8, 2025• 0 citations

Abstract

Abstract In 1985, David Deutsch proposed the original quantum algorithm, a simple yet remarkable demonstration of the enhanced computational power offered by quantum mechanics. Deutsch’s algorithm provides a reduction in the number of queries to an unknown function required to discern some property of that function, relative to the best possible classical counterpart. This is known as an advantage in query complexity, and whilst the attention of the quantum computing community has, by and large, moved on to quantum algorithms that provide an advantage in computational rather than query complexity, it is still instructive to study some of the most important quantum algorithms for query problems. Such algorithms are historically important and, moreover, reveal the source of the computational power of quantum mechanics in a clear and easy to understand manner. This chapter studies four algorithms for query problems: Deutsch’s algorithm, the Deutsch–Jozsa algorithm, the Bernstein–Vazirani algorithm, and Simon’s algorithm.

DOI: 10.1093/9780191964381.003.0007

Related papers

Quantum Query Algorithms

Walid E. Gomaa

This presentation gives a comprehensive overview of quantum query algorithms, beginning with an introduction to the query model of computation where input is accessed via an oracle function. It then details several foundational quantum algorithms that demonstrate a quantum advantage over classical approaches: Deutsch's problem is solved with a single query using phase kickback to determine if a function is constant or balanced; the Deutsch-Jozsa algorithm extends this to n-bit inputs, efficiently distinguishing constant from balanced functions with one query versus an exponential need classically; the Bernstein-Vazirani algorithm identifies a hidden string with one query, outperforming classical linear requirements; and Simon's algorithm, which finds a hidden period in a two-to-one function with a linear number of queries, showcases an exponential speedup over the best classical probabilistic algorithms.

Nov 19, 20250 citations

uantum Advantage and the Evolution of Query Complexity a Critical Analysis of the Deutsch, Deutsch–Jozsa, and Simon Algorithms

Medak Srinivas

Quantum computation transformed our thinking about computational complexity by showing that quantum mechanical principles can be used to reduce the number of queries needed to solve some problems. The work constitutes a critical analysis of the evolution of the query complexity through three fundamental quantum algo rithms: the Deutsch algorithm, the Deutsch–Jozsa algorithm and Simon’s algorithm. Together, these algorithms illustrate the emergence of quantum advantage where quantum systems outperform classical deterministic and probabilistic approaches by exploiting superposition, interference, entanglement and unitary evolution.The study begins with the Deutsch algorithm, the first demonstration that a quantum computer can compute a global property of a Boolean function with fewer oracle queries than any deterministic classical algorithm. We further extend the analysis to the Deutsch–Jozsa algorithm, which generalizes this speedup to the exponential level by distinguishing between balanced and constant Boolean functions with one quantum query. Then we study Simon’s Algorithm, a milestone that achieved an exponential separation between classical randomized and quantum query complexity. The groundwork for many later advances, such as Shor’s algorithm for factoring integers, was established by this body of work. The discussion continues with an emphasis on Linear Algebra and the use of Hilbert spaces, Tensor Products, Unitary Transformations, and Fourier based interference methods. As the report describes, significant advancements toward reducing the time it takes for quantum systems to perform calculations are made possible through use of Oracle construction, Spectral Decomposition, and Mea surement Theory. This comparative analysis explores the use of computational queries in deterministic, probabilistic, and quan tum models while examining the transition from classical decision tree complexities into quantum computation paradigms. Ultimately, the results of this analysis show that the early quantum algorithms must be recognized not merely as isolated computational oddities, but rather as crucial components of the development of quantum information sci ence. They provided a conceptual and mathematical framework for the modern understanding of what constitutes a quantum advantage; Moreover, they also provide valuable insight into how quantum mechanical systems influ ence both computational efficiency and complexity theory, specifically as well as future information processing system design.

Iterative International Publishers eBooksMay 1, 20260 citations

Quantum Advantage with Deutsch-Jozsa, Bernstein-Vazirani, and Simon’s Algorithms

Vladimir Silva

In this chapter, we study three algorithms of little practical use but important because they were the first to show that quantum computers can solve problems significantly faster than classical ones. Consider the time complexities O(n) for the algorithms: classical vs. quantum in Table 9-1 (where n is the size of the input).

Apress eBooksDec 18, 20230 citations

Black-Box Algorithms

Robert Hundt

The algorithms presented in this chapter were the first to establish a query complexity advantage for quantum algorithms. The list of algorithms includes the Bernstein-Vazirani algorithm, Deutsch’s algorithm, and Deutsch-Jozsa algorithm. Quantum oracles and their construction are being introduced.

Cambridge University Press eBooksNov 20, 20250 citations

Characterization of exact one-query quantum algorithms (ii): for partial functions

Zekun Ye, Lvzhou Li

The query model (or black-box model) has attracted much attention from the communities of both classical and quantum computing. Usually, quantum advantages are revealed by presenting a quantum algorithm that has a better query complexity than its classical counterpart. For example, the well-known quantum algorithms including Deutsch-Jozsa algorithm, Simon algorithm and Grover algorithm all show a considerable advantage of quantum computing from the viewpoint of query complexity. Recently we have considered in (Phys. Rev. A. {\bf 101}, 02232 (2020)) the problem: what functions can be computed by an exact one-query quantum algorithm? This problem has been addressed for total Boolean functions but still open for partial Boolean functions. Thus, in this paper we continue to characterize the computational power of exact one-query quantum algorithms for partial Boolean functions by giving several necessary and sufficient conditions. By these conditions, we construct some new functions that can be computed exactly by one-query quantum algorithms but have essential difference from the already known ones. Note that before our work, the known functions that can be computed by exact one-query quantum algorithms are all symmetric functions, whereas the ones constructed in this papers are generally asymmetric.

arXiv:2008.11998Aug 27, 20201 citation

Foundations of Quantum Computing: The Query Model Perspective

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.

Iterative International Publishers eBooksMay 1, 20260 citations