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.”

The collaboration of TU Wien with research groups in China has resulted in a crucial building block for a new kind of quantum computer: The realization of a novel type of quantum logic gate makes it possible to carry out quantum computations on pairs of photons that are each in four different quantum states, or combinations thereof. The advancement is an important milestone for optical quantum computers. The study has now been published in Nature Photonics.

The basic idea of quantum computers is simple: While a classical computer only works with the values “0” and “1,” quantum physics allows for arbitrary combinations of these states. In a certain sense, a quantum bit (“qubit”) can be in the states 0 and 1 simultaneously. This makes it possible to develop algorithms that can solve some problems much faster than a comparable classical computer.

However, such superpositions can in principle involve more than two states. Depending on what degree of freedom one considers, a quantum system such as a photon may not just have two different settings—two different outcomes of a potential measurement—but many. In this case, one refers to the system as a “qudit” rather than a “qubit.”