quantum wave

• 저자 Stephen P. Jordan, Noah Shutty, Mary Wootters, Adam Zalcman, Alexander Schmidhuber, Robbie King, Sergei V. Isakov, Tanuj Khattar, Ryan Babbush (Google Quantum AI, Stanford University, MIT, Caltech)
• 저널 Nature 646, 831–836 (2025)
• 게재일 2025. 10. 22. (arXiv:2408.08292로 2024년 8월에 처음 공개)
• 카테고리 양자 알고리즘
• DOI 10.1038/s41586-025-09527-5

양자 알고리즘 이론의 화두: 실용적이고 증명 가능한 양자 이득

양자 알고리즘 연구에서 가장 큰 화두는 단연 실용적이면서 증명 가능한 양자 이득(quantum advantage)을 주는 양자 알고리즘을 찾는 것이다. 어떤 문제에서 양자 이득을 증명할 수 있다는 것은, 적절한 계산 복잡도 가정 아래에서 고전 알고리즘으로는 그 문제를 빨리 풀 수 없지만 양자 알고리즘으로는 빨리 풀 수 있음을 수학적으로 보일 수 있다는 뜻이다. 대표적인 예가 1994년에 발표된 쇼어(Shor)의 소인수분해 알고리즘이다. 고전 알고리즘으로는 소인수분해에 오랜 시간이 걸릴 수밖에 없다는 것은 널리 받아들여지는 가정이다. 우리가 일상에서 쓰는 암호 체계가 이 가정에 기대고 있을 정도다. 그런데 쇼어의 알고리즘은 소인수분해를 다항 시간에 해낸다. 양자 컴퓨터가 나오면 암호가 뚫린다는 말은 여기서 나온다.

쇼어의 알고리즘 이후 30여 년 동안 양자 컴퓨팅은 눈부시게 발전했다. 하드웨어에서는 중성 원자, 이온 트랩, 초전도 회로, 실리콘 스핀 큐비트 등 여러 플랫폼이 자웅을 겨루고 있고, 상용 플랫폼들은 오류 정정 기술을 도입하는 추세다. 알고리즘 이론에서도 양자 시뮬레이션, QAOA(quantum approximate optimization algorithm), 단열 알고리즘(adiabatic algorithm) 같은 훌륭한 아이디어가 많이 나왔다. 하지만 “그래서 양자 컴퓨터를 만들면 암호를 깨는 것 말고 할 수 있는 게 뭔데?”라고 물으면 여전히 명확한 답이 없다. 지금 양자 컴퓨팅에서는 실험이 이론을 앞질렀다는 평가가 일각에서 나오는 것도 이 때문이다.

DQI가 겨냥하는 문제

이런 배경에서 2024년에 처음 공개된 알고리즘이 DQI(Decoded Quantum Interferometry)다. 이름의 decoded는 오류 정정 부호의 복호(decoding)를 가리킨다. DQI가 다루는 문제를 가장 단순한 꼴로 쓰면 다음과 같다. 유한체 \(\mathbb{F}_2\) 위의 변수 \(x=(x_1,\ldots,x_n)\)에 대한 선형 방정식 \(m\)개 \(b_i\cdot x=v_i\) \((b_i\in\mathbb{F}_2^n,\ v_i\in\mathbb{F}_2,\ i=1,\ldots,m)\)가 주어졌을 때, 가장 많은 방정식을 만족하는 \(x\)를 찾는 문제다(max-XORSAT). 이 문제의 최적해를 정확히 구하는 것은 NP-hard다. 즉 \(\mathrm{P}\neq\mathrm{NP}\)라면 다항 시간 알고리즘은 없다. 그래서 최적값의 일정 비율에 이르는 해를 찾는 근사 알고리즘을 고려한다. DQI도 이런 근사 알고리즘이다.

핵심 아이디어: 간섭으로 좋은 해의 진폭 키우기

DQI의 핵심 아이디어는 단순하다. 목적 함수를

로 정의하자. \(b_i\cdot x=v_i\)이면 \(i\)번째 항이 \(+1\)이고 아니면 \(-1\)이므로, \(f(x)\)는 만족하는 방정식 수에서 만족하지 않는 방정식 수를 뺀 값이다.

이제 상태 \(\sum_{x\in\mathbb{F}_2^n} f(x)|x\rangle\)를 보자. 정규화 상수를 빼면 이 상태는 \(H^{\otimes n}\sum_{i=1}^{m}(-1)^{v_i}|b_i\rangle\)와 같다. 오른쪽의 \(m\)항 중첩은 효율적으로 만들 수 있으므로, 이 상태도 효율적으로 준비할 수 있다. 이 상태를 계산 기저에서 측정하면 비트열 \(x\)가 \(f(x)^2\)에 비례하는 확률로 나온다. 즉 \(f(x)\)가 양수라면 높은 점수를 갖는 비트열이 더 높은 확률로 추출되는 것이다.

DQI는 더 나은 시작 상태를 쓴다. 적절한 다항식 \(P\)를 골라 \(\sum_x P(f(x))|x\rangle\)를 준비하는 것이다. 차수를 높일수록 이 치우침은 강해지지만, 그만큼 더 어려운 복호 문제를 풀어야 한다.

이렇게 하면 특정한 문제에서 DQI가 얻는 근사비를 증명할 수 있고, 그 값은 지금까지 알려진 고전 알고리즘의 근사비보다 높다. 다만 어떤 고전 알고리즘도 그 값을 낼 수 없다는 것까지 증명된 것은 아니다.

DQI의 한계와 이후 진행 상황

앞서 살펴보았듯이 DQI가 양자 이득을 달성한다는 주장은 현존하는 고전 알고리즘보다 더 성능이 좋다는 것이다. 역사적으로 양자 이득을 주장하는 많은 경우에 더 나은 고전 알고리즘이 발견되어 양자 이득을 무력화시켰다. DQI에 실제로 양자 이득이 있는지는 지금도 활발히 연구되고 있는 주제이다.

연구 그룹 소개 및 연구 전망

구글 퀀텀 AI(Google Quantum AI)는 구글의 양자 컴퓨팅 연구 조직으로, IBM과 함께 초전도 큐빗 양자 컴퓨터 개발을 이끌어 왔다. 알고리즘 이론과 양자 컴퓨터 개발 두 방면 모두에서 강한 것이 특징이다. 2024년에는 105큐빗 윌로우(Willow) 칩에서 표면 부호의 크기를 키울수록 논리 큐빗의 오류율이 지수함수적으로 줄어드는 이정표를 달성하였다. 같은 그룹의 Craig Gidney는 2025년에 RSA 2048 암호를 100만 물리 큐빗으로 일주일 안에 깰 수 있다고 추정해, 주목을 받았다. 그 밖에도 DQI, 마법 상태 재배 등 중요한 개념들을 제안하는 등 양자 컴퓨팅 학계와 산업의 중요한 한 축을 담당한다.