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

<blockquote>
  <p>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.</p>
</blockquote>

<p>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.</p>

<p>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.</p>

<p>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. </p>

CC BY-SA 3.0
2018-03-23T20:08:55.973Z
2018-03-23T20:08:55.973Z
Eric Bahr
<p>This question is regarding <a href="https://arxiv.org/pdf/1009.5104.pdf" rel="nofollow noreferrer">The Equivalence of Searching and Sampling</a> by Aaronson. In page 4 he makes the following statement,</p>

<blockquote>
  <p>... 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?</p>
</blockquote>

<p>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?</p>

<complexity-classes><quantum-computing><promise-problems>
PromiseBQP and expectation values of operators
biryani
# PromiseBQP and expectation values of operators

(Asked by: username_0 on 2018-02-09)

This question is regarding [The Equivalence of Searching and Sampling](https://arxiv.org/pdf/1009.5104.pdf) 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?

**Tags:** complexity-classes, quantum-computing, promise-problems


---

## 1 answers

### Answer by username_1 on 2018-03-23. Score: 2

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.


---

