A quantum annealing approach to the minimum distance problem of quantum codes

기술 요약: 양자 코드의 최소 거리 문제에 대한 양자 어닐링 접근법

문제 정의
양자 오류 정정 코드(QECC)의 최소 거리($d$)는 코드가 양자 정보를 보존하는 능력을 정의하는 핵심 파라미터이다. 구체적으로, $d$는 탐지되지 않는 오류(논리적 파울리 연산자)의 최소 가중치(weight)를 나타낸다. 일반적인 이진 안정화 코드(binary stabilizer code)에 대해 $d$를 결정하는 것은 NP-난해(NP-hard) 문제로 알려져 있다. Grassl와 White가 개발한 특화된 고전 알고리즘(예: BZDistMW 등)이 존재하지만, 저자들은 현대의 양자 플랫폼이 특히 양자 하드웨어가 확장됨에 따라 이 양을 평가하거나 경계값을 구하기 위한 실행 가능한 대안이나 새로운 경로를 제공할 수 있는지 탐구하고자 한다.

방법론
저자들은 이진 양자 안정화 코드의 최소 거리 문제를 이차 무제약 이진 최적화(QUBO) 문제로 재정의할 것을 제안한다. 이러한 재정의를 통해 문제를 확립된 QUBO 솔버, 여기에는 고전적 휴리스틱, 하이브리드 양자-고전 알고리즘, 그리고 양자 어닐링(QA)이 포함된다.

핵심 알고리즘 단계는 다음과 같다:

1. 파울리 가중치 표현: 파울리 연산자의 가중치는 $X$ 및 $Z$ 서포트를 나타내는 이진 벡터를 사용하여 표현된다. 표준 가중치 공식은 패리티 함수의 곱을 포함하며, 이는 이차 형식이 아니다.
2. 패리티 분해: 이차 형식을 달성하기 위해, 저자들은 패리티의 곱을 행렬 $A$, $B$, 그리고 $A+B$와 관련된 세 개의 패리티 함수의 합으로 분해한다.
3. 모듈로 산술 제거: 패리티 계산에 내재된 모듈로-2 연산은 보조 비음수 정수 변수들에 대한 최소화 과정으로 대체된다. 이 정수들은 이진 변수를 사용하여 인코딩되며, 이는 전체 변수의 개수에 로그 단위의 곱셈 오버헤드를 도입한다. 총 변수 개수는 물리적 큐비트 수 $n$에 따라 $O(n \log n)$으로 스케일링된다.
4. 제약 조건 처리: 해가 자명한 논리 연산자(즉, 안정화 그룹에 속하지 않는 것)여야 한다는 요구 사항은 두 가지 방식으로 처리된다:
   • 페널티 방법: 제약 조건이 위반될 경우 비용 함수에 페널티 항을 추가한다.
   • 섹터 분해: 해 벡터의 첫 번째 비제로(non-zero) 성분의 위치를 고정함으로써 문제를 여러 개의 무제약 QUBO로 나눈다. 순환 자기 쌍대 코드(circulant self-dual codes)의 경우, 대칭성을 활용하여 단일 변수($x_1=1$)를 고정함으로써 제약 조건을 만족시킬 수 있으며, 이는 단일 무제약 QUBO 문제로 축소된다.

실험적 구현 및 결과
저자들은 D-Wave Advantage 4.1 양자 어닐러와 Qbsolv 하이브리드 양자-고전 알고리즘을 사용하여 제안된 공식을 테스트하였다. 이들은 다음 모델들과 벤치마킹하였다:

• 시뮬레이티드 어닐링 (SA): 고전적 휴리스틱.
• 특화된 고전적 방법: 정확한 Brouwer–Zimmermann 알고리즘(BZDistMW) 및 휴리스틱 QDistRnd.

주요 결과는 다음과 같다:

• 순수 양자 어닐링: 작은 코드 크기($n \leq 12$)에 대해 QA는 정확한 최소 거리를 성공적으로 찾아냈다. 그러나 더 큰 크기($n \geq 13$)에서는 성능이 저하되었으며, QA는 보수적인 상한값만을 제공할 수 있었다. 저자들은 이를 마이너 임베딩(minor embedding)을 요구하는 제한된 큐비트 연결성으로 인해 물리적 큐비트 요구량이 이차적으로($O(n^2 \log^2 n)$ 유효 물리적 요구량) 증가하고 노이즈가 유입되는 현상 때문이라고 설명한다.
• 하이브리드 vs 고전: QA 지원 및 SA 지원 Qbsolv 구현은 전반적으로 유사한 성능을 보였다. 두 방식 모두 동일한 벽시계 시간(wall-clock time) 예산 내에서 테스트된 인스턴스들에 대해 특화된 고전적 거리 탐색 방법(특히 QDistRnd)보다 효과가 떨어졌다.
• 런타임 분석: 어닐링 역학에 대한 수치 시뮬레이션은 이론적으로 요구되는 어닐링 시간이 나노초 범위임을 시사했다. 그러나 실제 하드웨어에서는 약 $4.5 \, \mu s$의 어닐링 시간에서 최적의 성능이 관찰되었는데, 이는 성능이 비단열 전이(non-adiabatic transitions)보다는 노이즈 축적에 의해 현재 지배되고 있음을 시사한다.

주요 기여

1. QUBO 공식화: 본 논문은 이진 안정화 코드의 최소 거리 문제를 위한 솔버 독립적인 QUBO 공식을 소개한다.
2. 변수 스케일링: 이 방법은 변수 개수에 로그 단위의 곱셈 오버헤드($O(n \log n)$)만을 도입하여, 하드웨어 연결성이 개선된다면 더 큰 논리적 문제에 대해서도 이론적으로 확장 가능하다.
3. 경험적 벤치마킹: 본 연구는 특정 NP-난해 문제에 대해 양자, 하이브리드 및 고전적 접근 방식을 엄격하게 비교하며, 현재의 양자 어닐링 하드웨어(특히 연결성 및 노이즈)가 성숙한 고전적 알고리즘에 비해 갖는 한계를 명확히 밝힌다.

의의 및 주장
저자들은 자신들의 연구의 의의를 양자 우위의 입증이라기보다 QUBO 공식화에 대한 **개념 증명(proof-of-concept)**으로 겸허하게 규정한다.

• 저자들은 현재의 양자 어닐링 구현이 특화된 고전적 방법보다 계산적 우위를 보여주지 못함을 명시적으로 밝힌다.
• 주요 가치는 미래의 더 강력한 양자 플랫폼 및 범용 QUBO 솔버에서 활용될 수 있는 프레임워크를 구축하는 데 있다.
• 본 논문은 마이너 임베딩과 연결성을 현재 구현상의 핵심적인 제한 요소로 식별한다.
• 저자들은 이 접근법이 개념적으로 최소 거리 문제와 유사한 격자 최단 벡터 문제(shortest lattice vector problem)와 같은 정보 이론의 다른 NP-난해 문제들로 확장될 수 있다고 제안한다.

결론적으로, 현재의 하드웨어는 고전적 솔버를 능가하지 못하지만, 이 재정립된 방식은 양자 하드웨어의 연결성과 품질이 향면함에 따라 향후 탐구를 위한 실행 가능한 경로를 제공한다.