For a long time, researchers have been looking for the sort of task that a quantum computer will be better at doing than a classical computer. Because if a quantum computer shows that it can be superior, it will achieve a milestone called quantum supremacy.
Researchers from the University of Oxford and Universidad de Sevilla recently demonstrated quantum supremacy using a simple game.
Their finding, published in Physical Review Letters in February, borrowed a concept from the odd-cycle graph. The aim here is simple: to colour a circle containing an odd number of points with two colours, such that no two adjacent points have the same colour. This is mathematically impossible.
The researchers adapted this game to use as a test of quantum supremacy.
Previous attempts at showing quantum supremacy have used complicated problems. For example, Google used a problem called random circuit sampling to demonstrate the supremacy of its Sycamore processor in 2019. Researchers in China went with the Gaussian boson sampling problem for the Jiuzhang quantum computer. Both these problems require complex mathematics and specialised equipment to perform, which make it hard to verify the results.
The colouring problem
The setup for the odd-cycle problem is simple. Consider a circle with an odd number of points inside it, say three. The challenge is to use two colours, blue and red, to colour the points such that no two adjacent points have the same colour.
Once one of the points is coloured red and the other blue, the third point has to be red or blue, breaking the rule.
In the researchers’ experiment, there are two players named Alice and Bob who can’t communicate with each other. A referee asks them questions about the colour of the points in an odd-numbered circle. The game ends in victory if two conditions are met: when asked about the same points, the players must answer with the same colour (e.g. both must say “blue”) and when asked about adjacent points, they must answer with different colours (i.e. Alice says “blue” and Bob says “red”).
In the classical scenario, the players agree on a colouring pattern for the points before the game begins, yielding a success rate of 83.3% for a three-point circle. In other words, the game can be won 83.3% of the time.
Playing the quantum game
To implement the quantum version of the experiment, the researchers trapped two strontium atoms in separate locations 2 m apart.
Using lasers, the researchers entangled the two atoms. When two particles are entangled, they are correlated in a way that classical physics can’t explain. Measuring one particle — i.e. checking its present condition — will instantaneously affect the other.
A single computer acted as the referee, sending the questions to two separate control systems controlled by Alice and Bob. After receiving the questions, each player performs specific quantum operations on the atom using laser pulses.
These operations involved rotating their particles through specific angles that were mathematically related to which point on the circle a question was about. The first question meant rotating some angle, say, and the second question meant rotating through a different angle.
After performing the operations, the players measured their atoms to determine the answer, which could be 0 or 1. Each number was mapped to a colour, blue or red, and its value was reported to the referee.
The researchers played this game for circles containing 3 to 27 points 101,000 times, which took about a minute.
They also performed additional tests to verify the strength of the correlations and ensure they are quantum in nature.
The quantum advantage
For the 3-point circle, the quantum scenario had a win rate much greater than the classical scenario (i.e. 83.3%). It clearly demonstrated quantum supremacy, which the team showed for circles with up to 19 points.
Across all the 101,000 games, their implementation achieved a win rate of 97.8%. The remaining 2.2% gap was attributed to noise while creating the entanglement between the atoms.
Their test to make sure the atoms were properly entangled was also found to be the strongest such correlation ever observed between two separated quantum systems.
Why this matters
As demonstrated in the study, the odd-cycle game approach is much simpler to implement in order to establish quantum supremacy.
In order to prove the Sycamore processor had achieved quantum supremacy, Google fit it with 53 superconducting qubits, an enormous computational resource. On the other hand, the researchers used only two entangled qubits, which is much simpler and less computationally demanding than Google’s setup.
According to the researchers, their approach could be used in practical scenarios where collaborating agents can’t communicate, such as the rendezvous task. A type of coordination problem, the rendezvous task is about two or more people meeting at a particular location without communicating with each other.
A classical computer may try to determine where they will meet by systematically exploring potential meeting points and the routes the two people may take to get there. A quantum computer will leverage quantum entanglement to create correlations that classical physics can’t reproduce, speeding up its search for the most likely meeting point.
If there are 1 million meeting points, for example, the worst-case number of steps for a classical computer to find the meeting point is 1 million whereas for a quantum computer using Grover’s algorithm would be 1,000 steps.
For now, the odd-cycle game is an example of the kind of power quantum computers have, and without requiring complicated mathematics to make sense of.
Tejasri Gururaj is a freelance science writer and journalist with a master’s degree in physics.
Published – April 09, 2025 05:30 am IST
