Quantum Algorithm Beats Classical Tools On Complement Sampling Tasks (phys.org)
(Tuesday February 24, 2026 @05:00AM (BeauHD)
from the making-gains dept.)
- Reference: 0180850288
- News link: https://tech.slashdot.org/story/26/02/24/0047210/quantum-algorithm-beats-classical-tools-on-complement-sampling-tasks
- Source link: https://phys.org/news/2026-02-quantum-algorithm-classical-tools-complement.html
[1]alternative_right shares a report from Phys.org:
> 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, [2]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."
[1] https://slashdot.org/~alternative_right
[2] https://journals.aps.org/prl/abstract/10.1103/q55v-wm7y
> 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, [2]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."
[1] https://slashdot.org/~alternative_right
[2] https://journals.aps.org/prl/abstract/10.1103/q55v-wm7y