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

Annales Universitatis Scientiarum Budapestinensis de Rolando Eötvös Nominatae Sectio computatorica

Comparing two quantum oracles using the Deutsch–Jozsa algorithm

Attila Kiss, Krisztián Varga

Published Jan 1, 2020• 1 citation
Publisher

Abstract

There are a lot of articles about quantum algorithms, which involve querying a black box function, often called an oracle.This paper proposes a way to combine two oracles and to determine how similar they are using the Deutsch-Jozsa algorithm.In this case being similar means, that the sets of marked states have just a few ones outside of their intersection.The new quantum algorithm is compared to its classical counterparts and a detailed analysis shows when it will outperform them.

DOI
10.71352/ac.50.199

Related papers

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

Improved quantum test for linearity of a Boolean function

Kaushik Chakraborty, Subhamoy Maitra

Let a Boolean function be available as a black-box (oracle) and one likes to devise an algorithm to test whether it has certain property or it is $ε$-far from having that property. The efficiency of the algorithm is judged by the number of calls to the oracle so that one can decide, with high probability, between these two alternatives. The best known quantum algorithm for testing whether a function is linear or $ε$-far $(0 < ε< \frac{1}{2})$ from linear functions requires $O(ε^{-\frac{2}{3}})$ many calls [Hillery and Andersson, Physical Review A 84, 062329 (2011)]. We show that this can be improved to $O(ε^{-\frac{1}{2}})$ by using the Deutsch-Jozsa and the Grover Algorithms.

arXiv:1306.6195•Jun 26, 2013•8 citations

Possible Implementations of Oracles in Quantum Algorithms

Jiahao Zhao

Abstract Quantum computing is an inspiring technic on solving complicate problems, which shows the superiority over the classical computing. Contemporarily, the quantum-based algorithms were invented in many purposes on solving those problems. The thing is some of the algorithms were composed with oracles, which can be treated as a black box. It can be worked out/analyzed in theoretical mathematical expressions, but it can never fall in the ground without those actual implementations. Therefore, this paper will illustrate the idea and possible implementations on some quantum algorithm. Among various algorithms, this research will choose those relatively famous quantum algorithms, i.e., Deutsch-Jozsa Algorithm, Shor’s Algorithm, and Grover’s Algorithm. Different algorithms have the different intrinsic logics, which means there is no general description for all solution in this problem, but all of those can achieve the goal according to the same framework. Since those oracles are black boxes that can only be analyzed by its behavior with different cases, and then based on the behaviors and cases, and in IBM quantum platform, one can fill out the oracle by manipulate with different quantum operators. Lastly, the figures of some the possible implementation of those oracles with the three quantum algorithms will be shown in the IBM quantum platform, as well as the histograms of probability distributions that can justify the correctness of the implementations. These results shed light on guiding further exploration of the design and analysis on quantum algorithms.

Journal of Physics Conference Series•Dec 1, 2022•1 citation

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

More advanced quantum algorithms

Jonathan A. Jones, Dieter Jaksch

Deutsch's algorithm and Grover's quantum search are theoretically interesting, but it is not obvious that these two algorithms are actually useful for anything important. We next consider a selection of more advanced algorithms, several of which may have real-life applications. Some of these will be too complicated to explain fully, and their properties will only be sketched briefly. The Deutsch–Jozsa algorithm Deutsch's algorithm is simple, but important, as it shows that a quantum algorithm can find a property of an unknown function (its parity) with a smaller number of queries than any possible classical algorithm (one rather than two). For this reason we can say that quantum computing is more efficient than classical computing within the oracle model of function evaluation. (It is widely believed that quantum computing is more efficient than classical computing in general, but this is a surprisingly hard thing to prove.) The simplicity of the algorithm is also an advantage, as it can be implemented on very primitive quantum computers. Beyond this, however, Deutsch's algorithm is also important as the simplest member of a large family of quantum algorithms, including most notably Shor's quantum factoring algorithm. The second simplest algorithm in the family is the Deutsch–Jozsa algorithm, which solves a very closely related problem. Consider an unknown binary function with n input bits, giving N = 2 n possible inputs, and a single output bit.

Cambridge University Press eBooks•Jul 19, 2012•0 citations

Efficient classical simulation of the Deutsch–Jozsa and Simon’s algorithms

Niklas Johansson, Jan-Åke Larsson

A long-standing aim of quantum information research is to understand what gives quantum computers their advantage. This requires separating problems that need genuinely quantum resources from those for which classical resources are enough. Two examples of quantum speed-up are the Deutsch–Jozsa and Simon’s problem, both efficiently solvable on a quantum Turing machine, and both believed to lack efficient classical solutions. Here we present a framework that can simulate both quantum algorithms efficiently, solving the Deutsch–Jozsa problem with probability 1 using only one oracle query, and Simon’s problem using linearly many oracle queries, just as expected of an ideal quantum computer. The presented simulation framework is in turn efficiently simulatable in a classical probabilistic Turing machine. This shows that the Deutsch–Jozsa and Simon’s problem do not require any genuinely quantum resources, and that the quantum algorithms show no speed-up when compared with their corresponding classical simulation. Finally, this gives insight into what properties are needed in the two algorithms and calls for further study of oracle separation between quantum and classical computation.

arXiv:1508.05027•Quantum Information Processing•Aug 12, 2017•29 citations
There are a lot of articles about quantum algorithms, which involve querying a black box function, often called an oracle.This paper proposes a way to combine two oracles and to determine how similar they are using the Deutsch-Jozsa algorithm.In this case being similar means, that the sets of marked states have just a few ones outside of their intersection.The new quantum algorithm is compared to its classical counterparts and a detailed analysis shows when it will outperform them.
Let a Boolean function be available as a black-box (oracle) and one likes to devise an algorithm to test whether it has certain property or it is εεε-far from having that property. The efficiency of the algorithm is judged by the number of calls to the oracle so that one can decide, with high probability, between these two alternatives. The best known quantum algorithm for testing whether a function is linear or εεε-far (0<ε<12)(0 < ε< \frac{1}{2})(0<ε<21​) from linear functions requires O(ε−23)O(ε^{-\frac{2}{3}})O(ε−32​) many calls [Hillery and Andersson, Physical Review A 84, 062329 (2011)]. We show that this can be improved to O(ε−12)O(ε^{-\frac{1}{2}})O(ε−21​) by using the Deutsch-Jozsa and the Grover Algorithms.
Abstract Quantum computing is an inspiring technic on solving complicate problems, which shows the superiority over the classical computing. Contemporarily, the quantum-based algorithms were invented in many purposes on solving those problems. The thing is some of the algorithms were composed with oracles, which can be treated as a black box. It can be worked out/analyzed in theoretical mathematical expressions, but it can never fall in the ground without those actual implementations. Therefore, this paper will illustrate the idea and possible implementations on some quantum algorithm. Among various algorithms, this research will choose those relatively famous quantum algorithms, i.e., Deutsch-Jozsa Algorithm, Shor’s Algorithm, and Grover’s Algorithm. Different algorithms have the different intrinsic logics, which means there is no general description for all solution in this problem, but all of those can achieve the goal according to the same framework. Since those oracles are black boxes that can only be analyzed by its behavior with different cases, and then based on the behaviors and cases, and in IBM quantum platform, one can fill out the oracle by manipulate with different quantum operators. Lastly, the figures of some the possible implementation of those oracles with the three quantum algorithms will be shown in the IBM quantum platform, as well as the histograms of probability distributions that can justify the correctness of the implementations. These results shed light on guiding further exploration of the design and analysis on quantum algorithms.
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.
Deutsch's algorithm and Grover's quantum search are theoretically interesting, but it is not obvious that these two algorithms are actually useful for anything important. We next consider a selection of more advanced algorithms, several of which may have real-life applications. Some of these will be too complicated to explain fully, and their properties will only be sketched briefly. The Deutsch–Jozsa algorithm Deutsch's algorithm is simple, but important, as it shows that a quantum algorithm can find a property of an unknown function (its parity) with a smaller number of queries than any possible classical algorithm (one rather than two). For this reason we can say that quantum computing is more efficient than classical computing within the oracle model of function evaluation. (It is widely believed that quantum computing is more efficient than classical computing in general, but this is a surprisingly hard thing to prove.) The simplicity of the algorithm is also an advantage, as it can be implemented on very primitive quantum computers. Beyond this, however, Deutsch's algorithm is also important as the simplest member of a large family of quantum algorithms, including most notably Shor's quantum factoring algorithm. The second simplest algorithm in the family is the Deutsch–Jozsa algorithm, which solves a very closely related problem. Consider an unknown binary function with n input bits, giving N = 2 n possible inputs, and a single output bit.
A long-standing aim of quantum information research is to understand what gives quantum computers their advantage. This requires separating problems that need genuinely quantum resources from those for which classical resources are enough. Two examples of quantum speed-up are the Deutsch–Jozsa and Simon’s problem, both efficiently solvable on a quantum Turing machine, and both believed to lack efficient classical solutions. Here we present a framework that can simulate both quantum algorithms efficiently, solving the Deutsch–Jozsa problem with probability 1 using only one oracle query, and Simon’s problem using linearly many oracle queries, just as expected of an ideal quantum computer. The presented simulation framework is in turn efficiently simulatable in a classical probabilistic Turing machine. This shows that the Deutsch–Jozsa and Simon’s problem do not require any genuinely quantum resources, and that the quantum algorithms show no speed-up when compared with their corresponding classical simulation. Finally, this gives insight into what properties are needed in the two algorithms and calls for further study of oracle separation between quantum and classical computation.