Nonuniform families of polynomial-size quantum finite automata and quantum logarithmic-space computation with polynomial-size advice

DOI10.1007/978-3-030-13435-8_10zbMath1425.68238arXiv1907.02916OpenAlexW2963378357MaRDI QIDQ5919277

Tomoyuki Yamakami

Publication date: 4 December 2019

Published in: Information and Computation, Language and Automata Theory and Applications (Search for Journal in Brave)

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

zbMATH Keywords

state complexityquantum finite automataquantum Turing machinequantum advicebounded-error probabilitynonuniform state complexityflexible garbage tapesuper quantum finite automata

Mathematics Subject Classification ID

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

Related Items (4)

Quantum logical depth and shallowness of streaming data by one-way quantum finite-state transducers (preliminary report) ⋮ Special issue: Selected papers of the 13th international conference on language and automata theory and applications, LATA 2019 ⋮ Unambiguity and fewness for nonuniform families of polynomial-size nondeterministic finite automata ⋮ How does adiabatic quantum computation fit into quantum automata theory?

Cites Work

• Unnamed Item
• Unnamed Item
• 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
• Size lower bounds for quantum automata
• Superiority of exact quantum automata for promise problems
• One-way reversible and quantum finite automata with advice
• Promise problems solved by quantum and classical finite automata
• Two-way unary automata versus logarithmic space
• Unbounded-error quantum computation with small space bounds
• Turing machines that take advice
• An application of quantum finite automata to interactive proof systems
• Improved constructions of quantum automata
• Theory of one-tape linear-time Turing machines
• Quantum automata and quantum grammars
• Parameterized graph connectivity and polynomial-time sub-linear-space short reductions (preliminary report)
• Quantum computation with write-only memory
• On the complexity of simulating space-bounded quantum computations
• Space-bounded quantum complexity
• Two-way automata versus logarithmic space
• Relativizations of nonuniform quantum finite automata families
• Supportive oracles for parameterized polynomial-time sub-linear-space computations in relation to L, NL, and P
• Two-way automata characterizations of L/poly versus NL
• Polynomial time quantum computation with advice
• Interactive proofs with quantum finite automata
• Complexity of Promise Problems on Classical and Quantum Automata
• THE ROLES OF ADVICE TO ONE-TAPE LINEAR-TIME TURING MACHINES AND FINITE AUTOMATA
• Characterizations of 1-Way Quantum Finite Automata
• A Time Complexity Gap for Two-Way Probabilistic Finite-State Automata
• Size Complexity of Two-Way Finite Automata
• Quantum Complexity Theory
• Lower space bounds for randomized computation
• On the state complexity of semi-quantum finite automata
• Nondeterminism and the size of two way finite automata
• Inverting well conditioned matrices in quantum logspace
• Quantum State Complexity of Formal Languages
• State complexity characterizations of parameterized degree-bounded graph connectivity, sub-linear space computation, and the linear space hypothesis
• Analogies and differences between quantum and stochastic automata

This page was built for publication: Nonuniform families of polynomial-size quantum finite automata and quantum logarithmic-space computation with polynomial-size advice