⚛️ 양자물리학

Analog quantum approximate optimization algorithm for solving the weighted MaxCut problem on three-dimensional single-atom Rydberg array

이 논문은 이산화된 양자 어닐링과 그래프 신경망 웜스타트 초기화의 결합된 최적화 전략을 활용하여 3D 리드베리 원자 배열에 구현된 아날로그 양자 근사 최적화 알고리즘이 현실적인 오차 모델 하에서도 가중치 MaxCut 문제를 해결하는 데 있어 고전적인 Goemans-Williamson 알고리즘보다 뛰어난 성능을 보일 수 있음을 이론적으로 입증한다.

원저자: Junxi Chen, I. I. Beterov

게시일 2026-11-11

📖 5 분 읽기🧠 심층 분석

CC BY 4.0

원저자: Junxi Chen, I. I. Beterov

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

컴퓨팅의 세계에서 어떤 문제들은 해결하기 매우 까다롭기로 악명이 높습니다. 이들은 NP-hard라고 알려진 부류에 속하며, 여기서 완벽한 답을 찾는 것은 문제가 커짐에 따라 기하급수적으로 어려워져서, 가장 강력한 슈퍼컴퓨터로도 우주의 나이만큼 긴 시간이 걸릴 수 있습니다. 이러한 퍼즐 중 하나가 가중치 최대 컷(weighted maximum cut) 문제입니다. 네트워크의 점들이 선으로 연결되어 있고, 각 선에는 특정 값이 있다고 상상해 보십시오. 목표는 두 그룹 사이를 잇는 선들의 총합(가치)이 최대한 높도록 점들을 두 그룹으로 나누는 것입니다. 이 과제는 단순한 수학적 호기심을 넘어, 효율적인 컴퓨터 칩 설계, 데이터 클러스터 구성, 네트워크 인프라 계획과 같은 현실 세계의 과제들을 뒷받침합니다. 완벽한 솔루션을 찾는 것이 매우 어렵기 때문에, 과학자들은 근사 알고리즘이라 불리는 영리한 지름길에 의존합니다. 수십 년 동안 고만스-윌리엄슨(Goemans and Williamson)에 의해 개발된 고전적 방법은 황금 표준으로 자리 잡았으며, 완벽한 답의 최소 87.8%에 달하는 해답을 보장합니다.

최근, 양자 역학의 기묘한 법칙을 사용하여 이러한 어려운 문제들을 해결하고자 하는 새로운 분야가 등장했습니다. 표준 비트가 0 또는 1의 상태를 갖는 대신, 양자 컴퓨터는 여러 상태가 동시에 혼합될 수 있는 큐비트를 사용합니다. 유망한 접근 방식 중 하나는 양자 근사 최적화 알고리즘(QAOA)입니다. 전통적인 양자 컴퓨터는 종종 일련의 정밀한 논리 게이트를 길게 연결하여 문제를 해결하려고 하지만, 더 새로운 "아날로그" 버전은 레이저 펄스의 영향 아래서 양자 시스템이 자연스럽게 진화하도록 둡니다. 이 논문은 진공 속에 갇힌 개별 원자들의 3차원 격자를 사용하는 이 진보된 아날로그 접근 방식의 특정 버전을 탐구합니다. 이 원자들은 서로 강하게 상호작용하는 리드베리(Rydberg) 상태라고 알려진 고에너지 상태로 들뜨게 됩니다. 연구진은 이 물리적 설정이 기존의 최선인 고전적 방법보다 가중치 최대 컷 문제를 더 잘 해결할 수 있는지, 그리고 실제 환경의 노이즈와 오류에도 불구하고 어떻게 안정적으로 작동하게 할 수 있는지를 알아보고자 했습니다.

연구진은 12개의 점을 가진 20개의 서로 다른 무작위 네트워크를 사용하여 시뮬레이션을 설계하며 시작했습니다. 그들은 이 네트워크들을 원자들의 물리적 격자에 매핑하였으며, 3차원 공간에 원자들을 배치하여 두 원자 사이의 거리가 상호작용의 강도를 결정하도록 했습니다. 원자들을 정교하게 배치함으로써, 문제의 특정 값들을 입자들 사이의 물리적 힘 속에 직접 인코딩했습니다. 만약 문제의 두 점이 강한 연결이 필요하다면 해당 원자들을 가깝게 배치했고, 약한 연결이 필요하다면 더 멀리 배치했습니다. 이 방법은 별도의 "도움" 원자나 복잡한 기술 없이, 시스템의 자연스러운 물리학에 의존하여 문제를 해결할 수 있게 해주었습니다. 그런 다음 연구진은 레이저 펄스의 연속적인 시퀀스를 통해 양자 시스템을 실행하며, 시스템을 최적의 해로 유도하기 위한 두 가지 다른 전략을 테스트했습니다.

"콜드 스타트(cold start)"로 알려진 첫 번째 전략은 모든 원자가 중립 상태에서 시작하여 시스템이 일련의 단계들을 통해 진화하도록 두는 방식이었습니다. 연구진은 시스템이 취하는 경로가 매우 중요하다는 것을 발견했습니다. 만약 단순히 컴퓨터 최적화 도구가 가이드 없이 층(layer)별로 최적의 설정을 선택하게 내버려 둔다면, 시스템은 초반에는 좋아 보이지만 과정이 진행됨에 따라 개선되지 못하는 경로에 갇히게 됩니다. 이 경로는 완벽한 답의 약 77% 수준에 불과한 해답으로 이어졌습니다. 그러나 레이저 펄스의 특정 부분이 지속되는 시간을 제한하는 간단한 물리적 제약을 추가함으로써, 연구진은 시스템을 다른 경로로 유도했습니다. 이 새로운 경로는 '어닐링(annealing)'이라고 알려진 느리고 신중한 냉각 과정처럼 작동했습니다. 이 경로에서는 층을 추가할수록 해의 품질이 계속 향상되었으며, 결국 95.9%의 점수에 도달하여 대부분의 테스트 케이스에서 고전적 황금 표준을 능가했습니다.

"웜 스타트(warm start)"라고 불리는 두 번째 전략은 양자 시스템에 유리한 출발점을 제공하려고 시도했습니다. 레이저 펄스가 시작되기 전, 연구진은 그래프 신경망(graph neural network)이라는 유형의 인공지능인 고전 컴퓨터 프로그램을 사용하여 좋은 초기 배치를 추측했습니다. 그런 다음 그 추측에 맞춰 원자들을 준비했습니다. 이 접근 방식은 초기 추측이 맞을 때만 매우 효과적이었습니다. 네트워크의 추측이 맞았을 때, 양자 시스템은 이를 매우 빠르게 거의 완벽한 해로 정교화했습니다. 그러나 네트워크의 추측이 틀렸을 때, 양자 시스템은 그 잘못된 답 근처에 갇혀 진정한 최적의 해를 찾지 못하는 경향을 보였습니다. 이는 두 전략이 서로 다른 상황에서 실패한다는 중요한 통찰을 보여주었습니다. 콜드 스타트 방식은 원자들의 물리적 배치가 불완전할 때 어려움을 겪었고, 웜 스타트 방식은 인공지능의 초기 추측이 좋지 않을 때 어려움을 겪었습니다.

두 방식의 장점을 모두 얻기 위해, 연구진은 이 두 접근 방식을 하나의 포트폴리오로 결합했습니다. 각 문제에 대해 콜드 스타트와 웜 스타트 버전을 모두 실행한 뒤, 단순히 더 나은 결과를 선택하는 방식입니다. 이 결합된 전략은 완벽하고 노이즈가 없는 시뮬레이션의 20개 테스트 케이스 중 19개에서 고전적 황금 표준을 능가했습니다. 그러나 기존의 양자 프로세서인 Aquila를 기반으로 한 현실적인 오류 모델을 적용하여 테스트했을 때, 결과는 달라졌습니다. 이 노이즈가 있는 환경에서는 길고 복잡한 시퀀스를 실행하여 얻는 이점이 사라졌습니다. 시뮬레이션에서 매우 효과적이었던 깊은 어닐링 기반의 경로는 너무 취약해졌고, 시퀀스가 길어짐에 따라 품질을 유지할 수 없었습니다. 이러한 노이즈 조건에서 가장 좋은 성능을 보인 것은 단 몇 단계와 매우 짧은 레이저 펄스만을 요구하는 짧은 웜 스타트 방식이었습니다. 그러나 이 짧은 버전조차 노이즈가 있는 시뮬레이션에서는 고전적 황금 표준을 이기지 못했습니다. 단일 고만스-윌리엄슨 라운딩(rounding)이 성공하는 횟수의 절반에도 미치지 못하는 16%의 샷(shot)에서만 최적의 컷을 산출했습니다.

본 연구는 아날로그 양자 접근 방식이 고전적 알고리즘을 능가할 수 있는 큰 잠재력을 가지고 있지만, 그 잠재력을 실현하는 길이 결코 단순하지 않다고 결론짓습니다. 가장 높은 이론적 성능을 제공하는 깊은 어닐링 형태의 시퀀스는 현재의 하드웨어에서 발견되는 오류들에 너무 민감합니다. 당장 실행 가능한 가장 효과적인 전략은 짧고 영리한 초기 추측을 사용하여 시스템을 안내하거나, 여러 전략을 병렬로 실행하여 승자를 선택하는 하이브리드 방식인 것으로 보입니다. 연구진은 깊고 고성능인 시퀀스를 실행 가능하게 만들려면 양자 프로세서의 오류율이 대략 10배(an order of magnitude) 정도 낮아져야 한다는 것을 발견했습니다. 그때까지 이 기계들을 사용하는 가장 실용적인 방법은, 짧은 시퀀스의 속도와 다양한 전략의 힘을 활용하여 복잡한 난제들의 지형을 탐색하는 결합된 접근 방식을 사용하는 것입니다.

기술 요약: 3D 리드베리 배열에서의 가중치 MaxCut를 위한 아날로그 양자 근사 최적화 알고리즘(QAOA)

문제 정의
본 연구는 VLSI 설계, 데이터 클러스터링, 네트워크 인프라 등에서 응용되는 근본적인 NP-난해 조합 최적화 문제인 가중치 최대 컷(Weighted MaxCut) 문제를 다룹다. 이 문제는 그래프 $G=(V, E, w)$ 의 정점들을 두 개의 서로 소인 집합으로 분할하여 두 집합을 연결하는 에지의 총 가중치를 최대화하는 것을 목표로 한다. 저자들은 개별적으로 트랩된 3차원(3D) 리드베리 원자 배열을 사용하여 가중치 MaxCut 문제를 해결하기 위한 아날로그 방식의 양자 근사 최적화 알고리즘(QAOA) 구현에 집중한다. 임의의 그래프를 임베딩하기 위해 가젯(gadget) 구성을 사용하거나 평면 격자에 의존하는 기존의 접근 방식과 달리, 본 연구는 임의의 가중치 에지를 직접 인코딩하기 위해 3D 원자 배열의 자연스러운 기하학적 구조를 활용한다.

방법론
제안된 프로토콜은 $N=12$ 개의 초저온 $^{87}$ Rb 원자가 리드베리 상태( $|70S_{1/2}\rangle$ )로 들뜬 3D 배열을 사용한다. 시스템은 반데르발스 상호작용( $V_{ij} \propto 1/r_{ij}^6$ )이 프로그래밍 가능한 2체 이싱 결합(two-body Ising couplings)을 제공하는 해밀토니안에 의해 지배된다.

그래프 임베딩: 저자들은 가중치 MaxCut 문제를 물리적 시스템에 직접 매핑한다. 에지 가중치 $w_{ij}$ 는 상호작용 에너지 $V_{ij}/4$ 가 원하는 가중치에 대응하도록 원자들을 특정 거리 $r_{ij}$ 에 배치함으로써 인코딩된다. 인접하지 않은 원자들도 상호작용하지만, 이러한 "비에지(non-edge)" 결합은 제거되기보다는 시스템 역학의 일부로 취급된다.
해밀토니안 및 펄스 시퀀스: 시스템은 시간 의존적 해밀토니안 $H(t) = \sum_i \frac{\Omega_i(t)}{2}(e^{i\phi}|g\rangle\langle r| + h.c.) - \sum_i \Delta_i(t) n_i + \sum_{i<j} V_{ij} n_i n_j$ $H (t) = \sum_{i} \frac{Ω _{i} ( t )}{2} (e^{i ϕ} ∣ g ⟩ ⟨ r ∣ + h . c .) - \sum_{i} Δ_{i} (t) n_{i} + \sum_{i < j} V_{ij} n_{i} n_{j}$ 하에서 진화한다.
- 준비(Preparation): 전역 펄스가 초기 상태(콜드 스타트(cold start)를 위한 $|+\rangle^{\otimes N}$ 또는 웜 스타트(warm start)를 위한 특정 곱 상태)를 준비한다.
- 비용 세그먼트(Cost Segments): 드라이브가 꺼져 있는( $\Omega=0$ ) 기간으로, 사이트별 디튜닝(detuning) $\Delta_i$ 를 사용하여 반데르발스 상호작용에서 발생하는 단일 사이트 항을 상쇄하며 비용 해밀토니안 $H_C$ 하에서 진화한다.
- 믹서 세그먼트(Mixer Segments): 전역 또는 사이트별 드라이브가 활성화되는 기간으로, 가로 자기장(transverse field) 성분을 제공한다.
최적화 전략: 펄스 파라미터(지속 시간 $\gamma_k$ $γ_{k}$ 및 $\beta_k$ $β_{k}$ )를 최적화하기 위해 두 가지 접근 방식을 비교한다.
- 콜드 스타트(Cold Start): 균일한 중첩 상태 $|+\rangle^{\otimes N}$ 로부터 초기화한다.
- 웜 스타트(Warm Start): 정점 마진럴(vertex marginals)을 예측하는 그래프 신경망(GNN)으로부터 유도된 곱 상태를 사용하여 초기화한다. 이는 믹서의 고유 상태가 되도록 하기 위해 사이트별 라비 주파수와 특정 디튜닝 이동을 필요로 한다.
시뮬레이션 및 검증: 저자들은 "Aquila" 중성 원자 양자 프로세서를 모사하기 위해 크릴로프 전파법(Krylov propagation method, Arnoldi)과 양자 궤적 솔버(quantum trajectory solver)를 사용하여 시스템을 시뮬레이션한다. 이 오차 모델에는 준정적 레이저 노이즈, 원자 위치 변동, 탈위상(dephasing), 자발적 붕괴 및 검출 오류가 포함된다.

주요 결과
연구는 12개의 정점을 가진 20개의 무작위 생성된 3-정규 그래프를 평가한다.

최적화 랜드스케이프: 저자들은 최적화 랜드스케이프에서 두 개의 뚜렷한 분기(branch)를 식별한다. 표준적인 레이어별 최적화 도구는 근사 비율( $R_a$ )이 약 0.77에서 포화되는 "비단열 분기(non-adiabatic branch, Basin B)"에 갇히기 쉽다. 비용 세그먼트의 지속 시간을 제한하는 물리적 제약( $\gamma_k \leq 1 \mu s$ )을 부과함으로써, 최적화 도구는 "어닐링 분기(annealing branch, Basin A)"로 유도된다. 이 분기에서 $R_a$ 는 깊이( $p$ )에 따라 단조 증가하며, $p=20$ 에서 $0.959$에 도달한다.
고전 알고리즘과의 비교:
- 무잡음(noiseless) 영역에서, 최적화된 어닐링 분기( $p \geq 16$ )는 기대 컷 값 측면에서 Goemans-Williamson(GW) 라운딩 알고리즘보다 우수한 성능을 보인다.
- 그러나 GNN 웜 스타트 프로토콜은 통계적으로 GW와 구별되지 않는다 (예: $p=10$ 에서 평균 차이는 $-0.006$, $P=0.76$ ).
- **포트폴리오 전략(Portfolio strategy)**은 각 인스턴스에 대해 콜드 스타트 어닐링 분기와 웜 스타트 프로토콜 중 더 나은 결과를 선택하며, 20개 인스턴스 중 19개에서 GW를 능가하는 평균 $R_a$ 0.966을 달성한다. 그러나 포트폴리오의 GW 대비 평균 차이는 통계적으로 유의미하지 않으며( $P=0.45$ ), 포트폴리오는 GNN 라운딩 자체보다 유의미하게 낫지 않다. GNN 라운딩은 강력한 고전적 참조 역할을 하며, 특히 네트워크의 초기 추측이 최적에 가까운 경우 기대값 측면에서 양자 프로토콜보다 뛰어난 성능을 보인다.
- GNN 웜 스타트는 네트워크의 초기 추측이 최적에 가까울 때는 매우 효과적이지만, GNN 예측이 좋지 않을 때는 실패(차선책의 문자열에 집중)할 수 있다. 반대로, 콜드 스타트 어닐링 분기는 GNN 실패에 강건하지만 더 깊은 회로를 요구한다.
노이즈 분석: Aquila 프로세서의 실제 오차 모델로 에뮬레이션했을 때:
- 깊은 회로의 이점이 감소한다. 어닐링 분기의 최적 깊이는 $p=20$ 에서 $p=5$ 로 떨어진다.
- 얕은 깊이( $p=3$ )에서의 웜 스타트 프로토콜이 가장 견고한 단일 프로토콜이 되어, 노이즈가 있는 어닐링 분치보다 우수한 성능을 보인다.
- 결정적으로, 노이즈 수준이 증가함에 따라 포트폴리오 전략의 가치가 상실된다. 노이즈 스케일링 인자 $\lambda \geq 1$ (현재 하드웨어 능력 수준)에서 웜 스타트가 모든 인스턴스에서 더 나은 멤버가 되어, 사실상 포트폴리오를 웜 스타트 단독으로 축소시킨다. 포트폴리오는 훨씬 낮은 노이즈 수준( $\lambda \approx 0.1$ )에서만 보완적인 가치를 유지한다.
샘플링 통계: 기대값은 개선되지만, 단일 샷에서 정확한 최적 컷을 측정할 확률( $P_{opt}$ )은 작은 깊이에서 반복적인 GW 라운딩보다 여전히 낮다. 그러나 양자 프로토콜은 특정 영역에서 고전적 샘플링에 비해 적은 샷으로 고품질 컷을 찾는 데 잠재력을 보여준다.

의의 및 주장
본 논문은 가젯 기반 임베딩의 오버헤드 없이 가중치 MaxCut를 위한 아날로그 리드베리 기반 QAOA의 잠재력을 입증했다는 점을 겸허히 주장한다. 주요 기여는 다음과 같다:

직접적인 3D 임베딩: 원자 간 거리를 조절함으로써 임의의 가중치 그래프를 네이티브하게 인코딩할 수 있는 3D 원자 배열을 입증하여, 보조 큐비트의 필요성을 피했다.
랜드스케이프 분석: $p=1$ 에서의 최적 국소 최소값(local minimum)을 선택하는 "탐욕적(greedy)" 선택이 어떻게 하위 최적의 글로벌 성능(비단열 분기)으로 이어질 수 있는지 식별하였고, 펄스 지속 시간에 대한 단순한 물리적 제약이 어떻게 최적화 도구를 더 우수한 단열 궤적으로 유도할 수 있는지 밝혔다.
하이브리드 전략: 고전적 휴리스틱(GNN)을 이용한 웜 스타트와 양자 어닐링 분기를 결합함으로써, 무잡음 한계 내에서 각자의 약점을 보완하여 단독 방법보다 더 강력한 포트폴리오를 생성할 수 있음을 보여주었다. 그러나 이 이점은 낮은 노이즈 수준에서 조건부로 성립된다. 현재의 하드웨어 노이즈 하에서는 포트폴리오가 웜 스타트 프로토콜로 수렴한다.
노이즈 탄력성: 현재의 하드웨어 노이즈가 깊은 회로의 이점과 포트폴리오 전략의 효용성을 제한하고 있지만, 얕은 깊이의 웜 스타트 프로토콜이 오차율이 관리될 경우 기대값 측면에서 고전적 베이스라인을 능가할 수 있다는 현실적인 평가를 제공한다.

저자들은 현재의 노이즈 수준이 깊은 어닐링 분기와 포트폴리오 접근 방식의 전체 잠재력 실현을 방해하고 있지만, 무잡음 한계에서의 관찰된 성능과 웜 스타트 프로토콜의 견고함은 하드웨어 충실도가 향상됨에 따라 유망한 경로가 될 것임을 시사한다고 결론짓는다.

유사한 논문