Generalizations of the distributed Deutsch-Jozsa promise problem

DOI10.1017/S0960129515000158MaRDI QIDQ2973249zbMATHOpenAlexFDO

Authors Jozef Gruska, Shenggen Zheng, Daowen Qiu

Publication date 3 April 2017

Published in Mathematical Structures in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1402.7254

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Quantum algorithms and complexity in the theory of computing (68Q12) Quantum computation (81P68)

Abstract: In the {em distributed Deutsch-Jozsa promise problem}, two parties are to determine whether their respective strings $x,yin{0,1}^n$ are at the {em Hamming distance} $H(x,y)=0$ or $H(x,y)=fracn2$. Buhrman et al. (STOC' 98) proved that the exact {em quantum communication complexity} of this problem is $$ while the {em deterministic communication complexity} is $$. 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 $fracn2leqkleqn$, whether $H(x,y)=0$ or $H(x,y)=k$, and show that an exponential gap between exact quantum and deterministic communication complexity still holds if $k$ is an even such that $frac12nleqk<(1-lambda)n$, where $0<lambda<frac12$ is given. We also deal with a promise version of the well-known {em disjointness} problem 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.

Recommendations

• The communication complexity of the Hamming distance problem
• Exponential separation of quantum and classical communication complexity
• Lower Bounds on the Deterministic and Quantum Communication Complexities of Hamming-Distance Problems
• Lower bounds on the deterministic and quantum communication complexity of Hamming-distance problems
• Quantum and classical query complexities for generalized Deutsch-Jozsa problems

Cites work

• scientific article; zbMATH DE number 1579275 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 1011685 (Why is no real title available?)
• scientific article; zbMATH DE number 1502104 (Why is no real title available?)
• scientific article; zbMATH DE number 1775389 (Why is no real title available?)
• scientific article; zbMATH DE number 2182451 (Why is no real title available?)
• An information statistics approach to data stream and communication complexity
• Communication Complexity
• Complexity measures and decision tree complexity: a survey.
• Exact quantum query complexity of EXACT and THRESHOLD
• Exponentially more concise quantum recognition of non-RMM regular languages
• Forbidden Intersections
• On exact quantum query complexity
• On hybrid models of quantum finite automata
• On quantum and probabilistic communication: Las Vegas and one-way protocols
• On the distributional complexity of disjointness
• On the power of Las Vegas for one-way communication complexity, OBDDs, and finite automata
• On the state complexity of semi-quantum finite automata
• One-way finite automata with quantum and classical states
• Potential of quantum finite automata with exact acceptance
• Power of the interactive proof systems with verifiers modeled by semi-quantum two-way finite automata
• Quantum communication complexity
• Quantum communication complexity of symmetric predicates
• Quantum finite automata
• Quantum search of spatial regions
• Rapid solution of problems by quantum computation
• State succinctness of two-way finite automata with quantum and classical states
• Succinctness of two-way probabilistic and quantum finite automata
• Superiority of exact quantum automata for promise problems
• Superlinear advantage for exact quantum algorithms
• The Probabilistic Communication Complexity of Set Intersection
• Two-way finite automata with quantum and classical states.

Cited in

(13)

• Revisiting Deutsch-Jozsa algorithm
• Quantum finite automata: a modern introduction
• Lifting query complexity to time-space complexity for two-way finite automata
• On a poset of quantum exact promise problems
• Time-Space Complexity Advantages for Quantum Computing
• Testing Boolean functions properties
• From quantum query complexity to state complexity
• Complexity of promise problems on classical and quantum automata
• Quantum finite automata: advances on Bertoni's ideas
• Randomized decision tree complexity of Deutsch-Jozsa problem and a generalization
• Application of distributed semi-quantum computing model in phase estimation
• On coverings of products of uninitialized sequential quantum machines
• Evaluation of exact quantum query complexities by semidefinite programming

This page was built for publication: Generalizations of the distributed Deutsch-Jozsa promise problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2973249)