What makes a Quantum Computer Faster for solving specific problems?

Question

I have an undergraduate understanding of Quantum Mechanics (or at least of whatever is covered in Griffith's) and the idea of a Quantum Computer sounds really interesting but I am having some trouble seeing where its effectiveness comes from.

I understand that a qubit, or collection of qubits, can exist in a superposition of states and that you can apply a quantum logic gate to the state of the system to preform computations, for example the Hadamard Gate shown here: https://en.wikipedia.org/wiki/Quantum_logic_gate

What isn't clear is that after applying the gate, your system is still in general in a superposition of states and when you go to make a measurement of the system, it will collapse into one of its eigenstates with probability dependent on the inner product between the current state and the eigenstate. And so you are left with a single result. Can't this same single result be achieved by a series of similar computations on a classical computer with its bits in some determinate configuration? Why do the qubits being in a superposition of states somehow lead to computations being faster?

In order to get a for sure (or at least fairly accurate result) for some series of computations on a set of qubits that were initially in a superposition state, it seems like you would need to repeat the same calculations on the same state multiple times and find the correct distribution of results. So it seems like you would need to repeat the calculation multiple times on a quantum computer where as on a classical computer you only need to do the computation once which begs the question of how is in what respect is the quantum computer faster (assuming the speed of the calculations on both classical and quantum computers are the same or at least similar).

My bad if this is a repost or something.

Answer 1

These are good questions. I will try to give a flavor, but I strongly recommend that you look at some real quantum algorithms to see how these statements are actually implemented. There are some very good resources online, for instance John Preskill's quantum computing course, Scott Aaronson's quantum computing course, and Peter Shor's quantum computing course.

In some sense your intuition is right, that any that can be done on a quantum computer can also be done on a classical computer. However, simulating the behavior of a quantum computer on a classical computer is very inefficient. In classical computing, the state of $N$ bits is represented by $N$ binary numbers. However in quantum computing, the state of $N$ qubits is represented by $2^N$ complex numbers (each qubit can be in one of 2 states, so there are $2^N$ possible states, and you need one complex number for every possible state). Therefore it is hopeless to simulate the behavior of a quantum computer with a large number of qubits with on a classical computer. One way to express the mysteriousness of quantum mechanics, is that Nature is able to deal with this exponential number of states efficiently.

You are also correct that quantum superposition, by itself, is not enough to give quantum computers an edge. If your quantum computer is in a superposition of 100 states, but only one state represents the right answer, then on average you are going to need to do lots of measurements before you find the right answer.

The cleverness of designing good quantum algorithms is in finding a way that the final state of the computer is the state representing the correct answer, with a very high probability. For example, Shor's factoring algorithm works by converting the factoring problem into a Fourier transform problem, and then (very roughly speaking) putting the state of the quantum computer into one Fourier mode representing the correct answer. Then measuring the Fourier mode gives you the solution of the factoring problem (with a high probability).

It is not known how to design quantum algorithms that beat an efficient classical algorithm for every possible problem (or even many problems), and thus it is not expected that quantum computers will simply replace classical computers. However, what makes quantum computers interesting is that there are a class of special problems with nice structure that can be exploited.

In addition to designing efficient quantum algorithms that can solve a problem, another major active area of research is in developing robust quantum algorithms. Quantum computers exploit the coherence between different states (in other words, the idea that amplitudes for states corresponding to the right answer will interfere constructively, and amplitudes for states with the wrong answer will interfere destructively). However, if the qubits interact with the environment, they will very quickly decohere, which destroys the nice properties that allow quantum computers to do anything useful at all. The role of quantum error correction is to develop techniques to store the quantum information in a robust way in the available qubits, so as to protect the state against decoherence. Quantum error correction stores the information "globally" in the entire state, so that if one quibit decoheres, the important information in the state of the computer is preserved and computation can proceed.