What unique capabilities do quantum computers possess that traditional computers cannot replicate? This question is central to a swiftly evolving industry, and recent findings aim to provide clarity on this topic.

Unlike classical bits, quantum computers utilize qubits that can occupy multiple states beyond just “0” or “1”, offering potential computational advantages. However, the debate on whether quantum computers can accomplish tasks beyond the reach of the most advanced traditional computers, including the notion of quantum supremacy, remains complex and contentious. This is primarily due to the stipulation that genuine demonstrations of quantum advantage must involve practical computational tasks, achievable with realistic quantum technology, while explicitly excluding any mathematical or algorithmic enhancements that may allow classical computers to eventually catch up.

William Crescher from The University of Texas at Austin and his colleagues are presently conducting experiments that satisfy both criteria. In contrast to earlier claims of quantum dominance, which were ultimately bridged by classical computing advancements, the researchers assert, “Our results are clear and enduring: no future classical algorithm development will close this gap.”

The team executed a complex mathematical experiment addressing communication challenges using 12 qubits created from laser-controlled ions by the Quantum Computing Company Quantinuum. The experiment’s objective was for two virtual participants, referred to as Alice and Bob, to devise the most efficient method for exchanging messages and performing calculations.

One section of the quantum computer, acting as Alice, prepares a specific quantum state and transmits it to Bob, another segment of the machine. Bob must discern its properties and determine how to measure Alice’s state to produce an output. By iterating this process, the duo can establish a means to forecast Bob’s output before Alice discloses her state.

The researchers conducted the procedure 10,000 times to refine the way Alice and Bob execute their tasks. With an analysis of these iterations and a rigorous mathematical examination of the protocol involved, it was found that classical algorithms with fewer than 62 bits could not compete with the performance of a 12-qubit quantum computer in this particular task. For a classical algorithm to achieve equivalent performance, it would require a performance threshold of about 330 bits, representing a nearly 30-fold difference in computational capability.

“This is an extraordinary scientific achievement that illustrates the extent of the ‘quantum advantage’ landscape, which may be broader than previously understood,” said Ashley Montanaro from the University of Bristol, UK. “Unlike most demonstrations of quantum superiority, the prospect of discovering a superior classical algorithm is virtually impossible.”

Ronald de Wolf from the Dutch Institute for Mathematics and Computer Science highlights that this experiment effectively leverages the recent rapid enhancements in existing quantum technologies while drawing upon theories of communication complexity that have been explored for years.

“The intricacies of communication are known to contribute to a verifiable and realistic distinction between quantum and classical systems. The difference is that advancements in hardware have made it feasible to implement the model for the first time,” he explains. “Moreover, they tackled a novel challenge in communication complexity, revealing a significant gap between classical and quantum capabilities even with just 12 qubits.”

These new findings differentiate themselves from earlier demonstrations of quantum superiority, but share a crucial element: their immediate practicality remains uncertain. Notable examples of quantum advantage that could produce substantial real-world benefits, such as Shor’s algorithm which could revolutionize encryption, still await confirmation regarding their applicability.

In the future, research teams might enhance their findings further by separating Alice and Bob into distinct computers. While this limits the chances of unmonitored interactions affecting outcomes of the quantum computer, the true utility of quantum dominance remains a critical issue, according to De Wolf.

“Progress beyond mere [quantum] dominance is essential for achieving [quantum] utility. Quantum computers currently outperform classical ones in specific areas of genuine interest, like some chemical computations and logistics optimization,” he suggests.