Equivalence of non-local computation tasks beyond Clifford operations

기술 요약: 클리포드 연산을 넘어선 비로컬 계산 작업의 동등성

문제 정의
비로컬 양자 계산(NLQC)은 두 명의 분리된 당사자인 앨리스(Alice)와 밥(Bob)이 단 한 번의 동시 양자 통신과 공유된 얽힘만을 사용하여 분산된 시스템에 대한 공동 양자 채널을 어떻게 구현할 수 있는지를 연구한다. 모든 양자 채널가 NLQC를 통해 구현될 수 있음은 알려져 있으나, 그 자원 비용, 특히 사전에 공유된 얽힘의 양은 서로 다른 작업들에 따라 크게 달라진다.

NLQC 연구의 주요 동기는 양자 위치 검증(QPV)에 대한 응용이다. QPV에서 증명자는 검증자들에게 자신의 물리적 위치를 입증하려고 시도한다. 다른 곳에 위치한 속임수를 쓰는 증명자는 NLQC를 사용하여 정직한 증명자의 로컬 연산을 시뮬레이션해야 한다. QPV 스킴의 보안은 NLQC 작업의 난해함에 의존한다: 만약 속임수를 쓰는 증명자가 해당 작업을 시뮬레이션하기 위해 지수적으로 큰 양의 얽힘을 필요로 한다면, 그 스킴은 안전하다고 간주된다.

본 연구에서 다루는 핵심 문제는 서로 다른 NLQC 작업들 간의 상대적 난이도에 대한 통합된 이해가 부족하다는 점이다. 특히 "f-라우팅(f-routing)" 작업(양자 시스템의 클래식 제어 라우팅)은 광범위하게 연구되어 왔으나, 다른 유망한 QPV 프로토콜들—특히 단순한 라우팅을 넘어선 제어된 양자 측정이나 유니터리를 포함하는 작업들—이 개선된 보안을 제공하는지는 불분명하다. 저자들은 이러한 겉보기에 구별되는 작업들이 서로 환원 가능한지, 즉 이들이 동일한 점근적 얽힘 비용을 공유하는지를 결정하고자 한다.

저자들은 계산 복잡도 이론에서의 환원과 유사한 환원(reductions) 프레임워크를 사용한다. 저자들은 두 가지 유형의 환원을 정의한다:

1. 자원 상태 환원(Resource State Reduction): 작업 $G$가 $F$에 필요한 자원 상태의 적은 수의 복사본을 사용하여 구현될 수 있다면, $G$는 $F$로 환원된다.
2. 오라클 환원(Oracle Reduction): 작업 $G$가 $F$를 구현하는 블랙박스 호출의 적은 횟수와 로컬 연산 및 추가적인 적은 양의 공유 자원을 사용하여 구현될 수 있다면, $G$는 $F$로 환원된다.

본 논문은 f-제어 2→2 작업에 초점을 맞춘다. 여기서 수행되는 연산은 앨리스($x$)와 밥($y$)에게 주어진 불리언 함수 $f(x, y)$의 값에 따라 결정된다. 입력 시스템은 일반적으로 상수 크기($O(1)$ 큐비트)이며, 클래식 입력은 매우 클 수 있다($n$ 비트).

기술적 접근 방식은 다음과 같다:

• 게이트 텔레포테이션 및 측정 기반 양자 계산(MBQC): 저자들은 한 NLQC 작업을 다른 NLQC 작업으로 변환하는 프로토콜을 구축하기 위해 게이트 텔레포테이션과 비적응형 MBQC에서 영감을 얻은 가젯(gadget)을 활용한다.
• 각도 특성화 및 조작: 단일 큐비트 측정을 위해, 저자들은 블로흐 구(Bloch sphere) 상의 회전 각도를 사용하여 작업을 특성화한다. 저자들은 더 단순한 프로토콜들의 조합(예: 각도 $\theta_1$과 $\theta_2$를 가진 $f$-측정 프로토콜을 결합하여 $\theta_1 + \theta_2$를 시뮬레이션하는 방식)을 사용하여 이러한 각도를 더하고, 나누고, 근사하는 기술을 개발한다.
• 포트 기반 텔레포테이션(Port-Based Teleportation): 부록에서는 양자 입력의 공간적 분포(앨리스 측, 밥 측, 또는 분할된 상태)가 상수 크기의 입력을 제공하는 한, 작업의 난이도를 크게 변화시키지 않음을 입증하는 데 사용된다.

주요 기여 및 결과

1. 단일 큐비트 f-측정 프로토콜의 동등성:
   저자들은 모든 비자명한 단일 큐비트 $f$-측정 프로토콜($f(x,y)$에 따라 측정 기저가 두 임의의 기저 $U$와 $V$ 사이에서 선택되는 경우)이 $O(1)$ 오라클 환원 하에 동등함을 증명한다.

   • 구체적으로, 임의의 $f\text{-measure}(U, V)$는 정준적인 경우인 $f\text{-measure}(I, H)$(계산 기저 또는 하다마르 기저에서의 측정)로 환원될 수 있다.
   • 이는 단일 큐비트 투영 측정 프로토콜 중 그 어떤 것도 $f$-라우팅에서 알려진 아지수적(sub-exponential) 얽힘 상한을 넘어서는 보안상의 이점을 제공하지 못함을 의미한다.

2. 제어된 클리포드 유니터리의 환원:
   본 논문은 $f$-제어 클리포드 유니터리와 클리포드 관련 기저에서의 측정이 $f\text{-measure}(I, H)$로 환원될 수 있음을 보여준다.

   • $f\text{-measure}(I, H)$와 $f\text{-Bell}$ 측정(벨 기저에서의 측정) 사이의 동등성을 확립함으로써, 저자들은 제어된 클리포드 연산이 $f\text{-Bell}$ 오라클을 사용하는 게이트 텔레포테이션 전략을 통해 구현될 수 있음을 보여준다.
   • 이는 $f$-라우팅으로 환원 가능한 작업의 범위를 확장하며, 멀티 큐비트 클리포드 제어 연산조차 기본 라우팅 작업보다 본질적으로 더 많은 얽힘을 요구하지 않음을 확인시켜 준다.

3. 제어된 대각 유니터리로의 확장:
   $U = C_1 D C_0$ 형태의 $f$-제어 유니터리($C_0, C_1$은 클리포드 회로, $D$는 임의의 대각 유니터리)에 대한 환원은 중요한 결과이다.

   • 저자들은 $f\text{-unitary}(I, U)$가 $O(n_Q)$의 오버헤드($n_Q$는 큐비트 수)를 가지고 $f\text{-measure}(I, H)$로 오라클 환원됨을 보여준다.
   • 이는 $D$가 높은 T-깊이(T-depth)를 가질 수 있어 $U$가 매우 비-클리포드(non-Clifford) 성질을 띌 수 있음에도 불구하고, 구현 비용이 더 단순한 클리포드 기반 $f$-측정 작업에 묶여 있다는 점에서 놀라운 결과이다.
   • 이 구성은 제어된 단일 큐비트 X-회전($f$-측정을 통해 구현 가능)을 CZ 게이트를 통해 제어된 멀티 큐비트 Z-회전과 연결하는 "Z-회전 주입 가젯"에 의존한다.

의의 및 주장
본 논문은 실행 가능한 QPV 프로토콜의 지형이 이전에 생각했던 것보다 더 제한적이라고 주장한다. 환원의 풍부한 구조를 확립함으로써 저자들은 다음을 입증한다:

• 보안의 한계: 제어된 단일 큐비트 측정, 클리포드 연산, 그리고 특정 비-클리포드 대각 유니터리를 포함하는 많은 제안된 QPV 스킴들은 기본 $f$-라우팅 작업보다 개선된 보안을 제공하지 못한다. 이들은 모두 (클래식 입력 크기에 대해) 동일한 점근적 얽힘 비용 스케일링(아지수적)을 공유한다.
• 통합된 난이도: 이러한 작업들의 상대적 난이도는 통합되어 있다. 만약 $f$-라우팅에 대한 아지수적 공격이 존재한다면, 확립된 환원을 통해 이러한 더 넓은 클래스의 작업들에도 그 공격이 확장된다.
• 기술적 진보: 본 연구는 특정 게이트 텔레포테이션 가젯 및 각도 분할 기술과 같은 새로운 NLQC 전략을 도입하며, 이는 다른 NLQC 작업에 대한 얽힘 비용의 상한을 구축하는 데 독립적인 관심사가 될 수 있다.

저자들은 이러한 결과의 범위에 대해 신중한 태도를 유지하며, 본 연구가 다루는 범위가 광범위한 "실행 가능한" 프로토콜(큰 클래식 입력, 작은 양자 입력)을 포괄하고 있지만, 두 층의 대각 게이트나 더 복잡한 유니터리 구조가 이러한 환원을 피할 수 있는 더 높은 보안 수준을 제공할 수 있는지 여부는 여전히 미해결 과제로 남아 있다고 언급한다. 이 결과들은 초선형 하한(super-linear lower bounds)을 증명하려는 것이 아니라, $f$-라우팅의 알려진 상한을 벗어나지 못하는 직관적인 확장들이 많다는 점을 명확히 하는 데 목적이 있다.