3
$\begingroup$

How can the EQP quantum complexity class exist? I mean, doesn't the superposition principle imply it is not possible to know with probability 1 whether a quantum algorithm will return a solution?

For if a quantum computer’s state is in superposition, quantum measurement implies the state we obtain when we read the computer's state is random - with the probabilty we will obtain any particular state being based on its probability amplitude at the time of measurement. Thus unless some state has probability amplitude 1 (which would mean the system wasn't in superposition, so can't have been a quantum algorithm, as any quantum algorithm must use superposition), we cannot know whether we will obtain a solution state at any quantum computation's completion.

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ Have you tried looking at some of the foundational papers on EQP? They are cited in the complexity zoo. $\endgroup$ – Yuval Filmus Dec 2 '16 at 7:59
4
$\begingroup$

If the algorithm has no error, then the system is not in a superposition when it is measured, but it is possible it was in a superposition during the computation, after which it was cleverly interfered constructively on the right answer(s) and interfered destructively on the wrong one(s).

For example, Deutsch's algorithm has this property, the way he initially introduced it: the system is put into a superposition without entanglement, then it is operated on to produce a superposition in which the two qubits are entangled, and then it is operated on some more so that the final measurement is deterministic.

One way to understand why some deterministic quantum algorithms use superposition is to see that an algorithm is a map from input vectors to output vectors. A good algorithm goes from the input vector to the output vector via the shortest path. The only steps that it can take are elementary gates (Hadamard, CNOT, X, Y, Z, etc.). Sometimes, the shortest path happens to be one in which the intermediate states are in a superposition, even if the final state is not. If this is the case, if all shortest paths involve superposition, then this problem is solvable more quickly by a quantum computer than by a classical computer, which cannot take those paths.

Improve this answer
$\endgroup$
1
$\begingroup$

This is a bit like asking "doesn't the ability to rotate objects prevent me from ever getting them right-side-up again?".

Yes, if you initialize a qubit into the $|\text{Off}\rangle$ state and (for example) rotate it by 180 degrees around the X+Z axis (i.e. apply a Hadamard gate) the qubit ends up in the state $\frac{1}{\sqrt 2}|\text{Off}\rangle + \frac{1}{\sqrt 2}|\text{On}\rangle$. But you know what happens if you apply another Hadamard? Yeah, you rotate by another 180 degrees for a total of 360. You end up right back where you started, in the $|\text{Off}\rangle$ state.

HH circuit

A physical experiment that nicely demonstrates this principle is the Mach–Zehnder interferometer. Beam splitters create superpositions of paths, but they can also put them back together:

Mach-Zehnder interferometer

Improve this answer
$\endgroup$
2
  • $\begingroup$ But then, what's the point of rotating a qubit twice if all you get is what you started with? $\endgroup$ – Yuval Filmus Dec 2 '16 at 22:37
  • $\begingroup$ @YuvalFilmus Well, this was just intended to be a maximally trivial example of going into and out of superposition. It's not useful on its own, except maybe as a test that your quantum computer is functioning correctly or as a counterfactual bomb testerfor noticing sneaky CNOTs on your wires. if you don't get $|\text{Off}\rangle$ at the end, you know something wonky is going on in the middle. $\endgroup$ – Craig Gidney Dec 2 '16 at 22:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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