양자 기반 희귀 사건 탐지 및 샘플링

Quantum enhanced rare event discovery and sampling

금융 시장의 급락, 사회 기반 시설의 연쇄적인 고장, 그리고 인공 지능 시스템의 심각한 오류는 매우 낮은 확률로 발생하는 사건에 의해 자주 유발됩니다. 따라서 특정 임계값 이하의 확률을 갖는 사건들을 효율적으로 탐지하고 샘플링하는 것은 매우 중요한 과제입니다. 그러나 기존의 고전적 또는 양자적 방법으로는 이러한 작업이 매우 어렵습니다. 희귀한 사건들은 충분한 데이터 샘플을 수집하기 위해 막대한 샘플링 비용이 필요하며, 또한 희귀 사건은 사전에 알려지지 않으므로 표준적인 기술을 사용하여 증폭할 수 없습니다. 본 연구에서는 어떤 사건이 희귀한지 미리 알지 않고도 희귀 사건 탐지 및 샘플링을 위한 양자 알고리즘을 소개합니다. 이 알고리즘은 희귀성 임계값에 대한 최적의 양자 스케일링을 달성하며, 꼬리가 유한한 총 질량을 갖는 시스템에서는 2차 속도 향상을 얻을 수 있음을 보여줍니다. 또한, 이는 정지 확률 과정에서 견고한 다항식 수준의 속도 향상을 제공하며, 그 지수는 엔트로피율 구조에 의해 결정됩니다.

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.