Learning quantum Hamiltonians at any temperature in polynomial time

이 논문은 새로운 평탄 다항식 근사와 합제곱 완화 기법을 활용하여 임의의 상수 역온도 $\beta > 0$에서 깁스 상태의 다항식 개 복본으로부터 $\epsilon$ 정밀도로 국소 양자 해밀토니안을 학습하는 다항 시간 알고리즘을 제시함으로써 주요 미해결 문제를 해결한다.

핵심

"임의의 온도에서 다항 시간 안에 양자 해밀토니안을 학습한다"는 논문에 대한 설명을 일상적인 언어와 비유를 사용하여 번역한 것입니다.

전체적인 그림: 양자 기계의 역공학

마치 거대하고 보이지 않는 양자 입자로 이루어진 시계 장치처럼, 수많은 미세한 상호작용 부품으로 구성된 신비롭고 복잡한 기계가 있다고 상상해 보세요. 당신은 기계의 내부를 볼 수 없으며, 기어들이 어떻게 연결되어 있고 스프링의 강도가 얼마나 되는지 알지 못합니다.

하지만 기계가 "휴식"하거나 "차분한" 상태일 때 (물리학자들이 깁스 상태라고 부르는 상태) 이를 관찰할 수 있습니다. 당신은 이 휴식 상태의 수많은 스냅샷을 찍을 수 있습니다.

목표: 당신의 임무는 기계의 정확한 설계도를 찾아내는 것입니다. 구체적으로 말하면, 모든 스프링과 기어 연결의 강도 (이를 상호작용 강도 또는 계수라고 함) 를 파악하는 것입니다. 물리학에서 이 설계도를 해밀토니안이라고 부릅니다.

문제: "차가운" 함정

오랫동안 과학자들은 이 설계도를 알아내는 방법을 가지고 있었지만, 이는 기계가 뜨거울 때만 작동했습니다. 뜨거울 때 입자들은 혼란스럽게 움직이며 연결고리가 쉽게 드러납니다. 마치 실뭉치를 격렬하게 흔들면 엉킨 실 한 올 한 올을 볼 수 있는 것과 비슷합니다.

하지만 기계가 차갑게 식었을 때 (초전도 현상과 같은 가장 흥미로운 양자 마법이 일어나는 곳) 입자들은 가라앉아 매우 특이하고 경직된 패턴에 고정됩니다.

• 과거의 문제: 이 "차가운" 상태에서 설계도를 역공학으로 알아내려는 이전 방법들은 이론적으로는 가능했지만 실제로는 불가능했습니다. 이는 우주의 나이보다 더 오래 걸릴 컴퓨터 시간을 필요로 하는 퍼즐을 풀려는 것과 같았습니다. 차가운 상태를 해독하는 데 필요한 수학은 너무 무거웠습니다.

돌파구: 새로운 종류의 "번역기"

이 논문은 기계가 얼어붙을 정도로 차갑더라도 이 퍼즐을 빠르게 ("다항 시간" 안에) 풀 수 있는 새로운 알고리즘을 제시합니다.

다음은 그들이 사용한 세 가지 주요 트릭입니다.

1. "평탄한" 근사 (곡선 매끄럽게 하기)

기계를 이해하려면 지수 함수라는 특정 수학 곡선을 이해해야 합니다. 이 곡선을 가파르고 톱니처럼 날카로운 산으로 상상해 보세요.

• 과거의 방법: 이전 방법들은 이 산을 작은 평평한 블록 (다항식) 을 서로 쌓아 올려 근사하려 했습니다. 하지만 차가운 상태에서 정확히 맞추려면 너무 많은 블록이 필요했고, 그 결과 쌓인 더미는 불가능할 정도로 높고 불안정해졌습니다.
• 새로운 방법: 저자들은 새로운 유형의 "평탄한" 근사를 고안했습니다. 블록을 쌓는 대신, 산의 중간 부분은 완벽하게 감싸지만 가장자리에서는 부드럽게 떨어지도록 허용된 유연하고 늘어나는 시트를 사용한다고 상상해 보세요. 이 "평탄한" 시트는 다루기 훨씬 쉽고 계산의 무게 아래서 무너지지 않습니다.

2. "중첩 교환자" 번역기

양자 역학의 수학에는 교환자라는 것이 포함되는데, 이는 "순서가 중요하다"는 게임과 같습니다. 기어를 왼쪽으로 밀었다가 오른쪽으로 밀면, 오른쪽으로 밀었다가 왼쪽으로 밀는 것과 다릅니다.

• 번역: 저자들은 이러한 복잡한 "순서가 중요하다"는 양자 규칙을 간단한 다항식 (기본 대수 방정식) 으로 번역하는 사전 (사전을 의미하는 번역기) 을 만들었습니다.
• 도움되는 이유: 양자 규칙을 간단한 대수로 번역한 후, 그들은 전체 문제를 고등학교에서 풀 수 있는 방정식 체계처럼 다룰 수 있게 되었고, 무서운 양자 미스터리가 아닌 것입니다.

3. "SOS" 탐정 (제곱의 합)

이제 대수 방정식 체계가 갖춰졌으니, 이를 풀어야 합니다.

• 방법: 그들은 제곱의 합 (Sum-of-Squares, SoS) 이라는 강력한 수학 도구를 사용했습니다. 이는 하나의 해만 찾는 것이 아니라, "오차의 제곱"을 살펴봄으로써 어떤 해가 가능한지 확인하는 초지능 탐정이라고 생각하세요.
• 결과: 이 탐정은 "평탄한" 근사와 대수적 규칙에 부합하는 해를 찾으면, 그것이 기계의 올바른 설계도여야만 있음을 증명했습니다. 시스템을 속일 수 있는 다른 가짜 설계도는 존재하지 않습니다.

해법의 "레시피"

1. 스냅샷 촬영: 알고리즘은 양자 기계의 휴식 상태 사본을 여러 개 취합니다.
2. 단서 측정: 특정 상호작용을 측정합니다 (예: 두 개의 특정 기어가 어떻게 함께 움직이는지 확인).
3. 퍼즐 구성: 새로운 "평탄한" 근사를 사용하여 수학을 관리 가능하게 유지하면서, 그 측정값을 기반으로 거대한 대수 방정식 체계를 구축합니다.
4. 퍼즐 해결: 제곱의 합 (SoS) 탐정을 사용하여 방정식을 풉니다.
5. 설계도 획득: 해답은 기계 내의 모든 상호작용의 정확한 강도를 제공합니다.

왜 이것이 중요한가 (논문에 따르면)

이 논문은 이것이 주요 돌파구라고 주장합니다. 그 이유는 다음과 같습니다.

• 임의의 온도에서 작동: 뜨겁고 차가운 상태 모두에 대한 문제를 해결하여, 오랫동안 연구자들을 괴롭혔던 "저온" 코드를 마침내 해독했습니다.
• 빠름: 이전 시도들은 영원히 걸릴 것 같았지만, 이는 합리적인 시간 안에 실행됩니다.
• 엄밀함: 그들은 단순히 추측한 것이 아니라, 그들의 방법이 작동하고 해답이 유일함을 수학적으로 증명했습니다.

요약하자면, 그들은 양자 기계의 비밀 설계도를 읽을 수 있는 빠르고 신뢰할 수 있는 해독 고리를 만들었습니다. 그 기계가 얼마나 차갑고 조용하든 상관없이 말입니다.

기술 요약

기술 요약: 임의 온도에서 다항 시간 내 국소 양자 해밀토니안 학습

문제 정의
본 논문은 국소 양자 시스템에 대한 해밀토니안 학습 문제를 다룹니다. 국소 해밀토니안 $H = \sum_{a=1}^m \lambda_a E_a$ 로 기술된 $n$ 개의 큐비트 시스템이 주어졌을 때, 여기서 상호작용 항 $E_a$ 는 경계된 국소성을 가진 잘 알려진 서로 다른 항등원이 아닌 파울리 연산자이며, 계수 $\lambda_a$ 는 $[-1, 1]$ 범위의 미지의 상호작용 세기입니다. 목표는 $\lambda_a$ 를 추정하는 것입니다. 알고리즘은 알려진 역온도 $\beta > 0$ 에서 깁스 상태 $\rho = e^{-\beta H} / \text{tr}(e^{-\beta H})$ 의 사본들에 접근할 수 있습니다. 목표는 시스템 크기 $n$(및 항의 개수 $m$) 과 $1/\epsilon$ 에 대해 다항식인 샘플 수와 실행 시간을 사용하여 모든 $a$ 에 대해 $|\hat{\lambda}_a - \lambda_a| \leq \epsilon$ 이 되도록 $\hat{\lambda}_a$ 추정을 출력하는 것입니다.

이 작업 이전에는 다항식 샘플 복잡도 상한이 알려져 있었으나 [AAKS20], 이에 상응하는 계산 알고리즘은 일반적인 저온 영역에서 비효율적 (지수 시간) 이었습니다. 효율적인 알고리즘은 고온 (작은 $\beta$) [HKT22] 이나 교환하는 해밀토니안 항 [AAKS21] 에 대해서만 존재했습니다. 핵심 열린 질문은 저온 (큰 $\beta$) 에서의 해밀토니안 학습이 $n$ 에 대해 다항식 시간 내에 해결될 수 있는지 여부였습니다.

방법론
저자들은 합계-제곱 (Sum-of-Squares, SoS) 계층 구조에 기반한 계산적으로 효율적인 알고리즘을 제안합니다. 핵심 기술 전략은 다음 세 가지 주요 구성 요소를 포함합니다:

1. 다항식 제약 시스템 구성:
   매개변수에서 국소 주변분포로의 매핑을 직접 역전시키는 것 (계산적으로 어렵습니다) 대신, 저자들은 참된 매개변수가 만족해야 하는 제약 시스템을 정의합니다. 이 시스템에는 다음이 포함됩니다:

   • 매개변수 범위: $-1 \leq \lambda'_a \leq 1$.
   • 교환자 제약: 후보 해밀토니안 $H'$ 이 깁스 상태 $\rho$ 와 교환됨을 보장 (즉, $[H', \rho] \approx 0$).
   • "평탄한" (flat) 다항식 제약: 행렬 지수함수 $e^{-\beta H'}$ 를 국소 관측가능량에 작용하는 저차수 다항식 근사 $p(H' | P)$ 로 대체합니다. 구체적으로, 국소 파울리 연산자 $P, Q$ 에 대해 기댓값 $\text{tr}(Q e^{-\beta H'} P e^{\beta H'} \rho)$ 가 $\text{tr}(PQ\rho)$ 에 가깝도록 강제합니다.

2. 지수함수의 평탄한 다항식 근사:
   주요 기술적 난제는 $e^{-\beta x}$ 의 표준 테일러 급수 근사가 근사 구간 외부에서 너무 빠르게 증가하여, 고유값 차이가 클 수 있는 저온 영역에는 적합하지 않다는 점입니다. 저자들은 새로운 "평탄한" 다항식 근사 $p(x)$ 를 구성합니다:

   • 구간 $[-1, 1]$ 에서 $e^{-\beta x}$ 를 잘 근사합니다.
   • 이 구간 밖에서는 통제된 느린 지수 증가율 ($e^{\eta \beta |x|}$) 로 증가합니다.
     이 구성은 Lieb-Robinson 경계에서 사용되는 반복적 "박리" (peeling) 기법에 영감을 받았습니다. 이를 통해 제약 조건 내의 행렬 지수함수를 미지수 $\lambda'_a$ 에 대한 저차수 다항식으로 대체할 수 있습니다.

3. 다항식과 중첩 교환자 간의 변환:
   저자들은 다변수 스칼라 다항식과 연산자의 중첩 교환자 간의 형식적 변환을 확립합니다. 하마르드 (Hadamard) 공식을 사용하여 $e^{-\beta H'} P e^{\beta H'}$ 와 같은 항이 $H'$ 의 고유값에 대한 다항식으로 표현될 수 있음을 보이며, 이는 중첩 교환자 $[H', P]_\ell$ 에 해당합니다. 연산자가 국소적이라면 스칼라 영역의 다항식 항등식이 작은 오차 항을 제외하고 중첩 교환자를 포함하는 항등식으로 변환됨을 증명합니다.

4. 합계-제곱 완화와 식별 가능성:
   결과적으로 생성된 제약 시스템은 저차수 다항식 부등식의 집합입니다. 저자들은 이를 Semi-Definite Program (SDP) 으로 공식화할 수 있는 차수-$d$ 합계-제곱 (SoS) 완화를 사용하여 풉니다.

   • 실현 가능성: 참된 매개변수가 (샘플링 노이즈까지) 시스템을 만족함을 증명합니다.
   • 식별 가능성: 시스템의 모든 해가 참된 매개변수에 가까워야 함을 보여주는 SoS 증명을 제공합니다. 이는 "증명에서 알고리즘으로" 철학에 의존합니다. 중요한 단계는 깁스 상태 하에서 국소 연산자의 분산이 0 에서 멀리 떨어져 있음을 보이는 것으로, 이는 고전적 그래픽 모델의 속성에 대한 양자 유사체이며 매개변수의 식별 가능성을 보장합니다.
   • 효율성: SoS 증명의 특정 구조를 분석함으로써, 희소한 단항식 부분 집합만 필요함을 보여 SDP 를 $m$ 과 $1/\epsilon$ 에 대해 다항식 시간 (차수에서 $\beta$ 에 대한 지수 의존성은 있지만 $n$ 에 대해서는 다항식) 에 해결할 수 있음을 보입니다.

주요 결과
본 논문은 정리 1.1을 제시하며, 이는 임의의 상수 역온도 $\beta > 0$(특히 어떤 보편적 상수에 대해 $\beta \geq \beta_c$) 에 대해 확률 $99/100$ 으로 정밀도 $\epsilon$ 까지 해밀토니안 계수를 학습하는 알고리즘이 존재한다고 명시합니다.

• 샘플 복잡도: $n \geq \text{poly}(m, (1/\epsilon)^{2O(\beta)})$.
• 실행 시간: $n^{O(1)}$(구체적으로 $\text{poly}(m, \log(1/\delta)) \cdot (1/\epsilon)^{2O(\beta)}$).

이 알고리즘은 격자 위의 기하학적 국소 해밀토니안과 확장자 그래프 위에 정의된 해밀토니안을 포함하는 "저-교차" (low-intersection) 해밀토니안 클래스에서 작동합니다.

의의와 주장
저자들은 저온에서의 효율적인 해밀토니안 학습에 대한 열린 문제를 완전히 해결했다고 주장합니다.

• 열린 문제의 해결: 이 결과는 저온 해밀토니안 학습이 다항식 시간 내에 해결 가능한지에 대한 질문에 긍정적 답변을 제공합니다 [AAKS20; HKT22; Alh23; AA23]. 또한 저온 깁스 상태가 의사난수일 수 있다는 가설 [AA23 의 질문 3] 에는 부정적 답변을, 근사 조건부 독립 하에서 학습이 가능한지에 대한 질문 [AA23 의 질문 2] 에는 긍정적 답변을 제공합니다.
• 알고리즘적 도구: 이 작업은 최적화 이론의 정교한 도구, 특히 합계-제곱 계층 구조가 파티션 함수 계산의 어려움으로 인해 이전에는 해결 불가능해 보였던 양자 다체 학습의 장벽을 극복할 수 있음을 보여줍니다.
• 고전적 한계와의 독립성: 저자들은 고전적 해밀토니안 학습 (무방향 그래픽 모델 학습) 은 $\beta$ 에 대해 지수 시간이 필요하지만, 양자 설정은 양자 시스템의 비교환성과 비국소성에도 불구하고 반드시 이러한 어려움을 물려받지는 않는다고 지적합니다.
• 실용성: 논문은 알고리즘이 이론적으로 효율적 ($n$ 에 대해 다항식) 이지만, 실행 시간과 샘플 복잡도의 지수 내 $\beta$ 의존성으로 인해 현재 매우 낮은 온도나 대규모 시스템에는 실용적이지 않음을 인정합니다. 그러나 이전에는 존재하지 않았던 이론적 가능성을 확립합니다.

본 논문은 새로운 실험 설정이나 즉각적인 실용적 응용을 제안하지는 않지만, 특히 저온 영역에서 작동하는 아날로그 양자 시뮬레이터의 검증에 특히 관련이 있는 양자 시스템 특성화의 계산 복잡성을 이해하는 데 있어 근본적인 진전으로 결과를 제시합니다.