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!
Things that imply BQP Derandomization
cc.complexity theory;quantum computing
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.