Space-Bounded Quantum Complexity

✍ Scribed by John Watrous

• Publisher: Elsevier Science
• Year: 1999
• Tongue: English
• Weight: 511 KB
• Volume: 59
• Category: Article
• ISSN: 0022-0000
• DOI: 10.1006/jcss.1999.1655

✦ Synopsis

This paper investigates the computational power of space-bounded quantum Turing machines. The following facts are proved for space-constructible space bounds s satisfying s(n)=0(log n):

1. Any quantum Turing machine (QTM) running in space s can be simulated by an unbounded error probabilistic Turing machine (PTM) running in space O(s). No assumptions on the probability of error or running time for the QTM are required, although it is assumed that all transition amplitudes of the QTM are rational.

2. Any PTM that runs in space s and halts absolutely (i.e., has finite worst-case running time) can be simulated by a QTM running in space O(s).

If the PTM operates with bounded error, then the QTM may be taken to operate with bounded error as well, although the QTM may not halt absolutely in this case. In the case of unbounded error, the QTM may be taken to halt absolutely.

We therefore have that unbounded error, space O(s) bounded quantum Turing machines and probabilistic Turing machines are equivalent in power and, furthermore, that any QTM running in space s can be simulated deterministically in NC 2 (2 s ) DSPACE(s 2 ) & DTIME(2 O(s) ). We also consider quantum analogues of nondeterministic and one-sided error probabilistic space-bounded classes and prove some simple facts regarding these classes.