Resource-Efficient Quantum Optimization via Higher-Order Encoding

본 논문은 고차 비제약 이진 최적화(HUBO)가 조합 최적화 문제에 대해 전통적인 QUBO 정식화보다 큐비트 및 CNOT 게이트 수를 실질적으로 감소시키면서도 훨씬 더 자원 효율적인 대안을 제공함을 입증하며, 근미래 양자 장치에서의 도입을 촉진하기 위한 오픈 소스 라이브러리를 제공한다.

핵심

당신이 거대하고 복잡한 퍼즐을 풀려고 노력하고 있다고 상상해 보십시오. 양자 컴퓨팅의 세계에서 이 퍼즐은 **조합 최적화 문제(Combinatorial Optimization Problem)**라고 불립니다. 이것은 마치 비행기를 공항 게이트에 배정하는 완벽한 방법, 인접한 국가가 같은 색이 되지 않도록 지도를 색칠하는 방법, 또는 비용을 절감하기 위해 공장의 생산 라인을 스케줄링하는 방법을 찾아내는 것과 같습니다.

오랫동안 과학자들은 QUBO(Quadratic Unconstrained Binary Optimization, 이차 무제약 이진 최적화)라고 불리는 특정 방식을 사용하여 이 퍼즐을 풀기 위해 노력해 왔습니다. QUBO를 당신의 퍼즐을 양자 컴퓨터가 이해할 수 있는 언어로 번역하는 매우 엄격하고 경직된 방식이라고 생각하십시오.

기존 방식(QUBO)의 문제점

이 논문은 QUBO 방식이 마치 모든 물건을 각각의 커다란 개별 상자에 억지로 집어넣어 여행 가방을 싸는 것과 같다고 주장합니다.

• 너무 많은 상자 (큐비트): 만약 하나의 변수가 10개의 서로 다른 값(예: 10개의 서로 다른 공항 게이트)을 가질 수 있다면, QUBO는 그 하나의 선택을 표현하기 위해 10개의 별도 "상자"(양자 비트 또는 큐비트)를 사용하도록 강제합니다.
• 너무 많은 접착제 (패널티 항): 컴퓨터가 한 번에 두 개의 상자를 선택하는 실수(잘못된 선택)를 하지 않도록 하기 위해, 당신은 "패널티 항"이라는 무거운 "접착제"를 추가해야 합니다. 이 접착제는 명령어(양자 회로)를 믿기 힘들 정도로 길고 복잡하게 만듭니다.
• 결과: 양자 컴퓨터는 과부하에 걸립니다. 문제가 그리 크지 않음에도 불구하고, 이를 해결하기 위해 너무 많은 부품(큐비트)과 너무 많은 복잡한 움직임(게이트)을 필요로 하게 됩니다.

새로운 솔루션: HUBO

이 논문의 저자들은 HUBO(Higher-Order Unconstrained Binary Optimization, 고차 무제약 이진 최적화)라고 불리는 더 똑똑한 방법을 소개합니다.

HUBO를 동일한 여행 가방을 싸되 압축 백을 사용하는 것이라고 생각해 보십시오. 모든 물건에 각각 커다란 상자를 주는 대신, 선택지를 나타내기 위해 압축된 이진 코드(디지털 압축 파일과 같은)를 사용합니다.

• 더 적은 상자: 10개의 옵션이 있다면, HUBO는 10개의 상자가 필요하지 않습니다. (왜냐하면 $2^4 = 16$이므로 10을 커버할 수 있기 때문입니다.) 이는 컴퓨터의 자연스러운 "이진" 언어를 훨씬 더 효율적으로 사용합니다.
• 추가적인 접착제 없음: 인코딩이 매우 스마트하기 때문에, 컴퓨터는 자연스럽게 한 번에 하나의 값만 선택할 수 있다는 것을 이해합니다. 실수를 막기 위해 그 무겁고 비싼 패널티 항을 추가할 필요가 없습니다.
• 결과: 명령어는 훨씬 짧아지고, 양자 컴퓨터는 작업을 수행하는 데 훨씬 적은 부품을 필요로 합니다.

그들이 실제로 한 일

연구진은 단순히 말로만 설명한 것이 아니라, 세 가지 실제 유형의 퍼즐을 통해 HUBO를 테스트했습니다:

1. 게이트 배정 (GAP): 승객의 도보 시간을 최소화하기 위해 비행기를 공항 게이트에 배정하는 문제.
2. 그래프 채색 (MkCS): 인접한 영역이 같은 색을 공유하지 않도록 지도를 색칠하는 문제.
3. 정수 계획법 (IP): 자원을 최적화하기 위한 일반적인 수학 문제.

그들은 인기 있는 양자 알고리즘인 QAOA를 사용하여 기존의 "QUBO" 방식과 새로운 "HUBO" 방식을 비교했습니다.

결과: 압도적인 승리

결과는 극적이었습니다. HUBO로 전환함으로써:

• 더 적은 부품 필요: 훨씬 더 적은 수의 큐비트(컴퓨터의 기본 구성 요소)가 필요했습니다.
• 획기적으로 적은 움직임: 가장 중요한 발견은 "CNOT 게이트"(양자 컴퓨터가 수행해야 하는 특정 유형의 움직임)의 수였습니다. HUBO 방식은 모든 테스트에서 CNOT 게이트의 수를 최소 89.6% 이상 줄였습니다. 어떤 경우에는 거의 100%에 가까운 감소를 보였습니다.
• 더 나은 솔루션: 실행 비용이 저렴해졌을 뿐만 아니라, HUBO 방식은 두 방식 모두에게 동일한 시간을 주었을 때 QUBO 방식보다 더 나은 정답을 찾아냈습니다.

시사점

이 논문은 현재의 양자 컴퓨터(그리고 곧 다가올 양자 컴퓨터들)를 위해 기존의 QUBO 방식은 너무 무겁고 낭비적이라고 결론짓습니다. 새로운 HUBO 방식은 현재의 하드웨어에 더 잘 맞는 "경량화된" 대안입니다.

다른 사람들이 이를 사용할 수 있도록, 저자들은 이러한 복잡한 문제들을 효율적인 HUBO 형식으로 자동 변환해 주는 무료 오픈 소스 소프트웨어 도구(PyHUBO라는 이름의 파이썬 라이库러리)를 함께 공개하여, 다른 과학자와 엔지니어들이 이 자원 절약형 방법을 즉시 사용할 수 있도록 했습니다.

요약하자면: 그들은 복잡한 퍼즐을 풀기 위한 양자 명령어를 축소하는 방법을 찾아냈으며, 이를 통해 오늘날의 양자 컴퓨터로 실제 세상의 문제들을 실제로 해결할 가능성을 높였습니다.

기술 요약

기술 요약: 고차 인코딩을 통한 자원 효율적 양자 최적화

문제 정의
조합 최적화 문제(Combinatorial Optimization Problems, COPs)는 물류에서 계산 생물학에 이르기까지 다양한 분야의 핵심이지만, 종종 NP-난해(NP-hard) 특성을 지니고 있어 문제 규모가 커짐에 따라 고전적 솔버로는 계산이 불가능해지는 경우가 많습니다. 양자 알고리즘, 특히 양자 근사 최적화 알고리즘(QAOA)은 이러한 과제를 해결할 수 있는 잠재적인 경로를 제공합니다. 그러나 현재의 양자 접근 방식은 이차 무제약 이진 최적화(Quadratic Unconstrained Binary Optimization, QUBO) 정식화의 자원 요구 사항으로 인해 빈번하게 병목 현상이 발생합니다. One-Hot 인코딩과 같은 표준 QUBO 인코딩은 변수의 개수($n$)와 변수당 가능한 값의 개수($m$) 모두에 선형적인 수의 큐비트를 요구하여 $n \times m$개의 큐비트가 필요합니다. 또한, QUBO에서 제약 조건을 강제하기 위해서는 대규모 페널티 항이 필요한데, 이는 회로 깊이와 2-큐비트 CNOT 게이트의 수를 증가시켜 많은 실질적인 문제들을 근미래 양자 하드웨어에서 실행 불가능하게 만듭니다.

방법론
저자들은 이러한 자원 제약을 완화하기 위해 고차 무제약 이진 최적화(Higher-Order Unconstrained Binary Optimization, HUBO)를 활용하는 체계적인 프레임워크를 제안합니다. 이 방법론은 세 가지 주요 구성 요소로 이루어집니다:

1. 이진 인코딩(Binary Encoding) 대 원핫 인코딩(One-Hot Encoding): 각 변수-값 쌍을 별도의 큐비트로 사용하는 One-Hot 인코딩 대신, 저자들은 이진 인코딩을 채택합니다. 여기서 각 변수 $i$는 $d = \lceil \log_2(m) \rceil$ 비트의 압축된 이진 레지스터로 표현됩니다. 이는 큐비트 요구량을 $n \times m$에서 $n \times \lceil \log_2(m) \rceil$로 줄여줍니다.
2. HUBO 해밀토니안 구축: 저자들은 이러한 이진 인코딩이 자연스럽게 최대 $2 \times d$ 차의 고차 상호작용 항을 포함하는 HUBO 해밀토니안으로 이어진다는 것을 보여줍니다. "원핫" 제약 조건(변수가 단 하나의 값만을 가져야 함)을 강제하기 위해 페널티 항이 필요한 QUBO와 달리, 이진 인코딩은 단일 값 할당을 본질적으로 준수합니다. 제약 조건(예: $s_i \neq s_j$)은 해밀토니안에 직접 포함되거나 변수 공간을 확장할 필요가 없는 페널티 항을 통해 통합됩니다.
3. 회로 컴파일: 고차 항은 형식적으로 다중 큐비트 상호작용을 의미하지만, 저자들은 이를 표준 단일 및 2-큐비트 게이트로 완전히 컴파일할 수 있음을 보여줍니다. 저자들은 비용 유니터리(cost unitary) $e^{-i\gamma \hat{H}_C}$를 구현하기 위해 Gray-code 기반 회로 합성(Welch 등의 방식)을 활용합니다. 이 접근 방식은 한 항을 위해 생성된 패리티 상태를 다른 항을 구축하는 데 활용함으로써 중복 연산을 최소화하며, 이를 통해 점근적 CNOT 게이트 수가 $O(n^2 m^2)$로 스케일링되어 QUBO와 유사하면서도 실제로는 훨씬 낮은 상수 계수를 유지하도록 보장합니다.

또한 저자들은 Walsh-Hadamard 변환을 사용하여 HUBO 해밀토니안을 자동 구축하고 계수를 계산하는 오픈 소스 파이썬 라이브러리인 PyHUBO를 소개합니다. 이는 수치적 복잡도가 문제 크기에 따라 다항식 수준으로 스케일링되도록 보장합니다.

주요 기여

• 체계적 프레임워크: One-hot 또는 관련 제약이 있는 문제를 HUBO 해밀토니안으로 매핑하는 일반적인 방법론을 제시하며, 이는 다양한 문제에 적용 가능합니다.
• 자원 감소: HUBO 정식화가 큐비트 수를 크게 줄이고, 결정적으로 QAOA 실행에 필요한 총 CNOT 게이트 수를 줄인다는 것을 입증했습니다.
• 소프트웨어 도구: 양자 커뮤니티의 HUBO 모델 채택을 촉진하기 위해 PyHUBO를 공개했습니다.
• 벤치마킹: 세 가지 뚜렷한 COP 클래스인 게이트 할당 문제(GAP), 최대 k-색 가능 부분 그래프(MkCS), 정수 계획법(IP)에 대한 포괄적인 평가를 수행했습니다.

결과
저자들은 세 가지 선택된 문제 클래스에 대해 QUBO와 HUBO 인코딩을 모두 사용하여 QAOA를 벤치마킹했습니다. 결과는 HUBO의 상당한 자원 절감을 나타냅니다:

• 큐비트 효율성: HUBO는 큐비트 요구량을 $O(nm)$에서$O(n \log m)$으로 줄입니다.
• 게이트 수 감소: 테스트된 모든 사례에서 HUBO는 총 CNOT 게이트 수를 최소 89.6% 감소시켰습니다. 정수 계획법(IP) 벤치마크와 같은 특정 사례에서는 감소 폭이 최대 **97.1%**에 달했습니다.
• 솔루션 품질: 고정된 QAOA 레이어 수에 대해, HUBO-QAOA는 QUBO-QAOA보다 일관되게 더 나은 근사 비율(최적해에 더 가까운 값)을 달로했습니다. 예를 들어, GAP 벤치마크에서 HUBO는 평균 목적 함수 값 12.1분을 기록하여 QUBO의 15.8분보다 우수한 성능을 보였습니다.
• 수렴성: HUBO-QAOA는 훨씬 적은 총 게이트로 목표 근사 비율에 도달했습니다. IP 벤치마크에서 HUBO는 1개 레이어만으로 0.60의 목표 비율에 도달한 반면, QUBO는 10개 레이어가 필요했으며, 결과적으로 QUBO는 31.6배 더 많은 CNOT 게이트와 24.5배 더 많은 RZ 게이트를 소비했습니다.
• 확장성: HUBO의 자원 이점은 문제 규모가 커짐에 따라 지속되었으며 종종 더 증가했습니다. HUBO는 과도한 자원 요구량으로 인해 QUBO-QAOA가 계산적으로 불가능해지는 문제 규모에서도 실행 가능성을 유지했습니다.

의의
본 논문은 HUBO 정식화가 근미래 장치에서의 양자 최적화를 위한 실질적인 대안을 제공한다고 주장합니다. 고차 상호작용이 하드웨어 요구 사항을 증가시킬 것이라는 직관과는 반대로, 저자들은 페널티 항의 제거와 변수 표현의 압축이 순적인 회로 복잡도의 감소를 이끌어낸다는 것을 보여줍니다. 큐비트 및 CNOT 요구량을 크게 낮춤으로써, HUBO 인코딩은 현재 실질적인 산업 문제에 양자 알고리즘을 적용하는 데 제약이 되는 자원 병목 현상을 완화하는 데 도움을 줍니다. 저자들은 양자 기술이 발전하고 문제 규모가 확장됨에 따라 이러한 자원 효율적인 방법이 점점 더 필수적이 될 것이며, 이를 통해 산업 및 연구 분야에서 더욱 실현 가능한 응용을 가능하게 할 것이라고 결론짓습니다.