Generalizations of the distributed Deutsch-Jozsa promise problem

DOI10.1017/S0960129515000158zbMATH Open1364.68211OpenAlexW2963840356MaRDI QIDQ2973249FDOQ2973249

Authors: Jozef Gruska, Shenggen Zheng, Daowen Qiu 

Publication date: 3 April 2017

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

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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
• Lifting query complexity to time-space complexity for two-way finite automata
• From quantum query complexity to state complexity
• Complexity of promise problems on classical and quantum automata
• Testing Boolean functions properties
• Evaluation of exact quantum query complexities by semidefinite programming
• Quantum finite automata: a modern introduction
• On a poset of quantum exact promise problems
• Time-Space Complexity Advantages for Quantum Computing
• Application of distributed semi-quantum computing model in phase estimation
• Quantum finite automata: advances on Bertoni's ideas
• On coverings of products of uninitialized sequential quantum machines
• Randomized decision tree complexity of Deutsch-Jozsa problem and a generalization

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)