Quantum query complexity of Hurwitz stability testing

기술 요약: 허위츠 안정성 테스트의 양자 쿼리 복잡도

1. 문제 정식화

본 논문은 선형 동역학계 $\dot{x} = Ax$가 허위츠 안정(Hurwitz stable)한지 여부를 결정하는 근본적인 제어 이론 문제를 다룬다. 행렬 $A \in \mathbb{C}^{n \times n}$는 모든 고윳값이 개방된 좌반평면에 존재할 때 허위츠 안정하며, 이는 모든 궤적이 0으로 수렴함을 보장한다.

저자들은 블록 인코딩 액세스 모델(block-encoding access model) 하에서 이 결정 문제의 양자 쿼리 복잡도를 연구한다. 입력은 $A$의 정확한 정규화된 블록 인코딩인 $U_A$이다. 결정적으로, 알고리즘은 **허수축 거리(imaginary-axis distance)**에 대한 약속(promise) 또는 알려진 하한 $\nu > 0$ 하에서 작동한다:
$$\omega_A := \min_{t \in \mathbb{R}} \sigma_{\min}(A - itI)$$
여기서 $\sigma_{\min}$은 최소 특이값(smallest singular value)을 나타낸다. 조건 $\nu \le \omega_A$는 $A$가 허수축 상에 고윳값을 갖지 않음을 보장하며, 안정성을 위한 정량적 마진을 제공한다. 목표는 $U_A$와 그 수반 행렬(adjoint)에 대한 쿼리 횟수를 최소화하면서 $A$가 허위츠 안정인지 결정하는 것이다.

2. 방법론적 전략

저자들은 문제를 두 가지 주요 단계로 분해한다:

A. 스펙트럼 투영 제로-테스팅(Spectral Projector Zero-Testing)으로의 환원

안정성 조건은 행렬 부호 함수(matrix sign function)를 사용하여 재구성된다. 허수 고윳값이 없는 행렬 $A$에 대해, 행렬 부호 함수 $\text{sign}(A)$는 조르단 분해(Jordan decomposition)를 통해 정의된다. 저자들은 우반평면 불변 부분 공간(right-half-plane invariant subspace)으로의 스펙트럼 투영을 활용한다:
$$\text{sign}_+(A) := \frac{I + \text{sign}(A)}{2}$$
핵심적인 성질은 $A$가 허위츠 안정할 필요충분조건이 $\text{sign}_+(A) = 0$이라는 것이다. 따라서 문제는 특정 블록 인코딩된 아이뎀포텐트 행렬(idempotent matrix, 투영 행렬)이 영행렬인지 테스트하는 문제로 귀결된다.

B. 블록 인코딩된 아이뎀포텐트 행렬의 제로-테스팅

논문은 먼저 미지의 아이뎀포텐트 행렬 $P$ (단, $P^2=P$)가 0인지 테스트하기 위한 쿼리 복잡도를 확립한다. 이때 주어진 것은 $(\beta, b, \epsilon_+)$-블록 인코딩 $U_P$이다.

• 알고리즘: 알고리즘은 **진폭 추정(Amplitude Estimation)**을 사용한다. 최대 얽힘 상태(maximally entangled state)를 준비하고, 블록 인코딩을 적용한 뒤, 보조 큐비트(ancilla qubits)가 $|0\rangle$ 상태에 있을 확률을 측정한다. 이 확률은 투영된 행렬의 제곱 프로베니우스 노름(squared Frobenius norm)에 비례한다.
• 복잡도: 정규화 계수 $\beta$와 오차 $\epsilon_+ \le 1/(4\sqrt{n})$를 가진 투영 행렬에 대해, 알고리즘은 $\Theta(\beta\sqrt{n})$ 쿼리를 사용하여 $P=0$인지 일정한 성공 확률로 결정한다.

C. $A$로부터 투영 행렬 구성

$\text{sign}_+(A)$에 대한 제로-테스트를 적용하기 위해, 저자들은 $A$의 블록 인코딩으로부터 이 투영 행렬의 블록 인코딩을 구성해야 한다.

• 일반적인 경우 (비정규 행렬, Non-Normal): 구조화된 행렬 역행렬을 통해 구현된 **파데 근사(Padé approximation)**를 사용하여 $\text{sign}_+(A)$를 근사한다. 이 구성은 간극 $\nu$에 의존하는 정규화 계수 $\beta$를 도입한다.
• 정규/에르미트 행렬의 경우 (Normal/Hermitian): 정규 행렬의 경우, $\text{sign}_+(A)$가 노름이 1인 직교 투영(orthogonal projector)이므로 문제가 단순화된다. 이 구성은 $A$의 에르미트 부분에 대한 표준 유니터리 선형 결합(LCU) 기법을 활용한다.

3. 주요 결과 및 복잡도 경계

논문은 표 1에 요약된 바와 같이, 로그 인자를 제외하고 일치하는 상한 및 하한(matching upper and lower bounds)을 제공한다.

하한 (Lower Bound)

저자들은 $\Omega(\sqrt{n}/\nu)$의 근본적인 하한을 증명한다.

• 이 경계는 $A$가 **실수 대각 행렬(real diagonal matrix)**로 제한될 때도 성립한다.
• 이 증명은 약한 유니터리 오라클(weak unitary oracles)을 가진 탐색 문제로부터의 환원을 사용하며, 이를 통해 $\sqrt{n}$ 스케일링은 차원 때문에 필요하고, $1/\nu$ 스케일링은 스펙트럼 간극 때문에 필요함을 보여준다.

상한 (Upper Bounds)

상한은 행렬의 구조에 따라 달라진다:

1. 일반 행렬 (비정규 행렬):
   알고리즘은 다음의 쿼리 복잡도를 달성한다:
   $$O\left( \frac{\sqrt{n}}{\nu^2} \log\left(\frac{\sqrt{n}}{\nu}\right) \right)$$
   이 결과는 투영 근사를 구성하는 비용(scaling as $\nu^{-1} \log(\dots)$)과 제로-테스팅 비용(scaling as $\sqrt{n}$)의 결합에서 기인한다.

2. 정규 또는 에르미트 행렬:
   $AA^\dagger = A^\dagger A$를 만족하는 행렬의 경우, 복잡도는 다음과 같이 개선된다:
   $$O\left( \frac{\sqrt{n}}{\nu} \log n \right)$$
   이는 로그 인자 $\log n$을 제외하면 하한과 일치한다. 이러한 개선은 스펙트럼 투영이 노름 1인 직교 투영이기 때문이며, 일반적인 경우의 사선 투영(oblique projectors)과 관련된 추가적인 $\nu^{-1}$ 인자를 피할 수 있기 때문이다.

4. 의의 및 주장

논문의 기여와 의의는 다음과 같다:

• 정규 행렬에 대한 근사 최적성: 정규 행렬에 대해 차원 의존성($\sqrt{n}$)과 간극 의존성($1/\nu$)이 로그 인자를 제외하고 하한과 일치하므로 거의 최적임을 보여준다.
• 열린 간극(Open Gap)의 식별: 일반적인 비정규 행렬의 경우, 하한($\Omega(\sqrt{n}/\nu)$)과 상한($O(\sqrt{n}/\nu^2 \dots)$) 사이에 간극이 존재한다. 논문은 상한의 $1/\nu$ 인자를 "열린 컨디셔닝 간극(open conditioning gap)"으로 식별하였다. 이 의존성이 필수적인 것인지, 아니면 현재의 구성 방법의 산물인지는 아직 알려지지 않았다.
• 균일성(Uniformity): 기존의 고윳값 추정 방식이 상태 준비 중첩(state preparation overlap)이나 특정 조르단 블록 구조에 의존하는 것과 달리, 이 경계들은 $\nu$-간극 약속을 만족하는 행렬 클래스 전반에 걸쳐 균일하다.
• 강건성(Robustness): 결과는 임의의 행렬(비대각화 가능 행렬 포함)에 대해 유효하며, 단 허수축 거리가 0에서 멀리 떨어져 있어야 한다.

저자들은 행렬 부호 구성에 사용된 파데 근사가 그 자체로 새로운 것은 아니지만, 이 구성을 진폭 추정과 결합하여 이러한 구체적인 쿼리 경계를 도출한 것이 주요 기여임을 명시한다. 저자들은 비정규 행렬에 대한 컨디셔닝 간극을 해결했다고 주장하지 않으며, 이를 향후 연구 과제로 남겨두었다.