Evolutionary Discovery of Bivariate Bicycle Codes with LLM-Guided Search

이 논문은 파이썬 프로그램을 변이시키고 다단계 파이프라인을 통해 후보들을 엄격하게 검증함으로써, 분해 불가능한 코드와 고거리 변형을 포함하여 465개의 서로 다른 코드를 산출하며 새로운 고성능 이변수-자전거 양자 LDPC 코드를 성공적으로 발견하는 LLM 유도 진화 워크플로우를 제시한다.

핵심

당신이 완벽한 디지털 금고용 자물쇠를 만들려고 한다고 상상해 보십시오. 양자 컴퓨팅의 세계에서 이 "자물쇠"는 **양자 오류 정정 코드(quantum error-correcting code)**라고 불립니다. 이 코드의 역할은 취약한 양자 정보를 노이즈와 오류로부터 보호하는 것입니다. 자물쇠가 더 좋을수록, 더 많은 데이터를 저장할 수 있고(높은 "율(rate)"), 파손되기 전까지 더 많은 손상을 견뎌낼 수 있습니다(높은 "거리(distance)").

오랫동안 과학자들은 이러한 자물록, 특히 이변량 바이시클(Bivariate Bicycle, BB) 코드라고 불리는 유형의 최적의 설계를 찾기 위해 노력해 왔습니다. 이들은 복잡한 수학적 청사진과 같습니다. 문제는 가능한 청식의 수가 너무 방대하여, 마치 지구상의 모든 해변에서 특정 모래알 하나를 찾는 것과 같으며, 특정 청식의 작동 여부를 확인하는 작업이 매우 느리고 어렵다는 점입니다.

이 논문은 **인공지능(구체적으로 대규모 언어 모델, LLM)**을 진화적 가이드로 사용하여 이러한 청식을 찾아내는 새로운 방법을 설명합니다.

이 발견의 과정은 다음과 같이 간단한 개념들로 나누어 설명할 수 있습니다.

1. "진화적" 검색 엔진

인간이 완벽한 청식을 추측하는 대신, 연구진은 자연 진화를 모방한 시스템을 구축했습니다.

• "유기체": 단일 코드를 진화시키는 대신, 코드를 생성하는 파이썬 컴퓨터 프로그램(레시피)을 진화시켰습니다.
• "돌연변이": AI(LLM)는 현재 가장 좋은 레시피를 살펴보고 "이 숫자를 바꿔라" 또는 "새로운 단계를 추가하라"와 같이 작은 변화를 제안합니다.
• "적자생존": 시스템은 수천 개의 새로운 레시피를 생성합니다. 이를 빠르게 테스트하여 유효한 코드를 생성하는지 확인합니다. 가장 좋은 것들은 다시 돌연변이를 일으키기 위해 살아남고, 나쁜 것들은 버려집니다.

다섯 번의 "캠페인"(검색 라운드) 동안, 이 AI 기반 시스템은 약 1,650세대를 실행하며 약 200,000개의 후보 코드를 스크리닝했습니다. 전체 과정에는 약 400달러의 컴퓨터 비용과 약 140시간이 소요되었습니다.

2. "함정"과 "심판"

탐색 초기 단계에서 AI는 영리한 함정에 빠졌습니다. AI는 엄청난 양의 데이터 저장 능력(높은 "율")을 가진 레시피를 찾아냈고, 이는 매우 매력적으로 보였습니다. 하지만 이 코드들은 실제로는 오류를 수정하는 능력이 전혀 없었기 때문에(거리 = 2) 쓸모가 없었습니다. 이는 마치 종이 클립으로 열 수 있는 금고 문을 발견한 것과 같습니다. 물건은 많이 담을 수 있지만, 보안은 전혀 되지 않는 것입니다.

연구진은 초기 "거리 측정 도구"(BP-OSD라고 불리는 표준 도구)가 그들에게 거짓말을 하고 있다는 사실을 깨달았습니다. 이 도구는 코드의 강도를 때때로 12배까지 과대평가하고 있었습니다.

이를 해결하기 위해, 그들은 과정에 엄격한 **심판(MILP)**을 추가했습니다.

• 심판의 역할: 이 심판은 코드의 거리를 100% 확실하게 확인하는 강력한 수학적 솔버(solver)입니다.
• 결과: 심판은 "함정"을 즉시 잡아냈습니다. 또한 AI가 강력하다고 생각했던 많은 코드가 실제로는 약하다는 것을 드러냈습니다. 이는 AI가 "가짜" 고성능 코드들을 찾는 것을 멈추고 진정으로 강력한 코드들을 찾도록 강제했습니다.

3. 발견들

과정을 개선한 후, 시스템은 465개의 뚜렷하고 고품질인 코드를 찾아냈습니다. 주요 내용은 다음과 같습니다.

• "골드 스탠다드" 매치: 그들은 기존의 최고 수준 코드(Gross Code)와 성능은 동일하지만 더 복잡한 구조를 사용하는 새로운 유형의 코드("섭동 이변량 바이시클(Perturbed Bivariate Bicycle)")를 찾아냈습니다. 이는 마치 시장에서 가장 좋은 자동차와 동일한 연비를 내면서도 다른 종류의 연료를 사용하는 새로운 엔진 설계를 찾아낸 것과 같습니다.
• 더 많은 데이터, 동일한 보호: 그들은 적절한 수준의 보호를 유지하면서도 이전 기록보다 더 많은 데이터(최대 54 큐비트)를 저장할 수 있는 코드들을 찾아냈습니다.
• "분해 가능한" 발견: 시스템은 마치 초고급 자물쇠처럼 보이는 코드를 찾아냈습니다. 그러나 심판의 그래프 분석 결과, 그것은 사실 두 개의 평범한 자물쇠를 붙여 놓은 것에 불과했습니다. 그것은 새로운 발명이 아니라, 기존의 두 개가 나란히 놓여 있는 것이었습니다. 이는 시스템이 "가짜" 복잡성을 식별할 수 있는 능력을 보여주었습니다.

4. "율(Rate) 대 거리(Distance)"의 트레이드오프

연구진은 모든 코드의 지형을 매핑하여 이 자물쇠들에 적용되는 일관된 규칙, 마치 물리 법칙과 같은 것을 발견했습니다.

• 포락선(The Envelope): 일반적으로 엄청난 양의 데이터를 저장하면서 동시에 극도로 강력한 자물쇠를 가질 수는 없습니다.
• 곡선: 더 많은 데이터(높은 율)를 저장하고 싶다면, 자물쇠는 부서지기 쉬워집니다(낮은 거리). 반대로 매우 강력한 자물쇠를 원한다면, 더 적은 데이터를 저장해야 합니다.
• 예외: 그들은 이 곡선의 한계를 밀어붙이는 코드들(예: 50 단위의 데이터와 거리 8을 가진 코드)을 찾아냈지만, 여전히 이 근본적인 트레이드오프의 "포락선"을 깰 수는 없었습니다.

5. 이것이 중요한 이유

이 논문은 AI를 사용하여 컴퓨터 프로그램을 진화시키는 것이 새로운 양자 코드를 발견하기 위한 실용적이고 저비용의 도구라는 결론을 내립니다.

• AI는 인간과 전통적인 수학적 탐색이 놓쳤던 코드들을 찾아냈습니다.
• 표준 테스트 도구가 고성능 코드에 대해 얼마나 위험할 정도로 부정확할 수 있는지 입증했으며, 엄격한 "심판(MILP)"의 필요성을 보여주었습니다.
• AI가 "함정"을 피하고, 서로 다른 크기의 양자 컴퓨터에 걸쳐 일반화될 수 있는 복잡한 대수적 패턴을 발견할 수 있음을 증명했습니다.

요약하자면, 연구진은 AI를 사용하여 "코드 생성기"를 진화시켰고, AI에게 가짜 결과를 무시하도록 가르쳤으며, 결과적으로 우리가 이전에 가졌던 것보다 더 강력하거나, 더 효율적이거나, 혹은 단순히 다른 형태의 새로운 양자 자물쇠 가족을 성공적으로 발견했습니다.

기술 요약

기술 요약: LLM 유도 탐색을 통한 이변량 바이시클ل 코드의 진화적 발견

문제 정의

양자 저밀도 패리티 검사(qLDPC) 코드, 특히 이변량 바이시클(Bivariate Bicycle, BB) 코드의 발견은 유리한 속도-거리-임계값(rate–distance–threshold) 트레이드오프를 가진 코드를 찾기 위해 방대한 조합 설계 공간을 탐색해야 하는 과제를 안고 있습니다. BB 코드는 실용적인 블록 길이($n \lesssim 1000$)에서 높은 성능을 보이는 코드의 지형이 여전히 미개척 상태인 가운데, 무게-6 안정기(weight-6 stabilizers)와 상수 깊이 신드롬 추출 기능을 제공하여 근미래 하드웨어에 적합합니다. 기존의 체계적 열거 방식은 특정 다항식 형태나 작은 블록 길이에 국한되는 경우가 많으며, 탐색 공간은 연속적 최적화에 적합한 기울기(gradient) 구조가 부족합니다. 또한, 후보 코드의 파라미터(특히 최소 거리 $d$)를 신뢰성 있게 인증하는 것은 계산적으로 매우 어렵습니다. 표준 휴리스틱 방법인 BP-OSD(Belief Propagation with Ordered Statistics Decoding)는 고율(high-rate) 코드에서 거리를 체계적으로 과대평가하는 것으로 나타났으며, 이는 진화적 탐색에서 신뢰할 수 없는 피트니스 신호를 초래합니다.

방법론

저자들은 양자 코드를 발견하고 검증하기 위해 설계된 LLM 유도 진화 워크플로우를 소개합니다. 이 시스템은 개별 코드 파라미터를 진화시키는 대신, 임의의 격자 차원에 대한 후보 다항식 쌍(또는 비-CSS 코드를 위한 4-튜플)을 생성하는 파이썬 프로그램인 **생성기 안사츠(generator ansätze)**를 진화시킵니다.

진화 프레임워크

• 알고리즘: 시스템은 MAP-Elites 알고리즘의 구현체인 OpenEvolve를 사용하여 LLM이 코드 생성기를 변이시키도록 유도합니다.
• 변이 전략: LLM은 현재 가장 높은 피트니스를 가진 안사츠, 도메인 지식, 그리고 평가 피드백을 전달받아, 전체 재작성이 아닌 타겟팅된 코드 디프(diff)(예: 지수 조정, 제어 흐로(control-flow) 구조 재구성)를 제안합니다.
• 개체군: 탐색은 다양성을 유지하기 위해 주기적인 이동(migration)을 수행하는 여러 "섬(islands)"을 통해 분산되어 진행됩니다. 아카이브는 유효한 코드를 생성하는 격자의 수와 고품질 코드의 총 개수와 같은 행동 차원을 기준으로 안사츠를 인덱싱합니다.

단계별 검증 파이프라인

휴리스틱 거리 추정의 불확실성을 완화하기 위해, 저자들은 다단계 캐스케이드(cascade)를 채택합니다.

1. 1단계 (스크리닝): 작은 격자에서 $\text{GF}(2)$ 랭크를 통해 인코딩 차원 $k$를 계산하여 빠르게 평가합니다. 유효한 코드를 생성하지 못하는 안사츠는 폐기됩니다.
2. 2단계 (휴리스틱 추정): 생존한 안사츠는 더 큰 격자에서 다양한 디코더 구성(OSD0, OSD-CS10)을 사용하는 BP-OSD를 통해 거리 $d$를 추정합니다.
3. 3단계 (정밀 검증): 상위 후보(및 후기 캠페인에서의 인 루프(in-loop) 과정)에 대해, **혼합 정수 선형 계획법(MILP)**을 사용하여 정확한 거리를 계산하거나 엄격한 상한을 구합니다. 이 단계는 BP-OSD에서 관찰된 체계적인 과대평가를 교정하는 데 결정적입니다.
4. 사후 캠페인 분석: 순열 동치(permutation-equivalent) 코드를 식별하기 위한 BLISS 기반 태너 그래프 중복 제거, 직접 합(direct sum)을 감지하기 위한 분해 가능성 분석, 그리고 비-CSS 코드를 위한 로컬 클리포드(Local-Clifford, LC) 동치 체크를 포함합니다.

코드 패밀리

• CSS BB 코드: $\mathbb{F}_2[x,y]/(x^\ell-1, y^m-1)$ 상의 두 삼항 다항식 $A, B$로 정의됩니다.
• 섭동된 BB (PBB) 코드: 혼합 안정기를 생성하기 위해 섭동 다항식 $C, D$를 도입하는 비-CSS 안사츠로, 비-CSS 구조를 허용합니다.

주요 기여

1. 465개의 뚜렷한 코드 발견

5회의 진화 캠페인에 걸쳐 시스템은 $n \le 360$에서 465개의 뚜렷한 코드를 발견했습니다:

• 97개의 CSS 코드: 97개의 서로 다른 대표 코드(재발견을 포함한 99개의 동치 클래스)를 포함합니다. 주목할 만한 결과는 다음과 같습니다:
  • [[288, 16, 12]] 코드: $d=12$(정확한 값)와 모든 시프트(shift) $\le 3$을 갖는 비분해(indecomposable) CSS 코드입니다.
  • 고중량 코드: 새로운 $(k, d)$ 조합을 달 achieving하는 무게-8 코드, 예: [[288, 50, 8]] ($k=50, d=8$).
  • 알려진 고성능 코드의 회복(예: "gross code" [[144, 12, 12]]) 및 새로운 유한 길이 대표 코드 식별.
• 368개의 비-CSS PBB 코드: 혼합 안정기를 사용하는 코드입니다. 탐색을 통해 Gross 코드의 FOM(Figure of Merit)과 일치하는 [[144, 12, 12]] PBB 코드를 찾았으며, 신뢰할 수 있는 FOM 상한이 19.2인 [[360, 12, $\le$24]] 코드를 발견했습니다.

2. 검증 방법론의 발전

• BP-OSD 과대평가: 본 연구는 BP-OSD가 고율 코드($k/n > 0.1$)에서 거리를 체계적으로 과대평가하며, 오차가 최대 12배에 달할 수 있음을 정량화합니다. 예를 들어, [[360, 40, 2]] 코드는 BP-OSD에 의해 $d \le 24$로 추정되었으나, MILP는 $d=2$임을 확인했습니다.
• 달성 가능한 신드롬 샘플링 (Achievable-Syndrome Sampling): 비-CSS 코드의 경우, 달성 가능한 논리 코셋(logical coset)이 엄격한 부분 공간을 형성하기 때문에 표준 무작위 신드롬 샘플링은 실패합니다. 저자들은 달성 가능한 부분 공간에서만 샘격하는 방법을 도입하여 BP-OSD 기능을 복구했습니다.
• MILP 그라운드 트루스 (Ground Truth): 검증 표준으로서의 MILP 사용은 많은 고-$k$ 후보들이 실제로는 낮은 거리이거나 분해 가능한 코드임을 드러냈습니다 (예: [[288, 24, 12]] 코드는 두 개의 gross 코드가 결합된 직접 합으로 식별됨).

3. BB 지형의 구조적 특성

저자들은 서로 다른 속도-거리 프로파일을 가진 네 가지 대수적 패밀리를 식출합니다:

• 단변량/HGP: 순환 코드의 하이퍼그래프 곱(hypergraph product)과 동치인 코드들입니다. 이들은 가장 높은 인코딩 차원($k \propto \ell$)을 달성하지만, 거리 상한 $d \le 4$의 한계를 겪습니다.
• x/y-swap: 다항식에 혼합 변수를 사용하는 코드로, $d \ge 12$를 달성하지만 비분해 코드의 경우 $k \le 16$으로 제한됩니다.
• 혼합 단항식/고중량 (Mixed-Monomial/Higher-Weight): 새로운 $(k, d)$ 지점(예: $d=8$에서 $k=50$)에 접근할 수 있는 4~6개 항의 다항식을 가진 코드들이지만, 전반적인 속도-거리 포락선(envelope)을 벗어나지는 못합니다.
• 비-CSS PBB: $n=144$에서의 최적 CSS 코드의 FOM과 일치하지만 이를 초과하지는 않는 코드들입니다.

4. 경험적 속도-거리 트레이드오프

탐색은 일관된 경험적 트레이드오프를 보여줍니다: 높은 인코딩 속도는 일반적으로 낮은 거리를 동반합니다.

• $d=12$를 갖는 비분해 무게-6 코드는 $k \le 16$으로 제한됩니다.
• $k > 24$를 갖는 무게-6 코드는 보편적으로 $d \le 4$를 가집니다.
• 더 높은 중량의 코드(무게-8)는 중간 정도의 $d$에서 더 높은 $k$ (예: $d=8$에서 $k=50$)에 접근할 수 있지만, 관찰된 포락선을 깨지는 못합니다.

결과 및 의의

핵심 결과

• LLM 효능: LLM 유도 진화는 격자 차원 전반에 걸쳐 일반화될 수 있는 대수적 패턴(예: 단변량 구조, x/y-swap)을 성공적으로 발견하였으며, 이는 무작위 탐색 및 표준 유전 알고리즘보다 $d \ge 6$인 고-FOM 코드를 찾는 데 있어 우수한 성능을 보였습니다.
• 검증의 필요성: 본 연구는 고율 코드 발견에 있어 휴리스틱 거리 추정이 불충분함을 입증합니다. "A = B 거리 함정"(A=B일 때 $d=2$가 되는 현상)은 $1.5 \times 10^6$번의 시도에도 불구하고 BP-OSD에 의해 감지되지 않았으나, MILP 파이프라인에 의해 즉각적으로 식별되었습니다.
• 하드웨어 관련성: 발견된 코드들, 예를 들어 [[288, 16, 12]]는 gross 코드보다 최대 1.7배 높은 논리 큐비트 수를 제공하면서도 표면 코드(surface code)와 유사한 의사 임계값(pseudo-threshold)을 유지합니다. 비-CSS PBB 코드는 특정 노이즈 모델(X-only) 하에서 개선된 오류 억제 잠재력을 보여주지만, 표준 디코더를 사용하는 탈분극 노이즈(depolarizing noise) 하에서는 이 장점이 감소합니다.

의의

본 논문은 LLM 유도 프로그램 진화가 엄격한 다단계 독립 검증(특히 MILP)과 결-합될 때, 구조화된 양자 코드 발견을 위한 실용적이고 비용 효율적인 도구로 기능할 수 있음을 주장합니다. 약 $400의 총 계산 비용과 140시간의 시간은 이 접근 방식의 실현 가능성을 입증합니다.

이 연구는 고율 BB 코드 주장에 대한 새로운 검증 표준을 확립하며, 휴리스틱 추정과 정확한 거리 사이의 결정적인 간극을 강조합니다. 이는 양자 코드의 조합 공간을 탐색하기 위한 재사용 가능한 프레임워크를 제공하며, 속도-거리 포락선이 견고하지만 구조화된 탐색을 통해 그 안에서 새로운 고성능 대표들을 찾아낼 수 있음을 보여줍니다. 저자들은 이 포락선을 벗어나기 위해서는 이변량 바이시클 패밀리를 넘어 더 복잡한 대수적 구조로 나아가야 할 것이라고 언급합니다.