A critical question for the field of quantum computing is whether quantum devices without error correction can perform a well-defined computational task beyond the capabilities of state-of-the-art classical computers, achieving so-called quantum supremacy(1).
Quantum supremacy is what John Martinis at Google is planning to achieve by the end of this year. Google hired him and his research team at the University of California, Santa Barbarain in 2014, just to do this. You know, Google is all about supremacy… Will Martinis be able to do it?
The concept of quantum supremacy was coined by John Preskill in 2012(2):
One way to achieve such “quantum supremacy” would be to run an algorithm on a quantum computer which solves a problem with a super-polynomial speedup relative to classical computers, but there may be other ways that can be achieved sooner, such as simulating exotic quantum states of strongly correlated matter.
He also wondered in his paper: when will we be able to perform tasks with controlled quantum systems going beyond what can be achieved with ordinary digital computers?
To realize that dream, we must overcome the formidable enemy of decoherence, which makes typical large quantum systems behave classically. So another question looms over the subject: Is controlling large-scale quantum systems merely really, really hard, or is it ridiculously hard?
To beat the world’s largest supercomputers, and avoid as much as possible the controversy of previous announcements, Martinis and collaborators are turning the tables, focusing on a problem that they think it is a natural task for quantum computers, while (ridiculously) difficult for conventional computers: “sampling from the output distributions of (pseudo-)random quantum circuits.” Using this problem, Martinis thinks they will need a grid of 49 qubits. So far, they have only a 9-qubit computer.
Make no mistake, for the time being the result of this tour-de-force is not expected to have many uses, except showing there are tasks at which quantum computers are unbeatable.
A small step for Google, one giant leap for quantum computing!
____________________
Boixo, Sergio, Sergei V. Isakov, Vadim N. Smelyanskiy, Ryan Babbush, Nan Ding, Zhang Jiang, Michael J. Bremner, John M. Martinis, and Hartmut Neven. 2016. ‘Characterizing Quantum Supremacy in Near-Term Devices’, July. https://arxiv.org/abs/1608.00263.
Preskill, John. 2012. ‘Quantum Computing and the Entanglement Frontier’, March. https://arxiv.org/abs/1203.5813.
Mind the Post 