고전 알고리즘이 D‑Wave의 ‘양자 우월성’ 주장을 뒤흔들다

양자 컴퓨팅 기업들이 새로운 성과를 발표할 때 자주 등장하는 표현이 있다. 바로 **‘양자 우월성(quantum supremacy)’**이다. 이는 양자 컴퓨터가 기존 고전 컴퓨터로는 현실적인 시간 안에 풀 수 없는 문제를 해결할 때 사용되는 개념이다.

하지만 최근 플랫아이언 연구소(Flatiron Institute)와 보스턴대학교 연구진이 발표한 연구는, 그 경계가 생각보다 빠르게 바뀔 수 있다는 점을 보여줬다.

연구진은 **텐서 네트워크(tensor networks)**와 신념 전파(belief propagation) 알고리즘을 결합한 새로운 고전 시뮬레이션 방법을 개발했다. 그 결과, D‑Wave가 2025년 ‘양자 우월성’의 사례로 제시했던 동일한 양자 동역학 문제를 고전 컴퓨터로 재현하는 데 성공했다. 일부 계산은 심지어 개인용 노트북에서도 실행 가능했다.

D‑Wave의 2025년 주장: 20분 vs 100만 년

2025년 3월, 캐나다 양자 컴퓨팅 기업 D‑Wave는 약 5,000큐비트 규모의 초전도 양자 어닐러 ‘Advantage2’ 시스템을 이용한 연구 결과를 발표했다.

연구팀은 복잡한 자기 물질의 동역학을 시뮬레이션하는 계산을 수행했고, 이 작업이 약 20분 이내에 완료됐다고 밝혔다. 동시에 같은 계산을 고전 슈퍼컴퓨터로 수행한다면 약 100만 년에 가까운 시간이 필요할 것이라고 추정했다.

이 문제는 격자 구조(lattice) 위에 배치된 이징 스핀 글라스(Ising spin‑glass) 모델의 동역학을 계산하는 것이었다. 이러한 시스템은 서로 얽힌 많은 스핀 상호작용을 포함하기 때문에, 기존 고전 알고리즘으로는 규모가 커질수록 계산이 급격히 어려워지는 것으로 알려져 있었다.

이 때문에 D‑Wave와 협력 연구진은 이를 ‘고전 컴퓨터를 넘어선 계산(beyond‑classical computation)’ 사례로 제시했다.

같은 문제를 다시 풀어본 고전 알고리즘

플랫아이언 연구소와 보스턴대 팀은 동일한 물리 시뮬레이션 문제를 다시 분석했다.

양자 시스템을 고전적으로 시뮬레이션할 때 가장 큰 난점은 전체 양자 상태를 직접 계산해야 한다는 점이다. 큐비트 수가 늘어날수록 필요한 계산량은 기하급수적으로 증가한다.

연구진은 이 문제를 다른 방식으로 접근했다. 핵심은 시스템의 수학적 구조를 활용하는 것이었다.

그들이 사용한 방법의 핵심 요소는 다음과 같다.

• 스핀 격자 구조를 그대로 반영한 2차원·3차원 텐서 네트워크
• 네트워크의 값을 효율적으로 업데이트하는 신념 전파 알고리즘
• 얽힘(entanglement)이 증가해도 표현 크기를 억제하는 텐서 압축 기법

이 접근법을 사용하면 5,000큐비트 전체 파동함수를 직접 저장하지 않아도 된다. 대신 시스템에서 실제로 나타나는 상관관계만 압축 형태로 표현할 수 있다.

그 결과 연구진은 양자 어닐링 과정에서 나타나는 동일한 동역학을 높은 정확도로 재현할 수 있었다고 보고했다.

왜 노트북에서도 가능했을까

텐서 네트워크의 핵심 아이디어는 양자 상태를 압축 표현하는 것이다.

일반적인 양자 시뮬레이션은 파동함수의 모든 진폭을 저장해야 하기 때문에 계산량이 폭발적으로 증가한다. 하지만 많은 물리 시스템에서는 실제로 필요한 상관관계가 제한적이기 때문에, 이를 압축된 형태로 표현할 수 있다.

특히 격자 구조를 가진 시스템에서는 이러한 압축이 더욱 효과적으로 작동한다. 연구진은 여기에 신념 전파 기반 메시지 전달 업데이트를 결합해 계산 효율을 크게 높였다.

이 덕분에 일부 시뮬레이션은 대형 슈퍼컴퓨터가 아니라 일반 개인용 컴퓨터에서도 실행 가능한 수준으로 계산량이 줄어들었다.

‘양자 우월성’ 논쟁에 던지는 의미

이번 결과가 양자 컴퓨터의 장점이 없다는 것을 의미하는 것은 아니다.

다만 중요한 사실을 보여준다. 양자 우위의 기준은 고정된 것이 아니라 계속 움직이는 목표라는 점이다.

대부분의 양자 우월성 주장은 “당시 알려진 최고의 고전 알고리즘”과 비교해 이루어진다. 하지만 고전 알고리즘 역시 빠르게 발전하고 있다. 텐서 네트워크, 몬테카를로 방법, 변분 알고리즘 등 새로운 접근법이 계속 등장하고 있기 때문이다.

즉, 오늘은 고전 컴퓨터로 불가능해 보이는 문제가 내일 더 나은 알고리즘이 등장하면서 가능해질 수도 있다는 뜻이다. 이번 연구는 바로 그런 사례를 보여준다. 문제의 한계가 계산 자체의 물리적 한계가 아니라 고전 알고리즘의 발전 수준이었을 가능성을 시사한다.

양자 컴퓨터 vs 고전 알고리즘: 계속되는 경쟁

이 때문에 연구자들은 이제 양자 우위를 입증할 때 더 엄격한 기준을 요구하고 있다.

예를 들어 다음과 같은 조건이 점점 중요해지고 있다.

• 고전 알고리즘이 크게 개선되기 어려운 문제
• 양자 하드웨어가 확실한 규모 확장 이점을 가지는 문제
• 독립적으로 검증 가능한 결과

결국 계산 과학의 발전은 하드웨어와 알고리즘이 동시에 경쟁하며 발전하는 과정이다. 양자 프로세서는 계속 향상되고 있지만, 고전 알고리즘 역시 예상보다 빠르게 진화하고 있다.

그리고 그 경쟁은 아직 끝나지 않았다. 새로운 ‘양자 우월성’ 주장이 등장할 때마다, 다음 단계의 고전 알고리즘이 그 주장을 시험하게 될 가능성도 계속 남아 있다.