Quantum enhanced rare event discovery and sampling
Authors: Naixu Guo, Po-Wei Huang, Qisheng Wang, Jayne Thompson, Patrick Rebentrost, Mile Gu, Chengran Yang
Organizations: Centre for Quantum Technologies, National University of Singapore, Singapore 117543, Singapore · Mathematical Institute, University of Oxford, Oxford OX2 6GG, United Kingdom · School of Computer Science, Shanghai Jiao Tong University, Shanghai 200240, China · School of Informatics, University of Edinburgh, Edinburgh EH8 9AB, United Kingdom · College of Computing and Data Science, Nanyang Technological University, Singapore 639798, Singapore · School of Computing, National University of Singapore, Singapore 117417, Singapore · Nanyang Quantum Hub, School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore 637371, Singapore
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.