Comparing Qubit and Qudit Encodings for EV Charging and Trip Assignment Problems

본 논문은 가변 양자 알고리즘에 대해 기존의 큐비트(이진) 인코딩 대신 qudit(정수) 인코딩을 사용할 경우 현실적인 전기차 차량대대 관리 문제에서 동등하거나 우수한 최적화 성능을 달성하면서도 자원 요구사항과 시뮬레이션 실행 시간을 크게 줄일 수 있음을 보여준다.

핵심

작은 규모의 전기 택시 함대의 관리자가 되어 보십시오. 매일 당신은 두 가지 큰 업무를 수행해야 합니다:

1. 차량 충전: 비용을 절감하기 위해 언제 차량을 플러그에 연결해 충전하거나, 전력을 그리드 (전력망) 로 되돌려 보내야 할지 결정해야 합니다.
2. 여행 배정: 어떤 차량이 어떤 고객의 여행을 담당할지 결정해야 합니다.

이것은 퍼즐입니다. 잘못된 차량에 여행을 배정하거나 잘못된 시간에 충전하면 배터리가 방전되거나 전력망 규정을 위반할 수 있습니다. 특히 양자 물리학의 규칙을 추가하면 이 퍼즐을 완벽하게 해결하는 것은 컴퓨터에게 매우 어렵습니다.

이 논문은 혼다 리서치 인스티튜트와 라이덴 대학교의 연구자들이 던진 단순한 질문에 대한 보고서입니다: "이 퍼즐을 양자 컴퓨터의 언어로 번역하는 '방식'이 중요할까요?"

그들은 양자 컴퓨터가 문제를 더 빠르고 효과적으로 해결하는 데 도움이 되는 두 가지 다른 '언어 (인코딩)'를 테스트했습니다.

두 가지 언어: "큐비트" 대 "큐디트"

이 실험을 이해하기 위해, 로봇에게 여행 목록을 설명하려는 상황을 상상해 보십시오.

1. 구식 방법: "큐비트" 언어 (이진 스위치)
전등 스위치를 생각해 보십시오. 그것은 켜져 있거나 (ON) 꺼져 있거나 (OFF) 둘 중 하나입니다.

• 이 방법에서 연구자들은 차량과 여행의 가능한 모든 조합 하나하나마다 별도의 전등 스위치를 사용했습니다.
• 차량이 3 대이고 여행이 2 건이라면 6 개의 스위치가 필요합니다. 스위치가 켜져 있으면 "차량 1 이 여행 A 를 담당한다"는 뜻이고, 꺼져 있으면 그렇지 않다는 뜻입니다.
• 문제점: 이는 스위치로 가득 찬 거대하고 지저분한 방을 만들어냅니다. 컴퓨터는 수백만 가지 조합을 확인해야 하는데, 그중 대부분은 무의미합니다 (예: "차량 1 이 여행 A 를 담당한다" AND "차량 2 가 여행 A 를 담당한다"가 동시에 성립하는 경우). 컴퓨터는 이러한 불가능한 시나리오를 확인하는 데 시간을 낭비합니다.

2. 신식 방법: "큐디트" 언어 (다단 위치 다이얼)
0 또는 1 만 가리키는 것이 아니라 여러 숫자를 가리킬 수 있는 디머 스위치나 다이얼을 생각해 보십시오.

• 이 방법에서는 많은 스위치 대신 각 여행마다 하나의 다이얼을 사용했습니다.
• 다이얼이 "1"을 가리키면 "차량 1 이 이 여행을 담당한다"는 뜻이고, "2"를 가리키면 "차량 2"를 뜻하며, "0"을 가리키면 "어떤 차량도 이 여행을 담당하지 않는다"는 뜻입니다.
• 장점: 훨씬 더 직접적입니다. 두 차량이 같은 여행을 두고 경쟁하는지 확인할 필요가 없습니다. 다이얼은 물리적으로 동시에 두 차량을 가리킬 수 없기 때문입니다. 이는 컴퓨터가 탐색해야 하는 '방'의 크기를 줄여줍니다.

실험: 시간과의 경주

연구자들은 양자 컴퓨터의 시뮬레이션 (완벽하고 잡음이 없는 연습 주기와 같은 '상태 벡터 시뮬레이션') 을 실행하여 이 두 가지 언어가 어떻게 작동하는지 확인했습니다. 그들은 차량 수, 여행 수, 시간대 수가 서로 다른 많은 무작위 시나리오를 설정했습니다.

그들이 발견한 바는 다음과 같습니다:

• 탐색 공간의 축소: "큐디트 (다이얼)" 방법은 탐색 공간의 크기를 기하급수적으로 줄였습니다. 건초더미에서 바늘을 찾는 상황을 상상해 보십시오. 큐비트 방법은 산만한 건초더미를 제공한 반면, 큐디트 방법은 신발 상자만한 건초더미를 제공했습니다.
• 더 빠른 결과: "신발 상자"가 훨씬 작기 때문에 시뮬레이션이 훨씬 빠르게 실행되었습니다. 큐디트 방법은 해답을 찾는 데 훨씬 적은 시간이 걸렸습니다.
• 더 나은 품질: 놀랍게도 큐디트 방법은 단순히 더 빠르게 실행된 것뿐만 아니라, 더 좋거나 동등한 해답을 찾았습니다. 그들이 찾은 해답은 완벽한 정답에 더 가까웠고, 결과도 더 일관적 (덜 '떨림'이나 무작위적) 이었습니다.
• "깊이" 문제: 그들은 알고리즘에 더 많은 층 (깊이) 을 추가하여 양자 컴퓨터가 더 "깊이" 생각하도록 시도했습니다. 일반적으로 더 깊이 생각하면 도움이 됩니다. 하지만 여기서는 큐비트 방법이 혼란을 겪으며 깊이가 깊어질수록 더 나쁜 성능을 보였습니다. 이는 처리해야 할 변수가 너무 많고 컴퓨터가 너무 일찍 최적화를 멈췄기 때문일 것입니다. 반면 큐디트 방법은 문제가 더 복잡해짐에도 불구하고 안정적이고 견고하게 유지되었습니다.

결론

이 논문은 전기차를 여행에 배정하는 것과 같은 스케줄링 및 할당 문제를 해결할 때, 기존의 큐비트 (스위치) 방식보다 큐디트 (다이얼) 방식을 사용하는 것이 훨씬 현명한 선택이라고 결론 내립니다.

여행을 준비하는 것과 같습니다:

• 큐비트: 개별 양말을 하나씩 가져와서 상자에 끼워 넣으려 합니다. 공간과 시간을 낭비합니다.
• 큐디트: 깔끔하게 접힌 양말 한 묶음을 가져옵니다. 완벽하게 들어맞고 공간을 덜 차지하며 즉시 꺼낼 수 있습니다.

연구자들은 옵션이 많은 실제 세계의 스케줄링 문제에서는 이러한 '다중 값' 양자 다이얼 (큐디트) 을 사용하는 것이 시간과 컴퓨팅 파워를 모두 절약하는 실용적이고 효율적인 길이라고 제안합니다.

기술 요약

기술 요약: EV 충전 및 이동 경로 할당 문제를 위한 큐비트와 큐디트 인코딩 비교

문제 정의
본 논문은 전기차 (EV) 함대 관리의 제약 최적화 문제를 다룹니다. 이는 이산 시간 구간 $T$에 걸쳐 $N_{EV}$대의 차량에 대한 양방향 (또는 단방향) 충전 일정을 수립하고, 이러한 차량을 $R$개의 고객 이동 경로 요청에 할당하는 두 가지 결합된 의사결정 과정을 포함합니다. 목표는 배터리 충전 상태 (SOC) 한계, 이동 경로 중첩, 그리드 전력 범위, 그리고 차량이 이동 경로 서비스를 제공하는 동안은 충전할 수 없다는 요구사항을 포함한 엄격한 운영 제약을 만족하면서 충전 비용을 최소화하는 것입니다.

조사된 핵심 과제는 이동 경로 할당 변수에 대한 인코딩 선택이 변분 양자 알고리즘 (VQA), 특히 양자 근사 최적화 알고리즘 (QAOA) 의 자원 요구 사항과 최적화 행동에 미치는 영향입니다. 저자들은 두 가지 서로 다른 표현 방식을 비교합니다:

1. 이진 (큐비트) 인코딩: 모든 EV-이동 경로 쌍에 대해 하나의 이진 변수 ($r_{n,i} \in \{0,1\}$) 를 사용합니다. 이는 각 이동 경로를 최대 하나의 EV 만이 서비스하도록 보장하고, 중첩된 이동 경로가 동일한 차량에 할당되지 않도록 명시적인 제약을 필요로 합니다.
2. 정수 (큐디트) 인코딩: 이동 경로당 하나의 정수 변수 ($q_i \in \{0, \dots, N_{EV}\}$) 를 사용하며, 이 값은 직접적으로 할당된 EV(또는 미서비스 상태) 를 지정합니다. 이 인코딩은 "이동 경로당 하나의 EV" 제약을 본질적으로 만족시켜 할당에 대한 명시적인 이진 제약이 필요 없게 합니다.

방법론
저자들은 QAOA 를 사용하여 문제를 공식화합니다. 두 인코딩 모두 충전 전력 수준 ($l_{n,t}$) 에 대해 큐디트 변수를 사용하지만, 이동 경로 할당을 위한 계산 기저에서는 차이가 있습니다.

• 해밀토니안 구성: 고전적 비용 함수와 제약 조건은 계산 기저에서 대각 연산자로 승격됩니다. 제약 조건 (예: SOC 한계, 이동 경로 중 충전 금지) 은 비용 해밀토니안에 추가된 비선형 페널티 항을 통해 강제됩니다.
• 시뮬레이션: 본 연구는 알고리즘을 벤치마크하기 위해 정확한 상태 벡터 시뮬레이션을 사용합니다. 현실적인 하드웨어 제한을 모방하기 위해 비용 함수의 기대값은 정확한 계산 대신 유한한 수의 측정 샷 ($M=256$) 을 사용하여 추정됩니다.
• 최적화: 고전적 최적화기 (Powell 방법) 가 QAOA 매개변수 ($\gamma, \beta$) 를 변경하여 비용 함수를 최소화합니다. 연구는 각 문제 클래스에 대해 10 개의 무작위 인스턴스를 실행하며, 각 인스턴스당 10 번의 최적화 실행을 수행하고 고정된 200 회의 내부 최적화 반복을 사용합니다.
• 테스트 사례: 두 가지 문제 클래스가 분석됩니다:
  • 양방향 충전: EV 3 대, 시간 단계 2 개, 이동 경로 2 개, 충전 레벨 3 개 ($d=3$).
  • 단방향 충전: EV 2 대, 시간 단계 3 개, 다양한 이동 경로 ($R=2,3,4$), 충전 레벨 2 개 ($d=2$).

주요 기여 및 결과
본 논문은 여러 지표를 통해 두 인코딩에 대한 비교 분석을 제공합니다:

1. 힐베르트 공간 축소: 정수 (큐디트) 인코딩은 이진 (큐비트) 인코딩에 비해 힐베르트 공간의 차원을 기하급수적으로 줄입니다. 구성 비율은 $N_{int}/N_{bin} \approx 2^{-R N_{EV} + R \log_2(N_{EV}+1)}$로 주어집니다. 테스트된 인스턴스의 경우, 이는 수만 개의 검색 공간을 수천 개의 상태로 축소하는 결과를 낳습니다.
2. 최적화 성능:
   • 평균 에너지 갭: 큐디트 인코딩은 일관되게 큐비트 인코딩과 유사하거나 약간 더 나은 평균 에너지 갭을 달성합니다.
   • 분산: 큐디트 결과는 서로 다른 실행 간 에너지 갭에서 훨씬 더 낮은 분산을 보입니다.
   • 성공 확률: 전역 최적해를 찾는 실행의 비율과 샘플링된 실현 가능 상태의 비율은 일반적으로 큐디트 인코딩에서 더 높거나 더 안정적입니다.
3. 실행 시간 및 수렴:
   • 시뮬레이션 실행 시간: 더 작은 힐베르트 공간으로 인해 큐디트 인코딩은 훨씬 짧은 시뮬레이션 실행 시간이 필요합니다 (회로 깊이에 선형적이지만 계수가 훨씬 작음).
   • 레이어 깊이 동작: QAOA 깊이 ($L$) 가 증가함에 따라 큐비트 인코딩의 성능은 큐디트 인코딩보다 훨씬 더 크게 저하됩니다. 저자들은 이를 고정된 반복 예산 내에서 최적화 지형을 탐색하기가 더 어려워지게 만드는 증가된 변분 매개변수의 수로 귀인합니다. 큐디트 인코딩은 고전적 최적화기의 조기 종료에 대해 더 강건합니다.
4. 비용 지형: 큐비트 인코딩의 비용 지형은 큐디트 인코딩에 비해 실현 불가능한 상태의 비율이 더 크기 때문에 (이는 높은 페널티 비용을 수반함) 더 큰 에너지 규모와 더 높은 진동 주파수를 보입니다.

의의 및 주장
본 논문은 큐디트 네이티브 인코딩이 변분 양자 최적화에서 정수 및 다중 값 스케줄링 문제를 해결하기 위한 실용적인 경로를 제공한다고 주장합니다. 주요 의의는 이진 큐비트로 확장하는 대신 이산 다중 값 변수를 직접 큐디트로 표현함으로써 다음과 같은 이점을 얻는다는 것을 입증하는 데 있습니다:

• 힐베르트 공간 차원에서의 기하급수적인 자원 절감.
• 표현 복잡성의 대리 지표로서 고전적 시뮬레이션의 계산 오버헤드 감소.
• 실현 가능한 해가 희소한 고도로 제약된 영역에서 특히 최적화 과정의 개선된 강건성.

저자들은 본 연구가 상태 벡터 시뮬레이션을 사용하지만, 이러한 컴팩트한 표현은 제약 처리 및 논리 변수 매핑의 오버헤드를 줄임으로써 하드웨어 구현에 잠재적 이점을 시사한다고 지적합니다. 그들은 제약이 있는 스케줄링 문제의 경우, 큐디트 인코딩이 자원 요구 사항을 극적으로 줄이면서 최적화 성능을 유지하거나 향상시키는 우월한 선택이라고 결론지었습니다. 본 논문은 겸손하게 향후 연구가 이러한 추세를 더 큰 인스턴스와 실제 양자 하드웨어에서 테스트하여 시뮬레이션을 넘어선 이점이 유지되는지 확인해야 한다고 제안합니다.