3
$\begingroup$

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.

$\endgroup$
  • 4
    $\begingroup$ The computation is choreographed in such a way that there's a high probability of getting the right answer. That's exactly why the probabilistic quantum algorithms have to be run several times. Anyway, you won't really be able to understand this concept unless you actually thumb through the math of some basic quantum algorithms. Better pick up a good textbook! $\endgroup$ – Sanchayan Dutta Nov 1 at 16:25
  • 1
    $\begingroup$ Sanchayan's comment is just the correct answer and I recommend that it be repeated as a stated answer to the question. The only thing I would change is to replace "have to be run several times" with "may have to be run more than once". The answer is indeed statistical and the algorithm may have to be repeated. But if it has a 99.99% chance of being correct, "several" is an overstatement. $\endgroup$ – Greg Kuperberg Nov 1 at 16:38
  • $\begingroup$ @SanchayanDutta: can you suggest me some good resources to understand the math behind the Quantum Algorithms since as you rightly guessed I am struggling to understand it, even the supposed hello world algorithm of Deutsch-Jozsa algorithm $\endgroup$ – dhiraj suvarna Nov 1 at 17:19
  • $\begingroup$ @SanchayanDutta: Thank You for the link. Its good. $\endgroup$ – dhiraj suvarna Nov 2 at 16:33
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ +1 I'd also add that quantum algorithms are not necessarily probabilistic (cf. EQP). $\endgroup$ – Sanchayan Dutta Nov 2 at 15:09
  • 1
    $\begingroup$ @MarkS This is basically correct, except: (1) NP is not an adjective, it's a noun. You mean a problem in NP. (2) Actually you mean TFNP rather than NP. You mean that in some cases, the quantum computer can calculate a function (F for function) such that the correct answer can always (T for total) be checked in polynomial time (the NP). $\endgroup$ – Greg Kuperberg Nov 2 at 16:54
  • 1
    $\begingroup$ @SanchayanDutta - Actually, I think of EQP as an artificial subclass of BQP. In the real world, since quantum amplitudes are statistical information, neither states nor gates can be trusted 100%, and even the output of an algorithm in EQP subject to the same statistical warnings as any algorithm in BQP. For one thing, the minute that you have an error-correction layer and the Solovay-Kitaev concept of approximating words, you've wrecked EQP and you are in BQP instead. $\endgroup$ – Greg Kuperberg Nov 2 at 16:57
  • 1
    $\begingroup$ Actually, in the real world you can never be certain of anything anyway. On the one hand, you can amplify any algorithm in BQP with repeated trials to drive the probability that it is incorrect to below the probability that you are delusional and aren't actually doing any QC in the first place. On the other hand, even a classical computer that checks answers in TFNP is subject to noise just like a quantum computer is. TFNP is a standard of certitude, but certitude is a funny concept in the real world. $\endgroup$ – Greg Kuperberg Nov 2 at 17:04
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Welcome to Quantum Computing SE! Do check out the formatting help page. $\endgroup$ – Sanchayan Dutta Nov 4 at 18:42
  • $\begingroup$ Thanks! Will do. @SanchayanDutta $\endgroup$ – Logon Nov 4 at 18:44
-1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Given that quantum computation specifically employs "quantum events" to perform computations, it's unreasonable to suggest that its likelihood of being influenced by those events is "astronomically low". $\endgroup$ – Sanchayan Dutta Nov 4 at 16:39
  • $\begingroup$ @SanchayanDutta Obviously any computation is influenced by quantum events - because the computation itself is an emergent property of those events. I simply meant that the likelihood of possible external disturbances having any measurable effect which would effect the outcome of the computation is astronomically low. $\endgroup$ – Snowshard Nov 4 at 16:45
  • 1
    $\begingroup$ That's certainly not true; if it were, we'd already be having viable quantum computers today! One of the biggest challenges in the field of experimental quantum computing today is error-correction (the errors are largely manifestations of "external disturbances"). Try running some quantum circuits on IBM's cloud quantum computers, to check the error-rate for yourself. $\endgroup$ – Sanchayan Dutta Nov 4 at 16:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.