기술 요약: 최적의 트레이스 거리 추정을 통한 연산자 노름 거리 추정

문제 정의

본 논문은 두 $n$-큐비트 양자 상태 $\rho_0$와 $\rho_1$ 사이의 연산자 노름 거리(operator norm distance) $T_\infty(\rho_0, \rho_1)$를 추정하는 계산 복잡도를 조사한다. 이 거리는 $T_\infty(\rho_0, \rho_1) := \frac{1}{2}\|\rho_0 - \rho_1\|_\infty$로 정의된다. 여기서 $\|\cdot\|_\infty$는 연산자 노름(가장 큰 특잇값)을 의미한다.

상태들은 다항식 크기의 상태 준비 회로(state-preparation circuits) $Q_0$와 $Q_1$를 통해 제공된다. 목표는 쿼리 복잡도가 상태의 계수(rank)(따라서 차원 $d=2^n$)에 의존하지 않으면서, 가법 오차(additive error) $\epsilon$ 내에서 이 거리를 추정하는 양자 알고리즘을 설계하는 것이다. 이는 $\alpha > 1$인 클래식 $\ell_\alpha$ 거리에서 나타나는 결과와 유사하게, 연산자 노름 거리에 대해 계수 독립적인 경계가 존재하는지에 대한 미해결 문제를 다룬다.

방법론

저자들은 유니터리 확장(unitary dilation), 큐비타이제이션(qubitization), 그리고 **최대 위상 추정(maximum phase estimation)**을 결 조합한 프레임워크를 사용한다. 핵심 전략은 헐미션 연산자 $\Delta = (\rho_0 - \rho_1)/2$의 고윳값을 유니터리 연산자의 고유 위상(eigenphases)으로 매핑하여, 양자 위상 추정 기법을 통해 효율적으로 추정하는 것이다.

1. 유니터리 확장 및 큐비타이제이션

상태 준비 회로 $Q_0, Q_1$이 주어졌을 때, 저자들은 선형 결합 유니터리(Linear Combination of Unitaries, LCU) 기법과 순수화된 밀도 행렬(purified density matrix) 방법을 사용하여 $\Delta$의 유니터리 확장 $U_\Delta$를 구성한다.

• 저자들은 큐비타이제이션 유니터리 $W = U R U^\dagger R$ (여기서 $R$은 반사 연산자)를 정의한다.
• 이 구성은 $\Delta$의 고윳값 $\lambda$와 $W$의 고유 위상 $\theta$ 사이에 단조적인 대응 관계를 생성한다: 구체적으로 $\theta = 2 \arccos(\lambda)$ (전역 위상 제외).
• 따라서 $\|\Delta\|_\infty$(최대 고윳값 크기)를 추정하는 문제는 $W$의 **최대 고유 위상(maximum eigenphase)**을 추정하는 문제로 환원된다.

2. "웜 스타트(Warm Start)" 전략

위상 추정에서 중요한 과제는 입력 상태가 타겟 고유 공간(즉, $\Delta$의 최상위 고유 공간)과 무시할 수 없는 중첩(overlap)을 갖도록 보장하는 것이다. 본 논문은 입력 상태의 순도에 따라 두 가지 경우를 구분한다.

• 경우 1: 한 상태가 순수 상태(Pure State)인 경우 (Warm Start Lemma)
  한 상태(예를 들어 $\rho_0 = |\psi\rangle\langle\psi|$)가 순수할 때, 저자들은 구조적 정리(Lemma 3.1)를 증명한다. 그들은 순수 상태 $|\psi\rangle$ 자체가 $\Delta$의 가장 큰 양의 고윳값에 대응하는 유일한 고유 벡터와 적어도 $1/2$ 이상의 제곱 중첩을 가짐을 보여준다.

  • 직관: $\rho$는 양의 준정부호(positive semidefinite)이므로, $|\psi\rangle$에 직교하는 부분 공간에 대한 $\Delta$의 제한은 음의 준정부호이다. 따라서 양의 고윳값은 $|\psi\rangle$와 상당한 중첩을 갖는 고유 벡터에 대응해야 한다.
  • 이러한 "웜 스타트" 덕분에 최대 위상 추정을 상수 중첩 파라미터 $\gamma = 1/2$와 함께 사용할 수 있다.

• 경우 2: 일반 혼합 상태(General Mixed States) (고윳값 스케일링 중첩)
  두 상태가 모두 혼합 상태일 때는 상수 중첩이 보장되지 않는다. 저자들은 입력 상태의 순수화된 상태와 최상위 고유 공간 사이의 중첩이 타겟 고윳값에 따라 스케일링됨을 보여주는 더 약한 경계(Lemma 4.1)를 도출한다: $\|\Pi_{\max} |\psi_0\rangle\|^2 \ge 2\lambda_{\max}(\Delta)$.

  • 목표 거리가 $\epsilon$이므로, 중첩은 대략 $O(\epsilon)$이다.
  • 이를 보완하기 위해 알고리즘은 진폭 증폭(amplitude amplification)(암묵적으로 최대 위상 추정 루틴의 파라미터를 통해 수행)을 사용하여 성공 확률을 상수로 높인다.

주요 기여 및 결과

1. 하나의 순수 상태에 대한 최적 추정

정리 1.1: 한 상태가 순수할 때, $T_\infty(\rho, |\psi\rangle\langle\psi|)$ 또는 트레이스 거리 $T(\rho, |\psi\rangle\langle\psi|)$를 가법 오차 $\epsilon$ 내에서 추정하기 위한 양자 쿼리 복잡도는 $\Theta(1/\epsilon)$이다.

• 의의: 이는 순수-대-순수(pure-vs-pure) 케이스의 최적 경계와 일치한다. 결정적으로, 이 복잡도는 **계수 독립적(rank-independent)**이다. 기존의 접근 방식들(예: van Apeldoorn 등, Wang 및 Zhang)은 계수 $r$에 선형적으로 스케일링되는 쿼리 복잡도(잠재적으로 $O(2^n)$)를 가졌던 반면, 이 방법은 상수 $\epsilon$에 대해 $\text{poly}(n)$ 시간 내에 실행된다.
• 샘플 복잡도: 샘플-투-쿼리 리프팅(sample-to-query lifting)을 통해 샘플 복잡도는 $\Theta(1/\epsilon^2)$이다.

2. 일반 상태에 대한 효율적 추정

정리 1.2: 일반적인 양자 상태 $\rho_0, \rho_1$에 대하여, $T_\infty(\rho_0, \rho_1)$를 $\tilde{O}(1/\epsilon^{3/2})$의 쿼리 복잡도로 추정하는 양자 알고리즘이 존재한다.

• 의의: 이는 $\ell_\alpha$ 거리($\alpha > 1$)에 대한 기존의 최선 상한($O(1/\epsilon^{\alpha+1})$ 또는 그보다 나쁜 수준)을 개선한 것이다. 이는 알려진 하한인 $\Omega(1/\epsilon)$과 제곱근 차이만을 남겨두고 있다.
• 샘플 복잡도: 샘플 복잡도는 $\tilde{O}(1/\epsilon^3)$이다.

3. 복잡도 클래스 결과

본 논문은 약속 문제(promise problem) QSD$_\infty$($T_\infty \ge 2/5$ 또는 $\le 1/5$를 테스트)의 계산 복잡도를 확립한다.

• 따름정리 1.3: QSD$_\infty$는 **BQP-완전(BQP-complete)**이다.
• 따름정리 1.4: 제한된 변형인 OnePureQSD$_\alpha$(적어도 하나의 상태가 순수함)는 모든 $\alpha \in [1, \infty]$에 대해 BQP-완전이다.
• 이러한 결과들은 기존의 QMA 상한을 개선하며, 연산자 노름 거리를 추정하는 것이 양자 증거(quantum witness) 없이도 양자 컴퓨터에서 효율적으로 해결 가능하다는 것을 확인시켜 준다.

의의 및 주장

본 논문은 연산자 노름 거리 추정의 계수 독립성에 관한 오랜 미해결 문제를 해결했다고 주장한다.

• 구조적 통찰: 저자들은 연산자 노름 거리의 특정 구조적 특징을 강조한다. 즉, 한 상태가 순수할 때, 그 순수 상태는 차이 연산자의 최상위 고유 공간을 위한 "웜 스타트" 역할을 한다는 점이다. 이는 일반적인 혼합 상태에서는 성립하지 않는 계수-1 섭동(rank-one perturbation) 현상이다.
• 효율성: 제안된 추정기들은 차원 $d=2^n$에 따라 스케일링되는 상태 토모그래피 기반 접근 방식에 비해 지수적 가속을 제공하며, 기존의 계수 의존적 추정기들에 비해 다항식 가속을 제공한다.
• 계층적 맥락: 이 결과들은 연산자 노름 거리($\alpha = \infty$)가 $\ell_\alpha$ 계층 구조에서 가장 완화된 근접성 개념임에도 불구하고, 쿼리 복잡도 측면에서는 $\alpha=2$나 $\alpha=3$ 같은 중간 단계의 경우보다 오히려 "가장 쉬운" 경우임을 시사한다.

논문은 일반 혼합 상태의 경우 상한($\tilde{O}(1/\epsilon^{3/2})$)과 하한($\Omega(1/\epsilon)$) 사이에 제곱근 차이가 여전히 남아 있으며, 이 상한의 최적성을 밝히는 것이 향후 과제로 남아 있다고 결론짓는다.