Quantum WalkScore: Benchmarking Quantum Computers on the Graph Nodefinding Problem

기술 요약: 퀀텀 워크스코어 (Quantum WalkScore, QWS)

문제 정의
본 논문은 노이즈가 있는 중간 규모 양자(NISQ) 및 미래의 결함 허용 양자 컴퓨터의 성숙도를 평가하기 위한 애플리케이션 지향적 벤치마크의 필요성을 다룹니다. 기존 벤치마크는 물리적 게이트 충실도나 무작위 회로 샘플링에 집중되어 있는 반면, 유망한 양자 루틴, 특히 **이산 시간 양자 워크(Discrete-Time Quantum Walks, DTQW)**와 **양자 진폭 증폭(Quantum Amplitude Amplification, AA)**을 활용하여 실제 그래프 문제를 해결하는 벤치마크는 부족한 실정입니다. 저자들은 무방향 그래프 내에서 특정 "표식된(marked)" 타겟 노드 $v_t$를 소스 노드 $v_0$로부터 찾아내는 그래프 노드 탐색 문제에 초점을 맞춥니다. 이 문제는 통신 라우팅, 데이터베이스 검색, 복잡한 네트워크 분석과 같은 실제 응용 분야의 근본적인 빌딩 블록 역할을 합니다.

방법론: 퀀텀 워크스코어 (QWS) 프로토콜
저자들은 양자 컴퓨터가 성공적으로 해결할 수 있는 최대 문제 크기를 측정하기 위해 설계된 확장 가능한 벤치마크 프로토콜인 **Quantum WalkScore (QWS)**를 제안합니다.

• 그래프 패밀리: 벤치마크는 단순성, 확장성 및 하드웨어 적용 가능성의 균형을 맞추기 위해 두 가지 특정 그래프 토폴로지를 활용합니다:
  1. 사이클 그래프(Cycle Graphs): $2^n$개의 노드를 가진 1D 구조로, 각 노드는 두 개의 이웃 노드와 연결됩니다.
  2. 2D-토러스 그래프(2D-Torus Graphs): $2^n \times 2^n$개의 노드를 가진 2D 구조로, 각 노드는 네 개의 이웃 노드와 연결됩니다 (주기적 경계 조건).
• 문제 인스턴스: $(n, d)$로 정의되며, 여기서 $n$은 큐비트 수이고 $d$는 소스와 타겟 노드 사이의 거리(최단 경로 엣지 수)입니다.
• 알고리즘 루틴:
  1. 초기화: 시스템을 상태 $|v_0\rangle$로 초기화합니다.
  2. 이산 시간 양자 워크 (DTQW): 워커(walker)가 $num\_w$ 단계 동안 진화합니다. 프로토콜은 도달 가능성을 보장하기 위해 $num\_w \ge d$ 및 $num\_w \equiv d \pmod 2$를 요구합니다. 편향되지 않은 워크를 위해 Hadamard 코인이 사용됩니다.
  3. 진폭 증폭 (AA): 타겟 상태를 측정할 확률을 높이기 위해 DTQW 루틴을 AA 프레임워크(Brassard 등) 내에 삽입합니다. 이는 타겟 및 초기 상태에 대한 반사(reflection)를 $num\_aa$번 반복하는 과정을 포함합니다.
  4. 측정: 성공 확률 $p_{exp}$는 타겟 노드 상태를 관찰할 확률로 측정됩니다.
• 스코어링 기준:
  • 임계 확률 ($p^*$): 성공 확률이 무작위 추측보다 유의미하게 높음을 보장하기 위해 동적 임계값이 정의됩니다. $d \le 2$인 경우 $p^* = 1/3$입니다. $d > 2$인 경우 $p^* = 1/5 + 1/2^d$입니다.
  • 메트릭: 성공 확률은 여러 배치(1000 샷의 4개 배치)와 여러 타겟 노드 인스턴스(사이클의 경우 2개, 토러스의 경우 4개)에 대해 평균을 냅니다.
  • QWS 스코어: 스코어는 첫 번째 실패가 발생하기 전까지 측정된 성공 확률이 $p^*$를 초과하는 가장 큰 문제 크기 $(n, d)$입니다. 스코어는 마지막 성공 인스스턴스를 $(e_n, e_d)$라고 할 때, $QWS_{cycle} = 2^{e_n-1} + e_d$ 및 $QWS_{torus} = 2^{e_n} + e_d$로 계산됩니다.

주요 기여

1. 프로토콜 설계: DTQW와 AA라는, 미래 양자 알고리즘에 필수적인 두 루틴을 통합한 완전한 애플리케이션 지향적 벤치마크 프로토콜을 도입했습니다.
2. 확장성 및 재현성: 프로토콜은 모든 게이트 기반 양자 컴퓨터에 적용 가능하도록 설계되었으며, 표준화된 실험 파라미터(샷 수, 배칭)와 사용자 최적화가 가능한 유연한 알고리즘 파라미터($num\_w, num\_aa$)를 갖추고 있습니다.
3. 이론적 및 경험적 분석: 모든 문제 크기를 이론적으로 해결할 수 있는 파라미터의 존재에 대한 이론적 보증을 제공하며, 알고리즘 구현 및 네이티브 하드웨어 구현 모두에 대한 상세한 리소스 추정(회로 깊이 스케일링)을 제공합니다.
4. 실험적 검증: 프로토콜은 세 세대의 IBM 양자 프로세서(Heron r2, Heron r3, Nighthawk r1)에서 실행되어 현재 하드웨어 역량에 대한 개념 증명 평가를 제공합니다.

결과

• 무잡음 시뮬레이션: 이상적인 양자 컴퓨터에서의 시뮬레이션은 본 벤치마크가 큰 문제 크기에 대해서도 해결 가능함을 보여줍니다. "suff-perf" 시나리오(AA 반복 횟수 최소화)에서는 성공 확률이 임계값 근처에 머뭅니다. "best-perf" 시나리오에서는 성공 확률이 1에 근접하지만, 이는 더 높은 회로 깊이를 요구합니다.
• 회로 깊이 스케일링: 이론적인 알고리즘 깊이는 $O(nd)$로 스케일링됩니다. 그러나 IBM의 Heron 아키텍처로 트랜스파일(transpiled)될 때, 네이티브 깊이는 사이클 그래프의 경우 $O(n^{3.45}d)$, 2D-토러스 그래프의 경우 $O(n^{2.2}d)$로 스케일링되어 하드웨어 매핑의 상당한 오버헤드를 강조합니다.
• IBM 하드웨어에서의 실험적 성능:
  • ibm_kingston (Heron r2) 프로세서에서의 실험 결과, 노이즈와 결맞음(decoherence)으로 인해 문제 크기가 증가함에 따라 성공 확률이 급격히 감소했습니다.
  • 시스템은 문제 크기 **(3, 1)**까지 임계값을 성공적으로 통과했습니다. 이후 크기에서는 성공 확률이 무작위 추측과 유사한 수준으로 급락했으나, (4, 1) 크기는 예외적으로 나타났으나 연속적인 성공 시퀀스를 구성하지 못했습니다. 결과적으로, "suff-perf" 시나리오 하에서 사이클 그래프에 대한 퀀텀 워크스코어는 5로 결정되었습니다.
  • 더 큰 인스턴스(예: 깊이 > 700 게이트)의 경우, 결과는 무작위 추측과 구별할 수 없는 수준으로 저하되었습니다.
  • Heron r2, Heron r3, Nighthawk r1 간의 비교는 유사한 경향을 보였으며, Heron r3가 약간 더 나은 정확도를 제공했으나, 세 아키텍처 모두 약 1000개의 게이트를 초과하는 회로에 어려움을 겪었습니다.

의의 및 주장
본 논문은 QWS가 추상적인 하드웨어 메트릭과 실제 애플리케이션 성능 사이의 간극을 메우는 데 필요한 도구라고 주장합니다. 그래프 노드 탐색 문제에 집중함으로써, 최적화 및 검색 작업을 위해 필수적인 핵심 양자 프리미티브(DTQW 및 AA)를 실행하는 하드웨어의 능력을 직접 평가합니다.

저자들은 이 벤치마크가 알고리즘 파라미터와 하드웨어 제한 사이의 상호작용을 강조한다는 점을 역설합니다. 결과는 이론적 프레임워크가 큰 문제를 해결할 수 있도록 허용함에도 불구하고, 현재의 NISQ 장치들이 회로 깊이와 오류 누적에 의해 제한된다는 것을 보여줍니다. 본 논문은 QWS가 NISQ 및 미래의 결함 허용 양자 컴퓨팅(FTQC) 장치 간의 성능 차이를 구분하며, 양자 컴퓨터의 성숙도를 추적하기 위한 의미 있고 해석 가능한 점수를 제공한다고 결론짓습니다. 현재 하드웨어에서 달성한 낮은 점수인 5는 이러한 알고리즘들을 대규모 실제 문제에 적용하기 전에 여전히 상당한 기술적 과제가 남아 있음을 강조합니다.