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  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.
 A. K. Daniel, Y. Zhu, C. H. Alderete, V. Buchemmavari, A. M. Green, N. H. Nguyen, T. G. Thurtell A. Zhao, N. M. Linke, and A. Miyake, Quantum computational advantage attested by nonlocal games with the cyclic cluster state, Phys. Rev. Research 4, 0330