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

Classical deterministic one-query Deutsch-Jozsa algorithm

Niklas Johansson, Jan-Åke Larsson

Published Jun 15, 2015• 0 citations
OpenAlex

Related papers

Quantum and classical query complexities for generalized Deutsch–Jozsa problems

Zhengwei Xie, Daowen Qiu

Quantum Information Processing•Mar 25, 2020•1 citation

Generalized Deutsch-Jozsa problem and the optimal quantum algorithm

Daowen Qiu, Shenggen Zheng

The Deutsch-Jozsa algorithm is one of the first examples of a quantum algorithm that is exponentially faster than any possible deterministic classical algorithm. It was proposed by Deutsch and Jozsa in 1992 with improvements by Cleve, Ekert, Macchiavello, and Mosca in 1998. The Deutsch-Jozsa problem is a promise problem and we can equivalently describe it as a partial function ${\text{DJ}}_{n}^{0}:{{0,1}}^{n}\ensuremath{\rightarrow}{0,1}$ defined as ${\text{DJ}}_{n}^{0}(x)=1$ for $|x|=n/2, {\text{DJ}}_{n}^{0}(x)=0$ for $|x|=0,n$, and it is undefined for the rest of the cases, where $n$ is even, and $|x|$ is the Hamming weight of $x$. The optimal quantum algorithm needs only one query to compute ${\text{DJ}}_{n}^{0}$ but the classical deterministic algorithm requires ${2}^{n\ensuremath{-}1}+1$ queries to compute it in the worse case. In this article, we generalize the Deutsch-Jozsa problem as ${\text{DJ}}_{n}^{k}(x)=1$ for $|x|=n/2, {\text{DJ}}_{n}^{k}(x)=0$ for $|x|$ in the set ${0,1,...,k,n\ensuremath{-}k,n\ensuremath{-}k+1,...,n}$, and it is undefined for the rest of the cases, where $0\ensuremath{\le}k<n/2$. In particular, we give and prove an optimal exact quantum query algorithm with complexity $k+1$ for computing the generalized Deutsch-Jozsa problem ${\text{DJ}}_{n}^{k}$. It is clear that the case of $k=0$ is in accordance with the Deutsch-Jozsa problem. Also, we give a method for finding the approximate and exact degrees of symmetric partial Boolean functions.

Physical Review A•Jun 20, 2018•33 citations

Distributed Generalized Deutsch-Jozsa Algorithm

Hao Li, Daowen Qiu, Le Luo

Lecture notes in computer science•Jan 1, 2025•1 citation

On a poset of quantum exact promise problems

Elías F. Combarro, Sofia Vallecorsa, Alberto Di Meglio +2 more

Abstract Two of the most well-known quantum algorithms, those introduced by Deutsch–Jozsa and Bernstein–Vazirani, can solve promise problems with just one function query, showing an oracular separation with deterministic classical algorithms. In this work, we generalise those methods to study a family of quantum algorithms that can, with just one query, exactly solve promise problems stated over Boolean functions. We also show that these problems can be naturally ordered, inducing a partially ordered set of promise problems. We study the properties of such a poset, showing that the Deutsch–Jozsa and Bernstein–Vazirani problems are, in a certain sense, extremal problems in it, determining some of its automorphisms and proving that it is connected. We also prove that, for the problems in the poset, the corresponding classical query complexities can take any value between 1 and $$2^{n-1}+1$$ 2 n - 1 + 1 .

Quantum Information Processing•Jun 1, 2021•0 citations

Revisiting Deutsch-Jozsa algorithm

Daowen Qiu, Shenggen Zheng

Information and Computation•Aug 6, 2020•40 citations

Distributed Deutsch–Jozsa algorithm

Hao Li, Daowen Qiu, Le Luo

arXiv:2303.10663•The Journal of Supercomputing•Aug 9, 2025•27 citations
The Deutsch-Jozsa algorithm is one of the first examples of a quantum algorithm that is exponentially faster than any possible deterministic classical algorithm. It was proposed by Deutsch and Jozsa in 1992 with improvements by Cleve, Ekert, Macchiavello, and Mosca in 1998. The Deutsch-Jozsa problem is a promise problem and we can equivalently describe it as a partial function ${\text{DJ}}_{n}^{0}:{{0,1}}^{n}\ensuremath{\rightarrow}{0,1}$ defined as DJn0(x)=1{\text{DJ}}_{n}^{0}(x)=1DJn0​(x)=1 for ∣x∣=n/2,DJn0(x)=0|x|=n/2, {\text{DJ}}_{n}^{0}(x)=0∣x∣=n/2,DJn0​(x)=0 for ∣x∣=0,n|x|=0,n∣x∣=0,n, and it is undefined for the rest of the cases, where nnn is even, and ∣x∣|x|∣x∣ is the Hamming weight of xxx. The optimal quantum algorithm needs only one query to compute DJn0{\text{DJ}}_{n}^{0}DJn0​ but the classical deterministic algorithm requires ${2}^{n\ensuremath{-}1}+1$ queries to compute it in the worse case. In this article, we generalize the Deutsch-Jozsa problem as DJnk(x)=1{\text{DJ}}_{n}^{k}(x)=1DJnk​(x)=1 for ∣x∣=n/2,DJnk(x)=0|x|=n/2, {\text{DJ}}_{n}^{k}(x)=0∣x∣=n/2,DJnk​(x)=0 for ∣x∣|x|∣x∣ in the set ${0,1,...,k,n\ensuremath{-}k,n\ensuremath{-}k+1,...,n}$, and it is undefined for the rest of the cases, where $0\ensuremath{\le}k<n/2$. In particular, we give and prove an optimal exact quantum query algorithm with complexity k+1k+1k+1 for computing the generalized Deutsch-Jozsa problem DJnk{\text{DJ}}_{n}^{k}DJnk​. It is clear that the case of k=0k=0k=0 is in accordance with the Deutsch-Jozsa problem. Also, we give a method for finding the approximate and exact degrees of symmetric partial Boolean functions.
Abstract Two of the most well-known quantum algorithms, those introduced by Deutsch–Jozsa and Bernstein–Vazirani, can solve promise problems with just one function query, showing an oracular separation with deterministic classical algorithms. In this work, we generalise those methods to study a family of quantum algorithms that can, with just one query, exactly solve promise problems stated over Boolean functions. We also show that these problems can be naturally ordered, inducing a partially ordered set of promise problems. We study the properties of such a poset, showing that the Deutsch–Jozsa and Bernstein–Vazirani problems are, in a certain sense, extremal problems in it, determining some of its automorphisms and proving that it is connected. We also prove that, for the problems in the poset, the corresponding classical query complexities can take any value between 1 and 2n−1+12^{n-1}+12n−1+1 2 n - 1 + 1 .