Skip to content
Quantum.world

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.

PRL paper claims quadratic speedup for rare-event 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

  1. Original source · Paper American Physical Society · page 1 journals.aps.org

Other pages read

  1. American Physical Society · page 2 journals.aps.org

Related stories

Explore

More articles