기술적 요약: 근사 양자 회로 멤버십 및 최적화의 난해성에 관하여

1. 문제 정의

본 논문은 양자 회로 이론의 두 가지 근본적인 문제인 **근사 멤버십(Approximate Membership)**과 **근사 최적화(Approximate Optimization)**의 계산 복잡도를 조사한다.

• 근사 멤버십 ($\text{ApproxMember}$): 게이트 집합 $G$에 대한 양자 회로 $C$, 유니터리 집합 $S$, 거리 메트릭 $m$, 그리고 허용 오차 $\epsilon$이 주어졌을 때, $d_m(C, U) \le \epsilon$을 만족하는 유니터리 $U \in S$가 존재하는지 결정한다.
  • 특수한 경우로 근사 항등식($\text{ApproxId}$) 문제가 있으며, 이는 $S = \{I\}$인 경우이다.
  • 본 논문은 $S$에 대해 세 가지 특정 집합을 고려한다:
    1. $S = \{I\}$ (항등 행렬).
    2. $S \subseteq S_{\text{Cliff}}$ (클리포드 회로로 구현 가능한 유니터리).
    3. $S \subseteq S_{\text{GP}}$ (일반화된 치환 행렬, 즉 중첩을 생성하지 않는 유니터리).
• 근사 최적화 ($\text{ApproxOpt}$): 회로 $C$, 비용 함수 $f$, 그리고 예산 $k$가 주어졌을 때, $d_m(C, C') \le \epsilon$이고 $f(C') \le k$를 만족하는 동등한 회로 $C'$가 존재하는지 결정한다. 비용 함수 $f$는 그 "자유 집합(free set)" $S_f = \{U_{C'} \mid f(C') = 0\}$에 의해 특징지어진다.

본 연구는 Janzing, Wocjan, Beth (2005)의 선행 연구가 회로가 항등 행로(identity)에 가깝거나 멀다는 약속(promise) 하에서 비항등 체크(non-identity check) 문제의 QMA-완전성을 입증한 것과 대조적으로, 약속이 없는(promise-free) 입력에 초점을 맞춘다. 즉, 입력 회로의 대상 집합까지의 거리가 알려지지 않은 상태에서도 문제가 여전히 어려운지를 묻는다.

저자들은 유니터리 사이의 거리를 측정하기 위한 세 가지 표준 메트릭을 분석한다:

1. 사인 메트릭(Sine Metric): 트레이스(trace)에 기반하며, 평균적인 차이를 포착한다 ($d_{\text{Sine}}$).
2. 스펙트럼 메트릭(Spectral Metric): 연산자 노름(operator norm)에 기반하며, 최악의 경우의 차이를 포착한다 ($d_{\text{sp}}$).
3. 연산자 메트릭(Operator Metric): 스펙트럼 메트릭의 전역 위상 불변(global-phase-invariant) 버전이다 ($d_{\text{op}}$).

2. 방법론

저자들은 PP(Probabilistic Polynomial time) 복잡도 클래스를 근사 멤버십 문제로 환원함으로써 난해성을 입증한다. 이들의 방법론의 핵심 단계는 다음과 같다:

1. 소스 문제: 이들은 명제 공식 $\phi$가 그 할당의 최대 $\beta$만큼 만족되는지 묻는 PP-난해 문제인 AtMostSat을 활용한다. 또한, 만족하는 할당의 비율이 $\kappa$ 이하라고 약속되는 버전인 PromiseAtMostSat을 도입한다.
2. 약속-근사 환원(Promise-to-Approximate Reduction): 이들은 PromiseApproxId(회로가 $\tau$-가깝다는 약속 하에 $\epsilon$-가까운지 확인하는 문제)가 PP-난해임을 증명한다. 이는 공식 $\phi$로부터 만족하는 비율 $\gamma(\phi)$의 엄격한 증가 함수 $g(\gamma(\phi))$로서 거리 $d_m(I, C)$를 갖는 Clifford+T 회로 $C$를 구성함으로써 달성된다.
   • 사인 메트릭의 경우, 제어-XOR 연산($|x\rangle|b\rangle \mapsto |x\rangle|b \oplus \phi(x)\rangle$)을 구현하는 회로를 구성한다.
   • 스펙트럼 및 연산자 메트릭의 경우, $\gamma(\phi)$에 의존하는 고윳각(eigenangles)을 갖는 회로를 구성하기 위해 그로버 반복(Grover iterate)을 활용한다. 연산자 메트릭의 경우, 단위 원 위의 고윳각의 호 길이를 제어하기 위해 이러한 회로들의 텐서 곱을 사용한다.
3. 약속 제거:
   • 경우 $S = \{I\}$: 약속된 버전의 난해성은 특정 범위의 $\epsilon$에 대해 약속이 없는 버전의 난해성을 직접적으로 함의한다.
   • 경우 $S \subseteq S_{\text{Cliff}}$: 삼각 부등식 논증(Lemma 6)을 활용한다. 충분히 작은 $\epsilon$(구체적으로 $\epsilon < \sqrt{2}/4$)에 대해, 만약 회로 $C$가 $I$에 가깝다고 약속된다면, $C$에 $\epsilon$-가까울 수 있는 $S_{\text{Cliff}}$의 원소는 $I$로부터의 거리가 0인 것들(즉, $I$ 자신)뿐임을 보인다. 이는 $I$와 다른 클리포드 유니터리 사이의 최소 비제로 거리를 하한으로 설정함으로써 가능하다.
   • 경우 $S \subseteq S_{\text{GP}}$: 작은 $\gamma(\phi)$에 대해 $S_{\text{GP}}$ 집합까지의 거리가 정확히 항등 행렬까지의 거리와 같아지는 특정 회로를 구성하여 약속 문제로부터 직접적인 환원을 가능하게 한다. 이 환원은 $I$가 $S$에 포함될 때($I \in S \subseteq S_{\text{GP}}$) 적용된다.

3. 주요 기여 및 결과

주요 정리 (정리 1)

본 논문은 게이트 집합 $G$가 Clifford+T를 정확하게 구현할 수 있다면, ApproxMember가 광범위한 파라미터 범위에서 PP-hard임을 증명한다. 난해성은 다음 조건에서 성립한다:

• 집합 $S$: $S=\{I\}$, $I \in S \subseteq S_{\text{Cliff}}$, 그리고 $I \in S \subseteq S_{\text{GP}}$.
• 메트릭: 사인, 스펙트럼, 연산자 메트릭.
• 허용 오차 $\epsilon$:
  • $S=\{I\}$ 및 트레이스 기반(사인) 메트릭의 경우: 모든 $0 < \epsilon < 1$ (전체 직경)에 대해 PP-hard.
  • $S=\{I\}$ 및 스펙트럼/연산자 메트릭의 경우: 모든 $0 < \epsilon < 2$에 대해 PP-hard.
  • $I \in S \subseteq S_{\text{Cliff}}$의 경우: $0 < \epsilon < \sqrt{2}/4 \approx 0.3536$에 대해 PP-hard.
  • $I \in S \subseteq S_{\text{GP}}$의 경우: 사인 메트릭에 대해 $0 < \epsilon < 1$, 스펙트럼/연산자 메트릭에 대해 $0 < \epsilon < \sqrt{2}$에 대해 PP-hard.

따름정리 1 (최적화 난해성)

이 결과는 해당 $\epsilon$ 범위 내에서 총 게이트 깊이/개수, 비-클리포드 게이트 깊이/개수, 그리고 중첩 게이트 깊이/개수를 최소화하는 문제에 대해 ApproxOpt가 PP-hard임을 직접적으로 함의한다.

구체적 기술적 발견

1. 고전-가역 게이트에 대한 난해성: 게이트 집합 $G$가 중첩을 생성할 수 없는 고전-가역 게이트(예: X, CNOT, Toffoli)로만 구성되더라도, 사인 메트릭 하에서의 ApproxId 문제는 모든 $0 < \epsilon < 1$에 대해 여전히 PP-hard이다.
2. 강건성(Robustness): 난해성 결과는 사인, 스펙트럼 또는 연산자 메트릭으로부터 엄격히 증가하는 함수를 통해 유도된 모든 거리 척도로 일반화된다. 또한, 최적 비용이 0일 때 난해성이 유지되므로, 최적 비용을 임의의 인자(상수 혹은 그 이상) 내에서 근사하는 것만 목표로 하더라도 이 문제는 PP-hard이다.
3. 선행 연구와의 비교: 본 논문은 Janzing, Wocjan, Beth (2005)의 결과를 강화한다. 그들의 결과는 비항등 체크의 약속된 문제에 대해 QMA-완전성을 보여주었으나, 본 연구는 더 넓은 메트릭과 집합 $S$에 대해 약속이 없는 문제가 (QMA보다 훨씬 강력하다고 믿어지는) PP-hard임을 보여준다.

4. 의의 및 주장

저자들은 자신들의 결과가 근사 양자 회로 최적화가 약속 기반의 비항등 체크가 가진 QMA-완전성에 비해, 약속이 없는 입력에 대해 근본적으로 더 어렵다는 것을 입증한다고 주장한다.

• 자원 독립성: 난해성은 사용 가능한 양자 자원(모든 게이트, 비-클리포드 게이트, 또는 중첩)에 관계없이 지속된다.
• 메트릭 독립성: 난해성은 다양한 거리 메트릭(트레이스 기반, 스펙트럼, 연산자)에 걸쳐 성립한다.
• 실질적 함의: 표준 하드웨어 게이트 집합(Clifford+T 등)이 이러한 조건을 만족하므로, 이 난해성 결과는 실제 양자 컴파일 및 최적화 작업에 직접 적용된다. 이 결과는 최소 비용(예: 최소 T-count 또는 깊이)을 갖는 동등한 회로를 찾는 것이, 오차 허용 범위가 메트릭 공간의 직경을 초과할 정도로 매우 크지 않은 한, 클래식 컴퓨터에게는 난해함을 의미한다.

논문은 결론적으로 더 큰 $\epsilon$ 값(구체적으로 클리포드 집합의 경우 $\epsilon \ge \sqrt{2}/4$, 치환 집합의 경우 $\epsilon \ge \sqrt{2}$)에 대한 복잡도와 일치하는 상한(upper bound)에 관한 열린 문제를 언급하면서도, 대수적 게이트 집합과 $\epsilon = \sqrt{2}/2$에서의 사인 메트릭에 대해서는 문제가 PP-complete임을 밝히며 마무리한다.