기술 요약: 샘플링 기반 가이드 양자 워크 (SamBa–GQW)

문제 정의

본 논문은 임의의 차수를 가진 이진 조합 최적화 문제를 양자 컴퓨터로 해결하는 데 따르는 과제를 다룹니다. 이러한 문제들은 흔히 NP-난해(NP-hard)이며, 비용 함수 $C(x)$를 최소화하는 이진 벡터 $x^* \in \{0, 1\}^n$을 찾는 것을 목표로 합니다(제약 조건이 있을 수 있음). 양자 컴퓨터는 선형 큐비트 자원으로 지수적인 해 공간을 탐색할 수 있는 자연스러운 방법을 제공하지만, 현재의 노이로성 중간 규모 양자(NISQ) 장치들은 양자 근사 최적화 알고리즘(QAOA)과 같은 변분 알고리즘을 실행하는 데 어려움을 겪고 있습니다. 이러한 변분 접근 방식은 매개변수를 조정하기 위해 고전적 옵티마이저에 의존하는데, 이 과정은 종종 "바렌 플래토(barren plateaus)"(기울기 소실 현상)와 문제 크기가 증가함에 따라 필요한 회로 평가 횟수의 지수적 스케일링 문제로 인해 어려움을 겪습니다.

기존의 비변분 대안인 가이드 양자 워크(GQW)는 문제 해밀토니언의 스펙트럼으로부터 유도된 시간 의존적 호핑 비율(hopping rate)을 사용하여 고전적 최적화를 피하려고 시도합니다. 그러나 정확한 스펙트럼을 계산하는 것은 지수적으로 비용이 많이 들며, 베지에 곡선(Bézier curves)과 같은 매개변수 곡선을 사용한 이전의 근사 방식들도 여전히 고전적 최적화를 필요로 했기에 반복 횟수가 지수적으로 증가하는 문제를 안고 있었습니다.

방법론: SamBa–GQW

저자들은 고전적 옵티마이저 없이 양자 실행 단계에서 이를 제거한 비변분 양자 알고리즘인 SamBa–GQW(Sampled-Based Guided Quantum Walk)를 제안합니다. 이 알고리즘은 두 가지 뚜렷한 단계로 작동합니다.

1. 고전적 오프라인 샘플링 프로토콜

비용 해밀토니언 $H_C$의 정확한 스펙트럼을 계산($2^n$번의 평가 필요)하거나 매개변수 곡선을 최적화하는 대신, 알고리즘은 효율적인 샘플링 프로토콜을 사용합니다.

• 샘플링: 프로토콜은 $2^n$개의 해 공간으로부터 다항식 개의 후보 상태, 즉 $q = \text{poly}(n)$ (경험적으로 $q=n^2$이면 충분하다고 밝혀짐)를 무작위로 선택합니다.
• 갭 추정: 각 샘플링된 상태에 대해, 알고리즘은 해당 상태와 그 이웃들(예: X-믹서의 하이퍼큐브와 같은 믹서 연결성으로 정의됨) 사이의 에너지 갭을 계산합니다.
• 스펙트럼 근사: 알고리즘은 특정 에너지 레벨에 대한 최대 에너지 갭들의 평균을 계산합니다. 이는 이전 GQW 문헌에서 유도된 바와 같이, 호핑 비율과 에너지 갭 사이의 관계를 나타내는 함수 $\Gamma(E)$의 근사치를 제공합니다.
• 스케줄 구축: 이러한 샘플링된 점들을 사용하여, 알고리즘은 연속적이고 매끄러운 시간 의존적 호핑 비율 $\Gamma(t)$를 보간법(interpolation)을 통해 구축합니다. 이 스케줄은 믹싱 해밀토니언 $H_M$과 비용 해밀토니언 $H_C$ 사이의 균형을 맞추어, 고에너지 상태에서 저에너지 상태로의 진폭 전이를 극대화하도록 설계되었습니다.

2. 양자 온라인 실행

호핑 스케줄 $\Gamma(t)$가 결정되면, 양자 컴퓨터는 이 스케줄에 따라 연속 시간 양자 워크(CTQW)를 실행합니다.

• 해밀토니언: 시스템은 시간 의존적 해밀토니언 $H(t) = \Gamma(t)H_M + H_C$ 하에서 진화합니다.
• 회로 구현: 게이트 기반 양자 컴퓨터에서 이를 실행하기 위해, 저자들은 2단계 이산화 전략을 제안합니다. 먼저 시간 간격을 호핑 비율이 선형적으로 보간되는 구간들로 나눕니다. 이후 이 구간들을 트로터-스즈키 분해(Trotter-Suzuki decomposition)를 적용하기 위해 다시 세분화합니다. 이는 QAOA와 유사한 구조를 가지되, 매개변수가 최적화되는 것이 아니라 사전에 결정된 양자 회로를 생성하며, 비용($U_C$) 유니터리와 믹서($U_M$) 유니터리가 교대로 나타나는 층으로 구성됩니다.
• 측정: 알고리즘은 계산 기저(computational basis)에서 단 한 번의 측정 세트를 수행합니다. 측정된 결과 중 가장 좋은 솔루션을 선택합니다.

주요 기여

1. 비변분 프레임워크: SamBa–GQW는 양자 실행 중에 고전적 옵티마이저를 통해 매개변수를 튜닝할 필요가 없는 "원샷(one-shot)" 알고리즘으로, 이를 통해 바렌 플래토를 피하고 변분 루프와 관련된 지수적 스케일링 문제를 방지합니다.
2. 효율적인 샘플링: 본 논문은 정확한 스펙트럼 분석의 지수적 비용을 피하면서, 다항식 개의 샘플($q \approx n^2$)만으로도 최적의 호핑 비율을 근사하는 데 충분하다는 것을 입증합니다.
3. 회로 구현: 저자들은 연속 시간 진화를 큐비트 및 샘플 수에 대해 다항식 깊이를 갖는 게이트 기반 양자 회로로 이산화하는 구체적인 방법을 제공합니다.
4. 광범위한 적용성: 알고리즘은 다음과 같은 다양한 문제에 대해 테스트되었습니다:
   • 이차 문제(Quadratic Problems): MaxCut, 최대 독립 집합(MIS), 포트폴리오 최적화(제약 조건 포함).
   • 고차 문제(Higher-Order Problems): 저자기상 상관 이진 수열(LABS), MAX-k-SAT, 그리고 여행 사절 문제(TSP)의 4차 재구성 모델.

결과

저자들은 최대 $n=30$ 큐비트 크기에 대한 수치 시뮬레이션(해밀토니언 기반 및 회로 기반 모두)을 제시합니다.

• 성능: SamBa–GQW는 일관되적으로 고품질의 근사 솔루션을 찾아냅니다. 많은 사례에서 최적의 솔루션 또는 상위 5% 순위 내의 솔루션을 측정할 확률이 매우 높습니다.
• GQW와의 비교: 베지에 곡선을 맞추기 위해 고전적 옵티마이저를 사용하는 변분 GQW와 비교했을 때, SamBa–GQW는 대등한 근사 비율을 달 achieves 합니다. 결정적으로, Sam-Ba-GQW는 반복적인 고전적 최적화 루프를 피함으로써 실행 시간을 최소 10배 이상 단축합니다.
• QAOA와의 비교:
  • 얕은 회로 (NISQ 영역): 얕은 회로 깊이(예: $p < 20$)로 제한될 경우, QAOA는 특히 가중치가 부여된 MaxCut 및 MIS에 대해 일반적으로 SamBa–GQW보다 우수한 성능을 보입니다. 이는 특정 문제 인스턴스에 맞춰 매개변수를 미세 조정하기 위해 고전적 최적화를 사용하는 QAOA의 능력 때문입니다.
  • 깊은 회로 (NISQ 너머): 회로 깊이가 허용될 경우(최대 $p \approx 100$ 이상), SamBa–GQW는 근사 비율 측면에서 QAOA와 "대등한(in par)" 성능을 보입니다. 논문은 SamBa–GQW가 QAOA의 얕은 포화 상태와 비교하여 정점에 도달하기 위해 더 깊은 회로를 필요로 하지만, 변분 오버헤드 없이 유사한 최종 품질을 달성한다고 언급합니다.
• 확장성: 알고리즘은 큐비트 수에 따라 합리적으로 확장됩니다. MaxCut 및 MIS와 같은 문제의 경우, 샘플링 매개변수 $q$와 회로 깊이를 적절히 조정한다면 $n$이 증가하더라도 근사 비율이 높게 유지됩니다.

의의 및 주장

본 논문은 SamBa–GQW를 NISQ 시대를 넘어 조합 최적화 문제를 해결하기 위한 유망한 휴리스틱으로 자리매김합니다. 그 주요 의의는 바렌 플래토에 강건하며, 변분 방법에서 발견되는 고전적 최적화 반복의 지수적 스케일링 문제를 겪지 않는 비변분 대안을 제공한다는 점에 있습니다.

저자들은 SamBa–GQW가 최적의 결과를 얻기 위해 QAOA보다 더 깊은 회로를 필요로 할 수 있지만, 고전적 최적화 루프 동안 반복적인 양자 회로 평가를 제거함으로써 솔루션 품질과 계산 비용 사이의 유리한 트레이드오프를 제공한다고 주장합니다. 이 알고리즘은 NP-난해 문제에 대한 다항 시간 솔루션이 아니라, 다항식 자원(샘플링 및 회로 깊이 측면)이 고품질 상태를 향한 탐색을 효과적으로 가이드하는 데 충분할 수 있는 방법론으로서 제시되었습니다. 이 연구는 양자 하드웨어가 개선되어 더 깊은 회로가 가능해짐에 따라, SamBa–GQW가 대규모 조합 최적화를 위한 경쟁력 있고 확장 가능한 접근 방식이 될 수 있음을 시사합니다.