You might think, given all the fuss, that quantum computers were a very desirable thing. What you might not be aware of is that there is no theoretical basis to believe that a quantum computer can do anything more than a classical computer can. However, some new results seem to prove that a quantum computer really is worth having.

There are strong suggestions that quantum computers can do more than classical computers. The best known is Shor's algorithm for factoring integers, which does the job that takes a classical computer exponential time in polynomial time. This would seem to be a proof that quantum computers are better, but there it isn't a proof because we cannot demonstrate that classical factoring doesn't have a polynomial time algorithm.

You might think that factoring is obviously not in P, the class of polynomial time algorithms, but it is clearly in NP, the class of non-deterministic polynomial time algorithms - which means if you give me a potential solution, i.e. the factors, I can check to see if it is a solution in polynomial time.

If anyone ever proves that NP=P then factoring will be classically polynomial as well as quantum polynomial. At the moment the best we can do is sub-exponential, which is between polynomial and exponential, i.e. slower than any polynomial but still faster than exponential. Shor's algorithm is O(b³) and hence clearly polynomial.

So we can't really decide if the existence of Shor's algorithm is proof that a quantum computer is better unless we can prove that classical factoring cannot be done in polynomial time.

The new paper does more than this, but not with Shor's algorithm. Robert König of the Technical University of Munich (TUM), David Gosset of the University of Waterloo and Sergey Bravyi  from IBM take a version of a known problem and construct a quantum circuit that solves it.

Quantum circuits are the equivalent of classical programs. This particular quantum circuit solves the problem using a constant depth circuit independent of the problem size n. This is like saying that it is solved in constant time. The researchers then go on to prove that a similar classical set up has to have a depth logarithmic in n. They also go on to prove that this advantage is due to the non-locality inherent in quantum physics, i.e. it really is the "spooky action at a distance" that matters.

You will find headlines at the moment claiming that it is all over for the classical computer, but you need to take careful note of what exactly has been proved. A quantum computer limited to a particular mode beats a classical computer restricted in a similar way. If you take the restrictions off then we still don't know if the quantum beats the classical.

So this is not a reason to celebrate just yet and, in particular, Shor's algorithm isn't an example of the type of quantum algorithm just proven better than similarly restricted classical algorithms. At best it is another indication that quantum computers might have something to offer that we can't get any other way and it is a proof that in this one like-v-like situation they really and provably do.

You also need to take into account that this is theory. The difficulties of building quantum computers that are not made useless due to noise still hasn't been solved. It is such a hard problem that some have even conjectured that the universe might be built in such a way as to forbid a quantum computer to exist and the noise is the way that it enforces that prohibition.

To prove this you would need to show some non-physical consequence of successfully building a quantum computer and so far no one has invented such a paradox.

More Information

Quantum advantage with shallow circuits ArXiv preprint

http://science.sciencemag.org/content/362/6412/308 paywalled

Related Articles

Minecraft Goes Quantum       

The Theoretical Minimum        

Nobel Prize For Computer Chemists       

Quantum Computers Animated       

Solve The Riemann Hypothesis With A Quantum Computer

Boson Sampling Tests Quantum Computing       

A Quantum Computer Finds Factors       

The Revolution In Evolutionary Game Theory - Prisoners Dilemma Solved?       

$100,000 Prize For Proving Quantum Computers Are Impossible

To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on Twitter, Facebook or Linkedin.

Comments

Make a Comment or View Existing Comments Using Disqus

or email your comment to: comments@i-programmer.info