기술 요약: 교환 가능한 로컬 해밀토니안 문제: BQP-하드성에 대한 상대화된 증거

1. 문제 정의 및 배경

교환 가능한 로컬 해밀토니안(Commuting Local Hamiltonian, CLH) 문제는 모든 로컬 항들이 서로 쌍별로 교환(pairwise commute)되는 로컬 해밀토니안의 바닥 상태 에너지가 임계값 $\alpha$ 미만인지 또는 $\beta$ 초과인지를 묻는 문제입니다. 일반적인 로컬 해밀토니안 문제는 QMA-완전(QMA-complete)이지만, 교환 가능한 변형의 복잡도는 양자 복잡도 이론에서 여전히 핵심적인 미해결 과제로 남아 있습니다.

이전 연구들은 특정 계열의 교환 가능한 해밀토니안(예: 2-local, 특정 3-local, 또는 특정 격자 위의 해밀토니안)에 대해 이 문제가 NP에 속함을 입증했습니다. 그러나 일반적인 CLH 문제가 QMA-완전일 가능성을 배제하는 공식적인 증거는 존재하지 않았습니다.

QIMA(Quantum Interactive Merlin-Arthur with Commuting units)라는 복잡도 클래스는 Bostanci와 Hwang에 의해 도입되었으며, 이는 국소 테스트 유닛들이 서로 교환 가능한 반사(reflections)인 양자 검증자의 능력을 포착합니다. CLH 문제는 QIMA를 위해 완전(complete)합니다. 따라서 CLH가 QMA-완전인지에 대한 질문은 QIMA = QMA인지 묻는 것과 같습니다.

본 논문은 상대화된 설정(relativized setting)에서 QIMA와 BQP(Bounded-error Quantum Polynomial time) 사이의 관계를 조사합니다. 구체적으로, BQP$^O \not\subseteq$ QIMA$^O$를 만족하는 클래식 오라클 $O$가 존재하는지 확인하고자 합니다. 긍정적인 결과는 일반적인 CLH 문제가 BQP-하드(BQP-hard)일 가능성, 즉 QMA-완전일 가능성에 대한 **상대화된 증거(relativized evidence)**를 제공할 것입니다.

2. 방법론 및 정의

2.1 오라클 모델 QIMA$^O$

저자들은 QIMA$^O$라고 불리는 상대화된 QIMA를 정의하며, 이는 모델이 QMA$^O$의 비자명한 제한임을 보장하기 위한 특정 제약 조건을 포함합니다:

• 검증자 구조: 입력 $x$에 대해, 검증자는 $O$에 대한 적응적 쿼리(adaptive queries)를 수행하는 클래식 전처리 과정을 거쳐 양자 증인(witness)에 작용하는 일련의 "유닛" $W_1^O, \dots, W_m^O$를 생성합니다.
• 교환성(Commutativity): 약속된 인스턴스들에 대해, 모든 유닛은 반드시 쌍별로 교환되어야 합니다: $[W_i^O, W_j^O] = 0$.
• 반사 요구사항(Reflection Requirement): 결정적으로, 적어도 하나의 양자 오라클 쿼리를 포함하는 유닛 $W_j^O$는 반드시 **정확한 반사(exact reflection)**여야 합니다 (즉, $(W_j^O)^\dagger = W_j^O$ 이고 $(W_j^O)^2 = I$). 오라클이 없는 유닛은 임의의 유니터리일 수 있습니다.
• 검증: 검증자는 각 유닛의 $+1$ 고유 공간(eigenspace)에 증인이 있는지 확인하기 위해 하다마르 테스트(Hadamard test)를 사용합니다.
• 신뢰할 수 있는 보조 큐비트 없음(No Trusted Ancilla): 검증자는 하다마르 테스트에 사용되는 신선한 제어 큐비트 외에는 신뢰할 수 있는 작업 공간을 갖지 않습니다.

저자들은 반사 요구사항이 필수적이라고 주장합니다. 그들은 임의의 교환 가능한 유닛(심지어 반사에 매우 가까운 유닛이라도)을 허용하거나 신뢰할 수 있는 보조 큐비트를 허용하도록 완화하면 모델이 QMA$^O$로 붕괴됨을 보여줍니다.

2.2 Forrelation 문제

구분은 Aaronson에 의해 정의된 Forrelation 문제에 기반합니다. 두 불리언 함수 $f, g: \{0,1\}^n \to \{-1, +1\}$에 대한 오라클 접근이 주어졌을 때, 다음 중 하나를 구별하는 작업입니다:

• Yes: $f$가 $g$의 푸리에 변환(Fourier transform)과 높은 상관관계를 가짐 ($\Phi(f,g) \ge \alpha$).
• No: 상관관계가 작음 ($|\Phi(f,g)| \le \beta$).

Forrelation은 상수 개의 양자 쿼리로 해결 가능한 BQP 알고리즘에 의해 풀립니다. 본 논문의 목표는 Forrelation에 대한 QIMA$^O$ 검증자가 지수적인 쿼리 수를 요구함을 증명하는 것입니다.

3. 주요 기여 및 결과

3.1 오라클 분리: BQP$^O \not\subseteq$ QIMA$^O$

주요 결과는 BQP$^O \not\subseteq$ QIMA$^O$를 만족하는 클래식 오라클 $O$를 구성하는 것입니다. 이는 Forrelation 문제에 대한 QIMA$^O$ 검증자의 지수적 쿼리 하한(exponential query lower bound)을 증명함으로써 달성됩니다.

정리 1.7 (비형식적): 모든 약속된 쌍 $(f, g)$에 대해 Forrelation을 결정하는 모든 QIMA$^O$ 검증자는 다음을 만족해야 합니다:
$$C(n) + T(n) \ge \beta 2^n - O(1)$$
여기서 $C(n)$은 클래식 전처리 쿼리 수이고 $T(n)$은 총 양자 오라클 쿼리 수입니다.

증명 개요:

1. 다항식 방법(Polynomial Method): 검증자의 수락 확률은 오라클의 진리표 항목들에 대한 다항식으로 표현됩니다.
2. 교환성과 반사: 오라클을 포함하는 유닛들이 정확한 반사이며 서로 교환되기 때문에, 이들의 결합 수락 연산자는 직교 투영(orthogonal projectors)의 곱이 됩니다. 이를 통해 저자들은 모든 수락 부분 공간의 교집합을 나타내는 단일 투영체 $P_f$를 정의할 수 있습니다.
3. 차수 상한(Degree Bound): 수락 확률을 나타내는 다항식의 차수는 총 양자 쿼리 수 $T(n)$에 의해 제한됩니다.
4. 완벽한 Forrelation 쌍: 저자들은 $\Phi(g, h) = 1$인 "완벽한 Forrelation 쌍"(bent functions)을 활용합니다. 이들은 $h$를 $k$개의 비트로 섭동(perturbing)시킬 때 Forrelation 값이 선형적으로 변화함($\Phi(g, f) = 1 - 2k/N$)을 보여줍니다.
5. 대칭화(Symmetrization): 클래식 트랜스크립트를 고정하고 완벽한 쌍으로부터 해밍 거리가 고정된 함수들에 대해 평균을 내어, 일변수 다항식 $q(k)$를 구성합니다.
6. 근의 개수 세기(Root Counting): 다항식 $q(k)$는 모든 "No" 인스턴스(넓은 범위의 $k$)에 대해 0이어야 하며, "Yes" 인스턴스($k=0$)에 대해서는 0이 아니어야 합니다. 0이 아닌 다항식은 자신의 차수보다 많은 근을 가질 수 없으므로, 차수(즉, 쿼리 수)는 지수적이어야 합니다.

3.2 분리의 강건성(Robustness)

논문은 모델의 약간의 완화 하에서도 분리가 유지됨을 보여줍니다:

• 무시할 수 있는 편차(Negligible Deviations): 오라클을 포함하는 유닛이 정확한 반사에 무시할 수 있는 수준(연산자 노름 기준)으로 가깝더라도, 클래스는 여전히 QIMA$^O$이며 하한은 여전히 유효합니다.
• 제한된 주소 지원(Restricted Address Support): 저자들은 반사가 아니더라도 단일 쿼리만을 수행하는 유닛에 대해서도 하한을 확장합니다. 단, 쿼리를 둘러싼 오라클 없는 회로가 오직 적은 수의 주소 큐비트($k$)에 대해서만 비자명하게 작용한다는 조건이 있다면, $n - k(n) = \omega(\log n)$일 때 쿼리 하한은 여전히 초다항식(superpolynomial)입니다.

3.3 모델의 타이트함(Tightness of the Model - 붕괴 결과)

QIMA$^O$ 정의의 특정 제약 조건을 정당화하기 위해, 저자들은 이러한 제약들을 완화할 경우 클래스가 QMA$^O$로 붕괴됨을 증명합니다:

• 역다항식 편차(Inverse-Polynomial Deviations): 유닛이 반사와 역다항식 거리 내에 있도록 허용하면(무시할 수 있는 수준이 아닌), 클래스는 QMA$^O$로 붕괴됩니다. 이는 단일 유닛이 QMA 검증자를 시뮬레이션하는 Marriott-Watros 증폭 가젯의 변형을 사용하여 보여집니다.
• 반사 없는 단일 쿼리: 반사 요구사항이 완전히 제거되더라도 유닛이 단일 쿼리로 제한된다면, 클래스는 여전히 QMA$^O$로 붕괴됩니다. 이는 다중 쿼리 시뮬레이션을 단일 쿼리로 인코딩하는 순환 클락(cyclic clock) 구조(Feynman-Kitaev와 유사)를 사용합니다.
• 신뢰할 수 있는 보조 큐비트: 검증자에게 단 하나의 신뢰할 수 있는 보조 큐비트($|0\rangle$으로 초기화됨)를 허용하면 QIMA는 QMA로, QIMA$^O$는 QMA$^O$로 붕괴됩니다. 이는 QMA-완전임이 알려진 "Pinned Commuting Local Hamiltonian" 문제에 의존합니다.

4. 의의 및 주장

본 논문은 일반적인 CLH 문제가 BQP-하드일 가능성에 대한 상대화된 증거를 제공한다고 주장합니다. BQP는 QMA에 포함되므로, 만약 CLH가 BQP-하드라면 이는 QMA에 대한 강력한 구조적 성질을 함의하게 됩니다. $BQP^O \not\subseteq QIMA^O$라는 분리는 QIMA(그리고 확장하여 CLH)에서의 교환 가능성 제약이, 오라클이 존재하는 상황에서도 BQP의 전체 능력을 포착하는 것을 방해하는 유의미한 제한임을 시사합니다.

나아가, 이 연구는 QIMA 정의의 타이트함을 명확히 합니다. 저자들은 교환성, 오라클 쿼리에 대한 반사 요구사항, 그리고 신뢰할 수 있는 보조 큐비트의 부재라는 특정 조합이 QMA보다 엄격히 약한 클래스를 정의하는 데 필요하다고 주장합니다. 이러한 조건 중 하나라도 완화하면 즉시 QMA의 전체 능력을 회복하게 되며, 이는 QIMA의 "양자적 특성"이 매우 취약하며 이러한 구조적 제약에 정밀하게 의존하고 있음을 시사합니다.

이 결과는 CLH가 QMA-완전인지에 대한 비상대화적(unrelativized) 질문을 해결하지는 못하지만, 위에서 구축된 오라클에 대해 해당 명제가 실패하므로, 그러한 완전성을 증명하려면 비상대화적 기법이 필요할 것임을 확립합니다.