⚛️ quantum physics

Encoding Matters: Benchmarking Binary and D-ary Representations for Quantum Combinatorial Optimization

이 논문은 조합 최적화 문제를 이진 변수(QUBO) 대신 고차원 큐디트(qudit) 변수(QUDO)로 인코딩함으로써, 페널티 항으로 인한 복잡성을 줄이고 근사 비율과 계산 효율성을 높일 수 있음을 다양한 문제 사례를 통해 입증했습니다.

원저자: Shashank Sanjay Bhat, Peiyong Wang, Joseph West, Udaya Parampalli

게시일 2026-02-10

📖 2 분 읽기🧠 심층 분석

CC BY 4.0

원저자: Shashank Sanjay Bhat, Peiyong Wang, Joseph West, Udaya Parampalli

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

1. 기존 방식 (QUBO): "수만 개의 스위치로 책 정리하기" 💡

기존의 양자 컴퓨터 방식(QUBO)은 모든 선택지를 **'켜짐(1) 또는 꺼짐(0)'**이라는 아주 단순한 스위치로만 표현해야 합니다.

예를 들어, 10권의 책을 10개의 선반에 정리해야 한다고 해봅시다. 기존 방식은 이렇게 합니다.

"1번 책이 1번 선반에 있는가?" $\rightarrow$ (스위치 1개)
"1번 책이 2번 선반에 있는가?" $\rightarrow$ (스위치 1개)
... 이런 식으로 모든 경우의 수를 스위치로 만듭니다.

문제점: 책이 많아지면 스위치가 수천, 수만 개로 늘어납니다. 게다가 "한 선반에는 책이 딱 한 권만 있어야 해!"라는 규칙을 지키기 위해, 수많은 **'벌칙용 스위치(Penalty terms)'**를 추가로 달아야 합니다. 스위치가 너무 많아지니 양자 컴퓨터가 감당하기 힘들어지고, 계산도 엄청나게 복잡해집니다.

2. 새로운 방식 (QUDO): "숫자가 적힌 다이얼 사용하기" 🎡

이 논문에서 제안하는 방식(QUDO)은 스위치 대신 **'숫자가 적힌 다이얼'**을 사용합니다.

똑같이 10권의 책을 정리할 때, 이 방식은 이렇게 합니다.

"1번 선반의 다이얼을 돌려라." $\rightarrow$ (다이얼 1개)
다이얼을 1부터 10까지 돌리면, 그 숫자가 바로 '어떤 책이 들어갈지'를 결정합니다.

장점:

공간 절약: 스위치 수천 개가 필요했던 것이, 다이얼 10개로 끝납니다. (양자 컴퓨터의 메모리를 훨씬 적게 씁니다!)
규칙이 자연스러움: 다이얼 하나가 이미 '하나의 선택'을 의미하므로, "한 선반에 책이 여러 권 있으면 안 된다"는 복잡한 규칙을 일일이 스위치로 만들 필요가 없습니다.

3. 실험 결과: "다이얼 방식이 압도적으로 빠르고 정확하다!" 🏆

연구진은 이 '다이얼 방식(QUDO)'이 실제로 얼마나 좋은지 여러 가지 어려운 문제(여행 경로 짜기, 색칠하기, 작업 스케줄 짜기 등)로 테스트해 봤습니다.

결과는 놀라웠습니다.

정확도: 기존 방식은 규칙을 지키느라 쩔쩔매며 엉뚱한 답을 내놓기도 했지만, 다이얼 방식은 훨씬 더 정확한 정답을 찾아냈습니다.
속도: 다이얼 방식은 계산 과정이 훨씬 매끄러워서, 정답에 도달하는 시간이 훨씬 짧았습니다.
효율성: 양자 컴퓨터의 자원을 훨씬 적게 쓰면서도 더 어려운 문제를 풀 수 있었습니다.

요약하자면? 📝

이 논문은 **"양자 컴퓨터에게 문제를 줄 때, 0과 1로만 이루어진 복잡한 스위치 뭉치를 던져주는 대신, 숫자를 직접 돌릴 수 있는 다이얼을 쥐여주자!"**라고 제안하는 것입니다.

이렇게 하면 양자 컴퓨터가 훨씬 가볍게(적은 자원), 똑똑하게(높은 정확도), 빠르게(효율성) 복잡한 세상의 문제들을 해결할 수 있다는 것을 증명한 연구입니다.

[기술 요약] 양자 조합 최적화를 위한 이진 및 D-진 표현 방식의 벤치마킹 연구

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

조합 최적화 문제(TSP, VRP, Graph Coloring 등)를 양자 컴퓨터로 해결하기 위해 현재 가장 널리 쓰이는 방식은 **QUBO(Quadratic Unconstrained Binary Optimization)**입니다. 하지만 QUBO 방식은 다음과 같은 치명적인 한계가 있습니다.

제약 조건의 복잡성: 변수가 이진수(0 또는 1)로만 제한되기 때문에, "한 위치에는 하나의 도시만 방문해야 한다"와 같은 제약 조건을 강제하기 위해 수많은 **보조 변수(Auxiliary variables)**와 **패널티 항(Penalty terms)**을 추가해야 합니다.
자원 낭비: 제약 조건을 처리하기 위한 패널티 항들이 해밀토니안(Hamiltonian)을 매우 복잡하고 조밀하게(dense) 만들어, 큐비트(Qubit) 수와 회로 깊이(Circuit depth)를 급격히 증가시킵니다. 이는 NISQ(잡음이 있는 중규모 양자) 시대의 하드웨어 제약과 충돌하여 확장성(Scalability)을 저해합니다.

2. 연구 방법론 (Methodology)

본 논문은 QUBO의 대안으로 QUDO(Quadratic Unconstrained D-ary Optimization) 프레임워크를 제안하고 이를 체계적으로 검증합니다.

QUDO의 핵심 개념: 의사결정 변수를 단순 이진수가 아닌, $d$ 개의 상태를 가질 수 있는 D-ary(D-진) 변수로 직접 인코딩합니다. 이를 양자 하드웨어에서는 **큐디트(Qudit)**를 사용하여 구현합니다.
자연스러운 제약 조건 통합: QUDO는 변수의 도메인(Domain) 자체를 활용하여 제약 조건을 표현합니다. 예를 들어, 변수 하나가 이미 여러 상태를 가질 수 있으므로, QUBO에서 필요했던 복잡한 '원-핫 인코딩(One-hot encoding)' 없이도 구조적 제약을 훨씬 간결하게 표현할 수 있습니다.
실험 설계:
- 대상 문제: TSP(외판원 문제), VRP(차량 경로 문제 - 단일/다중 데포), Max-K-Cut, Graph Coloring, Job Scheduling.
- 알고리즘: QUBO에는 표준 QAOA를, QUDO에는 이를 확장한 qudit QAOA를 적용했습니다.
- 평가 지표: 근사비(Approximation Ratio, AR), 도달 확률(Reach %), 유효 해 샘플링 확률( $P_{valid}$ ), 최적화 반복 횟수, 실행 시간(Wall-clock time) 등.

3. 주요 기여 및 결과 (Key Contributions & Results)

① 양자 자원의 획기적 절감 (Resource Efficiency)

모든 실험에서 QUDO는 QUBO에 비해 필요한 양자 변수(큐비트 vs 큐디트)의 수를 크게 줄였습니다.

예시 (TSP): $N$ 개 도시 문제에서 QUBO는 $N^2$ 개의 큐비트가 필요하지만, QUDO는 $N$ 개의 큐디트만 있으면 됩니다. 이는 힐베르트 공간(Hilbert space)의 크기를 효율적으로 관리할 수 있게 합니다.

② 최적화 성능 및 안정성 향상 (Algorithmic Performance)

높은 근사비(AR)와 도달 확률: QUDO 기반의 qudit QAOA는 QUBO보다 훨씬 높은 근사비와 안정적인 도달 확률을 보였습니다. 특히 문제 규모가 커질수록 QUBO는 유효한 해를 찾을 확률( $P_{valid}$ )이 급격히 떨어지는 반면, QUDO는 안정적인 성능을 유지했습니다.
매끄러운 최적화 지형(Optimization Landscape): QUDO는 제약 조건으로 인한 복잡한 패널티 항을 줄임으로써, 고전적 최적화 알고리즘(COBYLA 등)이 파라미터를 더 효율적으로 찾을 수 있는 '매끄러운' 에너지 지형을 제공합니다.

③ 문제별 특이 사항

VRP 및 Graph Coloring: QUBO는 제약 조건 충돌로 인해 유효한 해를 찾는 데 실패하는 경우가 많았으나, QUDO는 변수 자체에 제약이 내재되어 있어 매우 높은 유효성( $P_{valid}$ )을 보였습니다.
Job Scheduling: QUDO는 문제 규모가 커져도 최적해를 거의 완벽하게(AR $\approx$ 1) 찾아내며 매우 빠른 실행 시간을 기록했습니다.

4. 연구의 의의 (Significance)

본 연구는 **"인코딩 방식이 양자 알고리즘의 성패를 결정한다"**는 것을 입증했습니다.

확장성 증명: QUDO가 단순한 이론적 모델을 넘어, 복잡한 조합 최적화 문제를 NISQ 장치에서 더 큰 규모로 확장할 수 있는 실질적인 경로임을 보여주었습니다.
하드웨어 친화적 설계: 큐비트의 개수를 늘리는 것보다, 각 단위 시스템의 차원(Dimension)을 높이는 큐디트 방식이 제약 조건이 많은 문제 해결에 훨씬 유리함을 확인했습니다.
향후 방향 제시: 향후 트랩 이온(Trapped Ion)이나 광자(Photonic) 기반의 큐디트 하드웨어에서 이 알고리즘을 구현할 경우, 실질적인 양자 이득(Quantum Advantage)을 얻을 가능성이 높음을 시사합니다.