⚛️ quantum physics

Optimizing QAOA circuit transpilation with parity twine and SWAP network encodings

이 논문은 고정 레이아웃 양자 하드웨어에서 QAOA 회로 트랜스파일링을 최적화하기 위해 패리티 트와인 체인(parity twine chains)과 SWAP 네트워크의 인코딩 오버헤드를 크게 줄임으로써, 표준 트랜스파일러에 비해 회로 깊이와 2-큐비트 게이트 수를 실질적으로 감소시키는 시뮬레이티드 어닐링 기반의 방법을 소개한다.

원저자: J. A. Montanez-Barrera, Yanjun Ji, Michael R. von Spakovsky, David E. Bernal Neira, Kristel Michielsen

게시일 2026-08-12

📖 3 분 읽기🧠 심층 분석

CC BY 4.0

원저자: J. A. Montanez-Barrera, Yanjun Ji, Michael R. von Spakovsky, David E. Bernal Neira, Kristel Michielsen

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

당신이 모든 손님이 언젠가는 서로의 손을 잡아야 하는 특별한 루틴을 수행하기 위해, 모든 손님이 서로의 손을 잡아야 하는 거대하고 혼란스러운 댄스 파티를 조직하려고 한다고 상상해 보십시오. 이제, 그 댄스 플로어가 좁은 일렬 행렬 형태의 복도라고 상상해 보십시오. 이 복도에서 사람들은 바로 옆에 있는 사람과만 손을 잡을 수 있습니다. 만약 손님 A가 줄의 맨 끝에 있는 손님 Z와 손을 잡아야 한다면, 군중 사이를 가로질러 손을 뻗을 수 없습니다. 그들은 이웃이 될 때까지 줄 사이를 비집고 들어가 자리를 바꾸고 움직여야 합니다. 이 움직임에는 시간이 걸리며, 두 사람이 위치를 바꾸기 위해 서로 부딪힐 때마다 발이 걸려 넘어지거나, 손을 놓치거나, 루틴을 망칠 가능성이 있습니다. 양자 컴퓨팅의 세계에서, 이 댄스 플로는 양자 칩이며, 손님들은 큐비트라고 불리는 작은 입자들입니다. 그리고 이 "넘어지는 것"은 계산을 망치는 일종의 오류입니다. 과학자들은 특히 현재의 칩들이 그 좁은 복도와 같아서 모든 이들을 서로 직접 연결할 수 없기 때문에, 큐비트들이 서로 엉키지 않고 효율적으로 소통하게 만드는 방법을 끊임없이 연구하고 있습니다.

이 논문은 그 춤을 위한 최적의 안무를 찾는 것에 관한 것입니다. 연구진은 QAOA라고 불리는 특정 알고리즘에 집중했는데, 이는 그룹을 두 팀으로 나누는 최적의 방법을 찾는 것과 같은 복잡한 퍼즐을 해결하는 데 사용됩니다. 이를 좁은 1차원 칩에서 구현하기 위해, 그들은 "트랜스파일레이션(transpilation)"이라는 기술을 사용해야 했습니다. 이는 하드웨어가 명령을 이해할 수 있도록 명령어를 재배열하는 것을 뜻하는 멋진 표현입니다. 그들은 셔플링(shuffling)을 테스트하기 위해 두 가지 주요 방식을 사용했습니다. 하나는 "SWAP 네트워크"로, 이는 모든 사람이 단계별로 움직이는 표준적이고 조직적인 라인 댄스와 같습니다. 다른 하나는 더 새롭고 까다로운 방식인 "패리티 트와인 체인(Parity Twine Chains, PTC)"인데, 이는 공간을 절약하기 위해 두 무용수의 정보를 한 사람의 움직임 속에 인코딩하는 것과 같습니다. 저자들은 또한 새로운 "시뮬레이티드 어닐링(simulated annealing)" 기법을 발명했는데, 이는 가장 적은 움직임이 필요한 시작 라인업을 찾기 위해 수천 번의 시행착오를 거치는 똑똑한 코치와 같습니다.

연구팀은 작고 희소한 퍼즐의 경우, IBM과 같은 기업들이 사용하는 표준 컴퓨터 프로그램들이 움직임을 최소화하는 데 상당히 효과적이었다는 것을 발견했습니다. 하지만 퍼즐이 커지고 큐비트 간의 연결이 빈번해짐에 따라, 그들의 새로운 방식들이 빛을 발하기 시작했습니다. 그들은 스마트한 코치를 사용하여 큐비트의 시작 순서를 재배열함으로써, 큐비트가 자리를 바꿔야 하는 횟수를 크게 줄일 수 있었습니다. 25%의 연결성을 가진 거대한 120-큐비트 퍼즐의 경우, 그들의 방식은 표준 IBM 소프트웨어와 비교했을 때 회로 깊이(실행 시간)를 87% 줄였고, 2-큐비트 게이트(위험한 동작)를 29% 줄였습니다. 그들은 또한 "ibm fez"와 "ibm kingston" 장치를 포함한 실제 양자 컴퓨터에서도 이를 테스트했습니다. "ibm fez"에서 그들은 PTC 방식을 사용하여 20-큐비트 문제의 완벽한 해답을 찾아낸 반면, 표준 방식은 15-큐비트까지만 작동했습니다. 흥 흥미롭게도, "ibm kingston" 장치에서는 특정 유형의 문제에 대해 표준 SWAP 방식이 PTC 방식보다 약간 더 나은 성능을 보였는데, 이는 때때로 움직임의 횟수를 줄이는 것만이 전부가 아니며, 정보가 어떻게 인코딩되는지가 그만큼 중요하다는 것을 시사합니다. 연구진은 자신들의 방법이 오류를 줄이고 시간을 절약하는 강력한 도구이긴 하지만, 모든 시나리오에서 완벽하게 작동하는 마법의 탄환은 아니며, 최선의 선택은 문제의 구체적인 형태와 하드웨어의 특성에 달려 있다고 제안합니다.

기술 요약: Parity Twine 및 SWAP 네트워크 인코딩을 통한 QAOA 회로 트랜스파일 최적화

문제 정의
현재의 초전도 양자 프로세서(QPU)는 특정 토폴로지(예: heavy-hex 격자)에서 인접한 이웃 간의 상호작용만을 제한하는 제한된 큐비트 연결성 문제를 겪고 있습니다. QAOA(Quantum Approximate Optimization Algorithm)와 같은 알고리즘을 실행하려면 종종 완전 연결(fully connected) 또는 조밀한(dense) 2-큐비트 상호작용이 필요하며, 이는 트랜스파일링 과정을 필수로 합니다. 이 과정은 논리적 큐비트를 물리적 큐비트에 매핑하고, 연결성 제약을 충족하기 위해 SWAP 게이트를 삽입합니다. 그러나 SWAP 게이트는 여러 개의 2-큐비트 게이트(예: 3개의 CNOT)로 분해되며, 이는 근미래 장치에서 노이즈와 오류의 주요 원인이 됩니다. SWAP 네트워크 및 Parity Twine Chains(PTC)와 같은 구조화된 인코딩 방식은 완전 연결 그래프에 대해서는 분석적인 자원 이점을 제공하지만, 희소하게 연결된(non-fully connected) 그래프에 대한 적용은 여전히 최적화 수준이 낮습니다. 또한, 게이트 수를 최소화하기 위한 최적의 초기 큐비트 매핑을 찾는 것(부분 그래프 동형 문제, subgraph isomorphism problem)은 NP-hard 문제입니다. 기존의 솔버인 SATMapper는 대규모 시스템에서 확장성 및 실행 시간 측면에서 한계를 보입니다.

방법론
저자들은 구조화된 인코딩 전략과 시뮬레이티드 어닐링(Simulated Annealing, SA) 휴리스틱을 결합한 하이브리드 접근 방식을 제안합니다.

인코딩:
- SWAP 네트워크: 1D 체인 상의 구조화된 라우팅 스케줄로, 교차하는 층(layer)의 인접 이웃 SWAP 게이트를 통해 논리적 큐비트를 이동시켜 필요한 인접성을 생성합니다.
- Parity Twine Chains (PTC): 다중 큐비트 Z-정보를 패리티(parity)를 통해 단일 물리적 큐비트로 인코딩하는 방법입니다. 이를 통해 비국소적 상호작용을 로컬 단일 큐비트 회전( $R_Z$ )으로 실행할 수 있어, SWAP 네트워크에 비해 2-큐비트 게이트 수를 줄일 수 있습니다. 이 방법은 측정값이 패리티 기저(parity basis)에서 이루어지고, 고전적 사후 처리(classical post-processing)를 통해 논리적 비트 문자열을 복구하는 디코딩 전략을 활용하며, 계산 기저로 돌아가기 위한 추가적인 CNOT 게이트가 필요하지 않습니다.
시뮬레이티드 어닐링 (SA) 최적화:
- 저자들은 SWAP 및 PTC 인코딩을 위한 부분 그래프 동형 문제를 해결하기 위해 SA 기반 알고리즘을 도입합니다.
- 비용 함수(Cost Function): 비용 함수는 조합론적이며 비매끄러운(non-smooth) 형태로, 회로에서 제거(pruning)할 수 있는 2-큐비트 게이트의 수를 평가합니다. 이는 레이어별로 매핑된 큐비트 쌍이 하드웨어 결합 그래프의 네이티브 에지(native edge)에 해당하는지 확인합니다. 만약 요구되는 상호작용이 문제 그래프에 존재하지 않으면, 인코딩 스케줄의 해당 게이트는 생략됩니다.
- 프로세스: 알고리즘은 큐비트 레이블 쌍을 반복적으로 교체하여 전체 2-큐비트 게이트 수와 회로 깊이를 최소화하는 순열(permutation)을 찾습니다. 이 접근 방식은 이산적 탐색 공간(discrete search space)에 적합하지 않은 경사 하강법(gradient-based methods)이나 계산 비용이 너무 큰 정확한 방법 대신 선택되었습니다.
벤치마킹 및 노이즈 모델링:
- 본 방법론은 표준 트랜스파일러(Qiskit-T, Qiskit-P, Qiskit-AI, TKET) 및 SATMapper와 벤치마킹됩니다.
- 노이즈 시뮬레이션은 가중치 최대 컷(Weighted MaxCut, WMC) 문제를 위한 Linear Ramp QAOA (LR-QAOA) 프로토콜 내의 2-큐비트 게이트에 작용하는 데포럴링(depolarizing) 노이즈 모델을 사용합니다.
- 실험적 검증은 IBM 양자 장치(ibm_fez 및 ibm_kingston)에서 수행됩니다.

주요 기여

SA 최적화 인코딩: 희소하게 연결된 그래프를 구체적으로 타겟팅하여, SWAP 및 PTC 인코딩을 위한 초기 큐비트 순서를 최적화하는 시뮬레이티드 어닐링 전략을 도입했습니다.
확장성: SA 접근 방식이 200 큐비트 규모의 시뮬레이션까지 효과적으로 확장됨을 입증하였으며, SATMapper에 비해 수 차수의 실행 시간 이점을 제공하면서도 대등한 솔루션 품질을 달 수 있음을 보여주었습니다.
PTC 디코딩: 계산 기저로 되돌리기 위한 회로 깊이를 증가시키는 CNOT 게이트가 필요 없는 PTC 디코딩 전략을 상세히 기술했습니다.
실험적 검증: 실제 양자 하드웨어에서 PTC 인코딩을 구현한 첫 번째 사례입니다.

결과

게이트 수 및 깊이 감소: 에지 밀도( $E_d$ $E_{d}$ )가 특정 임계값을 초과하는 QAOA 회로의 경우, PTC+SA 및 SWAP+SA는 표준 트랜스파일러보다 성능이 월등히 뛰어납니다.
- 25% 연결성을 가진 120-큐비트 인스턴스의 경우, 제안된 방법은 Qiskit 트랜스파일러(최적화 레벨 3) 대비 회로 깊이를 87% 감소시키고 2-큐비트 게이트를 29% 감소시켰습니다.
- PTC+SA가 Qiskit-T보다 게이트 수 측면에서 우위를 점하는 임계값은 시스템 크기가 커짐에 따라 감소합니다 (20 큐비트의 경우 $E_d \approx 0.35$ , 120 큐비트의 경우 $E_d \approx 0.13$ ).
실행 효율성: SA 방법은 200-큐비트 문제에 대해 몇 초 안에 고품질 솔루션에 수렴하는 반면, SATMapper는 수백에서 수천 초가 소요됩니다.
노이즈 탄력성:
- 시뮬레이션: 노이즈 시뮬레이션에서 PTC는 더 적은 게이트 수 덕분에 낮은 수준에서 중간 수준의 노이즈 환경에서 SWAP보다 높은 성공 확률( $p_{gs}$ )을 보였으나, 근사 비율( $r$ )은 두 방식 모두 유사했습니다.
- 실제 하드웨어 (ibm_fez): PTC 인코딩은 유용한 LR-QAOA 실험의 범위를 확장했습니다. PTC를 사용하면 20 큐비트 크기까지 최적의 솔루션을 찾을 수 있었던 반면, SWAP은 15 큐비트까지만 가능했습니다. 무작위 샘플링과의 차이는 PTC의 경우 22 큐비트까지, SWAP의 경우 20 큐비트까지 유지되었습니다.
- 실제 하드웨어 (ibm_kingston): $E_d = 0.298$ 인 20-큐비트 문제에 대해, SWAP+SA가 가장 좋은 근사 비율(무작위 대비 20.83% 개선)을 달성하여 PTC+SA(13.99%)를 앞질렀습니다. 저자들은 PTC가 더 적은 게이트를 사용함에도 불구하고, 비완전 연결 시나리오에서는 논리적 쌍을 단일 물리적 큐비트로 인코딩하는 방식이 노이즈 축적에 더 민감할 수 있다고 언급했습니다.
트랜스파일러 비교: 표준 트랜스파일러(예: Qiskit-T)는 종종 게이트 수를 최소화하는 대신 회로 깊이를 크게 증가시키며, 이는 노이즈를 악화시킵니다. 제안된 방법들은 컴팩트한 회로와 낮은 깊이를 유지합니다.

의의 및 주장
본 논문은 줄어든 큐비트 연결성 시나리오에서 표준 트랜스파일러 방법을 능가하는 SWAP 및 PTC 인코딩을 제시한 첫 번째 시연이라고 주장합니다. 또한, 실제 양자 하드웨어에서 PTC 인코딩을 구현한 첫 번째 실험적 사례이기도 합니다.

저자들은 완전 연결 그래프를 위한 구조화된 인코딩은 잘 알려져 있지만, 제안된 SA 기반 최적화를 통해 부분 연결 그래프에 적용함으로써 상당한 자원 절감을 얻을 수 있음을 강조합니다. 결론적으로, 20 큐비트 시스템까지 PTC 인코딩은 실제 하드웨어에서의 성능을 개선하여 LR-QAOA의 실행 가능한 문제 크기를 확장합니다. 다만, 비완전 연결 실험(ibm_kingston)에서 SWAP+SA가 때때로 PTC+SA보다 우수했다는 점을 들어, 게이트 수와 노이즈 민감도 사이의 트레이드오프는 특정 인코딩 구조와 문제 토폴로지에 따라 크게 달라질 수 있음을 신중하게 언급했습니다. 이 연구는 오버헤드를 줄이면서 연결성이 제한된 근미래 장치에서 QAOA를 실행하기 위한 실질적인 경로를 구축합니다.

유사한 논문