Unlocking Quantum Advantage with Complement Sampling
Quantum computing continues to push the boundaries of what is computationally possible.
BY HARRY BUHRMAN
Quantum computing continues to push the boundaries of what is computationally possible. A new study by Marcello Benedetti, Harry Buhrman, and Jordi Weggemans introduces Complement Sampling, a problem that highlights a dramatic separation between quantum and classical sample complexity. This work provides a robust demonstration of quantum advantage in a way that is not only provable but also feasible on near-term quantum devices.
The Complement Sampling Problem
Imagine a universe of N = 2n elements, from which a subset S of size K is drawn uniformly at random. The challenge is to sample from the complement S̅ without explicitly knowing S, but having access to samples of S. Classically, solving this problem requires roughly K samples, as the best a classical algorithm can do is guess at random after observing only some of the elements of S.
To better understand this, consider a small example. Suppose N = 8, meaning our universe consists of the numbers {0,1,2,3,4,5,6,7}. If a subset S of size K = 4 is drawn at random—say {1,3,5,7}—the goal is to sample from the complement S̅, which consists of {0,2,4,6}. A classical algorithm would need to collect and verify enough samples from S before it could infer what S̅ might be. However, a quantum algorithm can use a single superposition state over S (a quantum sample) to instantly generate a sample from S̅, eliminating the need for iterative searching.
Why This Matters: Quantum Advantage in Sample Complexity
Quantum advantage is often discussed in terms of computational speedups, such as those achieved by Shor’s algorithm for factoring large numbers. However, quantum resources provide advantages beyond time efficiency—they also affect how data is accessed, stored, and processed.
Complement Sampling fits into the category of sample complexity problems, where the goal is to minimize the number of samples needed to solve a problem. The authors prove that their quantum approach not only outperforms classical methods but does so in a way that is:
- Provable: It provides rigorous lower bounds on classical sample complexity, demonstrating an exponential separation.
- Verifiable: The correctness of the output of the sampler can be efficiently checked classically.
- NISQable: The quantum circuit required is shallow and feasible for Noisy Intermediate-Scale Quantum (NISQ) devices.
How the Quantum Algorithm Works
At its core, the quantum approach to Complement Sampling relies on the ability to perform a perfect swap between a subset S and its complement S̅. The method draws inspiration from a construction by Aaronson, Atia, and Susskind, which links state distinguishability to state swapping. The quantum algorithm:
- Uses a unitary transformation that maps the quantum sample |S⟩ to |S̅⟩ with high probability.
- For K = N/2, the algorithm works perfectly outputting an element from S̅ with probability 1.
- For other values of K, a probabilistic zero-error approach is used, ensuring correctness while reducing success probability.
This is made possible by quantum interference and superposition, allowing a quantum computer to manipulate distributions in ways that classical systems fundamentally cannot.
Classical Hardness and Cryptographic Implications
A crucial aspect of this work is its robustness. The authors prove that even for subsets generated using strong pseudorandom permutations, the problem remains hard for classical algorithms. This means that classical computers cannot efficiently solve Complement Sampling even with structured input distributions—an important consideration for real-world applications.
This robustness suggests potential applications in cryptography, where generating samples from complements could be useful in privacy-preserving protocols and quantum-secure verification methods.
Towards an Experimental Demonstration
Unlike some quantum advantage demonstrations that are difficult to verify classically (such as the random circuit sampling experiment), Complement Sampling is designed to be verifiable. The authors propose an interactive quantum versus classical game:
- A referee provides a quantum player with quantum samples from S.
- The player must return a sample from S̅
- A classical player, given the same number of classical samples, attempts to do the same.
While the classical player must resort to random guessing, the quantum player can leverage the swap algorithm to succeed with near certainty. Running such an experiment on NISQ hardware could serve as a practical demonstration of quantum advantage in a sample complexity setting.
Future Directions
This research raises exciting new questions:
- Can Complement Sampling be extended to more general probability distributions?
- Are there cryptographic protocols that can directly leverage this advantage?
- How well does the quantum algorithm perform in real-world noisy conditions?
With its blend of theoretical depth and experimental feasibility, Complement Sampling provides a compelling new frontier for demonstrating the power of quantum computing.
Conclusion
Complement Sampling represents one of the cleanest demonstrations of quantum advantage in a practical, verifiable, and NISQ-friendly setting. By leveraging quantum information processing in ways that classical computers fundamentally cannot, this work strengthens the case for near-term quantum technologies and their impact on computational complexity, cryptography, and beyond.
For those interested in the full details, the paper provides rigorous proofs, circuit designs, and further insights into the nature of quantum sample complexity. As quantum computing continues to evolve, Complement Sampling may serve as a cornerstone for future experimental demonstrations of quantum supremacy.
We have commenced work on the experiment – watch this space!
About Quantinuum
Quantinuum, the world’s largest integrated quantum company, pioneers powerful quantum computers and advanced software solutions. Quantinuum’s technology drives breakthroughs in materials discovery, cybersecurity, and next-gen quantum AI. With over 500 employees, including 370+ scientists and engineers, Quantinuum leads the quantum computing revolution across continents.
By Dr. Noah Berthusen
The earliest works on quantum error correction showed that by combining many noisy physical qubits into a complex entangled state called a "logical qubit," this state could survive for arbitrarily long times. QEC researchers devote much effort to hunt for codes that function well as "quantum memories," as they are called. Many promising code families have been found, but this is only half of the story.
Being able to keep a qubit around for a long time is one thing, but to realize the theoretical advantages of quantum computing we need to run quantum circuits. And to make sure noise doesn't ruin our computation, these circuits need to be run on the logical qubits of our code. This is often much more challenging than performing gates on the physical qubits of our device, as these "logical gates" often require many physical operations in their implementation. What's more, it often is not immediately obvious which logical gates a code has, and so converting a physical circuit into a logical circuit can be rather difficult.
Some codes, like the famous surface code, are good quantum memories and also have easy logical gates. The drawback is that the ratio of physical qubits to logical qubits (the "encoding rate") is low, and so many physical qubits are required to implement large logical algorithms. High-rate codes that are good quantum memories have also been found, but computing on them is much more difficult. The holy grail of QEC, so to speak, would be a high-rate code that is a good quantum memory and also has easy logical gates. Here, we make progress on that front by developing a new code with those properties.
Building on prior error correcting codes
A recent work from Quantinuum QEC researchers introduced genon codes. The underlying construction method for these codes, called the "symplectic double cover," also provided a way to obtain logical gates that are well suited for Quantinuum's QCCD architecture. Namely, these "SWAP-transversal" gates are performed by applying single qubit operations and relabeling the physical qubits of the device. Thanks to the all-to-all connectivity facilitated through qubit movement on the QCCD architecture, this relabeling can be done in software essentially for free. Combined with extremely high fidelity (~1.2 x10-5) single-qubit operations, the resulting logical gates are similarly high fidelity.
Given the promise of these codes, we take them a step further in our new paper. We combine the symplectic double codes with the [[4,2,2]] Iceberg code using a procedure called "code concatenation". A concatenated code is a bit like nesting dolls, with an outer code containing codes within it---with these too potentially containing codes. More technically, in a concatenated code the logical qubits of one code act as the physical qubits of another code.
The new codes, which we call "concatenated symplectic double codes", were designed in such a way that they have many of these easily-implementable SWAP-transversal gates. Central to its construction, we show how the concatenation method allows us to "upgrade" logical gates in terms of their ease of implementation; this procedure may provide insights for constructing other codes with convenient logical gates. Notably, the SWAP-transversal gate set on this code is so powerful that only two additional operations (logical T and S) are necessary for universal computation. Furthermore, these codes have many logical qubits, and we also present numerical evidence to suggest that they are good quantum memories.
Concatenated symplectic double codes have one of the easiest logical computation schemes, and we didn’t have to sacrifice rate to achieve it. Looking forward in our roadmap, we are targeting hundreds of logical qubits at ~ 1x 10-8 logical error rate by 2029. These codes put us in a prime position to leverage the best characteristics of our hardware and create a device that can achieve real commercial advantage.
Every year, the International Conference for High Performance Computing, Networking, Storage, and Analysis (SC) brings together the global supercomputing community to explore the technologies driving the future of computing.
Join Quantinuum at this year’s conference, taking place November 16th – 21st in St. Louis, Missouri, where we will showcase how our quantum hardware, software, and partnerships are helping define the next era of high-performance and quantum computing.
Visit Quantinuum in the Expo Hall
The Quantinuum team will be on-site at booth #4432 to showcase how we’re building the bridge between HPC and quantum.
- Live demo unit of our quantum hardware
- Our new Helios replica, providing an up-close look at the design behind our next-generation system
- The Helios chip, highlighting the innovation driving the world’s most advanced trapped-ion quantum computers
From Monday through Wednesday, our quantum computing experts will host daily tutorials at our booth on Helios, our next-generation hardware platform, Nexus, our all-in-one quantum computing platform, and Hybrid Workflows, featuring the integration of NVIDIA CUDA-Q with Quantinuum Systems.
Register for a tutorial
Speaking Sessions at SC25
Join our team as they share insights on the opportunities and challenges of quantum integration within the HPC ecosystem:
Panel Session: The Quantum Era of HPC: Roadmaps, Challenges and Opportunities in Navigating the Integration Frontier
November 19th | 10:30 – 12:00pm CST
During this panel session, Kentaro Yamamoto from Quantinuum, will join experts from Lawrence Berkeley National Laboratory, IBM, QuEra, RIKEN, and Pawsey Supercomputing Research Centre to explore how quantum and classical systems are being brought together to accelerate scientific discovery and industrial innovation.
BoF Session: Bridging the Gap: Making Quantum-Classical Hybridization Work in HPC
November 19th | 5:15 – 6:45pm CST
Quantum-classical hybrid computing is moving from theory to reality, yet no clear roadmap exists for how best to integrate quantum processing units (QPUs) into established HPC environments. In this Birds of a Feather discussion, co-led by Quantinuum’s Grahame Vittorini and representatives from BCS, DOE, EPCC, Inria, ORNL NVIDIA, and RIKEN we hope to bring together a global community of HPC practitioners, system architects, quantum computing specialists and workflow researchers, including participants in the Workflow Community Initiative, to assess the state of hybrid integration and identify practical steps toward scalable, impactful deployment.
Quantinuum’s real world experiment, on the world’s most powerful quantum computer, is the largest of its kind— so large that no amount of classical computing could match it
In 1911, a student working under famed physicist Heike Kamerlingh Onnes made a discovery that would rewire our understanding of electricity. The student was studying the electrical resistance of wires, a seemingly simple question that held secrets destined to surprise the world.
Kamerlingh Onnes had recently succeeded in liquefying helium, a feat so impressive it earned him the Nobel Prize in Physics two years later. With this breakthrough, scientists could now immerse other materials in a cold bath of liquid Helium, cooling things to unprecedented temperatures and observing their behavior.
Many theories existed about what would happen to a wire at such low temperatures. Lord Kelvin predicted that electrons would freeze in place, making the resistance infinite and stopping the conduction of electricity. Others expected resistance to decrease linearly with temperature—a hypothesis that led to thermometer designs still in use today.
When the student cooled a mercury wire to 3.6 degrees above absolute zero, he found something remarkable: the electrical resistivity suddenly vanished.
Onnes quickly devised an ingenious experiment: as a diligent researcher, he knew that he needed to validate these surprising findings. He took a closed loop of wire, set a current running through it, and watched as it flowed endlessly without fading—a type of perpetual motion that seemed to defy everything we know about physics. And so, superconductivity was born.
More than a century later, all known superconductors still require extreme conditions like brutal cold or high pressure. If we could instead design a material that superconducts at room temperature, and under normal conditions, our world would be profoundly reshaped. “Room temperature superconductivity”, as it is generally called, would enable a raft of technological breakthroughs from affordable MRI machines to nearly lossless power grids.
Designing such a material means answering many open questions, and scientists are pursuing diverse strategies to find answers. One promising approach is light-induced superconductivity. In one astonishing study, researchers at the Max Planck Institute in Hamburg used light to entice a material that normally superconducts at roughly -180 °C to superconduct at room temperature - but only for a few picoseconds. This effect raised new questions: how does light achieve something that scientists have been grappling with for decades? What is the microscopic mechanism behind this phenomenon? Could understanding it unlock practical room-temperature superconductors?
Nature’s language is mathematics and mathematics is the language of the world’s most powerful quantum computer, Helios
Physics is a surprisingly profound field when you stop to think about it. At its core lies the idea that nature speaks the language of mathematics—and that by discovering the right equations, we can reveal her secrets. As bold as that sounds, history has proven it true time and again. Whenever we peek behind the veil; mathematics is there.
To understand a phenomena like superconductivity, physicists first need a mathematical model, or a set of equations that describe how it works. With the right model, they can predict and even design new superconductors that operate under more practical conditions. This is a key frontier in the search for room temperature superconductors, one of science’s holy grails.
Since the discovery of superconductivity, a lot of work has gone into finding this right model – one that can act as a sort of ‘Rosetta stone’ for harnessing this phenomenon. One of the best bets for describing high temperature superconductors like the one in the Hamburg study is called the “non-equilibrium Fermi-Hubbard” model, which describes how electrons interact and move in a crystal.
A surprising element of models that describe superconductivity is the prediction that electrons ‘pair up’ when the material becomes superconducting, dancing around in a waltz, two at a time. These pairs are referred to as “cooper pairs” after the famous physicist Leon Cooper. Now, scientists studying superconductors look for “pairing correlations”, a key signature of superconductivity.
Even armed with the Fermi-Hubbard model, light-induced superconductivity has been very difficult to study. The world’s most powerful supercomputers can only handle very small versions, limiting their utility. Even quantum platforms, like analog simulators, limit researchers to observing ‘average’ quantities and obscuring the microscopic details that are crucial for unravelling this mystery.
Light-induced superconductivity has proved challenging to study with quantum computers as well, as doing so requires low error rates, many qubits, and extreme flexibility to measure the fickle symptoms of superconductivity.
That was, until now: Quantinuum’s Helios is one of the first machines in the world able to handle the complexity of the non-equilibrium Fermi-Hibbard model at scales previously out of reach.
Hopping across the lattice and connecting the dots
Before Helios, we were limited to small explorations of this model, stalling research on this critical frontier. Now, with Helios, we have a quantum computer uniquely suited for this problem. With a novel fermionic encoding and using up to 90 qubits (72 system qubits plus 18 ancilla), Helios can simulate the dynamics of a 6×6 lattice — a system so large that its full quantum state spans over 2^72 dimensions.
Using Helios to study a system like this offers researchers a sort of “qubit-based laboratory.” Capable of handling complex quantum mechanical effects better than classical computers, Helios allows researchers to thoroughly explore phenomena like this without wasting expensive laboratory time and materials, or spending lots of money and energy running it on a supercomputer.
Our qubit-based laboratory is a dream come true for several reasons. First, it allows arbitrary state preparation – preparing states far from equilibrium, a challenging task for classical computers. Second, it allows for meaningfully long ‘dynamical simulation’ – seeing how the state evolves in time as entanglement spreads and complexity increases. This is notoriously difficult for classical computers, in part due to their difficulty with handling distinctly quantum phenomena like entanglement. Finally, it allows for flexible measurements and experimental parameters – you can measure any observable, including critical “off-diagonal” observables that carry the signature of superconductivity, and simulate any system, such as those with laser pulses or electric fields.
This last point is the most significant. While analog quantum simulators, like cold atom systems, can take snapshots of atom positions or measure densities, they struggle with off-diagonal observables—the very ones that signal the formation of Cooper pairs in superconductors.
Breaking new ground: a light-induced pairing
In our work, we've simulated three different regimes of the Fermi-Hubbard model and successfully measured non-zero superconducting pairing correlations — a first for any quantum computing platform.
We began by preparing a low-energy state of the model at half-filling — a standard benchmark for testing quantum simulations. Then, using simulated laser pulses or electric fields, we perturbed the system and observed how it responded.
After these perturbations, we measured a notable increase in the so-called “eta” pairing correlations, a mathematical signature of superconducting behavior. These results prove that our computers can help us understand light-induced superconductivity, such as the results from the Max Planck researchers. However, unlike those physical experiments, Helios offers a new level of control and insight. By tuning every aspect of the simulation — from pulse shape, to field strength, to lattice geometry — researchers can explore scenarios that are completely inaccessible to real materials or analog simulators.
Looking to a future where superconductors permeate our lives
Why does any of this matter? If we could predict which materials will become superconducting — and at what temperature, field, or current — it would transform how we search for new superconductors. Instead of trial-and-error in the lab, scientists could design and test new materials digitally first, saving huge amounts of time and money.
In the long run, Helios and its successors will become essential tools for materials science — not just confirming theories but generating new ones. And perhaps, one day, they’ll help us crack the code behind room-temperature superconductors.
Until then, the quantum revolution continues, one entangled pair at a time.