Optimized QUBO formulation methods for quantum computing

1. 연구 배경 및 문제 정의

• 문제점: 많은 조합 최적화 문제는 QUBO 형태로 변환되어 양자 어닐러 (D-Wave 등) 나 게이트 기반 양자 컴퓨터에서 해결됩니다. 그러나 제약 조건을 QUBO 형식에 포함시키기 위해 슬랙 변수가 필요합니다. 기존의 표준 방법 (Standard Method) 은 제약 조건을 만족시키기 위해 너무 많은 슬랙 변수를 요구하며, 이는 필요한 큐비트 수를 급증시키고 문제의 크기를 제한합니다.
• 목표: NISQ 장치의 제한된 큐비트 수와 연결성 (connectivity) 을 고려할 때, 슬랙 변수를 최소화하면서도 제약 조건을 정확히 부과할 수 있는 새로운 QUBO 재형식화 (reformulation) 기법이 필요합니다.
• 대상 문제: 금융 분야의 실제 시나리오에서 영감을 받은 최대 수익 균형 정산 (Max-Profit Balance Settlement, MPBS) 문제. 이는 NP-하드 문제이며, 각 노드 (사용자) 에 대한 계좌 잔고 상/하한선 (CAP/FLOOR) 과 입출금 균형 (IN/OUT) 제약 조건을 가집니다.

2. 제안된 방법론 (Methodology)

저자들은 슬랙 변수를 줄이기 위해 두 가지 독립적이지만 상호 보완적인 기법을 개발했습니다.

A. 반복 2 차 다항식 (Iterative Quadratic Polynomial, IQP) 방법

• 개념: 제약 조건을 만족하는 이진 변수 조합에는 0 을, 위반하는 조합에는 -1 이하의 값을 갖는 가장 일반적인 2 차 다항식 $P(x, s)$를 찾습니다.
• 절차:
  1. 슬랙 변수 없이 ($s=0$) 2 차 다항식이 존재하는지 확인합니다.
  2. 해가 없으면 슬랙 변수를 하나씩 추가하며 반복적으로 다항식을 구성합니다.
  3. 제약 조건을 위반하는 경우 모든 슬랙 변수 조합에서 페널티 (-1 이하) 를 주고, 만족하는 경우 적어도 하나의 슬랙 변수 조합에서 0 이 되도록 설계합니다.
• 장점: 선형/비선형, 정수/비정수 파라미터 제약 모두에 적용 가능하며, 변수 간의 완전한 연결 (fully connected) 이 필요하지 않아 희소성 (sparsity) 을 유지합니다.

B. 마스터 - 위성 (Master-Satellite, MS) 방법

• 개념: 동일한 이진 변수 집합에 정의된 여러 제약 조건이 있을 때, 이를 **마스터 (Master)**와 **위성 (Satellite)**으로 분류합니다.
  • 마스터 제약: 모든 이진 변수 조합에 대해 엄격하게 부과됩니다.
  • 위성 제약: 마스터 제약이 이미 만족된 경우에만 부과됩니다. 마스터 제약이 위반된 경우 위성 제약에 대한 조건은 무시됩니다.
• 동작 원리: 위성 제약은 마스터 제약이 위반된 경우 실수로 인한 인센티브 (양수 값) 를 줄 수 있으므로, **마스터 제약의 페널티 가중치 ($\lambda_{MC}$)**를 적절히 증폭시켜 전체 페널티가 음수가 되도록 조정합니다.
• 연결 (Concatenation): 3 개 이상의 제약 조건이 공유될 경우, 위계 구조 (마스터 $\to$ 위성 1 $\to$ 위성 2...) 로 연결하여 더 많은 조건을 생략하고 슬랙 변수를 추가로 줄일 수 있습니다.

C. MPBS 문제 적용

• 적용 전략: MPBS 문제에서 IN/OUT 제약 조건을 마스터로, CAP/FLOOR을 위상으로 설정합니다.
• 결과: 노드의 연결된 간선 (arc) 수가 5 개 이하인 경우, IQP 및 MS 방법을 결합하여 슬랙 변수를 거의 사용하지 않거나 (0 개) 극소수 (1~2 개) 만 사용해도 제약 조건을 구현할 수 있음을 증명했습니다.

3. 주요 기여 (Key Contributions)

1. 새로운 QUBO 변환 프레임워크: 기존 표준 방법과 달리 슬랙 변수를 최소화하는 IQP 및 MS 알고리즘을 제안했습니다.
2. 비선형 및 비정수 제약 처리: 제약 조건의 형태나 파라미터 타입에 관계없이 동일한 계산 비용으로 처리 가능함을 보였습니다.
3. 실제 금융 문제 (MPBS) 에의 적용: 실제 UniCredit 은행 데이터에서 영감을 받은 MPBS 문제에 이 기법을 적용하여, 표준 방법 대비 약 90% 적은 슬랙 변수로 QUBO 를 구성할 수 있음을 입증했습니다.
4. 양자 어닐러 성능 비교: D-Wave 의 두 가지 어닐러 (Advantage_system4.1 과 차세대 프로토타입 Advantage2_prototype1.1) 를 사용하여 제안된 방법의 우수성을 검증했습니다.

4. 실험 결과 (Results)

• 슬랙 변수 감소: 제안된 IQPMS 방법을 사용하면 표준 방법 대비 슬랙 변수가 약 90% 감소했습니다. 예를 들어, 표준 방법은 CAP/FLOOR 제약에 노드당 16 개 이상의 슬랙 변수가 필요할 수 있었으나, 제안된 방법은 노드당 0~2 개로 충분했습니다.
• 큐비트 효율성: D-Wave 어닐러에 문제를 매핑 (embedding) 할 때, 표준 방법은 간선 (arc) 당 약 10.5 개의 큐비트가 필요했으나, 제안된 방법은 약 2 개만 필요했습니다.
• 해의 정확도 (Success Rate):
  • 입력 크기 (간선 수) 가 증가함에 따라 표준 방법의 성공률은 급격히 떨어졌으나, 제안된 방법은 높은 성공률을 유지했습니다.
  • 성공률 향상: 가장 작은 인스턴스 (Advantage) 에서 7 배, 가장 큰 인스턴스 (Advantage2) 에서 184 배까지 성공률이 향상되었습니다.
• 어닐러 비교: 차세대 어닐러 (Advantage2) 가 더 높은 연결성과 낮은 노이즈로 인해 더 좋은 성능을 보였으며, 제안된 방법과 결합 시 그 효과가 극대화되었습니다.

5. 의의 및 결론 (Significance)

• NISQ 시대의 실용성: 현재 제한된 큐비트 수와 연결성을 가진 양자 하드웨어에서 더 크고 복잡한 최적화 문제를 해결할 수 있는 길을 열었습니다.
• 문제 정의의 최적화: 양자 알고리즘 자체의 개선뿐만 아니라, 문제를 QUBO 로 변환하는 전처리 (pre-processing) 단계의 최적화가 양자 컴퓨팅 성능에 결정적임을 강조했습니다.
• 확장성: 이 방법은 금융뿐만 아니라 물류, 약물 발견 등 다양한 NP-하드 조합 최적화 문제에 적용 가능하며, 특히 국소적으로 제약된 (locally-constrained) 문제 구조에 매우 효과적입니다.

요약하자면, 이 논문은 양자 어닐링을 위한 QUBO 형식화 과정에서 발생하는 '슬랙 변수 과부하' 문제를 해결하기 위한 혁신적인 수학적 기법을 제시하고, 이를 실제 금융 데이터에 적용하여 기존 방법 대비 압도적인 성능 향상을 입증했습니다.