6
$\begingroup$

I am aware that it is generally believed that P = BPP, but BQP != P (since factoring is in BQP, and factoring seems hard.)

For BPP, we have the hardness vs randomness result: which states that circuit lower bounds for EXP imply derandomization results for BPP.

Even though I do not expect BQP to be simulatable in sub-exponential time, I am curious if there are any implication results along the lines of "If pigs can whistle, than donkeys can fly."

Formally, I'm asking if there exists provable statements of the form:

If [XYZ] then BQP can be simulated in sub-exponential time.

Ideally, [XYZ] would be about the hardness of certain problems against certain complexity classes. However, any XYZ not of the form "BQP can be simulated in sub-exponential time" would be interesting.

Thanks!

Improve this question
$\endgroup$

1 Answer 1

Reset to default
6
$\begingroup$

Interesting! I don't know of any nontrivial result of that kind -- neither one that says "if [XYZ] then BPP=BQP", nor one that says "if [XYZ] then BQP ⊆ BPTIME(2o(n))." The closest I can think of is a result of Terhal and DiVincenzo, who showed that if constant-depth quantum sampling can be efficiently classically simulated then BQP ⊆ AM. (Later work, by Bremner-Jozsa-Shepherd and myself and Arkhipov, shows that the same assumption would even imply P#P = BPPNP.) Combining that with some assumption that gave AM ⊆ BPTIME(2o(n)) would then yield what you wanted.

Improve this answer
$\endgroup$
5
  • $\begingroup$ So is the best we have: "if quantumness can be simulated, then ...". Thus, do we not have a statement of the form: "If (EXP is not contained in subexp quantum w/ subexp quantum advice) then BQP is in subexp time" ? $\endgroup$
    – user13175
    Jan 2, 2013 at 17:15
  • $\begingroup$ Well, EXP can't be contained in deterministic subexponential time, because of the Time Hierarchy Theorem. EXP could be contained in BPSUBEXP. And if so, then it would indeed follow that BQP was in BPSUBEXP, but merely because BQP is contained in EXP! So I didn't count that as a "nontrivial" example of the sort of result you were looking for. $\endgroup$
    – Scott Aaronson
    Jan 2, 2013 at 21:16
  • $\begingroup$ I think I'm asking something different. Hardness vs Randomness states: if EXP does not have sub-exp size circuits, then BPP can be simulated in polynomial time. I'm interested if there's a statement of the form: if EXP does not have sub-exp size quantum circuits, then BQP can be simulated in subexp time. $\endgroup$
    – user13175
    Jan 3, 2013 at 14:51
  • 1
    $\begingroup$ Ah, sorry! No, I don't know of any result of that form (and would consider it quite unlikely, as someone who believes both that EXP doesn't have subexp-size quantum circuits and that BQP can't be simulated in subexp time...) $\endgroup$
    – Scott Aaronson
    Jan 5, 2013 at 20:38
  • $\begingroup$ All is clear now. Thanks! (My intuition agrees with your intuition, but I wanted to double check as complexity has destroyed faith in things I can't prove.) $\endgroup$
    – user13175
    Jan 5, 2013 at 22:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.