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.
Quantinuum and NVIDIA, world leaders in their respective sectors, are combining forces to fast-track commercially scalable quantum supercomputers, further bolstering the announcement Quantinuum made earlier this year about the exciting new potential in Generative Quantum AI.
Make no mistake about it, the global quantum race is on. With over $2 billion raised by companies in 2024 alone, and over 150 new startups in the past five years, quantum computing is no longer restricted to ‘the lab’.
The United Nations proclaimed 2025 as the International Year of Quantum Science and Technology (IYQ), and as we march toward the end of the first quarter, the old maxim that quantum computing is still a decade (or two, or three) away is no longer relevant in today’s world. Governments, commercial enterprises and scientific organizations all stand to benefit from quantum computers, led by those built by Quantinuum.
That is because, amid the flurry of headlines and social media chatter filled with aspirational statements of future ambitions shared by those in the heat of this race, we at Quantinuum continue to lead by example. We demonstrate what that future looks like today, rather than relying solely on slide deck presentations.
Our quantum computers are the most powerful systems in the world. Our H2 system, the only quantum computer that cannot be classically simulated, is years ahead of any other system being developed today. In the coming months, we’ll introduce our customers to Helios, a trillion times more powerful than H2, further extending our lead beyond where the competition is still only planning to be.
At Quantinuum, we have been convinced for years that the impact of quantum computers on the real world will happen earlier than anticipated. However, we have known that impact will be when powerful quantum computers and powerful classical systems work together.
This sort of hybrid ‘supercomputer’ has been referenced a few times in the past few months, and there is, rightly, a sense of excitement about what such an accelerated quantum supercomputer could achieve.
The Power of Hybrid Quantum and Classical Compute
In a revolutionary move on March 18th, 2025, at the GTC AI conference, NVIDIA announced the opening of a world-class accelerated quantum research center with Quantinuum selected as a key founding collaborator to work on projects with NVIDIA at the center.
With details shared in an accompanying press statement and blog post, the NVIDIA Accelerated Quantum Research Center (NVAQC) being built in Boston, Massachusetts, will integrate quantum computers with AI supercomputers to ultimately explore how to build accelerated quantum supercomputers capable of solving some of the world’s most challenging problems. The center will begin operations later this year.
As shared in Quantinuum’s accompanying statement, the center will draw on the NVIDIA CUDA-Q platform, alongside a NVIDIA GB200 NVL72 system containing 576 NVIDIA Blackwell GPUs dedicated to quantum research.
The Role of CUDA-Q in Quantum-Classical Integration
Integrating quantum and classical hardware relies on a platform that can allow researchers and developers to quickly shift context between these two disparate computing paradigms within a single application. NVIDIA CUDA-Q platform will be the entry-point for researchers to exploit the NVAQC quantum-classical integration.
In 2022, Quantinuum became the first company to bring CUDA-Q to its quantum systems, establishing a pioneering collaboration that continues to today. Users of CUDA-Q are currently offered access to Quantinuum’s System H1 QPU and emulator for 90 days.
Quantinuum’s future systems will continue to support the CUDA-Q platform. Furthermore, Quantinuum and NVIDIA are committed to evolving and improving tools for quantum classical integration to take advantage of the latest hardware features, for example, on our upcoming Helios generation.
The Gen-Q-AI Moment
A few weeks ago, we disclosed high level details about an AI system that we refer to as Generative Quantum AI, or GenQAI. We highlighted a timeline between now and the end of this year when the first commercial systems that can accelerate both existing AI and quantum computers.
At a high level, an AI system such as GenQAI will be enhanced by access to information that has not previously been accessible. Information that is generated from a quantum computer that cannot be simulated. This information and its effect can be likened to a powerful microscope that brings accuracy and detail to already powerful LLM’s, bridging the gap from today’s impressive accomplishments towards truly impactful outcomes in areas such as biology and healthcare, material discovery and optimization.
Through the integration of the most powerful in quantum and classical systems, and by enabling tighter integration of AI with quantum computing, the NVAQC will be an enabler for the realization of the accelerated quantum supercomputer needed for GenQAI products and their rapid deployment and exploitation.
Innovating our Roadmap
The NVAQC will foster the tools and innovations needed for fully fault-tolerant quantum computing and will be enabler to the roadmap Quantinuum released last year.
With each new generation of our quantum computing hardware and accompanying stack, we continue to scale compute capabilities through more powerful hardware and advanced features, accelerating the timeline for practical applications. To achieve these advances, we integrate the best CPU and GPU technologies alongside our quantum innovations. Our long-standing collaboration with NVIDIA drives these advancements forward and will be further enriched by the NVAQC.
Here are a couple of examples:
In quantum error correction, error syndromes detected by measuring "ancilla" qubits are sent to a "decoder." The decoder analyzes this information to determine if any corrections are needed. These complex algorithms must be processed quickly and with low latency, requiring advanced CPU and GPU power to calculate and apply corrections keeping logical qubits error-free. Quantinuum has been collaborating with NVIDIA on the development of customized GPU-based decoders which can be coupled with our upcoming Helios system.
In our application space, we recently announced the integration of InQuanto v4.0, the latest version of Quantinuum’s cutting edge computational chemistry platform, with NVIDIA cuQuantum SDK to enable previously inaccessible tensor-network-based methods for large-scale and high-precision quantum chemistry simulations.
Our work with NVIDIA underscores the partnership between quantum computers and classical processors to maximize the speed toward scaled quantum computers. These systems offer error-corrected qubits for operations that accelerate scientific discovery across a wide range of fields, including drug discovery and delivery, financial market applications, and essential condensed matter physics, such as high-temperature superconductivity.
We look forward to sharing details with our partners and bringing meaningful scientific discovery to generate economic growth and sustainable development for all of humankind.
In the rapidly advancing world of quantum computing, to be a leader means not just keeping pace with innovation but driving it forward. It means setting new standards that shape the future of quantum computing performance. A recent independent study comparing 19 quantum processing units (QPUs) on the market today has validated what we’ve long known to be true: Quantinuum’s systems are the undisputed leaders in performance.
The Benchmarking Study
A comprehensive study conducted by a joint team from the Jülich Supercomputing Centre, AIDAS, RWTH Aachen University, and Purdue University compared QPUs from leading companies like IBM, Rigetti, and IonQ, evaluating how well each executed the Quantum Approximate Optimization Algorithm (QAOA), a widely used algorithm that provides a system level measure of performance. After thorough examination, the study concluded that:
“...the performance of quantinuum H1-1 and H2-1 is superior to that of the other QPUs.”
Quantinuum emerged as the clear leader, particularly in full connectivity, the most critical category for solving real-world optimization problems. Full connectivity is a huge comparative advantage, offering more computational power and more flexibility in both error correction and algorithmic design. Our dominance in full connectivity—unattainable for platforms with natively limited connectivity—underscores why we are the partner of choice in quantum computing.
Leading Across the Board
We take benchmarking seriously at Quantinuum. We lead in nearly every industry benchmark, from best-in-class gate fidelities to a 4000x lead in quantum volume, delivering top performance to our customers.
Our Quantum Charged-coupled Device (QCCD) architecture has been the foundation of our success, delivering consistent performance gains year-over-year. Unlike other architectures, QCCD offers all-to-all connectivity, world-record fidelities, and advanced features like real-time decoding. Altogether, it’s clear we have superior performance metrics across the board.
While many claim to be the best, we have the data to prove it. This table breaks down industry benchmarks, using the leading commercial spec for each quantum computing architecture.
These metrics are the key to our success. They demonstrate why Quantinuum is the only company delivering meaningful results to customers at a scale beyond classical simulation limits.
Our progress builds upon a series of Quantinuum’s technology breakthroughs, including the creation of the most reliable and highest-quality logical qubits, as well as solving the key scalability challenge associated with ion-trap quantum computers — culminating in a commercial system with greater than 99.9% two-qubit gate fidelity.
From our groundbreaking progress with System Model H2 to advances in quantum teleportation and solving the wiring problem, we’re taking major steps to tackle the challenges our whole industry faces, like execution speed and circuit depth. Advancements in parallel gate execution, faster ion transport, and high-rate quantum error correction (QEC) are just a few ways we’re maintaining our lead far ahead of the competition.
This commitment to excellence ensures that we not only meet but exceed expectations, setting the bar for reliability, innovation, and transformative quantum solutions.
Onward and Upward
To bring it back to the opening message: to be a leader means not just keeping pace with innovation but driving it forward. It means setting new standards that shape the future of quantum computing performance.
We are just months away from launching Quantinuum’s next generation system, Helios, which will be one trillion times more powerful than H2. By 2027, Quantinuum will launch the industry’s first 100-logical-qubit system, featuring best-in-class error rates, and we are on track to deliver fault-tolerant computation on hundreds of logical qubits by the end of the decade.
The evidence speaks for itself: Quantinuum is setting the standard in quantum computing. Our unrivaled specs, proven performance, and commitment to innovation make us the partner of choice for those serious about unlocking value with quantum computing. Quantinuum is committed to doing the hard work required to continue setting the standard and delivering on our promises. This is Quantinuum. This is leadership.
Dr. Chris Langer is a Fellow, a key inventor and architect for the Quantinuum hardware, and serves as an advisor to the CEO.
_______________________________________
Citations from Benchmarking Table
1 Quantinuum. System Model H2. Quantinuum, https://www.quantinuum.com/products-solutions/quantinuum-systems/system-model-h2
2 IBM. Quantum Services & Resources. IBM Quantum, https://quantum.ibm.com/services/resources
3 Quantinuum. System Model H1. Quantinuum, https://www.quantinuum.com/products-solutions/quantinuum-systems/system-model-h1
4 Google Quantum AI. Willow Spec Sheet. Google, https://quantumai.google/static/site-assets/downloads/willow-spec-sheet.pdf
5 Sales Rodriguez, P., et al. "Experimental demonstration of logical magic state distillation." arXiv, 19 Dec 2024, https://arxiv.org/pdf/2412.15165
6 Quantinuum. H1 Product Data Sheet. Quantinuum, https://docs.quantinuum.com/systems/data_sheets/Quantinuum%20H1%20Product%20Data%20Sheet.pdf
7 Google Quantum AI. Willow Spec Sheet. Google, https://quantumai.google/static/site-assets/downloads/willow-spec-sheet.pdf
8 Sales Rodriguez, P., et al. "Experimental demonstration of logical magic state distillation." arXiv, 19 Dec 2024, https://arxiv.org/pdf/2412.15165
9 Quantinuum. H2 Product Data Sheet. Quantinuum, https://docs.quantinuum.com/systems/data_sQuantinuum. H2 Product Data Sheet. Quantinuum,heets/Quantinuum%20H2%20Product%20Data%20Sheet.pdf
10 Google Quantum AI. Willow Spec Sheet. Google, https://quantumai.google/static/site-assets/downloads/willow-spec-sheet.pdf
11 Sales Rodriguez, P., et al. "Experimental demonstration of logical magic state distillation." arXiv, 19 Dec 2024, https://arxiv.org/pdf/2412.15165
12 Moses, S. A., et al. "A Race-Track Trapped-Ion Quantum Processor." Physical Review X, vol. 13, no. 4, 2023, https://journals.aps.org/prx/pdf/10.1103/PhysRevX.13.041052
13 Google Quantum AI and Collaborators. "Quantum Error Correction Below the Surface Code Threshold." Nature, vol. 638, 2024, https://www.nature.com/articles/s41586-024-08449-y
14 Bluvstein, Dolev, et al. "Logical Quantum Processor Based on Reconfigurable Atom Arrays." Nature, vol. 626, 2023, https://www.nature.com/articles/s41586-023-06927-3
15 DeCross, Matthew, et al. "The Computational Power of Random Quantum Circuits in Arbitrary Geometries." arXiv, Published on 21 June 2024, hhttps://arxiv.org/pdf/2406.02501
16 Montanez-Barrera, J. A., et al. "Evaluating the Performance of Quantum Process Units at Large Width and Depth." arXiv, 10 Feb. 2025, https://arxiv.org/pdf/2502.06471
17 Evered, Simon J., et al. "High-Fidelity Parallel Entangling Gates on a Neutral-Atom Quantum Computer." Nature, vol. 622, 2023, https://www.nature.com/articles/s41586-023-06481-y
18 Ryan-Anderson, C., et al. "Realization of Real-Time Fault-Tolerant Quantum Error Correction." Physical Review X, vol. 11, no. 4, 2021, https://journals.aps.org/prx/abstract/10.1103/PhysRevX.11.041058
19 Carrera Vazquez, Almudena, et al. "Scaling Quantum Computing with Dynamic Circuits." arXiv, 27 Feb. 2024, https://arxiv.org/html/2402.17833v1
20 Moses, S.A.,, et al. "A Race Track Trapped-Ion Quantum Processor." arXiv, 16 May 2023, https://arxiv.org/pdf/2305.03828
21 Garcia Almeida, D., Ferris, K., Knanazawa, N., Johnson, B., Davis, R. "New fractional gates reduce circuit depth for utility-scale workloads." IBM Quantum Blog, IBM, 18 Nov. 2020, https://www.ibm.com/quantum/blog/fractional-gates
22 Ryan-Anderson, C., et al. "Realization of Real-Time Fault-Tolerant Quantum Error Correction." arXiv, 15 July 2021, https://arxiv.org/pdf/2107.07505
23 Google Quantum AI and Collaborators. “Quantum error correction below the surface code threshold.” arXiv, 24 Aug. 2024, https://arxiv.org/pdf/2408.13687v1
The 2025 Joint March Meeting and April Meeting — referred to as the APS Global Physics Summit — is the largest physics research conference in the world, uniting 14,000 scientific community members across all disciplines of physics.
The Quantinuum team is looking forward to participating in this year’s conference to showcase our latest advancements in quantum technology. Find us throughout the week at the below sessions and visit us at Booth 1001.
Join these sessions to discover how Quantinuum is advancing quantum computing
T11: Quantum Error Correction
Speaker: Natalie Brown
Date: Sunday, March 16th
Time: 8:00 – 8:12am
Location: Anaheim Convention Center, 261B (Level 2)
The computational power of random quantum circuits in arbitrary geometries
Session MAR-F34: Near-Term Quantum Resource Reduction and Random Circuits
Speaker: Matthew DeCross
Date: Tuesday, March 18th
Time: 8:00 – 8:12am
Location: Anaheim Convention Center, 256A (Level 2)
Topological Order from Measurements and Feed-Forward on a Trapped Ion Quantum Computer
Session MAR-F14: Realizing Topological States on Quantum Hardware
Speaker: Henrik Dreyer
Date: Tuesday, March 18th
Time: 9:12 – 9:48am
Location: Anaheim Convention Center, 158 (Level 1)
Trotter error time scaling separation via commutant decomposition
Session MAR-F34: Near-Term Quantum Resource Reduction and Random Circuits
Speaker: Yi-Hsiang Chen (Quantinuum)
Date: Tuesday, March 18th
Time: 10:00 – 10:12am
Location: Anaheim Convention Center, 256A (Level 2)
Squared overlap calculations with linear combination of unitaries
Session MAR-J35: Circuit Optimization and Compilation
Speaker: Michelle Wynne Sze
Date: Tuesday, March 18th
Time: 4:36 – 4:48pm
Location: Anaheim Convention Center, 256B (Level 2)
High-precision quantum phase estimation on a trapped-ion quantum computer
Session MAR-L16: Quantum Simulation for Quantum Chemistry
Speaker: Andrew Tranter
Date: Wednesday, March 19th
Time: 9:48 – 10:00am
Location: Anaheim Convention Center, 160 (Level 1)
Robustness of near-thermal dynamics on digital quantum computers
Session MAR-L16: Quantum Simulation for Quantum Chemistry
Speaker: Eli Chertkov
Date: Wednesday, March 19th
Time: 10:12 – 10:24am
Location: Anaheim Convention Center, 160 (Level 1)
Floquet prethermalization on a digital quantum computer
Session MAR-Q09: Quantum Simulation of Condensed Matter Physics
Speaker: Reza Haghshenas
Date: Thursday, March 20th
Time: 10:00 – 10:12am
Location: Anaheim Convention Center, 204C (Level 2)
Teleportation of a Logical Qubit on a Trapped-ion Quantum Computer
Session MAR-S11: Advances in QEC Experiments
Speaker: Ciaran Ryan-Anderson
Date: Thursday, March 20th
Time: 11:30 – 12:06pm
Location: Anaheim Convention Center, 155 (Level 1)
*All times in Pacific Standard Time