What is Quantum Supremacy?
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.
