## Provably intractable problems

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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?

-

For PSPACE $\subset$ SPACE(f(n)), see en.wikipedia.org/wiki/Space_hierarchy_theorem – Ricky Demer Jul 10 2010 at 21:44

## 1 Answer

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.

-

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 2010 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 2010 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 2010 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 2010 at 5:44
I managed to work out the proof without having to use that. – Ricky Demer Jul 11 2010 at 8:02
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 23, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9062830209732056, "perplexity_flag": "head"}