기술 요약: 2D 격자 상의 가환 게이트에 대한 효율적인 회로 트랜스파일링 (Efficient Circuit Transpilation of Commuting Gates on 2D Grids)

문제 정의

최대 컷(Maximum Cut, MC) 및 최대 독립 집합(Maximum Independent Set, MIS)과 같은 조합 최적화 문제는 많은 응용 분야의 중심이지만, 종종 NP-완전(NP-complete) 문제입니다. 양자 근사 최적화 알고리즘(QAOA)은 이러한 문제들을 해밀토니안으로 매핑함으로써 양자 접근 방식을 제공합니다. 그러나 디지털 양자 컴퓨터에서의 실제 구현은 제한된 하드웨어 연결성으로 인해 상당한 장애물에 직면합니다.

문제 해밀토니안 $H_C$는 일반적으로 많은 큐비트 쌍 사이의 상호작작용을 유도합니다. 제한된 연결성(예: 2D 격자)을 가진 하드웨어에서, 이러한 비인접 상호작용은 큐비트를 인접한 위치로 라우팅하기 위해 SWAP 게이트를 사용하여 구현되어야 합니다. 이 라우팅 과정은 회로 깊이와 누적 오차를 증가시켜, 종종 양자 알고리즘의 이점을 상쇄합니다. 표준 트랜스파일링 방법(Qiskit의 방식 등)은 무작위 초기 매핑과 고정된 라우팅을 사용하지만, 특히 희소한(sparse) 상호작용 그래프의 경우 최적이 아닌 회로를 생성하는 경우가 많습니다. 또한, 완전 연결 그래프를 위해 설계된 사전 결정된 SWAP 네트워크는 희소한 비용 해밀토니안에 대해 비효율적입니다.

방법론

저자들은 2차원(2D) 격자 하드웨어에서 구성된 가환 2-큐비트 게이트 블록(QAOA의 전형적인 형태)을 위한 트랜스파일링 스킴을 제안합니다. 핵심 방법론은 문제 의존적인 SWAP 레이어 시퀀스를 구축하는 것과 큐비트 레이아웃을 업데이트하는 것을 교대로 수행하는 것을 포함합니다.

본 논문은 다음과 같은 여러 전략을 도입하고 비교합니다:

1. 선형 전략 ($S_{line}, C_{line}^{grid}$): 2D 격자를 1D 선으로 취급하는 최첨단 베이스라인입니다. SWAP 레이어는 격자의 가장 긴 선의 짝수 및 홀수 에지를 번갈아 가며 적용됩니다.
2. 하이브리드 전략 ($S_{line}, C_{grid}$): 선 기반의 SWAP 라우팅을 적용하되, 근본적인 SWAP 네트워크를 변경하지 않고 가능한 경우 2D 격자의 사용되지 않은 에지를 활용하여 $R_{ZZ}$ 게이트(상호작용)를 직접 적용하는 선형 전략의 수정 버전입니다.
3. 격자 전략 ($S_{grid}, C_{grid}$): 2D 연결성을 완전히 활용하기 위해 수평 및 수직 SWAP을 교대로 적용하는 맞춤형 기저 집합($B_{grid}$)을 사용하는 전략입니다.
4. 탐욕적 문제 의존 전략 ($S_{greedy}, C_{grid}$): 저자들의 주요 기여입니다. 이 방법은 특정 문제 인스턴스의 비용 해밀토니안에 맞춰 SWAP 시퀀스와 초기 큐비트 매핑을 조정하기 위해 탐욕적 탐색 알고리즘을 채택합니다.
   • 내부 루프(Inner Loop): 도달 가능한 큐비트 구성의 트리를 탐색하기 위해 깊이 우선 탐색(DFS)을 사용합니다. 필요한 모든 상호작용을 구현하는 가장 짧은 SWAP 레이어 경로를 찾습니다. 복잡성을 관리하기 위해, 최적의 부분 시퀀스를 선택하고 계속 진행하기 전까지 최대 깊이 $k_{max}$까지 탐색을 제한합니다.
   • 외부 루프(Outer Loop): SAT 기반 매핑 솔버를 사용하여 초기 큐비트 매핑($\pi_0$)을 반복적으로 업데이트합니다. 현재 SWAP 시퀀스 길이가 기준 길이를 초 exceed하면, 더 짧은 시퀀스를 찾기 위해 새로운 매핑으로 탐색을 재설정합니다.
   • 기저 집합(Basis Set): 탐색은 표준 격자 기저를 넘어, 검색 오버헤드를 줄이기 위해 추가적인 SWAP 레이어를 포함하는 확장된 기저 집합($B_{extended}^{grid}$)을 활용합니다.

주요 기여

1. 문제 의전적 트랜스파일링: 본 논문은 고정된 문제 불가지론적 네트워크에 의존하는 대신, 최적화 문제의 특정 상호작용 그래프에 맞게 SWAP 전략과 초기 매핑을 동적으로 구축하는 탐욕적 알고리즘을 도입합니다.
2. 하이브리드 베이스라인: 선형 SWAP 백본을 유지하면서 2D 격자 에지를 상호작용에 활용하는 하이브리드 전략을 제안하여 중간 단계의 베이스라인 역할을 수행하게 합니다.
3. 확장성 분석: 격자 기반 전략, 특히 탐욕적 접근 방식이 희소 그래프에 대해 선형 전략($O(n)$)에 비해 회로 복잡도 지표(SWAP 레이어, 깊이, 게이트 수)에서 점근적 $O(\sqrt{n})$ 개선을 달성함을 이론적 및 경험적으로 입증했습니다.
4. 하드웨어 검증: 최대 80 큐비트 규모의 문제를 대상으로 IBM의 직사각형 격자 하드웨어에서 QAOA 회로를 실험적으로 실행하여 시뮬레이션 결과를 검증했습니다.

결과

저자들은 Random Regular (RR) 그래프(차수 $d=3$)의 MC 인스턴스와 Erdős–Rényi (ER) 그래프(에지 확률 $q=0.08$)의 MIS 인스턴스에 대해 접근 방식을 벤치마킹했습니다.

• 회로 복잡도: 표준 방법(선형 전략 및 Qiskit의 SABRE 트랜스파일러 포함)과 비교하여, 탐욕적 전략은 희소 그래프에서 회로 깊이와 2-큐비트 게이트 수를 약 2배 감소시켰습니다.
  • RR 그래프의 경우, 선형 전략은 SWAP 레이어, 깊이, CZ 게이트가 각각 $n, n, n^2$으로 스케일링되는 반면, 탐욕적 전략은 더 낮은 상수와 더 나은 스케일링 동작을 유지했습니다.
  • ER 그래프의 경우, 탐욕적 전략은 선형 전략의 CZ 게이트 스케일링이 $O(n^3)$인 것에 비해 $O(n^{5/2})$를 기록하며 선형 전략을 크게 압도했습니다.
• 실행 가능 영역: 게이트 수의 감소는 노이즈가 있는 하드웨어에서의 실행 가능한 문제 크기를 확장했습니다. 고정된 CZ 게이트 예산(예: 3,600개 게이트)에 대해, 탐욕적 전략은 최대 100개의 노드를 가진 인스턴스 실행을 가능하게 한 반면, 선형 전략은 약 60개 노드에 제한되었습니다.
• 근사 비율: 하드웨어 실험은 개선된 성능을 보여주었습니다:
  • 최대 컷 (MC): 탐욕적 전략은 72 큐비트에서 선형 전략에 비해 평균 근사 비율을 최대 6.62% 개선했습니다.
  • 최대 독립 집합 (MIS): 개선 효과는 더욱 두드러져, 56 큐비트에서 **9.32%**에 달했습니다.
• 절단(Truncation) 비교: 비용 해밀토니안을 절단하여 깊이를 줄이는 방식(이론적 보장을 희생함)과 달리, 탐욕적 전략은 동일한 SWAP 레이어 내에서 훨씬 더 큰 타겟 상호작용의 부분 집합을 구현함으로써 더 많은 문제 구조를 보존했습니다.

의의 및 주장

본 논문은 효율적인 트랜스파일링이 근접 양자 하드웨어에서 QAOA의 실질적인 성능을 위해 매우 중요하다고 주장합니다. 저자들은 문제 인식적(problem-aware) 트랜스파일링 스킴이 노이즈가 있는 장치, 특히 희소한 최적화 문제에서 양자 알고리즘 성능을 향상시키는 핵심이라고 단언합니다.

주요 의의에 관한 주장은 다음과 같습니다:

• 더 큰 실험 가능: 이 방법은 회로 깊이와 오차 누적을 줄임으로써 현재 하드웨어에서 최대 80 큐비트 규모의 실험을 가능하게 합니다.
• 하드웨어 개선의 증폭: 하드웨어 품질이 향상됨에 따라(사용 가능한 CZ 게이트 예산 증가), 효율적인 트랜스파일링의 이점은 증폭됩니다. 탐욕적 전략은 게이트 예산이 증가함에 따라 선형 전략에 비해 더 큰 폭의 접근 가능한 문제 크기 증가를 허용합니다.
• 양자 우위와의 관련성: 이 접근 방식은 클래식 솔버가 어려움을 겪는 영역(예: 500개 노드의 저밀도 MIS 인스턴스)을 포함하여, 잠재적 양자 우위를 탐색하는 데 특히 유효합니다.
• 미래 대비: 본 연구는 bivariate bicycle code와 같은 오류 정정 코드가 직사각형 격자에 기반한 구조적이고 비국소적인 연결성을 요구함에 따라, 2D 연결성을 활용하도록 트랜스파일링 전략을 적응시키는 것이 미래 아키텍처의 회로 복잡성을 줄이는 데 필수적임을 강조합니다.

저자들은 자신의 방법이 사전 정의된 SWAP 레이어에 의존하기는 하지만, 문제 인식적 트랜스파일링이 이론적인 양자 알고리즘과 실제 노이즈가 있는 하드웨어 실행 사이의 간극을 메우기 위한 필수적인 단계임을 입증한다고 결론짓습니다.