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?

  • 3
    $\begingroup$ This question would be better suited for the (non-research level) Computer Science stackexchange. $\endgroup$ – Niel de Beaudrap Apr 6 '17 at 9:15
  • $\begingroup$ @NieldeBeaudrap Sorry. Thank you for letting me know. $\endgroup$ – PPenguin Apr 6 '17 at 9:29

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).


Not the answer you're looking for? Browse other questions tagged or ask your own question.