In News:

Researchers from the University of Oxford and Universidad de Sevilla have demonstrated quantum supremacy using a simple mathematical game based on the odd-cycle graph colouring problem. The study, published in Physical Review Letters, marks a significant milestone in quantum computing.

What is Quantum Supremacy?

Quantum supremacy refers to the ability of a quantum computer to perform a task that is practically impossible for classical computers to solve efficiently. This advancement showcases the unique capabilities of qubits, which leverage two core principles:

• Superposition: Qubits can represent both 0 and 1 simultaneously.
• Entanglement: Measurement of one qubit instantly affects another, even over a distance.

These principles enable exponential scaling of computational power. For instance, a 50-qubit quantum computer could potentially outperform the most powerful classical supercomputers.

The Odd-Cycle Game: A Novel Approach

The team implemented a game inspired by graph theory:

• Players (Alice and Bob) are tasked with colouring an odd-numbered cycle (e.g., triangle) using only two colours such that adjacent points differ in colour.
• Mathematically, this is impossible in classical terms for odd cycles due to inevitable repetition of colours.

In the experiment:

• Two strontium atoms placed 2 meters apart were entangled using lasers.
• A referee sent each atom a "question" (mapped to a point on the cycle).
• Players performed quantum operations based on the questions and returned either 0 or 1 (representing colours).

The experiment was repeated 101,000 times, covering circles from 3 to 27 points.

Results and Significance

• Classical win rate: 83.3% for 3-point cycles.
• Quantum win rate: 97.8%, clearly surpassing classical limits.
• Quantum supremacy was evident up to 19-point circles.
• The entanglement correlation was the strongest ever recorded between two separated quantum systems.

Comparison with Previous Demonstrations

• Google’s Sycamore (2019): Used 53 superconducting qubits for a complex problem called random circuit sampling.
• China’s Jiuzhang: Used Gaussian boson sampling.
• In contrast, this new approach used just two entangled qubits, making it simpler, efficient, and easier to verify.

Practical Implications

This simplified game-based model of quantum advantage could have real-world applications in problems where coordination is needed without communication—such as the "rendezvous problem". Quantum systems can dramatically reduce search steps compared to classical ones (e.g., Grover’s algorithm can reduce 1 million steps to 1,000).