양자 강화 희귀 사건 발견 및 샘플링

금융 붕괴, 인프라의 연쇄적 실패, 그리고 AI 시스템의 치명적인 오류는 매우 낮은 확률로 발생하는 사건들에 의해 빈번하게 촉발됩니다. 따라서 임계값(threshold) 미만의 확률을 가진 사건들을 효율적으로 발견하고 샘플링하는 것은 매우 중요한 관심사입니다. 하지만 이 작업은 기존의 고전적(classical) 또는 양자(quantum) 방법을 사용하더라도 매우 까다롭습니다. 이러한 사건들은 희귀하기 때문에, 충분한 데이터 샘플을 수집하기 위해서는 엄청난 샘플링 오버헤드(sampling overhead)가 필요합니다. 더욱이, 희귀 사건은 사전에 알려져 있지 않기 때문에 표준 기술을 사용하여 증폭(amplification)을 위해 표시(flag)할 수 없습니다. 본 논문에서는 어떤 사건이 희귀한지 먼저 학습하지 않고도 희귀 사건을 발견하고 샘플링할 수 있는 양자 알고리즘(quantum algorithm)을 소개합니다. 이 알고리즘은 희귀성 임계값(rarity threshold)에 대해 최적의 양자 스케일링(quantum scaling)을 달성합니다. 나아가 우리는 이것이 꼬리 부분이 사라지지 않는 총 질량(nonvanishing total mass)을 가진 헤비 테일(heavy-tailed) 시스템에 대해 이차적 가속(quadratic speedup)을 달성할 수 있음을 입증하며, 이는 엔트로피율(entropy-rate) 구조에 의해 결정되는 지수를 가진 정적 확률 과정(stationary stochastic processes)에 대해 강력한 다항식 가속(polynomial speedup)으로 전환됨을 보여줍니다.