How do quantum states collapse to the right answer?

Question

I am a computer engineer and have recently started understanding quantum computers.

I am still struggling to wrap my head around some concepts.

One such query is the following - It is said that during the computation the qubits exist in the multiple states with some probability until it is measured. Once the act of measurement is done all the probabilities collapse and one answer is the output.

Now, what I am not able to get my head around is, how are we sure that this collapsed answer is the right answer? Since the superposition states are probabilistic in nature, there is a probability (though slim) of a wrong answer being output too.

Also since we cannot see or measure the intermediate superposition states we do not know which state has the highest probability. So how do we make quantum computer output the right answer?

I would highly appreciate someone to guide me through this.

Answer 1

I see maybe three questions here:

1. Given an efficient (quantum) algorithm, how is it that the efficient algorithm will give the correct answer with high probability?

2. Given an efficient (quantum) algorithm, how do we know that the efficient algorithm will give the correct answer with high probability?

3. Upon executing our efficient quantum algorithm, how can we be sure that the probabilistic answer so achieved is correct?

Regarding the first question, this is answered in the comments. The quantum algorithm choreographs the probability amplitudes to interfere constructively to the correct answer.

Regarding the second question, many algorithms are proved both efficient and correct with high probability, but indeed there are some quantum algorithms and heuristics that we are not sure will give a correct answer in an efficient amount of time. For example, as I understand it the quantum adiabatic algorithm or the quantum approximate optimization algorithm in many cases lack a proof that an answer will be provided in an efficient amount of time. That is, although the correct answer may eventually be given with high-enough probability, it is unknown whether the answer will be given in a short-enough amount of time.

Regarding the third question, for very many problems of interest, we hope a quantum algorithm will give an answer to a problem in the so-called $\mathrm{TFNP}$ class of problems (see comments). The implication is that if our quantum computer provides one answer, we can test that answer on our classical computer to determine whether the answer is correct. For example, the oft-repeated quip that quantum computers have used Shor's algorithm to successfully factor $21$ into $3\times 7$ "with high probability" has a joke hidden therein. Namely, the quantum computer successfully determined that $3$ is a factor of $21$ with high probability, or that $7$ is a factor of $21$ with high probability, and we can classically check that $21=3\times 7$. The same could be said for any problem in $\mathrm{TFNP}$ that also happens to have an efficient quantum algorithm - e.g. problems in the so-called so-called $\mathrm{BQP}$ complexity class.

However, interestingly there are indeed some problems that have an efficient quantum algorithm to find a putative answer, but likely do not have an efficient classical verification algorithm that can verify the putative answer. For example, determining certain properties of mathematical knots falls into this category, as does, for example, Google's approach to quantum supremacy, and there are indeed issues about the classical verification of the output of such algorithms - but I don't think that's the direction the OP was going.

Answer 2

Some algorithms do have deterministic answers or a high probability of getting the correct answer when implemented. For example, Deutsch's algorithm (Deutsch-Jozsa) which tells us with certainty whether a function is constant or balanced. On the other hand, however, you have Grover's search. Grover's has a high probability of giving you the correct answer but it is not definite. The more iterations of Grover's that are done in a circuit, the higher the probability of the correct answer appearing. It's really about trusting the mathematics. If you were to implement these algorithms by hand and work out the math (and use Born's Rule of squaring the coefficients of states to find that state's probability) you'll find that you will arrive at the correct answer or you will see that the correct answer has a high probability of appearing (relative to the other states).

And if you're interested in a book for starting out, I highly suggest: Quantum Computation and Quantum Information by Nielson and Chuang.

Answer 3

Technically, there is no way to determine with perfect accuracy, and the same applies to any event. Everything that happens in our universe involves interactions between quantum states, and therefore is probabilistic. When we do a simple math calculation in our minds or on a calculator, there is always a small chance that the "wrong" answer will be produced by unlikely though possible quantum events. Every observation we make is under this influence as well. In essence, there won't be any difference in error rates among classical vs. quantum computers, ignoring mechanical failures and decoherence interference. Any calculation done by any computer, whether it's classical, quantum, or even a brain, will only provide an answer according to certain probabilities, and even our observation of that answer will follow the same probabilistic functions, so there is technically a) no way to know for certain whether an answer is correct.

However, the likelihood of any computation being influenced by external quantum events is so astronomically low that we can assume, beyond a reasonable doubt, the accuracy of any given computation - including those done by a quantum computer. Ignoring external factors, all computations follow the probabilistic rules which they are privy to, and the correct answer will usually be the result, because the likelihood of the quantum events which compose the computation behaving outside the expected probability is close to zero.