Quantum Rejection Sampling

Overview

Rejection sampling is a classical method for drawing samples from a target distribution by drawing from an easier distribution and accepting each sample with a probability proportional to the ratio of the two. Samples that are rejected are wasted, so the cost grows with the rejection rate. Quantum rejection sampling does the same thing coherently: given a quantum state whose amplitudes encode one distribution, it prepares a state whose amplitudes encode a different target distribution.

The quantum version replaces repeated trials with amplitude amplification, so the cost scales with the square root of the factor that classical rejection sampling pays. It is a primitive inside larger algorithms, and Ozols, Roetteler, and Roland showed that it explains the key step of the HHL algorithm and speeds up quantum Metropolis sampling.

The problem it solves

Generate samples from a hard target distribution π using a simpler proposal distribution σ, with fewer quantum samples than classical rejection sampling requires.

History and background

Classical rejection sampling was formalized by John von Neumann in 1951. On the quantum side, Grover showed in 2000 how to synthesize quantum superpositions corresponding to desired amplitude patterns, and Aharonov and Ta-Shma introduced the idea of quantum sampling, or qsampling, in 2003, in which the goal is to prepare a state whose amplitudes are square roots of probabilities.

Ozols, Roetteler, and Roland defined quantum rejection sampling in 2012 and gave a tight characterization of its query complexity, with the proof of optimality using semidefinite programming and the automorphism principle. They showed three uses: the amplitude-conditioning step in HHL, a speedup of the main step in the quantum Metropolis algorithm of Temme and coauthors, and a new algorithm for the hidden shift problem. In 2014 Low, Yoder, and Chuang used amplitude amplification to give a quadratic speedup for inference in Bayesian networks, a closely related application.

How it works

Prepares a quantum state encoding the proposal distribution. Uses amplitude amplification to boost the probability of the accepted sample, achieving a quadratic improvement over classical rejection sampling in some settings.

Suppose you can prepare a quantum state that holds a superposition of many items, each with a certain amplitude, and you want a superposition of the same items with different amplitudes. Classically you would draw an item, flip a biased coin to decide whether to keep it, and repeat until you keep one. If the keep probability is small, you waste many draws.

The quantum version first prepares the superposition, then rotates an ancilla qubit by an angle that depends on each item and on the ratio of target to source amplitudes, so that the ancilla is in the state good with a probability equal to the keep probability. After this step, the good branch of the state has exactly the target amplitudes, but it has small weight overall.

Amplitude amplification then boosts the weight of the good branch to nearly 1, using a number of rounds proportional to the inverse square root of the good-branch probability. This preserves the coherence between items, so the output is a coherent superposition with the target amplitudes, which a classical sampler could not give.

Step by step

1. Start with a procedure that prepares the source state, a superposition of items with source amplitudes.
2. Compute, in an auxiliary register, the ratio of the target amplitude to the source amplitude for each item, normalized by an upper bound on the ratio.
3. Rotate an ancilla qubit so that its good component has amplitude equal to that normalized ratio.
4. Define the good subspace as the states where the ancilla is good, and build the corresponding amplitude amplification operator from the source preparation and the rotation.
5. Apply amplitude amplification for about the inverse square root of the good-branch probability rounds.
6. Uncompute the auxiliary register and the ancilla if possible, leaving the main register in the target superposition.

A worked example

Take two items, A and B. The source state gives A probability 0.9 and B probability 0.1. The target gives A probability 0.5 and B probability 0.5. The ratio of target to source probabilities is 0.556 for A and 5 for B, so the maximum ratio is 5. Rescale by 5, so the keep probabilities are 0.111 for A and 1 for B.

The overall good-branch probability is 0.9 times 0.111 plus 0.1 times 1, which is 0.2. Classical rejection sampling would need about 5 draws on average per accepted sample. Amplitude amplification needs about the square root of 5, roughly 2, rounds to produce the target superposition with high probability.

Complexity and resources

What hardware it needs

• Fault-tolerant hardware for amplitude amplification with deep circuits.
• Reversible arithmetic to compute amplitude ratios.
• Efficient preparation of the source distribution state.

Applications

• The conditioning step in HHL, where amplitudes are rescaled by the inverse of eigenvalues.
• Faster quantum Metropolis sampling and preparation of thermal states.
• Inference in Bayesian networks, where evidence must be conditioned on, with a quadratic speedup over classical rejection sampling.
• Preparing states for amplitude estimation and Monte Carlo, such as loading distributions.

Limitations and caveats

• The speedup is quadratic, which is modest and hard to realize in practice.
• The ratio between target and source can be huge when the distributions differ strongly, so the cost is high.
• It requires coherent access to the distributions and arithmetic circuits.

Common misconceptions

• Quantum rejection sampling does not produce independent classical samples faster in general. It prepares a quantum state.
• It does not give an exponential speedup over classical sampling.
• It is not the same as quantum Metropolis sampling, though it can be used inside it.

How it compares

• Classical rejection sampling needs about the full ratio of repeated trials.
• Markov chain Monte Carlo avoids rejection but needs time to mix.
• Amplitude amplification is the general tool of which quantum rejection sampling is an application.

Real-world impact

Used as a subroutine in quantum Gibbs sampling algorithms and quantum simulation, particularly for preparing thermal states of quantum systems.

Why it matters

Quantum rejection sampling is an example of how classical statistical techniques translate to the quantum setting, and it clarifies the core of other famous algorithms, including HHL. Knowing it helps in recognizing patterns across quantum algorithm design.

It also provides a rigorous tool for Bayesian inference and sampling tasks in quantum machine learning, with known optimal cost.

Frequently asked questions

Keep learning

• Related algorithm: Quantum Amplitude Amplification
• Related algorithm: HHL Algorithm
• Related algorithm: Quantum Metropolis Algorithm
• Related algorithm: Quantum Gibbs Sampling

This page is written for educational purposes. Complexity statements describe the best known results at the time of review (September 30, 2026), and research in this area moves quickly, so check recent papers before relying on a specific bound.

← Back to Algorithms Database