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

arXiv:1402.7254 · Mathematical Structures in Computer Science

Generalizations of the distributed Deutsch–Jozsa promise problem

Jozef Gruska, Daowen Qiu, Shenggen Zheng

Published May 6, 2015• 39 citations
arXivHTMLPDF

Abstract

In thedistributed Deutsch–Jozsa promise problem, two parties are to determine whether their respective stringsx, y∈ {0,1}nare at theHamming distanceH(x, y) = 0 orH(x, y) = $\frac{n}{2}$ . Buhrmanet al.(STOC' 98) proved that the exactquantum communication complexityof this problem isO(logn) while thedeterministic communication complexityisΩ(n). This was the first impressive (exponential) gap between quantum and classical communication complexity. In this paper, we generalize the above distributed Deutsch–Jozsa promise problem to determine, for any fixed $\frac{n}{2}$ ⩽k⩽n, whetherH(x, y) = 0 orH(x, y) =k, and show that an exponential gap between exact quantum and deterministic communication complexity still holds ifkis an even such that $\frac{1}{2}$ n⩽k< (1 − λ)n, where 0 < λ < $\frac{1}{2}$ is given. We also deal with a promise version of the well-knowndisjointnessproblem and show also that for this promise problem there exists an exponential gap between quantum (and also probabilistic) communication complexity and deterministic communication complexity of the promise version of such a disjointness problem. Finally, some applications to quantum, probabilistic and deterministic finite automata of the results obtained are demonstrated.

DOI
10.1017/s0960129515000158

Related papers

Communication complexity of promise problems and their applications to finite automata

Jozef Gruska, Daowen Qiu, Shenggen Zheng

Equality and disjointness are two of the most studied problems in communication complexity. They have been studied for both classical and also quantum communication and for various models and modes of communication. Buhrman et al. [Buh98] proved that the exact quantum communication complexity for a promise version of the equality problem is ${\bf O}(\log {n})$ while the classical deterministic communication complexity is $n+1$ for two-way communication, which was the first impressively large (exponential) gap between quantum and classical (deterministic and probabilistic) communication complexity. If an error is tolerated, both quantum and probabilistic communication complexities for equality are ${\bf O}(\log {n})$. However, even if an error is tolerated, the gaps between quantum (probabilistic) and deterministic complexity are not larger than quadratic for the disjointness problem. It is therefore interesting to ask whether there are some promise versions of the disjointness problem for which bigger gaps can be shown. We give a positive answer to such a question. Namely, we prove that there exists an exponential gap between quantum (even probabilistic) communication complexity and classical deterministic communication complexity of some specific versions of the disjointness problem. Klauck [Kla00] proved, for any language, that the state complexity of exact quantum/classical finite automata, which is a general model of one-way quantum finite automata, is not less than the state complexity of an equivalent one-way deterministic finite automata (1DFA). In this paper we show, using a communication complexity result, that situation may be different for some promise problems. Namely, we show for certain promise problem that the gap between the state complexity of exact one-way quantum finite automata and 1DFA can be exponential.

arXiv:1309.7739•Sep 30, 2013•3 citations

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•31 citations

Distributed exact quantum algorithms for Deutsch-Jozsa problem

Hao Li, Daowen Qiu, Le Luo

Deutsch-Jozsa (DJ) problem is one of the most important problems demonstrating the power of quantum algorithm. DJ problem can be described as a Boolean function $f$: $\{0,1\}^n\rightarrow \{0,1\}$ with promising it is either constant or balanced, and the purpose is to determine which type it is. DJ algorithm can solve it exactly with one query. In this paper, we first discover the inherent structure of DJ problem in distributed scenario by giving a number of equivalence characterizations between $f$ being constant (balanced) and some properties of $f$'s subfunctions, and then we propose three distributed exact quantum algorithms for solving DJ problem. Our algorithms have essential acceleration over distributed classical deterministic algorithm, and can be extended to the case of multiple computing nodes. Compared with DJ algorithm, our algorithms can reduce the number of qubits and the depth of circuit implementing a single query operator. Therefore, we find that the structure of problem should be clarified for designing distributed quantum algorithm to solve it.

arXiv:2303.10663•Mar 19, 2023•5 citations

Exponential separation of quantum and classical communication complexity

Ran Raz

Communication complexity has become a central completity model.In that model, we count the amount of communication bits needed between two parties in order to solve certain computational problems.We show that for certain communication complezity problems quantum communication protocols are exponentially faster than classical ores.More explicitly, we give an example for a communication complexity relation (0~ promise problem) P such that: 1) The quantum communication complexity of P is O(log m). 2) The classical probabilistic communication complexity of P is Q(m'l'/ logm).(where m is the length of the inputs).This gives an ezponential gap between quantum communication complexity and classical probabilistic communication complexity.Only a quadratic gap was previously known.Our problem P is of geometrical nature, and is a finite precision variation of the following problem: Player I gets as input a unit vector z E R" and two orthogonal subspaces MO, MI c R". Player II gets as input an orthogonal matrixT : R" + R".Their goal is to answer 0 if T(x) E MO and 1 if T(x) E M,, (and any an~luer in any other case).We give an almost tight analysis for the quantum communication complexity and for the classical-probabilistic communication complexity of this problem.

ACM Symposium on Theory of Computing (STOC)•May 1, 1999•222 citations

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

‘Quantum supremacy’ revisited: low-complexity, deterministic solutions of the original Deutsch–Jozsa problem in classical physical systems

László B. Kish

The original Deutsch–Jozsa (oDJ) problem is for an oracle (realized here as a database) of size N , where, according to their claim, the deterministic solution of the problem on a classical Turing computer requires O( N ) computational complexity. They produced the famous Deutsch–Jozsa quantum algorithm that offered an exponential speed-up over the classical computer, namely O[log( N )] complexity for the solution in a quantum computer. In this paper, the problem is implemented on an instantaneous noise-based logic processor. It is shown that, similarly to the quantum algorithm, the oDJ problem can deterministically be solved with O[log( N )] complexity. The implication is that by adding a truly random coin to a classical Turing machine and using this classical-physical algorithm can also speed up the deterministic solution of the Deutsch–Jozsa problem exponentially, similarly to the quantum algorithm. Then it is realized that the same database and the solution of the Deutsch–Jozsa problem can also be realized by using an identical algorithmic structure in a simpler way, even without noise/random coin. The only lost function in this new system, as compared with noise-based logic, is the ability to do generic parallel logic operations over the whole database. As the latter feature is not needed for the oDJ problem, it is concluded that the problem can be solved on a classical computer with O[log( N )] complexity even without a random coin. Therefore, while the oDJ algorithm is a historically important step in the developments of quantum computers, it is insufficient to prove quantum supremacy. Note, there is also a simplified Deutsch–Jozsa problem proposed later, which is more popular in the field; however, it is irrelevant for the present paper.

arXiv:2210.07088•Royal Society Open Science•Feb 28, 2023•12 citations
In thedistributed Deutsch–Jozsa promise problem, two parties are to determine whether their respective stringsx, y∈ {0,1}nare at theHamming distanceH(x, y) = 0 orH(x, y) = n2\frac{n}{2}2n​ . Buhrmanet al.(STOC' 98) proved that the exactquantum communication complexityof this problem isO(logn) while thedeterministic communication complexityisΩ(n). This was the first impressive (exponential) gap between quantum and classical communication complexity. In this paper, we generalize the above distributed Deutsch–Jozsa promise problem to determine, for any fixed n2\frac{n}{2}2n​ ⩽k⩽n, whetherH(x, y) = 0 orH(x, y) =k, and show that an exponential gap between exact quantum and deterministic communication complexity still holds ifkis an even such that 12\frac{1}{2}21​ n⩽k< (1 − λ)n, where 0 < λ < 12\frac{1}{2}21​ is given. We also deal with a promise version of the well-knowndisjointnessproblem and show also that for this promise problem there exists an exponential gap between quantum (and also probabilistic) communication complexity and deterministic communication complexity of the promise version of such a disjointness problem. Finally, some applications to quantum, probabilistic and deterministic finite automata of the results obtained are demonstrated.
Equality and disjointness are two of the most studied problems in communication complexity. They have been studied for both classical and also quantum communication and for various models and modes of communication. Buhrman et al. [Buh98] proved that the exact quantum communication complexity for a promise version of the equality problem is O(log⁡n){\bf O}(\log {n})O(logn) while the classical deterministic communication complexity is n+1n+1n+1 for two-way communication, which was the first impressively large (exponential) gap between quantum and classical (deterministic and probabilistic) communication complexity. If an error is tolerated, both quantum and probabilistic communication complexities for equality are O(log⁡n){\bf O}(\log {n})O(logn). However, even if an error is tolerated, the gaps between quantum (probabilistic) and deterministic complexity are not larger than quadratic for the disjointness problem. It is therefore interesting to ask whether there are some promise versions of the disjointness problem for which bigger gaps can be shown. We give a positive answer to such a question. Namely, we prove that there exists an exponential gap between quantum (even probabilistic) communication complexity and classical deterministic communication complexity of some specific versions of the disjointness problem. Klauck [Kla00] proved, for any language, that the state complexity of exact quantum/classical finite automata, which is a general model of one-way quantum finite automata, is not less than the state complexity of an equivalent one-way deterministic finite automata (1DFA). In this paper we show, using a communication complexity result, that situation may be different for some promise problems. Namely, we show for certain promise problem that the gap between the state complexity of exact one-way quantum finite automata and 1DFA can be exponential.
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.
Deutsch-Jozsa (DJ) problem is one of the most important problems demonstrating the power of quantum algorithm. DJ problem can be described as a Boolean function fff: {0,1}n→{0,1}\{0,1\}^n\rightarrow \{0,1\}{0,1}n→{0,1} with promising it is either constant or balanced, and the purpose is to determine which type it is. DJ algorithm can solve it exactly with one query. In this paper, we first discover the inherent structure of DJ problem in distributed scenario by giving a number of equivalence characterizations between fff being constant (balanced) and some properties of fff's subfunctions, and then we propose three distributed exact quantum algorithms for solving DJ problem. Our algorithms have essential acceleration over distributed classical deterministic algorithm, and can be extended to the case of multiple computing nodes. Compared with DJ algorithm, our algorithms can reduce the number of qubits and the depth of circuit implementing a single query operator. Therefore, we find that the structure of problem should be clarified for designing distributed quantum algorithm to solve it.
Communication complexity has become a central completity model.In that model, we count the amount of communication bits needed between two parties in order to solve certain computational problems.We show that for certain communication complezity problems quantum communication protocols are exponentially faster than classical ores.More explicitly, we give an example for a communication complexity relation (0~ promise problem) P such that: 1) The quantum communication complexity of P is O(log m). 2) The classical probabilistic communication complexity of P is Q(m'l'/ logm).(where m is the length of the inputs).This gives an ezponential gap between quantum communication complexity and classical probabilistic communication complexity.Only a quadratic gap was previously known.Our problem P is of geometrical nature, and is a finite precision variation of the following problem: Player I gets as input a unit vector z E R" and two orthogonal subspaces MO, MI c R". Player II gets as input an orthogonal matrixT : R" + R".Their goal is to answer 0 if T(x) E MO and 1 if T(x) E M,, (and any an~luer in any other case).We give an almost tight analysis for the quantum communication complexity and for the classical-probabilistic communication complexity of this problem.
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 .
The original Deutsch–Jozsa (oDJ) problem is for an oracle (realized here as a database) of size N , where, according to their claim, the deterministic solution of the problem on a classical Turing computer requires O( N ) computational complexity. They produced the famous Deutsch–Jozsa quantum algorithm that offered an exponential speed-up over the classical computer, namely O[log( N )] complexity for the solution in a quantum computer. In this paper, the problem is implemented on an instantaneous noise-based logic processor. It is shown that, similarly to the quantum algorithm, the oDJ problem can deterministically be solved with O[log( N )] complexity. The implication is that by adding a truly random coin to a classical Turing machine and using this classical-physical algorithm can also speed up the deterministic solution of the Deutsch–Jozsa problem exponentially, similarly to the quantum algorithm. Then it is realized that the same database and the solution of the Deutsch–Jozsa problem can also be realized by using an identical algorithmic structure in a simpler way, even without noise/random coin. The only lost function in this new system, as compared with noise-based logic, is the ability to do generic parallel logic operations over the whole database. As the latter feature is not needed for the oDJ problem, it is concluded that the problem can be solved on a classical computer with O[log( N )] complexity even without a random coin. Therefore, while the oDJ algorithm is a historically important step in the developments of quantum computers, it is insufficient to prove quantum supremacy. Note, there is also a simplified Deutsch–Jozsa problem proposed later, which is more popular in the field; however, it is irrelevant for the present paper.