0. Summary

  • 기본 정보 : ArXiv,2026.10.27, AI-Assisted Discovery of CNOT Decompositions for Quantum Permutations on Constrained Topologies
  • 연구 배경 : 현재 양자 하드웨어는 결합 그래프(coupling graph)의 인접 큐비트 사이에서만 2-큐비트 게이트를 허용하므로, 논리 회로를 물리 토폴로지에 맞게 컴파일할 때 큰 오버헤드가 생긴다. 표준 방식은 멀리 떨어진 큐비트가 상호작용해야 할 때 SWAP(= CNOT 3개)을 삽입하는 것이며, SWAP 수 최소화가 CNOT 수의 대리 목표로 쓰인다. 전역 연결(all-to-all)에서는 $n$ 원소·$k$ 개 서로소 순환을 갖는 순열의 최적 CNOT 비용이 정확히 $3(n-k)$ 로 알려져 있지만(Bu et al. 2025), 연결 제약 아래서는 SWAP 최소화와 CNOT 최소화가 다른 문제라는 것(Chen et al. 2022)만 알려져 있고, SWAP 기반 라우팅이 어떤 최적화 기회를 놓치는지는 구조적으로 규명되지 않았다. 최근 AI 기반 합성기(AlphaCNOT 등)가 회로를 줄이는 데 성과를 냈지만, 그 출력에서 새 결정론적 컴파일 알고리즘을 이끌어낼 원리를 찾는 역할은 거의 탐구되지 않았다.
  • 제안 방법 : 모델 기반 강화학습 합성기 AlphaCNOT(Cossio et al. 2026)을 블랙박스 최적화기가 아니라 탐색 도구로 쓴다. Faro et al.(2024)의 상수 깊이 회전·순열 회로를 기준선으로 삼아, AlphaCNOT이 내놓는 토폴로지 합법 CNOT 회로를 검사해 반복되는 구조를 찾고 이를 정리·증명·알고리즘으로 형식화한다. 첫째, 그래프 거리 $d>1$ 인 두 큐비트의 전치(transposition)를 SWAP 사슬의 $6d-3$ 개가 아니라 최대 $6d-4$ 개 CNOT 으로 구현하는 구성적 증명(Theorem 3.1)을 준다. 둘째, 모든 논리 전치에 토폴로지 의존 CNOT 비용 $w_G$ 를 부여하고 대칭군 $S_n$ 의 가중 Cayley 그래프에서 Dijkstra로 최소 비용 분해를 찾는 결정론적 합성법 Global Transpositions(GT) 를 정의한다. 셋째, GT 모델로도 표현되지 않는 추가 절감을 Intermediate CNOT Fusion(중간 CNOT 융합)으로 정의하고 실험으로 관찰한다.
  • 발견 사실 : 단일 샷 AlphaCNOT은 대부분의 전치에서 $f(d)=6d-4$ 개 CNOT을 찾고, best-of-ten에서는 모든 전치에서 정확히 $f(d)$ 를 찾는다(Table 1). 5큐비트 이하 모든 토폴로지의 완전 탐색에서 $6d-4$ 보다 짧은 구현은 없었다(최적성은 추측). 토폴로지당 100개(4큐비트는 24개 전부)의 순열에서 평균 CNOT 수는 SWAP$\times 3$ 23.85 → GT 22.55 → AlphaCNOT 21.83 으로, 전치 모델이 평균 1.31개, 직접 합성이 추가로 0.72개(GT 대비 3.2%) 줄인다(Table 3). 4L에서 $\sigma=[2,3,1,0]$ 은 GT 14개 vs AlphaCNOT 13개이며, 양방향 BFS로 13이 최적임이 증명된다.
  • 핵심 기여 :
    1. 원격 전치의 $6d-4$ 구성 : 거리 $d>1$ 인 전치에 대해 최대 $6d-4$ 개 CNOT의 토폴로지 합법 구현을 귀납적으로 구성했다. SWAP 기반 $6d-3$ 보다 정확히 1개 적다.
    2. Global Transpositions 알고리즘 : 독립적으로 합성된 논리 전치의 최소 비용 분해를 계산하는 결정론적 방법으로, 생성자 집합이 모든 인접 SWAP을 포함하므로 최적 SWAP 라우팅을 CNOT으로 전개한 것보다 나쁘지 않다($\ell_{\mathrm{GT} }\le 3\,\ell_{\mathrm{SWAP} }$)는 보장과 함께, 참 CNOT 최적값의 인증된 상한을 준다.
    3. Intermediate CNOT Fusion의 관찰 : 직접 CNOT 합성이 순열 부분군 $S_n\subset GL(n,\mathbb{F}_2)$ 을 일시적으로 벗어나는 중간 선형 변환을 이용해 여러 논리 연산의 부분 효과를 결합한다는 메커니즘을 정의하고, 최소 예시와 전체 평가로 그 존재를 보였다.

Abstract 쉬운 설명(Claude)

한마디로: AI가 찾아낸 “요령”을 사람이 분석해서 공식으로 만들었고, 그 공식이 기존 방법보다 조금 더 효율적이라는 이야기입니다.

1. 배경: 양자 컴퓨터의 “자리 배치” 문제

<% include embed.html src=”assets/images/posts/2026-11-07-2610.37045/qubit_line_swap_routing.html” %>

양자 컴퓨터 안에는 정보를 담는 작은 칸(큐비트)이 여러 개 있습니다. 문제는 모든 칸이 서로 직접 대화할 수 있는 게 아니라는 점입니다. 바로 옆에 붙어 있는 칸끼리만 정보를 주고받을 수 있습니다.

일렬로 앉은 교실을 떠올려 보세요. 학생들은 바로 옆 사람하고만 쪽지를 주고받을 수 있습니다. 그런데 맨 끝의 두 학생이 자리를 바꿔야 한다면 어떻게 할까요? 중간 학생들과 한 칸씩 차례로 자리를 바꿔 가며 이동해야 합니다.

양자 컴퓨터에서 이 “한 칸씩 자리 바꾸기”를 SWAP이라고 합니다. SWAP 한 번에는 CNOT이라는 기본 동작이 3번 필요합니다. CNOT은 실수(오류)가 잘 생기는 비싼 동작이라서, CNOT 횟수를 줄이는 것이 곧 성능 향상입니다.

2. 발견: AI가 찾아낸 한 단계 짧은 방법

<% include embed.html src=”assets/images/posts/2026-11-07-2610.37045/swap_vs_direct_cnot_tau02.html” %>

연구진은 AlphaCNOT이라는 AI에게 “이 자리 바꾸기를 CNOT 최소 횟수로 해 봐”라는 과제를 주었습니다. AI는 SWAP을 그대로 쓰지 않고, CNOT을 더 자유롭게 조합해서 해결했습니다.

결과는 이렇습니다. 거리가 d만큼 떨어진 두 칸을 바꿀 때 기존 방식은 6d−3번이 들었는데, AI는 매번 6d−4번, 즉 1번 적게 해냈습니다. 예를 들어 세 칸짜리 줄에서 양 끝을 바꾸면 기존 방식은 9번, AI 방식은 8번입니다.

1번 차이는 작아 보이지만, 큰 회로에서는 이런 절약이 수없이 반복됩니다.

3. 핵심: AI의 요령을 “공식”으로 만들다

fig 1

이 연구에서 중요한 점은 AI 결과를 그냥 쓰고 끝내지 않았다는 것입니다. 연구진은 AI가 만든 회로를 들여다보며 반복되는 패턴을 찾았습니다. 그리고 그 패턴이 항상 통한다는 것을 수학적으로 증명했습니다.

AI는 매번 답이 조금씩 다르고, 왜 그런 답이 나왔는지 설명해 주지 않습니다. 반면 증명된 공식은 언제나 똑같이 작동하고 결과를 믿을 수 있습니다. 비유하자면 요리 잘하는 사람의 감을 정확한 레시피로 옮겨 적은 셈입니다.

4. 응용: Global Transpositions

연구진은 이 공식을 이용해 Global Transpositions라는 새 방법을 만들었습니다. 여러 칸의 자리를 한꺼번에 재배치해야 할 때, 어떤 순서와 조합으로 바꾸면 총 비용이 가장 적은지 계산해 주는 방법입니다. 이 방법은 최소한 기존 SWAP 방식보다 나쁠 수는 없도록 설계되어 있습니다.

5. 아직 남은 수수께끼: “중간 융합”

그런데 AI는 이 새 공식보다도 더 짧은 답을 찾아내곤 했습니다. 이유를 살펴보니, AI는 자리 바꾸기를 하나씩 따로 끝내지 않았습니다. 여러 개의 자리 바꾸기를 중간에 섞어서 동시에 진행했던 겁니다.

이사에 비유하면 이렇습니다. 짐을 하나씩 완전히 옮기고 나서 다음 짐을 옮기는 대신, 중간에 여러 짐을 임시로 겹쳐 놓았다가 마지막에 한꺼번에 제자리에 두는 식입니다. 중간 과정은 엉망처럼 보이지만 전체 이동 횟수는 줄어듭니다.

연구진은 이것을 중간 CNOT 융합이라고 이름 붙였습니다. 다만 이 현상은 아직 실험으로 관찰된 단계이고, 언제 왜 가능한지에 대한 이론은 앞으로의 과제로 남아 있습니다.

정리하면: AI는 이 연구에서 계산만 대신해 준 도구가 아닙니다. 사람이 미처 보지 못한 규칙을 찾아 준 탐색 도구였습니다. 연구진은 그 규칙을 증명해 믿을 수 있는 방법으로 만들었고, 아직 설명되지 않은 더 깊은 요령이 있다는 것까지 밝혀냈습니다.

관련 개념

연결 제약 컴파일과 SWAP 라우팅

양자 알고리즘은 보통 어떤 큐비트 쌍이든 상호작용할 수 있는 논리 큐비트 관점에서 설계됩니다. 그러나 실제 양자 프로세서는 결합 그래프(coupling graph) 의 인접 정점 사이에서만 2-큐비트 게이트를 허용합니다(Davis et al. 2020; Kissinger & Van De Griend 2020; Wu et al. 2023). 따라서 알고리즘의 실제 실행 비용은 논리 회로뿐 아니라 그 회로를 대상 토폴로지에 어떻게 컴파일하는지에 달려 있습니다.

🔀 1. SWAP 삽입과 CNOT 비용

표준 접근은 상호작용해야 하는 두 논리 큐비트가 물리적으로 인접하지 않을 때 SWAP 게이트를 삽입하는 것입니다. SWAP은 보통 CNOT 3개로 분해되므로, SWAP 수를 최소화하는 것이 2-큐비트 게이트 수를 줄이는 자연스러운 대리 목표가 됩니다. 현재 장치에서는 2-큐비트 게이트가 실행 오류와 컴파일 오버헤드를 모두 지배하므로 이 목표가 특히 중요합니다.

개념 정의
결합 그래프 $G=(V,E)$ 정점 = 물리 큐비트, 간선 = 허용된 2-큐비트 상호작용
토폴로지 합법(topology-legal) 회로 모든 CNOT이 $G$ 의 간선 위에서만 작용하는 회로
그래프 거리 $d_G(i,j)$ 두 큐비트 사이 최단 경로의 간선 수
SWAP 비용 CNOT 3개

🔄 2. 순열 회로에서 SWAP과 CNOT의 관계

순열 회로에서는 SWAP 합성과 CNOT 합성의 관계가 특히 직접적입니다. 순열은 큐비트 상태의 재배열을 기술하므로 전치(transposition)의 열로 구현할 수 있습니다. 연결 제약이 없을 때 이 관계는 잘 이해되어 있습니다.

Bu et al.(2025): $n$ 원소 순열이 $k$ 개의 서로소 순환으로 이루어지면 정확히 $3(n-k)$ 개의 CNOT으로 최적 구현된다.

즉 전역 연결에서는 최적 CNOT 비용이 대상 순열의 순환 구조만으로 완전히 결정됩니다.

그러나 연결 제약 아래서는 SWAP 최소화와 CNOT 최소화가 별개의 문제입니다. Chen et al.(2022)은 최소 SWAP 수를 갖는 라우팅 해가 각 SWAP을 독립적으로 전개했을 때 최소 CNOT 구현을 주지 않을 수 있음을 보였습니다. 이것은 두 목표의 분리를 확립하지만, 더 구조적인 질문은 열어 둡니다.

직접 CNOT 합성에 열려 있는 기회 중, 탐색을 SWAP 기반 라우팅으로 제한하면 어떤 것이 배제되는가?

🧱 3. 기준 회로: Faro et al.(2024)의 상수 깊이 회전·순열

$R=(q_0,\ldots,q_{n-1})$ 을 $n$ 큐비트 레지스터라 할 때, 크기 $k$ 의 회전(rotation) 은 큐비트 상태를 $k$ 칸 순환 이동시키고, 순열(permutation) 은 임의의 $\pi\in S_n$ 에 따라 재배열합니다. Faro et al.(2024)은 두 연산 모두를 logspace-uniform, 상수 깊이, 선형 크기의 회로족으로 구현했습니다.

구성 요소 내용
회전 두 개의 반사(reflection)로 분해. 각 반사는 서로소 SWAP의 한 층으로, 완전히 병렬 실행 가능 → 깊이가 레지스터 크기와 무관
순열 서로소 순환으로 분해 후, 각 순환을 해당 큐비트에만 작용하는 순환 회전으로 구현. 서로소 순환은 동시에 실행 → 상수 깊이 유지, 선형 크기
복잡도 임의 큐비트 순열이 $\mathrm{QNC}^0$ 에 속함을 확립

이 회로는 서로소 전치 층으로 이루어진 고도로 구조화된 SWAP 기반 구성이므로, “순열 수준에서 이미 최적화된 회로를 CNOT 수준에서 더 줄일 수 있는가”를 묻는 자연스러운 벤치마크입니다. 이 논문은 라우팅 자체를 바꾸지 않고, AI 기반 CNOT 합성이 이 SWAP 최적 회로를 어떻게 변형하는지와 결과 CNOT 분해의 구조적 성질을 분석합니다.

💡 Key Takeaway 전역 연결에서는 순열의 CNOT 최적 비용이 순환 구조로 닫힌 형태로 결정되지만, 연결 제약이 들어오면 SWAP 최소화가 CNOT 최소화를 보장하지 않습니다. 이 논문의 출발 질문은 “SWAP으로 생각하면 무엇을 놓치는가”입니다.

AlphaCNOT: 모델 기반 강화학습 CNOT 합성기

AI는 최근 양자 회로 합성·최적화·컴파일의 유망한 접근으로 떠올랐습니다. 강화학습은 하드웨어 인식 트랜스파일과 CNOT 최소화에 적용되었고(Kremer et al. 2024; Romanello et al. 2025; Cossio et al. 2026), AI 기반 탐색이 비자명한 회로 구조와 컴파일 전략을 발견할 수 있다는 사례도 있습니다.

📚 1. 관련 연구 계보

연구 내용
AlphaTensor for quantum circuits (Ruiz et al. 2025) 텐서 분해 관점의 회로 최적화
Zen et al. (2025) 내결함 상태 준비 회로의 RL 기반 발견
Villar et al. (2025) 일반 토폴로지에서 순열 회로 합성·트랜스파일의 RL
AlphaClifford (Lizzio Bosco et al. 2026b), Yeung et al. (2026) RL 기반 Clifford 합성
Q-PRESYN (Lizzio Bosco et al. 2026a) 학습된 국소 회로 변환이 후속 합성 결과를 개선
Finger et al. (2026) 자동 양자 알고리즘 발견

이 결과들은 AI 생성 해가 최적화된 출력으로서뿐 아니라 재사용 가능한 컴파일 원리를 식별할 대상으로도 유용할 수 있음을 시사합니다.

🧮 2. 패리티 행렬과 순차 계획 문제

AlphaCNOT(Cossio et al. 2026)은 CNOT 합성을 순차 계획 문제로 다루는 모델 기반 강화학습 알고리즘입니다. CNOT 회로는 패리티 행렬 $A\in GL(n,\mathbb{F}_2)$ 로 표현되며, CNOT 합성은 $A$ 를 단위행렬로 환원하는 CNOT 열을 찾는 문제가 됩니다.

탐색 요소 대응
상태 가역 이진 행렬 $A\in GL(n,\mathbb{F}_2)$
행동 CNOT 게이트 하나 = $\mathbb{F}_2$ 위의 기본 행 연산
목표 단위행렬 도달
토폴로지 인식 설정 행동 공간을 결합 그래프가 지원하는 CNOT으로 제한

CNOT $X_{a,b}$(제어 $a$, 표적 $b$)는 행 $b$ 에 행 $a$ 를 더하는 연산입니다. 순열 행렬은 $GL(n,\mathbb{F}_2)$ 의 부분군 $S_n$ 을 이루므로, 직접 CNOT 합성의 중간 상태는 순열이 아닌 일반 가역 선형 변환일 수 있습니다. 이 점이 뒤의 Intermediate CNOT Fusion 논의의 핵심입니다.

🌳 3. MCTS와 두 신경망

AlphaCNOT은 심층 신경망과 Monte Carlo Tree Search(MCTS) 를 결합해 여러 후보 합성 궤적을 명시적으로 탐색합니다. MCTS는 선택·확장·시뮬레이션·역전파의 표준 단계를 반복하며 유망한 가지에 집중합니다.

신경망 역할
정책망(policy network) 가능한 모든 CNOT 행동에 사전 확률 부여
가치망(value network) 현재 행렬 상태의 품질 추정 (완전 탐색 없이)

모델 기반 정식화 덕분에 알려진 회로 동역학을 활용해 look-ahead 탐색을 수행하며, 휴리스틱 기반 단일 행동 열에 묶이지 않습니다. 제약 없는 선형 가역 합성과 토폴로지 인식 합성 둘 다를 다룹니다.

🎲 4. 비결정성과 multi-shot 사용

탐색이 비결정적이므로 같은 회로에 대해 합성을 반복하고 최선을 고르는 multi-shot 사용이 가능합니다. 이 논문의 실험 설정은 두 가지입니다.

설정 의미
single-shot 합성 1회 실행
best-of-ten 독립적으로 10회 샘플링 후 CNOT 수가 가장 작은 해 유지

토폴로지 표기는 Kremer et al.(2024)을 따릅니다. 큐비트 수 뒤에 연결 패밀리 문자를 붙여, 예컨대 3L은 3큐비트 선형, 4T는 4큐비트 T자형입니다(Figure 1은 7Y와 8H를 예시). AlphaCNOT 소스 코드와 실험 토폴로지용 학습 모델은 GitHub 저장소(Jaccos01/AlphaCNOT)에 공개되어 있습니다.

이 논문에서 AlphaCNOT은 주로 탐색 도구로 쓰입니다. 제공된 분해를 검사해 반복 구조를 찾고, 이후 결정론적 구성으로 형식화할 가설을 세우는 것이 방법론입니다.

💡 Key Takeaway AlphaCNOT은 $GL(n,\mathbb{F}_2)$ 전체를 상태 공간으로 삼는 MCTS 합성기입니다. SWAP 라우팅과 달리 중간 상태가 순열일 필요가 없다는 점이, 이 논문에서 관찰되는 두 가지 구조(국소 절감과 전역 융합)의 공통 원천입니다.

국소 프리미티브의 발견: 원격 전치의 $6d-4$ 패턴

출발점은 단일 전치 $\tau(i,j)$ 로 이루어진 대상 순열입니다. $d=d_G(i,j)$ 를 결합 그래프에서 두 끝점의 거리라 합시다.

📏 1. SWAP 기반 기준선: $6d-3$

표준 SWAP 기반 구현은 한 끝점을 최단 경로를 따라 이동시켜 다른 끝점과 교환하고 다시 되돌립니다. 이 과정은 인접 SWAP $2d-1$ 개를 쓰므로, 각 SWAP을 CNOT 3개로 전개하면 $3(2d-1)=6d-3$ 개의 CNOT이 됩니다.

Kutin et al.(2007)은 선형 최근접 이웃 설정에서 $n$ 선 라인의 두 끝점을 $6n-9$ 개 CNOT으로 교환하는 구성을 연구했는데, 끝점 거리가 $d=n-1$ 이므로 이는 $6d-3$ 에 해당합니다.

🔍 2. 가장 작은 분리 사례: $\tau(0,2)$ on $0-1-2$

이 상한은 CNOT 수에 관해 반드시 최적은 아닙니다. 가장 작은 예는 3큐비트 라인 $0-1-2$ 위의 $\tau(0,2)$ 입니다.

구현 CNOT 수
인접 SWAP 3개 9
직접 토폴로지 합법 구현 (Figure 2) 8

이것이 SWAP 라우팅과 직접 CNOT 합성 사이의 첫 국소 분리입니다.

📊 3. 경험적 패턴 (Table 1)

저자들은 여러 토폴로지에서 모든 전치에 대해 AlphaCNOT이 찾은 CNOT 수를 평가했고, 같은 패턴을 반복해서 관찰했습니다. 대부분의 대상 $\tau(i,j)$ 에 대해 CNOT 수는

$$f(d)=\begin{cases}3,& d=1,\\ 6d-4,& d>1\end{cases}$$

입니다. Table 1은 거리 $d$ 인 모든 전치에 대한 single-shot 평균 CNOT 수입니다. 굵은 값은 $f(d)$ 와 일치하지 않는 평균입니다.

토폴로지 $d=1$ $d=2$ $d=3$ $d=4$ $d=5$ $d=6$ $d=7$
공식 $f(d)$ 3 8 14 20 26 32 38
4L 3.00 8.00 14.00        
4Y 3.00 8.00          
5L 3.00 8.00 14.00 20.00      
5T 3.00 8.00 14.00        
6L 3.00 8.00 14.00 20.00 26.00    
6Y 3.00 8.00 14.00 20.00      
7L 3.00 8.00 14.00 20.33 26.00 32.00  
7Y 3.00 8.17 14.00 20.67      
8F 3.00 8.00 14.00 20.25 26.00 32.00  
8H 3.00 8.00 14.00 20.00 26.00    

Table 1의 어떤 토폴로지도 $d=7$ 열에는 값이 없습니다. 단일 샷에서는 몇몇 경우(굵은 값) 평균이 약간 높지만, best-of-ten으로 계산 예산을 늘리면 AlphaCNOT은 모든 전치에서 정확히 $f(d)$ 를 찾았습니다. 이는 거리 $d\ge 2$ 인 모든 전치 $\tau(i,j)$ 가 항상 $6d-4$ 개 CNOT으로 분해될 수 있음을 시사합니다.

💡 Key Takeaway AlphaCNOT 출력에서 읽힌 규칙성은 단순합니다. 거리 $d>1$ 전치의 CNOT 수가 SWAP 사슬보다 항상 정확히 1개 적다는 것입니다. 이 경험적 패턴이 다음 절의 구성적 정리로 승격됩니다.

Theorem 3.1: $6d-4$ 의 구성적 증명

Theorem 3.1. $G$ 를 토폴로지, $\tau(i,j)$ 를 끝점 거리 $d_G(i,j)>1$ 인 전치라 하자. 그러면 $\tau(i,j)$ 는 길이 최대 $6d-4$ 의 토폴로지 합법 CNOT 구현을 갖는다.

🛤️ 1. 라인으로의 환원

$i=v_0,v_1,\ldots,v_d=j$ 를 $G$ 에서 $i$ 에서 $j$ 로 가는 최단 경로라 합시다. 연속 쌍 $(v_k,v_{k+1})$ 은 모두 $G$ 의 간선이므로, 이 경로의 간선만 쓰는 CNOT 회로는 자동으로 $G$ 에서 토폴로지 합법입니다. 따라서 $v_k$ 를 $k$ 로 재표기한 라인 토폴로지 $0-1-\cdots-d$ 위에서 $\tau(0,d)$ 에 대해 증명하면 충분합니다.

$X_{a,b}$ 를 제어 $a$, 표적 $b$ 인 CNOT이라 하고, 게이트 곱은 적용 순서로 나열합니다.

🧱 2. 기저 사례 $d=2$: 8게이트 회로

라인 $0-1-2$ 위에서 다음 8개 게이트가 $\tau(0,2)$ 를 구현합니다.

$$X_{0,1}\,X_{1,0}\,X_{1,2}\,X_{0,1}\,X_{2,1}\,X_{1,0}\,X_{1,2}\,X_{0,1}$$

행 라벨 $(a,b,c)$ 에 순서대로 적용하면

$$(a,b,c)\mapsto(a,a+b,c)\mapsto(b,a+b,c)\mapsto(b,a+b,a+b+c)\mapsto(b,a,a+b+c)$$

$$\mapsto(b,b+c,a+b+c)\mapsto(c,b+c,a+b+c)\mapsto(c,b+c,a)\mapsto(c,b,a)$$

로, 정확히 두 끝점의 전치입니다. 중간 상태 $(b,a+b,a+b+c)$ 등은 순열이 아닌 선형 변환임에 주목할 만합니다. 즉 8게이트 회로는 이미 순열 부분군 밖을 지나갑니다.

🔁 3. 귀납 단계: 인접 전치로 감싸기

부분 경로 $1-2-\cdots-d$ 위에서 $\tau(1,d)$ 를 구현하는 길이 $6(d-1)-4$ 의 CNOT 회로 $C_{1,d}$ 가 있다고 가정합니다. 인접 전치 $\tau(0,1)$ 의 통상적 3-CNOT 구현을

$$S_0 = X_{0,1}\,X_{1,0}\,X_{0,1}$$

이라 하면, $S_0\,C_{1,d}\,S_0$ 이 $\tau(0,d)$ 를 구현합니다. 순열 수준에서

$$(0\,1)(1\,d)(0\,1)=(0\,d)$$

이기 때문입니다. 두 바깥 전치가 라벨 0과 1을 교환하므로, $(1,d)$ 를 $(0,1)$ 로 켤레하면 끝점 1이 0으로 바뀌고 $d>1$ 이므로 $d$ 는 고정됩니다. 길이는

$$3+\bigl(6(d-1)-4\bigr)+3=6d-4$$

입니다. $\blacksquare$

📐 4. 선형성의 기원과 최적성 추측

상한이 선형인 것은 재귀 구성의 자연스러운 결과입니다. 거리를 1 늘리는 것은 거리 $d-1$ 전치를 인접 전치 두 개(각 3 CNOT)로 감싸는 것이므로

$$L(d)=L(d-1)+6,\qquad L(2)=8 \;\Rightarrow\; L(d)=6d-4$$

입니다. Figure 3은 $d=4$ 에서 이 재귀 분해와 AlphaCNOT의 최적 출력을 비교합니다. AlphaCNOT 출력에서 $q_0$–$q_1$ 사이 SWAP $S_{0,1}$ 두 벌(6 CNOT)은 쉽게 식별되지만, 나머지 $\tau(1,4)$ 부분은 $S_{1,2}$ 와 $C_{2,4}$ 로 깔끔하게 분해되지 않습니다.

주장의 성격 내용
증명된 것 $6d-4$ 는 상한
증명되지 않은 것 $6d-4$ 의 최적성
계산적 증거 AlphaCNOT 결과 + 5큐비트 이하 모든 토폴로지의 완전 brute-force 탐색에서 $6d-4$ 보다 짧은 토폴로지 합법 구현 없음
저자의 입장 상한이 타이트하다고 추측. 일반 최적성 증명은 미해결

💡 Key Takeaway 증명은 “8게이트 기저 + 양쪽에 SWAP 3개씩 덧붙이기”라는 단순 귀납입니다. 절감 1개는 전부 기저 사례($d=2$ 에서 9 → 8)에서 나오며, 그 8게이트 회로의 중간 상태가 순열이 아니라는 점이 뒤의 융합 현상과 연결됩니다.

Global Transpositions: 가중 Cayley 그래프 위의 최소 비용 분해

Theorem 3.1은 모든 논리 전치에 구체적 토폴로지 합법 CNOT 분해와 명시적 CNOT 비용을 부여합니다. 그러면 순열을 인접 SWAP으로만 분해하는 대신, 모든 논리 전치 위에서 직접 탐색하고 각 전치를 그 CNOT 구현 비용으로 가중할 수 있습니다.

⚖️ 1. 전치 비용 $w_G$

$G=(V,E)$, $ V =n$ 이고 모든 무향 간선이 양방향 CNOT을 지원한다고 합시다. 전치 $\tau(i,j)$ 의 비용은

$$w_G(i,j)=\begin{cases}3,& d_G(i,j)=1,\\ 6\,d_G(i,j)-4,& d_G(i,j)>1\end{cases}$$

입니다. 모든 논리 전치는 인증된 CNOT 비용 $w_G$ 를 가지며, 같은 수의 CNOT으로 된 구성적 분해가 뒤에 있습니다. 비균일 비용을 갖는 전치로의 순열 최소 비용 분해는 일반 조합론 설정에서 Farnoud & Milenkovic(2012)이 연구했으며, 이 구성은 비용이 토폴로지 제약 CNOT 구현에서 유도되는 그 틀의 한 사례입니다.

🕸️ 2. 가중 Cayley 그래프 $\mathcal{T}_G$

정점이 $S_n$ 의 순열인 가중 그래프 $\mathcal{T}_G$ 를 정의합니다. 모든 $\pi\in S_n$ 과 모든 비순서쌍 ${i,j}\subseteq V$ 에 대해 간선

$$\pi \longrightarrow \pi\circ\tau(i,j), \qquad \text{가중치 } w_G(i,j)$$

를 추가합니다. 임의 전치들이 $S_n$ 을 생성하므로 $\mathcal{T}_G$ 는 연결되어 있습니다. $\mathcal{T}_G$ 의 경로는 대상 순열의 논리 전치 분해이고, 경로 가중치는 각 전치를 위 구성으로 전개했을 때 보장되는 CNOT 비용입니다.

가중 탐색이 반환한 경로가 $\sigma=\tau_1\tau_2\cdots\tau_m$ 이면 보고되는 CNOT 비용은

$$\ell_{\mathrm{GT} }^{G}(\sigma)=\sum_{r=1}^{m} w_G(\tau_r)$$

이고, 구체적 회로는 각 $\tau_r$ 을 두 끝점 사이 최단 경로에 연관된 CNOT 블록으로 치환해 얻습니다. “Global”인 이유는 분해를 순환별로 독립적이 아니라 대상 순열 전체에 대해 고르기 때문입니다.

🧭 3. 알고리즘

고정된 토폴로지 $G$ 에 대해:

단계 내용
1 $G$ 의 모든 쌍 그래프 거리 계산
2 각 논리 전치 $\tau(i,j)$ 에 가중치 $w_G(i,j)$ 부여
3 가중 Cayley 그래프 $\mathcal{T}_G$ 에서 항등 순열로부터 Dijkstra 실행
4 대상 $\sigma$ 에 대해 $\sigma$ 에서 항등까지의 선행자 사슬 복원 → 최소 가중 전치 분해
5 선택된 각 전치를 토폴로지 합법 CNOT 블록으로 전개
모든 쌍 최단 거리는 각 정점에서 BFS를 돌려 $O(n(n+ E ))$ 에 계산되며, 이 전처리 비용은 순열 공간의 $n!$ 상태 탐색에 비해 무시할 만합니다.

💡 Key Takeaway GT는 “인접 SWAP만 생성자로 쓰는 BFS”를 “모든 전치를 생성자로 쓰고 비용 $w_G$ 로 가중한 Dijkstra”로 바꾼 것입니다. 상태 공간은 여전히 $S_n$ 이며, 각 전치 블록이 끝날 때마다 순열 부분군으로 돌아옵니다.

GT의 보장과 세 합성 모델의 탐색 공간 비교

✅ 1. 두 부등식

GT의 출력은 자기 제한 모델 안에서 정확(exact) 합니다. 블록 비용 $w_G$ 를 갖는 논리 전치로의 모든 $\sigma$ 분해 중 Dijkstra는 최소 총 가중치를 갖는 것을 반환합니다. 또한 이 가중치는 항상 참 토폴로지 제약 CNOT 최적값의 상한입니다.

$$\ell_{\mathrm{CNOT} }^{G}(\sigma)\;\le\;\ell_{\mathrm{GT} }^{G}(\sigma)$$

$\mathcal{T}_G$ 의 모든 가중 간선 뒤에 구체적 토폴로지 합법 CNOT 회로가 있기 때문입니다. 그리고 GT는 게이트 단위로 전개한 최적 SWAP 라우팅을 지배합니다.

$$\ell_{\mathrm{GT} }^{G}(\sigma)\;\le\;3\,\ell_{\mathrm{SWAP} }^{G}(\sigma)$$

최적 인접 SWAP 분해를 잡으면, 각 인접 SWAP은 정확히 $d_G(i,j)=1$, 가중치 3인 전치 $\tau(i,j)$ 입니다. GT는 모든 전치 위에서 최소화하므로 그 SWAP 경로를 재현할 수 있고, $6d-4$ 항등식을 쓰는 더 긴 전치로 개선할 수도 있습니다.

🧩 2. “중간 기준선”으로서의 역할

이 부등식들은 GT가 유용한 중간 기준선인 이유를 설명합니다. SWAP 라우팅보다 엄격히 표현력이 크지만, 각 전치 블록 뒤에 여전히 $S_n$ 으로 돌아옵니다. 따라서 연속 블록 사이의 CNOT 수준 융합을 표현할 수 없습니다. 잔여 간격

$$\ell_{\mathrm{GT} }^{G}(\sigma)-\ell_{\mathrm{CNOT} }^{G}(\sigma), \qquad \text{또는 경험적으로} \qquad \ell_{\mathrm{GT} }^{G}(\sigma)-\ell_{\mathrm{AlphaCNOT} }^{G}(\sigma)$$

는 독립 전치 블록을 넘어서는 현상의 증거입니다.

📊 3. 탐색 공간과 복잡도 (Table 2)

세 가지 정확 탐색 관점은 주로 상태 공간과 생성자 집합에서 다릅니다. $m= E $ 라 하고, 상태 인코딩과 해시 조회의 상수 시간을 무시한 가장 직접적인 완전 탐색 비용은 다음과 같습니다.
방법 상태 공간 상태 수 생성자 단순 알고리즘 최악 시간
Optimal SWAP $S_n$ $n!$ $\lvert E\rvert$ 개 인접 SWAP BFS $O(n!\,\lvert E\rvert)$
Global Transpositions $S_n$ $n!$ $\binom{n}{2}$ 개 가중 전치 Dijkstra $O\bigl(n!\,n^2\log(n!)\bigr)$
Optimal CNOT $GL(n,\mathbb{F}_2)$ $\prod_{k=0}^{n-1}(2^n-2^k)$ $2\lvert E\rvert$ 개 방향 CNOT BFS $O\bigl(\lvert GL(n,2)\rvert\,\lvert E\rvert\bigr)$

🧱 4. 경도 결과와 확장 가능성

정확 합성은 세 모델 모두에서 계산적으로 어렵습니다.

문제 경도
임의 연결 그래프에서 최소 길이 인접 SWAP 열 Token Swapping 문제 = NP-hard (Miltzow et al. 2016)
토폴로지 제약 CNOT 합성 경도 결과 알려짐 (Jiang et al. 2020)
CNOT-distance 전역 연결에서도 NP-complete (Acuaviva et al. 2026)

이 결과들은 완전 탐색의 확장 가능한 대안을 요구합니다. 비균일 전치 비용 순열 분해의 근사 기법(Farnoud & Milenkovic 2012)은 $S_n$ 전체를 명시적으로 탐색하지 않는 GT의 근사 변형의 자연스러운 출발점입니다. 토폴로지 유도 비용 함수 $w_G$ 가 더 강한 근사 보장이나 특화 알고리즘을 허용하는지는 열린 질문입니다.

💡 Key Takeaway GT는 SWAP 모델과 CNOT 모델 사이의 정확한 샌드위치입니다. $\ell_{\mathrm{CNOT} }\le\ell_{\mathrm{GT} }\le 3\ell_{\mathrm{SWAP} }$ 이므로, GT와 AlphaCNOT 사이의 간격은 “전치보다 싼 전치”로는 설명되지 않는 별도의 현상을 가리킵니다.

Intermediate CNOT Fusion: 정의와 최소 예시

GT는 합성에 쓰는 기본 객체를 바꿔 SWAP 라우팅을 개선합니다. 그럼에도 AlphaCNOT이 만든 회로는 이 구성이 가능한 절감을 다 쓰지 못함을 보여줍니다. 여러 사례에서 직접 CNOT 합성은 전치 열을 전역적으로 이미 고른 완전한 GT 구성보다 짧은 회로를 만듭니다.

📐 1. GT 비용의 최소화 형태

연결 맵 $G=(V,E)$, $ V =n$, 순열 $\sigma\in S_n$ 에 대해 GT가 찾는 비용은

$$\ell^{G}{\mathrm{GT} }(\sigma)=\min{\substack{m\ge 0,\;\sigma=\tau_1\tau_2\cdots\tau_m\\ \tau_r\ \text{transposition},\ 1\le r\le m} }\;\sum_{r=1}^{m} w_G(\tau_r)$$

입니다. 즉 GT는 전치 분해 모델에 관해 최적입니다.

🧩 2. Definition 1 (Intermediate CNOT fusion)

$G$ 를 연결 맵, $\sigma\in S_n$ 이라 하자. 다음을 만족하는 토폴로지 합법 CNOT 회로 $\mathcal{C}$ 가 존재하면 $\sigma$ 가 $G$ 에서 (전치에 관한) 중간 CNOT 융합을 허용한다고 말한다.

$$\ell^{G}{\mathcal{C} }(\sigma) \;<\; \ell^{G}{\mathrm{GT} }(\sigma) \tag{1}$$

그런 회로 $\mathcal{C}$ 를 $\sigma$ 의 융합 증인(fusion witness) 이라 부릅니다. 즉 GT 모델이 고려하는 전치 블록의 최소 비용 연결보다 적은 CNOT으로 $\sigma$ 를 구현하는 토폴로지 합법 회로가 있을 때마다 융합이 일어납니다.

정의의 범위 내용
기준 블록 길이 2 순환(논리 전치)과 그 구성적 비용 $w_G$ (최적이라 가정)
가능한 확장 블록 라이브러리에 더 긴 순환(전치 + 3-순환 등)을 포함하는 합성 모델로의 일반화
확장하지 않은 이유 전치는 구성적 비용 $w_G$ 를 얻었지만, 더 긴 순환은 다른 도구가 필요하거나 각 순환의 최적 비용을 직접 계산해야 함

🔬 3. 최소 예시: 4L 위의 $\sigma=[2,3,1,0]$

라인 토폴로지 4L과 대상 순열 $\sigma=[2,3,1,0]$ 을 봅시다.

방법 분해 CNOT 수
Global Transpositions $\tau(1,2)\,\tau(0,1)\,\tau(1,3)$ $3+3+8=14$
AlphaCNOT (전체 순열에 직접 적용) Figure 4의 회로 13
양방향 BFS (토폴로지 합법 CNOT 회로 완전 탐색) — 13이 최적임을 인증

GT의 앞 두 블록은 인접 전치이고 마지막은 Section 4 구성으로 구현된 거리 2 전치입니다. 이 예는 중간 융합을 앞 절의 원격 전치 구성과 분리합니다. 후자는 논리 전치 하나의 비용을 줄이지만, 여기서는 세 전치 모두에 이미 GT 구성이 쓰는 개별 비용이 부여되어 있고, 추가 CNOT 1개는 완전한 순열을 하나의 회로로 합성할 때만 사라집니다. 수치상 개선은 작지만, 독립적으로 합성된 전치 블록의 비용 합으로 총비용을 얻는 모든 방법의 한계를 드러냅니다.

💡 Key Takeaway 융합은 “전치 비용을 더 깎는 것”이 아니라 “전치 경계를 지우는 것”입니다. 정의 (1)은 GT 최적값을 기준으로 삼으므로, 융합 증인의 존재는 전치 분해 모델 자체가 CNOT 최적값에 도달하지 못함을 뜻합니다.

전체 평가: SWAP × 3 vs GT vs AlphaCNOT vs 최적 CNOT (Table 3)

🧪 1. 설정

항목 내용
대상 토폴로지당 무작위 순열 100개 (4L·4Y는 24개 순열 전부)
SWAP × 3 최적 SWAP 알고리즘의 SWAP 수 × 3
GT Global Transpositions
AlphaCNOT best-of-ten (10회 실행 후 최선 선택)
Optimal CNOT 5큐비트 이하에서 양방향 BFS로 얻은 평균 최적 CNOT 수

📊 2. 결과 표

토폴로지 SWAP $\times 3$ Global Transpositions AlphaCNOT Optimal CNOT
4L 8.64 8.18 8.03 8.03
4Y 8.04 7.83 7.59 7.59
5L 15.03 14.21 13.73 13.71
5T 13.50 12.92 12.46 12.42
6L 22.59 21.24 20.37 –
6T 19.20 18.28 17.67 –
6Y 18.78 17.86 17.26 –
7L 32.28 30.23 28.97 –
7T 27.45 25.89 25.01 –
7Y 26.40 24.95 24.53 –
8F 37.71 35.34 34.07 –
8H 32.40 30.82 29.92 –
8T 38.67 36.36 35.23 –
8T2 33.27 31.57 30.71 –

📈 3. 읽기

비교 평균 CNOT 수 절감
SWAP 합성 23.85 —
Global Transpositions 22.55 SWAP 대비 1.31
AlphaCNOT 21.83 GT 대비 0.72 (= 3.2%)

AlphaCNOT은 표의 모든 토폴로지에서 GT보다 낮은 평균 CNOT 수를 얻습니다. GT 대비 간격은 모든 제약 토폴로지에 존재하며 대상당 평균 0.15–1.27 CNOT 범위입니다. 4큐비트(4L·4Y)에서는 AlphaCNOT 평균이 양방향 BFS 최적값과 정확히 일치하고, 5큐비트에서는 최적값보다 0.02–0.04 높습니다.

이 결과는 AlphaCNOT이 드러낸 구조의 2단계 해석을 뒷받침합니다.

단계 설명하는 것
원격 전치 합성 ($6d-4$) 논리 전치를 완전한 SWAP 사슬로 구현할 필요가 없는 이유
중간 융합 전치를 전역적으로 고르고 개선된 개별 비용을 부여한 뒤에도, 독립 블록으로 취급하면 남는 추가 CNOT 절감

🖼️ 4. 추가 예시 (Figure 5)

저자들은 GT와 AlphaCNOT의 해를 비교하는 비자명한 중간 융합 사례를 시각화합니다.

순열 토폴로지
$[2,4,3,1,0]$ 5T
$[1,5,0,4,2,3]$ 6L
$[3,0,5,1,2,4]$ 6T
$[3,2,0,4,5,1]$ 6Y
$[4,3,7,6,5,1,2,0]$ 8T2

AlphaCNOT은 최적이 아니지만, $S_n$ 위에서 최적 합성을 해도 얻을 수 없는 비자명한 CNOT 절감을 찾습니다. 이는 중간 CNOT 융합이 순열 회로의 효율적 CNOT 분해에 주요한 역할을 한다는 것을 시사합니다.

💡 Key Takeaway 평균 절감 2.02개(23.85 → 21.83) 중 약 65%(1.31)는 결정론적 GT가 설명하고, 나머지 35%(0.72)는 전치 모델 밖의 융합입니다. 4큐비트에서 AlphaCNOT이 BFS 최적과 일치한다는 점은 best-of-ten 설정의 탐색 품질에 대한 간접 증거입니다.

왜 융합이 가능한가: $S_n$ 과 $GL(n,\mathbb{F}_2)$ 의 차이

🧮 1. 두 탐색 공간

방법 중간 상태가 사는 공간
SWAP 라우팅 순열 부분군 $S_n$
Global Transpositions 순열 부분군 $S_n$ (각 전치 블록 뒤에 복귀)
직접 CNOT 합성 (AlphaCNOT, Optimal CNOT) 가역 이진 선형 변환군 $GL(n,\mathbb{F}_2)$ 전체

융합에 의한 추가 절감은 여러 논리 연산의 부분 효과를 함께 합성할 때 생깁니다. 중간 접두 변환은 일시적으로 순열 부분군 $S_n\subset GL(n,\mathbb{F}_2)$ 을 떠나 더 일반적인 선형 가역 변환을 지나간 뒤 대상 순열로 돌아올 수 있습니다. 그러면 부분 효과가 독립적으로 합성된 전치의 경계를 넘어 공유됩니다.

🔭 2. SWAP–CNOT 분리의 구조적 설명

이 현상은 SWAP 기반 합성과 직접 CNOT 합성의 분리에 대한 가능한 설명을 줍니다. SWAP 라우팅과 GT는 순열 부분군 안에서 탐색하지만, 직접 CNOT 합성은 더 큰 가역 이진 선형 변환 공간을 이용할 수 있습니다. 순열 부분군 밖의 중간 상태가 대상 순열로 가는 더 짧은 경로를 제공할 수 있는 것입니다.

저자들의 결론은 두 겹입니다. SWAP 최적 합성과 CNOT 효율 합성 사이의 간격은 더 싼 전치에서만 오는 것이 아니라, CNOT 수준에서 이용 가능한 더 풍부한 중간 상태 공간에서도 옵니다.

🔗 3. Theorem 3.1 의 기저 회로와의 연결

Section 3의 8게이트 기저 회로 자체가 이미 $(b,a+b,a+b+c)$ 같은 비순열 중간 상태를 거칩니다. 즉 $6d-4$ 절감의 원천인 기저 사례도 작은 규모의 “순열 부분군 이탈”이며, GT는 그 이탈을 전치 블록 내부로 봉인한 것입니다. Intermediate CNOT Fusion은 그 이탈이 블록 경계를 넘을 때 생기는 추가 이득입니다. (이 연결은 논문이 명시적으로 서술하지는 않지만, 증명의 행 라벨 추적에서 직접 읽힙니다.)

💡 Key Takeaway 핵심 대비는 상태 공간입니다. $|S_n|=n!$ 대 $|GL(n,\mathbb{F}2)|=\prod{k=0}^{n-1}(2^n-2^k)$ 이고, 후자에만 존재하는 중간 상태를 거치는 경로가 때로 더 짧습니다. SWAP 최소화가 CNOT 최소화를 놓치는 이유가 이 공간 차이로 설명됩니다.

AI-assisted discovery: 최적화기에서 발견 도구로

이 논문의 방법론적 주장은 결과 자체만큼 중요합니다. AlphaCNOT이 만든 회로는 검사해서 반복 패턴을 찾고 구조적 가설을 세울 수 있는 구체적 대상입니다.

🔁 1. 두 수준의 구조와 두 가지 결말

관찰된 구조 성격 이 논문에서의 처리
원격 전치의 $6d-4$ 절감 국소적 구성적 증명(Theorem 3.1) → 결정론적 알고리즘(GT)으로 완전히 형식화
Intermediate CNOT Fusion 전역적 정의(Definition 1)와 실험적 관찰(Table 3, Figure 4·5)까지. 아직 완전히 특성화되지 않음

첫 번째 경우 패턴이 구성적 증명과 결정론적 합성 알고리즘으로 이어졌고, 두 번째 경우 중간 상태를 순열 부분군으로 제한하는 접근의 한계를 드러냈습니다.

🧪 2. 탐색 도구로서의 사용 조건

조건 이 논문에서의 충족 방식
출력의 검사 가능성 패리티 행렬 상태와 CNOT 열은 수작업으로 추적 가능 (Figure 2·3·4)
반복성 확인 여러 토폴로지·모든 전치에 대한 single-shot 평균 (Table 1)
예산 증가에 의한 안정화 best-of-ten에서 모든 전치가 $f(d)$ 에 도달
독립 검증 5큐비트 이하 완전 탐색, 양방향 BFS로 최적성 인증

AI 합성기의 비결정성은 여기서 단점이 아니라 탐색 폭으로 쓰였습니다. 단일 샷의 굵은 값(Table 1)이 best-of-ten에서 사라진 것이 그 예입니다.

💡 Key Takeaway “AI가 더 짧은 회로를 찾았다”에서 멈추지 않고, 그 회로를 읽어 정리·알고리즘·새 개념을 뽑아낸 것이 이 논문의 기여입니다. 형식화에 성공한 국소 패턴과 아직 정의 단계인 전역 현상을 분명히 구분해 둔 점도 특징입니다.

열린 질문과 한계

저자들은 Section 6에서 열린 방향을 정리합니다. 여기에 본문에서 읽히는 범위상의 한계를 덧붙입니다.

❓ 1. 저자가 제시한 열린 질문

질문 내용
융합의 이론적 특성화 언제 융합이 가능한가, 절감이 얼마나 클 수 있는가, 대상 순열과 결합 그래프에서 직접 융합 기회를 식별할 수 있는가
비순열 중간 변환의 필요성 일부 순열 회로의 CNOT 최적 구현에 순열 부분군 밖 중간 변환이 필수인가, 아니면 더 제한된 중간 변환 클래스 안에서도 같은 길이의 회로가 항상 존재하는가
방법론 확장 AlphaCNOT이 드러낸 패턴에서 새 결정론적 합성 규칙을 유도하고, 같은 방법론을 다른 회로족과 양자 컴파일 문제로 확장
$6d-4$ 의 최적성 5큐비트 이하 완전 탐색에서 반례가 없지만 일반 증명은 미해결
GT의 근사 변형 Farnoud & Milenkovic(2012)의 근사 기법을 출발점으로, $S_n$ 전체 탐색을 피하는 변형. $w_G$ 특유의 더 강한 보장이나 특화 알고리즘 가능성

📏 2. 본문에서 읽히는 범위상의 한계

  • 규모 : 평가는 4–8큐비트 토폴로지에 국한되며, 최적 CNOT 값은 5큐비트 이하에서만 보고됩니다. 6큐비트 이상에서 AlphaCNOT과 참 최적값의 간격은 알 수 없습니다.
  • GT의 확장성 : GT는 $n!$ 상태 Dijkstra이므로 그 자체로는 큰 $n$ 에 적용할 수 없습니다. 논문도 이를 인정하고 근사 변형을 향후 과제로 둡니다.
  • 융합의 양적 범위 : Table 3의 GT–AlphaCNOT 간격(0.15–1.27)은 AlphaCNOT 상한 기준이므로 융합의 하한일 뿐입니다. 참 융합 이득은 6큐비트 이상에서 측정되지 않았습니다.
  • 블록 라이브러리 : Definition 1은 전치에 관한 융합만 다룹니다. 3-순환 등을 포함한 모델에서는 “융합”으로 분류되는 사례가 줄어들 수 있으며, 저자들도 이 확장을 명시적으로 미뤘습니다.
  • 벤치마크 회로 : Faro et al.(2024)의 상수 깊이 회로가 출발 동기였지만, Table 3 실험은 무작위 순열에 대한 것입니다. 깊이 최적 회로를 CNOT 수준에서 얼마나 줄이는지에 대한 별도 수치는 본문에 없습니다.
  • Table 1의 빈칸 : $d=7$ 열은 어떤 토폴로지에도 값이 없으며, 각 토폴로지의 최대 거리까지만 채워져 있습니다.

💡 Key Takeaway 확립된 것은 “$6d-4$ 상한”, “GT ≤ 3·SWAP”, “융합의 존재”이고, 열려 있는 것은 “$6d-4$ 의 최적성”, “융합의 특성화와 크기”, “큰 $n$ 으로의 확장”입니다. 이 논문을 인용할 때는 결과가 8큐비트 이하 소규모 토폴로지에서 얻어졌다는 조건을 함께 적어야 합니다.