ĢƵ

Unlocking Quantum Advantage with Complement Sampling

Quantum computing continues to push the boundaries of what is computationally possible.

February 25, 2025

BY HARRY BUHRMAN

Quantum computing continues to push the boundaries of what is computationally possible. 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 ̅ 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  ̅, 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 ̅ might be. However, a quantum algorithm can use a single superposition state over S (a quantum sample) to instantly generate a sample from ̅, 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 ̅. The method draws inspiration from a construction by Aaronson, Atia, and Susskind, which links state distinguishability to state swapping. The quantum algorithm:

  1. Uses a unitary transformation that maps the quantum sample |S⟩ to |̅⟩ with high probability.
  2. For K = N/2, the algorithm works perfectly outputting an element from ̅ with probability 1.
  3. 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:

  1. A referee provides a quantum player with quantum samples from S.
  2. The player must return a sample from ̅
  3. 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 ĢƵ

ĢƵ, the world’s largest integrated quantum company, pioneers powerful quantum computers and advanced software solutions. ĢƵ’s technology drives breakthroughs in materials discovery, cybersecurity, and next-gen quantum AI. With over 500 employees, including 370+ scientists and engineers, ĢƵ leads the quantum computing revolution across continents. 

Blog
|
technical
July 16, 2026
A New State in Quantum Computing
  • Researchers from ĢƵ, Caltech, the University of Chicago, and Harvard created a rare topologically ordered state of matter on ĢƵ's System Model H2 and used it to perform protected universal quantum gates with non-Abelian anyons.
  • The work explores an alternative approach to fault tolerance by using topological properties to protect quantum information. This could reduce the need for magic state distillation, which can (in some circumstances) be resource-intensive.
  • ĢƵ continues to show leadership in fault tolerance, with successful demonstrations spanning world record error rates to exotic approaches like topological computing

Quantum computing is all about putting the exotic properties of physics to work. Qubits can exist in two states at once, like the famous cat that is both alive and dead. Qubits can also be entangled, where the state of one will instantaneously affect the state of another - even when they have no way to “talk” to each other. Qubits can even be teleported, moving a quantum state from one place to another without physically moving it through space.

These features give quantum computing its power. But the ‘spooky’ nature of quantum computing doesn’t stop there: our quantum computers are potent enough to make exotic states of matter out of our qubits, and to perform calculations that would warp the mind of more traditional thinkers.

A new approach

In a recent paper published in Nature, researchers at ĢƵ teamed up with Caltech, the University of Chicago, and Harvard to create a rare ‘topologically ordered’ state of matter from our qubits.

When the qubits become ‘topologically ordered’, they become more than individual particles, now ‘related’ to each other in a specific way. This is like how hydrogen and oxygen act as individual gas particles alone, but you can put them together in a certain way so that they become water, a liquid, and an entirely different creature.

When the qubits become topologically ordered, the quantum information that they carried individually gets spread out over the whole system, which acts as a sort of protection from noise. This is like how a net makes a stronger barrier than a bunch of un-knotted ropes.

Once the researchers had topologically ordered qubits, they used the exotic particles that resulted (called non-Abelian anyons) to compute, performing error-protected gates and measurements.

To perform gates, the researchers 'braided' the anyons, which is like changing the shape of the “net”. This is something like the children’s game ‘cats cradle’. Through a sequence of changes to the “net”, the quantum computer can perform full calculations, one day helping scientists to understand the secrets hidden in the world around us.

Why go to such trouble? Well, for the love of discovery of course - but the team had an additional, specific motivation. One of the biggest challenges in building practical quantum computers is protecting them from errors while still being able to perform every operation needed for computation (this is referred to as universality).

This work takes a fresh approach to this challenge. Unlike traditional quantum error correction, the special properties of topological matter enable a universal set of fault tolerant gates without relying on expensive magic state distillation.

Why this matters

Quantum error correction is essential for large-scale quantum computing. While it protects fragile quantum information from noise by turning delicate physical qubits into robust logical qubits, it also introduces a significant constraint: not every quantum gate can be performed directly on logical qubits.

For decades, the standard solution has been to supplement error-corrected operations with magic states. These specially prepared quantum resources enable universal computation but can come at a steep cost - in many estimates of future fault-tolerant quantum computers, magic state preparation dominates both the physical qubit count and the runtime of useful algorithms.

Reducing this overhead has therefore become an important goal in quantum computing. This new approach may significantly reduce the cost by enabling the ‘topological preparation’ of magic states, eliding expensive protocols like distillation. If universal computation can be performed without large-scale magic state distillation, quantum computers could require significantly fewer physical qubits and spend much less time generating computational resources before running useful algorithms.

We will never stop exploring

While there is still considerable work ahead to understand the practical implementation and scalability of these ideas, this result expands the landscape of what's possible in quantum fault tolerance.

Of course, this impressive demonstration describes just one approach we are taking to fault tolerance at scale. We will continue to push forward with topological computing alongside more traditional approaches to quantum error correction, as well as exploring everything we can imagine in between. We are looking at a number of ways to reduce the resource cost of magic states in particular, and are making strides in multiple dimensions. With machines that are both flexible and accurate enough to do it all, who can resist?

technical
All
Blog
|
technical
June 10, 2026
ĢƵ's Fault-Tolerance Advantage: Turning Quantum Reliability into Commercial Usefulness
  • ĢƵ continues its progress toward fault-tolerant quantum computing, with a series of peer-reviewed breakthroughs in fault-tolerant operations.
  • Our progress is not only scientific; it is commercial. By improving logical-qubit reliability and encoding efficiency, ĢƵ is reducing the resource overhead required to scale its quantum computers toward commercially useful workloads.
  • These results were achieved on commercial ĢƵ hardware, reinforcing that our architecture is not just setting new standards, but building a practical foundation for customers, partners, and researchers preparing for the fault-tolerant era.

Fault-tolerant quantum computing is the threshold the industry must cross before quantum computers can solve the hardest, highest-value problems with confidence. To be commercially useful at scale, the question is not simply who can build more qubits. It is who can build reliable, efficient, scalable systems that reduce technical risk and accelerate the path to commercial usefulness.

ĢƵ is progressing on that path.

Last year, in partnership with Microsoft, we published a breakthrough in logical computing, demonstrating logical qubits that outperformed their physical counterparts by a factor of 800. We are proud to announce that this work is now being published in Nature, one of the most highly regarded scientific journals in the world.  

This work highlights our leading fidelities, as shown in Table 1:

Since then, we’ve accelerated our efforts to reach large-scale fault tolerance and advanced what we believe to be the core building blocks of fault-tolerant quantum computing, from logical-qubit teleportation and multiple error-correction breakthroughs to one of the first meaningful computations using logical qubits. Importantly, these results were achieved on commercial ĢƵ hardware, demonstrating not just scientific progress, but a practical and efficient path toward scalable, customer-ready fault tolerance.

A Recap of Our Recent Technical Progress

Since the work with Microsoft, we achieved a milestone years ahead of schedule, demonstrating high-fidelity teleportation of a logical qubit, which was published in one of the world’s most prestigious journals. Later, we beat our own record in this crucial fault tolerance milestone, thanks to continued improvements to our System Model H2’s fidelity.

Then, a series of results demonstrating more error-correcting milestones (and codes):

  • Better than physical results in a ,
  • (which significantly reduces resource requirements) in 4 dimensions
  • with a concatenated code
  • Observed with concatenated codes
  • High fidelity magic states and a fully fault tolerant universal gate set in two

Recently, we topped ourselves yet again by performing one of the first meaningful computations with logical qubits – exploring key questions in materials and magnetism, using . This result also includes a leading “encoding rate” squeezing 48 logical qubits out of just 98 physical qubits, emphasizing how our architecture helps to support large scale fault tolerance without enormous resource costs.

It is worth noting that all these results were achieved on our commercial hardware, not on one-off laboratory test-stands – reflecting the performance that we are able to deliver to our customers.

We also did crucial theoretical work, exploring that can reduce resource requirements, time to solution, and shorten the timeline to large scale fault tolerance.

Commercial Implications and the Road Ahead

We believe the commercial implication is clear: ĢƵ is reducing the uncertainty around the path to fault-tolerant quantum computing. Our architecture, hardware fidelity, full-stack control, and error-correction progress are converging into a practical roadmap for systems that can support valuable scientific and commercial workloads.

For those evaluating when quantum computing will become strategically relevant, we believe the signal is also increasingly clear: the fault-tolerant era is no longer a distant concept. It is becoming an engineering reality, and ĢƵ is leading the way.

technical
All
Blog
|
partnership
May 7, 2026
Denmark Strengthens its Quantum Leadership with ĢƵ Helios
  • University of Southern Denmark (SDU) to use ĢƵ Helios, supported by the Danish e-Infrastructure Consortium (DeiC)
  • Access to Helios enables SDU to test and refine fault-tolerant algorithms and error-correction codes under realistic hardware conditions
  • The collaboration supports at a scale of 48 logical qubits, positioning Denmark at the forefront of scalable, practical quantum computing
  • Researchers exploring the scientific foundations for future development of applications in fields including pharmaceuticals, finance, and defense

Progress in quantum computing is measured by hardware advances plus the algorithms and quantum error-correction codes that turn quantum systems into useful computational tools.

Thanks to recent hardware advances, researchers are increasingly sharpening their tools to probe the performance of quantum algorithms and understand how they behave in realistic conditions – where stability, system architecture and algorithm design all shape performance.

A new Denmark-based collaboration between the University of Southern Denmark (SDU), ĢƵ, and the Danish e-Infrastructure Consortium (DeiC) will utilize ĢƵ Helios. Researchers at the SDU’s Centre for Quantum Mathematics, led by Jørgen Ellegaard Andersen, will use Helios to pursue research into topological quantum computing.

Their work could help explain how and why successful quantum algorithms perform as they do, informing the development of high-performance algorithms suited to emerging quantum systems. They’re exploring the scientific foundations that support future quantum applications across areas including pharmaceuticals, finance, and defense.

“We are thrilled to gain access to ĢƵ’s high-fidelity Helios system. This collaboration gives us a unique opportunity to test the limits of our algorithms and evaluate system performance, while advancing fundamental research and laying the foundation for future applications.”

— Professor Jørgen Ellegaard Andersen, Director of the Centre for Quantum Mathematics at University of Southern Denmark
Why topological methods matter

Topological quantum computing is an area of research that connects quantum computation with deep mathematical structures. It includes the study of error correcting codes known as surface codes that encode quantum information in the global properties of systems of logical qubits.

The research team will explore how these codes behave, and how they may support the development of fault-tolerant quantum algorithms in practical implementations under realistic conditions.

This distinction between theory and practical implementation matters. In theory, topological approaches offer a rich framework for designing algorithms and error-correcting codes. In practice, researchers need to understand how those ideas perform when implemented on real systems, where questions of noise, stability, overhead, and scaling become central. The collaboration will allow the SDU team to investigate these questions directly.

New ways to benchmark quantum processors

Beyond individual algorithms and codes, the research will also develop tools for benchmarking quantum processors. The goal is to develop new ways to characterize fidelity and stability in regimes that can be difficult to access.

The team will also explore hybrid quantum–classical approaches, including machine-learning techniques assisted by quantum hardware, to study the mathematical structures at the heart of topological quantum computing. This work reflects a broader field of research in which quantum and classical methods are used together, each contributing to parts of a computational problem.

Strengthening Denmark’s quantum ecosystem

The collaboration reflects the growing role of national quantum infrastructure in supporting research and talent development. Denmark has a long tradition of scientific innovation, and this collaboration is intended to support the country’s continued development in quantum technology.

The initiative is supported by DeiC, which played a central role in securing funding and enabling access to ĢƵ’s systems. DeiC has been assigned a particular role in developing and coordinating quantum infrastructure initiatives for the benefit of universities and industry, operating without its own commercial, sectoral, or geographical interests. This includes securing dedicated access to quantum computers, producing advisory services and supporting the development of new talent in the Danish quantum sector.

“DeiC’s special effort to secure funding and access for this research initiative is rooted in our organization’s role in relation to the Danish Government’s strategy for quantum technology.”

— Henrik Navntoft Sønderskov, Head of Quantum at Danish e-Infrastructure Consortium

This collaboration promises to accelerate the development of practical algorithms. It is grounded in fundamental science – but its focus is practical: discovering and testing mathematical approaches to topological quantum computing that can be implemented, evaluated, and improved on real quantum hardware.

That work requires both theoretical insight and access to a system such as Helios capable of supporting meaningful scientific work.

partnership
All