- Authors: D. van Melkebeek and T. Watson.
- Reference: Theory of Computing, 8: 1-51, 2012.
- Earlier version:
Abstract
We give two time- and space-efficient simulations of quantum computations with
intermediate measurements, one by classical randomized computations with
unbounded error and the other by quantum computations that use an arbitrary
fixed universal set of gates. Specifically, our simulations show that every
language solvable by a bounded-error quantum algorithm running in time
t and space s is also solvable by an unbounded-error
randomized algorithm running in time O(t log t) and
space O(s + log t), as well as by a
bounded-error quantum algorithm restricted to use an arbitrary universal set
and running in time O(t polylog t) and
space O(s + log t), provided
the universal set is closed under adjoint.
We also develop a quantum model
that is particularly suitable for the study of general computations with
simultaneous time and space bounds.
As an application of our randomized
simulation we obtain the first nontrivial lower bound for general quantum
algorithms solving problems related to satisfiability.
Our bound applies to MajSAT and
MajMajSAT, which are complete problems for the first and second levels of
the counting hierarchy, respectively. We prove that for every real d
and every positive real ε there exists a real c > 1
such that either:
- MajMajSAT does not have a quantum algorithm with bounded two-sided
error that runs in time nc, or
- MajSAT does not have a quantum algorithm with bounded two-sided error
that runs in time nd and space
n1-ε.
In particular, MajMajSAT cannot be solved by a quantum algorithm with
bounded two-sided error running in time n1+o(1)
and space n1-ε for any positive real ε.
Our lower bounds hold for any reasonable uniform model of quantum
computation, in particular for the model we develop.
