Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let f(n) be a space-constructible superpolynomial function. Then BQP $\subseteq$ PSPACE $\subset$ SPACE(f(n)), so in particular, SPACE(f(n)) $\not\subseteq$ BQP. Let L be a problem such that every problem in SPACE(f(n)) is BQP-reducible to L. Then L $\notin$ BQP.

Are there any problems that have been proven to not be in BQP for which that is not known to be provable by the above method?

share|improve this question
For PSPACE $\subset$ SPACE(f(n)), see en.wikipedia.org/wiki/Space_hierarchy_theorem –  Ricky Demer Jul 10 '10 at 21:44
add comment

1 Answer

up vote 5 down vote accepted

There are few complexity class separations known which do not follow from some type of diagonalization (a complexity hierarchy theorem of some kind). I know of none for $\mathbf{BQP}$. One canonical example of a separation that doesn't seem to follow from a diagonalization argument is $\mathbf{AC}^0 \subsetneq \mathbf{NC}^1$, which instead follows from the Ajtai-Furst-Saxe-Sipser theorem that the parity of $n$ bits does not have polynomial size circuits of unbounded fan-in and constant depth.

Now, if by "the above method" you meant something more specific than just diagonalization, then there is just a little something else you can say about $\mathbf{BQP}$. Adleman, DeMarrais, and Huang proved that $\mathbf{BQP} \subseteq \mathbf{PP}$:

Leonard M. Adleman, Jonathan DeMarrais, Ming-Deh A. Huang: Quantum Computability. SIAM J. Comput. 26(5): 1524-1540 (1997)

(Recall that $\mathbf{PP}$ consists of languages recognized by randomized polynomial time algorithms with "exponential precision". Without loss of generality, we may say that an input is "accepted" by such an algorithm if and only if the probability of outputting $1$ is strictly greater than $1/2$. Note this probability could be $1/2+1/2^{n^{\Omega(1)}}$. It is known that $\mathbf{PP} \subseteq \mathbf{PSPACE}$, but the other direction is unknown.)

Just like $\mathbf{PSPACE}$ has a superpolynomial analogue $\mathbf{SPACE}(f(n))$, $\mathbf{PP}$ has a superpolynomial analogue $\mathbf{PTIME}(f(n))$, so in your above argument you can replace $\mathbf{SPACE}(f(n))$ with $\mathbf{PTIME}(f(n))$. Note the latter is contained in the former.

share|improve this answer
By "the above method", I meant space hierarchy theorem with PSPACE at the bottom. I did know BQP $\subseteq$ PP, slightly better is BQP $\subseteq$ AWPP. The relevant questions are how good are the hierarchy theorems for PTIME and AWPTIME. –  Ricky Demer Jul 11 '10 at 2:32
For PTIME(f), since there is an effectively computable list of all PTIME(f) machines, the time hierarchy will be quite tight, certainly no worse than the hierarchy for DTIME(f). On the other hand, AWPP is a "semantic" class and so I'd imagine the known time hierarchies there would mimic that of BPP and other such classes. They are strictly weaker. A pretty good survey of these issues can be found at: eccc.hpi-web.de/report/2007/004 –  Ryan Williams Jul 11 '10 at 3:47
The issue I can't find a way around is that switching the answer of each path won't change the answer the machine gives if the paths split exactly. –  Ricky Demer Jul 11 '10 at 4:54
Let p in (0,1) be arbitrary. One can redefine PP so that the acceptance condition becomes: probability of outputting 1 in the algorithm is strictly greater than p. (Consider what happens when you allow an exponential number of extra "dummy" computation paths that ignore the input and always accept...) This makes it easy to do the complementation. –  Ryan Williams Jul 11 '10 at 5:44
I managed to work out the proof without having to use that. –  Ricky Demer Jul 11 '10 at 8:02
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.