Computer Science – Computational Complexity
Scientific paper
1999-11-16
Computer Science
Computational Complexity
18 pages. Appears in FOCS '99
Scientific paper
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: (1) Any space O(s) uniform family of quantum circuits 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^2) and size 2^(O(s)). The quantum circuits are not required to operate with bounded error and may have depth exponential in s. (2) Any (unbounded error) 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 an unbounded error space O(s) ordinary probabilistic Turing machine, and hence deterministically in space O(s^2).
No associations
LandOfFree
On quantum and classical space-bounded processes with algebraic transition amplitudes does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On quantum and classical space-bounded processes with algebraic transition amplitudes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On quantum and classical space-bounded processes with algebraic transition amplitudes will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-239019