On the complexity of simulating space-bounded quantum computations

DOI10.1007/s00037-003-0177-8zbMath1068.68066OpenAlexW2069609886MaRDI QIDQ1889853

John Watrous

Publication date: 13 December 2004

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00037-003-0177-8

zbMATH Keywords

space complexityspace-bounded computationspace-bounded quantum computation

Mathematics Subject Classification ID

Related Items (17)

Quantum alternation ⋮ Very narrow quantum OBDDs and width hierarchies for classical OBDDs ⋮ Complexity Bounds of Constant-Space Quantum Computation ⋮ Quantum circuits with classical channels and the principle of deferred measurements ⋮ Unnamed Item ⋮ Quantum cryptography beyond quantum key distribution ⋮ A Complete Characterization of Unitary Quantum Space ⋮ Quantum Markov chains: description of hybrid systems, decidability of equivalence, and model checking linear-time properties ⋮ QUANTUM COUNTER AUTOMATA ⋮ Quantum computation with write-only memory ⋮ Unbounded-error quantum computation with small space bounds ⋮ Quantum branching programs and space-bounded nonuniform quantum complexity ⋮ Perturbation gadgets: arbitrary energy scales from a single strong interaction ⋮ Exponential separation of quantum and classical online space complexity ⋮ Nonuniform families of polynomial-size quantum finite automata and quantum logarithmic-space computation with polynomial-size advice ⋮ Quantum State Complexity of Formal Languages ⋮ On hybrid models of quantum finite automata

This page was built for publication: On the complexity of simulating space-bounded quantum computations