COFI-DQI: Curve-based Optimal Function Intersection via Decoded Quantum Interferometry

기술 요약: COFI-DQI: 디코딩된 양자 간섭계(Decoded Quantum Interferometry)를 통한 곡선 기반 최적 함수 교차(Curve-Based Optimal Function Intersection)

문제 정의
본 논문은 유한체 $\mathbb{F}_q$ 상에서의 최대 선형 만족도(Maximum Linear Satisfiability, max-LINSAT) 문제를 다룹니다. $k$개의 변수를 가진 $n$개의 선형 방정식 시스템이 주어졌을 때, 목표는 노이즈나 불일치가 존재하는 상황에서도 가능한 최대수의 방정식을 만족하는 할당(assignment)을 찾는 것입니다. 이 문제는 최대 실행 가능한 부분집합(maximum feasible subsystem) 문제의 유한체 특수화 버전으로, 일반적인 인스턴스의 경우 계산적으로 매우 어렵고(NP-hard), 무작위 할당 베이스라인을 넘어서는 근사화가 어려운 것으로 알려져 있습니다.

저자들은 구조화된 인스턴스에 대해 증명 가능한 가속을 달й기 위해 Jordan 등(2025)이 도입한 양자 알고리즘인 디코딩된 양자 간섭계(Decoded Quantum Interferometry, DQI) 프레임워크를 활용하는 데 집중합니다. DQI는 최적화 문제를 고전 오류 정정 부호의 듀얼(dual)에 대한 신드롬 디코딩(syndrome-decoding) 문제로 환원합니다. 구체적으로, max-LINSAT의 목적 함수를 선형 부호의 듀얼에 대한 신드롬 디코딩 문제로 매핑합니다. DQI의 성능은 듀얼 부호의 디코딩 반경(decoding radius)에 달려 있습니다. 디코딩 반경이 클수록 다항식 증폭(polynomial amplification)의 정도를 높일 수 있으며, 이는 결과적으로 만족되는 제약 조건의 기대 비율을 높입니다.

방법론
본 논문은 OPI(Optimal Polynomial Intersection) 및 HOPI(Hermitian Optimal Polynomial Intersection) 프레임워크를 일반화한 **COFI(Curve-based Optimal Function Intersection)**를 소개합니다. OPI와 HOPI가 각각 사영 직선(projective line) 또는 헤르미안 곡선(Hermitian curve) 상의 다항식 함수로 최적화를 제한하는 반면, COFI는 임의의 매끄러운 사영 곡선(smooth projective curves) 위의 디바이저(divisor)에 대한 리만-로흐 공간(Riemann-Roch space) $L(G)$로 이를 확장합니다.

방법론은 다음과 같이 진행됩니다:

1. 프레임워크 일반화: 저자들은 COFI를 $f \in L(G)$인 함수 $f$를 찾아, $f(P_i)$가 지정된 제약 집합 $F_i \subseteq \mathbb{F}_q$에 속하는 점 $P_i$의 수를 최대화하는 것으로 정의합니다. 이를 통해 대수 기하(AG) 부호를 활용함으로써 단순 다항식을 넘어 유리 함수(rational functions) 상에서 최적화를 수행할 수 있게 합니다.
2. 듀얼 부호 분석: DQI 알고리즘은 듀얼 부호 $C^\perp$의 효율적인 유일 디코딩(unique decoding)을 필요로 합니다. 저자들은 특정 곡선 가계(family)로부터 유도된 AG 부호의 듀얼을 분석합니다. 이들은 특정 곡선의 듀얼 또한 동일한 곡선으로부터 유도된 AG 부호라는 성질에 의존하며, 이를 통해 효율적인 디코딩 알고리즘(예: Berlekamp-Massey-Sakata, Feng-Rao 또는 보간법 기반 방법)을 적용할 수 있습니다.
3. 만족 비율 도출: 이전 DQI 문헌에서 유도된 반원 법칙(semi-circle law)을 사용하여, 저자들은 기대 만족 비율 $s/n$에 대한 하한을 도출합니다. 이 경계값은 듀얼 부호의 디코딩 반경 $\ell$, 체의 크기 $q$, 그리고 제약 조건의 수 $n$의 함수입니다. 핵심 지표는 $\ell/n$의 비율이며, 이는 양자 상태를 최적해 쪽으로 편향시키는 알고리즘의 능력을 결정합니다.
4. 특정 곡선 가계: 본 논문은 유리점이 많은 세 가지 특정 곡선 가계에 이 프레임워크를 적용합니다:
   • 스즈키 곡선(Suzuki Curves): $q=2^{2t+1}$인 $\mathbb{F}_q$ 상에서 정의됨.
   • 확장된 노름-트레이스 곡선(Extended Norm-Trace Curves): 헤르미안 곡선을 일반화한 $\mathbb{F}_{q^t}$ 상의 곡선.
   • 이점 헤르미안 부호(Two-Point Hermitian Codes): 하나의 점이 아닌 두 개의 점에 의해 지지되는 디바이저를 활용함.

주요 기여

1. COFI의 도입: 저자들은 임의의 곡선 상의 리만-로흐 공간에 DQI를 적용하기 위한 통합된 프레임워크를 구축하여, 다항식 표현의 범위를 넘어 그 적용 가능성을 넓혔습니다.
2. 이론적 경계: 저자들은 일반 곡선의 AG 부호로부터 기대 DQI 만족 비율에 대한 명시적인 공식을 도출하였으며, 이 경계값을 종수(genus) $g$ 및 디바이저 $G$의 차수(degree)와 직접 연결하였습니다.
3. 성능 개선:
   • 스즈키 부호: 본 논문은 원점 스즈키 부호(one-point Suzuki codes)가 유사한 길이의 헤르미안 부호와 비교했을 때, 필드 요소당 필요한 큐비트 수를 적게 사용하면서도 개선된 만족 비율을 달성할 수 있음을 보여줍니다.
   • 확장된 노름-트레이스 부호: 디바이저 차수에 대한 특정 가정 하에서, 이 부호들은 상응하는 원점 헤르미안 부호보다 더 큰 만족 비율을 달성합니다.
   • 이점 헤르미안 부호: 저자들은 동일한 차원을 가진 원점 헤르미안 부호와 비교했을 때, 비포화 영역(nonsaturated regime) 내에 있다면 이점 헤르미안 부호가 엄격하게 더 큰 기대 만족 비율을 생성함을 보여줍니다.
4. 고전적 베이스라인과의 비교: DQI의 성능을 스즈키 부호를 사용한 Prange 알고리즘(고전적 무작위 디코딩 알고리즘)과 비교하여, 작은 체 크기에서도 DQI가 더 높은 기대 만족 비율을 달성함을 입증했습니다.

결과

• 큐비트 효율성: 유리점이 많은 곡선(예: 스즈키 및 확장 노름-트레이스)을 활용함으로써, 저자들은 필드 크기 $q$에 대비하여 제약 조건의 수 $n$을 증가시킬 수 있음을 보여줍니다. 이는 리드-솔로몬 부호($n \le q$)나 일부 헤르미안 부호와 비교했을 때, 단일 필드 요소를 표현하는 데 필요한 큐비트 수를 줄여줍니다.
• 만족 비율: 수치적 예시와 이론적 비교(예: 예제 4.5 및 표 4)를 통해, 매칭된 블록 길이와 제약 밀도에 대해 스즈키 부호와 이점 헤르미안 부호가 원점 헤르미안 부호보다 엄격하게 높은 기대 만족 비율의 하한을 제공함을 보여줍니다.
• 디코딩 반경: 분석 결과, 이러한 특정 곡선 가계의 듀얼 부호는 표준 원점 헤리미안 구조의 디코딩 반경을 특정 파라미터 영역에서 (부호 길이에 대해 정규화했을 때) 초과하는 디코딩 반경을 보유하고 있음을 확인했습니다.

의의
본 논문은 COFI가 기존에 연구된 리드-솔로몬 및 원점 헤르미안 설정을 넘어 DQI 프레임워크의 적용 가능성을 확장한다고 주장합니다. 양의 종수(positive genus)를 가진 곡선의 AG 부호가 가진 풍부한 대수적 구조를 활용함으로써, 양자 최적화 알고리즘의 이론적 보증을 개선할 수 있음을 입증했습니다. 특히, 적절한 곡선 가계를 선택하는 것이 큐비트 자원 요구량(필드 요소당 큐비트 수)을 줄이거나 효과적으로 처리할 수 있는 제약 조건의 수를 늘릴 수 있음을 보여주며, 이는 조합 최적화 문제를 위한 더 효율적인 양자 솔루션으로 가는 경로를 제시합니다. 저자들은 이러한 개선이 듀얼 부호에 대한 효율적인 유일 디코딩 알고리즘의 존재 여부에 따라 달라질 수 있음을 언급하며, 분석된 특정 가계들이 이 조건을 충족함을 명시했습니다.