| Google:We Have Quantum Supremacy IBM: No You Don't |
| Written by Mike James |
| Wednesday, 23 October 2019 |
|
You think it would be easy to prove that a quantum computer was better than a classical computer. Google's Quantum Computer Group thinks that it has done just that, but has it?
The Sycamore processor. (Erik Lucero, Research Scientist and Lead Production Quantum Hardware) This is another one of those "it couldn't happen in a book" type situations. Quantum supremacy is a poorly named concept that relates to proof that a quantum computer really can compute things that a classical computer can't. If you haven't been following the development of quantum computing, you might be surprised that this is an open question - surely quantum computers are better. In practice, however, until we actually have built a quantum computer that is so much faster than a classical computer we don't know if the advantage is just theoretical. The best known quantum algorithm is Shore's factoring method, which if it can be implemented will factor big numbers faster than any classical computer could. This is proof that a quantum computer is better - or is it? It is only proof of quantum supremacy if there are no physical laws which stop us from building a quantum computer or if there really are no better classical algorithms for factoring. A month ago a leaked paper from Google's Quantum Computer Group claimed that a calculation that would have taken the best supercomputer 10,000 years had taken just 200 seconds on its 53-bit quantum computer. As the paper was leaked and withdrawn very soon afterwards we decided not to report it until it was published. The paper has now appeared in Nature and we can rely on its results. So that's it then - all over, case closed. Not really. The problem is that the algorithm that was used isn't something useful or natural for a classical computer. It was designed to allow an imperfect quantum computer to do something, anything really, that was out of the reach of a classical computer. The algorithm consists of selecting a random sequence of gates - essentially operations on the qubits. The result of the algorithm is a random bit string with some probability distribution. The task is to find the probability distribution and for the quantum computer this is just a matter of running the program multiple times and seeing what the output is. For a classical computer the computation is much more difficult and is exponential in both the number of qubits and gates.
Process for demonstrating quantum supremacy Starting small, the Google team ran simple circuits with small numbers of qubits that were in the reach of a classical computer and verified that they were getting the correct results. Then they moved on to bigger and more complex problems and left the classical computer behind. Various respected experts endorsed the announcement while others dismissed it on a range of theoretical grounds with most of the arguments used being too vague to really judge. Now the quantum computing team at IBM has proposed a very real objection. It has proposed an improved classical algorithm that uses the large amount of cheap storage that disks provide. Its algorithm does the job in days rather than seconds, but with more work it could be optimized further. The quantum computer is still better than the improved classical, but then it is simulating a quantum property and it would be unreasonable for it not to have some speed advantage. This raises the whole question of what quantum computation is about? Is it simply a quantum analog computer? In which case the advantages for quantum problems are obvious, but they don't necessarily translate to solving non-quantum problems. When a quantum computer factors very big numbers that would take a classical computer decades to factor, then we will have the proof. The reason is that factoring isn't a quantum process and we will have proof that the supremacy extends beyond the quantum regime.
Artist's rendition of the Sycamore processor mounted in the cryostat. (Forest Stearns, Google AI Quantum Artist in Residence) More InformationQuantum Supremacy Using a Programmable Superconducting Processor - blog post Quantum supremacy using a programmable superconducting processor - paper On “Quantum Supremacy” - IBM blog post Leveraging Secondary Storage to Simulate Deep 54-qubit Sycamore Circuits Related ArticlesGoogle Takes On Quantum Computing Google Announces 72-Qubit Machine Nobel Prize For Computer Chemists 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
or email your comment to: comments@i-programmer.info |
| Last Updated ( Wednesday, 23 October 2019 ) |
