Towards Natural Gas Contract Selection via Quantum-Guided Independent Set Reduction

기술 요약: 양자 유도 독립 집합 축소를 통한 천연가스 계약 선택을 향하여

문제 정의
본 논문은 상호 호환 가능한 천연가스 운송 계약을 선택하는 최적화 과제를 다룹니다. 대규모 에너지 시스템에서 운영자는 시간적, 인프라적, 흐름 관련 제약 조건의 적용을 받는 방대한 수의 후보 계약들 중에서 선택을 해야 합니다. 후보군이 증가함에 따라, 탐색 공간은 전수 조사가 불가능한 수준이 됩니다.

저자들은 이 문제에 대한 **쌍별 추상화(pairwise abstraction)**를 제안합니다. 계약은 호(edge)가 쌍별 호환성을 나타내는 호환성 그래프의 정점(vertex)으로 모델링됩니다. 이 그래프에서 최대 클리크(Maximum Clique) 문제를 찾는 것은 가장 큰 상호 호환 계약 집합을 찾는 것과 같습니다. 마찬가지로, 여그래프(complement graph)를 고려하면, 이 문제는 최대 독립 집합(Maximum Independent Set, MIS) 문제, 즉 인접한 두 정점이 없는 정점들의 부분 집합 $S \subseteq V$ 중 가장 큰 집합을 식별하는 문제로 정식화됩니다.

본 논문은 이러한 쌍별 추상화가 누적 세그먼트 기간 용량 제약(세 개 이상의 개별적으로 호환 가능한 계약이 총 용량을 초 exceed할 수 있는 경우)을 명시적으로 강제하지 않는다는 점을 인정합니다. 따라서 제안된 방법은 2단계 스크리닝 절차의 첫 번째 단계 역할을 합니다. 즉, 상호 호환되는 계약들의 작은 가계(family)로 후보군을 좁힌 후, 이후의 계산 비용이 적은 단계에서 총 용량 제약에 대해 검증하는 방식입니다.

방법론
저자들은 현재의 노이즈가 있는 중간 규모 양자(NISQ) 하드웨어 제약 내에서 대규모 MIS 인스ธาน스를 해결하기 위해 설계된 하이브리드 양자-고전 프레임워크를 개발했습니다. 워크플로우는 네 가지 주요 구성 요소로 이루어집니다:

1. 결정론적 고전적 축소(Deterministic Classical Reduction):
   양자 최적화 이전에, 그래프는 확정적 규칙(예: 셀프 루프 제거, 고립 정점 포함, 차수가 1인 정점을 이웃보다 우선 선택)을 사용하여 반복적인 고전적 축소를 거칩니다. 이 단계는 증명 가능한 최적 정점들을 확정하고 문제의 크기를 줄여, 양자 처리를 위한 더 작은 "환원 불가능한 커널(irreducible kernel)"을 남깁니다. 축소된 그래프는 연결 성분(connected components)으로 분해되어 독립적으로 처리됩니다.

2. 하드웨어 인지형 회로 합성(Hardware-Aware Circuit Synthesis):
   노이즈와 라우팅 오버헤드를 완화하기 위해, 축소된 문제 그래프는 시뮬레이티드 어닐링 휴리스틱을 사용하여 선형 큐비트 토폴로지(IBM의 heavy-hex 아키텍처 모사)에 매핑됩니다. 이 매핑은 특정 **SWAP 예산(SWAP budget)**을 준수하며, 이를 통해 결과적인 상호작용 그래프가 연결되도록 하면서 2-큐비트 게이트 깊이를 최소화합니다. SWAP 예산은 연결된 그래프를 생성하는 최소한의 예산을 찾기 위해 각 인스턴스에 대해 적응적으로 결정됩니다.

3. 계층적 QAOA 파라미터 최적화(Hierarchical QAOA Parameter Optimization):
   변분 파라미터($\beta, \gamma$)를 해결하기 위해 양자 근사 최적화 알고리즘(QAOA)이 사용됩니다. 저자들은 3단계 최적화 전략을 활용합니다:

   • 1단계: $p=1$ 깊이에서의 그리드 탐색을 통해 좋은 초기값을 찾습니다.
     def 2단계: 미분 불필요 최적화 도구인 COBYLA를 사용한 국소 정밀화(local refinement)를 수행합니다.
   • 3단계: 재귀적 깊이 확장 단계로, 깊이 $k$의 파라미터를 깊이 $k+1$의 초기값으로 선형 보간합니다.
     최적화는 비용 해밀토니안의 기댓값을 평가하기 위해 **파울리 전파법(Pauli propagation method)**을 사용하여 고전적으로 수행되며, 이를 통해 전체 상태 벡터 시뮬레이션을 피합니다. 양자 프로세서는 오직 후보 솔루션의 샘플링을 위해서만 사용됩니다.

4. 양자 유도 그래프 축소(Quantum-Guided Graph Reduction):
   단순히 가장 낮은 에너지의 비트스트링 하나만을 선택하는 대신, 알고리즘은 QAOA 측정 분포로부터의 통계적 정보를 활용합니다. 저자들은 저에너지 샘플을 기반으로 각 정점의 **한계 포함 확률(marginal inclusion probability, $p_i$)**을 추정합니다. 높은 확률을 가진 정점은 직접 선택되는 반면, 다른 정점들은 선택 확률과 제거되는 이웃의 수를 균형 있게 맞춘 점수 함수 $score(v) = p_v / (deg(v) + 1)$를 사용하여 순위가 매겨집니다. 이 과정은 반복됩니다: 고전적 축소가 적용되고, QAOA가 제거할 정점을 선택하도록 유도하며, 그래프가 완전히 해결될 때까지 업데이트됩니다.

주요 기여
본 논문은 자신의 기여를 현재의 문제 크기에 대해 최첨단 고전적 정확 솔버(예: KaMIS/ReduMIS)보다 빠른 솔버라고 주장하는 것이 아니라, 방법론적인 것으로 명시합니다. 구체적인 기여는 다음과 같습니다:

• 도메인 적응(Domain Adaptation): 천연가스 계약 선택을 최대 클리크/MIS 문제로 공식화하고, 쌍별 추상화와 전체 파이프라인 스케줄링 사이의 범위를 정의했습니다.
• 하드웨어 인지형 임베딩(Hardware-Aware Embedding): 제한된 SWAP 예산 토폴로지에 QUBO 상호작용 그래프를 임베딩하는 연결성 인지형 회로 합성을 도입하였으며, 회로 깊이를 제어하기 위한 계층적 파라미터 스케줄을 결합했습니다.
• 체계적 벤치마킹(Systematic Benchmarking): 양자 최적화 벤치마킹 라이브러리(QOBLIB)의 15개 인스턴스에 대해 하드웨어 실행 평가와 정답(ground truth)을 제공하며 솔버를 평가했습니다.
• 양자 한계(Quantum Marginals)의 경험적 분석: 전체 QAOA 측정 분포를 사용하는 것이 균일한 무작위 샘플링보다 특히 "고품질 꼬리(high-quality tail)" 영역에서 훨씬 더 나은 결과를 낳는다는 것을 입증했습니다.

실험 결과
프레임워크는 두 가지 벤치마크 세트에서 평가되었습니다:

1. QOBLIB 인스턴스 (15개 그래프, 17~186개 정점):

   • 하이브리드 솔버는 평균 0.996의 근사 비율을 달로했습니다.
   • 15개 인스턴스 중 14개에서 정확한 CPLEX 최적해를 복구했습니다.
   • 도전적인 $C125-9$ 인스턴스(125개 정점)의 경우, 양자 유도 접근 방식은 균일 샘플링 베이스라인에 비해 독립 집합 크기 31 이상에 도달할 확률이 12배 더 높았으며, 베이스라인이 전혀 도달하지 못한 경우에도 5%의 실행에서 최적해(크기 34)를 찾아냈습니다.
   • 실행 간 재현성은 인스턴스의 난이도에 따라 달랐으나, "Best-of-N" 전략은 일관되게 고품질 솔루션을 찾아냈습니다.

2. 합성 천연가스 계약 (6개 그래프, 250~900개 계약):

   • 고전적 전처리는 평균 **86.2%**의 정점을 제거하여, 가장 큰 900개 계약 그래프를 124-큐비트 커널로 축소했습니다.
   • 하이브리드 솔버는 평균 0.989의 근사 비율을 달성했습니다.
   • 6개 인스턴스 중 4개에서 CPLEX 최적해와 일치했습니다. 가장 큰 두 개의 그래프에서는 최적해에서 단 두 개의 계약 차이만 발생했습니다.
   • 균일 무작위 베이스라인은 더 큰 그래프에서 성능이 저조했으며, 가장 큰 인스턴스들의 경우 성공 확률이 1.1% 미만으로 떨어졌습니다.

의의 및 주장
저자들은 현재 기술 수준에 대해 겸허한 입장을 유지합니다. 그들은 현재 양자 하드웨어에서 실행 가능한 문제 크기에 대해 고전적 정확 솔버(branch-and-reduce 또는 KaMIS 등)보다 빠르거나 최적임을 주장하지 않는다고 명시적으로 밝힙니다. 이러한 영역에서는 고전적 방법이 여전히 더 빠르고 정확합니다.

대신, 본 논문의 의의는 다음과 같습니다:

• 방법론적 검증: (하드웨어 인지형 임베딩, 계층적 QAOA, 양자 유도 축소와 같은) 실행 가능한 파이프라인을 입증하였으며, 이는 광범 \text{범위}의 근접 미래 양자 최적화 작업에 전이될 수 있습니다.
• 확장 가능성 경로: 이 프레임워크는 양자 작업량이 전체 문제 크기가 아닌 환원 불가능한 커널의 크기(큐비트 수에 의해 제한됨)에 따라 확장되도록 설계되었습니다. 이는 양자 하드웨어가 개선됨에 따라 고전적 정확 방법이 한계에 부딪히는 더 밀도가 높은 미래의 문제 영역을 처리할 수 있는 위치를 점하게 합니다.
• 개념 증명: 알려진 최적해를 가진 MIS를 테스트베드로 사용하여 양자 기여도를 격리하고 정량화함으로써, 양자 한계(marginals)가 무작위 샘플링보다 고전적 축도를 가이드하는 데 유용한 정보를 포함하고 있음을 증명했습니다.

본 논문은 현재의 구현이 "제품"이라기보다는 "측정 막대(measuring stick)"에 가깝지만, 반복적인 고전-양자 피드백을 통해 대규모 조합 최적화 문제에 근접 미래 양자 컴퓨팅을 적용하는 실질적인 경로를 구축한다고 결론짓습니다.