arXiv:cs/9911008 · Annual Symposium on Foundations of Computer Science

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

John Watrous

Published Jan 20, 2003• 10 citations

Abstract

We define a class of stochastic processes based on evolutions and measurements of quantum systems, and consider the complexity of predicting their long term behavior. It is shown that a very general class of decision problems regarding these stochastic processes can be efficiently solved classically in the space-bounded case. The following corollaries are implied by our main result for any space-constructible space bound s satisfying s(n)=/spl Omega/(log n): (i) any space O(s) uniform family of quantum circuit acting on s qubits and consisting of unitary gates and measurement gates defined in a typical way by matrices of algebraic numbers can be simulated by an unbounded error space O(s) ordinary (i.e., fair-coin flipping) probabilistic Turing machine, and hence by space O(s) uniform classical (deterministic) circuits of depth O(s/sup 2/) and size 2/sup 0/(s); (2) any quantum Turing machine running in space s, having arbitrary algebraic transition amplitudes, allowing unrestricted measurements during its computation, and having no restrictions on running time can be simulated by a space O(s) ordinary probabilistic Turing machine in the unbounded error setting. We also obtain the following classical result: any unbounded error probabilistic Turing machine running in space s that allows algebraic probabilities and algebraic cut-point can be simulated by a space O(s) ordinarily probabilistic Turing machine with cut-point 1/2. Our technique for handling algebraic numbers in the above simulations may be of independent interest. It is shown that any real algebraic number can be accurately approximated by a ratio of GapL functions.

DOI: 10.1109/sffcs.1999.814605

Related papers

Relationships between quantum and classical space-bounded complexity classes

John Watrous

This paper investigates the relative power of space-bounded quantum and classical (probabilistic) computational models. The following relationships are proved. 1. Any probabilistic Turing machine (PTM) which runs in space s and which halts absolutely (i.e. halts with certainty after a finite number of steps) can be simulated in space O(s) by a quantum Turing machine (QTM). 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 unbounded error case, the QTM may be taken to halt absolutely. 2. Any QTM running in space s can be simulated by an unbounded error PTM running in space O(s). No assumptions on the probability of error or Turing time for the QTM are required, but it is assumed that all transition amplitudes of the quantum machine are rational. It follows that unbounded error, space O(s) bounded quantum Turing machines and probabilistic Turing machines are equivalent in power. This 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 simulated in NC/sup 2/ We also consider quantum analogues of nondeterministic and one-sided error probabilistic space-bounded classes, and prove some simple relationships regarding these classes.

IEEE Conference on Computational Complexity (CCC)Nov 27, 200215 citations

Space-bounded quantum computation

John Watrous, Eric Bach

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 logarithmic in the input size. For such space-bounds, it is shown that quantum Turing machines and probabilistic Turing machines are equivalent in power in the unbounded-error setting, in the sense that each model may simulate the other with at most a constant factor increase in space. From this, it follows that any quantum Turing machine computation can be simulated deterministically with at most a quadratic increase in space, and can be simulated deterministically in time at most exponential in the space-bound. Several other facts regarding quantum complexity classes defined in terms of such space-bounds are also proved. Second, we consider the power of quantum Turing machines restricted to constant space. In this case, we first prove that quantum Turing machines having one-sided error and running in linear time are strictly more powerful than probabilistic Turing machines having either one-sided error or having two-sided bounded error and running in polynomial time. Second, we prove that exact (i.e., accepting with probability 0 or 1) constant-space quantum Turing machines upon which no restrictions on running time are placed can recognize languages that cannot be recognized by any bounded-error constant-space probabilistic Turing machine. ii Acknowledgements I would like to take this opportunity to express my gratitude to a number of people. First, I would like to thank my advisor Eric Bach for all that he has taught me, regarding both theoretical computer science and how to be a researcher in general. His advice and support are greatly appreciated. I would also like to thank Anne Condon for her great advice and for many helpful discussions during my years as a graduate student. This dissertation has benefitted greatly from comments and suggestions by Anne and Eric as well.

Jan 1, 199820 citations

Quantum simulations of classical random walks and undirected graph connectivity

John Watrous

There are a number of questions in quantum complexity that have been resolved in the time-bounded setting, but remain open in the space-bounded setting. For example, it is not currently known if space-bounded probabilistic computations can be simulated by space-bounded quantum machines without allowing measurements during the computation, while it is known that an analogous statement holds in the time-bounded case. A more general question asks if measurements during a quantum computation can allow for more space-efficient solutions to certain problems. In this paper we show 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. By means of such simulations, it is demonstrated 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. It follows that symmetric logspace is contained in the quantum analogue of randomized logspace, i.e., SL/spl sube/QR/sub H/L.

IEEE Conference on Computational Complexity (CCC)Jan 20, 20035 citations

Quantum Circuits That Can Be Simulated Classically in Polynomial Time

Leslie Gabriel Valiant

A model of quantum computation based on unitary matrix operations was introduced by Feynman and Deutsch. It has been asked whether the power of this model exceeds that of classical Turing machines. We show here that a significant class of these quantum computations can be simulated classically in polynomial time. In particular we show that two-bit operations characterized by 4 × 4 matrices in which the sixteen entries obey a set of five polynomial relations can be composed according to certain rules to yield a class of circuits that can be simulated classically in polynomial time. This contrasts with the known universality of two-bit operations and demonstrates that efficient quantum computation of restricted classes is reconcilable with the Polynomial Time Turing Hypothesis. Therefore, it is possible that, The techniques introduced bring the quantum computational model within the realm of algebraic complexity theory. In a manner consistent with one view of quantum physics, the wave function is simulated deterministically, and randomization arises only in the course of making measurements. The results generalize the quantum model in that they do not require the matrices to be unitary. In a different direction these techniques also yield deterministic polynomial time algorithms for the decision and parity problems for certain classes of read-twice Boolean formulae. All our results are based on the use of gates that are defined in terms of their graph matching properties.

SIAM Journal on ComputingJan 1, 2002310 citations

Quantum computers that can be simulated classically in polynomial time

Leslie Gabriel Valiant

A model of quantum computation based on unitary matrix operations was introduced by Feynman and Deutsch. It has been asked whether the power of this model exceeds that of classical Turing machines. We show here that a significant class of these quantum computations can be simulated classically in polynomial time. In particular we show that two-bit operations characterized by 4 \times 4 matrices in which the sixteen entries obey a set of five polynomial relations can be composed according to certain rules to yield a class of circuits that can be simulated classically in polynomial time. This contrasts with the known universality of two-bit operations, and demonstrates that efficient quantum computation of restricted classes is reconcilable with the Polynomial Time Turing Hypothesis. In other words it is possible that quantum phenomena can be used in a scalable fashion to make computers but that they do not have superpolynomial speedups compared to Turing machines for any problem. The techniques introduced bring the quantum computational model within the realm of algebraic complexity theory. In a manner consistent will one view of quantum physics, the wave function is simulated deterministically, and randomization arises only in the course of making measurements. The results generalize the quantum model in that they do not require the matrices to be unitary. In a different direction these techniques also yield deterministic polynomial time algorithms for the decision and parity problems for certain classes of read-twice Boolean formulae. All our results are based on the use of gates that are defined in terms of their graph matching properties.

ACM Symposium on Theory of Computing (STOC)Jul 6, 200178 citations

Quantum simulations of classical random walks and undirected graph connectivity

John Watrous

It is not currently known if quantum Turing machines can efficiently simulate probabilistic computations in the space-bounded case. In this paper we show that space-bounded quantum Turing machines can efficiently simulate a limited class of random processes: random walks on undirected graphs. By means of such simulations, it is demonstrated that the undirected graph connectivity problem for regular graphs can be solved by one-sided error quantum Turing machines that run in logspace and halt absolutely. It follows that symmetric logspace is contained in the quantum analogue of randomized logspace.

arXiv:cs/9812012Dec 11, 19981 citation