How does a quantum computer execute a process by leveraging superposition?

Question

I understand in plain terms superposition and entanglement, but I'm very unclear how either of these could work as a means to increase computation power.

A helpful metaphor is that of the maze. A normal computer must work through every path of the maze to find the exit. If it takes a wrong turn, it must start over. This is time-consuming. On the other hand, a quantum computer can work through every path simultaneously. Obviously, this is more efficient.

But that metaphor doesn't explain how superposition makes this possible because it doesn't describe how a quantum computer would execute the calculation/process.

So what I'm looking for is an explanation of that, how does a quantum computer execute a process by leveraging superposition?

That qubits collapse under observation seems to make the whole thing useless.

Let's say I have a dictionary of possible passwords. One password is correct. I can create a function that loops through every word in the dictionary and attempts to use it as the password.

The password is stored in a variable called "temp". In a quantum world, if "temp" was made of qubits, it could have a multitude of values at once, drastically reducing the number of times we would need to run the password test.

But in order for the test to execute, wouldn't we need to observe the value of "temp" and therefore collapse the potential states?

Answer 1

Your intuition is correct if you think of the superpositions as classical probability distributions, which is how they are usually described in popularizations.

What's unique to quantum mechanics is not superposition as such, but constructive/destructive interference between different computational paths, which leads to certain results appearing more/less often than they would in the classical probabilistic picture. All quantum algorithms exploit that in some way. If you ran them on a computer that measured every qubit after every gate, making it effectively classical, there would still be a nonzero chance that they would produce the correct answer, but it would be a smaller chance (small enough to make the algorithm useless).