patternMinor
Doesn't a quantum algorithm being deterministic contradict the superposition principle?
Viewed 0 times
superpositiontheprinciplebeingalgorithmcontradictdoesndeterministicquantum
Problem
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.
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.
Solution
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.
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.
Context
StackExchange Computer Science Q#66782, answer score: 4
Revisions (0)
No revisions yet.