Quantum optimization beyond QUBO for industrial logistics and scheduling

본 논문은 산업 물류 및 스케줄링을 위한 고차 비제약 이진 최적화 (HUBO) 형식을 조사하여, 표준 QUBO 모델에 비해 더 컴팩트한 이진 인코딩과 감소된 큐비트 요구 사항을 제공하지만 현재 하드웨어에서의 실제 구현은 증가된 회로 깊이로 인해 제한받음을 보여주며, 이는 하이브리드 양자 - 고전 워크플로우와 초기 오류 허용 시스템이 가장 실현 가능한 향후 방향임을 시사한다.

핵심

거대한 복잡한 퍼즐을 풀려고 한다고 상상해 보세요. 산업 물류 세계—수천 개의 택배를 어떻게 배송할지, 또는 공장 라인에서 자동차를 어떻게 조립할지 파악하는 것과 같은—에서 이 퍼즐은 극도로 어렵습니다. 오랫동안 과학자들은 일반 컴퓨터보다 이 퍼즐을 더 빠르게 풀기 위해 양자 컴퓨터를 사용해 왔습니다.

하지만 함정이 하나 있습니다: 오늘날 대부분의 양자 컴퓨터는 "네모난 말뚝"을 "둥근 구멍"에 끼우려는 것과 같습니다. 이들은 QUBO(2 차 무제약 이진 최적화)라는 특정한 단순한 언어로 작성된 문제를 풀도록 설계되었습니다. QUBO 는 두 가지 사물 간의 관계만 한 번에 설명할 수 있는 언어라고 생각하세요 (예: "A 가 여기에 있으면 B 는 반드시 저기에 있어야 한다").

하지만 현실 세계의 문제는 복잡합니다. 종종 세 개, 네 개, 또는 그 이상의 사물이 동시에 서로 의존하는 복잡한 규칙을 포함합니다. 이러한 복잡한 규칙을 단순한 "한 번에 두 개"의 QUBO 언어로 억지로 끼워 넣는 것은 두 음표의 쌍만 이야기하며 교향곡을 설명하려는 것과 같습니다. 작동은 하지만, 음악을 너무 많이 분해해야 하므로 퍼즐이 거대해져 양자 컴퓨터가 사용할 수 있는 조각 (큐비트) 수보다 더 많은 조각이 필요하게 됩니다.

새로운 접근법: "네이티브" 언어로 말하기

이 논문은 다른 전략을 제안합니다. 복잡한 문제를 단순한 QUBO 언어로 억지로 끼워 넣는 대신, 연구자들은 HUBO(고차 무제약 이진 최적화)를 사용할 것을 제안합니다.

비유:
여행 가방을 싸는 상황을 상상해 보세요.

• QUBO 방식: 모든 단일 품목 쌍에 대해 서로 맞는지 확인하기 위해 메모를 작성해야 합니다. 100 개의 품목이 있다면 수천 개의 메모를 작성해야 합니다. 이는 많은 공간 (메모리/큐비트) 을 차지합니다.
• HUBO 방식: "이 다섯 개의 품목은 완벽하게 어울린다"라고 말하는 단일하지만 약간 더 복잡한 메모를 작성합니다. 이는 훨씬 더 간결합니다. 같은 여행 가방을 설명하기 위해 훨씬 적은 수의 메모 (적은 수의 큐비트) 가 필요합니다.

연구자들은 이 "HUBO" 접근법을 세 가지 실제 산업 시나리오에 적용했습니다:

1. **바람막이와 서퍼 **(QUEST) 연료를 절약하기 위해 한 자동차가 다른 자동차 뒤에 따라가도록 고속도로를 주행하는 자동차들을 매칭하는 것.
2. **배송 트럭 **(CVRP) 제한된 화물 공간으로 많은 고객에게 물품을 배송하기 위해 트럭 함대의 최적 경로를 파악하는 것.
3. 자동차 조립 라인: 병목 현상을 피하기 위해 선루프, 가죽 시트 등 다양한 옵션이 있는 자동차들이 라인에서 지나가야 할 순서를 결정하는 것.

트레이드오프: 공간 절약 vs. 더 높은 탑 건설

이 논문은 넓은 평평한 건물과 가늘고 높은 마천루 사이를 선택하는 것과 같은 중요한 트레이드오프를 강조합니다.

• **이익 **(적은 수의 큐비트) HUBO 를 사용하여 연구자들은 퍼즐의 크기를 성공적으로 줄였습니다. 문제를 표현하는 데 훨씬 적은 "양자 비트"(큐비트) 가 필요했습니다. 이는 현재 양자 컴퓨터가 매우 작고 큐비트 수가 매우 적기 때문에 매우 좋습니다.
• **비용 **(깊은 회로) 하지만 그 "단일 복잡한 메모"를 작동시키기 위해 양자 컴퓨터는 훨씬 더 복잡한 춤을 추어야 합니다. 양자 용어로 이는 "회로 깊이"(컴퓨터가 취해야 하는 단계 수) 가 훨씬 깊어짐을 의미합니다.

은유:
양자 컴퓨터를 줄타기 예술가로 생각하세요.

• QUBO는 짧고 넓은 줄입니다. 균형을 잡기 쉽지만, 다른 쪽으로 가기 위해서는 매우 긴 줄 (많은 수의 큐비트) 이 필요합니다.
• HUBO는 매우 짧고 좁은 줄입니다. 매우 적은 줄 (적은 수의 큐비트) 이 필요하지만, 복잡하고 고속의 움직임 (깊은 회로) 을 요구하기 때문에 균형을 잡는 것이 극도로 어렵습니다.

결과가 보여주는 것

연구자들은 HUBO 접근법이 얼마나 잘 작동하는지 보기 위해 시뮬레이션과 고전 컴퓨터를 사용하여 이러한 아이디어를 테스트했습니다.

1. **작동함 **(이론적으로) 작은 문제의 경우, HUBO 방법은 최선의 해결책을 성공적으로 찾았습니다. 이는 필요한 "재료"(큐비트) 의 수 측면에서 이러한 복잡한 물류 문제를 훨씬 더 효율적으로 설명할 수 있음을 증명했습니다.
2. 하드웨어 병목 현상: 문제는 현재 양자 컴퓨터가 "잡음"이 많다는 것입니다. 이는 허리케인 속에서 균형을 잡으려 하는 줄타기 예술가와 같습니다. HUBO 방법은 더 길고 복잡한 단계 시퀀스 (더 깊은 회로) 를 필요로 하기 때문에, 잡음으로 인해 컴퓨터가 퍼즐을 풀기 전에 균형을 잃게 됩니다.
3. 판단:
   • **오늘 **(잡음 시대) "높은 탑"(HUBO) 은 현재 하드웨어에는 너무 불안정합니다. "넓은 건물"(QUBO) 은 더 많은 공간을 차지하지만, 실제로는 지금 구축하기가 더 쉽습니다.
   • **내일 **(오류 수정 시대) 이 논문은 우리가 더 나은 오류 수정 양자 컴퓨터 ("오류 허용" 영역) 를 갖게 되면 HUBO 접근법이 승리할 것이라고 제안합니다. 이러한 미래 기계는 HUBO 가 요구하는 복잡하고 깊은 회로를 처리할 만큼 충분히 안정적이 되어, 더 적은 수의 큐비트로 훨씬 더 큰 문제를 풀 수 있게 될 것입니다.

하이브리드 솔루션

완벽한 미래 컴퓨터를 기다릴 수 없기 때문에, 이 논문은 가까운 장래를 위한 "하이브리드" 접근법을 제안합니다. 거대한 퍼즐 전체를 양자 컴퓨터에서 한 번에 풀려고 하는 대신, 퍼즐을 작고 관리 가능한 조각으로 나눕니다. 고전 컴퓨터로 큰 그림과 쉬운 부분을 처리하고, 작고 어려운 조각만 양자 컴퓨터에 보내 정제합니다.

요약하자면:
이 논문은 "간결한" HUBO 언어가 복잡한 산업 물류를 설명하는 가장 효율적인 방법이지만, 현재 양자 컴퓨터는 그것이 요구하는 복잡성을 처리하기에 너무 약하다고 주장합니다. 우리는 더 나은 하드웨어를 기다리거나 이 강력한 방법을 실용화하기 위해 고전 컴퓨팅과 양자 컴퓨팅을 혼합해야 합니다.

기술 요약

기술 요약: 산업 물류 및 스케줄링을 위한 QUBO 를 넘어선 양자 최적화

문제 제기
산업 스케줄링 및 운송 경로 문제는 점점 더 복잡해지고 있으며, 종종 2 차가 아닌 고차 이진 최적화 (HUBO) 형식으로 이어지는 자연스러운 수학적 구조를 지닙니다. 양자 최적화 분야는 이징 해밀토니안 (Ising Hamiltonians) 에 대한 네이티브 매핑과 현재 양자 어닐러와의 호환성으로 인해 주로 2 차 무제약 이진 최적화 (QUBO) 에 초점을 맞춰 왔으나, 이러한 초점은 상당한 한계를 부과합니다. 보조 변수를 통해 HUBO 문제를 QUBO 로 축소하는 것은 종종 문제 크기 (큐비트 수) 를 비대하게 만들고, 주요 의존 관계를 흐리게 하며, 정교한 운영 제약을 충실히 반영하지 못합니다. 반면, 양자 근사 최적화 알고리즘 (QAOA) 과 같은 디지털 양자 알고리즘은 이론적으로 고차 상호작용을 처리할 수 있지만, 잡음이 있는 하드웨어에서의 근미래 구현은 상호작용 차수가 증가함에 따라 종종 깊이 제한을 받습니다. 본 논문은 HUBO 형식의 표현적 간결성과 현재 및 신흥 양자 하드웨어에서의 구현 비용 간의 트레이드오프를 조사합니다.

방법론
저자들은 세 가지 대표적인 산업 사용 사례에 대한 HUBO 형식을 제안하고 분석합니다:

1. QUEST(양자 강화 공유 교통): 공기 저항 및 시간/속도 불일치를 최소화하기 위해 '브레이커 (breakers)'와 '서퍼 (surfers)'를 매칭하는 차량 매칭 문제.
2. CVRP(용량 제한 차량 경로 문제): 외판원 문제를 확장한 용량 제약이 있는 함대 경로 문제.
3. 자동차 조립 스케줄링: 조립 라인에서 갭, 그룹, 저장 차선 제약을 포함하는 자동차 시퀀싱 문제.

각 사용 사례에 대해 저자들은 표준 원-핫 인코딩 (선형 스케일링) 대신 컴팩트 이진 인코딩 (변수에서의 로그 스케일링) 을 사용하여 문제를 HUBO 로 재형식화합니다. 이러한 형식은 시뮬레이션 어닐링 (SA) 및 메메틱 타부 서치 (MTS) 를 포함한 고전 솔버를 사용하여 검증되었으며, 정수 선형 계획법 (ILP) 및 브루트포스 솔루션과 비교 평가되었습니다.

양자 실현 가능성을 평가하기 위해 저자들은 Bias-Field Digitized Counterdiabatic Quantum Optimization (BF-DCQO) 알고리즘을 사용합니다. 이 프로토콜은 이전 측정 결과에서 파생된 종방향 편향 장을 사용하여 시스템을 더 낮은 에너지 구성으로 유도하는 반복적 피드백 메커니즘을 도입함으로써 표준 DCQO 를 확장합니다. 저자들은 다양한 하드웨어 연결 가정 (all-to-all, heavy-hex, square-lattice) 및 잡음 모델 하에서 자원 요구 사항 (큐비트 수, 2 큐비트 게이트 수, 회로 깊이) 및 회로 충실도를 추정합니다.

주요 기여

• HUBO 모델의 형식화: 본 논문은 QUEST, CVRP 및 자동차 스케줄링에 대한 명시적인 HUBO 형식을 제공하여, 컴팩트 이진 인코딩이 이진 변수의 수를 $O(N)$ 또는 $O(N^2)$에서 $O(N \log N)$으로 줄이는 방식을 보여줍니다.
• 트레이드오프 분석: 이 작업은 HUBO 형식이 큐비트 요구 사항 (큐비트 스케일링) 을 크게 줄이지만, 더 깊은 회로와 더 많은 2 큐비트 게이트가 필요한 고차 상호작용 항을 도입한다는 중심 트레이드오프를 체계적으로 강조합니다.
• 자원 및 확장성 분석: 저자들은 BF-DCQO 에 대한 회로 충실도 및 런타임에 대한 상세한 추정을 제공합니다. HUBO 가 큐비트 발자국을 줄이지만, 증가하는 2 큐비트 게이트 수에 따른 회로 충실도의 지수적 감쇠가 현재 잡음이 있는 중규모 양자 (NISQ) 장치에 대한 결정적인 병목 현상을 초래함을 보여줍니다.
• 하이브리드 워크플로우 제안: 전체 양자 실행이 불가능한 대규모 사례 (예: 자동차 스케줄링) 에 대해, 본 논문은 하이브리드 롤링 호라이즌 워크플로우를 제안하고 평가합니다. 이 접근법은 전역 문제를 고전 또는 근미래 양자 솔버로 해결 가능한 국소 하위 문제로 분해하면서도 전체 목적 함수의 고차 구조를 유지합니다.

결과

• QUEST 및 CVRP 검증: 작은 사례 (QUEST 의 경우 최대 6 개의 브레이커/서퍼 및 작은 CVRP 사례) 에 대해 BF-DCQO 시뮬레이션은 최적 해를 복원하여 HUBO 인코딩을 검증합니다. 그러나 문제 크기가 증가함에 따라 BF-DCQO 의 근사 비율은 2 차화된 HUBO 에 대한 고전 시뮬레이션 어닐링보다 더 빠르게 저하되며, 이는 회로 복잡성의 급격한 증가와 일치합니다.
• 하드웨어 제약: 분석에 따르면 현재 하드웨어 (예: IBM heavy-hex 또는 square-lattice) 의 경우, 더 많은 큐비트가 필요함에도 불구하고 더 낮은 2 큐비트 게이트 수로 인해 QUBO 인코딩이 종종 더 실현 가능합니다. HUBO 형식은 all-to-all 연결성을 가진 아키텍처 (예: 트랩드 이온) 에서만 게이트 수 측면에서 경쟁력이 있으며, coherence 시간과 오류 누적으로 인해 매우 작은 사례 (예: CVRP 의 4 명의 고객) 로만 제한됩니다.
• 확장성 한계: 대표적인 대규모 CVRP 사례 (100 명의 고객) 의 경우, 저자들은 충실한 DCQO 회로 구현이 평균 2 큐비트 게이트 오류율을 $10^{-10}$ 미만으로 요구할 것으로 추정하며, 이는 양자 오류 정정에 의해 가능해지는 논리 큐비트 영역에서만 달성 가능한 수준입니다.
• 스케줄링 성능: 자동차 스케줄링 사례에서 고전 솔버 (MTS 및 ILP) 는 HUBO 형식을 벤치마킹하는 데 사용되었습니다. MTS 는 FIFO(선입선출) 위반을 효과적으로 줄였으나 문제 크기가 커짐에 따라 고차 그룹 제약에 어려움을 겪었습니다. SA 를 사용한 하이브리드 롤링 호라이즌 접근법은 국소 및 전역 위반 모두를 균형 있게 감소시켰습니다.

의의 및 주장
본 논문은 산업 규모 사례에서 양자 우위를 입증하는 것이 아니라, 언제 고차 형식이 의미 있는 표현적 이점을 제공하는지 그리고 그 이점이 양자 자원 요구 사항에 의해 어떻게 제한되는지를 명확히 하는 것이 주요 기여라고 겸손하게 주장합니다.

저자들은 다음과 같이 결론 내립니다:

1. HUBO 대 QUBO: HUBO 형식은 우수한 큐비트 스케일링을 제공하여, 큐비트 수는 제한되지만 게이트 충실도가 높은 초기 오류 허용 환경에서 QUBO 보다 잠재적으로 더 매력적일 수 있습니다.
2. 현재 한계: 현재 NISQ 하드웨어에서의 실용적 구현은 게이트 충실도, coherence 시간, 회로 깊이에 의해 제한됩니다. HUBO 의 증가된 2 큐비트 게이트 요구 사항은 현존하는 장치에서 감소된 큐비트 수의 이점을 종종 상쇄합니다.
3. 미래 경로: 이러한 형식의 실용적 사용에 대한 가장 그럴듯한 시나리오는 순차적 하이브리드 양자 - 고전 워크플로우입니다. 이 패러다임에서 양자 루틴은 주로 고전 최적화 파이프라인 내의 국소 하위 문제에 대한 정제 단계로 작용합니다. 이 접근법은 HUBO 의 유리한 큐비트 스케일링을 활용하면서도, 초기 오류 허용 영역에서도 전체 양자 최적화와 관련된 금지적인 런타임 및 오류 누적을 완화합니다.

이 작업은 산업 내 양자 최적화의 실현 가능성은 문제 구조와 하드웨어 능력을 정렬하는 데 달려 있으며, 이론적 HUBO 이점과 실용적 구현 간의 격차를 해소하기 위해 하이브리드 전략이 필수적임을 강조합니다.