List-Decodable Folded Quantum Hermitian Codes

기술적 요약: 리스트-디코딩 가능한 폴딩 양자 에르미트 코드

문제 제기
대수기하 (AG) 코드에서 유도된 양자 오류 정정 코드는 오랫동안 연구의 대상이 되어 왔으며, 풍부한 자기동형군과 유리한 점근적 매개변수 덕분에 에르미트 곡선이 중요한 역할을 해왔습니다. 고전적인 리스트 디코딩은 싱글턴 한계에 근접하는 폴딩된 리드-솔로몬 코드로 정점에 이르렀을 정도로 크게 발전했지만, 이러한 기법을 양자 환경으로 전환하는 것은 도전 과제를 안고 있습니다. 구체적으로, 베르가마시, 골로위치, 건이 최근에 구성한 폴딩된 양자 리드-솔로몬 코드는 양자 싱글턴 한계를 달성하지만 큰 알파벳 크기를 겪습니다. 이를 완화하기 위해 해당 연구들은 복잡도를 증가시키는 "양자 거리 증폭" 기법을 사용했습니다. 본 논문에서 다루는 핵심 문제는 양자 싱글턴 한계에 근접하면서 더 작은 알파벳 크기를 활용하여 거리 증폭이 불필요해질 수 있도록, 양자 폴딩 코드를 양수 종수 곡선 (특히 에르미트 곡선) 에서 구성할 수 있는지 여부입니다.

방법론
저자들은 고전적인 폴딩된 AG 코드에서 양자 코드를 구성하기 위해 칼더뱅크 - 쇼어 - 스테인 (CSS) 프레임워크를 활용합니다. 방법론은 다음과 같은 단계를 거쳐 진행됩니다.

1. 고전적 폴딩: 저자들은 $\mathbb{F}_{q^2}$ 위의 에르미트 곡선 $H$의 자기동형군을 활용합니다. 단일 순환 궤도에 의존하는 리드 - 솔로몬 코드와 달리, 에르미트 코드는 아핀 유리점을 여러 구조화된 궤도로 분할하는 자기동형 $\sigma_{\delta, \mu}$를 활용합니다. 이러한 궤도를 따라 연속적으로 평가된 값들을 확장체 $\mathbb{F}_{q^m}$ 위의 단일 심볼로 그룹화하여 폴딩된 원점 에르미트 코드 $C^{(\sigma, m)}$를 생성합니다.
2. CSS 구성: 두 개의 폴딩된 고전적 에르미트 코드 $C_1^{(\sigma, m)}$와 $C_2^{(\sigma, m)}$를 선택하여 두 번째 코드의 쌍대코드가 첫 번째 코드에 포함되도록 ($(C_2^{(\sigma, m)})^\perp \subseteq C_1^{(\sigma, m)}$) 합니다. 저자들은 폴딩이 CSS 구성과 교환 가능하게 만드는 조건을 공식화하여 결과적인 양자 코드가 잘 정의되도록 합니다.
3. 얽힘 보조 확장: 논문은 얽힘 보조 폴딩 양자 AG 코드에 대한 구성도 제시합니다. 이 접근법은 사전 공유된 얽힘 (ebits) 을 활용하여 엄격한 포함 요구사항 ($C_2^\perp \subseteq C_1$) 을 완화함으로써, 임의의 두 폴딩된 에르미트 코드가 양자 코드를 정의할 수 있게 합니다.
4. 디코딩 분석: 결과적인 양자 코드의 리스트 디코딩 가능성은 기반이 되는 고전적인 폴딩된 에르미트 코드의 리스트 디코딩 가능성을 활용하여 분석됩니다. 저자들은 구성 요소인 고전적 코드가 $(\tau, L)$-리스트 디코딩 가능하면 결과적인 CSS 코드는 $(\tau, L^2)$-양자 리스트 디코딩 가능하다는 베르가마시 등의 이전 연구에서 나온 보조정리를 적용합니다.

주요 기여 및 결과

• 폴딩된 양자 에르미트 코드 (FQHC) 구성: 논문은 CSS 프레임워크를 사용하여 폴딩된 양자 에르미트 코드의 명시적 구성을 제공합니다. 이러한 코드는 에르미트 곡선의 특정 자기동형을 통해 폴딩된 원점 에르미트 코드에서 유도됩니다.
• 양자 싱글턴 한계까지의 리스트 디코딩 가능성: 저자들은 FQHC 가 $\tau = \frac{1 - R_{FQHC}}{2} - \epsilon$인 디코딩 반경으로 $(\tau, L)$-리스트 디코딩 가능함을 증명합니다. 여기서 $R_{FQHC}$는 양자 코드의 비율입니다. 이 반경은 폴딩된 양자 리드 - 솔로몬 코드의 성능과 일치하는 양자 싱글턴 한계 ($1 - R$) 에 근접합니다.
• 알파벳 크기 효율성: 주요 결과는 FQHC 가 $(1/\epsilon)^{O(1/\epsilon^2)}$ 크기의 알파벳으로 이러한 성능을 달성함을 보여준다는 점입니다. 반면, 유사한 한계를 달성하는 폴딩된 양자 리드 - 솔로몬 코드는 양자 거리 증폭을 필요로 하여 $2^{O(1/\epsilon^5)}$ 크기의 알파벳을 요구합니다. 저자들은 임의의 $\epsilon$에 대해 FQHC 의 알파벳 크기가 엄격하게 더 작음을 보여 거리 증폭의 필요성을 제거합니다.
• 결정론적 디코딩 알고리즘: 논문은 결정론적 양자 리스트 디코딩 알고리즘의 존재를 확립합니다. 이 절차는 안정자 (stabilizers) 를 측정하여 고전적 신드롬을 얻고, 구성 요소인 폴딩된 에르미트 코드에 고전적 리스트 디코더를 실행하여 후보 오류 목록을 생성한 다음, 이러한 목록을 짝지어 다항식 크기의 후보 파울리 오류 목록을 형성하는 것을 포함합니다. 총 실행 시간은 $N^{O(1/\epsilon^2)}$입니다.
• 얽힘 보조 구성: 논문은 프레임워크를 얽힘 보조 코드로 확장하여, 쌍대 포함 조건을 요구하지 않고 임의의 폴딩된 에르미트 코드 쌍으로부터 양자 코드를 구성할 수 있게 하며, 이는 얽힘을 소비하는 대가를 치릅니다.

의의
본 논문은 폴딩된 양자 에르미트 코드의 구성이 폴딩된 양자 리드 - 솔로몬 코드보다 더 효율적인 대안을 제공한다고 주장합니다. 양수 종수 곡선의 기하학적 구조를 활용함으로써 저자들은 양자 싱글턴 한계까지의 리스트 디코딩 가능성을 달성하면서도 훨씬 더 작은 알파벳 크기를 유지합니다. 결정적으로, 이 연구는 에르미트 곡선을 사용할 때 근사 최적 디코딩 반경을 달성하기 위해 "비싼" 양자 거리 증폭 기법이 필요하지 않음을 보여줍니다. 이는 양수 종수 곡선이 폴딩된 양자 코드의 비율, 오류 정정 반경, 알파벳 크기 간의 더 나은 절충안을 제공함을 시사합니다. 논문은 다른 양수 종수 곡선으로부터 명시적인 폴딩된 양자 AG 코드를 구성하고, CSS 및 얽힘 보조 프레임워크를 넘어선 구성을 탐구하는 것이 여전히 열린 문제임을 결론으로 맺습니다.