Promises should be taken seriously: On relativization with promise problems

기술 요약: 약속 문제는 진지하게 다뤄져야 한다: 약속 문제(promise problems)에 대한 상대화에 관하여

문제 정의
본 논문은 표준적인 언어(language)가 아닌 *약속 문제(promise problems)*에 대한 접근을 통해 상대화될 때 계산 복잡도 클래스의 동작을 조사한다. 표준적인 상대화에서 오라클은 확정적인 답변(0 또는 1)을 제공한다. 반면, 약속 문제 $\Pi = (\Pi_{yes}, \Pi_{no})$는 약속 집합 $\Pi_{yes} \cup \Pi_{no}$ 내의 입력만을 제약하며, 이 집합 외부의 입력(off-promise)은 제약되지 않는다.

중심적인 어려움은 표준적인 오라클 접근 정의가 전사 함수(total function)를 가정한다는 점에서 발생한다. 약속 문제의 경우, 기계가 off-promise 입력을 쿼리할 때 어떻게 행동해야 하는지를 정의해야 한다. 저자들은 이러한 접근에 대한 두 가지 구별되는 의미론(semantics)을 분석한다:

1. 강건한 쿼리(Robust Queries): 기계는 약속의 모든 완성본(completion) $A$에 대해 올바르게 작동해야 한다(즉, 모든 완성본에 대해 성공해야 함).
2. 느슨한 쿼리(Loose Queries): 기계의 내부 선택(예: 무작위 문자열 또는 증거)은 완성본이 선택되기 전에 고정된다. 기계는 동일한 내부 선택을 사용하여 모든 완성본에 대해 성공해야 한다.

본 논문은 언어에 대해 알려진 상대화 결과(예: $BPP \subseteq P/poly$, Toda의 정리)가 이 의미론 하에서 약속 문제로 전이되는지, 그리고 선택된 의미론이 결과적인 복잡도 계층 구조에 어떤 영향을 미치는지 묻는다.

방법론
저자들은 오라클 구성과 산술화(arithmetization) 방법을 결합하여 다음과 같은 기법을 사용한다:

• 오라클 구성: 언어 기반 결과와 약속 기반 결과를 분리하기 위해, 저자들은 PSPACE-완전 언어와 PSPACE에 대한 코헨-제네릭(Cohen-generic) 집합을 결합하여 특정 오라클 $O$를 구성한다. 이 과정에서 제네릭 집합 안에 사이몬 문제(Simon's problem)의 독립적인 인스턴스들을 인코딩한다.
• 직접 곱 경계(Direct-Product Bounds): 저자들은 직접 곱 경계(Dru12)를 활용하여, 어드바이스(advice)를 가진 기계가 오라클에 인코딩된 사이몬 문제의 모든 독립적인 인스턴스를 동시에 해결할 수 없음을 논증함으로써, 상대화된 세계에서 $PromiseBQP$와$PromiseP/poly$를 분리한다.
• 느슨한 접근 및 산술화: $QCPH$의 상한을 개선하기 위해, 저자들은 Toda의 정리를 변형한다. 저자들은 "느슨한 접근 불명확 계층(loose-access unambiguous hierarchy)"을 도입하고, 무작위 시드(random seed)를 단일 쿼리로 압축하기 위해 정확한 산술화(acceptance probability를 GapP 함수로 표현)를 사용한다. 이를 통해 $PromiseBQP$가$BQP$ 내에서 임의의 완성본으로 대체될 수 없는 문제를 우회한다.
• 무작위 임계값을 통한 자기 낮음성(Self-Lowness): $PromiseBQP$의 자기 낮음성 결과를 입증하기 위해, 저자들은 off-promise 쿼리의 수락 확률이 $1/2$에 임의로 가까워질 수 있는 문제를 다룬다. 저자들은 off-promise 구간을 하위 구간으로 나누고 각 쿼리에 무작위 임계값을 할당하여, 시뮬레이션 오차가 다항식 크기로 작게 유지되도록 보장한다.
• 사후 선택(Postselection) 변형: 카운팅 결과를 처리하기 위해, 저자들은 사후 선택 회로가 입력 자체가 아닌 입력 길이에만 의존하는 $PostBQP$의 변형인$PromisePostBQP^*$를 도입한다. 이를 통해$PromiseYQP^*$와$PP$ 사이의 간극을 메운다.

주요 기여 및 결과

1. 언어와 약속 설정의 분리:
   저자들은 다음을 만족하는 오라클 $O$를 구성한다:
   $$P^O = BPP^O = BQP^O = AWPP^O$$
   그러나,
   $$PromiseBQP^O \not\subseteq PromiseP^O/poly$$
   이는 언어에 대해 성립하는 결과(예: $BPP \subseteq P/poly$)가 반드시 약속 문제로 전이되지는 않음을 보여준다. 특히, 이는 $BPP = BQP$이지만 $PromiseBQP \neq PromiseBPP$인 오라클이 존재하는지에 대한 니산(Nisan)의 질문에 답한다. 이는 약속 문제의 "완성(completion)"이 대응하는 언어 클래스에 속한다고 가정할 수 없음을 강조한다.

2. $QCPH$의 개선된 상한:
   느슨한 오라클 접근을 사용하여, 저자들은 양자-고전 다항 계층($QCPH$)의 상한을 개선한다. 저자들은 다음을 증명한다:
   $$QCPH \subseteq BP \cdot PP \subseteq PromiseBPP^{PP}$$
   이는 클래스가 도입된 이후 변화가 없었던 기존의 최선 상한인 $PP^{PP}$를 개선한 것이다. 이 증명은 Toda의 정리를 약속 문제에 직접 적용할 수 있도록 적응시키며, 느슨한 접근 불명확 계층과 GapP 산술화를 활용한다. 결과적으로, $PP^{PromiseBQP} = PP$임을 보인다.

3. $PromiseBQP$의 자기 낮음성:
   저자들은 $PromiseBQP$가 양자 어드바이스를 가진 경우에도 강건한 쿼리 하에서 자기 낮음성을 가짐을 입증한다:
   $$PromiseBQP^{PromiseBQP} = PromiseBQP$$
   $$PromiseBQP^{PromiseBQP/qpoly} = PromiseBQP/qpoly$$
   이는 쿼리 시뮬레이션에 사용되는 임계값을 무작위화함으로써, off-promise 확률이 $1/2$에 매우 가까울 때도 시뮬레이션 오차가 무시할 수 있는 수준임을 보장함으로써 달성된다.

4. 카운팅 계층 붕괴에 대한 장애물:
   본 논문은 $GapP \subseteq FP^{PromiseAWPP}$임을 보여준다. 결과적으로, 만약 $PromiseAWPP \subseteq PromiseBQP/qpoly$라면, 카운팅 계층($CH$)이 $YQP^*$로 붕괴될 것이다. 이는 $PromiseAWPP$와$PromiseBQP$가 서로 다를 가능성이 높음을 시사한다.
   또한, $AWPP$가 언어 설정에서 $PP$를 위해 낮다면($PP^{AWPP} = PP$), 저자들은 약속 클래스에 대한 직접적인 유사 모델이 카운팅 계층의 붕괴를 초래함을 보여준다. 이를 해결하기 위해 저자들은 $PromisePostBQP^*$를 도입하고 다음을 증명한다:
   $$PP^{PromisePostBQP^*} = PP \implies PP^{PromiseYQP^*} = PP$$

의의
본 논문은 의미론적 복잡도 클래스(수용 확률에 의해 정의되는 클래스)의 경우, off-promise 쿼리에 대한 처리가 필수적이며 무시될 수 없다고 주장한다. 연구 결과는 다음과 점을 보여준다:

• 언어에 대한 상대화된 결과가 약속 문제로 자동 전이되지 않는다.
• "강건한" 쿼리와 "느슨한" 쿼의 의미론적 선택이 결과적인 복잡도 클래스의 위력을 크게 변화시킨다.
• 산술화나 자기 낮음성 증명과 같은 표준 기법을 약속 문제에 적용할 때는, 카운팅 계층의 붕괴나 잘못된 결론을 피하기 위해 임계값 무작위화나 사후 선택 제한과 같은 세심한 적응이 필요하다.

이 연구는 약속된 세계에서의 약속 문제를 분석하기 위한 엄밀한 프레임워크를 제공하며, 언어 기반의 복잡도 결과를 약속 설정으로 확장할 때의 한계를 명확히 한다.