arXiv:1707.09553 · Physical Review X

Extreme Quantum Memory Advantage for Rare-Event Sampling

Cina Aghamohammadi, Samuel P. Loomis, John R. Mahoney, James P. Crutchfield

Published Feb 13, 2018• 31 citations

Abstract

A new theoretical analysis shows how to greatly improve upon the computational requirements of modeling extreme rare events in complex systems by implementing a quantum algorithm for rare-event sampling.

DOI: 10.1103/physrevx.8.011025

Related papers

Gaining a Quantum Advantage Sooner than Expected

Marric Stephens

For an important quantum many-body problem, a hybrid quantum-classical algorithm could outperform purely classical approaches using surprisingly few quantum resources.

PhysicsDec 10, 20200 citations

Spatiotemporal quantum advantages for rare-event sampling

Akshat Gupta, Jianjun Chen, Chengran Yang +4 more

In a world fraught with uncertainty, it behooves us to consider the most disastrous possible outcomes, in order that we can best mitigate against them. Often these are extreme risk events -- of high consequence, but low probability. Yet, the rarity of such events limits our ability to study them; there is a paucity of past occurrences to draw upon, and sampling such rare events from models is typically costly in time. Here, we introduce an approach for rare-event sampling based on quantum stochastic models. This integrates the memory advantages of quantum stochastic modelling -- and its associated efficient means of preparing quantum sample states -- with the `speed-ups' of quantum amplitude amplification, to yield simultaneous reductions in spatial and temporal computational complexity compared to classical Monte Carlo-based approaches.

quant-pharXiv:2610.03026Physical Review LettersOct 5, 20260 citations

Quantum enhanced rare event discovery and sampling

Naixu Guo, Po-Wei Huang, Qisheng Wang +4 more

Financial crashes, cascading failures in infrastructure, and critical errors in AI systems are frequently triggered by events that occur with extremely small probability. Efficiently discovering and sampling events with probability below a threshold is therefore of critical interest. Yet this task is highly non-trivial using existing classical or quantum methods. Being rare, such events require an immense sampling overhead to collect sufficient data samples. Moreover, because the rare events are not known in advance, they cannot be flagged for amplification using standard techniques. Here, we introduce a quantum algorithm for rare-event discovery and sampling without first learning which events are rare. The algorithm achieves the optimal quantum scaling with the rarity threshold. We further demonstrate that this can achieve a quadratic speedup for heavy-tailed systems whose tail has nonvanishing total mass, and translates into a robust polynomial speedup for stationary stochastic processes, with the exponent determined by its entropy-rate structure.

quant-pharXiv:2606.06316Jun 5, 20260 citations

Quantum energetic advantage before computational advantage in Boson Sampling

Anonymous

Physical Review LettersSep 14, 20260 citations

Quantum Memory Breaks Performance Barrier

Ryan Wilkinson

Quantum Memory Breaks Performance BarrierA new approach stores and retrieves quantum states with record reliability, paving the way for improved quantum information processing.

PhysicsOct 21, 20250 citations

Investigating Quantum Speedup for Track Reconstruction: Classical and Quantum Computational Complexity Analysis

Duarte Magano, Akshat Kumar, Mārtiņš Kālis +10 more

To investigate the fundamental nature of matter and its interactions, particles are accelerated to very high energies and collided inside detectors, producing a multitude of other particles that are scattered in all directions. As the charged particles traverse the detector, they leave signals of their passage. The problem of track reconstruction is to recover the original trajectories from these signals. This represents a very challenging data analysis problem, which will become even more demanding as the luminosity of future accelerators keeps increasing, leading to collision events with a more complex structure. Therefore, there is a pressing need to develop more efficient methods, capable of sieving through the vast amount of data produced by these machines, in order to find the extremely rare events that may contain the clues for new Physics. In light of these challenges, approaches to track reconstruction based on quantum computation have recently been put forward. In this work, we study track reconstruction from a computational complexity perspective. Namely, we analyse a standard algorithm for tracking, the Combinatorial Track Finder, in the asymptotic limit of infinitely many recorded particles. First, we show that it is possible to improve the classical algorithm in this regime. Then, we show how to use quantum search routines to reach a lower computational complexity. And - although the found quantum speed-up is modest and of limited practical advantage in finite scenarios - to the best of our knowledge this constitutes the first theoretical proof of a quantum advantage for a state-of-the-art track reconstruction method, which we hope can further inspire classical and quantum improvements to High-Energy Physics computational challenges.

Apr 23, 20210 citations