1. 연구 배경 및 문제 정의 (Problem)

• 배경: 대규모 결함 허용 양자 컴퓨팅 (FTQC) 시스템은 수천 개의 논리 큐비트와 깊은 회로 깊이를 요구합니다. 양자 상태의 취약성으로 인해 양자 오류 정정 (QEC) 이 필수적이며, 이를 위해 측정된 오류 신드롬 (syndrome) 을 해석하고 보정 작업을 결정하는 '디코더 (Decoder)'가 핵심 역할을 합니다.
• 문제점:
  • 자원 불균형: 전력, 메모리 대역폭, 칩 면적 등의 물리적 제약으로 인해 각 논리 큐비트에 전용 디코더를 할당하는 것은 불가능합니다. 따라서 사용 가능한 디코더 수 ($M$) 는 논리 큐비트 수 ($N$) 보다 훨씬 적습니다 ($M \ll N$).
  • 가상화 양자 디코더 (VQD) 의 한계: 제한된 디코더 풀을 여러 큐비트가 시간 분할 (Time-multiplexing) 방식으로 공유하는 VQD 아키텍처가 제안되었으나, 기존 스케줄링 알고리즘 (MFD, RR, MLS 등) 은 **국소적 휴리스틱 (Local Heuristics)**에 의존합니다.
  • 기존 알고리즘 (MLS) 의 결함: '최장 해독되지 않은 시퀀스 최소화 (Minimize Longest Undecoded Sequence, MLS)' 알고리즘은 현재 시점의 대기열 길이를 기준으로 할당하지만, **전체 회로 구조 (Global Circuit Structure)**를 고려하지 못합니다. 특히, 논리 T 게이트 실행 전에는 반드시 디코딩이 완료되어야 하는 '강제적 우선순위 (Mandatory Precedence)'를 예측하지 못해, 디코더 자원이 T 게이트 요구에 의해 선점되는 동안 다른 큐비트들이 예상치 못한 긴 대기 시간을 겪게 됩니다. 이는 시스템의 불안정성과 메모리 오버헤드를 초래합니다.

2. 제안된 방법론: CODA (Methodology)

저자들은 **CODA (Constraint-Optimal Driven Allocation)**라는 새로운 스케줄링 알고리즘을 제안합니다. 이는 휴리스틱이 아닌 전역 최적화 기반 (Global Optimization-based) 접근법입니다.

• 핵심 아이디어:
  • 디코더 할당 문제를 직접적인 최적화 문제 (Optimization) 로 풀기보다, **구현 가능성 결정 문제 (Feasibility Decision Problem)**의 연속으로 변환합니다.
  • 목표는 '최장 해독되지 않은 시퀀스 길이 ($G$)'를 최소화하는 것이지만, 이를 위해 $G=1$부터 시작하여 점진적으로 증가시키며 주어진 시간 제한 내에서 모든 제약 조건을 만족하는 해가 존재하는지 확인합니다.
• 알고리즘 흐름:
  1. 제약 조건 생성 (Constraint Generator): 물리적 자원 제약 (사용 가능한 디코더 수) 과 성능 제약 (최대 허용 대기 길이 $G$), 그리고 논리 게이트 (T 게이트) 에 따른 강제적 우선순위 제약을 수학적 모델로 정의합니다.
  2. 최적화 솔버 (Optimization Solver): 제약 프로그래밍 (CP-SAT) 솔버를 사용하여 정의된 제약 하에서 해가 존재하는지 탐색합니다.
  3. 시간 제한 탐색 (Time-Bounded Search): 각 $G$ 값에 대해 엄격한 시간 제한 ($T_{limit}$) 을 두어 계산 복잡도를 통제합니다. 해가 발견되면 즉시 해당 할당 맵을 반환하고 종료합니다. 해가 없으면 $G$를 1 씩 증가시켜 제약 조건을 완화하고 다음 단계를 수행합니다.
• 기술적 혁신:
  • 전역적 관점: T 게이트와 같은 미래의 필수 디코딩 요구사항을 사전에 고려하여, 현재 시점의 대기열이 길더라도 T 게이트가 없는 큐비트에 디코더를 할당하는 등 전역적으로 자원을 균등하게 분배합니다.
  • 복잡도 우회: 이론적으로 NP-hard 인 조합 폭발 (Combinatorial Explosion) 문제를, 해의 존재 여부를 검증하는 단계적 과정으로 변환함으로써 계산 비용을 선형적으로 관리합니다.

3. 주요 기여 (Key Contributions)

1. 확장 가능한 디코딩의 수학적 모델링: 디코더 스케줄링 문제의 계산적 난이도를 분석하고, 이를 효율적인 해를 찾을 수 있는 일련의 구현 가능성 결정 문제로 재정의했습니다.
2. CODA 알고리즘 설계: 자원 제약과 디코딩 우선순위 (T 게이트 등) 를 통합한 제약 최적화 기반 스케줄링 알고리즘을 개발하여, 전역 최적 해를 찾는 동시에 확장성을 보장합니다.
3. 실증적 검증: 19 개의 벤치마크 회로에 대한 실험을 통해 기존 휴리스틱 (RR, MLS) 대비 성능이 월등히 뛰어나며, 회로 크기가 커져도 스케줄링 시간이 선형적으로 증가함을 입증했습니다.

4. 실험 결과 (Results)

• 성능 향상 (Longest Undecoded Sequence Length):
  • 19 개의 벤치마크 회로 (소형, 중형, 대형 포함) 에서 CODA 는 기존 최첨단 휴리스틱인 MLS 대비 평균 74% 감소, RR 대비 더 큰 개선을 보였습니다.
  • 특정 회로 (예: qwalk-31) 에서는 최대 99.97% (3853→1) 의 감소 효과를 기록했습니다.
  • 이는 오류 누적 (Error Accumulation) 을 효과적으로 억제하여 시스템 안정성을 높임을 의미합니다.
• 확장성 (Scalability):
  • 이론적으로 해 공간은 회로 크기에 따라 지수적으로 증가하지만, CODA 는 **선형 스케일링 (Linear Scaling)**을 보입니다.
  • 큐비트 수가 5 개에서 60 개로 증가할 때, 스케줄링 소요 시간은 1.21 초에서 135.67 초로 선형적으로 증가하여 대규모 FTQC 시스템에서도 실용적인 실행 시간을 보장합니다.
  • 이는 물리적 자원 비율 ($N/M$) 에 의해 결정되며, 조합론적 탐색 공간의 폭발을 우회했음을 의미합니다.
• 기타 지표:
  • 디코더 활용률 (Utilization) 과 메모리 사용량 (Peak Memory Usage) 에서도 기존 방식보다 우수한 효율성을 보여주었습니다.

5. 의의 및 결론 (Significance)

• FTQC 의 핵심 병목 해결: 대규모 양자 컴퓨팅 시스템에서 디코더 자원의 부족은 근본적인 병목 현상이며, CODA 는 이를 해결하여 효율적인 디코더 가상화 (Decoder Virtualization) 를 가능하게 합니다.
• 휴리스틱의 한계 극복: 국소적 의사결정에 의존하는 기존 방식의 단점을 보완하고, 전역 회로 구조를 고려한 최적화 기반 솔루션을 제시함으로써 시스템의 안정성과 확장성을 동시에 확보했습니다.
• 실용성: 이론적 복잡도 문제를 우회하여 실제 대규모 시스템에서도 적용 가능한 스케줄링 시간을 보장하므로, 향후 수천 개의 논리 큐비트를 가진 결함 허용 양자 컴퓨터의 실현을 위한 중요한 기반 기술로 평가됩니다.

요약하자면, 이 논문은 CODA를 통해 제한된 디코더 자원을 가진 대규모 양자 시스템에서 전역 최적화를 기반으로 한 효율적이고 확장 가능한 오류 정정 스케줄링을 실현하여, FTQC 시스템의 안정성을 획기적으로 개선함을 증명했습니다.