Modifications of Quantum Computation and Adaptive Queries to PP

1. 문제 정의 및 배경

• 배경: 양자 복잡도 클래스 (BQP, QMA 등) 와 고전적 복잡도 클래스 (P, NP, PP 등) 간의 관계는 계산 복잡도 이론의 핵심 질문입니다. Aaronson 은 2004 년 PostBQP (특정 측정 결과가 발생할 조건부 확률로 계산하는 모델) 를 도입하여 PostBQP = PP임을 증명했습니다. 이는 PP 가 교집합에 대해 닫혀 있음을 보여주는 간결한 증명을 제공했습니다.
• 연구 동기: BQP 에 다양한 "형이상학적" (물리적으로 실현 불가능하지만 계산 이론적 관점에서 정의된) 능력을 부여했을 때 계산 능력이 어떻게 변하는지, 그리고 이 모델들이 PP 와 PSPACE 사이의 공간에서 어떤 위치를 차지하는지 규명하는 것입니다. 특히, 중간 측정 (intermediate measurements) 이나 적응형 (adaptive) 쿼리가 계산 능력에 미치는 영향을 분석하고자 했습니다.

2. 제안된 모델 (Methodology)

저자들은 BQP 에 두 가지 새로운 능력을 부여하여 두 가지 새로운 복잡도 클래스를 정의했습니다.

2.1 CorrBQP (Correlated Measurements)

• 정의: 여러 레지스터에 걸쳐 상관된 측정 (Correlated Measurements) 을 수행할 수 있는 모델입니다.
• 작동 원리:
  1. 여러 레지스터를 '리더 (Leader)'와 '팔로워 (Follower)'로 나눕니다.
  2. 리더 레지스터의 측정 결과에 따라 팔로워 레지스터의 상태가 결정되도록 조건부 확률을 조정합니다.
  3. 서로 다른 값을 갖는 상태의 확률 진폭을 제거하고, 리더 레지스터의 확률 분포를 따르도록 가중치를 재분배한 후 측정을 수행합니다.
• 특징: 이는 단순히 포스트셀렉션을 시뮬레이션하는 것보다 강력하며, 상태 복제 (Cloning) 나 비붕괴 측정 (Non-collapsing measurements) 을 시뮬레이션할 수 있습니다.

2.2 MajBQP 및 AdMajBQP (Quantum Majority)

• 정의: 양자 다수결 게이트 (Quantum Majority Gate) 를 추가한 모델입니다.
• 작동 원리: 단일 큐비트 상태 $|\psi\rangle = \alpha|0\rangle + \beta|1\rangle$ 에 대해, $|\alpha|^2 \ge |\beta|^2$ 이면 $|0\rangle$ 로, 그렇지 않으면 $|1\rangle$ 로 붕괴시킵니다. 이는 가장 가능성이 높은 측정 결과를 선택하는 것과 동일합니다.
• 변형:
  • MajBQP: 중간 측정이 불가능한 모델.
  • AdMajBQP: 중간 측정이 가능한 적응형 모델.

3. 주요 결과 (Key Results)

3.1 복잡도 클래스의 정확한 특성화 (Exact Characterization)

논문의 가장 중요한 결과는 제안된 모델들이 PP 와 관련된 특정 오라클 클래스와 정확히 일치한다는 것입니다.

• 주요 정리 (Result 1):
  • CorrBQP = AdMajBQP = BPP$^{PP}$
  • MajBQP = PPP
  • 또한, 기존에 연구된 다른 모델들인 CBQP (상태 복제 가능), AdPostBQP (적응형 포스트셀렉션), RwBQP (측정 후 상태 되돌리기) 들도 모두 BPP$^{PP}$ 와 동일함을 증명했습니다.
  • 의미: 이러한 모델들의 계산 능력은 PostBQP (PP) 보다 약간 강력하지만, PSPACE 보다는 약합니다. 특히 중간 측정 (Adaptive) 이 가능할 때와 불가능할 때의 차이가 BPP$^{PP}$ 와 PPP 사이의 격차로 나타납니다.

3.2 자기-로우 (Self-Low) 속성과 계수 계층 (Counting Hierarchy)

• 고전적 쿼리 vs 양자적 쿼리:
  • CorrBQP 와 MajBQP 는 고전적 쿼리 (Classical queries) 에 대해 자기-로우 (Self-low) 성질을 가집니다. 즉, $CorrBQP^{CorrBQP} = CorrBQP$가 성립합니다. (이는 PostBQP 와는 다른 중요한 차이점입니다.)
  • 반면, 양자적 쿼리 (Quantum queries, 중첩 상태에서의 쿼리) 에 대해 자기-로우 성질이 성립한다면, 계수 계층 (Counting Hierarchy, CH) 이 붕괴됩니다.
  • Result 2: 만약 $CorrBQP^{CorrBQP} \subseteq CorrBQP$ (양자 쿼리 기준) 라면, $CH = BPP^{PP}$가 되어 CH 가 붕괴됩니다. 이는 CH 가 붕괴되지 않는 한, 고전적 쿼리에는 자기-로우 성질이 있지만 양자적 쿼리에는 그렇지 않은 클래스가 존재함을 시사합니다.

3.3 쿼리 복잡도 및 새로운 하한 (Query Complexity & Lower Bounds)

• Rational Tree Degree (trdeg): 적응형 포스트셀렉션 (AdPostBQP) 의 쿼리 복잡도를 하한하는 새로운 척도인 Rational Tree Degree를 정의했습니다.
  • Result 3: AdPostBQP 의 쿼리 복잡도는 $trdeg$에 의해 하한됩니다. 오류가 0 인 경우$rdeg$ (기존 유리수 차수) 와 같지만, 상수 오류의 경우 분리될 수 있음을 보였습니다.
• AdPDQP 의 적응성:
  • AdPDQP (적응형 비붕괴 측정) 에 대해 어드버사리 (Adversary) 방법을 확장했습니다.
  • Result 5: 적응성을 추가하더라도 비구조화된 검색 (Unstructured Search) 은 $\Omega(n^{1/4})$, 패리티 (Parity) 는 $\Omega(n^{1/2})$ 쿼리가 필요합니다.
  • 의외의 발견: PostBQP 에 적응성을 추가하면 패리티를 효율적으로 풀 수 있지만, PDQP 에 적응성을 추가해도 검색이나 패리티 문제 해결에 큰 이득이 없습니다. 이는 AdPDQP 가 PDQP 와 동등하거나 매우 유사한 힘을 가진다는 것을 의미합니다.

3.4 오라클 분리 (Oracle Separation)

• Result 4: 고전적 쿼리만 허용된 PostBQP$^{classical}$ 과 일반 BQP(양자 쿼리) 는 오라클에 따라 분리될 수 있음을 보였습니다. 즉, 모든 오라클 $O$에 대해 $PPO \subseteq PostBQP^{classical}_O$가 성립하지 않습니다. 이는 PP 가 고전적 쿼리만 가능함에도 불구하고, 양자 쿼리를 가진 BQP 와는 다른 힘을 가질 수 있음을 보여줍니다.

4. 의의 및 결론 (Significance)

1. PP 와 PSPACE 사이의 구조 규명: 이 연구는 PP 와 PSPACE 사이의 복잡한 공간에 있는 여러 양자 계산 모델 (CorrBQP, MajBQP 등) 을 BPP$^{PP}$ 와 PPP로 정확히 매핑함으로써, 이 영역의 구조를 명확히 했습니다.
2. 중간 측정의 중요성: 중간 측정 (Adaptive) 이 가능할 때와 불가능할 때의 계산 능력 차이 (BPP$^{PP}$ vs PPP) 를 명확히 보여주었습니다. 이는 양자 알고리즘 설계에서 측정 시점의 중요성을 강조합니다.
3. 계수 계층 (CH) 붕괴 조건: 양자적 쿼리 하에서의 자기-로우 성질이 계수 계층의 붕괴와 직결됨을 보임으로써, 복잡도 이론의 근본적인 문제 (CH 붕괴 여부) 와 양자 계산 모델의 관계를 연결했습니다.
4. 새로운 하한 기법: Rational Tree Degree 를 도입하여 적응형 양자 알고리즘의 쿼리 복잡도를 분석하는 새로운 도구를 제공했습니다.
5. 형이상학적 모델의 통합: 상태 복제, 비붕괴 측정, 적응형 포스트셀렉션 등 서로 다른 "형이상학적" 능력들이 사실은 동일한 계산 능력 (BPP$^{PP}$) 을 가진다는 것을 증명하여, 이 분야 연구의 통합된 관점을 제시했습니다.

요약하자면, 이 논문은 양자 계산에 다양한 비물리적 능력을 부여했을 때 발생하는 계산 능력의 변화를 정량화하고, 이를 통해 PP 와 PSPACE 사이의 복잡도 지형을 더 깊이 이해하는 데 기여했습니다. 특히 적응성 (Adaptivity) 과 측정 방식이 복잡도 클래스의 경계를 어떻게 결정하는지에 대한 통찰을 제공합니다.