Demonstrating a Quantum Edge in a Coloring Game
In principle, a modest quantum computer can perform in minutes a computational task that would occupy the most powerful classical computer for millennia. Demonstrating this quantum advantage unambiguously has proven difficult, however, as early claims have been answered with better classical algorithms (see Research News: A Moving Target for Quantum Advantage). Peter Drmota at the University of Oxford, UK, and colleagues at Oxford and the University of Seville, Spain, have now demonstrated quantum advantage in a way that’s impossible to rebut. The team’s experiment showed that players of the so-called odd-cycle game can achieve a higher rate of success if they have access to quantum resources [1].
The odd-cycle game is played on a circular graph with an odd number of binary nodes—imagine a round table set with an odd number of plates that can be either red or blue. The referee randomly assigns a node to each of two cooperating players—either the same node or an adjacent pair. Following a predetermined strategy but with further communication forbidden once the game begins, the players respond with a color. They win if they return the same color when assigned the same node or different colors when assigned different nodes. While the performance of both classical and quantum strategies is limited by the size of the graph, quantum strategies allow for higher success rates than the best possible classical strategy.
Drmota and his colleagues conducted a version of the game in which the players shared a trapped pair of entangled strontium ions. The players independently performed measurements on the ions to determine their responses to the referee’s queries. As measurements performed on the pairs exhibit correlations that do not arise in the classical case, with the right strategy, the players’ responses can exceed the best possible classical performance. “We believe this is the first time that quantum advantage is shown and explained in a tangible way, accessible to a nonspecialist audience,” Drmota says.
–Marric Stephens
Marric Stephens is a Corresponding Editor for Physics Magazine based in Bristol, UK.
References
- P. Drmota et al., “Experimental quantum advantage in the odd-cycle game,” Phys. Rev. Lett. 134, 070201 (2025).