A brief history of quantum vs classical computational advantage

본 리뷰 논문은 양자 계산 우위를 주장하는 모든 실험을 종합적으로 요약하고, 그 실험들의 도전 과제와 반박을 비판적으로 검토하며, 특정 문제에서의 이론적 우위를 논의하고, 쇼어 알고리즘에서의 우위 달성을 위한 핵심 단계로서 양자 오류 정정의 최근 진전을 강조한다.

핵심

다음은 라이언 라로즈 (Ryan LaRose) 의 논문 "양자 대 고전 컴퓨팅 우위의 간략한 역사"에 대한 설명을, 창의적인 비유를 곁들여 쉽고 일상적인 언어로 번역한 것입니다.

큰 그림: 위대한 경주

두 명의 주자 사이의 경주를 상상해 보세요: 고전 컴퓨터(오늘날 우리가 사용하는 초고속이고 신뢰할 수 있는 마라톤 주자) 와 양자 컴퓨터(양자 물리학의 이상한 규칙에 따라 작동하는 신비롭고 번개처럼 빠른 단거리 주자) 입니다.

이 논문의 목표는 양자 단거리 주자가 "나는 이 특정 퍼즐을 고전 주자보다 더 빠르게 풀 수 있다!"라고 주장할 때마다 점수표를 기록하는 것입니다. 저자 라이언 라로즈는 스포츠 역사가처럼 행동하여 모든 경주, 모든 이의 제기, 그리고 모든 실격 처리를 검토하여 오늘날 이 경주가 어디에 서 있는지를 정확히 알려줍니다.

이 논문은 '우위'를 단순히 정의합니다: 누가 작업을 먼저 끝내는가? 작업이 질병 치료와 같이 유용하든, 아니면 단순한 어리석은 퍼즐과 같이 쓸모없든 상관없습니다. 유일한 질문은 속도입니다.

---

제 1 부: "어리석은 퍼즐" 경주 (실험적 우위)

지금까지 양자 단거리 주자들은 세 가지 특정 유형의 "어리석은" 경주에서 승리하려고 시도했습니다. 이들은 아직 다리 건설이나 이메일 작성에 유용하지 않으며, 고전 컴퓨터에게는 어렵지만 양자 컴퓨터에게는 쉽도록 특별히 고안된 것입니다.

1. 무작위 회로 샘플링 경주 (동전 던지기 혼란)

• 작업: 완전히 무작위적이고 혼란스러운 방식으로 한 번에 53 개의 동전을 던지는 기계를 상상해 보세요. 양자 컴퓨터는 이를 수행하고 앞면과 뒷면의 패턴을 기록합니다. 고전 컴퓨터는 그 패턴이 어떻게 될지 추측해야 합니다.
• 첫 번째 승리 (구글, 2019 년): 구글의 "시카모어 (Sycamore)" 컴퓨터는 이를 200 초 만에 수행했습니다. 그들은 고전 슈퍼컴퓨터가 동일한 계산을 수행하는 데 10,000 년이 걸릴 것이라고 주장했습니다.
• 반격: 고전 주자들은 포기하지 않았습니다. 그들은 퍼즐을 풀 새로운, 더 지능적인 방법을 고안해냈습니다.
  • 비유: 고전 주자가 트랙 전체를 달릴 필요가 없으며, 발견한 터널을 통해 단축로를 이용할 수 있음을 깨달은 것과 같습니다.
  • 결과: 시간이 지남에 따라 고전 컴퓨터는 더 빨라졌습니다. 2024 년까지 고전 슈퍼컴퓨터는 동일한 작업을 86 초 만에 수행하여 양자 컴퓨터를 능가했습니다.
• 판결: 구글의 첫 번째 승리는 "반박"되었습니다. 고전 주자가 따라잡고 앞서갔습니다. 그러나 구글은 더 크고 어려운 퍼즐 (더 많은 동전, 더 많은 던지기) 로 다시 도전했고, 그 새로운 경주들은 아직 반박되지 않았습니다.

2. 가우스 보손 샘플링 경주 (광자 핀볼)

• 작업: 동전 대신 이 경주는 거울 미로로 튕겨 나가는 빛 입자 (광자) 를 사용합니다. 양자 컴퓨터는 광자를 쏘아 넣고, 광자는 특정 지점에 떨어집니다. 고전 컴퓨터는 광자가 어디에 떨어졌는지 계산해야 합니다.
• 참가자: 중국 (USTC) 과 캐나다 (Xanadu) 의 팀들이 이 광자 기반 주자들을 구축했습니다.
• 반격: 동전 경주와 마찬가지로 고전 컴퓨터는 "비율"을 찾았습니다. 그들은 빛 입자가 완벽하지 않다면 (그들은 결코 완벽하지 않습니다) 수학이 더 쉬워진다는 것을 깨달았습니다. 그들은 예상보다 훨씬 빠르게 광자 미로를 시뮬레이션하는 새로운 알고리즘을 구축했습니다.
• 판결: 이러한 주장 대부분은 "약하게 반박"되었습니다. 이는 고전 컴퓨터가 아직 가장 큰 퍼즐에서 양자 컴퓨터를 이기지 못했다는 뜻이지만, 가까운 미래에 조금 더 나은 고전 컴퓨터가 이를 이길 수 있을 정도로 충분히 가깝다는 것을 의미합니다.

3. 양자 시뮬레이션 경주 (날씨 예보)

• 작업: 복잡한 시스템 (예: 자성 물질) 이 시간에 따라 어떻게 변하는지 시뮬레이션하는 작업입니다.
• 참가자: IBM 과 D-Wave.
• 반격: IBM 은 고전 컴퓨터보다 자성 시스템을 더 빠르게 시뮬레이션했다고 주장했습니다. 하지만 2 주 이내에 고전 연구자들은 이를 노트북에서 몇 분 만에 시뮬레이션할 수 있음을 보여주었습니다.
• 판결: IBM 의 주장은 빠르게 "반박"되었습니다. 고전 주자가 훨씬 더 빠른 경로를 찾았습니다. D-Wave 의 최근 시도는 여전히 주시되고 있지만, 유사한 도전에 직면할 가능성이 높습니다.

---

제 2 부: "이론적" 경주 (수학적 증명)

때때로 수학자들은 "우리가 완벽한 양자 컴퓨터를 구축한다면, 그것은 이 경주에서 반드시 이겨야 한다"고 말합니다. 하지만 역사는 고전 수학자들이 새로운 트릭을 찾는 데 매우 능숙함을 보여줍니다.

• 추천 시스템 경주: 고전 컴퓨터보다 영화를 더 빠르게 추천하는 양자 알고리즘이 제안되었습니다.
  • 반전: 한 고전 수학자 (Ewin Tang) 는 "이봐, 만약 고전 컴퓨터가 양자 컴퓨터가 사용하는 동일한 특수 데이터 구조를 가진다면, 그 문제는 똑같이 빠르게 풀 수 있다!"라고 깨달았습니다.
  • 결과: 양자 우위가 사라졌습니다. 이를 "양자화 제거 (dequantization)"라고 합니다.
• 최적화 경주: 복잡한 일정 문제를 해결하도록 설계된 알고리즘에서도 비슷한 이야기가 발생했습니다. 양자 우위가 주장되었고, 그다음에 그와 똑같이 좋은 고전 알고리즘이 발견되었습니다.

---

제 3 부: 최후의 국경 (오류 수정)

여기에 이 논문의 가장 중요한 결론이 있습니다: 양자 컴퓨터는 취약합니다.

• 비유: 양자 단거리 주자가 유리 주자라고 상상해 보세요. 그들은 놀라울 정도로 빠르지만, 작은 자갈 (잡음) 에 넘어지면 산산조각 납니다. 마라톤 (암호 해독을 위한 큰 수 인수분해 등) 을 뛰기 위해서는 방패를 착용해야 합니다.
• 방패: 이 방패는 양자 오류 수정이라고 합니다. 이는 많은 물리적 "유리" 큐비트를 사용하여 하나의 튼튼한 "논리적" 큐비트를 만듭니다.
• 현재 상태: 우리는 이제 막 이 방패를 구축하기 시작했습니다.
  • 2024 년, 구글은 "논리적" 큐비트 (방패를 쓴 주자) 가 개별 "물리적" 큐비트 (유리 주자) 보다 더 오래 지속되는 새로운 칩 (Willow) 을 발표했습니다.
  • 이것이 "성배"의 순간입니다. 오류를 수정하기 위해 더 많은 부분을 추가하는 것이 시스템을 더 나쁘게 만드는 것이 아니라 더 좋게 만든다는 것을 증명합니다.
• 미래: 이 방패를 갖기 전까지는, 우리는 "유용한" 경주 (코드 깨기나 새로운 약물 시뮬레이션 등) 를 달릴 수 없습니다. 이 논문은 오류 수정이 양자 컴퓨터가 실제 세계 문제에서 고전 컴퓨터를 진정으로 이기기 전의 최후의 국경이라고 주장합니다.

요약: 우리는 어디에 서 있는가?

이 논문은 경주가 줄다리기라고 결론 내립니다.

1. 양자 컴퓨터가 큰 도약을 합니다.
2. 고전 컴퓨터는 더 똑똑해지고, 단축로를 찾아 따라잡거나 (또는 앞서갑니다).
3. 양자 컴퓨터는 더 나은 하드웨어를 구축하고 다시 시도합니다.

지금 우리는 경계선에 있습니다. 우리는 양자 컴퓨터가 특정하고 쓸모없는 퍼즐에서 승리하는 것을 보았지만, 고전 컴퓨터는 거의 모든 경우에 그들을 이길 방법을 찾았습니다. 이 논문은 양자 컴퓨터가 유용한 경주에서 승리하려면 먼저 오류 수정의 기술을 숙달해야 한다고 제안합니다. 그 전까지는 주도권이 계속 바뀌게 될 것입니다.

기술 요약

제목: 양자 대 고전 컴퓨팅 우위의 간략한 역사
저자: 라이언 라로즈
출처: Quantum (2026-05-14 채택)

문제 제기

본 논문은 "양자 컴퓨팅 우위"(양자 우월성 또는 고전 초월 계산으로도 불림) 의 진화하는 지형을 다룹니다. 핵심 문제는 고전 컴퓨터와 양자 컴퓨터 각각에게 계산적으로 실현 가능한 것 사이의 이동하는 경계를 정의하고 추적하는 것입니다. 저자들은 계산적 우위를 문제의 실용적 유용성과 무관하게, 주어진 문제에 대한 해결 시간의 감소로 구체적으로 정의합니다. 이 검토는 현재까지의 모든 양자 우위 실험적 주장과 이를 뒤이은 고전적 도전, 반박, 그리고 이러한 주장의 지위를 변경한 이론적 발전을 함께 기록하는 것을 목표로 합니다.

방법론

본 논문은 실험 물리학, 컴퓨터 과학, 복잡성 이론의 역사적 데이터를 종합하는 포괄적인 검토 방법론을 사용합니다.

1. 연대기적 목록화: 저자들은 양자 우위를 주장하는 모든 실험의 연대기를 작성하며, 이를 무작위 회로 샘플링 (RCS), 가우스 보손 샘플링 (GBS), 양자 시뮬레이션 (QSim) 의 문제 유형별로 분류합니다.
2. 지위 분류: 각 실험은 후속 문헌에 기반하여 다음과 같은 지위를 부여받습니다:
   • 반박되지 않음: 고전 알고리즘이 아직 해당 실험을 더 빠르게 시뮬레이션하지 못함.
   • 도전됨: 고전 알고리즘이 시뮬레이션 시간을 개선하거나 특정 실험적 측면에 의문을 제기함.
   • 약하게 반박됨: 향후 고전 하드웨어에서 해당 실험을 시뮬레이션할 수 있을 것으로 보이는 고전 알고리즘이 존재함.
   • 반박됨: 고전 컴퓨터가 양자 장치보다 빠르게 실험을 성공적으로 시뮬레이션함.
3. 이론적 분석: 이 검토는 근사 최적화, 추천 시스템, 양자 화학과 같은 특정 영역에서의 이론적 우위를 검토하여, 양자 알고리즘에서 영감을 받은 고전 알고리즘의 개발인 "탈양자화 (dequantization)"가 어떻게 이론적 속도 향상을 약화시킬 수 있는지 강조합니다.
4. 오류 수정 검토: 본 논문은 쇼어 (Shor) 알고리즘과 같은 오류 내성이 필요한 알고리즘에서 우위를 달성하기 위한 필수적인 "최종 최전선"으로 식별된 양자 오류 수정 (QEC) 실험의 역사를 추적합니다.

주요 기여

• 포괄적 지위 표: 본 논문은 구글의 2019 년 시카모어 (Sycamore) 에서 D-Wave 의 2024 년 시뮬레이션에 이르기까지 모든 양자 우위 주장과 고전적 반박에 대한 현재 지위를 연대기적으로 나열한 표 1 을 제공합니다.
• 도전의 상세한 서술: 양자 실험과 고전 시뮬레이션 사이의 "군비 경쟁"을 문서화합니다. 주목할 만한 기여로는 텐서 네트워크 수축 최적화 (예: "빅 헤드" 알고리즘, 초그래프 분할) 와 특정 실험에 대한 추정 고전 실행 시간을 수천 년에서 몇 시간 또는 몇 초로 줄인 노이즈 활용 전략의 추적이 포함됩니다.
• 지표의 명확화: 이 검토는 고전 알고리즘이 전체 회로를 시뮬레이션하지 않고도 높은 XEB 값을 "사기 (spoof)"할 수 있는 허점을 논의하며, 약한 반박과 강한 반박을 구분함으로써 크로스 엔트로피 벤치마크 (XEB) 충실도를 비판적으로 분석합니다.
• 이론적 탈양자화: 본 논문은 Max-E3LIN2 최적화 및 추천 시스템에서의 이론적 우위가 Barak 등 및 Ewin Tang 에 의한 고전 알고리즘이 유사한 입력 가정 하에서 양자 성능을 맞먹거나 초과했을 때 어떻게 상실되었는지 상세히 설명합니다.
• QEC 진전: 표 2 와 4 절은 단순 반복 코드에서 거리가 최대 7 인 표면 코드로의 전환, 그리고 최근 구글의 2024 년 실험에서 논리적 오류율이 물리적 오류율 임계값 아래로 떨어진 최근의 이정표를 포함하여 오류 수정 실험의 급속한 진전을 요약합니다.

결과

• 실험적 변동성: 검토 결과, 거의 모든 주요 양자 우위 실험적 주장이 심각한 도전에 직면한 것으로 나타났습니다.
  • 구글의 2019 년 RCS(53 큐비트): 초기에 1 만 년의 고전 실행 시간이 주장되었습니다. 이는 텐서 네트워크 최적화에 의해 도전받았으며, 결국 2024 년 Zhao 등 (Zhao et al.) 이 1,432 개의 GPU 를 사용하여 86.4 초 만에 실험을 시뮬레이션함으로써 강하게 반박되었습니다.
  • USTC GBS(Jiuzhang 1.0, 2.0, 3.0): 우위 주장은 Oh 등 (2023) 에 의해 약하게 반박되었습니다. 그들은 텐서 네트워크를 사용하여 양자 장치보다 훨씬 빠르게 이러한 실험을 시뮬레이션했으나, 가장 큰 인스턴스의 경우 "강한" 의미에서는 여전히 반박되지 않았습니다.
  • IBM QSim(2023): 횡단장 이징 (transverse-field Ising) 모델 시뮬레이션에서의 우위 주장은 노트북이나 단일 GPU 에서 실행된 여러 고전적 접근법 (텐서 네트워크, 신뢰 전파, 클리포드 섭동 이론) 에 의해 수주 내에 반박되었습니다.
  • D-Wave(2024): 최근의 양자 시뮬레이션 우위 주장은 작성 시점에는 반박되지 않았으나, 저자들은 이것이 향후 고전적 도전을 받을 가능성이 높다고 지적합니다.
• 이론적 변화: 본 논문은 이론적 우위가 정적이지 않음을 보여줍니다. 추천 시스템 및 근사 최적화 (QAOA) 를 위한 알고리즘은 유사한 데이터 구조나 근사 기법을 활용하는 "탈양자화"된 고전 알고리즘에 의해 그 양자 우위가 약화되었습니다.
• 오류 수정 이정표: 오류 내성 양자 컴퓨팅은 아직 실현되지 않았지만, 이 검토는 논리적 큐비트가 이제 물리적 구성 요소보다 더 긴 수명을 달성하고 있으며 오류율이 확장 가능한 오류 내성에 필요한 임계값에 접근하고 있음을 강조합니다.

의의 및 주장

본 논문은 양자 우위의 역사가 정적 성취가 아닌 역동적이고 이동하는 표적이라고 주장합니다.

• 이동하는 표적: 저자들은 계산적 우위가 특정 시점의 최고로 알려진 고전 알고리즘과 하드웨어에 상대적으로 정의됨을 강조합니다. 고전 알고리즘이 개선됨에 따라 (종종 양자 통찰에서 영감을 받아) 우위의 경계는 다시 고전 컴퓨터로 이동합니다.
• 검증 위기: 본 논문의 상당 부분은 양자 우위를 검증하는 어려움에 초점을 맞춥니다. 많은 현재 실험 (RCS 등) 은 고전적으로 검증하기 어려워, 우위 주장 자체가 그 자체로 계산적으로 다루기 어려운 고전 계산에 의존하는 역설을 만듭니다. 본 논문은 효율적으로 검증 가능한 우위를 위한 향후 방향으로서 "피크드 회로 샘플링 (peaked circuit sampling)"과 "숨겨진 코드 샘플링 (Hidden Code Sampling)"을 지적합니다.
• 오류 수정의 역할: 이 검토는 지수적 속도 향상이 입증된 알고리즘 (쇼어 알고리즘 등) 의 경우 "최종 최전선"이 단순히 큐비트 수가 아니라 양자 오류 수정이라고 주장합니다. 오류 내성이 없으면 오류 수정의 오버헤드가 이론적 속도 향상을 상쇄할 수 있습니다.
• 겸손한 전망: 저자들은 특정 문제에 대해 양자 우위가 가능할 가능성이 높지만, 현재 이 분야는 양자와 고전적 우세 사이의 "경계"에 있다고 결론지었습니다. 영구적인 우위를 가정하는 것을 경계하며, 고전 및 양자 기술이 진화함에 따라 지위가 계속 이동할 것이라고 경고합니다. 본 논문은 고전적으로 어렵고 양자적으로 쉬우며, 효율적으로 검증 가능하고 과학적으로 유용한 새로운 문제 형식을 향해 연구자들을 추진하는 역사적 기록 역할을 합니다.