# Space-Bounded Quantum Complexity

@article{Watrous1999SpaceBoundedQC, title={Space-Bounded Quantum Complexity}, author={John Watrous}, journal={J. Comput. Syst. Sci.}, year={1999}, volume={59}, pages={281-326} }

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)=?(logn): 1.Any quantum Turing machine (QTM) running in space s can be simulated by an unbounded error probabilistic Turing machine (PTM) run- ning 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… Expand

#### 67 Citations

Unbounded-error quantum computation with small space bounds

- Computer Science, Physics
- Inf. Comput.
- 2011

It turns out that these automata are equal in power to their probabilistic counterparts, and this fact does not change when the QFA model is augmented to allow general measurements and mixed states. Expand

Classical and quantum computation with small space bounds (PhD thesis)

- Computer Science, Physics
- ArXiv
- 2011

A new quantum Turing machine (QTM) model that supports general quantum operators, together with its pushdown, counter, and finite automaton variants, is introduced, and the computational power of classical and quantum machines using small space bounds in many different cases is examined. Expand

Time-Space Efficient Simulations of Quantum Computations

- Computer Science, Mathematics
- Theory Comput.
- 2010

The first nontrivial lower bound for general quantum algorithms solving problems related to satisfiability is obtained and applies to MAJSAT and MAJMAJSAT, which are the problems of determining the truth. Expand

Quantum branching programs and space-bounded nonuniform quantum complexity

- Computer Science, Mathematics
- Theor. Comput. Sci.
- 2005

It is shown that non-uniform quantum Turing machines with algebraic amplitudes and QBPs with a suitable analogous set of amplitudes are equivalent in computational power if both models work with bounded or unbounded error. Expand

On quantum and classical space-bounded processes with algebraic transition amplitudes

- Mathematics, Computer Science
- 40th Annual Symposium on Foundations of Computer Science (Cat. No.99CB37039)
- 1999

A class of stochastic processes based on evolutions and measurements of quantum systems, and the complexity of predicting their long term behavior is considered, is defined, and any real algebraic number can be accurately approximated by a ratio of GapL functions. Expand

A Quantum Time-Space Lower Bound for the Counting Hierarchy

- Computer Science, Mathematics
- Electron. Colloquium Comput. Complex.
- 2008

The first nontrivial time-space lower bound for quantum algorithms solving problems related to satisfiability is obtained and it is proved that for every real d and every positive real ǫ there exists a real c > 1 such that MajSAT cannot be solved by a quantum algorithm with bounded two-sided error. Expand

Quantum Simulations of Classical Random Walks and Undirected Graph Connectivity

- Computer Science, Physics
- J. Comput. Syst. Sci.
- 2001

This paper shows that space-bounded quantum Turing machines can efficiently simulate a limited class of random processes-random walks on undirected graphs-without relying on measurements during the computation, and demonstrates that the Undirected graph connectivity problem for regular graphs can be solved by one-sided error quantum Turing Machines that run in logspace and require a single measurement at the end of their computations. Expand

Quantum simulations of classical random walks and undirected graph connectivity

- Computer Science
- Proceedings. Fourteenth Annual IEEE Conference on Computational Complexity (Formerly: Structure in Complexity Theory Conference) (Cat.No.99CB36317)
- 1999

This paper shows that space-bounded quantum Turing machines can efficiently simulate a limited class of random processes-random walks on undirected graphs-without relying on measurements during the computation, and demonstrates that the Undirected graph connectivity problem for regular graphs can be solved by one-sided error quantum Turing Machines that run in logspace and require a single measurement at the end of their computations. Expand

Turing-equivalent automata using a fixed-size quantum memory

- Computer Science, Physics
- ArXiv
- 2012

A new public quantum interactive proof system and the first quantum alternating Turing machine are introduced, obtained from their classical counterparts by augmenting them with a fixed-size quantum register, and it is shown that any Turing-recognizable language can be recognized by a constant-space qATM even with one-way input head. Expand

Exponential separation of quantum and classical online space complexity

- Mathematics, Physics
- SPAA '06
- 2006

This paper introduces a very natural and simple model of a space-bounded quantum online machine and proves an exponential separation of classical and quantum online space complexity, in the bounded-error setting and for a total language. Expand

#### References

SHOWING 1-10 OF 42 REFERENCES

Relationships between quantum and classical space-bounded complexity classes

- Mathematics, Computer Science
- Proceedings. Thirteenth Annual IEEE Conference on Computational Complexity (Formerly: Structure in Complexity Theory Conference) (Cat. No.98CB36247)
- 1998

It follows that unbounded error, space O(s) bounded quantum Turing machines and probabilistic Turing machines are equivalent in power, which implies that any space s QTM can be simulated deterministically in space O (s/sup 2/), and further that any (unbounded-error) QTM running in log-space can be simulation in NC/Sup 2/. Expand

Space-bounded quantum computation

- Mathematics
- 1998

In this dissertation, we investigate the computational power of quantum Turing machines operating in bounded space.
First, we consider space-bounds that are space-constructible and at least… Expand

Quantum complexity theory

- Computer Science
- STOC '93
- 1993

This dissertation proves that relative to an oracle chosen uniformly at random, the class NP cannot be solved on a quantum Turing machine in time $o(2\sp{n/2}).$ and gives evidence suggesting that quantum Turing Machines cannot efficiently solve all of NP. Expand

Oracle Quantum Computing

- Mathematics
- Workshop on Physics and Computation
- 1992

This paper continues the study of the power of oracles to separate quantum com.plexity classes from classical (including probabilistic and nondeterministic) complexity classes, which we initiated in… Expand

Space-bounded hierarchies and probabilistic computations

- Computer Science
- STOC '82
- 1982

Two aspects of the power of space-bounded probabilistic Turing machines are studied, one of which raises interesting questions about space hierarchies, and the other demonstrates that any language in the log n space hierarchy can be recognized by an log n Space Turing machine with small error. Expand

On the power of quantum finite state automata

- Mathematics, Computer Science
- Proceedings 38th Annual Symposium on Foundations of Computer Science
- 1997

It is proved that the class of languages recognizing by linear time, bounded error 2qfa's properly includes the regular languages, and 1-way and 2-way quantum finite state automata are introduced, which are the quantum analogues of deterministic, nondeterministic and probabilistic 1- way and2-way finite state Automata. Expand

Quantum Circuit Complexity

- Mathematics, Computer Science
- FOCS
- 1993

It is shown that any function computable in polynomial time by a quantum Turing machine has aPolynomial-size quantum circuit, and this result enables us to construct a universal quantum computer which can simulate a broader class of quantum machines than that considered by E. Bernstein and U. Vazirani (1993), thus answering an open question raised by them. Expand

Quantum theory, the Church–Turing principle and the universal quantum computer

- Mathematics
- Proceedings of the Royal Society of London. A. Mathematical and Physical Sciences
- 1985

It is argued that underlying the Church–Turing hypothesis there is an implicit physical assertion. Here, this assertion is presented explicitly as a physical principle: ‘every finitely realizible… Expand

Parallel Computation for Well-Endowed Rings and Space-Bounded Probabilistic Machines

- Computer Science
- Inf. Control.
- 1983

The method introduces a generalization of the ring of integers, called well-endowed rings, which possesses a very efficient parallel implementation of the basic (+,−,×) ring operations. Expand

Time/Space Trade-Offs for Reversible Computation

- Mathematics, Computer Science
- SIAM J. Comput.
- 1989

Using a pebbling argument, this paper shows that, for any $\varepsilon > 0$, ordinary multitape Turing machines using time T and space S can be simulated by reversible ones using time $O(T^{1 + \varpsilon } )$ and space $O (S\log T)$ or in linear time and space$O(ST^\varePSilon )$. Expand