Qubit-efficient and gate-efficient encodings of graph partitioning problems for quantum optimization

이 논문은 그래프 분할 문제의 최적화 버전을 양자 환경에서 해결하기 위해 $\lceil \log_2 k \rceil$ 비트를 사용하는 새로운 효율적인 인코딩 기법을 제안하고, 이를 통해 큐비트 및 게이트 수를 줄이면서도 기존 원-핫 (one-hot) 인코딩 대비 더 우수한 해의 품질과 시간 효율성을 입증했습니다.

핵심

이 논문은 **"양자 컴퓨터로 복잡한 문제를 풀 때, 자원을 얼마나 아낄 수 있을까?"**에 대한 획기적인 해결책을 제시합니다.

비유를 들어 설명하면, 이 논문은 **"양자 컴퓨터라는 좁은 주차장에 수많은 차 (문제) 를 주차시키는 방법"**을 연구한 것입니다.

1. 문제 상황: 주차장이 너무 좁아요 (양자 비트의 부족)

우리가 양자 컴퓨터로 '그래프 분할'이나 '지도 그리기 (그래프 색칠하기)' 같은 복잡한 문제를 풀려고 할 때, 가장 큰 걸림돌은 양자 비트 (qubit) 라는 주차 공간이 너무 부족하다는 점입니다.

• 기존 방법 (원-핫 인코딩):
  예전에 우리는 10 가지 색을 표현할 때, 10 개의 주차 공간 (비트) 을 모두 준비했습니다. 1 번 색을 쓰려면 1 번 주차칸만 비우고 나머지는 모두 비워두는 식이죠.
  • 단점: 문제가 커질수록 (색이 많아질수록) 필요한 주차 공간이 기하급수적으로 늘어납니다. 양자 컴퓨터는 공간이 매우 비싸기 때문에, 큰 문제는 아예 주차할 수 없게 됩니다.

2. 새로운 해결책: 이진법으로 주차하기 (로그arithmic 인코딩)

이 논문은 **"왜 10 개의 주차칸을 다 쓸까? 10 을 표현하는 데는 4 개의 칸 (이진법: 1010) 만 있으면 되지 않나?"**라고 질문합니다.

저희가 제안한 방법은 로그arithmic 인코딩입니다.

• 비유: 100 개의 주차칸을 다 쓸 필요 없이, 이진법 (0 과 1) 을 이용해 숫자를 표현하면 훨씬 적은 공간으로 같은 수의 차를 주차할 수 있습니다.
• 효과: 100 개의 색을 표현하려면 기존에는 100 개의 비트가 필요했지만, 이新方法을 쓰면 약 7 개의 비트 (2^7 = 128) 만이면 됩니다. 공간 (비트) 사용량이 기하급수적으로 줄어듭니다.

3. 새로운 트릭: "순서대로 주차하세요" (사전식 페널티 시스템)

그런데 여기서 새로운 문제가 생깁니다. "색을 적게 쓰라"는 조건을 어떻게 넣을까요?
기존 방법은 "몇 개의 색을 썼는지"를 따로 세는 별도의 센서 (변수) 를 달아야 해서 공간이 더 낭비되었습니다.

이 논문은 매우 영리한 규칙을 만들었습니다.

• 비유: 주차장에 차를 주차할 때, **"1 번 주차칸부터 순서대로 채워야 한다"**는 규칙을 세운 것입니다.
  • 만약 1 번, 2 번, 3 번 칸에 차가 있고 4 번 칸은 비어있다면, 우리는 "3 개의 색만 썼다"고 자연스럽게 알 수 있습니다.
  • 만약 1 번 칸은 비어있고 3 번 칸에 차가 있다면, 그건 "불법 주차"로 간주하여 벌금을 매깁니다.
• 결과: 별도의 센서 없이도, 숫자 (색) 가 작을수록 우선순위가 높게 되도록 설계하여, 자연스럽게 가장 적은 수의 색만 쓰도록 유도합니다.

4. 실험 결과: 더 빠르고, 더 정확해요

이新方法을 실제 양자 컴퓨터 (D-WAVE) 에 적용해 본 결과:

• 속도: 같은 문제를 풀 때, 기존 방법보다 10 배에서 100 배까지 더 빠르게 정답을 찾았습니다.
• 규모: 문제가 커질수록 (차량이 많아질수록) 이新方法의 이점이 더 커졌습니다.
• 안정성: 주차칸 (비트) 들이 고르게 사용되어, 양자 컴퓨터가 오작동할 확률 (에러) 이 줄었습니다.

요약

이 논문은 **"복잡한 문제를 풀 때, 필요한 양자 컴퓨터의 자원을 획기적으로 줄이는 새로운 주차법 (인코딩)"**을 개발했습니다.

기존의 비효율적인 방식 (모든 주차칸 다 쓰기) 대신, **이진법과 지능적인 규칙 (순서대로 주차)**을 적용함으로써, 작은 양자 컴퓨터로도 훨씬 더 크고 복잡한 문제 (지도 그리기, 커뮤니티 찾기 등) 를 해결할 수 있는 길이 열렸습니다.

이는 양자 컴퓨터가 실용화되는 데 있어 가장 중요한 '효율성' 문제를 해결한 첫걸음이라고 할 수 있습니다.

기술 요약

이 논문은 **그래프 분할 문제 (Graph Partitioning Problems)**를 양자 최적화 알고리즘에 효율적으로 부호화하기 위한 새로운 방법을 제안합니다. 특히, **레이블 수 최소화 (label-count minimization)**가 목표인 문제들 (최소 그래프 채색, 최소 k-컷, 커뮤니티 탐지 등) 에 대해 **큐비트 효율성 (qubit-efficient)**과 **게이트 효율성 (gate-efficient)**을 동시에 달성하는 고차원 이진 최적화 (HUBO) 인코딩 기법을 개발했습니다.

다음은 논문의 주요 내용을 기술적으로 요약한 것입니다.

---

1. 문제 정의 및 배경 (Problem & Background)

• 배경: NP-난해한 조합 최적화 문제를 양자 컴퓨터로 해결하기 위해서는 문제를 양자 하드웨어 (큐비트) 에 적합한 형태로 인코딩해야 합니다. 기존에 가장 널리 쓰이는 방법은 **원-핫 인코딩 (One-hot encoding)**으로, $k$개의 가능한 레이블을 표현하기 위해 각 정점에 대해 $k$개의 큐비트를 사용합니다.
• 한계점:
  • 큐비트 과부하: 정점 수 $|V|$와 레이블 수 $k$에 비례하여 $O(|V| \cdot k)$개의 큐비트가 필요하여, 대규모 문제나 $k$가 큰 경우 하드웨어 제약에 직면합니다.
  • 게이트 복잡도: 원-핫 인코딩은 2-큐비트 게이트 (CNOT) 수가 $O(|V|k^2 + |E|k)$로 매우 많습니다.
  • 비실현 상태: 원-핫 인코딩은 많은 수의 비실현 상태 (infeasible states) 를 포함하며, 이를 제어하기 위해 정교한 페널티 파라미터 튜닝이 필요합니다.
  • 최적화 버전 부재: 기존 연구들은 주로 그래프 채색의 '결정 문제 (decision problem, $k$개의 색으로 가능한가?)'를 다뤘으며, '최적화 문제 (최소 색 수 찾기)'를 양자 환경에서 직접 해결하는 연구는 부족했습니다.

2. 제안된 방법론 (Methodology)

저자들은 **로그arithmic 인코딩 (Logarithmic Encoding)**을 기반으로 한 새로운 HUBO 형식을 제안했습니다.

A. 인코딩 전략

• 로그arithmic 비트 사용: 각 정점의 $k$-값 변수를 $\lceil \log_2 k \rceil$개의 비트로 인코딩합니다. 이는 정보 이론적 최소한의 큐비트 수를 사용합니다.
• 사전적 페널티 시스템 (Lexicographic Penalty System):
  • 단순히 레이블 수를 세는 별도의 지시 변수 (indicator variables) 를 도입하지 않고, 비트 문자열의 **사전적 순서 (lexicographic order)**를 통해 최소 분할 수를 자동으로 달성합니다.
  • 각 비트 위치 $k$에 대해 가중치 $P_k$를 부여하고, $P_1 < P_2 < \dots < P_L$이 되도록 설정합니다.
  • 이 구조는 해가 가능한 상태 내에서 더 작은 레이블 (더 낮은 비트 값) 을 선호하도록 강제하여, 결과적으로 사용된 레이블의 수를 최소화합니다.

B. 수학적 형식화 (HUBO Formulation)

최소 그래프 채색 (Minimum Graph Coloring) 을 예로 들면, 목적 함수는 다음과 같이 구성됩니다:
$$H_{MGC} = H_{adjacency} + H_{lexicographic}$$

• $H_{adjacency}$: 인접한 정점이 같은 비트 문자열 (같은 색) 을 가지지 않도록 하는 항 (고차원 상호작용 포함).
• $H_{lexicographic}$: 사용된 레이블 수를 최소화하기 위한 사전적 페널티 항.

C. 페널티 계수 조건 (Sufficient Conditions)

최저 에너지 해가 실현 가능하고 최적임을 보장하기 위해 모든 페널티 계수에 대한 이론적으로 충분한 조건을 유도했습니다.

• 원-핫 인코딩: $A_{link}, A_{adjacency}, A_{one-hot}$의 크기 관계에 대한 부등식 유도.
• 로그arithmic 인코딩: $P_k$ (사전적 가중치) 와 $A_{adjacency}$ (인접성 페널티) 간의 엄격한 부등식 유도.
  • 예: $P_{k+1} > |V| \cdot \sum_{j=1}^{k} P_j$
• 2 차원화 (Quadratization): 양자 어닐러나 QAOA 와 같은 2-차 상호작용만 지원하는 하드웨어를 위해 Rosenberg 기법을 사용하여 HUBO 를 QUBO 로 변환할 때 필요한 보조 변수 (auxiliary variables) 와 페널티 계수 조건도 제시했습니다.

3. 주요 기여 (Key Contributions)

1. 최초의 최적화 버전 양자 접근: 그래프 분할 문제의 '결정 문제'가 아닌 '최적화 문제 (최소 레이블 수 찾기)'를 양자 환경에서 해결한 최초의 연구입니다.
2. 새로운 인코딩 기법: 별도의 지시 변수 없이 사전적 페널티 시스템을 통해 레이블 수를 최소화하는 새로운 HUBO 구성을 제안했습니다.
3. 이론적 보장: Rosenberg 2 차원화를 포함한 모든 페널티 계수에 대한 엄밀한 충분 조건을 증명하여, 최저 에너지 해가 항상 실현 가능하고 최적임을 보장합니다.
4. 복잡도 분석:
   • 큐비트 수: 원-핫 인코딩 ($O(|V|k)$) 대비 로그arithmic 인코딩 ($O(|V|\log k)$) 으로 지수적 감소.
   • 게이트 수 (CNOT): 원-핫 인코딩 ($\Theta(|V|k^2 + |E|k)$) 대비 로그arithmic 인코딩 ($\Theta(|E| \cdot k \log k)$) 으로 대폭 감소. 특히 희소 그래프에서 게이트 수 감소 효과가 극대화됩니다.

4. 실험 결과 (Benchmarking Results)

D-WAVE Advantage2_1.11 양자 어닐러를 사용하여 350 개의 무작위 연결 그래프에 대해 원-핫 인코딩과 제안된 로그arithmic 인코딩을 비교했습니다.

• 해결 시간 (Time-to-Solution, TTS):
  • 정점 수 $|V|$가 증가함에 따라 로그arithmic 인코딩이 원-핫 인코딩보다 1~2 차수 (orders of magnitude) 더 빠른 해결 시간을 보였습니다.
  • 문제 크기가 커질수록 성능 격차가 더욱 벌어졌습니다.
• 큐비트 및 체인 길이 (Chain Length):
  • 2 차원화 후 논리 큐비트 수는 그래프 밀도에 따라 원-핫보다 많을 수도 있으나, 물리적 큐비트 수는 두 방식이 비슷했습니다.
  • 핵심 발견: 로그arithmic 인코딩은 **체인 길이의 분산 (variance)**이 원-핫 인코딩보다 현저히 낮았습니다.
  • 의미: 체인 길이가 균일하면 어닐링 과정에서 사슬 끊김 (chain breaks) 이 줄어들고, 전역 체인 강도 (chain strength) 설정이 최적화되어 문제의 충실도 (fidelity) 가 유지됩니다. 이는 물리적 큐비트 수 감소보다 체인 길이의 균일성이 TTS 개선의 주요 동인이었음을 시사합니다.

5. 의의 및 결론 (Significance)

• 확장성: 제안된 프레임워크는 최소 그래프 채색뿐만 아니라 최소 k-컷, 커뮤니티 탐지 등 레이블 대칭성과 분할 수 최소화가 필요한 광범위한 그래프 분할 문제에 적용 가능합니다.
• 하드웨어 호환성: 양자 어닐링 (QA), QAOA, VQE 등 다양한 양자 최적화 알고리즘 및 하드웨어에 적용 가능합니다.
• 실용적 가치: 현재의 제한된 양자 하드웨어 (Noisy Intermediate-Scale Quantum, NISQ) 환경에서 대규모 조합 최적화 문제를 해결하기 위한 큐비트 및 게이트 효율적인 인코딩의 표준을 제시했습니다.

요약하자면, 이 논문은 로그arithmic 인코딩과 사전적 페널티 시스템을 결합하여 그래프 분할 최적화 문제를 해결함으로써, 기존 원-핫 인코딩의 한계를 극복하고 양자 하드웨어에서 더 빠른 해결 시간과 더 높은 해의 품질을 달성할 수 있음을 이론적 증명과 실험을 통해 입증했습니다.