1
$\begingroup$

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?

$\endgroup$

closed as off-topic by Niel de Beaudrap, Emil Jeřábek, Kaveh, Mohammad Al-Turkistany, Sasho Nikolov Apr 9 '17 at 20:24

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – Niel de Beaudrap, Emil Jeřábek, Kaveh, Mohammad Al-Turkistany, Sasho Nikolov
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 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
4
$\begingroup$

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

$\endgroup$

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