Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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.


share|improve this question

1 Answer 1

up vote 4 down vote accepted

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.

share|improve this answer
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" ? –  user13175 Jan 2 '13 at 17:15
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. –  Scott Aaronson Jan 2 '13 at 21:16
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. –  user13175 Jan 3 '13 at 14:51
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...) –  Scott Aaronson Jan 5 '13 at 20:38
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.) –  user13175 Jan 5 '13 at 22:18

Your Answer


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