PromiseBQP and expectation values of operators

Question

This question is regarding The Equivalence of Searching and Sampling by Aaronson. In page 4 he makes the following statement,

... a difficult and unsolved meta-question is whether PromiseBPP = PromiseBQP implies SampP = SampBQP. Translated into “physics language,” the question is this: suppose we had an efficient classical algorithm to estimate the expectation value of any observable in quantum mechanics. Would that imply an efficient classical algorithm to simulate any quantum experiment, in the sense of sampling from a probability distribution close to the one quantum mechanics predicts?

I have trouble understanding this statement. From the definition of PromiseBQP I don't see how PromiseBPP = PromiseBQP means an efficient classical algorithm to estimate the expectation value of any observable in quantum mechanics. Any ideas how this connection can be made?

Answer 1

Aaronson is working within a particular context, but if you take his statement in an absolute sense, you're right to be skeptical.

Translated into “physics language,” the question is this: suppose we had an efficient classical algorithm to estimate the expectation value of any observable in quantum mechanics.

This is technically imprecise. PromiseBQP and BQP, as you no doubt understand, are concerned with sampling states that are constructed with polynomial-sized (uniform families of) circuits. And it's true that if you're talking about 'estimating the expectation value of any observable', this seems to include ANY quantum state which may generally require an exponential number of gates to construct.

However, the concerns of a complexity theorist preclude much worrying about such 'exponentially' constructable quantum states. In any 'quantum experiment,' if a state evolves from a particular pure quantum state in a set amount of time t, the expectation value of its observables will be very close to some state that can be constructed from a circuit with a polynomial number of gates.

That is, the complexity theorist paradigm of 'experiments deal with polynomial time constructable states' is realistic for experimental physics in all contexts that I'm familiar with.