Constrained Quantum Optimization at Utility Scale: Application to the Knapsack Problem

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

• 배경: 제약 조건이 있는 조합 최적화 문제는 양자 컴퓨팅, 특히 현재의 NISQ(Noisy Intermediate-Scale Quantum) 하드웨어에서 해결하기 매우 어렵습니다. 그러나 이러한 문제는 에너지 시스템의 유닛 커미트먼트 (Unit Commitment, UC) 문제와 같이 산업적으로 매우 중요합니다. UC 는 예측된 수요를 충족하면서 공학적 및 운영 제약을 준수하도록 발전 단위의 가동 여부를 결정하는 문제입니다.
• 주요 과제:
  1. 혼합 정수 최적화: UC 문제는 이진 변수 (가동/정지) 와 연속 변수 (전력 출력) 를 모두 포함하여, 양자 하드웨어에서 연속 변수를 직접 처리하는 데 큰 오버헤드가 발생합니다.
  2. 제약 조건 처리: 기존 변분 양자 알고리즘 (QAOA 등) 은 전체 힐베르트 공간을 탐색하므로, 유효한 해 (feasible solution) 만이 존재하는 좁은 부분 공간 내에서 탐색하는 데 비효율적입니다.
  3. 규모의 문제: 유틸리티 규모 (수백 개의 단위) 의 문제를 실제 양자 하드웨어에서 해결하는 것은 아직 시도되지 않았습니다.
• 목표: 단일 기간 (single-period) UC 문제를 1 차원 배낭 문제 (1D Knapsack Problem) 로 축소하고, 이를 cop-QAOA 알고리즘을 사용하여 IBM 양자 하드웨어 (최대 150 큐비트) 에서 성공적으로 해결하는 것을 목표로 합니다.

2. 방법론 (Methodology)

A. 문제 축소 (Problem Reduction)

• 단일 기간 UC 문제를 1 차원 배낭 문제로 변환하기 위해 1 차 최적성 조건 (First-order optimality conditions) 을 활용했습니다.
• 연속 변수인 전력 출력 ($p_i$) 을 라그랑주 승수 (한계 비용 $D$) 를 통해 분석적으로 제거했습니다.
• 결과적으로, UC 문제는 단 하나의 연속 파라미터 $D$ 와 이진 변수 ($y_i$) 로 구성된 배낭 문제로 환원되었습니다. 이는 $D$를 탐색하는 과정에서 각 $D$ 값에 대해 배낭 문제를 해결하는 하이브리드 워크플로우를 가능하게 합니다.

B. Copula-QAOA (cop-QAOA) 알고리즘

• 핵심 아이디어: 제약 조건을 엄격하게 강제하는 복잡한 회로 (깊은 회로) 대신, 편향된 초기 상태 (Biased Initial State) 와 상수 깊이 믹서 (Constant-depth Mixer) 를 사용하여 양자 상태를 유효한 해 공간 쪽으로 편향시킵니다.
• 편향된 초기 상태: 'Lazy Greedy' 휴리스틱을 기반으로 한 'Warm-start' 분포를 사용하여, 각 큐비트가 $|1\rangle$ 상태가 될 확률 ($p_i$) 을 할당합니다. 이는 무작위 중첩 상태 대신 유망한 해에 가까운 상태에서 시작하게 합니다.
• 편향된 믹서 (Copula Mixer): 변수 간의 상관관계를 유지하면서 유효한 해 공간 내부를 탐색할 수 있도록 설계된 2 큐비트 유니터리 연산자를 사용합니다. 이는 제약 조건을 위반하는 상태로 전이하는 것을 억제하면서도 회로 깊이를 얕게 유지합니다.
• 구현: IBM Quantum 하드웨어 (Heron r2 프로세서, ibm_kingston) 에서 최대 150 큐비트까지 실행되었으며, Q-CTRL 의 성능 관리 (Performance Management) 툴을 사용하여 오류 억제 (layout 최적화, 동적 결합 등) 를 적용했습니다.

3. 주요 기여 (Key Contributions)

1. 유틸리티 규모의 실증: IBM 양자 하드웨어에서 최대 150 큐비트를 사용하여 제약 조건이 있는 조합 최적화 문제를 해결한 가장 큰 규모의 성공적인 실증을 제시했습니다.
2. 효율적인 알고리즘 적용: 제약 조건을 구조적으로 처리하는 cop-QAOA가 실제 하드웨어에서 유틸리티 규모의 문제 (UC → Knapsack) 에 적용 가능함을 입증했습니다.
3. 고전 솔버와의 경쟁력: Gurobi(상업용 최적화 솔버) 가 해를 찾지 못하거나 최적성 갭 (optimality gap) 이 존재하는 난이도 높은 인스턴스에서, cop-QAOA 가 Gurobi 보다 더 나은 해를 찾거나 동등한 성능을 보임을 입증했습니다.
4. 하이브리드 워크플로우 개선: 기존 연구의 한계를 극복하고, 단일 시간 단계 UC 문제를 단 하나의 연속 파라미터만 사용하여 양자 - 고전 하이브리드 방식으로 해결하는 방법을 제안했습니다.

4. 실험 결과 (Results)

• 실험 설정: 100 개 및 150 개 아이템을 가진 배낭 문제 인스턴스를 사용했습니다. Gurobi 가 최적 해를 찾기 어렵거나 (최적성 갭 존재), 검증에 시간이 많이 소요되는 인스턴스를 선정했습니다.
• 성능 비교:
  • 시뮬레이터: cop-QAOA 는 Lazy Greedy(휴리스틱) 기반의 Warm-start 해보다 더 나은 비용 (Cost) 을 달성했습니다. 특히 근사 비율 (Approximation Ratio) 에서 유의미한 개선을 보였습니다.
  • 하드웨어 (IBM Kingston): 잡음 환경에서도 유효한 해를 생성했습니다. 100 개 아이템 인스턴스에서는 Gurobi 가 70 분 이상 실행해도 개선하지 못한 해를, cop-QAOA 는 3 분 이내의 실행 시간 (훈련 제외) 으로 개선된 해를 찾았습니다.
  • 150 개 아이템: 하드웨어에서 유효한 샘플 비율이 감소하는 경향이 있었으나, 여전히 유효한 해를 생성했으며 Lazy Greedy 보다 우수한 성능을 보였습니다.
• 훈련 및 파라미터:
  • 무작위 초기화보다는 Lazy Greedy 기반의 Warm-start가 필수적이었습니다.
  • 파라미터 학습 시, 비용 함수의 기대값 최적화만으로는 부족할 수 있어, 그리드 서치 (Grid Search) 를 통해 초기 파라미터를 설정하는 전략이 효과적이었습니다.
  • 서로 다른 인스턴스 간에 파라미터 공간 (Cost landscape) 이 유사하여, 파라미터 전이 (Parameter Transfer) 가능성도 시사했습니다.

5. 의의 및 결론 (Significance & Conclusion)

• 실용적 가치: 이 연구는 양자 컴퓨팅이 이론적 가능성을 넘어, 실제 산업 문제 (에너지 관리) 의 규모와 복잡성을 가진 문제에서 고전 알고리즘과 경쟁할 수 있음을 보여줍니다.
• 하드웨어 효율성: 제약 조건을 엄격하게 강제하는 깊은 회로 대신, 얕은 회로와 편향된 초기 상태를 사용하는 접근 방식이 NISQ 하드웨어에서 매우 효과적임을 입증했습니다.
• 향후 전망:
  • 시간 결합 제약 (ramping limits 등) 이 포함된 다기간 UC 문제로 확장.
  • 제약 조건 최적화를 위한 더 나은 파라미터 학습 전략 및 CVaR 기반 방법론의 적용.
  • 실제 운영 환경을 반영한 벤치마크 인스턴스 생성 기법 고도화.

요약하자면, 이 논문은 제약 조건이 있는 대규모 조합 최적화 문제를 해결하기 위해 cop-QAOA를 개발하고, 이를 150 큐비트 규모의 IBM 양자 하드웨어에서 실행하여 Gurobi 와 경쟁하는 수준의 성능을 입증한 획기적인 연구입니다. 이는 양자 최적화 알고리즘이 실제 유틸리티 규모의 문제에 적용 가능한 첫 번째 사례 중 하나로 평가됩니다.