Many Hamiltonians Are Sparsifiable

본 논문은 파울리 스트링과 고차 연산자로 구성된 것을 포함하여 다양한 $r$-국소 해밀토니안이 스펙트럼 성질을 유지하면서 훨씬 적은 항으로 강건하게 희소화될 수 있음을 보여줌으로써 기존의 신념에 도전하고 양자 Max-Cut 과 같은 문제에 대한 개선된 준스트리밍 알고리즘을 가능하게 한다고 주장한다.

핵심

거대한 양자 케이크를 위한 방대하고 극도로 복잡한 레시피가 있다고 상상해 보세요. 이 레시피는 단순히 재료 목록이 아니라, 케이크의 서로 다른 부분들이 어떻게 상호작용하는지 알려주는 수천 개의 구체적인 지시사항 (항이라고 불림) 의 집합입니다. 이 케이크를 굽고 싶다면 모든 지시사항을 따라야 합니다. 하지만 지시사항의 99% 를 버려도 여전히 똑같은 맛의 케이크가 나온다면 어떨까요?

이것이 바로 이 논문에서 다루는 **해밀토니안 희소화 (Hamiltonian Sparsification)**의 핵심 아이디어입니다.

양자 물리학 세계에서 '해밀토니안'은 양자 시스템 (예: 큐비트 그룹) 이 어떻게 행동하고 얼마나 많은 에너지를 가지는지 설명하는 수학적 규칙책입니다. 보통 이러한 규칙책들은 수백만 개의 항을 포함하는 거대한 규모를 가집니다. 이 논문의 저자들은 다음과 같이 묻습니다: 시스템의 물리 법칙을 바꾸지 않고도 이러한 규칙책을 작고 관리 가능한 크기로 줄일 수 있을까요?

큰 놀라움: 많은 시스템에서 가능합니다!

오랫동안 과학자들은 답이 "아니오"라고 믿었습니다. 이전 연구에 따르면 많은 양자 시스템의 경우, 물리 법칙을 깨뜨리지 않고는 항을 버릴 수 없다는 것이었습니다. 이는 '불가능 정리 (no-go theorem)'로 여겨졌습니다.

그러나 이 논문은 상황을 뒤집습니다. 저자들은 많은 일반적인 양자 시스템 유형에 대해 답이 확실히 예임을 보여줍니다. 거의 모든 항을 제거하고 소수만 남겨두어도 시스템이 거의 동일하게 행동합니다.

비밀 재료: '비중복성 (Non-Redundancy)'

그들은 어떻게 했을까요? 그들은 **'비중복성 (Non-Redundancy)'**이라고 불리는 문제를 바라보는 새로운 방식을 고안해냈습니다.

해밀토니안을 건물을 감시하는 보안 요원 팀으로 생각해보세요.

• 중복 (Redundant): 경비원 A 와 경비원 B 가 모두 같은 문을 감시하고, 경비원 B 를 제거하면 경비원 A 가 경비원 B 가 보던 모든 것을 여전히 본다면, 경비원 B 는 '중복'입니다. 보안에 손실 없이 경비원 B 를 해고할 수 있습니다.
• 비중복 (Non-Redundant): 경비원 C 가 특정 숨겨진 창문 하나를 유일하게 감시하고, 경비원 C 를 제거하면 그 창문이 방치된다면, 경비원 C 는 '비중복'입니다. 그들을 해고할 수 없습니다.

저자들은 '희소화 (축소된)' 규칙책의 크기가 오직 비중복 항이 몇 개 있는지에 달려 있음을 깨달았습니다. 시스템에 항이 엄청나게 많더라도, 그중 대부분이 통제하는 측면에서 서로의 '복제본'이라면 복제본들을 삭제할 수 있습니다.

그들은 시스템이 가진 '고유한' 항의 수를 정확히 측정하는 수학적 도구를 개발했습니다. 고유 항의 수가 적다면 시스템을 축소하기 쉽습니다.

축소해낸 세 가지 시스템 유형

이 논문은 다음 세 가지 특정 양자 '레시피'에 대해 이것이 작동함을 증명합니다:

1. 파울리 스트링 (Pauli Strings, "표준" 블록): 이들은 대부분의 양자 컴퓨터의 구성 요소입니다. 저자들은 이러한 블록으로 구축된 거대한 시스템이라 할지라도, 큐비트 수에 비례하여 선형적으로만 증가하는 크기 (작은 오차 인자 추가) 로 축소할 수 있음을 보여줍니다. 마치 10,000 개의 지시사항 중 실제로 고유한 것은 500 개뿐임을 깨닫는 것과 같습니다.
2. 랜덤 연산자 ("혼돈" 시스템): 규칙이 무작위로 생성되는 시스템을 상상해 보세요. 놀랍게도 저자들은 이러한 혼돈 시스템이 고전적 대응물보다 실제로 축소하기 쉬운 것을 발견했습니다. 고전적 세계 (예: 표준 논리 퍼즐) 에서는 무작위 규칙을 단순화하기 어렵습니다. 하지만 양자 세계에서는 무작위 규칙이 종종 너무 많은 '중첩 (overlap)'을 가지고 있어 대부분을 삭제할 수 있습니다.
3. 양자 SAT ("어려운" 제약): 이는 규칙이 매우 엄격 (랭크가 높음) 한 시스템을 포함합니다. 저자들은 이러한 엄격한 시스템조차도 크게 단순화할 수 있음을 보여주었습니다.

실제 응용: 양자 "Max-Cut"

이 논문은 이론에 머무르지 않고 양자 Max-Cut이라는 유명한 문제에 적용합니다. 사람 (큐비트) 들의 네트워크가 있고, 두 그룹 사이 연결의 수를 최대화하도록 그들을 두 그룹으로 나누고 싶다고 상상해 보세요.

• 문제: 이를 해결하려면 일반적으로 네트워크의 모든 단일 연결을 살펴봐야 합니다. 네트워크가 거대하다면 이는 영원히 걸립니다.
• 해결: 그들의 희소화 기법을 사용하면 대부분의 연결을 버리고 작은 샘플만 유지한 채도 최상의 분할을 찾을 수 있음을 저자들은 보여줍니다.
• "스트리밍" 보너스: 이는 네트워크 연결의 라이브 피드와 같이 빠르게 들어오는 데이터에 특히 훌륭합니다. 저자들은 매우 적은 메모리 (작은 희소화된 버전을 유지하는 데 필요한 양) 로 이 데이터를 처리하면서도 올바른 답을 얻을 수 있음을 보여줍니다. 이는 컴퓨터 과학에서 이전까지 열린 질문이었던 문제를 해결합니다.

"고전 vs 양자"의 반전

가장 흥미로운 발견 중 하나는 고전 시스템과 양자 시스템 간의 비교입니다.

• 고전: 고전 논리 퍼즐 세계에서는 무작위 규칙이 종종 단순화하기 매우 어렵습니다.
• 양자: 양자 세계에서는 무작위 규칙이 종종 단순화하기 더 쉽습니다.

저자들은 양자 시스템이 우리가 생각했던 것보다 종종 "더 중복적"이라고 제안합니다. 양자 상태가 복잡한 방식으로 서로 간섭할 수 있기 때문에 많은 항이 같은 일을 하게 되어, 이를 삭제할 수 있게 됩니다.

요약

간단히 말해, 이 논문은 복잡한 양자 규칙책을 단순화하는 방법에 대한 가이드입니다.

• 옛 관점: "이것들을 단순화할 수 없다; 모든 항이 필수적이다."
• 새 관점: "사실 대부분의 항은 서로의 복사본일 뿐이다. (그들의 '비중복성' 도구를 사용하여) 중복을 찾는 법을 안다면, 결과를 바꾸지 않고도 규칙책을 막대하게 축소할 수 있다."

이 발견은 양자 컴퓨터를 위한 더 효율적인 알고리즘의 문을 엽니다. 이를 통해 양자 컴퓨터는 문제의 '희소화된' 버전으로 먼저 작업함으로써 더 빠르고 적은 메모리로 문제를 해결할 수 있게 됩니다.

기술 요약

기술적 요약: 많은 해밀토니안은 희소화 가능

문제 정의

본 논문은 해밀토니안 희소화 (Hamiltonian sparsification) 문제를 조사합니다. 각 $H_i$가 $r$-국소 (r-local) 양의 준정부호 (PSD) 항인 $n$-큐비트 해밀토니안 $H = \sum_{i=1}^m H_i$가 주어졌을 때, 모든 양자 상태 $|\psi\rangle \in \mathbb{C}^{2^n}$에 대해 다음을 만족하는 항의 희소 부분집합 $L \subseteq [m]$과 음이 아닌 가중치 $w: L \to \mathbb{R}_{\ge 0}$를 계산하는 것이 목표입니다:
$$\sum_{i \in L} w(i) \langle \psi | H_i | \psi \rangle \in (1 \pm \varepsilon) \sum_{i=1}^m \langle \psi | H_i | \psi \rangle$$
목표는 바닥 상태나 저에너지 부분공간뿐만 아니라 모든 상태의 에너지를 보존하는 $|L| \ll m$ 크기의 희소화기 $\tilde{H}$를 찾는 것입니다. 이는 바닥 상태와 스펙트럼 갭만 보존해야 하는 "갭 시뮬레이션 (gap simulation)"과 대조적입니다.

역사적으로 이 작업은 일반적인 해밀토니안에 대해 대체로 불가능한 것으로 여겨졌습니다. Aharonov 와 Zhou [AZ19] 는 특정 해밀토니안들이 갭 시뮬레이션이라는 더 약한 목표조차 위해 희소화될 수 없음을 보였으며, 이로 인해 해밀토니안 희소화에는 본질적인 한계가 있다는 지배적인 믿음이 생겼습니다. 본 논문은 광범위하고 견고한 해밀토니안 클래스에 대해 희소화가 가능함을 보여줌으로써 이러한 관점에 도전합니다.

방법론 및 핵심 개념

1. 비중복성 (Non-Redundancy)

본 논문에서 소개된 핵심 기술적 도구는 고전적 제약 만족 문제 (CSP) 에서 사용되는 개념의 양자 유사체인 비중복성입니다.

• 정의: 해밀토니안 $H$가 *비중복적 (non-redundant)*이라는 것은 모든 항 $H_i$에 대해, $\langle \psi | H_i | \psi \rangle \neq 0$이면서 모든 $j \neq i$에 대해 $\langle \psi | H_j | \psi \rangle = 0$인 상태 $|\psi\rangle$가 존재함을 의미합니다.
• 함의: 해밀토니안이 비중복적이라면, 이를 희소화할 수 없습니다 (어떤 항을 제거하더라도 그 항을 유일하게 만족하는 특정 상태에 대한 조건을 위반하게 됨).
• 전략: 저자들은 술어 행렬 $M$에 대해 가장 큰 비중복 부분 인스턴스의 크기 (기호: $NRD(M, n)$) 를 상한으로 묶습니다. 이 크기가 작다면 (예:$n$에 대해 선형), 해밀토니안은 매우 희소화 가능합니다.

2. 교차하는 항 분석

핵심 통찰은 교차하는 국소 항들의 영공간 (ground states) 간의 상호작용을 분석하는 것입니다.

• 불연속 영공간: 충분히 높은 랭크를 가진 무작위 해밀토니안의 경우, 저자들은 두 항 $H_i$와 $H_j$가 적어도 하나의 큐비트를 공유하면, 그들의 영공간이 불연속임을 증명합니다 (즉, $\ker(H_i) \cap \ker(H_j) = \{0\}$). 이는 상태가 자명하지 않는 한, 두 항을 동시에 영에너지로 만족하는 상태가 존재하지 않음을 의미합니다.
• 자기동형사상: 낮은 랭크나 특정 구조를 가진 해밀토니안 (예: 2-큐비트 시스템) 의 경우, 저자들은 바닥 상태의 **자기동형사상 군 (automorphism group)**을 분석합니다. 그들은 교차하는 항들이 바닥 상태에서 대칭성 (큐비트의 치환) 을 유도함을 보여줍니다. 상호작용 그래프에 특정 사이클이 포함되어 있으면, 이러한 대칭성들이 해밀토니안을 중복되게 만들어 비중복 부분집합의 크기를 제한합니다.

3. 희소화 알고리즘

본 논문은 항의 "중요도 점수"에 기반한 두 가지 주요 알고리즘적 전략을 사용합니다:

• 중요도 샘플링: 항 $H_i$의 중요도는 $\max_{|\psi\rangle} \frac{\langle \psi | H_i | \psi \rangle}{\langle \psi | H | \psi \rangle}$로 정의됩니다. 교차하는 항들의 교차 쌍들의 합에 대한 최소 고유값이 0 에서 멀리 떨어져 있다면, 개별 항의 중요도는 작아집니다 ($O(1/m)$).
• 행렬 체르노프 (Matrix Chernoff): 중요도 점수가 상한으로 묶이면, 저자들은 행렬 체르노프 상한을 사용하여 (적절히 가중치가 부여된) 항들의 무작위 샘플링이 높은 확률로 유효한 희소화를 생성함을 보입니다.
• 재귀적 박아내기 (Recursive Peeling): nullity-1 술어의 경우, 알고리즘은 "지배적 덮개 (dominating covers)" (스패닝 포레스트와 지배적 간선을 포함) 를 반복적으로 추출하고 나머지를 재귀적으로 희소화합니다.

주요 기여 및 결과

1. 파울리 해밀토니안

• 결과: $m$개의 항을 가진 임의의 $r$-국소 파울리 해밀토니안 (항들은 이동된 파울리 문자열) 은 크기 $\tilde{O}_r(\varepsilon^{-2} n)$로 희소화될 수 있습니다.
• 방법: 저자들은 상호작용 초그래프를 $r$-분할 (r-partite) 부분그래프로 분할합니다. 분할 설정에서 파울리 문자열은 교환하므로, 기저 변환을 통해 문제를 고전적 XOR-CSP 의 희소화로 축소할 수 있습니다. 그런 다음 고전적 CSP 희소화 결과를 적용합니다.

2. 일반적인 무작위 해밀토니안

• 결과: 각 항이 랭크 $R \ge 2^{r-1} + 1$인 무작위 PSD 행렬인 해밀토니안의 경우, 높은 확률로 크기 $\tilde{O}_r(\varepsilon^{-2} n)$로 희소화하는 것이 가능합니다.
• 의의: 이 결과는 랭크가 결여된 행렬 (충분히 높은 랭크라면) 에 대해서도 성립합니다. 이는 무작위 양자 해밀토니안이 종종 초선형 희소화 크기를 요구하는 무작위 고전적 CSP 들보다 훨씬 더 희소화하기 쉽다는 것을 보여줍니다.

3. Nullity-1 해밀토니안 (양자 SAT)

• 결과: 각 항의 nullity 가 최대 1 인 해밀토니안 (랭크 $\ge 2^r - 1$) 에 대해, 크기 $\tilde{O}_r(\varepsilon^{-2} n^2)$의 희소화가 존재합니다.
• 방법: 저자들은 "지배적 덮개"를 구성하고 재귀적 샘플링 전략을 사용합니다. 이는 양자 복잡성의 근본적인 클래스인 양자 SAT 문제에 적용됩니다.

4. 비중복성의 특성화

• 텐서 곱: 술어 행렬 $M$이 랭크-1 행렬들의 텐서 곱인 경우 (예: 고전적 AND 술어), 논문은 비중복성이 $\Omega(n^r)$임을 증명하여 희소화가 불가능함을 보입니다. 이는 고전적 AND 술자에 대한 알려진 하한을 일반화합니다.
• 2-큐비트 시스템: 저자들은 2-큐비트 해밀토니안의 비중복성을 완전히 특성화합니다. $NRD(M, n) = \Theta(n^2)$인 것은 $M$이 두 개의 랭크-1 행렬의 텐서 곱일 때만 해당되며, 그렇지 않으면 $NRD(M, n) = \Theta(n)$입니다.
• 일반적 랭크: 랭크 $R = 2^{r-1} - 1$인 무작위 행렬의 경우, 비중복성은 $\tilde{O}(n)$으로 제한되며, 이는 "일반적인" 경우보다 약간 낮은 랭크조차도 희소화를 허용함을 보여줍니다.

5. 양자 MAX-CUT 에의 적용

• 결과: 본 논문은 양자 MAX-CUT 인스턴스를 희소화하는 효율적인 알고리즘을 제공합니다. 그래프 $G$가 주어지면, $\tilde{G}$에 대해 거의 최적인 임의의 상태가 $G$에 대해서도 거의 최적인 $O(\varepsilon^{-2} n)$개의 간선을 가진 희소 부분그래프 $\tilde{G}$를 찾을 수 있습니다.
• 스트리밍: 이 결과는 Kallaugher 와 Parekh [KP22] 의 열린 질문에 답하여, 양자 MAX-CUT 이 $\tilde{O}(\varepsilon^{-2} n)$ 공간으로 스트리밍 모델에서 해결될 수 있음을 보여줍니다. 이는 $o(n)$ 공간 (상수 인자 근사만 가능한 경우) 에서 $\tilde{O}(n)$ 공간으로의 근사 가능성에 대한 위상 전이를 확립합니다.

의의 및 주장

본 논문은 이전 문헌에서 인용된 "불가능 (no-go)" 정리에 반하여, 해밀토니안 희소화는 다양한 자연스러운 해밀토니안 클래스에 대해 견고한 현상임을 주장합니다.

1. 비관주의 반박: Aharonov 과 Zhou [AZ19] 가 특정 클래스에 대한 한계를 보였지만, 이 작업은 "대부분"의 해밀토니안 (무작위 해밀토니안과 양자 코딩 및 SAT 에서 발생하는 해밀토니안 포함) 이 거의 선형 크기로 희소화 가능함을 보여줍니다.
2. 양자 대 고전: 이 결과는 양자 시스템과 고전 시스템 간의 근본적인 차이를 강조합니다. (충분한 랭크를 가진) 무작위 양자 해밀토니안은 종종 초선형 희소화기를 요구하는 무작위 고전적 CSP 들보다 희소화하기 쉽습니다.
3. 알고리즘적 유용성: 희소화기는 양자 알고리즘을 위한 전처리 단계로 작용합니다. 항의 수를 줄임으로써 하류 알고리즘은 더 낮은 기술적 복잡성을 가진 시스템에서 작동할 수 있습니다.
4. 이론적 프레임워크: 해밀토니안에 대한 비중복성의 체계적 이론을 도입함으로써 양자 바닥 상태와 그 상호작용의 구조를 이해하는 새로운 렌즈를 제공하며, 양자 해밀토니안 복잡성과 고전적 CSP 이론 간의 간극을 연결합니다.

저자들은 희소화가 보편적이지는 않지만 (예: 텐서 곱 랭크-1 술어의 경우 실패함), 그것이 성공하는 조건은 광범위하며 많은 물리적으로 관련 있고 알고리즘적으로 중요한 시스템을 포함한다고 결론지었습니다.