<p>The principle of deferred measurement (see <a href="https://en.wikipedia.org/wiki/Deferred_Measurement_Principle" rel="noreferrer">https://en.wikipedia.org/wiki/Deferred_Measurement_Principle</a>) tells us that measurements in the middle of a quantum computation can be simulated by using additional quantum gates instead. In particular, instead of measuring a qubit, we can apply a CNOT gate to that qubit and another qubit (which is used only at this point of the computation).</p>

CC BY-SA 3.0
2017-04-06T07:04:57.863Z
2017-04-06T07:04:57.863Z
Mikhail Rudoy
<p>BQP as usually defined is: the class of decision problems solvable by a quantum computer in polynomial time, with an error probability of at most 1/3 for all instances.</p>

<p>Just like BPP, the choice of 1/3 in the definition is arbitrary because we could just have a "higher level" algorithm that runs the "basic algorithm" many times and take a majority vote to achieve higher probability of correctness.</p>

<p>I can imagine this as:</p>

<ol>
<li><p>initialize qbits based on the input of length n</p></li>
<li><p>apply polynomial(n) quantum gates</p></li>
<li><p>measure output qbit</p></li>
<li><p>repeat steps 1-3, K times and report the majority measurement from step 3</p></li>
</ol>

<p>Essentially, having a classical computing loop call a quantum routine K times.</p>

<p>Is it possible instead to somehow do <em>ALL</em> the computation on the quantum computer, and only make a single measurement at the end which is equivalent to this?  </p>

<p>I'd hope for something like:</p>

<ol>
<li><p>initialize qbits based on the input of length n</p></li>
<li><p>apply K * polynomial(n) quantum gates</p></li>
<li><p>measure just a single output qbit</p></li>
</ol>

<p>Or is making multiple measurements absolutely necessary to the computational power here?</p>

CC BY-SA 3.0
2017-04-06T09:15:19.280Z
This question would be better suited for the (non-research level) [Computer Science stackexchange](http://cs.stackexchange.com/).
Niel de Beaudrap
CC BY-SA 3.0
2017-04-06T09:29:40.607Z
@NieldeBeaudrap Sorry. Thank you for letting me know.
PPenguin
<complexity-classes><quantum-computing>
Running multiple rounds of a BQP computation, without multiple measurements?
PPenguin
# Running multiple rounds of a BQP computation, without multiple measurements?

(Asked by: username_0 on 2017-04-05)

BQP as usually defined is: the class of decision problems solvable by a quantum computer in polynomial time, with an error probability of at most 1/3 for all instances.

Just like BPP, the choice of 1/3 in the definition is arbitrary because we could just have a "higher level" algorithm that runs the "basic algorithm" many times and take a majority vote to achieve higher probability of correctness.

I can imagine this as:

1. initialize qbits based on the input of length n
2. apply polynomial(n) quantum gates
3. measure output qbit
4. repeat steps 1-3, K times and report the majority measurement from step 3

Essentially, having a classical computing loop call a quantum routine K times.

Is it possible instead to somehow do *ALL* the computation on the quantum computer, and only make a single measurement at the end which is equivalent to this?

I'd hope for something like:

1. initialize qbits based on the input of length n
2. apply K \* polynomial(n) quantum gates
3. measure just a single output qbit

Or is making multiple measurements absolutely necessary to the computational power here?

**Tags:** complexity-classes, quantum-computing
> **Comments:**
> **username_1**: This question would be better suited for the (non-research level) [Computer Science stackexchange](http://cs.stackexchange.com/).  
> **username_0**: @NieldeBeaudrap Sorry. Thank you for letting me know.  

---

## 1 answers

### Answer by username_2 on 2017-04-06. Score: 4 | Accepted answer

The principle of deferred measurement (see <https://en.wikipedia.org/wiki/Deferred_Measurement_Principle>) tells us that measurements in the middle of a quantum computation can be simulated by using additional quantum gates instead. In particular, instead of measuring a qubit, we can apply a CNOT gate to that qubit and another qubit (which is used only at this point of the computation).


---

