Generalizations of the distributed Deutsch-Jozsa promise problem

DOI10.1017/S0960129515000158zbMATH Open1364.68211arXiv1402.7254OpenAlexW2963840356MaRDI 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

• Two-way finite automata with quantum and classical states.
• Title not available (Why is that?)
• Forbidden Intersections
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On hybrid models of quantum finite automata
• Quantum search of spatial regions
• One-way finite automata with quantum and classical states
• Exponentially more concise quantum recognition of non-RMM regular languages
• On the state complexity of semi-quantum finite automata
• The Probabilistic Communication Complexity of Set Intersection
• Rapid solution of problems by quantum computation
• Communication Complexity
• Quantum communication complexity of symmetric predicates
• An information statistics approach to data stream and communication complexity
• Quantum communication complexity
• Complexity measures and decision tree complexity: a survey.
• On the distributional complexity of disjointness
• On quantum and probabilistic communication
• On exact quantum query complexity
• Title not available (Why is that?)
• State succinctness of two-way finite automata with quantum and classical states
• Superiority of exact quantum automata for promise problems
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the power of Las Vegas for one-way communication complexity, OBDDs, and finite automata
• Potential of Quantum Finite Automata with Exact Acceptance
• Power of the interactive proof systems with verifiers modeled by semi-quantum two-way finite automata
• Title not available (Why is that?)
• Exact Quantum Query Complexity of EXACT and THRESHOLD
• Superlinear advantage for exact quantum algorithms

Cited In (13)

• Revisiting Deutsch-Jozsa algorithm
• Testing Boolean Functions Properties
• Lifting query complexity to time-space complexity for two-way finite automata
• From Quantum Query Complexity to State Complexity
• Unary probabilistic and quantum automata on promise problems
• Evaluation of exact quantum query complexities by semidefinite programming
• On a poset of quantum exact promise problems
• Complexity of Promise Problems on Classical and Quantum Automata
• 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
• Quantum Finite Automata: A Modern Introduction

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)