An iterative Ising decoder for quantum error correction codes

본 논문은 교대적인 서브 해밀토니안(sub-Hamiltonians)과 베이지안 사전 확률(Bayesian priors)을 통해 양자 오류 정정에서의 고차 $X$-$Z$ 오류 상관관계를 근사함으로써, 상호작용 복잡도를 줄이고, 큰 코드 거리(code distances)에 대한 솔버의 수렴성을 개선하며, 경쟁력 있는 오류 임계값을 유지하면서도 하드웨어 임베딩 오버헤드를 크게 낮추는 반복적 저차 디코딩(Iterative Low-Order Decoding, ILOD) 알고리즘을 제안한다.

핵심

당신은 큐비트(qubit)로 만들어진 거대하고 복잡한 퍼즐을 고치려고 노력 중이라고 상상해 보세요. 때때로 퍼즐 조각들이 "노이즈(noise)"에 의해 뒤집히거나 뒤섞이기도 합니다(오류). 당신의 임무는 전체 그림을 망가뜨리지 않으면서 정확히 어떤 조각들이 고장 났는지 파악하는 것입니다. 이것을 **양자 오류 정정(Quantum Error Correction)**이라고 부릅니다.

이 문제를 해결하기 위해 과학자들은 "디코더(decoder)"를 사용합니다. 디코더를 몇 가지 단서(이를 "신드롬(syndrome)"이라 부름)를 바탕으로 범죄 현장을 재구성하려는 탐정이라고 생각해보세요.

문제: 너무 복잡한 범죄 현장

과거에 연구자들은 이 퍼즐을 풀기 위해 **이징 프레임워크(Ising framework)**라고 불리는 방법을 사용했습니다. 이 프레임워크를 모든 퍼즐 조각들을 연결하는 거대한, 엉킨 실타래라고 상상해 보세요.

• 좋은 점: 이 웹(web)은 매우 정확합니다. 만약 한 조각이 뒤집히면, 그것이 다른 조각이 특정 방식으로 뒤집히는 것과 연관될 수 있다는 점(마치 도미노 효과처럼)을 이해합니다.
• 나쁜 점: 이러한 복잡한 관계를 모두 포착하기 위해, 이 웹은 매우 지저분해집니다. 한 지점에 최대 10개의 실이 묶여 있는 "매듭(knot)"이 생깁니다.
• 결과: 10개의 실로 된 매듭을 푸는 것은 컴퓨터에게 매우 어렵습니다. 시간이 오래 걸리고, 종종 "막다른 길"(컴퓨터가 해결책을 찾지 못하는 곳)에 빠지기도 하며, 그 매듭을 표현하기 위해 엄청난 양의 추가 메모리(보조 스핀)가 필요합니다. 이는 마치 오븐 장갑을 끼고 루빅스 큐브를 맞추는 것과 같습니다. 큐브가 복잡해질수록 손을 움직이기가 더 힘들어지는 것과 마찬가지입니다.

해결책: "ILOD" 탐정

이 논문의 저자들은 **ILOD(Iterative Low-Order Decoding, 반복적 저차 디코딩)**라고 불리는 새로운 전략을 제안합니다. 이 방법은 전체 10-실 매듭을 한꺼번에 풀려고 하는 대신, 문제를 두 개의 더 단순하고 분리된 작업으로 나누어 차례대로, 그리고 번갈아 가며 해결합니다.

작동 방식은 다음과 같은 간단한 비유를 통해 설명할 수 있습니다.

"두 팀" 전략
퍼즐에는 두 가지 유형의 오류가 있다고 가정해 봅시다: X-오류(이를 "빨간 실수"라고 부릅시다)와 Z-오류(이를 "파란 실수"라고 부릅시다). 때때로 "노란 실수"가 발생하는데, 이는 빨간 실수와 파란 실수가 동시에 발생하는 것입니다.

1. 기존 방식 (결합 정식화, Joint Formulation): 빨간 실수와 파란 실수를 동시에 해결하려고 시도합니다. 이 둘은 서로 연결되어 있기 때문에, 빨간색과 파란색이 복잡하게 상호작용하는 거대하고 복잡한 규칙 책을 고려해야 합니다. 이것이 "10-실 매듭"을 만듭니다.
2. 새로운 방식 (ILOD):
   • 1단계: 빨간 팀에게 오직 빨간 실수만 존재한다고 가정하고 퍼즐을 풀라고 요청합니다. 그들은 빨간 실수가 어디에 있는지 최선의 추측을 내놓습니다.
   • 2단계: 빨간 팀의 추측을 가져와서 파란 팀에게 전달합니다: "빨간 팀이 찾은 것에 근거하여, 이곳에서 파란 실수가 발생할 가능성이 얼마나 되는지 알려줄게요." 이는 파란 팀을 위한 규칙을 업데이트합니다.
   • 3단계: 파란 팀은 이 업데이트된 규칙을 가지고 퍼즐을 풉니다.
   • 4단계: 파란 팀의 새로운 추측을 가져와서 다시 빨간 팀을 위한 규칙을 업데이트합니다.
   • 반복: 두 팀이 해결책에 합의할 때까지 서로 쪽지를 주고받으며 이 과정을 반복합니다.

이것이 왜 중요한가

문제를 나눔으로써 저자들은 세 가지 주요 성과를 달성했습니다.

1. 더 단순한 매듭: 새로운 방식은 8개나 10개의 실로 된 매듭을 다루는 대신, 4개 또는 5개의 실로 된 매듭만을 다룹니다. 컴퓨터가 10-실 매듭을 푸는 것보다 4-실 매듭을 푸는 것이 훨씬 쉽습니다.
2. 더 빠른 속도: 매듭이 더 단순하기 때문에 컴퓨터가 퍼즐을 훨씬 빠르게 풉니다. 논문은 퍼즐이 커질수록(더 큰 "코드 거리") 기존 방식은 기하급적으로 느려지는 반면, 새로운 방식은 상대적으로 빠른 속도를 유지함을 보여줍니다.
3. 더 적은 메모리: 복잡한 매듭을 풀기 위해 컴퓨터는 보통 매듭을 유지하기 위한 "가짜" 추가 조각(보조 스핀)을 구축해야 합니다. 새로운 방식은 이 가짜 조각이 약 2.5배 적게 필요합니다. 이는 더 작은, 더 저렴한 하드웨어에서도 실행될 수 있음을 의미합니다.

결과

저자들은 이 방법을 **토릭 코드(Toric Code)**와 **컬러 코드(Color Code)**라는 두 가지 유명한 양자 퍼즐에 테스트했습니다.

• 정확도: 새로운 방식은 기존의 복잡한 방식만큼 거의 정확합니다. 어떤 경우에는 통계적으로 동일하며, 어떤 경우에는 아주 약간 덜 정확할 수도 있지만, 그 대가로 얻는 속도는 충분히 가치가 있습니다.
• 수렴성: 가장 큰 규모의 퍼즐에서 기존 방식은 종종 포기하고 해결책을 찾지 못했습니다. 하지만 새로운 방식은 계속 진행하여 답을 찾아냈습니다.
• 하드웨어: 더 적은 자원을 사용하기 때문에, 이 방식은 현재 제작 중인 이러한 유형의 퍼즐을 해결하기 위해 설계된 전용 하드웨어인 "이징 머신(Ising machines)"에서 실행될 준비가 훨씬 더 잘 되어 있습니다.

요 요약

이 논문은 양자 컴퓨터를 고치는 더 똑똑한 방법을 소개합니다. 거대하고 엉킨 덩어리를 한꺼번에 해결하는 대신, 문제를 두 개의 더 작고 관리 가능한 대화로 나누어 번갈아 가며 수행합니다. 이를 통해 해결 속도를 높이고, 컴퓨터 메모리를 적게 사용하며, 이전에는 깨뜨리는 것이 불가능했던 더 큰 퍼즐을 해결할 수 있게 해줍니다.

기술 요약

기술 요약: 양자 오류 정정 코드를 위한 반복적 이싱 디코더(Iterative Ising Decoder)

문제 정의
본 논문은 데폴러라이징 노이즈(depolarizing noise) 환경 하에서 토릭 코드(Toric code)와 6.6.6 컬러 코드(Color code)를 포함한 양자 오류 정정(QEC) 코드를 디코딩하는 과제를 다룬다. 이싱 프레임워크는 문제를 고전 해밀토니안의 바닥 상태 최적화 문제로 매핑함으로써 강력한 디코딩 방법을 제공하지만, 데폴러라이징 노이즈 하에서는 심각한 확장성 문제에 직면한다. 비트 플립(bit-flip) 노이즈가 2-body 상호작용을 생성하는 것과 달리, 데폴러라이징 노이즈는 $X$-$Z$ 오류 상관관계(Y 오류를 통한)를 도입하며, 이는 해밀토니안 내의 교차 항(cross-terms)으로 나타난다.
현상론적 데폴러라이징 노이즈(phenomenological depolarizing noise) 하에서 이러한 상관관계는 높은 차수의 상호작용 항을 초래한다. 구체적으로 토릭 코드의 경우 최대 8-body, 컬러 코드의 경우 10-body 상호작용이 발생한다. 이러한 고차 항은 휴리스틱 솔버가 직면한 에너지 경관(energy landscape)을 험난하게 만들어 수렴을 저해하고 실행 시간을 팽창시키며, 이를 네이티브 2-body 이싱 하드웨어에 임베딩할 때 수많은 보조 스핀(auxiliary spins)을 요구하는 심각한 오버헤드를 발생시킨다.

방법론: 반복적 저차 디코딩 (Iterative Low-Order Decoding, ILOD)
이러한 병목 현상을 완화하기 위해, 저자들은 ILOD 알고리즘을 제안한다. ILOD는 고차 교차 항을 포함하는 단일 결합 해밀토니안을 최적화하는 대신, 문제를 교대로 수행되는 $X$-타입 및 $Z$-타입 서브 해밀토니안으로 분해한다.

1. 분해 및 교대 수행: 알고리즘은 가우스-사이델(Gauss–Seidel) 직렬 스케줄에 따라 $X$-타입과 $Z$-타입 서브 문제를 해결한다. 이를 통해 최대 상호작용 차수를 토릭 코드의 경우 8/10-body에서 4/5-body로 낮춘다.
2. 베이지안 재가중치 부여 (Bayesian Reweighting): 누락된 $X$-$Z$ 상관관계를 근사하기 위해, ILOD는 베이지안 사전 확률 메커니즘을 채택한다. 한 유형(예: $X$)을 해결한 후, 추론된 오류 구성은 반대 유형($Z$)의 결합 강도를 재가중하는 데 사용된다. 구체적으로, 특정 큐비트에 $X$-성분 오류가 있는 것으로 추론되면, 해당 큐비트가 $Z$-성분을 가질 확률이 업데이트되며(예: $X$ 또는 $Y$가 존재할 경우 $1/2$로 업데이트), 니시모리 조건(Nishimori condition)을 통해 결합 강도 $J$가 조정된다.
3. 솔버 불완전성에 대한 강건성: 실제 솔버가 정확한 바닥 상태를 반환하지 못할 수 있음을 인지하여, 저자들은 "소프트 결정(soft-decision)" 정식화를 도입한다. 하드 결정 대신 솔버의 신뢰성을 반영하는 조건부 확률($a$와 $b$)을 사용하여 결합을 업데이트함으로써, 잘못된 로컬 추정치가 후속 최적화 단계를 지나치게 제약하는 것을 방지한다.
4. 현상론적 노이즈로의 확장: 3D 시공간 검출기 그래프가 필요한 현상론적 노이즈에 적용하기 위해, 측정 오류 결합은 고정된 상태로 유지하면서 시공간 차원 모두에 걸쳐 교대 최적화 및 베이지안 업데이트를 적용한다.

주요 기여

• 알고리즘적 혁신: 동적 결합 업데이트를 통해 교차 유형 간의 상관관계를 포착하면서, 정확한 결합 최적화를 반복적인 저차 근사로 대체하는 ILOD를 제안한다.
• 복잡도 감소: 상호작용 항의 최대 바디 카운트(body count)를 절반으로 줄인다. 이는 에너지 경관을 크게 완만하게 만들어 메타스테이블 상태(metastable states)의 확산을 줄인다.
• 하드웨어 효율성: 상호작용 차수를 낮춤으로써, ILOD는 네이티브 2-body 이싱 하드웨어(예: 코히어런트 이싱 머신, 양자 어닐러)에 임베딩할 때 필요한 보조 스핀 오버헤드를 획기적으로 줄인다.
• 수렴성 회복: 결합 정식화가 적절한 어닐링 예산 내에서 수렴하지 못하는 더 큰 코드 거리에서도 솔버의 수렴을 복구한다.

수치 결과
저자들은 코드 용량(code-capacity) 및 현상론적 데폴러라이징 노이즈 환경 모두에서 ILOD를 결합 이싱 정식화 및 MWPM 변형 모델과 비교 평가하였다.

• 임계값 (정확도):

  • 토릭 코드 (현상론적): ILOD는 **4.73%**의 임계값을 달성하였는데, 이는 결합 정식화의 **4.83%**보다는 약간 낮지만, MWPM(3.80%) 및 상관된 MWPM(Correlated MWPM, 4.65%)보다는 유의미하게 높다.
  • 컬러 코드 (현상론적): ILOD는 **4.41%**를 달성하여, 통계적 불확실성 범위 내에서 결합 정식화의 **4.36%**와 일치하며, 두 방식 모두 MWPM(3.35%)보다 우수한 성능을 보인다.
  • 코드 용량: 유사한 경향이 관찰되었으며, ILOD 임계값은 결합 정식화보다 약간 낮지만 매칭 기반 디코더보다는 우수하다.

• 실행 시간 및 수렴성:

  • 스케일링: 코드 용량 노이즈 하의 토릭 코드에 대한 경험적 실행 시간 비율(ILOD/Joint)은 $(0.81)^d$로 스케일링되어, 코드 거리 $d$가 증가함에 따라 지수적 가속을 나타낸다. 현상론적 노이즈 하에서 실행 시간 스케일링 기저값은 결합 정식화의 $b \approx 3.34$에서 ILOD의 $b \approx 2.70$으로 감소한다.
  • 수렴성: $d=9$인 컬러 코드의 경우, 결합 정식화는 큰 어닐링 예산($2 \times 10^5$ sweeps)에도 불구하고 수렴에 실패한 반면, ILOD는 훨씬 적은 sweep 횟수로 성공적으로 수렴하였다.

• 하드웨어 오버헤드:

  • 로젠버그 이차 형식화(Rosenberg quadratization)를 통해 2-body 항으로 변환한 후, ILOD는 두 코드 모두에서 결합 정식화 대비 총 스핀 수(게이지 + 보조 스핀)를 약 2.5배 감소시킨다.

의의 및 주장
본 논문은 IL-OD가 정확도, 지연 시간, 하드웨어 확장성 사이의 균형을 맞추는 효율적인 이싱 기반 디코딩 프레임워크를 제공한다고 주장한다. 주요 의의는 데폴러라이징 노이즈 하의 고차 QEC 코드를 디코딩하기 위해 네이티브 2-body 이싱 하드웨어를 사용할 수 있게 한다는 점에 있다. 상호작용 차수를 낮춤으로써 ILOD는 디코딩 문제를 다룰 수 있는 수준으로 만들며, 정확한 결합 정식화가 계산적으로 불가능해지는 코드 거리에서도 수렴성을 복구한다. 저자들은 ILOD가 결합 정식화에 비해 임계값 성능에서 미세한 근사 손실을 입을 수 있지만, 이는 솔버 속도와 하드웨어 자원 효율성의 상당한 이득에 의해 상쇄된다고 언급한다. 이 접근법은 높은 스테빌라이저 가중치(stabilizer weight)로 인해 결합 이싱 매핑이 매우 비용이 많이 드는 qLDPC 코드를 포함한 다른 CSS 코드에도 적용 가능하다고 제시된다.