Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR08-017 | 16th December 2007 00:00

A Quantum Time-Space Lower Bound for the Counting Hierarchy

RSS-Feed




TR08-017
Authors: Thomas Watson, Dieter van Melkebeek
Publication: 1st March 2008 00:36
Downloads: 3564
Keywords: 


Abstract:

We obtain the first nontrivial time-space lower bound for 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 $\epsilon$ there exists a real $c>1$ such that either:
\begin{itemize}
\item MajMajSAT does not have a quantum algorithm with bounded two-sided error that runs in time $n^c$, or
\item MajSAT does not have a quantum algorithm with bounded two-sided error that runs in time $n^d$ and space $n^{1-\epsilon}$.
\end{itemize}
In particular, MajMajSAT cannot be solved by a quantum algorithm with bounded two-sided error running in time $n^{1+o(1)}$ and space $n^{1-\epsilon}$ for any $\epsilon>0$.

The key technical novelty is a time- and space-efficient simulation of quantum computations with intermediate measurements by probabilistic machines with unbounded error. We also develop a model that is particularly suitable for the study of general quantum computations with simultaneous time and space bounds. However, our arguments hold for any reasonable uniform model of quantum computation.



ISSN 1433-8092 | Imprint