Quantum Supremacy Strengthened: New Experiments Push the Boundaries of Classical Physics

by

Author: Denis Avetisyan

Researchers have demonstrated a significant and robust violation of classical limits using a novel quantum experiment on trapped-ion hardware.

An exponentially large violation of classicality was achieved via complement sampling on Quantinuum’s trapped-ion quantum computers, providing further evidence for quantum computation and resilience against certain noise types.

Decades of testing quantum mechanics have increasingly relied on demonstrations tied to computational complexity and susceptible to hardware limitations. Here, in ‘Unconditional and exponentially large violation of classicality’, we present an experimental test of non-classicality based on a complement sampling game, achieving maximal separation between quantum and classical strategies without computational assumptions. Executed on Quantinuum trapped-ion quantum computers with up to 55 qubits, our experiments reveal an exponentially large violation of classicality, demonstrably attributable to quantum behavior. Does this efficiently verifiable approach offer a robust pathway towards characterizing and validating increasingly complex quantum hardware?

The Limits of Computation: Seeking Alternatives

Many computational problems, as they grow in complexity, demand resources – time and memory – that increase exponentially with the size of the input. This presents a fundamental limitation for classical computers, rendering certain tasks practically impossible even with the most powerful supercomputers. Consider, for example, simulating the behavior of molecules or optimizing complex logistical networks; the number of calculations required quickly becomes astronomical. This inherent difficulty fuels the investigation of non-classical approaches to computation, such as quantum computing, which leverage the principles of quantum mechanics to potentially overcome these exponential bottlenecks. The promise lies in harnessing phenomena like superposition and entanglement to perform calculations in a fundamentally different way, offering the possibility of tackling problems currently intractable for even the most advanced classical systems.

Establishing that a quantum system truly operates beyond the capabilities of classical computation – demonstrating what is known as non-classicality – presents a significant hurdle in quantum information science. The challenge arises because increasingly sophisticated classical algorithms and computational resources can mimic certain aspects of quantum behavior, making it difficult to definitively prove a quantum advantage. A result that appears to stem from quantum superposition or entanglement might, in fact, be achievable through clever classical programming and brute-force computation. Consequently, researchers require rigorous methods and carefully designed experiments to confidently distinguish genuine quantum effects from elaborate classical simulations, a necessity for validating the potential of quantum technologies and ensuring claims of quantum supremacy are not premature.

The complement sampling game provides a compelling benchmark for showcasing the power of quantum computation, offering a decisive advantage over even the most advanced classical algorithms. This game challenges a system to distinguish between probability distributions and their complements, a task where quantum strategies excel due to the inherent properties of superposition and entanglement. Recent implementations on a 37-qubit device have demonstrated a remarkable quantum-to-classical score ratio of up to $2^n$, indicating an exponential speedup – a feat unattainable with classical approaches. This isn’t merely theoretical promise; the observed performance gap validates the potential of quantum computers to solve specific problems with dramatically improved efficiency and serves as a critical step towards demonstrating practical quantum advantage.

A Protocol for Verification: The Complement Sampling Game

The complement sampling game utilizes subsets derived from instances of the Bernstein-Vazirani problem, a well-defined computational task, to construct a verification challenge. Specifically, the game presents a verifier with a subset of the Hamming weight-$k$ subsets of $\mathbb{F}_n^m$, where the subset is defined by evaluating a linear function $f: \mathbb{F}_n^m \to \mathbb{F}_2$. The function $f$ is constructed based on a hidden string $s$ and the Bernstein-Vazirani problem involves determining this hidden string $s$ given access to an oracle that computes $f(x) \cdot x$. This construction ensures that any strategy attempting to efficiently solve the complement sampling game must effectively address the underlying difficulty of the Bernstein-Vazirani problem, thereby creating a stringent test for both quantum and classical algorithms.

The complement sampling game offers a verification process with a favorable resource trade-off. While demonstrating a quantum advantage typically requires computational resources that scale exponentially with problem size, verifying this advantage within the complement sampling game requires only polynomial resources. Specifically, a verifier can confirm the claimed exponential speedup of a quantum strategy by evaluating a limited number of samples – a quantity that grows polynomially with the input size $n$. This efficiency stems from the game’s structure, which allows the verifier to focus on statistical properties of the samples rather than reconstructing the full solution, thus avoiding the computational bottleneck inherent in directly assessing exponential complexity.

The complement sampling game relies on the generation of truly random bit strings, denoted as $r$, to define the hidden subset used in the verification process. These bit strings, of length $n$, must be statistically independent and uniformly distributed to ensure the challenge presented to both classical and quantum strategies is unbiased. A robust random number generation (RNG) process is therefore critical; any predictability or correlation in the generated bit strings could allow a classical strategy to circumvent the verification, falsely indicating a lack of quantum advantage. Specifically, the RNG must produce bit strings that pass stringent statistical tests for randomness, such as those evaluating the frequency of 0s and 1s, and the length of consecutive identical bits, to guarantee the integrity of the game’s challenge.

Establishing True Randomness: Bell Tests and Quantum Teleportation

The generation of high-quality random numbers is critical for applications requiring unpredictability. While true randomness is difficult to achieve deterministically, pseudorandom number generators (PRNGs) offer a practical approximation. These PRNGs typically rely on pseudorandom permutations, which are constructed using cryptographic one-way functions. A one-way function is computationally efficient to execute in one direction, but computationally infeasible to reverse, providing a degree of security against prediction of the generated sequence. However, it is important to note that pseudorandom sequences are, by definition, deterministic and therefore not truly random; their quality is assessed by statistical tests and their resistance to various attacks.

Bell tests are employed to validate the randomness of generated bit sequences by demonstrating a violation of Bell inequalities, which would indicate correlations stronger than those achievable by any local hidden variable theory – effectively proving the bits are indistinguishable from truly random data. Specifically, a statistical analysis is performed, and a p-value is calculated to determine the probability of observing the obtained results if a classical strategy were in effect. A p-value less than 0.01 is the threshold for rejecting the null hypothesis of a classical strategy, thus confirming the quantum origin and genuine randomness of the generated bits. This rigorous statistical validation is critical to ensure fairness and unpredictability in applications relying on these random numbers.

Quantum teleportation facilitates secure delivery of random bits to the game referee by leveraging the principles of quantum entanglement and classical communication. This process does not transmit the actual quantum state of the random bit, but rather transfers the information encoded within it. Two entangled particles are distributed, one to the sender (random number generator) and one to the receiver (referee). The sender performs a Bell state measurement on their particle and the random bit, transmitting the classical result of this measurement to the referee. Using this classical information, the referee can reconstruct the original random bit’s state on their entangled particle. This method prevents any eavesdropping or manipulation of the random bits during transmission, as any attempt to intercept the quantum state would disturb the entanglement and be detectable, thereby guaranteeing unbiased evaluation.

Realizing the Advantage: Grover Diffusion and Hardware Fidelity

The core of this quantum approach lies in the application of the Grover diffusion operator, a technique designed to amplify the probability of finding correct solutions within a vast search space. In the context of the complement sampling game, this operator doesn’t simply test individual solutions, but intelligently navigates the entire solution landscape. By repeatedly applying Grover diffusion, the quantum system effectively ‘walks’ towards areas with a higher concentration of valid answers, significantly accelerating the search process. This is achieved through a quantum phenomenon where incorrect solutions interfere destructively, while correct ones constructively reinforce each other, making the identification of optimal solutions exponentially faster than any classical algorithm attempting a brute-force approach. The efficiency stems from the operator’s ability to explore all possibilities simultaneously, rather than sequentially, offering a substantial computational advantage.

Maintaining the delicate quantum state during computation requires robust error correction, as even minor disturbances can corrupt results. This work demonstrates the successful implementation of quantum error correction techniques, achieving a remarkably low memory error rate of $(1.20 \pm 0.20) \times 10^{-4}$ per qubit. This level of fidelity is crucial for extending the duration and complexity of quantum computations, effectively shielding the quantum information from the inevitable noise present in physical systems. By minimizing these errors, the stability and reliability of the quantum process are significantly enhanced, paving the way for more intricate and accurate quantum algorithms.

Recent demonstrations utilizing the Quantinuum System Model H2 have established a clear exponential speedup in computational performance compared to all known classical approaches. This advantage was realized through a strategy that achieves a quantum versus classical score ratio scaling up to $2^n$, showcasing the potential for increasingly significant gains as the problem size grows. Crucially, this performance was achieved on a 37-qubit device while maintaining high fidelity; two-qubit gates exhibited an infidelity of only $(8.30 \pm 0.48) \times 10^{-4}$, demonstrating the feasibility of implementing complex quantum algorithms with acceptable error rates on current hardware.

The study meticulously establishes a divergence from classical predictability, evidenced by an exponentially large violation observed in the complement sampling game. This resonates with de Broglie’s assertion: “It is in the interplay between waves and particles that the true nature of reality reveals itself.” The experiment doesn’t seek to define quantumness, but to demonstrate its existence through measurable deviation. The fidelity of Quantinuum’s trapped-ion system offers a platform where such subtle differences can be magnified, bypassing limitations imposed by noise and affirming a fundamentally non-classical behavior. The pursuit isn’t about achieving a perfect model, but about distilling the essence of the quantum realm.

Where Does This Leave Us?

The demonstration of an exponentially large violation of classicality, while mathematically satisfying, does not suddenly resolve the inherent ambiguities within the pursuit of quantum computation. It merely shifts the goalposts. The resilience of this particular method to certain noise profiles is noted, but noise – in all its insidious forms – remains the central, intractable problem. To focus solely on scaling up qubit counts without a concurrent, fundamental understanding of error mitigation is a distraction—a building of castles on sand.

The Bernstein-Vazirani problem, used as a benchmark, is a convenient starting point, but its limitations are self-evident. Future work should not cling to contrived problems designed to showcase quantum advantage. Instead, the challenge lies in identifying—or, more likely, constructing—practical applications where this demonstrably non-classical behavior translates into a tangible benefit, beyond the academic exercise. The true test will not be how far the quantum world diverges from the classical, but how efficiently it can solve a problem the classical world cannot.

Ultimately, the enduring question is not whether quantum computers can outperform classical ones – this work suggests they can, at least in principle – but whether that potential will ever be realized in a way that justifies the immense complexity of its pursuit. If simplicity is the hallmark of truth, then much work remains to be done.

Original article: https://arxiv.org/pdf/2511.11008.pdf

Contact the author: https://www.linkedin.com/in/avetisyan/

See also:

2025-11-17 12:11