Related Experiment Video
Updated: Feb 18, 2026
05:30
Large Scale Energy Efficient Sensor Network Routing Using a Quantum Processor Unit
Published on: September 8, 2023
1.2K
Provable and Verifiable Quantum Advantage in Sample Complexity
Marcello Benedetti1, Harry Buhrman1,2,3, Jordi Weggemans2,4
1Quantinuum, London, United Kingdom.
Physical Review Letters
|February 16, 2026
Summary
This study introduces a quantum algorithm for complement sampling, efficiently finding elements in a complementary set. Quantum computation offers significant advantages over classical methods in sample complexity, especially for noisy intermediate-scale quantum devices.
Area of Science:
- Quantum Computing
- Computational Complexity
- Information Theory
Background:
- Complement sampling involves obtaining a sample from a complementary subset given samples from a subset.
- Classical algorithms require numerous samples for complement sampling, especially when subset sizes are large.
Purpose of the Study:
- To develop a quantum algorithm for complement sampling.
- To demonstrate quantum advantage in sample complexity compared to classical algorithms.
- To explore the potential for noisy intermediate-scale quantum (NISQ) computer implementations.
Main Methods:
- A simple quantum algorithm utilizing a single quantum sample (uniform superposition) was developed.
- Analysis of the algorithm's success probability and comparison with classical sample complexity bounds.
- Extension of results to prove average-case hardness.
Main Results:
- The quantum algorithm achieves a 100% success probability for complement sampling when subset sizes are equal (K=N/2).
- Classical algorithms require samples proportional to N for comparable success probability.
- The quantum approach demonstrates the largest possible separation in sample complexity.
Conclusions:
- Quantum computation offers provable and verifiable advantages in sample complexity for complement sampling.
- The algorithm is suitable for demonstration on NISQ computers.
- Complement sampling provides a pathway to quantum advantage under the assumption of one-way functions.
Related Concept Videos
01:15Sampling Theorem
1.4K
In signal processing, the analysis of continuous-time signals, denoted as x(t), often involves sampling techniques to convert these signals into discrete-time signals. This process is essential for digital representation and manipulation. A critical component in sampling is the train of impulses, characterized by the sampling interval and the sampling frequency. The relationship between these parameters and the original signal's properties dictates the success of the sampling process.
1.4K
02:45The Quantum-Mechanical Model of an Atom
59.9K
Shortly after de Broglie published his ideas that the electron in a hydrogen atom could be better thought of as being a circular standing wave instead of a particle moving in quantized circular orbits, Erwin Schrödinger extended de Broglie’s work by deriving what is now known as the Schrödinger equation. When Schrödinger applied his equation to hydrogen-like atoms, he was able to reproduce Bohr’s expression for the energy and, thus, the Rydberg formula governing hydrogen spectra.
59.9K
01:14Norton's Theorem
1.5K
Norton's theorem is a fundamental principle stating that a linear two-terminal circuit can be substituted with an equivalent circuit, which comprises a current source (ⅠN) in parallel with a resistor (RN). Here, ⅠN represents the short-circuit current flowing through the terminals, and RN stands for the input or equivalent resistance at the terminals when all independent sources are deactivated. This implies that the circuit illustrated in Figure (a) can be exchanged with the one depicted...
1.5K
00:59Biot-Savart Law: Problem-Solving
4.0K
The magnitude and direction of a magnetic field created by a steady current can be calculated using the Biot-Savart law.
Consider a mobile phone battery bank as a source of steady current, which flows through the wire connected between the two. What is the magnitude of the magnetic field created by this current at a field point P?
To estimate the magnitude of the total magnetic field, we first consider a small current element of length dl, at a distance r from the field point. Now the following...
Consider a mobile phone battery bank as a source of steady current, which flows through the wire connected between the two. What is the magnitude of the magnetic field created by this current at a field point P?
To estimate the magnitude of the total magnetic field, we first consider a small current element of length dl, at a distance r from the field point. Now the following...
4.0K
04:08The Uncertainty Principle
33.3K
Werner Heisenberg considered the limits of how accurately one can measure properties of an electron or other microscopic particles. He determined that there is a fundamental limit to how accurately one can measure both a particle’s position and its momentum simultaneously. The more accurate the measurement of the momentum of a particle is known, the less accurate the position at that time is known and vice versa. This is what is now called the Heisenberg uncertainty principle. He...
33.3K
01:16Second Uniqueness Theorem
2.7K
Consider a region consisting of several individual conductors with a definite charge density in the region between these conductors. The second uniqueness theorem states that if the total charge on each conductor and the charge density in the in-between region are known, then the electric field can be uniquely determined.
In contrast, consider that the electric field is non-unique and apply Gauss's law in divergence form in the region between the conductors and the integral form to the surface...
In contrast, consider that the electric field is non-unique and apply Gauss's law in divergence form in the region between the conductors and the integral form to the surface...
2.7K