[고병선 학생, 오창훈 교수(KAIST), 정현석 교수] 부분 구별성 잡음이 있는 보손 샘플링에서의 양자 우위(PRX Quantum 논문 게재)
부분 구별성 잡음이 있는 보손 샘플링에서의 양자 우위
보손 샘플링은 선형 광학 시스템에서 정의되는 샘플링 문제로서, 실험적 구현 용이성과 계산 복잡성 이론에 근거한 고전적-계산-어려움(classical intractability)이 입증되어 있다는 점에서 양자 계산 우위를 실험적으로 시연하기 위한 가장 유망한 후보 중 하나이다. 그러나 실험적 잡음의 존재는 보손 샘플링을 통한 양자 계산 우위의 실현을 어렵게 만든다. 이러한 물리적 잡음이 불가피하다는 점을 고려할 때, 보손 샘플링이 고전적-계산-어려움을 유지하는 잡음률의 경계를 정밀하게 규명하는 것은 근시일 내 양자 광자 장치를 활용한 양자 계산 우위 달성에 있어 핵심적이다. 본 연구에서는 보손 샘플링이 고전적 계산 불가능성을 유지하는 부분 구별성 잡음(partial distinguishability noise)의 수준을 규명하였다. 그 결과, 입력된 광자 개수에 대해 로그-개수의 광자가 서로 구별 가능한 경우에도, 해당 보손 샘플링은 이상적인 보손 샘플링과 동등한 계산 복잡성을 유지함을 보였다. 이와 같은 결과는 잡음이 존재하는 보손 샘플링의 고전적 계산 불가능성에 대한 강력한 계산 복잡성 이론적 근거를 제공하며, 가까운 미래에 잡음이 존재하는 보손 샘플링 실험을 통한 양자 계산 우위의 실현을 촉진할 것으로 기대된다.
Quantum Computational Advantage of Noisy Boson Sampling with Partially Distinguishable Photons
Boson sampling stands out as a promising approach toward experimental demonstration of quantum computational advantage. However, the presence of physical noise in near-term experiments hinders the realization of the quantum computational advantage with boson sampling. Since physical noise in near-term boson sampling devices is inevitable, precise characterization of the boundary of noise rates where the classical intractability of boson sampling is maintained is crucial for quantum computational advantage using near-term devices. In this work, we identify the level of partial distinguishability noise that upholds the classical intractability of boson sampling. We find that boson sampling with on average logarithmic number of distinguishable photons maintains the equivalent complexity to the ideal boson sampling case. By providing strong complexity theoretical evidence for the classical intractability of noisy boson sampling, we expect that our findings will ultimately facilitate the demonstration of quantum computational advantage with noisy boson sampling experiments in the near future.
B. Go, C. Oh, and H. Jeong, "Quantum Computational Advantage of Noisy Boson Sampling with Partially Distinguishable Photons,” PRX Quantum 6, 030362 (2025). https://journals.aps.org/prxquantum/abstract/10.1103/rflv-gc66
B. Go, C. Oh, and H. Jeong, "Quantum Computational Advantage of Noisy Boson Sampling with Partially Distinguishable Photons,” PRX Quantum 6, 030362 (2025). https://journals.aps.org/prxquantum/abstract/10.1103/rflv-gc66