Recent quantum runtime (dis)advantages

본 논문은 현재의 양자 우월성 주장이 상당한 시스템 수준의 오버헤드를 배제함으로써 종종 편향되어 있음을 주장하며, 실험적으로 기반을 둔 엔드투엔드 런타임 정의와 강력한 고전적 기준선을 통해 검토된 어닐링 및 게이트 기반 알고리즘에 대해 NISQ 하드웨어에서 신뢰할 수 있는 런타임 우월성은 아직 달성되지 않았음을 입증합니다.

핵심

레이스 카 심판이 되어 새로운 미래형 전기차 (양자 컴퓨터) 가 고성능 스포츠카 (고전 컴퓨터) 보다 실제로 더 빠른지 판단한다고 상상해 보세요.

이 논문의 저자들, 즉 폴란드의 연구팀들은 최근 전기차가 승리한다는 주장들을 새롭게 검토하기로 결정했습니다. 그들은 대시보드에서 전기차는 빠르게 보이지만, 전체 경기를 자세히 살펴보면 실제로는 밀리고 있다는 사실을 발견했습니다.

다음은 그들의 발견을 간단한 비유로 정리한 내용입니다:

핵심 문제: "스톱워치 대 한 바퀴 시간"

과거에 사람들이 이 두 컴퓨터를 비교할 때, 종종 엔진이 실제로 회전하는 순간 (계산) 만을 타이밍했습니다. 그들은 다음에 소요된 시간을 무시했습니다:

• 엔진 시동 걸기.
• 기어 넣기.
• 타이어 점검하기.
• 결승선에서 속도계 읽기.

저자들은 양자 컴퓨터의 경우 이러한 "추가 단계"가 너무 많은 시간을 차지하여 속도 이점을 완전히 무너뜨린다고 주장합니다. 엔진의 시간만 재서는 안 되며, 차고에서 결승선까지의 전체 여정을 타이밍해야 합니다.

사례 연구 1: 양어닐러 ("느린 판독" 경기)

주장: 최근 한 연구는 최적화 문제를 해결하는 양자 컴퓨터인 양어닐러가 문제가 커질수록 더 빨라지고 있다고 주장했습니다.
현실 점검: 저자들은 결과를 읽는 시간을 포함해 전체 과정을 타이밍하며 실험을 재수행했습니다.

• 비유: 100 미터를 0.5 초에 질주하는 달리기 선수 (양자 부분) 를 상상해 보세요. 하지만 매번 결승선에 도착할 때마다 기록을 받기 위해 출발선까지 천천히 걸어 가야 하는데, 이 과정이 200 초가 걸립니다.
• 결과: "스프린트"는 빠르지만, "돌아오는 걷기"가 너무 느려 경기가 길어질수록 총 소요 시간은 개선되지 않습니다. 현재 양자 컴퓨터는 "답을 읽는" 시간에 지배받고 있어, 이러한 작업에서는 최고의 고전 컴퓨터보다 빠르지 않습니다.

사례 연구 2: 시몬 문제 ("마법" 대 "계산기")

주장: 또 다른 연구는 양자 컴퓨터가 고전 컴퓨터보다 훨씬 적은 "질문" (오라클 호출) 을 사용하여 특정 수학 퍼즐 (시몬 문제) 을 해결했다고 보여주었습니다. 양자 컴퓨터는 몇 번의 추측만으로, 고전 컴퓨터는 수백만 번의 추측이 필요한 마법처럼 보였습니다.
현실 점검: 저자들은 실제 기계에서 퍼즐을 해결하는 데 걸린 실제 시간을 살펴보았습니다.

• 비유: 양자 컴퓨터는 1 초 만에 답을 맞힐 수 있는 마법사처럼 보이지만, 주문을 부르고 결과를 읽는 데 매우 느립니다. 반면 고전 컴퓨터는 백만 개의 질문을 해야 하는 초고속 계산기이지만, 질문을 너무 빠르게 던져 0.03 초 만에 전체 작업을 끝냅니다.
• 결과: 양자 컴퓨터가 더 적은 질문을 했음에도 불구하고, 주문을 실행하는 "오버헤드"로 인해 실제 시간 기준으로는 100 배 더 느렸습니다. "마법"은 아직 계산기를 이길 만큼 빠르지 않습니다.

사례 연구 3: 하이브리드 알고리즘 ("불공평한 경기")

주장: 세 번째 연구는 하이브리드 양자 - 고전 알고리즘이 복잡한 비즈니스 문제를 해결하는 가장 빠른 방법이라고 주장했습니다.
현실 점검: 저자들은 두 가지 주요 문제를 발견했습니다:

1. 스톱워치가 고장 났음: 설정 (하이퍼파라미터) 을 조정하는 데 걸린 시간이나 고전 컴퓨터가 양자 컴퓨터를 돕는 데 걸린 시간을 계산하지 않았습니다.
2. 상대가 약함: 그들은 양자 컴퓨터를 특정 문제 유형에 최적화되지 않은 "느린" 고전 알고리즘 (CPLEX) 과 비교했습니다.

• 비유: 이는 페라리를 자전거와 비교하되, 페라리의 엔진 시간만 재고 트랙까지 운전하는 데 걸린 시간은 무시한 것과 같습니다. 저자들이 적절하고 고속인 스포츠카 (조정된 고전 알고리즘) 를 경기에 투입했을 때, 양자 "페라리"는 승리하지 못했습니다. 오히려 고전 자동차가 더 빨랐습니다.

큰 결론

이 논문은 아직까지 실제 세계의 속도 측면에서 "양자 우위"를 본 적이 없다고 결론 내립니다.

양자 컴퓨터가 이론적 이점 (예: 더 적은 단계 필요) 을 가지고 있다고 해서 오늘 경기를 이긴다는 뜻은 아닙니다. "오버헤드" (설정, 결과 판독, 냉각 등) 가 현재는 너무 무겁습니다.

미래의 경기를 위한 저자들의 조언:
양자 컴퓨터가 실제로 더 빠르다는 것을 증명하기 위해 향후 연구는 다음을 수행해야 합니다:

1. 전체 여정 타이밍: 설정, 판독, 냉각 시간을 스톱워치에 포함하세요.
2. 공정한 상대 선정: 구식 모델이 아닌 최신 최고의 고전 컴퓨터와 비교하세요.
3. 통계에 대한 정직함: 양자 차가 이긴 한 경기만 선택하지 말고 평균 성능을 살펴보세요.

이러한 조건들이 충족될 때까지 "양자 우위"는 오늘의 현실이 아닌 미래의 약속으로 남을 것입니다.

기술 요약

Tuziemski 외의 논문 "Recent quantum runtime (dis)advantages"에 대한 상세한 기술적 요약입니다.

1. 문제 제기

이 논문이 다루는 핵심 문제는 "양자 우위"를 주장하는 데 사용되는 양자 런타임에 대한 견고하고 실험적으로 근거 있는 정의의 부재입니다. 현재의 주장은 종종 다음에 의존합니다:

• 대리 지표: 전체 월클러 시간을 대신하기 위해 "어닐링 시간"이나 "오라클 호출 복잡도"를 사용합니다.
• 제외된 오버헤드: 판독, 열화, 트랜스파일레이션 (컴파일), 데이터 전송, 하이퍼파라미터 튜닝과 같은 시스템 수준의 비용을 무시합니다.
• 약한 기준선: 양자 알고리즘을 비최적의 고전적 구현 (예: 순차적 알고리즘 또는 문제 재형성이 필요한 알고리즘) 과 비교합니다.

저자들은 종단 간 런타임(문제 제출부터 솔루션 추출까지) 을 고려하지 않으면, 현재의 노이즈가 있는 중간 규모 양자 (NISQ) 하드웨어에 대한 양자 우위 주장이 종종 편향되고 오해의 소지가 있다고 주장합니다.

2. 방법론

저자들은 운영적으로 의미 있는 런타임 정의를 위한 프레임워크를 제안하고, 최근의 주목할 만한 양자 우위 주장과 관련된 세 가지 대표적인 사례 연구를 적용합니다.

A. 제안된 런타임 정의

• 양자 어닐링: 총 런타임 ($t_{tot}$) 에는 다음이 포함되어야 합니다:
  • 프로그래밍 시간 (문제 로딩).
  • 어닐링 시간 ($t_{anneal}$).
  • 판독 시간 (상태 측정).
  • 열화 시간 (장치 초기화).
  • 클라우드 액세스 오버헤드.
• 게이트 기반 (디지털) 양자: 총 런타임에는 다음이 포함되어야 합니다:
  • 트랜스파일레이션 (회로를 네이티브 게이트/토폴로지로 컴파일).
  • 실행 시간 (샷).
  • 샷 사이의 판독 및 열화.
  • 고전적 사후 처리 및 데이터 전송.
• 고전적 기준선: 참조 알고리즘은 다음을 충족해야 합니다:
  • 병렬화 가능: 현대 하드웨어 (GPU/FPGA) 활용.
  • 네이티브: 불필요한 재형성 없이 문제를 해결 (예: 네이티브 솔버가 존재하는 경우 Higher-Order Unconstrained Binary Optimization (HUBO) 을 Mixed-Integer Programming 으로 변환하지 않음).
  • 최적화: 하이퍼파라미터 튜닝 비용을 포함.

B. 분석된 사례 연구

1. 근사 QUBO 를 위한 양자 어닐링: Ref. [20] (Munoz-Bauza & Lidar) 재평가.
2. 게이트 기반 오라클 쿼리 (제한된 시몬 문제): Ref. [21] (Singkanipa 외) 재평가.
3. 하이브리드 BF-DCQO 알고리즘: HUBO 문제에 대한 Ref. [22] (Chandarana 외) 재평가.

3. 주요 기여 및 결과

사례 연구 1: 양자 어닐링 (근사 QUBO)

• 원래 주장: Ref. [20] 은 "어닐링 시간"($t_{anneal}$) 을 기반으로 양자 어닐링이 고전적 참조 (PT-ICM) 보다 확장성 우위가 있다고 보고했습니다.
• 재평가: 저자들은 판독 및 열화를 포함한 전체 QPU 액세스 시간을 측정했습니다.
• 결과:
  • 판독 시간 (200 µs) 은 총 런타임을 지배하며, 어닐링 시간 (0.5–27 µs) 보다 12 차수 더 큽니다.
  • 전체 종단 간 지표 ($TT_\epsilon$) 를 사용할 때, 확장성 우위는 사라지며 런타임은 문제 크기에 따라 거의 일정하게 유지됩니다.
  • 비교: GPU 에서 실행되는 고전적 **시뮬레이션 분기 기계 (SBM)**는 낙관적인 가정 하에서도 양자 어닐러보다 우월하며, 양자 장치가 보여주지 않는 견고한 확장성을 보입니다.

사례 연구 2: 게이트 기반 오라클 쿼리 (제한된 시몬 문제)

• 원래 주장: Ref. [21] 은 IBM 하드웨어에서 제한된 시몬 문제에 대해 쿼리 복잡도(오라클 호출 수) 에서 지수적 우위를 입증했습니다.
• 재평가: 저자들은 단일 GPU 에서 실행되는 고전적 브루트포스 알고리즘과 비교하여 양자 구현의 월클러 런타임을 비교했습니다.
• 결과:
  • 양자 알고리즘은 지수적으로 적은 오라클 호출이 필요하지만, 게이트 실행 및 판독 오버헤드로 인해 호출당 물리적 시간은 훨씬 느립니다.
  • 결과: 테스트된 크기 ($N=29$ 비트) 에서 고전적 GPU 구현은 약 0.035 초에 문제를 해결한 반면, 양자 구현은 약 2 초가 소요되었습니다 (약 100 배의 지연).
  • 교차점: 이론적 외삽에 따르면 런타임 교차는 $N \approx 60$에서만 발생하며, 이는 현재 노이즈가 있는 장치로 정확하게 해결할 수 없는 크기입니다.

사례 연구 3: 하이브리드 BF-DCQO 알고리즘 (HUBO)

• 원래 주장: Ref. [22] 는 HUBO 문제에 대해 디지털화된 반대 단열 양자 알고리즘 (BF-DCQO) 이 시뮬레이션 어닐링 (SA) 및 CPLEX 보다 런타임 우위가 있다고 주장했습니다.
• 재평가:
  • 기준선 결함: 원래 연구는 HUBO 를 Mixed-Integer Programming 으로 재형성해야 하는 CPLEX 와 같은 비최적 고전적 기준선을 사용했으며 (대규모 오버헤드 추가), 통계적 평균이 아닌 단일 "최적" 인스턴스에 대한 결과를 보고했습니다.
  • 새로운 기준선: 저자들은 GPU 가속 네이티브 HUBO 시뮬레이션 어닐링 솔버를 구현하고 BF-DCQO 와 비교했습니다.
  • 결과: 최적화된 고전적 SA 는 솔루션 품질과 시간당 비율 ($TTR$) 모두에서 하이브리드 양자 접근법보다 우월했습니다.
  • 임베딩 문제: D-Wave Advantage2 어닐러에서 동일한 인스턴스를 테스트했을 때, 필요한 임베딩 (하드웨어 토폴로지로 매핑) 은 긴 체인과 낮은 솔루션 품질을 초래하여 잠재적 우위를 더욱 무효화했습니다.

4. 중요성 및 결론

주요 결론

실험적으로 근거 있는 종단 간 성능 지표 하에서, 현재 NISQ 하드웨어에서 실용적인 런타임 양자 우위가 입증된 바 없습니다. 최근 문헌에서 관찰된 "우위"는 다음에 기인한 인공물입니다:

1. 지배적인 오버헤드 (판독, 컴파일, 열화) 무시.
2. 약하거나 비네이티브인 고전적 기준선 사용.
3. 작은 문제 크기에 대해 월클러 속도로 전환되지 않는 점근적 복잡도 지표 (쿼리 복잡도 등) 에 의존.

향후 벤치마킹을 위한 제안 원칙

저자들은 신뢰할 수 있는 양자 우위 주장을 보장하기 위한 일련의 원칙을 제시합니다:

1. 주요 런타임 측정: 명목 파라미터에서 추론된 것이 아닌 총 실행 시간을 직접 측정.
2. 종합적 오버헤드 계상: 판독, 데이터 전송, 튜닝 등 모든 시스템 수준 비용 포함.
3. 표준화된 지표: 다양한 인스턴스에 대해 Time-to-$\epsilon$ ($TT_\epsilon$) 같은 지표 사용.
4. 확장성 무결성: 유한 크기 효과를 피하기 위해 광범위한 문제 크기 범위에서 확장성 분석.
5. 고성능 고전적 기준선: 최첨단 병렬화 고전 솔버 (예: GPU 기반 SBM 또는 SA) 와 비교.
6. 하이브리드 영가설: 하이브리드 알고리즘의 경우, 양자 서브루틴을 고전적 것으로 대체했을 때 유사하거나 더 나은 성능이 나오는지 테스트.

영향

이 작업은 양자 컴퓨팅 분야에 대한 중요한 현실 점검 역할을 합니다. 이론적 속도 향상이 존재하지만, 현재 하드웨어의 공학적 현실(노이즈, 지연, 오버헤드) 이 이러한 이점이 실용적 유용성으로 전환되는 것을 현재 막고 있음을 강조합니다. 신뢰할 수 있는 우위 주장은 양자 및 고전 시스템을 동등한 운영적 검토로 대우하는 엄격하고 재현 가능하며 전체적인 벤치마킹을 요구합니다.