A complexity theory for non-local quantum computation

기술 요약: 비로컬 양자 계산을 위한 복잡도 이론

문제 정의
비로컬 양자 계산(Non-local quantum computation, NLQC)은 두 시스템 사이의 국소적 상호작용을 단 한 번의 통신과 공유된 얽힘으로 대체한다. NLQC에서 핵심적인 관심 대상은 특정 계산을 구현하는 데 필요한 얽힘 비용(entanglement cost)이다. 그러나 특정 NLQC 작업에 대한 얽힘 하한(lower bounds)을 증명하는 것은 기성 복잡도 측정치(예: 메모리 또는 통신 복잡도)에 대한 하한을 증명하는 것과 같이 매우 어려운 문제에 직면해 있어, 이 비용을 완전히 규명하는 데 근본적인 장애물이 존재한다. 예를 들어, P 클래스에 속하는 함수들에 대해 f-route 작업의 초다항식(super-polynomial) 하한을 증명하는 것은 복잡도 클래스 L과 P를 분리하는 문제가 된다.

이러한 직접적인 하한 증명의 장벽을 우회하기 위해, 저자들은 고전적 복잡도 이론과 유사한 간접적인 접근 방식을 제안한다. 즉, 서로 다른 NLQC 작업들 사이의 자원 효율적인 환산(reduction)을 식별함으로써 이들의 상대적 난이도를 연구하는 것이다. 목표는 다양한 작업 간의 관계를 매핑함으로써 NLQC를 위한 "복잡도 이론"을 구축하고, 기존의 증명들을 단순화하며, 동등한 작업들 사이에 속성을 전이시키는 것이다.

방법론
본 논문은 **NLQC 환산(NLQC reductions)**을 위한 공식적인 프레임워크를 도입한다.

• 자원 상태 환산 (Resource State Reduction): 만약 $F$를 구현하기에 충분한 자원 상태를 사용하여 (상수 배의 오버헤드로) $G$를 구현할 수 있다면, $G$는 $F$로 환산된다.
• 오라클 환산 (Oracle Reduction): $G$의 프로토콜이 $F$를 오라클(black box)로 사용하는 더 엄격한 형태이며, 이는 $F$의 국소 연산을 $G$에 직접 적용할 수 있음을 의미한다.
• 작업의 분류: 저자들은 NLQC 작업을 다음과 같이 분류한다:
  1. 고전적 제어 (Classically Controlled): 작은 양자 연산이 큰 고전적 계산에 의해 제어되는 프로토콜 (예: f-route, f-measure, CDQS).
  2. 결맞음 제어 (Coherently Controlled): 중첩 상태에 있는 입력을 통해 유니터리 연산을 구현하는 프로토콜 (예: Cf-SWAP, Cf-PHASE, Cf-PAULI).
  3. 상태/유니터리 클래스 (State/Unitary Classes): 불리언 함수가 아닌 상태 변환에 의해 정의되는 작업 (예: Interchange 및 Distinguish).

방법론은 다이아몬드 노름(diamond norm), 충실도(fidelity), 엔트로피 부등식(예: CIT 부등식)과 같은 양자 정보 이론의 특성을 활용하여 이러한 클래스들 사이의 명시적인 환산(함축 관계)을 구축하는 것을 포함한다.

주요 기여 및 결과

1. 고전적 제어 작업의 동등성:
   주요 결과는 세 가지 주요 고전적 제어 NLQC 작업이 $O(1)$ 오버헤드 환산 하에 동등함을 증명한 것이다:
   $$\text{f-route} \iff \text{f-measure} \iff \text{CDQS}$$

• f-route: 불리언 함수 $f(x,y)$에 따라 양자 시스템 $Q$를 Alice 또는 Bob에게 전달(routing)함.
• f-measure: Alice와 Bob이 $f(x,y)$에 의해 결정되는 BB84 상태를 입력으로 하여 비트 $b$를 출력함.
• CDQS (Conditional Disclosure of Secrets): $f(x,y)=1$일 때만 레퍼리(referee)에게 비밀이 공개되는 암호학적 프리미티브.
• 함축: 이 동등성은 기존 문헌을 크게 단순화한다. 이전에 f-route와 f-measure에 대해 각각 별도로 증명되었던 속성들이 이제 둘 모두에 적용된다. 특히, f-measure는 다음을 상속받는다:
  • 모든 함수에 대해 $2^{O(\sqrt{n} \log n)}$의 상한.
  • $\text{Mod}_k\text{L}$ 복잡도 클래스에 속하는 함수들을 위한 효율적인 프로토콜.
  • 랜덤 오라클 모델에서의 보안 결과 및 병렬 반복(parallel repetition) 속성.

2. 결맞음 제어 연산 간의 환산:
   저자들은 결맞음 작업들 사이의 계층 구조와 동등성을 확립한다:

• Cf-SWAP $\implies$ Cf-PHASE: 결맞은 스왑을 구현하는 것은 결맞은 위상 변화(phase shift)를 함축한다.
• Cf-PHASE $\iff$ Cf-PAULI: 저자들은 상수 배의 오버헤드 하에 결맞은 위상 작업이 결맞은 파울리 작업(Cf-Z 또는 Cf-PAULI)과 동등함을 증명한다.
• 결맞음 $\implies$ 고전적: 결정적으로, 본 논문은 결맞은 프리미티브인 Cf-PHASE(및 따라서 Cf-PAULI)가 고전적 제어 작업(f-route, f-measure, CDQS)을 구현하기에 충분히 강력하다는 것을 보여준다. 이는 결맞은 프로토콜이 비결맞음(incoherent) 프로토콜보다 최소한 같거나 더 어려울 수 있음을 시사한다.
• 합성 (Composition): 본 논문은 이러한 결맞은 작업들을 합성하는 방법(예: AND 연산을 통한 제어 추가)을 상세히 다루며, 이때 제어의 수에 대해 선형적인 오버헤드만을 갖는다.

3. 상태 변환 환산:
   저자들은 불리언 함수로 정의되지 않는 작업들을 조사한다. 그들은 Interchange(두 직교 상태 $|\psi_0\rangle$와 $|\psi_1\rangle$를 교환하는 것)에 대한 효율적인 NLQC가 Distinguish(푸리에 상태 $|\phi_\pm\rangle = \frac{1}{\sqrt{2}}(|\psi_0\rangle \pm |\psi_1\rangle)$를 구별하는 것)에 대한 효율적인 NLQC를 함축함을 증명한다. 이 결과는 표준 양자 회로 복잡도에서의 유사한 동등성에서 영감을 받았다. 역방향은 여전히 미해결 과제로 남아 있다.

의의 및 주장
본 논문은 이러한 환산을 확립함으로써 NLQC를 위한 보다 완전한 복잡도 이론의 토대를 마련한다고 주장한다.

• 단순화: f-route, f-measure, CDQS의 동등성은 이러한 작업의 연구를 통합하여, 연구자들이 하나의 대표적인 프리미티브에 집중할 수 있게 한다.
• 새로운 속성: (상한의 전이, 예: f-route에서 f-measure로)는 이전에 덜 연구되었던 작업들에 대해 새로운 효율적인 프로토콜과 복잡도 상한을 제공한다.
• 복잡도 이론적 통찰: 저자들은 이러한 환산을 연구하는 것이 결국 복잡도 측정치에 대한 새로운 하한을 찾는 경로가 될 수 있다고 제안한다. NLQC의 얽힘 비용는 복잡도 측정치에 의해 상한이 정해지므로, NLQC 작업에 대한 하한을 증명하는 것은 복잡도 클래스에 대한 하한을 도출할 수 있기 때문이다.
• 장벽: 본 논문은 이 작업들에 대해 선형 하한을 증명하는 것이 고전적 통신 복잡도에서 돌파구를 마련해야 하는 "CDS 장벽"과 동일한 문제에 직면해 있음을 인정한다.
• 열린 질문: 저자들은 모든 결맞은 작업이 모든 비결맞음 작업보다 엄격하게 더 어렵다는 것을 증명하지 않았으며, Interchange/Distinguish 환산의 역방향 또한 증명하지 않았음을 명시한다. 또한 Cf-SWAP이 Cf-PHASE를 함축하지만, 그 역방향은 아직 확립되지 않았음을 언급한다.

요약하자면, 본 논문은 직접적인 얽힘 비용 추정에서 벗어나 NLQC 작업의 구조적 분석으로 초점을 전환하며, 많은 서로 다른 프로토콜이 계산적으로 동등하고 결맞은 제어가 강력하며 잠재적으로 더 어려운 프레임워크를 제공한다는 것을 입증한다.