Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Oxford University Press eBooks

Quantum algorithms for query problems

Steven Herbert

Published Dec 8, 2025• 0 citations
Publisher

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, 2025•0 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 eBooks•May 1, 2026•0 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 eBooks•Dec 18, 2023•0 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 eBooks•Nov 20, 2025•0 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.11998•Aug 27, 2020•3 citations

Early quantum algorithms

Riccardo Manenti, Mário Motta

Abstract This chapter presents early quantum algorithms. We first describe Deutsch’s and Bernstein-Vazirani, some of the first quantum algorithms that showed a query advantage over their classical counterparts. We then present Grover’s algorithm, a quantum algorithm that finds an item in an unstructured database with a quadratic speed-up over classical algorithms. We explain the quantum Fourier transform, an important subroutine in various quantum algorithms. The chapter concludes with a detailed presentation of two of the most prominent applications of the quantum Fourier transform: the period finding algorithm and Shor’s algorithm for prime factorization.

Oxford University Press eBooks•Aug 25, 2023•0 citations
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.
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.
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.
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.
Abstract This chapter presents early quantum algorithms. We first describe Deutsch’s and Bernstein-Vazirani, some of the first quantum algorithms that showed a query advantage over their classical counterparts. We then present Grover’s algorithm, a quantum algorithm that finds an item in an unstructured database with a quadratic speed-up over classical algorithms. We explain the quantum Fourier transform, an important subroutine in various quantum algorithms. The chapter concludes with a detailed presentation of two of the most prominent applications of the quantum Fourier transform: the period finding algorithm and Shor’s algorithm for prime factorization.