Quantum power iterations via tensor networks

기술 요약: 텐서 네트워크를 통한 양자 거듭제곱 반복법 (Quantum Power Iterations via Tensor Networks)

문제 정의
거듭제곱 반복법(Power iteration)은 대각화 가능한 행렬의 지배적 고유벡터(dominant eigenvector)를 찾기 위해 사용되는 고전적 알고리즘으로, 이는 최적화 문제 중 고유값 탐색으로 정식화된 많은 문제의 핵심이다. 이 알고리즘은 행렬과 벡터를 반복적으로 곱하고(MatVec) 정규화하는 방식으로 작동한다. 이를 고전적 텐서 네트워크(특히 MPS 및 MPO)를 사용하여 구현할 경우, 텐서 랭크가 반복 횟수에 따라 지수적으로 증가하는 스케일링 병목 현상에 직면하게 된다. 즉, 최악의 경우 깊은 반복을 수행하는 것은 불가능해진다. 양자 컴퓨터는 랭크와 상관없이 자연스럽게 유니터리 연산을 수행하지만, 거듭제곱 반복법에서 사용되는 대각 행렬(비유니터리 연산자)을 인코딩하고, 지수적인 고전적 오버헤드 없이 발생하는 랭크 증가를 관리하는 것은 여전히 과제로 남아 있다.

방법론
저자들은 저차원(low-rank) 텐서 네트워크 표현을 양자 회로로 투영함으로써 고전적 랭크 증가의 병목 현상을 우회하는 양자 거듭제곱 반복법을 제안한다. 방법론은 다음과 같다:

1. 인코딩: 대상 함수 $f(x)$를 이산화하여 MPS로 표현한다. 그에 대응하는 대각 연산자 $H$는 MPO로 표현된다.
2. 변분적 유니터리 근사 (Variational Unitary Approximation): 양자 회로는 유니터리 진화를 요구하므로, 비유니터리 대상 MPO($H_{mpo}$)를 "유니터리 MPO" 안사츠($U_{mpo}$)로 근사한다. 이는 MPO의 텐서 코어를 유니터리 행렬로 제한함으로써 달성된다.
   • 비유니터리 대상을 수용하기 위해, 저자들은 보조 큐비트(ancillary qubits)를 도입한다. MPO의 가상 본드(virtual bonds)는 보조 공간으로 해석된다.
   • 리만 최적화(Riemannian optimization)를 사용하여 대상 $H_{mpo}$와 스케일링된 유니터리 근사 $c \cdot \tilde{U}$ 사이의 프로베니우스 거리(Frobenius distance)를 최소화하는 변분 탐색을 수행한다. 여기서 $\tilde{U}$는 초기화 및 보조 큐비트의 사후 선택(post-selection)을 통해 얻은 유효 선형 연산자이다.
3. 회로 구현: 최적화된 유니터리 MPO는 양자 회로로 컴파일된다. 단일 거듭제곱 반복은 초기 상태(준비된 $|+\rangle^{\otimes n} \otimes |0\rangle^{\otimes n_a}$)에 이 회로 블록을 적용하고, 보조 큐비트를 모든 0 상태로 사후 선택함으로써 실현된다.
4. 반복: $p$번의 반복을 수행하기 위해, 회로 블록을 $p$번 연결하며, 각 단계마다 새로운 보조 큐비트를 초기화한다. 과정은 시스템 큐비트를 측정함으로써 종료되며, 가장 높은 확률을 가진 비트 문자열이 후보 최적값이 된다.

주요 기여 정

• 양자 거듭제곱 반복법의 공식화: 본 논문은 정적인 회로 블록과 사후 선택을 사용하여 양자 하드웨어에서 거듭제곱 반복을 실행하는 프레임워크를 구축함으로써, 동일한 과정을 수행하는 고전적 텐서 네트워크 시뮬레이션에서 발생하는 지수적 랭크 증가를 피한다.
• 변분적 유니터리 MPO 구축: 저자들은 임의의 대각 MPO를 리만 최적화와 교차 근사(cross-approximation) 기술을 사용하여 유니터리 MPO로 변분적으로 근사하는 방법을 도입하였으며, 이를 통해 방식이 인스턴스에 구애받지 않고 블랙박스 최적화에 적합하도록 만들었다.
• 확장성 분석: 연구 결과, 고전적 텐서 네트워크의 랭크는 반복에 따라 지수적으로 증가하는 반면, 양자 회로의 깊이는 큐비트 수($n$), 반복 횟수($p$), 안사츠 랭크($R$)에 대해 다항식 수준으로만 증가함을 보여준다. 그러나 저자들은 이러한 다항식 깊이가 전체적인 확장성을 보장하지는 않는다고 명시했는데, 이는 일반적인 경우 사후 선택 확률이 반복 횟수($p$)에 따라 지수적으로 감소하기 때문이다.
• 성공을 위한 임계 조건: 본 연구는 방법론이 신뢰성 있게 작동하는 조건을 명시적으로 식별하였다. 성공 여부는 단순히 전역 피팅 오차(global fitting error)가 아니라, 목적 함수의 가장 큰 값과 두 번째로 큰 값 사이의 상대적 간격(relative gap)을 보존하는지에 달려 있음을 강조한다.

결과
저자들은 여러 최적화 벤치마크를 통해 방법론을 검증했다:

• 사인 함수 (Sine Function): 해석적으로 도출된 유니터리 MPO를 구성했다. 양자 거듭제곱 반복은 전역 최댓값으로 성공적으로 수렴했으며, 측정 확률은 이론적 기대치와 일치했다.
• 애클리 함수 (Ackley Function, 2D 및 4D): 이 방법은 2D 및 4D 인스턴스 모두에서 전역 최솟값을 성공적으로 찾아냈다. 저자들은 랭크가 부족한 유니터리 MPO(전역 피팅 오차가 무시할 수 없는 수준인 경우)에서도, 근사가 상위 함수 값들의 순서를 보존한다면(즉, 간격이 근사 오차보다 크다면) 방법이 성공함을 입증했다.
• 로젠브록 함수 (Rosenbrock Function, 2D): 방법은 "바나나 모양"의 골짜기로는 수렴했으나, 이산화된 정확한 전역 최적값을 식별하는 데는 실패했다. 저자들은 이를 변환된 목적 함수의 극단적인 평탄함 때문으로 보았는데, 즉 최적값과 그다음 차순위 그리드 포인트 사이의 상대적 간격이 근사 오차보다 작아 회로가 진정한 최댓값을 구별하지 못한 것이다.
• 스케일 인자 최적화: 변분 탐사에서 스케일 인자 $c$를 대상의 연산자 노름(operator norm)으로 제한($c = \|H_{mpo}\|_2$)하는 것이, 애클리 벤치마크의 정확도를 희생하지 않으면서도 사후 선택 확률을 (수 차례의 오더만큼) 획기적으로 개선한다는 중요한 발견을 했다.

의의 및 주장
본 논문은 검토된 특정 사례들에 대해 고전적 텐서 네트워크 최적화 대비 엔드 투 엔드(end-to-end) 계산 우위를 입증한 것이 아님을 명시적으로 밝힌다. 검토된 사례들(매끄러운 저차원 벤치마크)에서는 고전적 텐서 네트워크에서 랭크 폭발이 발생하지 않았으므로, 양자 접근 방식이 실행 시간 측면에서 이점을 제공하지 않았다.

대신, 이 연구의 의의는 다음과 같다:

1. 구축 확립: 텐서 네트워크 개념을 사용하여 양자 하드웨어에서 거듭제곱 반복을 구현할 수 있는 실행 가능한 경로를 제공한다.
2. 열린 질문 식별: 핵심적인 열린 질문은 다음 네 가지 조건을 동시에 만족하는 문제군을 찾는 것임을 강조한다: (i) 정확한 저차원 MPS/MPO 근사를 허용하고, (ii) 작은 오차를 가진 유니터리 MPO로 인코딩이 가능하며, (iii) 수용 가능한 사후 선택 확률을 유지하고, (iv) 중간 반복 단계들이 정확한 저차원 고전적 근사를 허용하지 않는 것(고전적 랭크 폭발을 유발하는 조건).
3. 블랙박스 잠재력: 이 방법은 함수에 구애받지 않으므로, 특정 간격 및 오차 조건을 충족하는 저차원 텐서 표현을 허용하는 함수들에 대한 블랙박스 최적화 가능성을 시사한다.

저자들은 회로당 자원은 다항식으로 스케일링되지만, 전체적인 확장성은 현재 인스턴스 의존적인 사후 선택 확률(반복에 따라 지수적으로 감소함)과 최적값을 해상하기 위해 필요한 측정 횟수(둘 다 일반적으로 다항식이 아님)에 의해 제한된다고 결론지었다.