기술 요약: 양자 상태 간의 Schatten 노름 및 거듭제곱 거리 추정

문제 정의

본 논문은 상태 준비 회로(state-preparation circuits)로 주어지는 두 $n$-큐비트 양자 상태 $\rho_0$와 $\rho_1$ 사이의 거리를 추정하는 계산 복잡도를 조사한다. 주요 초점은 양자 Schatten $\alpha$-노름 거리 $T_\alpha(\rho_0, \rho_1) := \frac{1}{2}\|\rho_0 - \rho_1\|_\alpha = \frac{1}{2}\text{tr}(|\rho_0 - \rho_1|^\alpha)^{1/\alpha}$와 그 거듭제곱 버전인 양자 Schatten $\alpha$-거듭제곱 거리 $\Lambda_\alpha(\rho_0, \rho_1) := \frac{1}{2}\text{tr}(|\rho_0 - \rho_1|^\alpha)$이다.

이 논문이 다루는 핵심 질문은 Schatten $\alpha$-노름을 이용한 양자 상태 구별 문제(QSD$_\alpha$): 즉, $T_\alpha(\rho_0, \rho_1) \geq 2/5$인지 또는 $T_\alpha(\rho_0, \rho_1) \leq 1/5$인지를 결정하는 문제의 계산 복잡도이다. 저자들은 트레이스 거리($\alpha=1$, QSZK-완전함이 알려짐)와 $\ell_2$ 유사 측정치(예: 힐베르트-슈미트 거리, $\alpha=2$, BQP에 속함) 사이의 복잡도 이분법을 해결하고자 한다. 구체적으로, 이 이분법이 모든 상수 $\alpha > 1$에 대해 성립하는지, 아니면 $\alpha$가 짝수 또는 홀수 정수인지에 따라 복잡도가 달라지는지를 묻는다.

또한, 본 논문은 $0 < \alpha < 1$ 범위에 대해서도 연구한다. 이 범위에서 $T_\alpha$는 더 이상 메트릭이 아니지만(삼각 부등식 실패), $\Lambda_\alpha$는 유효한 거리 메트릭(준 노름의 거듭제곱)으로 남는다. 저자들은 이 범위에서의 $\Lambda_\alpha$를 위한 효율적인 추정기를 탐구한다.

방법론

1. 효율적인 양자 추정기

저자들은 양자 특이값 변환(QSVT) 및 **유니타리 선형 결합(LCU)**에 기반한 양자 알고리즘을 개발한다.

• $\alpha > 1$인 경우 (Rank-Independent):
  핵심 과제는 함수 $f(x) = \text{sgn}(x)|x|^{\alpha-1}$를 효율적으로 근사하는 것이다. 저자들은 부호가 있는 양의 거듭제곱을 위해 최적 균등 다항식 근사(Bernstein의 연구 및 Tsallis 엔트로피에 관한 최근 결과에서 영감을 얻음)를 활용한다.

  • 저자들은 $[-1, 1]$ 상에서 균등 오차 $\epsilon$을 가지며 $\frac{1}{2}\text{sgn}(x)|x|^{\alpha-1}$을 근사하는 다항식 $P(x)$를 구성한다.
  • QSVT를 사용하여, $\nu = \rho_0 - \rho_1$에 대해 $\text{sgn}(\nu)|\nu|^{\alpha-1}$의 블록 인코딩을 구현한다.
  • 거리는 Hadamard 테스트를 통해 $\text{tr}(\rho_0 \cdot \text{sgn}(\nu)|\nu|^{\alpha-1}) - \text{tr}(\rho_1 \cdot \text{sgn}(\nu)|\nu|^{\alpha-1})$를 계산함으로써 추정된다.
  • 핵적인 혁신: 투영 연산자의 rank에 의존하는 블록 인코딩에 의존했던 기존 방식([WGL+24])과 달리, 이 방법은 상태의 rank에 의존하지 않는 다항식 근사를 사용하여 rank-independent한 쿼리 및 샘플 복잡도를 달성한다.

• $0 < \alpha < 1$인 경우 (Rank-Efficient):
  이 범위에서 함수 $x^{\alpha-1}$은 $x=0$에서 특이점을 갖는다. 저자들은 0에서 떨어진 곳에서 유효한(컷오프 $\delta$를 사용하는) 스케일링된 부호 거듭제곱에 대한 다항식 근사를 사용한다.

  • 알고리즘은 0 근처에서 오차가 발생하지만 유계인 다항식을 사용하여 $\text{sgn}(\nu)|\nu|^{\alpha-1}$을 근사함으로써 $\Lambda_\alpha$를 추정한다.
  • 이 접근 방식은 rank-dependent 복잡도, 즉 rank $r$에 대한 다항식 복잡도를 결과로 가져오지만, 이전의 경계값들을 개선한다.

2. 난해도 및 하한선

계산적 난해도를 확립하기 위해, 저자들은 트레이스 거리 $T(\rho_0, \rho_1)$를 $T_\alpha$ 및 $\Lambda_\alpha$와 연결하는 새로운 rank-dependent 부등식을 도출한다.

• 부등식: 순수 상태(pure states)에 대해 $T_\alpha$와 $T$는 상수 인자로 관계가 있지만, 혼합 상태(mixed states)의 경우 관계가 상태의 rank에 따라 달라짐을 증명한다. 구체적으로, $T(\rho_0, \rho_1) \leq 2(\text{rank}(\rho_0)^{1-\alpha} + \text{rank}(\rho_1)^{1-\alpha})^{-1/\alpha} T_\alpha(\rho_0, \rho_1)$이다.
• 축약(Reductions):
  • BQP-hardness: 순수 상태로 제한함으로써, 저자들은 $T_\alpha$ ($\alpha \geq 1$인 경우) 또는 $\Lambda_\alpha$ ($0 < \alpha < 1$인 경우)를 통한 상태 구별이 표준 BQP-완전 문제(PureQSD)만큼 어렵다는 것을 보여준다.
  • QSZK-hardness: $\alpha$가 1에 매우 가까운 경우(구체적으로 $1 \leq \alpha(n) \leq 1 + \text{negl}(n)$), 저자들은 $T_\alpha$에 대한 **부분 편극 정리(partial polarization lemma)**를 사용한다. 이 정리는 트레이스 거리에 대한 편극(polarization)과 유사하게 $T_\alpha$의 간극(gap)을 증폭할 수 있게 하여, 이 범위에서 QSD$_\alpha$가 QSZK-완전함을 증명한다.
  • 고정된 $0 < \alpha < 1$에 대해, 저자들은 트레이스 거리에 편극을 적용하고 $\Lambda_\alpha$의 $T^\alpha$ 및 rank에 대한 상한을 사용하여 PoweredQSD$_\alpha$가 QSZK-hard함을 보여준다.

주요 기여 및 결과

1. 효율적인 양자 알고리즘

• 고정된 $\alpha > 1$에 대해: 저자들은 $O(1)$ 쿼리(rank-independent)를 사용하여 가산 오차 $\epsilon$으로 $T_\alpha(\rho_0, \rho_1)$를 추정하는 효율적인 양자 알고리즘을 제시한다. 시간 복잡도는 상태 준비 회로가 다항식 크기라면 $\text{poly}(n)$이다.
  • 이는 rank $r$에 의존했던 이전의 최선 결과[WGL+24]($\tilde{O}(r^{3+1/\{\alpha/2\}}/\epsilon^{4\alpha+\dots})$)에 비해 **지수적 가속(exponential speedup)**을 나타낸다.
  • 샘플 복잡도 또한 $\tilde{O}(1/\epsilon^{3\alpha+2+\dots})$로 개선되어 rank-independent하다.
• 고정된 $0 < \alpha < 1$에 대해: 효율적인 알고리즘이 쿼리 복잡도 $\tilde{O}(r^{2/(\alpha-1)}/\epsilon^{2/\alpha})$로 $\Lambda_\alpha(\rho_0, \rho_1)$를 추정한다. 이는 이전의 최선 경계인 $\tilde{O}(r^{5/\alpha}/\epsilon^{5/\alpha+1})$를 개선하지만 여전히 rank $r$에 의존한다.

2. 계산 복잡도 이분법

본 논문은 QSD$_\alpha$의 복잡도에서 날카로운 상전이를 확립한다:

• $\alpha > 1$ (고정 상수): QSD$_\alpha$는 BQP-complete이다. 이 문제는 양자 컴퓨터로 효율적으로 풀 수 있으며, 추정기는 rank-independent하다.
• $1 \leq \alpha(n) \leq 1 + \text{negl}(n)$: QSD$_\alpha$는 QSZK-complete이다. BQP = QSZK가 아닌 한 효율적인 양자 추정기는 존재할 수 없다.
• $0 < \alpha < 1$ (고정 상수): PoweredQSD$_\alpha$는 QSZK-hard이다.

3. 새로운 부등식

저자들은 트레이스 거리를 Schatten 노름 및 거듭제곱 거리와 연결하는 새로운 rank-dependent 부등식을 제공한다. 이 부등식들은 독립적인 관심사이며, 특히 "쉬운" 영역(순수 상태)이 $\alpha$가 1에 접근함에 따라 어떻게 "어려운" 영역(높은 rank를 가진 혼합 상태)으로 전이되는지를 보여주는 데 있어 핵심적이다.

의의

본 논문은 서론에서 제기된 일반적인 Schatten $\alpha$-노름에 대한 근접성 테스트(closeness testing)의 계산 복잡도에 관한 문제 1을 해결한다.

• 이는 $\ell_1$-유사 측정치에 대한 QSZK-hard성과 $\ell_2$-유사 측정치에 대한 BQP-포함성 사이의 이분법이 단순히 짝수와 홀수의 구분이 아니라, $\alpha=1$과 임의의 상수 $\alpha > 1$ 사이에서 발생하는 날카로운 전이임을 입증한다.
• Rank-independent 추정기의 개발은 중요한 기술적 진보로, 이전에는 상태의 rank에 대한 지식이나 의존성을 요구했던 양자 상태 속성 테스트의 주요 병목 현상을 제거하였다.
• 이 결과들은 양자 상태 구별 가능성의 지형을 명확히 하며, $T_\alpha$ ($\alpha > 1$인 경우)가 트레이스 거리에 대한 자연스러운 하한을 제공하면서도, 트레이스 거리 자체와 달리 임의의 고정된 $\alpha > 1$에 대해 효율적으로 계산 가능하다는 것을 보여준다.

저자들은 $\alpha = \infty$인 경우의 경우 문제가 여전히 열려 있다고 언급하며, 관련 약속 문제(promise problem)인 QSD$_\infty$는 BQP-hard이고 QMA에 포함되지만, BQP에 포함되는지는 현재 알려져 있지 않다고 밝힌다. 또한, 표 1의 정량적 경계값을 더 정밀하게 개선할 수 있는지에 대한 질문도 남겨두었다.