From quantum query complexity to state complexity
From MaRDI portal
Publication:2944893
Abstract: State complexity of quantum finite automata is one of the interesting topics in studying the power of quantum finite automata. It is therefore of importance to develop general methods how to show state succinctness results for quantum finite automata. One such method is presented and demonstrated in this paper. In particular, we show that state succinctness results can be derived out of query complexity results.
Recommendations
Cites work
- scientific article; zbMATH DE number 1489998 (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?)
- Characterizations of 1-Way Quantum Finite Automata
- Communication Complexity
- Complexity measures and decision tree complexity: a survey.
- Dense quantum coding and quantum finite automata
- Exact quantum query complexity of EXACT and THRESHOLD
- Forbidden Intersections
- Generalizations of the distributed Deutsch-Jozsa promise problem
- Improved constructions of mixed state quantum automata
- Improved constructions of quantum automata
- Multi-letter quantum finite automata: decidability of the equivalence and minimization of states
- Note on the Succinctness of Deterministic, Nondeterministic, Probabilistic and Quantum Finite Automata
- On exact quantum query complexity
- On quantum and probabilistic communication: Las Vegas and one-way protocols
- On the Size of One-way Quantum Finite Automata with Periodic Behaviors
- 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 automata and quantum grammars
- Quantum finite automata
- Quantum lower bounds by polynomials
- Rapid solution of problems by quantum computation
- Small size quantum automata recognizing some regular languages
- Some formal tools for analyzing quantum automata.
- Some languages recognized by two-way finite automata with quantum and classical states
- 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
- Two-way finite automata with quantum and classical states.
- Unbounded-error quantum computation with small space bounds
Cited in
(10)- Superposition as memory: unlocking quantum automatic complexity
- Promise problems solved by quantum and classical finite automata
- Revisiting Deutsch-Jozsa algorithm
- On the state complexity of semi-quantum finite automata
- Lifting query complexity to time-space complexity for two-way finite automata
- Time-Space Complexity Advantages for Quantum Computing
- Quantum state complexity of formal languages
- On the state complexity of semi-quantum finite automata
- Quantum query as a state decomposition
- Evaluation of exact quantum query complexities by semidefinite programming
This page was built for publication: From quantum query complexity to state complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2944893)
