기술 요약: 인트랙터블 데카슬론(The Intractable Decathlon) – 양자 최적화 벤치마킹 라이브러리

문제 정의

본 논문은 휴리스틱 양자 최적화 알고리즘을 최첨단 고전 솔버와 체계적이고 공정하며 비교 가능한 방식으로 벤치마킹해야 할 절실한 필요성을 다룹니다. 양자 하드웨어가 대규모 벤치마킹이 가능한 수준으로 발전함에 따라, 현재 이 분야에는 적절한 규모에서 고전적 방법으로는 어렵지만 실질적인 응용 분야와 관련성이 있는 표준화된 문제 인스턴스 세트가 부족한 실정입니다.

저자들은 **인트랙터블 데카슬론(Intractable Decathlon)**을 소개합니다. 이는 10가지의 서로 다른 조합 최적화 문제 클래스의 집합입니다. 이 문제들은 다음과 같은 이유로 선정되었습니다:

1. 시스템 크기가 100개 미만에서 약 100,000개의 결정 변수 범위에 걸쳐 기존 고전 솔버가 어려움을 겪는 문제들입니다(종종 최적성 증명이나 실행 가능한 해를 찾는 데 어려움이 있음).
2. 주로 "프라이멀 디피컬티(primal difficult, 원형 난해성)"를 가집나다. 즉, 좋은 해를 찾는 것이 어려우며, 이는 현재의 휴리스틱 양자 알고리즘의 역량과 일치합니다.
3. 물류, 금융, 네트워크 설계 및 물리학의 실질적으로 유의미한 응용 분야에 매핑됩니다.
4. 정수 변수(가급적 이진 변수)와 정수 계수를 사용하여 모델링할 수 있어, 양자 정식화에서 흔히 발생하는 수치 정밀도 문제를 완화합니다.

10가지 문제 클래스는 다음과 같습니다:

• 마켓 스플릿(Market Split): 다차원 부분 집합 합 문제.
• 저상관 이진 수열(Low Autocorrelation Binary Sequences, LABS): 최소 상관 관계를 갖는 이진 수열 찾기.
• 최소 버코프 분해(Minimum Birkhoff Decomposition): 이중 확률 행렬을 최소한의 치환 행렬로 분해하기.
• 슈타이너 트리 패킹(Steiner Tree Packing): 그래프 내에서 노드 분리 슈타이너 트리를 패킹하기.
• 스포츠 토너먼트 일정 계획(Sports Tournament Scheduling): 복잡한 제약 조건이 있는 더블 라운드 로빈 토너먼트 일정 계획.
• 포트폴리오 최적화(Portfolio Optimization): 거래 비용을 포함한 다기간 평균-분산 최적화.
• 최대 독립 집합(Maximum Independent Set, MIS): 그래프에서 인접하지 않은 가장 큰 정점 집합 찾기.
• 네트워크 설계(Network Design): 최대 엣지 부하를 최소화하는 유향 그래프 구축.
• 차량 경로 문제(Vehicle Routing Problem, CVRP): 고정된 함대 규모를 가진 용량 제한 차량 경로 문제.
• 토폴로지 설계(Topology Design): 순서 및 차수 제약 조건이 주어졌을 때 네트워크 직경 최소화(Order Degree Problem).

방법론

저자들은 알고리즘, 모델, 하드웨어 플랫폼의 선택에 최대한의 유연성을 제공하기 위해 모델 독립적 벤치마킹 프레임워크를 제안합니다. 이 방법론에는 다음이 포함됩니다:

1. 문제 정식화 및 모델링

• 정수 중심: 문제는 정수 결정 변수 $x \in \mathbb{Z}^n$와 선형 또는 이차 목적 함수 및 제약 조건을 기반으로 정의됩니다. 수치적 부정확성을 피하기 위해 계수는 정수로 재조정됩니다.
• 모델 불가지론(Model Agnosticism): 본 라이브러리는 표준 혼합 정수 프로그래밍(MIP) 및 이차 무제약 이진 최적화(QUBO) 정식화를 제공하지만, 벤치마킹의 목표가 특정 정식화에 종속되지 않도록 합니다. 이는 문제를 재정식화하는 것(예: ILP를 QUBO로 변환)이 문제의 크기와 밀도를 극적으로 변화시켜 특정 솔버에 새로운 도전 과제나 이점을 도입할 수 있음을 인정하는 것입니다.
• 실행 가능성 vs 최적화: 프레임워크는 실행 가능성 문제(유효한 해를 찾는 것)와 최적화 문제(최선의 해를 찾는 것)를 구분합니다. 대부분의 양자 알고리즘이 최적성 보장이 없는 휴리스틱임을 고려하여, 벤치마크는 전역 최적성을 증명하는 것보다 고품질의 실행 가능한 해를 찾는 데 중점을 둡니다.

2. 지표 및 보고

재현성과 비교 가능성을 보장하기 위해 저자들은 특정 지표를 정의합니다:

• 해의 품질(Solution Quality): 반복 실행 시 발견된 최적의 목적 함수 값. 확률적 알고리즘의 경우, 최적해에 근접한 해($\epsilon$ 허용 오차 내)를 찾는 성공 횟수를 보고합니다.
• 계산 자원(Computational Resources):
  • 총 실행 시간(Total Runtime): 대기/유휴 시간을 제외한 실제 실행 시간(Wall-clock time).
  • 하드웨어 세부 내역(Hardware Breakdown): CPU, GPU, 양자 처리 장치(QPU) 및 기타 하드웨어에서 소비된 시간의 분리.
  • 양자 실행 시간 정의(Quantum Runtime Definition): IBM 퀀텀 플랫폼을 기준으로, 페이로드 수신부터 샘플 추출까지의 시간으로 정의하며, 회로 준비 및 실행을 포함하되 클래식 트랜스파일 시간(전처리로 간주)은 제외합니다.
• 제출 가이드라인: 모든 세부 사항(모델링 접근 방식, 변수 개수, 계수 범위, 워크플로우 단계)이 포착될 수 있도록 **양자 최적화 벤치마킹 라이브러리(QOBLIB)**를 위한 표준화된 템플릿(Table 10)을 제공합니다.

3. 인스턴스 생성

라이브러리는 "프라이멀 디피컬티"를 갖도록 생성된 인스턴스를 포함합니다. 실행 가능한 해를 찾는 것이 사소한 문제의 경우, 난이도를 보장하기 위해 알려진 해로부터 역공학을 통해 인스턴스를 구성합니다. 인스턴스는 다양한 밀도, 계수 범위 및 변수 개수를 가져 다양한 알고리즘의 병목 현상을 테스트합니다.

주요 기여

1. QOBLIB 저장소: 문제 인스턴스, 모델(MIP/QUBO), 해 검증기(Solution Checkers) 및 베이스라인 결과를 포함하는 오픈 소스 라이브러리입니다.
2. 인트랙터블 데카슬론(The Intractable Decathlon): 이론적 난해함과 실질적 관련성 사이의 간극을 메우는 10가지 문제 클래스 세트로, 근사 양자 하드웨어가 접근 가능한 규모에서 고전 솔버에게 도전적인 문제가 되도록 특별히 선정되었습니다.
3. 표준화된 벤치마킹 프로토콜: 서로 다른 양자 및 고전적 접근 방식 간의 공정한 비교를 촉진하기 위해 지표, 실행 시간 측정(특히 양자 하드웨어), 보고 형식에 대한 엄격한 정의를 제공합니다.
4. 베이스라인 결과: 성능의 하한선을 설정하기 위해 최첨단 솔버(예: Gurobi, CPLEX, 특화된 휴리스틱)를 사용한 광범위한 고전 베이스라인 결과를 제공합니다. 또한 세 가지 특정 문제에 대해 서로 다른 양자 알고리즘을 사용한 예시적인 양자 베이스라인 결과도 제시합니다.

결과 및 예시적 사례

논문은 10가지 모든 문제 클래스에 대한 고전 베이스라인을 제시하며, 많은 인스턴스가 현재 합리적인 시간 내에 고전 솔버에 의해 최적성 증명이 불가능하거나 상당한 계산 자원을 필요로 함을 보여줍니다.

예시적 양자 베이스라인:
저자들은 제출 형식과 현재 역량을 입증하기 위해 특정 양자 알고리즘을 사용하여 세 가지 문제 클래스에 대한 예비 결과를 제공합니다:

• 저상관 이진 수열(LABS):

  • 알고리즘: 편향 필드 디지털 카운터-디아바틱 양자 최적화(Bias-field Digitized Counter-Diabatic Quantum Optimization, BF-DCQO).
  • 결과: 시퀀스 길이 $n=20$(기존 양자 구현인 $n=18$을 초과)에서, 해당 알고리즘은 ibm marrakesh 장치에서 최적해를 찾아냈습니다. 평균 실행 시간은 약 61초(전/후 처리 포함)였으며, QPU 실행 시간은 약 60.8초였습니다.
  • 비교: BF-DCQO의 스케일링은 $p=12$ 레이어를 가진 QAOA와 유사했으나, 얽힘 게이트(entangling gates)는 6배 적게 필요했습니다. 특정 테스트 인스턴스에 대해 시간 대비 해결 능력(time-to-solution) 측면에서 정확한 고전 솔버(Gurobi, CPLEX)보다 우수했으나, 고전 솔버들은 더 작은 인스턴스에 대해 결국 최적해를 찾아냈습니다.

• 최소 버코프 분해(Minimum Birkhoff Decomposition):

  • 알고리즘: 치환 행렬을 샘플링하기 위한 매개변수화된 양자 회로를 사용하는 변분 양자 알고리즘(VQA).
  • 결과: $n=4$ 및 $n=5$ 이중 확률 행렬에 대해 테스트되었습니다. $n=4$의 경우, 알고리즘은 3~4개의 치환을 사용하여 고전 근사 솔버(Birkhoff+, Blended FW)와 일치하거나 이를 능가하는 정확한 분해를 일관되로 찾아냈습니다. $n=5$의 경우 성능이 저하되어 일부 인스턴스만이 희소 분해(sparse decomposition)에 도달했으며, 이는 더 크고 복잡한 인스턴스에 대한 변분 접근 방식의 현재 한계를 보여줍니다.

• 최대 독립 집합(MIS):

  • 알고리즘: GPU 하드웨어 상의 휴리스틱 솔버(ABS2).
  • 결과: 최대 4,000개의 노드를 가진 그래프에 대한 베이스라인 성능 데이터를 제공하여, 휴리스틱 해와 최적 경계(optimal bounds) 사이의 격차를 보여줌으로써 양자 휴리스틱의 목표를 제시했습니다.

의의 및 주장

본 논문은 QOBLIB와 인트랙터블 데카슬론이 컴포넌트 수준의 벤치마킹(예: 게이트 충실도)을 넘어 애플리케이션 수준의 벤치마킹으로 나아가기 위한 필수적인 인프라를 제공한다고 주장합니다.

• 양자 우위 입증: 저자들은 고전 컴퓨터가 어려운 문제(프라이멀 디피컬티)를 해결함으로써만 진정한 양자 우위를 입증할 수 있다고 명시합니다. 선택된 인스턴스들은 근사 양자 장치가 작동할 수 있는 크기에서 고전 솔버가 다루기 힘들도록 설계되었습니다.
• 커뮤니티 협업: 이 작업은 최적화 커뮤니티가 알고리즘, 소프트웨어 및 하드웨어의 발전을 추적하기 위해 이 인스턴스들을 사용하도록 촉구하는 호출의 의미를 담고 있습니다.
• 현재 역량에 대한 겸손함: 논문은 현재의 양자 성능에 대해 신중한 태도를 취합니다. 양자 알고리즘이 유망하고 특정 인스턴스(예: LABS $n=20$)에서 성과를 보이지만, 아직 모든 분야에서 최고의 고전 휴리스틱을 일관되게 능가하지 못한다는 점을 인정합니다. 주요 목표는 벤치마킹 솔루션을 제시하기 위한 표준화된 형식을 확립하여 비교 가능성, 재현성 및 개선 사항을 추적할 수 있는 능력을 보장하는 것입니다.

저자들은 이 프레임워크가 알고리즘의 정확성을 검증하고, 병목 현상을 식별하며, 궁극적으로 양자 컴퓨터가 실제 세계의 조합 최적화 문제를 해결하는 데 있어 실질적인 이점을 제공할 수 있는지 판단하는 데 필수적이라고 결론짓습니다.