Quantum advantage with noisy linear optics = 잡음이 있는 선형 광학에서의 양자 우위

국문 초록 (Abstract)

보손 샘플링은 선형 광학 플랫폼에서 정의되는 대표적인 양자 샘플링 문제로, 실험적 구현이 비교적 용이하면서도 계산 복잡성 이론에 기반한 고전적 계산의 어려움(classical hardness)이 확립되어 있어, 양자 계산 우위를 실험적으로 입증하기 위한 가장 유망한 비범용 양자 컴퓨팅 모델 중 하나로 평가된다. 그러나 실제 실험적 구현 과정에서 불가피하게 발생하는 다양한 잡음은 보손 샘플링의 계산 복잡성을 크게 약화시켜, 양자 계산 우위의 실현을 어렵게 만드는 핵심 장애 요소로 남아 있다. 본 학위 논문에서는 이러한 문제를 해결하기 위한 두 가지 상보적 접근을 제시한다. 첫째, 잡음 누적을 억제할 수 있는 얕은 깊이(shallow-depth) 선형광학 회로 아키텍처에서의 보손 샘플링이 여전히 고전적으로 시뮬레이션하기 어려울 수 있음을 해석적 분석과 수치적 증거를 통해 제시하였다. 둘째, 실제 실험에서 지배적으로 나타나는 잡음 요인 중 하나인 광자 사이의 부분 비식별성(partial distinguishability)이 존재하더라도 보손 샘플링의 고전적 어려움이 보존될 수 있음을 증명하고, 이러한 계산적 어려움이 유지되는 잡음 임계값을 명확히 도출하였다. 본 학위 논문의 결과는 잡음이 존재하는 현실적 선형광학 시스템에서도 보손 샘플링 기반 양자 계산 우위가 유지될 수 있음을 이론적으로 뒷받침하는 중요한 진전이며, 향후 근시일 내의 실험적 양자 우위 시연을 향한 기반을 공고히 할 것으로 기대된다.

다국어 초록 (Multilingual Abstract)

Boson sampling, a sampling problem in linear optical systems, is among the most promising candidates for the experimental demonstration of quantum computational advantage, owing to its experimental feasibility and strong complexity-theoretical evidence of hardness. However, noise inherent to physical implementations remains a significant challenge, as it can substantially reduce the computational complexity of boson sampling. This dissertation presents two complementary approaches to address this challenge. First, we investigate the classical hardness of boson sampling implemented with shallow-depth linear-optical circuits, where the noise rate can be substantially reduced, and provide both analytical and numerical evidence for classical hardness. Second, we establish classical hardness results for boson sampling in the presence of experimental imperfections, focusing in particular on partial distinguishability noise, and identify the noise threshold that preserves the classical hardness of ideal boson sampling. We believe that the analyses developed in this dissertation serve as a crucial step toward stronger and more robust hardness results applicable to noisy linear optical systems, and ultimately facilitating the demonstration of quantum computational advantage with boson sampling experiments in the near future.

목차 (Table of Contents)

• Abstract
• 1. Introduction 1
• 2. Preliminaries 5
• 3. Analysis on shallow-depth boson sampling I: Exploring the classical intractability of shallow-depth boson sampling 17
• 4. Analysis on shallow-depth boson sampling II:Computational complexity and average-case hardness of shallow-depth boson sampling 69
• 5. Analysis on noisy boson sampling 153
• 6. Conclusion 201