From Quantum Query Complexity to State Complexity

DOI10.1007/978-3-319-13350-8_18zbMath1323.68349arXiv1407.7342OpenAlexW1808882680MaRDI QIDQ2944893

Shenggen Zheng, Dao Wen Qiu

Publication date: 8 September 2015

Published in: Computing with New Resources (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Quantum algorithms and complexity in the theory of computing (68Q12)

Related Items (6)

Time-Space Complexity Advantages for Quantum Computing ⋮ Quantum query as a state decomposition ⋮ Lifting query complexity to time-space complexity for two-way finite automata ⋮ Revisiting Deutsch-Jozsa algorithm ⋮ Promise problems solved by quantum and classical finite automata ⋮ Evaluation of exact quantum query complexities by semidefinite programming

Cites Work

• 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
• Unbounded-error quantum computation with small space bounds
• Multi-letter quantum finite automata: decidability of the equivalence and minimization of states
• Improved constructions of quantum automata
• Improved constructions of mixed state quantum automata
• Quantum automata and quantum grammars
• 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
• Small size quantum automata recognizing some regular languages
• Some formal tools for analyzing quantum automata.
• Potential of Quantum Finite Automata with Exact Acceptance
• Exact Quantum Query Complexity of EXACT and THRESHOLD
• Generalizations of the distributed Deutsch–Jozsa promise problem
• Note on the Succinctness of Deterministic, Nondeterministic, Probabilistic and Quantum Finite Automata
• Characterizations of 1-Way Quantum Finite Automata
• One-Way Finite Automata with Quantum and Classical States
• On quantum and probabilistic communication
• Dense quantum coding and quantum finite automata
• Forbidden Intersections
• Rapid solution of problems by quantum computation
• On the Size of One-way Quantum Finite Automata with Periodic Behaviors
• Communication Complexity
• SOME LANGUAGES RECOGNIZED BY TWO-WAY FINITE AUTOMATA WITH QUANTUM AND CLASSICAL STATES
• On the State Complexity of Semi-quantum Finite Automata
• Quantum lower bounds by polynomials
• Superlinear advantage for exact quantum algorithms

This page was built for publication: From Quantum Query Complexity to State Complexity