A Unified Local Light-shifts Encoding For Solving Optimization Problems on a Rydberg Annealer

본 논문은 국소 광이동 부호화와 최적화된 양자 어닐링 프로토콜을 통해 다양한 NP-완전 조합 최적화 문제를 QUBO 형식으로 매핑하여 리드베리 양자 어닐러에서 해결하는 통합 프레임워크를 제시함과 동시에 문제 복잡도를 정량화하기 위한 일반화된 난이도 매개변수를 도입한다.

핵심

거대한 엉킨 퍼즐을 풀려고 노력한다고 상상해 보세요. 일부 조각은 쉽게 맞물리지만, 다른 조각들은 서로 맞서며 엉망진창을 만들어 해체하기가 매우 어렵습니다. 컴퓨터 세계에서는 이러한 퍼즐들을 최적화 문제라고 부릅니다. 이들은 간단한 논리 게임부터 공장 배치, 데이터 그룹화, 심지어 단백질이 3 차원 형태로 접히는 방식을 규명하는 것과 같은 복잡한 현실 세계의 도전 과제까지 다양하게 존재합니다.

이 논문은 리드버그 원자로 구성된 특별한 종류의 "양자 컴퓨터"를 사용하여 이러한 퍼즐을 해결하는 새로운 통합 방식을 제시합니다. 여기서는 간단한 비유를 사용하여 저자들이 수행한 작업을 설명합니다.

1. 문제: "NP-난해" 미로

이러한 퍼즐 중 많은 부분이 NP-난해라는 범주에 속합니다. 벽이 계속 변하는 미로에서 가장 짧은 경로를 찾으려 한다고 상상해 보세요. 일반 컴퓨터 (예: 노트북) 는 미로가 커질수록 영원히 걸릴 수 있는 모든 경로를 하나씩 확인해야 합니다. 저자들은 양자 기계가 훨씬 빠르게 출구를 찾을 수 있는지 확인하고자 했습니다.

그들은 QUBO(Quadratic Unconstrained Binary Optimization, 2 차 무제약 이진 최적화) 라고 불리는 특정 유형의 퍼즐을 선택했습니다. QUBO 는 이러한 퍼즐들을 위한 보편적인 언어라고 생각하세요. 여행 가방을 채우는 것 (Set Packing), 작업자에게 업무를 할당하는 것 (Quadratic Assignment), 또는 단백질을 접는 것 등 어떤 문제를 풀더라도 그 규칙을 이 이진 언어 (0 과 1) 로 번역할 수 있습니다.

2. 해결책: 리드버그 "원자 오케스트라"

저자들은 까다롭고 확장하기 어려운 일반적인 양자 컴퓨터 대신 리드버그 원자를 사용했습니다.

• 비유: 오케스트라의 악기들처럼 격자에 갇힌 원자들의 무리를 상상해 보세요. 각 원자는 "바닥 상태 (잠든 상태)" 또는 "리드버그 상태 (각성된 상태)" 중 하나의 상태에 있을 수 있습니다.
• 상호작용: 원자가 깨어나면 매우 커지고 이웃과 상호작용합니다. 두 이웃이 모두 깨어 있으면 서로 밀어냅니다 (이를 리드버그 차단이라고 합니다).
• 혁신: 일반적으로 이러한 퍼즐을 해결하려면 거대한 수의 원자 (10 명만 필요한 곡을 연주하기 위해 100 명의 음악가가 필요한 것처럼) 를 필요로 하는 매우 구체적이고 복잡한 방식으로 원자들을 상호작용시켜야 합니다. 저자들은 "국소 광이동 (Local Light-shifts)" 방법을 개발했습니다.
  • 은유: 전체 오케스트라가 악기를 바꾸도록 강요하는 대신, 지휘자 (레이저) 가 각각의 음악가에게 특정 지시를 속삭이는 것입니다 (이를 "디튜닝" 조정이라고 합니다). 이를 통해 추가적인 음악가나 복잡한 설정 없이도 정확한 곡을 연주 (특정 퍼즐 해결) 할 수 있습니다. 이로 인해 시스템이 훨씬 더 효율적이고 확장 가능해집니다.

3. 과정: 시스템을 목적지로 안내하기

원자들이 퍼즐을 표현하도록 설정되면, 저자들은 그들을 해답으로 안내해야 합니다.

• 여정: 그들은 양자 어닐링이라는 기술을 사용합니다. 언덕이 많은 지형에서 공이 굴러가는 상황을 상상해 보세요. 목표는 공을 가장 깊은 계곡 (최고의 해답) 의 바닥으로 보내는 것입니다.
• 도전: 이 지형에는 공이 바닥에 도달한 줄 알고 멈춰버릴 수 있는 작은 함정들 (국소 최소값) 이 가득합니다.
• 요령: 저자들은 스마트한 "제어 프로토콜"을 사용했습니다. 공이 굴러가게만 내버려 두지 않고, 레이저 펄스 (라비 주파수) 를 사용하여 지형을 부드럽게 흔들어 주고 (Rabi frequency), 디튜닝을 조정하여 지면을 정밀하게, 시간에 따라 기울였습니다. 이는 공이 언덕을 "터널링"하거나 작은 함정에서 스스로 떨쳐내어 진정한 가장 깊은 계곡을 찾도록 돕습니다. 그들은 완벽한 흔들기 패턴을 찾기 위해 스마트한 알고리즘들을 혼합하여 사용했습니다.

4. 결과: 다양한 퍼즐 해결

팀원들은 쉬운 것부터 매우 어려운 것까지 일곱 가지 유형의 퍼즐에 이 방법을 테스트했습니다.

• 쉬운 것들: 답이 직관적인 간단한 논리 퍼즐 (Two-SAT 등) 입니다. 시스템은 이러한 문제들을 거의 완벽한 정확도 (99.9%) 로 해결했습니다.
• 어려운 것들: 아미노산 사슬이 어떻게 꼬이는지 규명하는 단백질 접힘과 시설 배치 최적화인 2 차 할당과 같은 복잡한 문제들입니다.
  • 결과: 단백질 접힘 사례에서 시스템은 완벽한 것은 아니지만 매우 좋은 해답 (98% 정확도) 을 찾았습니다. 저자들은 단백질 접힘의 "지형"이 매우 평평하고 혼란스러우며, 해답처럼 보이지만 실제로는 아닌 경로가 많기 때문이라고 설명합니다.
  • 핵심 발견: 이 방법은 동일한 기본 설정을 사용하여 모든 문제에 작동하여, 이것이 "통합된" 프레임워크임을 입증했습니다.

5. "난이도" 측정하기

왜 어떤 퍼즐이 다른 것보다 쉬운지 이해하기 위해, 저자들은 **"난이도 매개변수"**를 고안했습니다.

• 비유: 이를 퍼즐의 에너지 지형에 대한 "난이도 등급"이라고 생각하세요.
  • 가장 깊은 계곡이 다른 모든 계곡과 멀리 떨어져 있다면 (큰 간격), 찾기 쉽습니다.
  • 가장 좋은 계곡과 거의 같은 깊이의 계곡이 많거나, 지면이 평평하고 혼란스럽다면 그 퍼즐은 "어렵습니다".
• 통찰: 그들은 단백질 접힘과 같은 문제들이 에너지 지형이 가장 혼잡하고 평평하기 때문에 가장 어려웠으며, 이로 인해 시스템이 진정한 최고의 해답과 "거의 최고의" 해답들을 구별하기 어렵다는 것을 발견했습니다.

요약

간단히 말해, 저자들은 리드버그 원자를 사용하여 유연하고 효율적인 "양자 놀이터"를 구축했습니다. 각 원자에게 개인화된 지시 (국소 광이동) 를 주고, 스마트하고 최적화된 리듬으로 그들을 안내함으로써, 그들은 다양한 복잡한 최적화 퍼즐들을 성공적으로 해결했습니다. 그들은 구조상 일부 퍼즐이 다른 것보다 본질적으로 더 어렵다는 것을 보여주었지만, 이 통합된 접근 방식은 각 문제 유형마다 다른 기계가 필요하지 않고 모든 문제를 해결할 수 있음을 입증했습니다.

기술 요약

기술 요약: Rydberg 어닐러에서 최적화 문제를 해결하기 위한 통합된 국소 광 이동 부호화

문제 제기
많은 조합 최적화 문제 (예: 이차 할당, 단백질 접힘) 는 NP-hard 복잡도 클래스에 속하며 고전 알고리즘으로는 계산적으로 어렵지만 실질적인 가치가 큽니다. 양자 알고리즘은 잠재적 이점을 제공하지만, 이러한 문제를 양자 하드웨어에 매핑할 때 종종 상당한 자원 오버헤드가 발생합니다. 구체적으로, 기존 Rydberg 원자 기반 부호화 방식은 Rydberg 차단 (blockade) 메커니즘에 의존하는 경우가 많으며, 이는 일반적으로 문제 크기에 대해 원자 수의 이차적 오버헤드를 요구합니다. 또한, 변분 양자 알고리즘은 종종 큰 매개변수 공간과 자체 매개변수의 NP-hard 최적화로 어려움을 겪습니다. 저자들은 이러한 한계를 극복하고, 자원 오버헤드를 줄이고 확장성을 향상시킨 Rydberg 양자 플랫폼에서 다양한 이차 무제약 이진 최적화 (QUBO) 문제를 부호화하고 해결하기 위한 통합 프레임워크를 개발하고자 합니다.

방법론
본 논문은 광학 집게에 갇힌 Rydberg 원자를 활용하는 "LOQAL"(Loop 내 양자 어닐링을 위한 국소 최적 제어) 이라는 통합 프레임워크를 제안합니다. 방법론은 세 가지 주요 구성 요소로 이루어집니다:

1. 국소 광 이동을 통한 통합 부호화:
   차단 기반 제약에 의존하는 대신, 저자들은 개별 원자에 대한 국소 광 이동 (detuning) 을 사용하여 QUBO 문제를 직접 Ising 스핀 모델로 매핑하는 차단 비기반 부호화 방식을 채택합니다.

   • 해밀토니안 매핑: 시스템은 전역 라비 주파수 ($\Omega$) 와 위치 의존적 디튜닝 ($\Delta_j$) 을 포함하는 Rydberg 해밀토니안으로 기술됩니다. 라비 주파수가 0 인 극한에서 이는 종방향 장과 쌍별 상호작용을 갖는 Ising 해밀토니안으로 매핑됩니다.
   • 매개변수 제어: 문제의 상호작용 강도 ($J_{ij}$) 는 원자 간 거리에 의해 제어되는 원자 간 반데르발스 상호작용 ($V_{ij}$) 으로 매핑됩니다. 국소 종방향 장 ($h_i$) 은 위치 의존적 디튜닝 ($\Delta_j$) 으로 매핑됩니다. 이는 차단 방식의 이차적 오버헤드를 피하고 물리적 큐비트 수를 이진 변수 수에 직접 대응시키는 직접적이고 선형적인 매핑을 가능하게 합니다.
   • 범위: 이 프레임워크는 두 가지 SAT, XOR-SAT, 혼합 두 가지 XOR-SAT, 집합 패킹, 이차 할당 문제 (QAP), 이진 클러스터링, 단백질 접힘 (HP 모델) 등 일곱 가지 서로 다른 문제 클래스에서 입증되었습니다.

2. 최적화된 양자 어닐링 프로토콜:
   목표 해밀토니안의 바닥 상태를 찾기 위해 저자들은 최적 제어 접근법을 활용합니다.

   • 펄스 성형: 시간 의존적 디튜닝 ($\Delta_j(t)$) 과 라비 주파수 ($\Omega(t)$) 프로파일을 최적화하여 초기 상태 (예: 모든 바닥 상태 또는 모든 들뜬 상태) 를 목표 바닥 상태로 유도합니다.
   • 하이브리드 최적화: 펄스 모양은 경계 기반 및 경계 없는 최적화기를 결합한 하이브리드 최적화 전략을 사용하여 결정됩니다. 이 접근법은 저에너지 부분 공간에 도달하고, 국소 최소값을 탈출하며, 전역 최소값을 향해 미세 조정함으로써 최적화 지형을 탐색하는 것을 목표로 합니다.
   • 목적 함수: 최적화는 목표 해밀토니안에 대한 순간 상태의 기대값을 최소화하면서, 충실도 및 근사 비율을 모니터링합니다.

3. 난이도 매개변수 정의:
   서로 다른 문제 인스턴스의 난이도를 정량화하고 비교하기 위해 저자들은 일반화된 방법 독립적 난이도 매개변수 ($H_{PMI}$) 를 도입합니다. 이 매개변수는 다음을 통합합니다:

   • 바닥 상태와 첫 번째 들뜬 부분 공간 사이의 스펙트럼 갭 ($G_\Delta$).
   • 바닥 상태의 축퇴도 ($D_{opt}$) 와 위협적인 비최적 부분 공간의 축퇴도 ($D_\alpha$).
   • 문제의 에너지 규모 ($|E_{opt}|$).
     이 매개변수는 작은 갭, 비최적 상태에서의 높은 축퇴도, 또는 많은 수의 "위협적인" 부분 공간을 가진 문제들이 계산적으로 해결하기 더 어렵다고 가정합니다.

주요 결과
저자들은 세슘 Rydberg 원자 ($60S_{1/2}$) 를 사용하여 일곱 가지 문제 유형의 전형적인 인스턴스 (일반적으로 3~5 개의 변수 포함) 에 대해 제안된 방식을 수치적으로 시뮬레이션했습니다.

• 성능 지표: 프로토콜은 대부분의 문제에서 약 0.98 에서 0.999 범위의 높은 근사 비율 ($R$) 을 달성했습니다.
  • 높은 충실도: 두 가지 SAT (좌절이 없는) 및 이진 클러스터링 (Rydberg 해밀토니안 구조에 고유한) 과 같은 유리한 구조를 가진 문제들은 약 1.0 에 근접하는 근사 비율 ($R \sim 0.999$ 및 $R \sim 1.0$) 을 달성했습니다.
  • 어려운 인스턴스: 더 복잡하거나 "비-고유 (non-native)"인 문제들은 더 낮은 충실도를 보였습니다. 단백질 접힘 인스턴스 (HP 모델) 는 평평한 에너지 지형과 기하학적 제약으로 인해 $R \sim 0.98$의 근사 비율과 $\sim 0.97$의 충실도를 보였습니다. 이차 할당 문제 (QAP) 도 이차적 변수 스케일링과 축퇴도로 인해 $R \sim 0.9985$로 감소된 충실도를 보였습니다.
• 난이도 분석: 계산된 난이도 매개변수 ($H_{PMI}$) 는 시뮬레이션 결과와 상관관계를 보였습니다. 단백질 접힘은 작은 스펙트럼 갭 ($0.08$) 과 상당한 비최적 축퇴도로 인해 가장 높은 난이도 ($H_{PMI} \approx 307.81$) 를 보였습니다. 반면, XOR-SAT 와 집합 패킹은 각각 $1.13$과$4.79$의 더 낮은 난이도 값을 보였으며 더 큰 스펙트럼 갭과 일치하는 더 높은 정확도로 해결되었습니다.
• 프로토콜 동역학: 결과는 더 쉬운 문제들의 경우 여러 최적 프로토콜이 존재함을 나타냈습니다. 더 어려운 문제들의 경우, 최적화 지형은 더 정교한 펄스 모양 (예: 중첩된 라비 피크) 과 수렴을 위한 더 많은 반복을 필요로 했습니다.

의의 및 주장
저자들은 이 작업이 다항 시간 해결 가능 사례부터 NP-hard 문제에 이르기까지 다양한 조합 최적화 문제를 단일 물리적 아키텍처 내에서 처리할 수 있는 통합 프레임워크를 입증한다고 주장합니다.

• 자원 효율성: 주요 의의는 부호화 방식의 선형 오버헤드에 있습니다. 변수 수에 대해 이차적으로 스케일링되는 차단 기반 접근법과 달리, 이 국소 광 이동 접근법은 선형적으로 스케일링되어 제한된 큐비트 수를 가진 근미래 양자 장치에 더 적합합니다.
• 유연성: 국소 디튜닝의 사용은 서로 다른 문제 유형에 대해 별도의 부호화 방식을 요구하지 않고 문제별 제약을 구현할 수 있게 합니다.
• 벤치마킹 도구: $H_{PMI}$ 난이도 매개변수의 도입은 특정 제어 방법과 무관하게 양자 어닐링에 대한 QUBO 문제의 난이도를 예측하기 위해 QUBO 문제의 스펙트럼 특성을 분석하는 도구를 제공합니다.
• 확장성 잠재력: 현재 결과는 작은 인스턴스에 대한 원리 증명이지만, 이 프레임워크는 게이트 기반 양자 방법에 대한 벤치마크를 제공하는 Rydberg 기반 아날로그 양자 최적화기를 위한 확장 가능한 다음 단계로 제시됩니다.

본 논문은 이 접근법이 유망함을 보여주지만, 노이즈에 대한 견고성과 더 크고 복잡한 인스턴스에서의 성능을 평가하기 위해서는 추가 조사가 필요하다고 결론지었습니다.