기술 요약: 임의 네트워크 토폴로지를 가진 분산 양자 아키텍처를 위한 클리포드 회로 합성

문제 정의

본 논문은 큐비트가 별도의 블록(예: 얽힘이나 논리 큐비트가 블록 코드에 인코딩된 별도의 양자 프로세서)으로 분할되는 분산 양자 아키텍처를 위한 양자 회로 컴파일 문제를 다룹니다. 이러한 시스템에서 비로컬 연산(파티션 간에 작용하는 게이트)은 로컬 연산에 비해 시간 및 오류율 측면에서 훨씬 더 비용이 많이 듭니다. 예를 들어, 제안된 "바이시클(bicycle) 아키텍처"에서 비로컬 연산은 로컬 연산보다 오류율이 두 자릿수 더 높습니다.

핵심 문제는 파티션 간의 임의적인 연결 제약을 준수하면서 비로컬 게이트의 수를 최소화하도록 CNOT, Clifford, 그리고 Clifford+RZ(Clifford+T 포함) 회로에 대해 동등한 회로를 합성하는 것입니다. 기존 방식은 주로 (텔레포테이션 등을 통해) 기존의 비로컬 게이트를 최소화하기 위해 큐비트를 배치하고 스케줄링하는 데 집중하며, 회로 재합성(resynthesis)을 통해 필요한 비로컬 게이트의 수 자체를 근본적으로 줄이는 데는 초점을 맞추지 않습니다.

방법론

1. 회로 표현

저자는 모든 로컬 클리포드 연산을 추상화하는 새로운 회로 표현법을 도입합니다. 모든 Clifford+RZ 회로는 다음과 같이 분해됩니다:

• 로컬 클리포드 회로 ($C_L$): 파티션 내에서만 작동하는 연산들을 포함합니다.
• 비로컬/비클리포드 DAG ($D(C_N)$): 남은 연산들을 나타내는 유향 비순환 그래프(DAG)로, 두 가지 게이트 유형으로 구성됩니다:
  • 파울리 지수 함수 ($P(A, \theta)$): 비클리포드 연산(예: T-게이트)을 인코딩하는 $e^{-i\theta/2 A}$.
  • 일반화된 CNOT 게이트 ($C(A, B)$): 서로 다른 파티션에 있는 파울리 문자열 $A$와 $B$에 대해 $e^{i\frac{\pi}{4}(A \otimes I + I \otimes B - A \otimes B - I \otimes I)}$로 정의됩니다. 결정적으로, 모든 일반화된 CNOT은 정확히 하나의 비로컬 CNOT 게이트(및 로컬 클리포드)를 사용하여 구현될 수 있으므로, 이 게이트들의 최소화는 비로컬 자원의 최소화와 동일합니다.

2. 합성 알고리즘

저자는 기존의 재합성 기술을 블록 행렬 및 블록 타블로(tableau)에 적용하여, 파티션을 원자적 단위로 취급하도록 확장했습니다.

• BlockRowCol (CNOT 회로용):

  • 패리티 행렬에 가우스 소거법을 사용하는 RowCol 알고리즘을 기반으로 합니다.
  • 핵심 통찰: 분산 회로의 패리티 행렬을 블록 행렬로 간주합니다. 목표는 블록 행 연산을 사용하여 비대각 블록(파티션 간 상호작용)을 제거하는 것입니다.
  • 메커니즘: 블록 행 덧셈은 일련의 일반화된 CNOT 게이트를 적용하는 데 해당합니다. 필요한 게이트 수는 블록 덧셈에 사용되는 계수 행렬의 **계수(rank)**에 의해 결정됩니다.
  • 연결성: 블록 연산을 수행할 때 임의의 파티션 연결성을 준수하기 위해 슈타이너 트리(Steiner trees)를 사용합니다.
  • 최적성: $k=2$인 파티션의 경우, 이 알고리즘은 ZX 유형의 일반화된 CNOT에 대해 최적의 비로컬 게이트 수의 2배 이내임을 증명하였습니다. 점근적으로 $k = o(n / \log n)$일 때 최적입니다.

• DistRowCol (Clifford 회로용):

  • **스테빌라이저 타블로(stabilizer tableaux)**를 사용하여 합성을 전체 클리포드 회로로 확장합니다.
  • 메커니즘: 스테빌라이저 타블로를 블록 대각 형태로 줄임으로써 파티션을 하나씩 분리합니다. 제거 과정 중 구조적 무결성을 보장하기 위해 기존 스테빌라이저/디스테빌라이저와 교환(commute)하는 파울리 문자열을 찾는 렘마(lemma)를 활용합니다.
  • 복잡도: 최대 $2n(k-1)$개의 비로컬 게이트를 사용하며, 이는 BlockRowCol의 점근적 경계와 일치합니다.

• Clifford+RZ 최적화:

  • 분포: 위상 다항식 합성 방법을 적응시켜 파울리 지수 함수를 파티션 간에 분산시키며, 미래의 게이트 수를 최소화하는 피벗 파티션을 선택하기 위해 휴리스틱을 사용합니다.
  • 폴딩(Folding): 일반화된 CNOT 폴딩을 도입합니다. 이는 위상 폴딩(phase-folding)과 유사한 기술로, 공유된 파울리 문자열 인자를 가진 인접한 일반화된 CNOT 게이트($C(A, B_1) \cdot C(A, B_2)$)를 결합하여 개수를 줄이며, 이 과정에서 로컬 클리포드 보정이 도입될 수 있습니다.
  • 서브회로 탐지: DAG 표현 내에서 CNOT 또는 클리포드 서브회로를 탐지하는 방법(볼록 비순환 파티션 및 빔 서치 사용)을 제안하여 특화된 BlockRow-Col 또는 DistRowCol 루틴을 적용합니다.

주요 결과 및 벤치마크

저자는 이 알고리즘들을 구현하여 pytket-dqc(큐비트 배치 및 텔레포테이션에 기반한 최첨단 분산 회로 최적화 도구) 및 표준 재합성 방법들과 벤치마크를 수행했습니다.

• CNOT 회로:

  • 깊은 회로와 더 큰 큐비트 수에 대해, BlockRowCol은 일반적으로 pytket-dqc와 재합성을 결합한 결과보다 우수하거나 대등한 성능을 보입니다.
  • BlockRowCol은 특히 선형 최근접 이웃(linear nearest-neighbor) 아키텍처에서 다른 방법들에 비해 비로컬 게이트 수를 크게 줄이는 데 효과적입니다.
  • 얕은 회로의 경우, 재합성의 오버헤드와 큐비트 재정렬의 이점 때문에 (현재 구현에는 포함되지 않은) 큐비트 재정렬을 지원하는 pytket-dqc(재합성 없이)가 더 나은 성능을 보이기도 합니다.

• Clifford 회로:

  • DistRowCol은 깊은 회로에 대해 재합성을 포함한 pytket-dqc보다 일관된 우위를 보이며, 특정 연결 토폴로지(2D 그리드 vs 선형)에 상당히 둔감합니다.

• Clifford+T 회로:

  • 결과가 엇갈립니다. 파티션이 많은 아키텍처($k=9$)의 경우, 저자의 방법을 포함한 재합성 방법들이 pytket-dqc 단독 사용보다 성능이 떨어지는 경우가 많습니다. 저자는 이것이 저자의 특정 방법의 결함이라기보다, 분산 환경에서 Clifford+T에 대한 일반적인 재합성의 비효율성 때문이라고 제안합니다.
  • $k=2$인 경우, 다른 방법들과 대등한 성능을 보입니다.

• 확장성:

  • 알고리즘의 실행 시간은 매우 효율적입니다. 저자는 512 큐비트 및 128 파티션 규모의 인스턴스(게이트 수 $> 2 \cdot 10^5$)를 몇 초 만에 성공적으로 실행하였으며, 이는 하이퍼그래프 분할에 기반한 pytket-dqc보다 훨씬 빠른 속도입니다.

의의 및 주장

본 논문은 다음과 같은 기여를 주장합니다:

1. 점근적 최적성: BlockRowCol 알고리즘은 파티션 수 $k$가 큐비트 수 $n$에 비해 작은 경우($k = o(n / \log n)$), 분산 환경에서의 CNOT 회로 합성에 대해 점근적으로 최적임을 증명했습니다.
2. $k=2$에 대한 근사 최적성: 두 개의 파티션에 대해, 이 방법은 ZX 유형의 일반화된 CNOT를 사용하는 회로에 대해 최적해의 상수 배(구체적으로 최대 2배) 이내임을 보여줍니다.
3. 일반 프레임워크: 패리티 행렬, 스테빌라이저 타블로, 위상 다항식에 기반한 기존 합성 기술들이 블록 구조를 통해 분산 환경으로 자연스럽게 일반화될 수 있음을 입증했습니다.
4. 실질적 응용:
   • CSS 코드: 이 방법은 CSS 코드에서 $O(nk)$의 블록 내 파울리 측정과$O(k^2)$의 블록 간 가로지르는(transversal) CNOT를 사용하여 논리적 CNOT 회로를 합성할 수 있게 하며, 이는 블록 간 연결성과 무관합니다.
   • 팬텀 코드(Phantom Codes): 논리적 큐비트 수가 아닌 블록 수에 따라 제곱으로 스케일링되는 $6k(k-1)$ CNOT 연산의 상한을 제공합니다.
   • 텐서 네트워크(Tree Tensor Networks): 이 방법은 텐서 네트워크 시뮬레이션에서 고차원 게이트를 최소화하는 데 사용될 수 있으며, 고전적 시뮬레이션 비용에 대한 점근적 개선을 제공합니다.

저자는 자신의 방법이 예비적인 단계이며, 큐비트 재정렬 및 휴리스틱 튜닝과 같은 실질적인 세부 사항이 더 최적화될 수 있음을 인정하며 겸허한 태도를 유지합니다. 또한, 이 접근 방식이 기존의 배치 및 스케줄링 전략을 대체하기보다는 이를 보완하는 것임을 강조합니다.