기술 요약: CNOT 및 클리포드 회로의 휴리스틱 및 최적 합성

문제 정의

클리포드(Clifford) 회로를 효율적으로 구현하는 것은 양자 오류 정정 및 양자 알고리즘의 기초가 됩니다. 이러한 회로의 효율성은 일반적으로 2-큐비트 얽힘 게이트(선형 가역 회로의 경우 구체적으로 CNOT)의 개수나 회로 깊이(depth)로 측정됩니다. 최적화 작업은 매우 까다로운데, 이는 단일 클리포드 연산자가 매우 다양한 게이트 수와 깊이를 가진 수많은 회로 구성으로 구현될 수 있기 때문입니다. rustiq, tket, qiskit과 같은 기존 방식(가우스 소거법 또는 휴리스틱 접근법)은 특히 큐비트 수가 많거나 특정 인코딩 회로의 경우 가장 조밀한 구현을 찾는 데 실패하는 경우가 많습니다. CNOT 전용 선형 가역 회로에 관한 고전 문헌들은 다양한 합성 기술을 확립해 왔으나, CNOT 전용 및 일반 클리포드 회로 모두에서 2-큐비트 게이트 수를 최소화할 수 있는 통합되고 효율적인 방법에 대한 필요성이 여전히 존재합니다.

방법론

저자들은 최적(Optimal), A*, 그리고 그리디(Greedy) 합성이라는 세 가지 뚜렷한 알고리즘 군을 사용하여 CNOT 및 일반 클리포드 회로를 합성하기 위한 통합 프레임워크를 제안합니다. 이들의 접근 방식 핵심은 회로 연산자를 이진 행렬로 매핑하고 동치 클래스(equivalence classes)를 활용하여 탐색 공간을 줄이는 것입니다.

1. 수학적 표현

• CNOT 회로: $GL(n, 2)$ 내의 가역 이진 행렬로 매핑됩니다. CNOT 게이트는 하나의 열을 다른 열에 더하는 것에 해당합니다.
• 일반 클리포드 회로: $Sp(2n, 2)$ 내의 심플렉틱(symplectic) 이진 행렬로 매핑됩니다. 저자들은 큐비트 치환(permutation), 단일 큐비트 클리포드, 그리고 두 큐비트 심플렉틱 트랜스베션(single-qubit Clifford까지 고려하면 CNOT과 동일함)의 세 가지 레이어로 구성된 회로 구조를 활용합니다.
• 동치 클래스: 저자들은 다음 항목들에 대해 행 및 열 치환(큐비트 치환), 행렬 전치(transposition) 및 역행렬(inversion)을 고려함으로써 계산 복잡도를 크게 줄였습니다.
  • 클리포드 회로의 경우, 단일 큐비드 클리포드 연산자에 의한 좌측 및 우측 곱셈을 고려합니다.
  • 이를 통해 동치 클래스 내에서 가장 낮은 게이트 수 또는 깊이를 가진 회로를 선택할 수 있습니다.

2. 알고리즘 군

A. 최적 합성 (Optimal Synthesis)

• 접근 방식: 특정 큐비트 수($n \le 7$ CNOT, $n \le 5$ Clifford)까지의 모든 동치 클래스 데이터베이스를 생성합니다.
• 메커니즘: 가능한 모든 게이트를 순차적으로 적용하여 행렬을 생성합니다. 동치는 행렬을 이색 그래프(bi-colored graphs, CNOT의 경우) 또는 일반화된 그래프(Clifford의 경우)로 매핑하고, nauty나 Bliss와 같은 패키지를 사용하여 동형성(isomorphism)을 확인하여 결정됩니다.
• 사용법: 타겟 행렬에 대해 사전 계산된 데이터베이스에서 해당 동치 클래스를 찾아 최적의 게이트 시퀀스를 검색하고, 타겟과 일치시키기 위해 필요한 치환을 적용합니다.

B. A* 합성 (A* Synthesis)

• 접근 방식: 최적 데이터베이스가 너무 커지는 중간 규모 회로를 위해 설계된 최선 우선 탐색(best-first search) 알고리즘입니다.
• 메커니즘: 우선순위 큐를 사용하여 게이트 시퀀스를 탐색합니다. 치환 행렬(CNOT의 경우) 또는 치환 및 단일 큐비드 클리포드(Clifford의 경우)에 도달하기 위한 남은 비용을 추정하기 위해 휴리스틱 함수 $h(P)$를 사용합니다.
• 휴리스틱: 저자들은 행 및 열 합(특히 $H_{sum}$ 및 $H_{prod}$ 메트릭)을 기반으로 한 견고한 추정치를 도출했습니다. 이들은 이러한 휴리스틱을 스케일링($r \cdot h$)하는 것이 성능을 향상시킨다는 것을 발견했습니다. 알고리즘은 즉시 게이트를 결정하지 않고, 가장 낮은 $g(P) + h(P)$ 값을 가진 노드를 확장합니다.
• 최적화: 지수적인 최악의 경우 복잡도를 관리하기 위해 우선순위 큐의 크기를 제한(예: 100개 항목)하며, 제한을 초과할 경우 최대 항목을 제거합니다.

C. 그리디 합성 (Greedy Synthesis)

• 접근 방식: 대규모 회로를 위한 빠르고 결정론적인 알고리즘입니다.
• 메커니즘: 각 단계에서 가능한 모든 게이트를 평가하고 특정 휴리스틱을 최소화하는 게이트를 선택합니다.
• 혁신: 이전의 스칼라 휴리스틱(항목을 합산하거나 로그 합을 구하며 종종 지역 최솟값에 갇히는 방식)과 달리, 저자들은 벡터 기반 휴리스틱을 도입했습니다. 이 벡터는 행렬, 그 역행렬, 전치 행렬, 그리고 역전치 행렬의 열 합을 정렬하여 형성됩니다.
• 깊이 최적화: 그리디 알고리즘은 깊이를 기본 비용으로 취급하고 휴리스틱을 보조 페널티로 취급함으로써 회로 깊이를 최소화하도록 수정될 수 있습니다.

주요 기여 및 결과

1. 알고리즘 개선

• 벡터 휴리스틱: 그리디 합성을 위한 제안된 벡터 기반 휴리스틱은 스칼라 휴리스틱($H_{sum}$ 및 $H_{prod}$)보다 지역 최솟값을 피하는 데 있어 성능이 월등히 뛰어납니다. $n \ge 32$ 큐비트 회로의 경우, 벡터 휴리스틱이 지배적이었던 반면, 스칼라 휴리스틱은 $n > 32$인 회로에서 100%의 포기율(abandonment rate)을 보이며 실패했습니다.
• 동치 클래스 축소: 그래프 동형 문제로 매핑하고 치환, 전치, 역행렬을 고려함으로써, 저자들은 이전 방식(예: Bravyi 등의 [4]와 비교하여 $Sp(2n, 2)$의 탐색 공간을 크게 축소)보다 지수적으로 작은 데이터베이스를 생성했습니다.

2. 벤치마킹 결과

저자들은 무작위 행렬 및 특정 데이터셋을 사용하여 rustiq, tket, qiskit, PyZX, Volanto와 벤치마킹을 수행했습니다.

• CNOT 회로:
  • Optimal/A*: $n \le 7$에 대해 A* 알고리즘은 최적의 게이트 수를 일치시키며, $n = 32$까지의 회로에 대해 A* 알고리즘은 가장 낮은 게이트 수를 제공합니다. $n \ge 32$인 회로의 경우, 벡터 휴리스틱을 사용하는 그리디 알고리즘이 가장 낮은 CNOT 수를 기록하며 가우스 소거법보다 평균 50% 적은 게이트 수 감소를 달 나타냈습니다.
• 일반 클리포드 회로:
  • 무작위 행렬: A* 알고리즘은 $n \le 5$에서 최적의 수를 일치시키며, $n \le 16$까지의 회로에서 가장 낮은 수를 제공합니다. $n > 16$인 회로의 경우, 그리디 알고리즘은 테스트된 모든 다른 방법(pytket 및 rustiq 포함)보다 성능이 현저히 뛰어납니다.
  • Hamiltonian 데이터셋: 4~64 큐비트의 해밀토니안 진화 회로 데이터셋에서, 그리디 알고리즘은 게이트 수와 실행 시간 모두에서 BSHM 알고리즘(pytket 최적화 포함)보다 우수한 성능을 보였습니다.
  • 인코딩 회로: Golay 코드 $[[23, 1, 7]]$에 대해, 저자들은 A*를 사용하여 이전 최고 기록인 Steane의 방식(57개) 및 강화 학습 방식(61개)을 개선한 56개의 얽힘 2-큐비트 게이트를 가진 인코딩 회로를 찾아냈습니다.
• SAT 솔버와의 비교: qsynth(SAT 기반 솔버)와 비교했을 때, 저자들의 최적 및 A* 알고리즘은 5 큐비트까지의 회로에 대해 더 나은 게이트 수를 일치시키면서도 처리 시간은 수 차례 더 빨랐습니다. $n \ge 6$의 경우, qsynth는 거의 모든 사례에서 타임아웃이 발생했으나, 저자들의 방법은 성공적으로 완료되었습니다.

3. 구현

알고리즘은 GitHub에서 사용할 수 있는 Python 패키지로 구현되어 있어, 커뮤니티가 결과를 재현하고 자신의 회로에 적용할 수 있도록 합니다.

의의 및 주장

본 논문은 자신의 주요 의의가 광범위한 회로 크기에 걸쳐 기존의 최첨단 방법들보다 일관되게 낮은 2-큐비트 게이트 수를 달성하는 일련의 합성 도구를 제공하는 데 있다고 주장합니다.

• 확장성: 이 연구는 소규모 최적 합성(optimal synthesis)과 대규모 휴리스틱 합성 사이의 간극을 메우며, 데이터베이스 크기로 인해 기존 최적 방법이 실패하고 SAT 솔버가 시간 제약으로 실패하는 64 큐비트까지의 회로에 대한 실질적인 해결책을 제공합니다.
• 견고성: 벡터 기반 휴리스틱은 스칼라 기반 그리디 접근 방식에서 흔히 발생하는 "지역 최솟값" 함정을 방지하는 핵심적인 발전임을 강조합니다.
• 실질적 영향: Golay 코드와 같은 오류 정정 코드를 위한 더 조밀한 회로를 찾는 능력은 논리적 연산에 필요한 자원 오버헤드를 줄임으로써 결함 허용 양자 컴퓨팅(fault-tolerant quantum computing)의 실현 가능성에 직접적인 영향을 미칩니다.
• 한계 인정: 저자들은 최적 합성이 현재 데이터베이스 크기로 인해 $n \le 7$(CNOT) 및 $n \le 5$(Clifford)로 제한되어 있음을 인정하면서도, 더 나은 코딩 기법을 통해 확장될 수 있음을 시사합니다. 또한, 그리디 알고리즘이 빠르기는 하지만 대규모 회로에 대해 전역적 최적성을 보장하지는 못하지만 경험적으로 경쟁 모델보다 우수하다는 점을 명시합니다.

결론적으로, 이 알고리즘들은 현재 장치 불가지론적(device-agnostic)이며, 향-후 C/Rust로 포팅하거나 특정 하드웨어 연결성 제약에 맞게 조정하여 더욱 최적화할 수 있다고 언급하며 마무리합니다.