An application of quantum finite automata to interactive proof systems
From MaRDI portal
Publication:1015813
DOI10.1016/j.jcss.2008.12.001zbMath1183.68350OpenAlexW1959691716MaRDI QIDQ1015813
Tomoyuki Yamakami, Harumichi Nishimura
Publication date: 30 April 2009
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcss.2008.12.001
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (15)
Complexity Bounds of Constant-Space Quantum Computation ⋮ Affine automata verifiers ⋮ Unnamed Item ⋮ Classically time-controlled quantum automata ⋮ Lifting query complexity to time-space complexity for two-way finite automata ⋮ Modeling of RNA secondary structures using two-way quantum finite automata ⋮ Exponentially more concise quantum recognition of non-RMM regular languages ⋮ One-way reversible and quantum finite automata with advice ⋮ Constant-space quantum interactive proofs against multiple provers ⋮ Interactive proofs with quantum finite automata ⋮ Nonuniform families of polynomial-size quantum finite automata and quantum logarithmic-space computation with polynomial-size advice ⋮ Quantum State Complexity of Formal Languages ⋮ Constant-space, constant-randomness verifiers with arbitrarily small error ⋮ Power of the interactive proof systems with verifiers modeled by semi-quantum two-way finite automata ⋮ On hybrid models of quantum finite automata
Cites Work
- Games against nature
- Parallel transport and ``quantum holonomy along density operators
- Multi-oracle interactive protocols with constant space verifiers
- Quantum multi-prover interactive proof systems with limited prior entanglement.
- Quantum automata and quantum grammars
- The computer as a physical system: a microscopic quantum mechanical Hamiltonian model of computers as represented by Turing machines
- Two-way finite automata with quantum and classical states.
- PSPACE has constant-round quantum interactive proof systems
- Interactive proof systems with polynomially bounded strategies
- Polynomial time quantum computation with advice
- Undecidability on quantum finite automata
- Characterizations of 1-Way Quantum Finite Automata
- Parallelization, amplification, and exponential time simulation of quantum interactive proof systems
- Parallel computation for well-endowed rings and space-bounded probabilistic machines
- The Knowledge Complexity of Interactive Proof Systems
- Quantum theory, the Church–Turing principle and the universal quantum computer
- Quantum computations: algorithms and error correction
- Finite state verifiers I
- Finite state verifiers II
- Algebraic methods for interactive proof systems
- IP = PSPACE
- On the Power of Finite Automata with both Nondeterministic and Probabilistic States
- Algorithms and Computation
- Algorithms and Computation
- STACS 2004
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: An application of quantum finite automata to interactive proof systems
