Exact Non-Identity Check and Gate-Teleportation-Based Indistinguishability Obfuscation are NP-hard for Low-T-Depth Quantum Circuits

기술 요약: 낮은 T-깊이 양자 회로에 대한 정확한 비항등 체크(Exact Non-Identity Check) 및 게이트 텔레포테이션 기반 구별 불가능 난독화의 NP-난해성

문제 정의
본 논문은 클리포드(Clifford) 및 $T$ 게이트로 구성된 양자 회로(Clifford+$T$ 회로)의 맥락에서 두 가지 상호 연관된 문제의 계산 복잡도를 조사한다. 첫 번째 문제는 **정확한 비항등 체크(Exact Non-Identity Check, ENIC)**로, 주어진 $n$-큐비트 양자 회로 $C$가 전역 위상(global phase)을 제외하고 항등 연산자와 정확히 동일한지($C = e^{i\theta}I^{\otimes n}$)를 묻는 문제이다. 두 번째 문제는 **게이트 텔레포테이션 기반 구별 불가능 난독화(qiO)**의 실현 가능성에 관한 것이다.

2021년, 브로드벤트(Broadbent)와 카즈미(Kazmi)는 양자 회로의 계산적 구별 불가능 난독화를 위한 프로토콜을 제안했다. 이 프로토콜의 효율성은 $C P_x C^\dagger$ (여기서 $P_x$는 벨 측정 결과에 대응하는 파울리 연산자)의 기술(description)을 고전적으로 효율적으로 계산할 수 있는 능력에 달려 있다. 이 작업은 두 회로가 완벽하게 동일한지 여부를 결정하는 것만큼이나 어렵다. 브로드벤트와 카즈미는 이 프로토콜이 **로그 개수의 T-게이트(logarithmic T-count)**를 가진 Clifford+$T$ 회로에 대해서는 효율적임을 보여주었으나, 로그 T-깊이(logarithmic T-depth)(최소 하나 이상의 $T$ 게이트를 포함하는 시간 단계의 수)를 가진 회로에 대한 복잡도는 미해결 상태로 남겨두었다. 본 논문은 $O(\log n)$의 낮은 $T$-깊이를 가진 회로로 제한될 때 ENIC 및 관련 공액 인코딩(conjugate-encoding) 작업이 여전히 다루기 쉬운지(tractable)를 다룬다.

방법론
저자는 코딩 이론의 문제, 특히 이진 선형 코드의 코드워드 가중치(codeword weights)와 관련된 문제에 양자 회로 문제의 복잡도를 연결하는 환원적 접근 방식을 사용한다.

1. 공액 인코딩 및 파울리 확장: 논문은 $C P_x C^\dagger$ 형태의 유니터리의 파울리 확장을 분석한다. 저자는 이들의 기능성에만 의존하는 이 유니터리의 고전적 기술인 "공액 인코딩(conjugate-encoding)"이라는 개념을 도입한다. 이러한 인코딩의 효율성은 파울리 계수(Pauli coefficients)를 계산하는 능력과 직결된다.
2. 코딩 이론으로의 환원: 핵심 기술 전략은 특정 Clifford+$T$ 회로(구체적으로 "PC-회로")를 구축하여, 이들의 파울리 계수가 특정 지점(예: $1/\sqrt{2}$)에서 평가된 이진 선형 코드의 가중치 열거 다항식(weight enumerator polynomials)을 인코딩하도록 하는 것이다.
   • 논문은 파울리 연산자에 적용되는 Clifford 및 $T$ 층(layers)의 순서를 나타내는 데이터 구조인 **깊이-$d$ 프레젠테이션(depth-$d$ presentations)**을 정의한다.
   • 깊이-$d$ 프레젠테이션의 파울리 계수가 깊이-$(d-1)$ 프레젠테이션의 계수와 어떻게 연관되는지를 보여주는 재귀 공식(명제 12)을 수립한다.
   • 특정 $T$-깊이를 가진 회로를 정교하게 설계함으로써, 저자는 결과적인 유니터리 확장의 계수가 이진 선형 코드의 코드워드들에 의해 인덱싱된 $1/\sqrt{2}$의 거듭제곱 합에 해당함을 입증한다.
3. 난해성 가정: 논문은 이진 코드에 관한 알려진 난해성 결과에 의존한다:
   • 이진 코드가 특정 가중치를 가진 코드워드를 포함하는지 결정하는 것은 **NP-완전(NP-complete)**이다 (정리 8).
   • 가중치 분포(따라서 가중치 열거 다항식)를 계산하는 것은 **#P-난해(#P-hard)**이다 (정리 9).
   • 저자는 파울리 확장의 위상을 제어하면서 이러한 코딩 문제를 양자 회로 환경에 삽입하기 위해 특정한 "1-나머지 행렬(1-remainder matrices)" 군을 도입한다.

주요 기여 및 결과
논문은 다음의 주요 결과(정리 6)를 확립한다:

1. 낮은 T-깊이에서의 ENIC의 NP-난해성: ENIC는 $T$-깊이가 2($T^2$)인 회로에 대해서는 다항 시간 내에 해결 가능하지만, $T$-깊이가 $O(\log n)$인 회로에 대해서는 결정 문제가 **NP-난해(NP-hard)**가 된다. 구체적으로, ENIC는 $T^{K \log n}$ 도메인 상에서 NP-난해이다.
2. 관련 문제의 난해성: SUPPORT( $C P_x C^\dagger$의 확장에서 특정 파울리가 0이 아닌 계수와 함께 나타나는지 결정하는 문제) 및 COMMUTE($C P_x C^\dagger = P_x$인지 결정하는 문제) 문제 또한 $T^{K \log n}$ 도메인 상에서 NP-난해임이 입증되었다.
3. 계수 계산의 #P-난해성: 파울리 계수의 정확한 값을 계산하는 함수적 문제(CONJUGATE)는 $T^3$ 도메인 상에서 #P-난해임이 밝혀졌다.
4. 난독화에 대한 함의: 이러한 결과는 $P \neq NP$가 아니라면, Clifford+$T$ 회로의 로그 $T$-깊이에 대해 게이트 텔레포테이션 기반의 구별 불가능 난독화(Broadbent and Kazmi, 2021) 프로토콜을 효율적인 프로토콜로 확장할 수 없음을 시사한다. 병목 현상은 요구되는 공액 인코딩( $C P_x C^\dagger$의 기술)을 생성하는 데 따르는 고전적 어려움에 있다.

의의 및 주장
본 논문은 ENIC에 대한 새로운 독립적 증명을 제공하며, 알려진 복잡도 지형을 일반 회로에서 낮은 $T$-깊이로 확장한다고 주장한다. 그 의의는 다음과 같다:

• 난독화 프로토콜의 한계 설정: 이 논문은 $P \neq NP$라고 가정할 때, 로그 $T$-깊이 Clifford+$T$ 회로에 대해 게이트 텔레포테이션 기반의 계산적 구별 불가능 난독화 가능성을 효과적으로 배제한다. 이는 이 프로토콜이 고전적 난독화로부터 양자 난독화를 구축하기 위한 주요 후보였기 때문에 중요하다.
• 양자 및 고전 복잡도의 연결: 이 연구는 양자 회로 분석과 고전 코딩 이론을 연결하며, 낮은 깊이의 양자 회로 내 파울리 계수의 대수적 구조가 어려운 코딩 이론적 문제를 인코딩하고 있음을 보여준다.
• 복잡도 경계의 정밀화: 논문은 다루기 쉬운 영역과 다루기 어려운 영역 사이의 간극을 좁힌다. $T$-깊이 2는 쉽지만, 난해성이 로그 깊이 영역에서 발생함을 보여준다. 이는 $T$-게이트가 비용이 많이 드는 결함 허용 양자 컴퓨팅(fault-tolerant quantum computing)에서 매우 중요한 부분이다.

열린 질문들
논문은 난해성의 정확한 경계가 여전히 불분명하다는 점을 언급하며 끝맺는다. ENIC가 상수 $T$-깊이($T^{O(1)}$)에서도 여전히 NP-난해인지, 아니면 $T$-깊이 3에서 다항 시간 내에 해결 가능한지에 대한 의문을 제기한다. 또한, SUPPORT 문제의 난해성이 "형식적 코드 동등성(formal code equivalence)" 문제(두 코드가 동일한 가중치 열거자를 갖는지 결정하는 문제, 이는 그래프 동형성(Graph Isomorphism)과 관련된 코드 동등성 문제의 변형임)와 연결되어 있을 가능성을 시사한다.