Quantum Computers May Not be Fully Deterministic, but that is OK



One thing that is almost always taken for granted in classical computing is that they are always deterministic, i.e. if you run a program with the same set of input data the answer will come out the same.    This will not always be true in quantum computers.    Because of decoherence and the probabilistic nature of measuring a qubit that has been in superposition you will not always get the same answer every time.

However, this does not necessarily destroy the value of a quantum computer.   There are many problems, particularly optimization problems, where it may not be too bad to return the second or third best choice instead of the first best when it is picking a solution out of millions of possibilities.  In fact, this can sometimes be a virtue because in some situations the second or third best choice may be more suitable due to other factors which were not explicitly included in the calculation.

In addition, even if you can get multiple answers, there is always the option of repeating a calculation multiple times and using voting to choose the one that comes up most often.   Although this may not seem efficient initially, if you have a quantum computer that is millions of times faster, you can run a calculation hundreds or thousands of time and achieve the correct answer with extremely high probability and still enjoy an enormous speedup.  For those of you interested, we have an Excel spreadsheet where you can specify the expected probability of the correct answer in a single run,  the number of iterations you will run and it will tell you the cumulative probability that majority voting will give you the correct answer.   Send us an email if you are interested in a copy.

So even though solving a problem on a quantum computer will require a different mindset it can still be of great value even if it is not fully deterministic.

2 Comments
Elsa Velazquez
@ 9:15 pm

Hello, may I please have a copy of that excel sheet? Also, can a quantum computer solve something that is not dterministic? Say, if I give it some harmonious tune, can it break down which notes I used to create that harmony? I believe not, nor can any computer if we are referring to analog sounds (obviously digital is different), but I’d like your take on it.
THanks!

Reply
Gemma Vall
@ 12:27 am

Interested in the xcel sheet. thanks!

Reply

Leave a Reply

Your email address will not be published. Required fields are marked *


*


This site uses Akismet to reduce spam. Learn how your comment data is processed.