From Random Quantum Codes to Explicit qLDPC Codes via Local Properties

정보 이론의 광활한 풍경 속에서, 데이터의 부패로부터 정보를 보호하려는 탐구는 수학적 코드를 이용한 전투와 같습니다. 노이즈가 있는 채널을 통해 메시지를 보낸다고 상상해 보십시오. 보호 장치가 없다면, 단 하나의 작은 결함만으로도 명확한 지시 사항이 횡설수설하는 헛소리로 변할 수 있습니다. 이를 방기하기 위해 엔지니어들은 추가적인 정보 비트를 더하여, 수신자가 오류를 발견하고 수정할 수 있게 해주는 안전망을 만듭니다. 수십 년 동안, 가장 효과적인 코드들은 마치 완벽한 열쇠를 찾기 위해 카드를 섞어 적절한 것이 나타날 때까지 기다리는 것처럼, 단지 숫자의 무작위 집합으로서만 존재하는 것으로 알려져 있었습니다. 이러한 무작위 코드들은 이론적으로는 이상적이지만, 그것을 사용하는 데 필요한 구체적인 지침을 아무도 작성할 수 없기 때문에 실제로는 쓸모가 없습니다. 오랫동안의 과제는 이러한 완벽한 코드들의 명시적이고 기록된 버전을 찾는 것이었으며, 이 버전들은 실제 기계가 처리할 수 있을 만큼 충분히 효율적이어야 했습니다. 이 어려움은 정보의 저장과 처리가 믿을 수 없을 정도로 취약한 물리 법칙을 따르는 신흥 분야인 양자 컴퓨팅에서 더욱 심화됩니다. 여기서 이상적인 코드는 완벽해야 할 뿐만 아니라 "저밀도(low-density)"여야 합니다. 즉, 데이터를 점검하는 규칙이 단순하고 국소적이어야 하며, 한 번에 몇 개의 정보 조각만을 다루어야 한다는 뜻입니다. 이러한 단순함이 없다면, 코드를 실행하는 데 필요한 하드웨어는 구축하기에 너무 복잡해질 것입니다.

오랫동안 연구자들은 좋은 양자 코드가 존재한다는 것은 증명할 수 있었지만, 그것들을 직접 써 내려가지는 못했습니다. 그들은 보물로 가는 지도는 가지고 있지만, 그곳에 도달할 경로를 제시하지 못하는 상황과 같았습니다. 최근 과학자들이 효율적이면서도 우수한 양자 코드를 명시적으로 구축해 내면서 중대한 돌파구가 마련되었으나, 이 코드들은 여전히 무작위 코드가 가진 강력한 오류 정정 특성의 전체 범위를 갖추지 못했습니다. 페르난도 그라냐 제로니모(Fernando Granha Jerimo), 샤오솬 마(Xiaojuan Ma), 니킬 샤그리타야(Nikhil Shagrithaya)의 새로운 연구는 이 마지막 간극을 메웁니다. 그들은 특정 종류의 오류 정정 작업, 특히 오류가 심각하고 많을 때도 데이터를 복구할 수 있는 능력을 포함하여, 최고의 무작위 코드와 성능이 일치하는 명시적 양자 코드를 구축하는 방법을 개발했습니다. 그들의 성과는 단 하나의 새로운 코드가 아니라, 미래의 양자 컴퓨터에서 구현 가능할 만큼 단순하면서도 매우 효율적인 다양한 유형의 양자 코드를 구축하는 데 사용할 수 있는 일반적인 프레임워크입니다.

연구자들은 먼저 CSS 코드라고 알려진 특정 유형의 양자 코드에서 시작했습니다. 이 코드는 함께 작동하는 두 층의 고전적 수학으로 구성됩니다. 한 층은 한 종류의 양자 교란과 관련된 오류를 처리하고, 다른 한 층은 다른 종류의 오류를 처리합니다. 이 코드를 분석하는 데 있어 어려움은 정보가 물리적 비트로부터 유도된 수학적 추상화인 "논리적(logical)" 공간에 저장되어 있다는 점에 있습니다. 코드가 좋은지 이해하려면 논리적 공간에서 어떻게 행동하는지를 보아야 하지만, 규칙은 물리적 비트에 부과됩니다. 이는 물리적 수준에서는 오류처럼 보이는 패턴이 논리적 세계에서는 무해할 수도 있고, 혹은 그 반대일 수도 있는 복잡한 상황을 만듭니다. 저자들은 물리적 규칙과 논리적 결과 사이의 관계를 하나의 통합된 시스템으로 취급함으로써 이 문제를 바라보는 새로운 방법을 도입했습니다. 그들은 피해야 할 일련의 국소적 제약 조건을 정의했으며, 이 제약 조건들을 피하면 코드가 오류에 대해 견고함을 보장하게 됩니다.

이러한 특성을 가진 코드가 존재함을 증명하기 위해, 팀은 먼저 코드를 무작위로 선택했을 때 거의 확실하게 이러한 제약 조건을 만족한다는 것을 보여주었습니다. 이것은 해당 분야의 표준적인 결과이지만, 실제 기계를 만드는 데는 도움이 되지 않습니다. 그들의 진정한 혁신은 "역무작위화(derandomization)" 과정에 있습니다. 그들은 무작위 코드가 작동한다는 수학적 증명을 찾아내어 특정 명시적 코드를 찾는 단계별 레시피로 바꾸었습니다. 그들은 "이너 가젯(inner gadget)"이라고 부르는 작고 일정한 크기의 구성 요소를 구축함으로써 이를 수행했습니다. 이 가젯은 연구자들이 우려하는 특정 유형의 오류에 대해 견고하도록 세심하게 설계된 작은 양자 코드입니다. 가젯이 작기 때문에, 연구자들은 모든 가능한 옵션을 확인하는 과정을 통해 이론적으로 이를 찾아낼 수 있으며, 이 과정은 계산적으로 실행 가능할 만큼 (비록 지루할지라도) 용이합니다.

이 견고한 이너 가젯을 확보한 후, 그들은 익스팬더 그래프(expander graph)라고 알려진 수학적 구조를 사용하여 이 많은 작은 블록들을 서로 연결했습니다. 익스팬더 그래프는 모든 점이 몇 개의 다른 점들과 연결되어 정보가 전체 시스템에 빠르고 균등하게 퍼지도록 보장하는 네트워크입니다. 이 이너 가젯들을 이 그래프 위에 배치함으로써, 작은 블록들의 국소적 견고함은 전체 코드에 대한 전역적 보장으로 증폭되었습니다. 네트워크를 통해 흐르는 기호의 순서를 제어하는 외부 층은 유효한 메시지 사이의 거리를 유지하는 데 매우 뛰어나다고 알려진 또 다른 유형의 양자 코드로 선택되었습니다. 견고한 이너 블록과 잘 연결된 외부 구조의 결组合은 두 가지의 장점을 모두 물려받은 거대한 코드를 만들어냈습니다.

그 결과는 명시적이고 효율적일 뿐만 아니라, 잠재적 오류 목록을 처리하는 최적의 능력을 갖춘 양자 코드 제품군입니다. 많은 오류 정정 시나리오에서 수신자는 오류를 즉시 정확하게 짚어낼 수는 없더라도, 가능한 후보들의 짧은 목록으로 범위를 좁힐 수 있습니다. 새로운 코드는 이론적으로 가능한 가장 작은 크기의 목록으로 이 작업을 수행할 수 있는데, 이는 이전의 명시적 구축 방식들이 달성하지 못했던 특성입니다. 더욱이, 이 코드들은 "서브스페이스 디자인(subspace designs)"으로 설계되었는데, 이는 오류가 복잡한 방식으로 구조화되어 있을 때도 잘 작동하도록 보장하는 수학적 특성입니다. 이는 오류가 상관관계가 있고 예측하기 어려운 양자 컴퓨팅 환경에서 특히 가치가 있습니다. 연구자들은 또한 수신자가 메시지의 각 부분에 대한 가능한 값들의 목록을 받고 그중 가장 적합한 하나의 유효한 메시지를 찾아야 하는 관련 작업인 "리스트 디코딩(list recovery)"에 대해서도 이 방법이 작동함을 입증했습니다.

이 연구의 의의는 단순히 더 나은 코드를 찾는 것을 넘어섭니다. 이는 무작위 코드에 대한 이론적 보장을 실용적이고 명시적인 구축으로 전환하는 일반적인 툴킷을 제공합니다. 저자들은 특정 특징을 가진 무-작위 코드가 존재할 확률이 높다면, 그와 동일한 특징을 가진 명시적 코드를 그들의 방법을 통해 구축할 수 있음을 보여주었습니다. 여기에는 상대적 거리가 양자 싱글턴 바운드(quantum Singleton bound)인 약 (1-R)/2에 가깝게 스케일링되는 오류 정정 능력과, 이론적 용량 한계보다 엄격히 낮은 반지름까지 리스트 디코딩을 수행하는 능력이 포함됩니다. 이전의 시도들은 이러한 한계에 도달하려 할 때 사용하기에 너무 복잡하거나 리스트 크기가 지나치게 커지는 코드를 낳았지만, 이 새로운 접근 방식은 리스트 크기를 일정하게 유지하고 복잡성을 관리 가능한 수준으로 유지합니다.

이 구축 방식은 내부 구성 요소들이 작고 고정되어 있다는 사실에 기반합니다. 이는 코드가 더 많은 데이터를 처리하기 위해 커지더라도 복잡성이 폭발적으로 증가하지 않음을 의미합니다. 대신, 코드는 효율적으로 확장되며, 크기에 관계없이 높은 성능과 낮은 복잡성을 유지합니다. 연구자들은 그들의 방법이 정보 전송률(유용한 데이터와 전송되는 총 데이터의 비율)에 대해 원하는 어떤 비율에 대해서도 작동함을 검증했습니다. 그들은 목표하는 어떤 비율에 대해서도, 아주 미미하고 통제 가능한 수준의 효율 손실만을 허용하면서 무작위 코드의 최적 성능에 임의로 가까워질 수 있는 코드를 구축할 수 있음을 보여주었습니다. 이러한 유연성은 서로 다른 작업마다 요구되는 데이터 전송량과 보호 수준 사이의 균형이 다르다는 점에서 실세계 응용 분야에 매우 중요합니다.

양자 오류 정정의 맥락에서, 저밀도 패리티 체크(low-density parity-check) 코드를 사용하는 능력은 필수적입니다. 이들은 데이터를 점검하는 규칙이 한 번에 아주 적은 수의 비트만을 다루는 코드들입니다. 이러한 국소성은 시스템이 불가능할 정도로 복잡한 외부 컨트롤러 없이 스스로 오류를 수정할 수 있는 결함 허용(fault-tolerant) 양자 컴퓨터를 구축할 수 있게 하는 핵심 요소입니다. 이 논문에서 개발된 코드들은 모두 저밀도이며, 이는 미래의 양자 하드웨어의 물리적 제약 조건과 호환됨을 의미합니다. 코드를 명시적이고 저밀도로 설계함으로써, 저자들은 양자 오류 정정의 실질적인 구현을 가로막던 주요 장벽을 제거했습니다.

또한 이 작업은 고전적 코딩 이론과 양자 코딩 이론 사이의 관계를 명확히 합니다. 양자 코드의 물리적 층과 논리적 층을 통합된 방식으로 다루는 프레임워크를 개발함으로써, 연구자들은 고전적 코딩 이론의 통찰력을 양자 영역으로 직접 번역할 수 있었습니다. 이를 통해 그들은 양자 설정에서 오랫동안 해결되지 않았던 문제를 풀기 위해 수십 년간 진행된 고전적 오류 정정의 발전을 활용할 수 있었습니다. 그 결과는 이론적으로 건전할 뿐만 아니라 실질적으로 실행 가능한 코드 세트로, 견고한 양자 통신 및 컴퓨팅 시스템의 발전을 위한 명확한 경로를 제시합니다.

궁극적으로, 이 논문은 "좋은 코드가 존재하는가?"라는 질문에서 "어떻게 그것들을 만드는가?"라는 질문으로의 전환을 의미합니다. 저자들은 무작위 코드의 이상적인 특성이 단지 수학적 호기심이 아니라, 명시적이고 구축 가능한 형태로 실현될 수 있음을 보여줌으로써 구체적인 답을 제시했습니다. 그들의 방법은 다양한 유형의 오류 정정 과제에 적용될 수 있을 만큼 일반적이며, 이는 명시적이고 고성능인 양자 코드의 시대가 진정으로 시작되었음을 시사합니다. 그들이 구축한 코드는 테스트와 구현을 위한 준비가 되어 있으며, 신뢰할 수 있는 양자 정보 전송을 위한 새로운 토대를 제공합니다.