Generalizations of the distributed Deutsch–Jozsa promise problem
From MaRDI portal
Publication:2973249
DOI10.1017/S0960129515000158zbMath1364.68211arXiv1402.7254OpenAlexW2963840356MaRDI QIDQ2973249
Jozef Gruska, Shenggen Zheng, Dao Wen 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
Formal languages and automata (68Q45) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Quantum computation (81P68) Quantum algorithms and complexity in the theory of computing (68Q12)
Related Items (12)
Unary probabilistic and quantum automata on promise problems ⋮ Time-Space Complexity Advantages for Quantum Computing ⋮ Complexity of Promise Problems on Classical and Quantum Automata ⋮ Quantum Finite Automata: A Modern Introduction ⋮ From Quantum Query Complexity to State Complexity ⋮ Lifting query complexity to time-space complexity for two-way finite automata ⋮ Revisiting Deutsch-Jozsa algorithm ⋮ 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 ⋮ Evaluation of exact quantum query complexities by semidefinite programming ⋮ Testing Boolean Functions Properties
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- State succinctness of two-way finite automata with quantum and classical states
- Superiority of exact quantum automata for promise problems
- Exponentially more concise quantum recognition of non-RMM regular languages
- An information statistics approach to data stream and communication complexity
- Quantum communication complexity
- On the distributional complexity of disjointness
- Two-way finite automata with quantum and classical states.
- Complexity measures and decision tree complexity: a survey.
- On the power of Las Vegas for one-way communication complexity, OBDDs, and finite automata
- Power of the interactive proof systems with verifiers modeled by semi-quantum two-way finite automata
- On exact quantum query complexity
- On hybrid models of quantum finite automata
- Potential of Quantum Finite Automata with Exact Acceptance
- Exact Quantum Query Complexity of EXACT and THRESHOLD
- One-Way Finite Automata with Quantum and Classical States
- On quantum and probabilistic communication
- Forbidden Intersections
- The Probabilistic Communication Complexity of Set Intersection
- Rapid solution of problems by quantum computation
- Quantum communication complexity of symmetric predicates
- Communication Complexity
- On the state complexity of semi-quantum finite automata
- Superlinear advantage for exact quantum algorithms
This page was built for publication: Generalizations of the distributed Deutsch–Jozsa promise problem
