Quantum algorithms and quantum computation

Question

Is my (very high-level) understanding correct here regarding quantum algorithms —

Quantum computers can process a massive amount of operations in parallel to the nature of qubits and their ability to have states that are superpositions of $|0\rangle$ and $|1\rangle$.

Yet when we measure the qubits all the possible states collapse into a single state of either $|0\rangle$ or $|1\rangle$, which seems to negate the potential benefits of parallel operations. All we really know are the probabilities that the states will end up as.

However, we can exploit quantum properties to increase the probability that we end up with a certain result. I believe Shor's algorithm is based on exploiting quantum properties too, although I'm not sure in what way?

e.g. in a quantum walk, quantum interference means the walk spreads faster than a classical random walk and hence can out-perform classical walks.

That is my very high level understanding of what is going on with quantum algorithms. Am I correct, 'sort-of' correct, or way-off? Can someone clarify my understanding?

Answer 1

This is more-or-less a reasonable description of quantum computation. A few remarks are in order:

1. Regarding "quantum parallelism":

   Quantum computers can process a massive amount of operations in parallel [...] Yet when we measure the qubits all the possible states collapse into a single state of either $|0\rangle$ or $|1\rangle$, which seems to negate the potential benefits of parallel operations. All we really know are the probabilities that the states will end up as.

   This description, as it stands, applies equally well to randomized computation. We don't assume that random bits have any special sort of state-space, of course — we can just flip coins rather than having to carefully manipulate ions, or photons, or what-have-you — but the mathematics behind probability distributions and quantum states are nearly identical. (Try out some computations involving probability vectors some time, replacing the unitary transformations with stochastic transformations.)

2. Regarding "quantum properties":

   However, we can exploit quantum properties to increase the probability that we end up with a certain result. I believe Shor's algorithm is based on exploiting quantum properties too [...] e.g. in a quantum walk, quantum interference means the walk spreads faster than a classical random walk and hence can out-perform classical walks.

   We do increase the probability that we observe a given result — but this is a consequence of the fact that we decrease the probability of seeing unhelpful outcomes. Classical probability distributions "interfere constructively" too, though we just call it cumulated probability — one thing which is special to quantum computation is the fact that destructive interference (partial or total cancelling of amplitudes) occurs.

   This can be seen as one of the reasons why quantum computation is more powerful: the existence of amplitudes which would cancel if you simply added them, means that amplitudes sometimes do cancel when the computation calls for transitions involving both of those amplitudes. This is something which simply doesn't happen with probability distributions — in fact, it doesn't even happen in nondeterministic Turing machines.

   The trick, of course, is to find the particular ways in which you can conspire to have unhelpful outcomes partially cancel (or indeed, to determine which outcomes could be helpful to you, in order to arrange for the other outcomes to cancel). Simply recognising that amplitudes can possibly cancel is not in itself enough to figure out how to compute more quickly.

3. Regarding Shor's algorithm:

   I believe Shor's algorithm is based on exploiting quantum properties too, although I'm not sure in what way?

   Shor's algorithm is an example of an algorithm which uses the quantum Fourier transform (or QFT), a unitary transformation which broadly speaking is helpful to find/expose periodic patterns. The fact that it can be performed unitarily means that certain simple periodic patterns which would otherwise be difficult to determine in a small number of trial calculations can be quickly discovered by looking at bulk properties.

   Using QFTs to expose periodic properties is one particular trick in the bag of quantum algorithms; there are others as well.