What is the smallest computational task a quantum computer might be able to complete, that the most powerful supercomputers available today would find prohibitively hard?
Find that and you locate the frontier of what is commonly (and some say, problematically) referred to as ‘quantum supremacy’.
The search has now begun in earnest, with researchers from Google, NASA, the University of California and UTS this week proposing the theoretical foundation for a practical demonstration of quantum supremacy in near-term devices.
Their Nature Physics paper, Characterising quantum supremacy in near-term devices, suggests ‘a realistic benchmark’ for those hoping to build quantum computers that might be capable of surpassing the power of classical computers.
“It proposes the task of sampling bit-strings from the output of random quantum circuits, which can be thought of as the ‘hello world’ program for quantum computers,” Google research scientist Dr Sergio Boixo explained.
Quantum supremacy, the researchers explain, is achieved when a computational task is performed with an existing quantum device which cannot be performed using any known algorithm running on an existing classical supercomputer in a reasonable amount of time.
“We focused our attention on chaotic, or random, quantum circuits because as they get bigger the amount of entanglement grows rapidly. Such circuits produce subtle non-local correlations that make them particularly difficult to model on a classical computer,” said one of the paper’s authors Professor Michael Bremner, chief investigator at the UTS node of the Centre for Quantum Computation and Communication Technology and a founding member of the university’s Centre for Quantum Software and Information.
“Sampling from random quantum circuits is an excellent calibration benchmark for quantum computers, which we call 'cross-entropy benchmarking'. A successful quantum supremacy experiment with random circuits would demonstrate the basic building blocks for a large-scale fault-tolerant quantum computer,” Boixo added.
A quantum device that achieves a cross entropy difference that surpasses the performance of the most powerful classical computer would be the first demonstration of quantum supremacy, the researchers say.
With this as their guide, they conclude that supremacy can be achieved “with circuits in a two-dimensional lattice of seven by seven qubits and around 40 clock cycles”.
Google unveiled its 72 qubit chip dubbed Bristlecone in March, which it claimed put it well on the path to supremacy.
Rival Intel launched its 49-qubit superconducting quantum test chip in January, which CEO Brian Krzanich said was “a step towards quantum supremacy”.
IBM, meanwhile has a prototype 50 qubit machine, which it is making available to commercial and research partners including Sydney start-up QCtrl.
The qubit count is just one of many obstacles scientists will have to overcome, however, before a fully functional quantum computer is realised.
“The advantage offered by quantum computers is subtle. Some applications can have an exponential quantum speed-up over classical computers, while others receive no benefit at all,” Bremner said.
“Understanding when quantum computers become useful is essential, especially when we are limited to using the noisy intermediate-scale devices that currently exist… we wanted to find the smallest quantum circuits that can do something that cannot be done at all on a classical computer,” he added.