February 23, 2026 by Ingrid Fadelli, Phys.org
Collected at: https://phys.org/news/2026-02-quantum-algorithm-classical-tools-complement.html
Quantum computers—devices that process information using quantum mechanical effects—have long been expected to outperform classical systems on certain tasks. Over the past few decades, researchers have worked to rigorously demonstrate such advantages, ideally in ways that are provable, verifiable and experimentally realizable.
A team of researchers working at Quantinuum in the United Kingdom and QuSoft in the Netherlands has now developed a quantum algorithm that solves a specific sampling task—known as complement sampling—dramatically more efficiently than any classical algorithm. Their paper, published in Physical Review Letters, establishes a provable and verifiable quantum advantage in sample complexity: the number of samples required to solve a problem.
“We stumbled upon the core result of this work by chance while working on a different project,” Harry Buhrman, co-author of the paper, told Phys.org. “We had a set of items and two quantum states: one formed from half of the items, the other formed from the remaining half. Even though the two states are fundamentally distinct, we showed that a quantum computer may find it hard to tell which one it is given. Surprisingly, however, we then realized that transforming one state into the other is always easy, because a simple operation can swap between them.”
This observation ultimately led Buhrman and his colleagues to formalize the complement sampling problem and analyze it rigorously.
A quantum approach to complement sampling
The complement sampling can be described as follows: suppose there is a universe of elements and an unknown subset S of size K. You are given access to samples drawn uniformly from S, and your task is to output an element from the complement set that is an element not in S.
In the classical setting, solving this problem requires numerous distinct samples from S. Specifically, when K = N/2, any classical algorithm succeeding with probability of at least 1/2 + δ needs roughly N samples—an exponential amount. Essentially, lacking structural insight, a classical algorithm must gather nearly all information about S to reliably produce an element not in it.
The quantum setting is fundamentally different. Instead of classical samples, the algorithm receives a quantum sample: a single copy of the uniform superposition over all elements of S. This state encodes the entire subset coherently.
The researchers show that when K = N/2, a quantum computer can use just one such quantum sample and transform it exactly into the uniform superposition over the complement set, after which a measurement produces a uniformly random element with certainty.
“Importantly, this is not a speedup in runtime,” Buhrman explained. “It is a separation in sample complexity. A single quantum state suffices, whereas any classical algorithm requires a number of samples proportional to the size of the universe. The advantage comes from how quantum information can be stored and manipulated, not from faster computation per se.”
Towards the large-scale deployment of quantum systems
“We believe this approach offers a new route to demonstrating quantum advantage,” Buhrman said. “It is provable, verifiable and compatible with near-term hardware. At the same time, it highlights a different kind of quantum advantage—one based on sample complexity rather than computational speed.”
The researchers also point out that complement sampling may have applications in cryptography. Because the task can be embedded in pseudorandom constructions and is classically hard under standard assumptions, it could potentially be used to strengthen certain cryptographic protocols.
“Another pressing question we had throughout the project was: how well does the quantum algorithm perform in real-world conditions? We have recently executed thousands of complement sampling instances on Quantinuum System Model H2 trapped-ion quantum computers and reported progress in a preprint on arXiv. The results are very promising, showing that current machines follow the theoretical predictions beautifully.”
Publication details
Marcello Benedetti et al, Provable and Verifiable Quantum Advantage in Sample Complexity, Physical Review Letters (2026). DOI: 10.1103/q55v-wm7y.
Journal information: Physical Review Letters , arXiv
Leave a Reply