Quantum Supremacy Achieved Using a Simple Odd-Cycle Game

Quantum supremacy refers to the point at which a quantum computer outperforms the best classical computers at a specific task, highlighting its unique computational advantage.

The Odd-Cycle Game Approach

In a landmark experiment, researchers from the University of Oxford and Universidad de Sevilla demonstrated quantum supremacy using a simple yet elegant task based on the odd-cycle graph colouring problem. Unlike previous approaches using highly complex problems (e.g., Google’s random circuit sampling), this method is intuitive, easily understandable, and verifiable.

Understanding the Problem:

• A circle with an odd number of points (e.g., 3, 5, 7…) must be coloured using two colours (blue and red).
• The rule: adjacent points must not have the same colour.
• Mathematically, this is impossible for an odd number of points.

Game Setup:

• Two players: Alice and Bob, who cannot communicate.
• A referee sends each player a question corresponding to a point on the circle.
• Win conditions:
  • If the same point is asked, both must give the same colour.
  • If adjacent points are asked, their colours must differ.
• Classical success rate: maxes out at 83.3% for 3-point circles.

Quantum Implementation:

• Two strontium atoms were separated by 2 meters and entangled using lasers.
• Entanglement allowed the players (Alice and Bob) to correlate their answers beyond classical limits.
• They performed angle-specific quantum operations on their respective atoms, depending on the referee’s question.
• Output: A binary measurement (0 or 1), mapped to colours.

Key Results:

• 101,000 games were played for circles ranging from 3 to 27 points.
• Achieved a 97.8% win rate, surpassing the classical ceiling.
• Demonstrated quantum supremacy for up to 19-point circles.
• The remaining 2.2% failure was attributed to noise in entanglement.
• Verified strongest quantum correlations ever recorded between two spatially separated particles.

Significance of the Research:

• Simplifies the demonstration of quantum supremacy, using only two qubits instead of complex multi-qubit systems like Google’s 53-qubit Sycamore.
• Makes verification easier and opens avenues for practical quantum protocols.
• Could be adapted to real-world problems like the rendezvous task, where communication is restricted and coordination is essential.

Quantum vs Classical in Real Scenarios:

• Example: In a search space of 1 million meeting points:
  • Classical worst-case steps = 1 million.
  • Quantum using Grover’s algorithm = ~1,000 steps.

TH