From quantum query complexity to state complexity

DOI10.1007/978-3-319-13350-8_18zbMATH Open1323.68349arXiv1407.7342OpenAlexW1808882680MaRDI QIDQ2944893FDOQ2944893

Authors: Shenggen Zheng, Daowen Qiu 

Publication date: 8 September 2015

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

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.

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

Recommendations

• On the state complexity of semi-quantum finite automata
• On the state complexity of semi-quantum finite automata
• Quantum state complexity of formal languages
• State succinctness of two-way finite automata with quantum and classical states
• Nonuniform families of polynomial-size quantum finite automata and quantum logarithmic-space computation with polynomial-size advice

Mathematics Subject Classification ID

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

Cites Work

• Two-way finite automata with quantum and classical states.
• Forbidden Intersections
• Title not available (Why is that?)
• Succinctness of two-way probabilistic and quantum finite automata
• Unbounded-error quantum computation with small space bounds
• One-way finite automata with quantum and classical states
• Rapid solution of problems by quantum computation
• Communication Complexity
• Complexity measures and decision tree complexity: a survey.
• Quantum lower bounds by polynomials
• On quantum and probabilistic communication: Las Vegas and one-way protocols
• On exact quantum query complexity
• Title not available (Why is that?)
• Improved constructions of quantum automata
• Quantum automata and quantum grammars
• Characterizations of 1-Way Quantum Finite Automata
• Dense quantum coding and quantum finite automata
• 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?)
• Some languages recognized by two-way finite automata with quantum and classical states
• Quantum finite automata
• Small size quantum automata recognizing some regular languages
• Some formal tools for analyzing quantum automata.
• On the state complexity of semi-quantum finite automata
• On the power of Las Vegas for one-way communication complexity, OBDDs, and finite automata
• Potential of quantum finite automata with exact acceptance
• Improved constructions of mixed state quantum automata
• On the Size of One-way Quantum Finite Automata with Periodic Behaviors
• Multi-letter quantum finite automata: decidability of the equivalence and minimization of states
• Power of the interactive proof systems with verifiers modeled by semi-quantum two-way finite automata
• Title not available (Why is that?)
• Generalizations of the distributed Deutsch-Jozsa promise problem
• Note on the Succinctness of Deterministic, Nondeterministic, Probabilistic and Quantum Finite Automata
• Exact quantum query complexity of EXACT and THRESHOLD
• Superlinear advantage for exact quantum algorithms

Cited In (10)

• On the state complexity of semi-quantum 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
• Quantum query as a state decomposition
• Promise problems solved by quantum and classical finite automata
• Quantum state complexity of formal languages
• Evaluation of exact quantum query complexities by semidefinite programming
• Superposition as memory: unlocking quantum automatic complexity
• Time-Space Complexity Advantages for Quantum Computing

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)