# PRL paper claims quadratic speedup for rare-event sampling

Published 2026-11-21 · Quantum.world Team · Quantum.world

> A paper in Physical Review Letters proposes combining quantum stochastic models with amplitude amplification to sample rare trajectories with quadratic scaling. Its demonstrations use toy models, including a modeled process where the authors compare amplified quantum samples with classical Monte Carlo sampling.

## Quadratic scaling on paper

A quantum-model method could reduce the sampling cost of rare trajectories from scaling as 1/p to 1/√p, while also reducing memory requirements, a paper published in *Physical Review Letters* reports. The work combines quantum stochastic models with quantum amplitude amplification, a technique used to increase the weight of selected outcomes in a quantum state.

Source [journals.aps.org](https://journals.aps.org/prl/pdf/10.1103/7zh3-zvnd)

The framework concerns discrete-time processes that produce sequences of events. It constructs a quantum sample state—a superposition of possible trajectories—and applies amplification to make trajectories containing a specified rare event more likely to be measured.

## How the method is meant to work

For classical Monte Carlo sampling, the paper says, a target trajectory set with probability p requires generating O(1/p) trajectories to obtain a target number of examples. The proposed method instead needs O(1/√p) amplification iterations, which the authors describe as a quadratic reduction in temporal complexity.

Efficient preparation of the state is part of the proposal: the quantum stochastic model’s circuit depth grows linearly with the number of time steps, rather than exponentially as in the paper’s comparison with a naive, unstructured construction. The authors also point to reduced memory dimension in quantum models as a spatial advantage.

## Toy-process comparison

One demonstration uses a five-step toy process called the Nemo process, with a target event consisting of an error in the final symbol. The paper sets two model error probabilities at about 10-6 and uses 1,024 Grover iterations to amplify the target trajectories.

In the paper’s comparison, 10,000 quantum-circuit shots after amplification yielded 8,796 target trajectories. A classical Monte Carlo run given an equivalent number of model-unitary calls—20,480,000 shots—produced 13 such trajectories, and the paper reports a poorer reconstruction of the symbols preceding the rare event. These are results from the study’s toy-model analysis, not a reported run of the method on a quantum processor.

## A second modeled example

The paper also applies the approach to a toy renewal process, a type of model relevant to queueing theory and reliability analysis. For this example, it gives the quantum model a memory dimension of 2, compared with 25 states for the corresponding classical model, and considers a rare event with probability around 10-15.

The authors say that this example has a larger temporal-complexity advantage and covers more time steps. They distinguish their method from earlier work on reweighted classical models: this approach combines quantum stochastic modeling with amplitude amplification and considers memory dimension alongside sampling cost.

## Sources

1. Original source · Paper [American Physical Society · page 1](https://journals.aps.org/prl/pdf/10.1103/7zh3-zvnd) journals.aps.org

Other pages read

2. [American Physical Society · page 2](https://journals.aps.org/prl/abstract/10.1103/7zh3-zvnd) journals.aps.org

## Related stories

- [Quantum channel paper sets new average-case testing bounds](https://quantum.world/news/quantum-channel-average-case-testing-bounds)
- [Preprint expects no exponential DQI speedup with local decoders](https://quantum.world/news/dqi-local-decoders-quantum-advantage-preprint)
- [Harvard researchers say quantum sensing can surpass Heisenberg limit](https://quantum.world/news/harvard-researchers-quantum-sensing-beyond-heisenberg-limit)
- [Quantum chemistry study tests two UCJ initialization methods](https://quantum.world/news/ucj-quantum-chemistry-initialization-methods)
- [Physical Review A publishes quantum Boltzmann energy method](https://quantum.world/news/physical-review-a-quantum-boltzmann-ground-state-energy)

## Explore

[More articles](https://quantum.world/news)

---

Canonical: https://quantum.world/news/prl-quantum-rare-event-sampling-quadratic-speedup
