Quantum advantage attested by nonlocal games
July 22, 2022 - Austin Daniel
It is a long standing challenge to show that quantum computers can do something classical computers cannot. While most examples rest on assumptions of a particular problem’s classical hardness, it has recently been known that there are tasks that can be accomplished by constant-depth quantum circuits but not their classical counterparts. In a recent joint publication in Physical Review Research [1] by Akimasa Miyake’s group at UNM and Norbert Linke’s lab at the University of Maryland, in order to make these tasks applicable to small problem sizes, a set of games was formulated where one can prove quantum advantage when quantum and classical circuits with the same gate connectivity are compared. The Linke lab performed a proof-of-principle implementation of such a game using six qubits in a trapped-ion quantum computer.
The task is phased as a nonlocal game, where six parties each receiving partial information about an input binary string must conspire to output a string with certain correlations. They show that any strategy using one round of nearest-neighbor communication, which are equivalent to depth-1 classical circuits, cannot win the game more than 80% of the time. On the other hand, a constant-depth quantum circuit of nearest-neighbor entangling gates can always win. In the Linke lab’s experimental implementation of this circuit, their device succeeds at this task just below 80% of the time, motivating an in depth error analysis.
As the problem size scales, proportionally larger depth classical circuits still cannot win more than 80% of the time. They expect these games to be useful quantitative benchmarks for near-term quantum computers as the number of available qubits increases.
