기술 요약: 큐비트 매핑 및 라우팅을 위한 컴파일러 생성

1. 문제 정의

양자 회로를 물리적 양자 프로세싱 유닛(QPU)에서 실행하려면 큐비트 매핑 및 라우팅(QMR) 문제를 해결해야 합니다. 컴파일러는 논리적 회로 큐비트를 물리적 장치 큐비트에 매핑하고, 대상 하드웨어의 특정 연결성 및 오류 제약 조건을 준수하면서 게이트 실행을 계획해야 합니다.

양자 하드웨어의 지형은 매우 다양하며 빠르게 진화하고 있습니다. 여기에는 다양한 물리적 구현체(초전도 회로, 트랩 이온, 중성 원자), 다양한 연결성 토폴로지(선형 배열, 그리드, 완전 연결된 트랩), 그리고 다양한 오류 수정 방식(NISQ 장치의 오류 수정 부재부터 결함 허용 아키텍처의 표면 코드에 이르기까지)이 포함됩니다. 현재 새로운 QMR 문제를 다루기 위해서는 연구자들이 처음부터 다시 시작해야 하는 경우가 많습니다. 즉, 난해도(hardness) 결과를 확립하고, 그래프 이론적 문제와의 연결성을 식별하며, 각 특정 하드웨어 구성에 특화된 컴파일 알고리즘을 개발해야 합니다. 본 논문은 아키텍처 제약 조건의 명세를 통해 컴파일러를 자동으로 합성하는 것이 가능한지 묻고 있습니다. 이는 매번 새로운 아키텍처가 등장할 때마다 수동으로 솔버를 엔지니어링하는 대신에 말입니다.

2. 방법론

저자들은 QMR 문제를 공통된 핵심 구조를 통해 통합하고 컴파일러를 자동으로 생성하는 프레임워크인 Amaro(Abstract MApping and ROuting)를 제안합니다.

2.1 추상적 정식화: 장치 상태 머신

핵심 통찰은 모든 QMR 문제를 **장치 상태 머신(device state machine)**으로 모델링할 수 있다는 것입니다. 솔루션은 다음과 같은 정보를 캡처하는 일련의 장치 상태(device states)로 간주됩니다:

• 현재 회로 큐비트의 물리적 위치 매핑.
• 해당 타임스텝에서 병렬로 실행되는 게이트 집합.
• 상태 간의 전이(예: 스왑 연산 또는 항등 변환).

저자들은 추상적인 QMR 문제를 정의하며, 여기서 특정 하드웨어 아키텍처의 제약 조건은 어떤 상태가 유효한지(실현 가능한지)와 어떤 전이가 허용되는지를 결정합니다.

2.2 Amaro 언어

이러한 추상적 문제를 용이하게 명세하기 위해 저자들은 Amaro라는 도메인 특화 언어(DSL)를 설계했습니다. Amaro 프로그램은 다음을 지정함으로써 구체적인 QMR 문제를 정의합니다:

• RouteInfo: 유효한 상태에 대한 제약 조건, 특히 게이트가 어떻게 실현되는지에 대한 방식(예: 두 큐비트 게이트를 연결성 그래프의 에지 또는 격자의 경로로 매핑).
• TransitionInfo: 상태 간의 유효한 전이에 대한 제약 조건(예: 인접한 큐비트 간의 스왑 연산 또는 맵이 정지된 상태의 항등 변환).
• Cost: 최적화 목표(예: 스왑 게이트 수 최소화, 타임스텝 최소화 또는 성공 확률 최대화).

Amaro 프로그램은 간결합니다. 예를 들어, 표준 NISQ 문제에 대한 명세는 단 12줄의 코드만 필요합니다.

2.3 파라미터 솔버

저자들은 Amaro 명세를 입력받아 해당 특정 문제를 위한 컴파일러를 인스턴스화하는 일반적인 파라미터 솔버를 제시합니다. 이 솔버는 **최대 상태 구축(maximal-state construction)**에 기반한 근사적, 반복적 접근 방식을 사용합니다:

1. 최대 상태 구축: 각 반복 단계에서 솔버는 현재 회로의 프런트 레이어로부터 가능한 한 많은 게이트를 라우팅하여 "최대 상태"를 구축하려고 시도합니다.
2. 단조성 및 비간섭성: 솔버는 이 과정을 최적화하기 위해 두 가지 속성을 활용합니다. 만약 문제가 **단조적(monotonic)**이라면(실현 가능한 상태의 부분 집합 또한 실현 가능함), 단 한 번의 패스로 최대 상태를 찾을 수 있습니다. 만약 문제가 **비간섭적(non-interfering)**이라면(하나의 게이트를 라우팅하는 것이 다른 게이트를 방해하지 않음), 최대 상태는 유일하며 순서에 의존하지 않습니다.
3. 탐색 전략: 게이트 경로가 충돌할 수 있는 비간섭적이지 않은 문제의 경우, 솔버는 라우팅되는 명령의 수를 최대화하기 위해 게이트의 최적 순서를 찾는 데 **시뮬레이티드 어닐링(simulated annealing)**을 사용합니다. 마찬가지로, 솔버는 최적의 초기 큐비트 매핑을 찾기 위해 시뮬레이티드 어닐링을 사용합니다.
4. 출력: 이 과정은 유효한 전이를 통해 큐비트 맵을 업데이트하며 모든 회로의 게이트가 라우팅될 때까지 반복됩니다.

3. 주요 기여

• 추상적 정식화: 다양한 하드웨어 제약을 통일된 방식으로 생각할 수 있게 해주는, 장치 상태 머신에 기반한 QMR 문제의 통합된 관점.
• 명세 언어 (Amaro): 고유한 아키텍처 제약을 간결하게 표현할 수 있게 하여, 최소한의 코드로 새로운 QMR 문제를 정의할 수 있게 하는 DSL.
• 파라미터 솔버: Amaro 명세로부터 특정 문제를 위한 컴파일러를 자동으로 인스턴스화하는 강력하고 일반적인 알고리즘. 이는 근사적 방법(최대 상태 구축 및 시뮬레이티드 어닐링)을 통해 솔루션 품질과 실행 시간을 조절합니다.
• 경험적 평가: NISQ 아키텍처부터 결함 허용 표면 코드 및 인터리브드 논리 큐비트에 이르기까지 7가지의 뚜렷한 사례 연구를 통한 종합적인 평가.

4. 실험 결과

저자들은 243개의 애플리케이션 회로 벤치마크 세트에 대해 생성된 컴파일러를 최신 전문 수기 작성 솔버들과 비교 평가했습니다.

• NISQ (NISQMR): 생성된 컴파일러는 Qiskit(Sabre 알고리즘 사용) 및 QSynth2와 경쟁할 만한 수준입니다. 약 48%의 벤치마크에서 Qiskit과 대등하거나 더 나은 성능을 보였으며, QSynth2가 종료되는 73개 케이스 중 66개에서 최적의 솔루션을 찾아냈습니다.
• 가변 오류 (NISQ-VE): 링크의 가변적인 오류율을 고려할 때, Amaro로 생성된 컴파일러는 평균적으로 Qiskit과 동등한 성공 확률을 가진 솔루션을 생성하여, 단순 게이트 수가 아닌 신뢰성을 최적화할 수 있음을 입증했습니다.
• 표면 코드 (SCMR): 생성된 컴파일러는 전문 도구인 DASCOT보다 우수한 성능을 보였으며, 두 도구가 모두 종료되는 경우 57%에서 더 나은 솔루션을 찾았고 92%에서 대등하거나 더 나은 결과를 냈습니다.
• 재구성 가능한 원자 배열 (RAA): 솔버는 Enola 컴파일러를 크게 능가하여, 적어도 하나의 도구가 종료되는 97%의 케이스에서 더 높은 품질의 솔루션을 찾아냈습니다.
• 인터리브드 논리 큐비트 (ILQ): 솔버는 93%의 케이스에서 베이스라인 그리디 컴파일러보다 엄격히 높은 품질의 솔루션을 생성했습니다.
• 트랩 이온 (TIQMR): 솔버는 Shaper 알고리즘을 크게 능가하여, 두 알고리즘이 모두 종료되는 모든 케이스에서 비용을 최소 50% 줄였으며, Shaper가 실패한 27개의 벤치마크를 해결했습니다.

실행 시간 측면에서, 생성된 컴파일러는 일반적으로 몇 분 내에 고품질 솔루션에 수렴하며(예: 80%의 벤치마크에서 최적 솔루션의 10% 임계값에 도달하는 데 약 300~600초 소요), 이는 산업 규모의 컴파일에 적합함을 보여줍니다.

5. 의의 및 주장

본 논문은 양자 하드웨어의 다양성이 수동적인 전문 컴파일러 개발에서 자동화된 합성으로의 전환을 필요로 한다고 주장합니다. QMR 문제의 공통된 핵심 구조를 식으로 파악함으로써, Amaro를 통해 연구자와 개발자는 새로운 아키텍처(신흥 결함 허용 체계 포함)에 대한 제약 조건을 명세하고 경쟁력 있는 컴파일러를 자동으로 생성할 수 있습니다.

저자들은 이 접근 방식이 새로운 및 신흥 아키텍처를 위한 양자 컴파일러 개발을 단순화한다고 강조합니다. 생성된 컴파일러는 근사적이며 최적성을 보장하지는 않지만(QMR은 NP-hard임), 솔루션 품질과 실행 시간 모두에서 수기로 작성된 전문 솔버와 매우 경쟁적임을 보여주었습니다. 이 연구는 "한 번 작성하여 다수를 생성하는(write once, generate many)" 접근 방식이 양자 컴파일 스택에서 실행 가능하다는 것을 시사하며, 이는 급변하는 하드웨어 환경에 양자 소프트웨어가 빠르게 적응하는 것을 가속화할 수 있습니다.