기술 요약: 대규모 양자 코드 및 회로 거리의 인증

문제 정의

양자 오류 정정(QEC)은 논리적 오류의 억제를 특성화하고 자원 추정치를 안내하기 위해 코드 거리(code distance, $d$)와 회로 거리(circuit distance, $d_{circ}$)에 의존한다. 코드 거리는 논리적 연산자의 최소 가중치이며, 회로 거리는 신드롬 측정 회로에서 검출기를 작동시키지 않으면서 논리적 관측량을 반전시키는 결함(fault)의 최소 개수이다.

이러한 거리들을 계산하는 것은 대규모 시스템에 대해 계산적으로 매우 어렵다(intractable). 고전 선형 코드의 최소 거리를 찾는 것은 NP-hard 문제이며, 회로 거리 문제는 현재 하드웨어 제안에서 $10^4$에서 $10^5$개의 결함 메커니즘을 포함하므로 훨씬 더 거대하다. 결과적으로, 많은 발표된 거리들은 휴리스틱 탐색(예: 무작위 디코딩, 정보 집합 샘플링, 또는 감지되지 않는 오류를 찾는 Stim의 탐색)을 통해 도출된 단순한 **상한값(upper bounds)**에 불과하다. 이러한 휴리스틱들은 발견된 오류가 최소 가중치임을 인증하는 데 실패하는 경우가 많으며, 이는 잠재적인 과대평가로 이어진다. 정수 계획법(integer programming), MaxSAT, 연결 클러스터 열거(connected-cluster enumeration)와 같은 정확한 방법들이 존재하지만, IBM의 이중 바이크로(bivariate bicycle) 코드나 Google의 모듈형 쌍곡선(modular hyperbolic) 코드와 같이 근접 미래 하드웨어에 제안된 회로 규모로 확장하는 데 어려움을 겪는다. 이러한 불확실성은 아키텍처 연구가 가정된 거리에 의존하게 만들어, 논리적 오류율 및 자원 요구 사항에 대한 예측에 상당한 오류를 유발한다.

방법론

저자들은 코드와 회로 거리를 **열대 분할 함수(tropical partition functions)**로 표현함으로써, 대규모 환경에서 코드 및 회로 거리를 정확하게 계산할 수 있는 통합 프레임워크를 제안한다. 거리는 민-플러스 대수(min-plus algebra)에서의 자유 에너지의 영온도 극한으로 공식화된다:
$$Z_M(t) = \min \{ |e| : Me = t \}$$
여기서 $M$은 제약 행렬(코드의 경우 체크 행렬, 회로의 경우 검출기 행렬)을 나타내며, $t$는 신드롬 및 논리적 레이블 제약을 나타낸다.

이 함수들을 평가하기 위해 저자들은 비용 모델에 의해 조정되는 세 가지 정확한 알고리즘을 사용한다:

1. 조밀한 랭크 기반 동적 계획법 (Rank DP): 동일한 경계 상태를 공유하는 부분 할당의 최소 가중치를 저장하는 민-플러스 동적 계획법이다. 복잡도는 문제의 분해(decomposition)에 따른 컷 랭크(cut rank 또는 rank-width)에 따라 결정된다. 표면 코드(surface codes) 및 합성 코드(concatenated codes)와 같이 랭크 폭이 낮은 문제에 효율적이다.
2. 가중치 절단 랭크 DP (Weight-Truncated Rank DP): 순방향 및 역방향 동적 계획법 테이블을 병합하지만, 규정된 가중치 예산 내의 항목만 저장하는 양방향 탐색이다. 이는 BEAST 알고리즘의 양방향 탐색과 민-플러스 상태 병합을 결합한 것으로, 거리는 작지만 랭크 폭이 높은 문제에 효과적이다.
3. 가중치 제한 탐색 (Weight-Bounded Search): 증가하는 가중치 예산 내에서 결함 집합을 탐색하는 전수 조사 방식이다. 이는 탐색 공간을 가지치기하기 위해 정준 브랜칭(canonical branching), 덮개(covering bounds, 쌍대 선형 계획법 경계), 그리고 완결 테이블(completion tables, meet-in-the-middle)을 사용한다. 이 방법은 거리가 큰 qLDPC 코드에 특히 효과적이다.

축약 및 인증 (Reductions and Certificates):
대규모 회로를 처리하기 위해, 이 방법은 회로 축약(circuit reductions) 기법을 사용한다:

• 섹터 축약 (Sector Reduction): 검출기를 단일 메모리 기저(basis)로 제한한다.
• 시간 붕괴 (Time Collapse): 각 체크에 대한 검출기들을 모든 라운드에 대해 합산하여, 전체 회로의 하한값 역할을 하는 더 작은 문제를 생성한다.
• 리프팅 (Lifting): 붕괴된 문제의 최소 가중치 해를 전체 회로로 다시 매핑하려고 시도한다. 만약 해가 리프팅되면 하한값이 일치하여 정확한 거리가 인증된다. 리프팅되지 않으면 하한값을 높인다.

결과는 전수 조사 평가기(exhaustive evaluator)로부터 얻은 증명된 하한값이 탐색에 의해 발견된 명시적 논리적 오류(상한값)의 가중치와 일치할 때만 **인증(certified)**된다. 회로의 경우, 이러한 오류들은 Stim 시뮬레이터에서 재현함으로써 검증된다.

주요 기여

1. 대규모에서의 정확한 계산: 이 방법은 최대 31,200 큐비트(Google의 모듈형 쌍곡선 코드) 및 최대 $8 \times 10^5$ 결함 메커니즘($\text{Cornucopia}$ 코드)을 가진 메모리 회로의 거리를 인증하며, 이는 기존의 정확한 솔버들이 도달하지 못했던 규모이다.
2. 벤치마크 우월성: 두 가지 종합적인 벤치마크(74개 사례 및 126개 독립 사례)에서, 이 방법은 다른 모든 테스트된 정확한 솔버(정수 계획법, MaxSAT, dist-m4ri 포함)를 합친 것보다 더 많은 사례를 인증했다.
3. 출판 문헌 감사: 저자들은 최근 26개의 논문(2023–2026)을 감사했다. 그들은 보고된 모든 정확한 코드 거리는 확인했으나, 10개의 논문에서 과대평가된 회로 또는 코드 거리를 발견했다. 최대 불일치는 8 이상이었으며, 가정된 거리가 인증된 값보다 현저히 높은 사례가 여러 건 있었다.
4. 설계 및 아키텍처 통찰:
   • 스케줄 최적화: IBM의 이중 바이크로 코드를 대상으로 8,496개의 균일한 깊이-7 스케줄을 평가했다. 표준 스케줄은 오직 하나의 코드에 대해서만 최적임을 발견했다. 다른 코드들의 경우, 최적화된 스케럴을 통해 회로 거리를 높일 수 있다(예: gross 코드의 경우 10에서 11로, two-gross 코드의 경우 16에서 18로).
   • 칩 수율: 이 방법은 "죽은(dead)" 체크 큐비트가 있는 칩의 거리를 인증한다. 저자들은 결함이 있는 칩을 유지하면서도 거리가 10 이상임을 인증함으로써, 99.98%의 접합 수율(junction yield)에서 사용 가능한 칩의 예상 수율을 완벽한 칩 기준인 53%에서 **94%**까지 높일 수 있음을 보여준다.
   • 논리적 측정: 병합된 코드를 사용한 논리적 측정을 위한 거리를 인증하며, 게이지 큐비트(gauge qubits)의 고정 여부에 따라 거리가 달라짐을 밝혀냈다. 고정하지 않을 경우 거리가 크게 떨어질 수 있는 반면(예: 2까지), 고정하면 거리가 보존된다.

결과

• IBM Two-Gross 코드: 이 논문은 IBM의 two-gross 메모리 회로에 대해 표준 스케줄의 회로 거리가 16임을 인증하며, 이는 아키텍처 연구에서 사용된 가정치인 18과 상충된다. 이는 논리적 오류율의 예측 지수를 1 감소시킨다. 최적화된 스케줄은 18에 도달할 수 있지만, 사이클당 추가적인 타임스텝이 필요하다.
• Google의 모듈형 쌍곡선 코드: 이 방법은 최대 31,200 큐비트에 달하는 코드의 거리를 인증하여 이전에 열려 있던 구간을 해결한다.
• Cornucopia 코드: 가장 큰 인증된 회로 사례는 $8 \times 10^5$ 결함 메커니즘을 가진다. 인증된 거리는 이전의 외삽법에서 가정된 $p^9$이 아니라, 논리적 오류율의 선도 차수가 $p^8$임을 의미한다.
• 성능: 이 방법은 단일 스레드에서 10초 이내에 거리 25까지의 표면 코드 메모리 회로를 해결하며, 이는 거리 15를 넘어서면 실패하는 다른 범용 정확 솔버들을 능가한다.

의의

본 논문은 인증된 정확한 거리가 코드나 회로의 거리를 단순한 추정치에서 **검증된 양(verified quantity)**으로 변환한다고 주장한다. 이는 코드 비교, 자원 추정, 아키텍처 선택에서 발생하는 핵심적인 오류 원인을 제거한다.

• 신뢰성: 오류 억제 능력의 과대평가를 방지하여, 자원이 부족하게 공급된 양자 컴퓨터가 구축되는 것을 막는다.
• 설계 가이드: 모든 후보 스케줄을 평가할 수 있게 하여, 회로 거리를 최대화하는 스케줄을 선택할 수 있도록 한다.
• 하드웨어 생존력: 결함이 있는 칩도 높은 거리를 유지할 수 있음을 인증함으로써, 양자 하드웨어 제조에 대한 더 현실적인 수율 추정을 지원한다.
• 프로토콜 특이성: 거리가 프로토콜에 따라 달라짐(예: 논리적 측정 시 게이지 큐비트 고정 여부)을 명확히 하여, 일반적인 가정이 아닌 특정 운영 맥락에 대한 정밀한 경계를 제공한다.

저자들은 일부 문제(넓고 큰 거리)가 여전히 비용이 많이 들지만, 축약, 완화 및 다양한 정확한 평가기의 조합을 통해 커뮤니티가 현재 하드웨어에 제안된 회로들에 대해 휴리스틱 상한을 넘어설 수 있게 한다고 강조한다.