A SWAP-free Framework for QAOA

본 논문은 하드웨어 호환성 비용 해밀토니안 선택과 큐비트 할당을 혼합 정수 반정부 계획법으로 공식화하는 SWAP 없는 QAOA 프레임워크를 제안하며, 이러한 하드웨어 인지 근사법이 희소 NISQ 장치에서 정밀하지만 잡음에 취약한 변환된 구현체보다 우수한 성능을 보일 수 있음을 입증합니다.

핵심

이 논문은 간단한 언어와 창의적인 비유를 사용하여 설명합니다.

큰 문제: 양자 도로 위의 '교통 체증'

거대한 퍼즐을 해결하기 위해 특수한 메신저 팀 (큐비트) 을 활용한다고 상상해 보세요. 이 메신저들은 도로가 매우 좁고 희소한 도시 (양자 컴퓨터) 에 살고 있습니다. 이 도시에서 메신저는 바로 옆 이웃과만 직접 대화할 수 있습니다. 도시 반대편에 있는 사람에게 소리를 지르며 대화할 수는 없습니다.

QAOA 알고리즘은 복잡한 최적화 퍼즐 (예: 최고의 투자 포트폴리오 찾기) 을 해결하는 유명한 방법입니다. 그러나 이 퍼즐은 종종 멀리 떨어진 메신저들이 서로 대화해야 하는 상황을 요구합니다.

표준 설정에서는 두 메신저가 대화해야 하지만 이웃이 아닐 때, 교통 통제관 (트랜스파일러) 이 SWAP 메신저를 보내 물리적으로 그들을 가까이 이동시킨 후 대화하게 하고 다시 원래 위치로 되돌려야 합니다.

• 문제점: 메신저를 이동할 때마다 'SWAP' 게이트가 추가됩니다. 이는 추가적인 신호등과 우회로를 설치하는 것과 같습니다. 오늘날의 잡음이 많은 양자 컴퓨터 (NISQ 장치) 에서는 매번 추가되는 단계가 메시지를 망가뜨리는 '잡음' (정적) 을 더합니다. 퍼즐이 크다면 SWAP 이 너무 많이 쌓여 답이 왜곡되어 쓸모없게 됩니다.

해결책: 교통을 개선하는 것이 아니라 퍼즐을 재설계하기

이 논문의 저자들은 급진적인 아이디어를 제안합니다: 메신저들이 도시 전체를 가로질러 대화하도록 강요하는 대신, 이웃끼리만 대화하면 되도록 퍼즐을 변경합시다.

이들은 이를 "SWAP 없는 프레임워크" 라고 부릅니다.

1. 오래된 방식: 퍼즐을 그대로 두고 모든 사람을 연결하기 위해 거대하고 잡음이 많은 SWAP 고속도로를 건설합니다.
2. 새로운 방식: 이미 연결된 이웃들 간의 상호작용만 요구하도록 퍼즐 (비용 해밀토니안) 을 약간 수정합니다.

트레이드오프: 퍼즐을 변경함으로써 원래의 정확한 질문을 해결하는 것이 아니라, 약간 다른 '근사' 버전을 해결하게 됩니다. 그러나 교통 체증 (SWAP) 을 제거했기 때문에 메신저들은 훨씬 더 빠르고 잡음이 적은 상태로 답을 전달할 수 있습니다. 저자들은 오늘날의 하드웨어에서는 정확하지만 messy 한 답보다 깔끔하고 근사적인 답이 종종 더 낫다고 발견했습니다.

실행 방법: '좌석 배치도' 알고리즘

이를 실현하기 위해 그들은 두 가지 문제를 동시에 해결해야 했습니다.

1. 퍼즐의 어떤 부분을 유지할 것인가? (어떤 상호작용이 유지될 만큼 중요한지, 어떤 것은 버려도 되는지)
2. 누가 어디에 앉을 것인가? (어떤 논리 변수가 어떤 물리 큐비트에 배치될지)

그들은 이를 혼합 정수 반정부 계획법 (Mixed-Integer Semidefinite Program, MISDP) 이라는 복잡한 수학 문제로 변환했습니다.

• 비유: 저녁 파티를 주최한다고 상상해 보세요. 특정 다른 손님들과 대화하고 싶어 하는 손님 목록 (퍼즐 변수) 이 있고, 옆에 앉은 사람들과만 대화할 수 있는 원형 테이블 (하드웨어) 이 있습니다.
• MISDP 는 파티 동안 아무도 이동시키지 않고 대화해야 하는 사람들이 서로 옆에 앉을 수 있도록 완벽한 좌석 배치도와 완벽한 손님 목록을 찾아내는 초지능 알고리즘입니다.

'마법' 같은 수학 및 단축키

이 논문은 완벽한 좌석 배치도를 찾는 것이 수학적으로 'NP-완전'이라서 극도로 어렵다고 증명합니다. 격자가 커질수록 기하급수적으로 어려워지는 스도쿠 퍼즐을 푸는 것과 같습니다.

실제 세계의 문제에 실용적으로 적용하기 위해 그들은 휴리스틱 (지능적인 단축키) 을 개발했습니다.

• 비유: 가능한 모든 좌석 배치를 시도하는 것 (영원히 걸릴 것임) 대신, 손님들의 '인기'를 살펴봅니다. 페로 고유벡터 (Perron Eigenvectors) 라는 수학적 도구를 사용하여 어떤 손님이 가장 '중심'적이거나 영향력이 있는지 파악합니다. 그런 다음 가장 중요한 손님들을 테이블에서 가장 연결된 자리 옆에 앉힙니다.
• 그들은 이러한 단축키를 작은 문제들에 테스트하여 슈퍼컴퓨터로 계산할 필요 없이 완벽한 해법에 매우 근접한 결과를 얻을 수 있음을 놀랍게도 발견했습니다.

결과: 실제로 작동할까?

저자들은 인덱스 추종 (Index Tracking) 이라는 실제 금융 문제 (더 큰 시장 지수를 모방하는 소수의 주식 그룹을 선택하는 것) 에 대해 그들의 방법을 테스트했습니다.

• 테스트: 그들은 SWAP 을 사용하지만 컴퓨터가 완벽하다고 가정하는 표준 방법 (이상적인 QAOA) 과 그들의 'SWAP 없는' 방법을 비교했습니다.
• 발견: 작은 문제에서는 표준 방법이 괜찮았습니다. 하지만 문제가 커질수록 (주식 수와 큐비트 수가 증가할수록), SWAP 에서 발생하는 잡음이 답을 압도하여 표준 방법은 실패했습니다.
• 승자: 문제를 약간 단순화한 버전을 해결했음에도 불구하고, 'SWAP 없는' 방법은 잡음이 많은 하드웨어에서 더 나은 결과를 산출했습니다.

결론

이 논문은 오늘날의 불완전한 양자 컴퓨터에서는 단순함이 승리한다고 주장합니다.

복잡하고 정확한 해결책을 희박하고 잡음이 많은 기계에 강요하는 것은 구덩이가 있는 흙길에서 포뮬러 1 카를 운전하려는 것과 같습니다; 차가 고장 납니다. 대신, 도로에 완벽하게 맞는 튼튼하지만 약간 느린 트럭 (수정된 해밀토니안) 을 운전하는 것이 더 낫습니다. 하드웨어가 문제에 맞춰지도록 강요하는 대신, 문제를 하드웨어에 맞도록 설계함으로써 다른 방법이 잡음만 주는 상황에서 쓸모 있는 답을 얻을 수 있습니다.

기술 요약

"A SWAP-free Framework for QAOA" (Assis 등) 논문에 대한 상세한 기술 요약입니다.

1. 문제 제기

양자 근사 최적화 알고리즘 (QAOA) 은 근미래 중규모 양자 (NISQ) 장치에서 2 차 무제약 이진 최적화 (QUBO) 문제를 해결하기 위한 주요 후보입니다. 그러나 현재 하드웨어 아키텍처의 희소한 큐비트 연결성으로 인해 성능이 심각하게 제한받고 있습니다.

• 병목 현상: QAOA 비용 해밀토니안에 필요한 상호작용이 양자 프로세서의 물리적 연결 그래프와 일치하지 않을 때, 양자 트랜스파일러는 큐비트를 라우팅하기 위해 SWAP 게이트를 삽입해야 합니다.
• 결과: SWAP 게이트는 회로 깊이를 크게 증가시키고 누적된 잡음 (오류) 을 유발하여, 종종 양자 우위가 상실될 정도로 솔루션 품질을 저하시킵니다. 이 문제는 문제 크기가 커짐에 따라 더욱 악화되어, 종종 2 차 함수에 비례하는 수의 SWAP 게이트가 필요합니다.
• 목표: 원래 목적 함수를 근사화할지라도 "하드웨어 네이티브"가 되도록 문제 형식을 수정함으로써 QAOA 의 비용 계층에서 SWAP 게이트의 필요성을 제거하는 프레임워크를 개발하는 것입니다.

2. 방법론

저자들은 후처리 컴파일 문제로 간주하는 대신 하드웨어 토폴로지 제약을 문제 설계에 직접 통합하는 SWAP-free QAOA 프레임워크를 제안합니다.

A. 핵심 개념: 해밀토니안 수정

원래 비용 해밀토니안 ($H_C$) 을 하드웨어에 맞게 트랜스파일링하는 대신, 이 프레임워크는 비용 행렬 $C$를 새로운 행렬 $\tilde{C}$로 수정합니다.

• 제약 조건: $\tilde{C}$는 하드웨어 그래프 $G$에서 직접 연결된 큐비트 쌍에 대해서만 0 이 아닌 항을 가져야 합니다.
• 트레이드오프: 이는 회로가 SWAP-free 가 되도록 보장하지만, 원래 문제에 비해 근사 오차를 도입합니다. 목표는 하드웨어 호환성을 극대화하면서 이 오차를 최소화하는 것입니다.

B. 수학적 형식화 (MISDP)

최적의 $\tilde{C}$와 논리 변수를 물리 큐비트에 매핑하는 최적의 매핑을 찾는 문제는 **혼합 정수 반정부 계획법 (Mixed-Integer Semidefinite Program, MISDP)**으로 형식화됩니다.

• 변수:
  • $\lambda$: 원래 목적 함수와 수정된 목적 함수 간의 편차를 경계 짓는 스칼라.
  • $X$: 수정된 비용 행렬.
  • $P$: 논리 큐비트를 물리 큐비트에 매핑하는 순열 행렬.
• 목적 함수: $X$가 원래 행렬 $\hat{C}$에 가깝고, $X$가 하드웨어 그래프 $G$(순열 $P$에 의해 순열됨) 에 간선이 없는 곳에 0 을 갖도록 하는 제약 조건 하에서 $\lambda$를 최소화합니다.
• 이론적 보장:
  • 이 문제의 결정 버전은 NP-완전임이 증명되었습니다.
  • 저자들은 하드웨어 그래프의 **Lovász 수 ($\vartheta(G)$)**를 사용하여 원래 최적화 문제에서의 손실에 대한 이론적 경계를 유도하며, MISDP 목적 함수 값과 근사 품질 간의 관계를 규명했습니다.

C. 휴리스틱 솔루션

MISDP 를 푸는 것은 대규모 인스턴스의 경우 계산적으로 불가능하므로, 저자들은 순열 행렬 $P$를 사전에 고정하여 문제를 표준 반정부 계획법 (SDP) 으로 축소하는 스펙트럴 휴리스틱을 제안합니다.

• Perron 기반 휴리스틱: 하드웨어 인접 행렬과 문제 행렬의 주 고유벡터 (Perron 벡터) 를 활용하여 정점을 순위 매깁니다.
  • 비연결 (Disconnected): 연결성 확인 없이 가장 높은 중심성 인덱스를 가장 높은 중심성 큐비트에 매핑합니다.
  • 연결 (Connected): 가장 중요한 인덱스를 하드웨어의 성장하는 연결 부분 그래프에 할당하는 탐욕 알고리즘으로, 매핑된 영역이 연결된 상태를 유지하도록 보장합니다.
• 라플라시안 기반 휴리스틱: 라플라시안 행렬의 고유벡터를 사용하는 유사한 접근법입니다.
• 무작위 기준: 비교를 위해 사용된 무작위 순열 (연결 및 비연결 모두 포함).

D. 적용 사례: 인덱스 추종

이 프레임워크는 k-medoids 클러스터링 기법에서 파생된 카디널리티 제약 2 차 최적화 문제에 적용하여 금융 인덱스 추종에 테스트되었습니다.

• 문제: 다양성 제약을 만족하면서 금융 인덱스를 추종하는 $k$개의 자산 부분집합을 선택합니다.
• 하드웨어 적응: 저자들은 XY-mixer($H_M$) 와 Dicke 상태 초기화 ($|D_n^k\rangle$) 를 사용하여 해밀토니안의 페널티 항 없이 $k$-여기 부분공간 내에서 카디널리티 제약 ($1^T x = k$) 을 자연스럽게 강제합니다.

3. 주요 기여

1. SWAP-Free 프레임워크: 하드웨어 토폴로지에 네이티브가 되도록 비용 해밀토니안을 수정하여 비용 계층에서 SWAP 게이트를 제거하는 새로운 접근법.
2. MISDP 형식화: 비용 행렬 근사와 큐비트 할당 (순열) 을 동시에 최적화하는 엄밀한 수학적 형식화.
3. 이론적 경계: 결정 문제에 대한 NP-완전성 증명 및 근사 오차를 하드웨어 그래프의 Lovász 수와 연결하는 성능 보장 유도.
4. 스펙트럴 휴리스틱: 순열 행렬을 효율적으로 고정하여 프레임워크가 더 큰 문제 인스턴스로 확장될 수 있도록 하는 실용적 알고리즘 (Perron 및 라플라시안 기반).
5. 실증적 검증: 희소한 NISQ 아키텍처에서 SWAP 게이트로 인한 잡음에 시달리는 정확한 구현보다 근사적이지만 SWAP-free 인 구현이 더 우수한 성능을 보임을 입증.

4. 결과

저자들은 SWAP 게이트로 인한 잡음 (소멸 채널을 통해 모델링됨) 을 겪는 "이상적인" QAOA 실행을 나타내는 기준선과 자신의 접근법을 비교했습니다.

• 소규모 인스턴스 ($n=8$):
  • Perron Connected 및 Perron Disconnected 휴리스틱이 일반적으로 무작위 전략보다 우수한 성능을 보였습니다.
  • 흥미롭게도 MISDP 목적 함수 ($\lambda$) 를 최소화하는 것이 최종 솔루션의 최적성 격차를 최소화하는 것과 항상 완벽하게 상관관계가 있는 것은 아니었습니다. 이는 다항 시간 휴리스틱이 MISDP 완화 문제를 완벽하게 해결하지 않더라도 거의 최적의 결과를 얻을 수 있음을 시사합니다.
• 대규모 인스턴스 ($n > 20$):
  • SWAP-free 휴리스틱 (특히 Perron Connected) 은 SWAP 기반 기준선보다 현저히 우수한 성능을 보였습니다.
  • 문제 크기 $n$이 증가함에 따라 필요한 SWAP 게이트의 수가 2 차 함수에 비례하여 증가하여, 표준 접근법에서의 잡음이 솔루션 품질을 압도하게 되었습니다.
  • SWAP-free 접근법은 근사 해밀토니안을 사용했음에도 불구하고, 회로 깊이와 오차 누적이 극적으로 감소했기 때문에 더 높은 솔루션 충실도를 유지했습니다.

5. 의의

이 논문은 QAOA 가 반드시 정확한 문제 해밀토니안을 보존해야 한다는 통념에 도전합니다. 희소한 NISQ 아키텍처에서는 정확한 구현의 이점보다 트랜스파일링 (SWAP 게이트) 의 비용이 더 크다는 것을 보여줍니다.

• 패러다임 전환: 문제를 기계에 강제로 적응시키는 대신, 목적 함수를 기계에 맞게 조정하는 "하드웨어 인식" 문제 형식을 옹호합니다.
• 실질적 영향: 현재 양자 하드웨어에서의 포트폴리오 최적화와 같은 실제 응용 분야에 대해, 약간 부정확하지만 잡음에 강한 회로가 정확하지만 잡음으로 황폐화된 회로보다 우월함을 시사합니다.
• 향후 방향: 이 프레임워크는 다른 QUBO 문제 (예: MAXCUT) 로 일반화될 수 있으며, 스펙트럴 휴리스틱과 지역 탐색을 결합하거나 실제 양자 하드웨어에서 잡음 모델을 검증하기 위한 길을 엽니다.