The Signal
PRL paper claims quadratic speedup for rare-event sampling
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
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
- Original source · Paper American Physical Society · page 1 journals.aps.org
Other pages read
- American Physical Society · page 2 journals.aps.org
Related stories
- Quantum channel paper sets new average-case testing bounds
- Preprint expects no exponential DQI speedup with local decoders
- Harvard researchers say quantum sensing can surpass Heisenberg limit
- Quantum chemistry study tests two UCJ initialization methods
- Physical Review A publishes quantum Boltzmann energy method