Finding diagonal logical gates in CSS codes and circuits

기술 요약: CSS 코드 및 회로에서의 대각 논리 게이트 탐색

문제 정의
대규모, 결함 허용(fault-tolerant) 범용 양자 컴퓨터의 실현을 위해서는 비-클리포드(non-Clifford) 논리 게이트의 효율적인 구현이 필수적이다. 클리포드 연산은 스테빌라이저 형식(stabilizer formalism) 내에서 비교적 간단하지만, 비-클리포드 게이트는 상당한 과제를 안겨준다. 현재의 접근 방식들은 매직 상태 증류(magic state distillation), 가로형(transversal) 비-클리포드 게이트(때로는 코드 스위칭과 결합됨), 또는 신드롬 추출 회로에 삽입되는 "시공간(spacetime)" 논리 게이트에 의존하는 경우가 많다. 핵심적인 과제는 주어진 물리적 안사츠(ansatz) 게이트 집합으로부터 구성된, 국소성 보존 대각 비-클리포드 논리 게이트(예: $T$, $CS$, 또는$CCZ$)를 허용하는 CSS(Calderbank-Shor-Steane) 코드 또는 회로를 식별하는 것이다. 삼직교성(triorthogonality) 조건과 같은 기존 방법들은 특정 게이트 유형에 국한되거나 임의의 국소성 보존 회로에 대한 일반성이 부족하다.

방법론
본 논문은 주어진 CSS 코드(또는 회로)의 논리 게이트 중, 규정된 대각 안사츠 게이트들로 구성된 모든 논리 게이트를 찾는 효율적인 알고리즘을 제안한다. 핵심적인 이론적 통찰은 대각 논리 게이트가 주어진 코호몰로지 클래스(cohomology class) 내의 모든 $Z$-기저 구성에 대해 동일한 위상을 할당할 때만 코드 공간을 보존한다는 것이다.

1. 수학적 정식화:

   • 대각 게이트 $V_c$가 계산 기저 상태 $|a\rangle$에 작용하는 방식은 위상 함수 $S_c(a)$로 정의된다. 클리포드 계층의 세 번째 레벨에 있는 게이트들의 경우, $S_c(a)$는 $a_i a_j a_k$ ($CCZ$의 경우),$a_i a_j$($CS$의 경우), 또는$a_i$($T$의 경우)와 같은 항들을 포함하는 "3차(third-order)" 함수이다.
   • 코드 공간 보존을 위한 조건은 $S_c(a)$가 동일한 코호몰로지 클래스 내의 모든 $a$에 대해 상수여야 한다는 것이다. 이는 $S_c(a + A e_j) = S_c(a)$가 모든 $X$-스테빌라이저 생성자 $A e_j$에 대해 성립해야 함을 의미하며, 여기서 $A$는 $X$-체크 행렬이다.
   • 이 조건은 위상 함수 $S_c$를 $X$-체크 행렬에 의해 당겨온(pullback) 결과인 $S_c \circ A$가 자명한(trivial) 위상 함수가 되어야 한다는 요구사항과 동치이다.

2. 풀백 호모모피즘 (Pullback Homomorphism, $A^*$):

   • 저자들은 물리적 안사츠 게이트의 계수($c \in G_{phys}$)를 유도된 $X$-체크 상의 위상 함수 계수로 매핑하는 군 호모모피즘(group homomorphism) $A^*$를 정의한다.
   • $G_{phys}$는 클리포드 계층의 서로 다른 레벨에 대응하는 유한 아벨 2-군(finite abelian 2-groups, 예: $\mathbb{Z}_2, \mathbb{Z}_4, \mathbb{Z}_8$)의 곱이다.
   • 유효한 논리 게이트의 집합은 이 호모모피즘의 커널(kernel), 즉 $A^* c = 0$인 집합과 정확히 일치한다.

3. 알고리즘 구현 (필트레이션, Filtration):

   • $A^*$의 커널을 효율적으로 계산하기 위해, 저자들은 스미스 노름 형식(Smith normal form, 큰 정수 산술을 수반함)을 사용하는 대신, 문제를 이진 필드($\mathbb{Z}_2$) 상의 일련된 커널 계산으로 분해하는 "필트레이션" 방법을 도입한다.
   • 알고리즘은 $X \pmod 2$, $X \pmod 4$ 등의 커널을 반복적으로 계산하여, 하위 차수 군의 해를 상위 차수 군으로 리프팅(lifting)한다. 이는 $\ker(X) \subset \ker(X \pmod 4) \subset \ker(X \pmod 2)$라는 사실을 활용한다.
   • 서브루틴은 비트 패킹(bit-packing)을 통해 가속화될 수 있는 표준 이진 선형 대수(가우스 소거법/RREF)에 의존한다.

4. 일반화:

   • 시공간 게이트: 본 방법은 대각 게이트가 신드롬 추출 회로에 삽입되는 "시공간 국소 논리 게이트"로 확장된다. 이는 회로를 텐서 네트워크(또는 경로 적분)로 모델링하고, 동일한 풀백 로직을 $Z$-디코딩 그래프에 적용함으로써 이루어진다.
   • 높은 레벨 및 임의의 게이트: 이 프레임워크는 위상 함수의 정의와 계수 군을 조정함으로써 클리포드 계층의 더 높은 레벨 및 임의의 대각 게이트(비-계층적 게이트)로 일반화된다.
   • 큐디트(Qudits): 이 방법은 $\mathbb{Z}_{d_i}$ 상의 적절한 고차 함수를 정의함으로써 소수 및 합성수 차원의 큐디트로 일반화된다.

주요 기여

• 통합된 프레임워크: 본 논문은 가로형 게이트, 국소성 보존 논리 회로, 시공간 논리 게이트의 탐색을 특정 군 호모모피즘 $A^*$의 커널을 찾는다는 하나의 대수적 조건 아래 통합하는 일반적인 형식론을 제공한다.
• 효율적인 알고리즘: $O(n)$개의 큐비트(또는 게이트)를 가진 시스템에 대해 나이브한 실행 시간이 $O(n^3)$인 빠른 알고리즘을 제시하며, 문제를 이진 행렬 연산으로 환원하는 필트레이션 기술을 사용한다.
• 유연성: 사용자가 (비-국소적 또는 폴디드 게이트를 포함한) 임의의 안사츠 게이트 집합을 지정할 수 있으며, 번역 불변성(translation invariance)을 부과하지 않고도 그로부터 발생하는 모든 논리 게이트를 찾을 수 있다.
• 구현: 특화된 패키지(twogroup-linalg)를 포함한 Python 구현이 제공된다.

결과 및 사례

• 알고리즘은 2D 및 3D 토릭 코드, 컬러 코드, 프랙톤 코드, 그리고 바이베리트 바이크레클(bivariate bicycle) 코드에 대해 알려진 논리 게이트들을 성공적으로 복구하였다.
• "듀얼 3D 컬러 코드"에서 논리적 $T$-게이트와 동등한 기능을 수행하는 이전에 알려지지 않은 3차 대각 게이트를 발견하였다.
• 본 방법은 시스템 크기에 관계없이 $O(1)$ 시간(단위 셀 파라미터에만 종속) 내에 번역 불변 논리 게이트를 찾는 것을 입증하였다.
• 800개의 큐비트를 가진 2D 컬러 코드의 경우, 비-번역 불변 케이스에 대해 표준 노트북에서 약 30초가 소요되었다.

의의 및 주장
본 논문은 자신의 방법이 CSS 코드 및 회로에 대한 결함 허용 논리 게이트의 공간을 탐색하는 체계적이고 효율적인 방법을 제공한다고 주장한다. 문제를 커널 계산으로 재구성함으로써, 삼직교성 조건을 임의의 클리포드 계층 곱 및 국소성 보존 회로로 일반화한다.

저자들은 본 방법이 임의의 대각 게이트를 찾을 수 있지만, 결함 허용 환경에서의 물리적 실현 가능성은 아마도 이러한 게이트들을 클리포드 계층으로 제한할 것이라고 언급한다(이는 Bravyi-Koenig 유형의 논거와 일치한다). 이 연구는 이 접근 방식이 바람직한 논리 게이트 특성을 가진 새로운 qLDPC 코드를 발견하거나, 코드 경계 및 도메인 월(domain wall)으로의 논리 게이트 확장을 최적화하는 데 사용될 수 있음을 시사한다. 저자들은 현재의 $O(n^3)$ 밀집(dense) 구현이 이미 코드의 논리 기저를 찾는 것과 경쟁할 만한 수준임을 인정하면서, qLDPC의 희소성(sparsity)을 통한 추가적인 최적화(예: Wiedemann 알고리즘 또는 로컬 커널 분해) 가능성을 열어두며 미래의 속도 향상에 대해 겸허한 태도를 유지한다.