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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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