Two-way finite automata with quantum and classical states.
From MaRDI portal
Publication:1853472
DOI10.1016/S0304-3975(02)00138-XzbMath1061.68047OpenAlexW2044141959MaRDI QIDQ1853472
Publication date: 21 January 2003
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0304-3975(02)00138-x
Related Items
Lower bounds on the size of semi-quantum finite automata, Unary probabilistic and quantum automata on promise problems, One-Way Finite Automata with Quantum and Classical States, Characterizations of quantum automata, On the Size of One-way Quantum Finite Automata with Periodic Behaviors, Two-way and one-way quantum and classical automata with advice for online minimization problems, Time-Space Complexity Advantages for Quantum Computing, Affine automata verifiers, Complexity of Promise Problems on Classical and Quantum Automata, Quantum Finite Automata: A Modern Introduction, From Quantum Query Complexity to State Complexity, State succinctness of two-way finite automata with quantum and classical states, Classical and Quantum Counter Automata on Promise Problems, Potential of Quantum Finite Automata with Exact Acceptance, Classically time-controlled quantum automata, Quaternionic quantum automata, On the Power of One-Way Automata with Quantum and Classical States, Exact results for accepting probabilities of quantum automata., Lifting query complexity to time-space complexity for two-way finite automata, Classical and Quantum Computations with Restricted Memory, Error-Free Affine, Unitary, and Probabilistic OBDDs, On a Conjecture by Christian Choffrut, Another approach to the equivalence of measure-many one-way quantum finite automata and its application, Algebraic Methods in Quantum Informatics, Generalizations of the distributed Deutsch–Jozsa promise problem, The elusive source of quantum speedup, Exponentially more concise quantum recognition of non-RMM regular languages, Automata theory based on quantum logic: reversibilities and pushdown automata, The complexity of debate checking, Quantum Markov chains: description of hybrid systems, decidability of equivalence, and model checking linear-time properties, Quantum Pushdown Automata with Garbage Tape, SOME LANGUAGES RECOGNIZED BY TWO-WAY FINITE AUTOMATA WITH QUANTUM AND CLASSICAL STATES, Application of distributed semi-quantum computing model in phase estimation, Promise problems solved by quantum and classical finite automata, Quantum finite automata: advances on Bertoni's ideas, Two-tape finite automata with quantum and classical states, Unbounded-error quantum computation with small space bounds, Quantum versus deterministic counter automata, Determination of equivalence between quantum sequential machines, Computation in Sofic Quantum Dynamical Systems, GENERALIZED COUNTERS AND REVERSAL COMPLEXITY, Debates with Small Transparent Quantum Verifiers, Determining the equivalence for one-way quantum finite automata, Interference automata, Some algebraic properties of measure-once two-way quantum finite automata, How does adiabatic quantum computation fit into quantum automata theory?, New Results on the Minimum Amount of Useful Space, An application of quantum finite automata to interactive proof systems, Efficient probability amplification in two-way quantum finite automata, Mathematical logic and quantum finite state automata, Uncountable classical and quantum complexity classes, On the power of two-way multihead quantum finite automata, Languages Recognized with Unbounded Error by Quantum Finite Automata, Looking for Pairs that Hard to Separate: A Quantum Approach, Characterizations of one-way general quantum finite automata, On coverings of products of uninitialized sequential quantum machines, Power of the interactive proof systems with verifiers modeled by semi-quantum two-way finite automata, On hybrid models of quantum finite automata, Computation with multiple CTCs of fixed length and width
Cites Work
- A lower bound for probabilistic algorithms for finite state machines
- Quantum automata and quantum grammars
- Dense quantum coding and a lower bound for 1-way quantum automata
- A Time Complexity Gap for Two-Way Probabilistic Finite-State Automata
- Quantum computations: algorithms and error correction
- Finite state verifiers I
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
