Quantum shown to be faster than classical computers
...while Google claims ‘quantum supremacy’ with 53-qubits. Arne Verheyde & Lucian Armasu examine progress on the quantum front.
In a new scientific publication, Google claims to have reached “quantum supremacy” with a 53-qubit quantum computer, meaning that it has solved a problem that no classical computer can solve within a reasonable timeframe. It is the first time this has been achieved, marking a major milestone in the field of quantum computing.
While the term supremacy is a bit of an exaggeration, as it concerns just one application, it shows that quantum computers with their qubits, albeit still years from commercialisation in all likelihood, have finally reached a point where they have solved a problem that no transistor-based computer or supercomputer could ever solve, essentially proving that quantum computers indeed work. “To our knowledge, this experiment marks the first computation that can only be performed on a quantum processor,” the Google researchers wrote.
The experiment involved calculating the output of certain specialised circuits, with as input randomly generated numbers “produced through a specialised scenario involving quantum phenomena.” The quantum processor took 200 seconds to sample one instance of the quantum circuit one million times, while a supercomputer would require 20,000 years to perform that task, according to the researchers. The quantum computer used was Google’s 53-qubit Sycamore system, scaling back from their 72-qubit Bristlecone machine, although no reason was provided.
The researchers further predict that quantum computing power will grow at a double exponential rate, possibly referring to the exponential growth in capabilities with each new qubit, but with the number of qubits growing at an exponential rate akin to Moore’s Law.
Not too long ago, quantum computers belonged largely to science fiction. But in recent years, several companies have made progress in scaling up the number of qubits, including Google, IBM, Microsoft, and Intel. Last year, IBM already proved that quantum computers could be superior to classical ones for a certain problem, while Intel unveiled its 49-qubit Tangle Lake quantum computer at CES 2018.
Meanwhile, IBM researchers have published a paper proving that quantum computers can indeed be faster than classical computers, something that has only be theorised so far. One of the main promises of quantum computers has been that they can solve complex problems much faster than classical computers can. Classical computers typically require exponentially more resources and power as the number of variables increase.
IBM was able to prove, for a specific difficult algebraic problem, that quantum computers need only a fixed number of steps to solve the problem, even as the number of inputs increases. This makes the quantum computation much more efficient than the classical counterpart. The more complex the problem becomes, the more efficient the quantum computed solution should be too.
The IBM researchers Sergey Bravyi, David Gosset and Robert König said in their paper:
“We show that parallel quantum algorithms running in a constant time period are strictly more powerful than their classical counterparts; they are provably better at solving certain linear algebra problems associated with binary quadratic forms.