A Quantum Time-Space Lower Bound for the Counting Hierarchy

Details A Quantum Time-Space Lower Bound for the Counting Hierarchy A Quantum Time-Space Lower Bound for the Counting Hierarchy

2007-12-15

arxiv.org/abs/0712.2545v1

Physics

Quantum Physics

25 pages

Scientific paper

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: MajMajSAT does not have a quantum algorithm with bounded two-sided error that runs in time n^c, or MajSAT does not have a quantum algorithm with bounded two-sided error that runs in time n^d and space n^{1-\epsilon}. 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.

Affiliated with

Also associated with

No associations

Rating

A Quantum Time-Space Lower Bound for the Counting Hierarchy 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 A Quantum Time-Space Lower Bound for the Counting Hierarchy, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Quantum Time-Space Lower Bound for the Counting Hierarchy will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-445829