⚛️ quantum physics

SSR: A Swapping-Sweeping-and-Rewriting Optimizer for Quantum Circuit Transformation

본 논문은 NISQ 장치에서의 양자 회로 변환 깊이를 크게 줄이기 위해 회로 재배열을 위한 유전 알고리즘, CNOT 서브회로 추출을 위한 스위핑 기법, 그리고 깊이 최적화된 리라이팅을 위한 SAT 솔버를 결합한 새로운 최적화 도구인 SSR을 제안한다.

원저자: Yunqi Huang, Xiangzhen Zhou, Fanxu Meng, Pengcheng Zhu, Yu Luo, Zhenlong Du

게시일 2026-06-23

📖 3 분 읽기🧠 심층 분석

CC BY 4.0

원저자: Yunqi Huang, Xiangzhen Zhou, Fanxu Meng, Pengcheng Zhu, Yu Luo, Zhenlong Du

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

도시 전체에 드론 함대를 이용해 메시지를 보내려고 한다고 상상해 보십시오. 하지만 여기에는 함정이 있습니다. 드론들은 바로 옆에서 비행하고 있을 때만 서로 통신할 수 있습니다. 만약 두 드론이 물건을 교환해야 하는데 도시의 반대편에 있다면, 제3의 드론을 보내 메시지를 앞뒤로 물리적으로 실어 날라야 합니다. 양자 컴퓨팅의 세계에서는 정확히 이런 일이 일ขึ้น합니다.

문제점: "우회" 교통 체증
양자 컴퓨터(특히 현재의 노이즈가 있는 NISQ 장치들)는 매우 엄격한 교통 규칙이 있는 도시와 같습니다. 이들의 "드론"(큐비트)은 물리적으로 연결되어 있을 때만 상호작용할 수 있습니다. 과학자들이 양자 프로그램을 설계할 때, 종종 모든 드론이 즉각적으로 서로 통신할 수 있다고 가정하곤 합니다. 이를 실제 하드웨어에서 작동하게 만들기 위해, **양자 회로 변환(QCT)**이라는 과정이 사용됩니다.

QCT를 드론들이 서로 가까워져서 상호작용할 수 있도록 위치를 바꾸는 "SWAP" 게이트를 삽입하는 교통 관제사라고 생각해 보십시오. 이 SWAP 게이트는 드론들이 위치를 바꿔야 하는 우회로와 같습니다. 이 과정이 연결성 문제를 해결해주기는 하지만, 거대한 교통 체증을 만들어냅니다. 회로는 훨씬 더 길어지며(깊어지며), 양자 신호는 매우 취약하기 때문에 여정이 길어질수록 메시지가 왜곡되거나 손실될 가능성이 높아집니다.

해결책: SSR (Swapping, Sweeping, and Rewriting)
이 논문의 저자들은 초기 우회로가 추가된 후 이 교통 체증을 정리하기 위한 새로운 도구인 SSR을 제안합니다. 이들은 매우 효율적인 교통 최적화 팀처럼 작동하는 3단계 전략을 사용합니다.

Swapping (유전 알고리즘):
교통 관제사가 드론들을 연결하기 위해 무작위 순서로 던져 놓았다고 상상해 보십시오. SSR은 유전 알고리즘을 사용하는데, 이는 디지털 진화 시뮬레이터와 같습니다. SSR은 "우회로"(SWAP)를 시퀀스의 앞이나 뒤로 옮기는 것이 전체 여정을 더 단축시키는지 확인하기 위해 드론의 순서(게이트)를 섞는 수천 가지의 다른 방법들을 시도합니다. 마치 자연이 가장 적합한 형질을 선택하듯, 가장 좋은 배치들을 남기고 나쁜 배치들은 버립니다.
Sweeping (스캐너):
순서가 최적화되면, SSR은 회로 전체를 쓸고 지나가는 진공청소기처럼 작동합니다. SSR은 서로 뭉쳐 있는 "CNOT" 게이트(특정 유형의 양자 상호작용)의 클러스터를 찾아냅니다. 그리고 이 클러스터들을 개선하기 딱 좋은 "서브 회로"로 식별합니다.
Rewriting (스마트한 설계자):
이 부분이 가장 강력한 부분입니다. 각 클러스터에 대해, SSR은 단순히 그것을 고치려고 노력하는 것이 아니라, 매우 똑똑한 "설계자"(SAT 솔버)에게 동일한 작업을 수행하면서도 단계는 더 적게 걸리는 완전히 새로운 수학적으로 완벽한 버전의 클러스터를 설계하도록 요청합니다.

함정: 만약 설계자가 완벽한 클러스터를 설계했지만, 그것이 다음 단계를 방해하는 위치에 배치한다면 전체 여정이 더 길어질 수 있습니다. 이를 방기하기 위해 SSR은 **"게이트 위치 제약(Gate Position Constraining)"**을 사용합니다. 이는 설계자에게 "완벽한 클러스터를 설계하되, 다른 드론들을 방해하지 않도록 특정 시간과 공간 경계 내에서 구축해야 한다"라고 지시하는 것과 같습니다.
속도 향 향상: 설계자에게 매번 처음부터 다시 시작하도록 요청하는 것은 느립니다. 따라서 SSR은 수백만 개의 사례를 학습한 인공 신경망(ANN)—일종의 AI—을 사용하여, 설계자에게 요청하기 전에 최적의 단계 수를 예측합니다. 이는 설계자에게 "1단계부터 시작하지 말고, 먼저 5단계로 만들어보라"고 알려주는 지름길 역할을 하여 시간을 크게 절약해 줍니다.

결과: 더 맑은 도로
논문은 다양한 양자 회로와 다양한 하드웨어 레이아웃(Google의 Sycamore 및 IBM 프로세서 등)을 대상으로 SSR 도구를 테스트했습니다.

결과: 기존 방식들과 비교했을 때, SSR은 회로의 "깊이"(총 이동 시간)를 평균 16.59% 줄였으며, 일부 회로에서는 무려 **29.04%**까지 개선되었습니다.
비교: 다른 도구들도 교통 체증을 해결하려고 시도했지만, 종종 상황을 악화시키거나 아주 약간의 개선만을 이루어냈습니다. SSR은 일관되게 더 매끄러운 경로를 찾아냈습니다.
효율성: 이미 표준 소프트웨어(Qiskit 등)에 의해 최적화된 회로라 할지라도, SSR은 여전히 10%의 추가 효율을 짜낼 수 있었습니다.

요약
SSR은 실제 기기의 제한 사항에 맞춰 강제로 조정된 양자 회로를 재배열하는 사후 최적화 도구입니다. SSR은 작업의 순서를 섞고, 단순화할 수 있는 단계들의 그룹을 찾아내며, 새로운 교통 체증을 유발하지 않고 그들을 재구축하는 최선의 방법을 예측하기 위해 AI를 사용합니다. 그 결과, 노이즈로 인해 실패할 가능성이 더 낮은, 더 빠르고 신뢰할 수 있는 양자 계산을 구현합니다.

기술 요약: SSR: 양자 회로 변환을 위한 스와핑-스위핑-및-리라이팅(Swapping-Sweeping-and-Rewriting) 최적화 도구

문제 정의
양자 회로 변환(QCT)은 논리적 양자 회로를 노이즈가 있는 중간 규모 양자(NISQ) 장치의 물리적 연결성 제약에 적응시키기 위해 필요한 과정이다. 이러한 제약을 충족하기 위해, QCT 알고리즘은 일반적으로 다수의 CNOT 게이트로 분해되는 수많은 SWAP 게이트를 삽입하며, 이는 회로 깊이(depth)를 증가시킨다. 이렇게 증가된 깊이는 오류율을 악화시키고 양자 계산의 성공 확률을 낮춘다. 기존의 사후 QCT 최적화 기법들이 존재하지만, 이들은 깊이를 충분히 최소화하지 못하거나, 연속적인 CNOT 및 SWAP 게이트의 급증과 같은 QCT 과정에서 발생하는 구조적 비효율성을 구체적으로 해결하지 못하는 경우가 많다. 저자들은 하드웨어 연결성 제약을 준수하면서 회로 깊이를 효과적으로 줄일 수 있는 전용 사후 QCT 최적화 프레임워크의 필요성을 식별하였다.

방법론
본 논문은 QCT 생성 회로의 깊이를 줄이기 위해 설계된 통합 최적화 프레임워크인 **SSR (Swapping-Sweeping-and-Rewriting)**을 제안한다. 이 방법론은 세 가지 핵심 단계로 구성된 반복 루프를 통해 작동한다:

스와핑 (유전 알고리즘 기반 커뮤테이션):
리라이팅(rewriting)을 수행하기 전, 프레임워크는 SWAP과 CNOT 게이트 사이의 일반화된 커뮤테이션 규칙을 탐색하기 위해 유전 알고리즘(GA)을 사용한다. GA는 유효한 게이트 스와프 시퀀스를 솔루션 공간으로 취급하여, 전체 깊이를 줄이고 후속 최적화에 더 유리한 서브회로 구조를 생성하도록 회로 모집단을 진화시킨다. 결정적으로, GA는 커뮤테이션 과정 중에 하드웨어 연결성 제약을 강제하여, 생성된 모든 후보 회로가 대상 아키텍처에 대해 유효함을 보장한다.
스위핑 (서브회로 추출 및 스코어링):
프레임워크는 회로를 스캔하여 CNOT과 SWAP 게이트로 구성된 연속적인 서브회로를 추출한다. 계산 복잡도를 관리하기 위해 추출된 서브회로에 최대 큐비트 제한( $n_q$ )을 부과한다. 스코어링 함수는 각 서브회로의 잠재적인 깊이 감소량을 평가한다. 이 점수는 현재 깊이와 최적의 서브회로 깊이 사이의 차이를 추정한다. 모든 후보에 대해 정확한 합성을 수행하는 것의 계산적 불가능성을 피하기 위해, 저자들은 CNOT 회로의 불리언 행렬 표현(Boolean matrix representation)을 학습한 지도 학습 기반 인공 신경망(ANN)을 활용하여 최적 깊이를 예측한다. 이 예측은 모든 서브회로를 동시에 리라이팅하는 대신, 가장 높은 점수를 받은 서브회로를 선택하여 리라이팅하도록 안내하며, 저자들은 이것이 글로벌 최적화를 방해할 수 있는 조기 국소 구조 고착(premature fixation of local structures)을 방지한다고 주장한다.
리라이팅 (제약 조건이 포함된 SAT 기반 합성):
선택된 서브회로는 불리언 만족도(SAT) 솔버를 사용하여 기능적으로 동일하면서 깊이가 최적인 회트로 리라이팅된다. 저자들은 표준 SAT 기반 합성에 두 가지 주요 수정을 도입했다:

ANN 지원 호출 (ANN-Assisted Invoking): 깊이 1부터 시작하는 시행착오 방식 대신, ANN이 예측한 깊이를 SAT 솔버의 초기 타겟으로 사용하여 솔버 호출 횟수를 크게 줄인다.
게이트 위치 제약 (Gate Position Constraining): 국소적 최적화가 글로벌 회로 깊이에 부정적인 영향을 미치지 않도록, SAT 정식화에는 "차단된 위치(blocked position)" 제약이 포함된다. 이 제약은 CNOT 게이트가 서브회로 이외의 게이트(예: 단일 큐비트 게이트 또는 인접한 서브회로의 게이트)가 점유하고 있는 시공간 좌표에 배치되는 것을 방지하여, 솔버가 기존의 글로벌 스케줄 내에 들어맞는 솔루션을 찾도록 강제한다.

주요 기여
본 논문은 다섯 가지 주요 기여를 기술한다:

통합 프레임워크: SSR 프레임워크에 의해 해결되는, 깊이 지향적 사후 QCT 최적화를 기존의 QCT 및 합성 기술을 보완하는 전용 문제로 정식화하였다.
ANN 지원 가속화: SAT 솔버의 탐색 순서를 안내하고, SAT 절차 자체의 완전성이나 최적성을 해치지 않으면서 호출 횟수를 줄이기 위해 ANN 기반의 깊이 예측 체계를 도입하였다.
게이트 위치 제약: 유효한 시공간 윈도우 내로 게이트 배치를 제한함으로써 국소적 서브회로 최적성과 글로벌 회로 수준의 깊이 감소 사이의 균형을 맞추는 메커즘을 제공한다.
반복 전략: 유전 알고리즘 기반의 커뮤테이션과 결합된 서브회로 스코어링 및 선택 전략을 통해, 최적화 가능성이 높은 서브회로를 우선순위에 두고 새로운 최적화 기회를 반복적으로 노출시킨다.
실증적 검증: 다양한 아키텍처와 벤치마크 세트에 걸쳐 일관되고 유의미한 깊이 감소를 입증하는 광범적인 실험을 수행하였다.

실험 결과
저자들은 여러 아키텍처(Grid 5x4, Google Sycamore, IBM Rochester, IBM Heron)와 벤치마크 세트(RevLib, Qiskit 추출 회로, 무작위 회로)에서 SSR을 평가하였다.

깊이 감소: SSR은 다양한 벤치마크 전반에 걸쳐 최대 29.04% 및 평균 **16.59%**의 깊이 감소를 달성하였다.
비교: SSR은 기존의 사후 QCT 최적화 도구인 CBIR 및 Q-Synth보다 우수한 성능을 보였다. 평균적으로 SSR은 깊이를 16.59% 개선한 반면, CBIR과 Q-Synth는 각각 평균 6.45% 및 -0.53%(일부 벤치마크에서 깊이가 약간 증가함을 나타냄)의 개선을 보였다.
확장성: SSR의 실행 시간(runtime)은 큐비트 수와 평균 게이트 수에 따라 거의 선형적으로 증가하는 것으로 관찰되어 확장성을 입증하였다.
구성 요소 분석: 절제 연구(Ablation studies)를 통해 각 구성 요소(GA, 게이트 위치 제약, ANN)가 전체 성능에 기여함을 확인하였다. 특히 ANN은 최종 회로 깊이에 미치는 영향이 미미하면서도 SAT 솔버 호출을 최대 95.87%까지 줄여 실행 시간을 획기적으로 단축하였다.

의의
본 논문은 SSR이 SAT-스위핑 기법을 양자 회로 변환 영역으로 유의미하게 확장했다고 주장한다. 휴리스틱 탐색(GA), 머신 러닝(ANN), 그리고 정밀 합성(SAT)을 하드웨어 연결성을 위한 특정 제약 조건과 통합함으로써, SSR은 QCT가 초래하는 깊이 오버헤드를 완화하는 강력한 방법을 제공한다. 저자들은 SSR을 기존 컴파일러의 보완적인 도구로 위치시키며, 이미 하드웨어에 매핑된 회로를 더욱 정교하게 다듬음으로써 NISQ 장치에서의 계산 신뢰도와 성공률을 높일 수 있다고 강조한다. 이 연구는 접근 방식이 (CNOT 서브회로에 집중하고 선택을 위해 휴리스틱을 사용함으로써) 엄격한 글로벌 최적성을 일부 희생하더라도, 순수하게 국소적이거나 순수하게 정밀한 방법만으로는 달성할 수 없는 실질적이고 유의미한 깊이 감소를 달 achieves 한다는 점을 강조한다.

유사한 논문