Complexity of detecting large coefficients in the Pauli basis

기술 요약: 파울리 기저(Pauli Basis)에서 큰 계수를 탐지하는 것의 복잡도

문제 정의
본 논문은 간결한 양자 회로 $C$에 의해 준비된 양자 상태 $\rho$가 파울리 기저에서 "큰" 계수를 갖는지 여부를 결정하는 계산 문제를 다룬다. 형식적으로, 주어진 상태 준비 회로 $C$와 임계값 $\epsilon > 0$가 주어졌을 때, $\text{Tr}(P\rho)$의 절댓값이 $\epsilon$ 이상인 비항등 파울리 행렬 $P \in \mathcal{P}_n \setminus \{I^{\otimes n}\}$가 존재하는지 결정하는 과제이다. 이 문제는 약속 문제(promise problem)로 프레임화된다: 알고리즘은 그러한 $P$가 존재하면 "Yes"를 반환해야 하며, 모든 비항등 $P$에 대해 $|\text{Tr}(P\rho)| \le \epsilon/2$이면 "No"를 반환해야 한다. 상태 $\rho$는 $C$에 의해 생성된 순수 상태의 부분 트레이스(partial trace)로 정의되나, 본 논문은 $\rho$가 순수 상태인 경우(큐비트를 버리지 않는 경우)도 고려한다.

방법론
핵심 방법론은 고전적 선형 코드에 대해 알려진 난해한 문제인 $\lambda$-Gap Minimum-Weight Codeword ($\lambda$-GapMWC) 문제로부터의 복잡도 이론적 환원(reduction)을 포함한다.

1. 환원 구성: 저자들은 $\lambda$-GapMWC의 인스턴스 $(G, t)$ (여기서 $G$는 생성 행렬이고 $t$는 임계값임)를 LPC(Large Pauli Coefficient) 문제의 인스턴스로 매핑하는 구조를 구축한다.

   • 저자들은 $G$의 패딩된 버전을 유니폼하게 샘플링하여 확률 변수 $V$를 정의한다.
   • 저자들은 $k$개의 독립적인 $V$ 복사본에 대한 기대값으로서 밀도 행렬 $\rho_{G,t}$를 구성하며, 이는 효과적으로 계산 기저(computational basis)에서 대각 상태를 생성한다.
   • Lemma 3.2를 사용하여, 코드워드 $xG$의 해밍 가중치(Hamming weight)와 $\rho_{G,t}$ 상의 대각 파울리 연산자 $Z^x$의 기대값 사이의 직접적인 대수적 연결 고리를 확립한다:
     $$\text{Tr}(Z^x \rho_{G,t}) = \left(1 - \frac{2\text{wt}(xG)}{N}\right)^k$$
   • 패딩 크기 $N$과 샘플 수 $k$를 신중하게 선택함으로써, 가중치가 $t$ 이하인 코드워드가 존재하면 대응하는 파울리 기대값이 $\epsilon$을 초과하는 반면, 모든 코드워드의 가중치가 $\lambda t$보다 크면 모든 기대값이 $\epsilon/2$ 미만임을 보장한다.

2. 순수 상태로의 확장: $\rho$가 반드시 순수 상태여야 하는 경우를 다루기 위해, 저자들은 "숨기기(hiding)" 기법을 사용한다. 저자들은 보조 "샘플 레지스터"에 작용하는 비항등 파울리 연산자의 기대값을 억제하는 유니티 연산자 $U$(집중 측정(concentration of measure) 논거를 통한 Lemma 3.3 및 3.4에 의해 존재가 보장됨)를 활용한다. 이를 통해 환원은 가짜의 큰 계수를 도입하지 않고도 혼합 상태의 로직을 순수 상태 $|\Psi_{G,t}\rangle$ 내에 임베딩할 수 있다.

3. 복잡도 분석:

   • 멤버십(Membership): 본 논문은 LPC가 QCMA에 속함을 입증한다. 클래식한 증거(witness)는 파울리 행렬 $P$의 기술이다. 양자 검증자는 반복적인 파울리 측정을 사용하여 $\text{Tr}(P\rho)$를 추정할 수 있다. 만약 $\epsilon$이 회로 크기에 대한 역다항식(inverse-polynomial)이라면, 이 검증은 다항 시간 내에 실행된다.
   • 난해성(Hardness): $\lambda$-GapMWC에서 LPC로의 환원은 결정론적 다항 시간 내에 수행된다. $\lambda$-GapMWC는 NP에 대해 난해하므로 (구체적으로, 이를 BQP 내에서 해결하는 것은 $\text{NP} \subseteq \text{BQP}$를 의미함), 그 난해성은 LPC로 전이된다.

주요 기여 및 결과

• QCMA 멤버십: 이 문제는 QCMA에 속함을 보여주며, 파울리 연산자의 클래식한 기술이 검증에 충분함을 확인한다.
• BQP 하에서의 NP-난해성: 주요 결과는 만약 LPC가 BQP에 있다면 (즉, 다항 시간 양자 알고리즘에 의해 해결 가능하다면), NP $\subseteq$ BQP가 된다는 것이다. 이는 표준적인 가정인 $\text{NP} \not\subseteq \text{BQP}$ 하에서, 일반적인 상태에 대해 큰 파울리 계수를 탐지하는 효율적인 양자 알고리즘은 존재하지 않음을 시사한다.
• 순수 상태 난해성: 입력 상태가 순수 상태로 제한되는 경우에도 난해성 결과가 유지됨을 보여줌으로써, 큐비트를 버리는 것(혼합 상태)이 어려움의 원인인지에 대한 의문을 해결한다.
• BQP-난해성: 본 논문은 더 나아가 LPC가 BQP-hard임을 증명한다. 이는 LPC가 아마도 NP에 속하지 않을 것임을(단, $\text{BQP} \subseteq \text{NP}$가 아닌 한) 시사하며, 순수하게 클래식한 증거 특성화가 어려울 것임을 나타낸다.
• 상수 임계값: 난해성은 $\epsilon$이 입력 크기와 무관한 상수일 때도 유지되므로, 어려움이 오직 높은 정밀도의 탐지를 요구하는 데서 오는 것이 아님을 배제한다.

의의 및 주장
본 논문은 양자 상태의 파울리 기저 내 최대 계수를 찾는 효율적인 토모그래피 절차가 존재하는지에 대한 열린 질문을 해결한다고 주장한다. 결과는 표준적인 복잡도 가정 하에서 그러한 효율적인 절차가 존재하지 않음을 나타낸다.

저자들은 자신들이 QCMA 멤버십과 NP에 대한 난해성을 확립했지만, 타이트한 경계(예: QCMA-완전성)를 증명한 것은 아니라고 언급한다. 그러나 그들은 이러한 결과가 지형을 명확히 하는 데 충분하다고 주장한다: 큰 파울리 계수를 찾으려는 알고리즘이 다항 자원을 사용하려면, 파울리 희소성(Pauli sparsity), 스태빌라이저 유사 동작(stabilizer-like behavior), 낮은 랭크, 국소성 또는 낮은 얽힘과 같은 상태에 대한 추가적인 구조적 가정을 반드시 의존해야 한다. 그러한 제약 조건이 없다면, 일반적인 문제는 계산적으로 난해한 상태로 남는다.