JVG algorithm은 작은 수에서만 이긴다

Source: Hacker News

정기적으로 다루던 AI 종말 시나리오를 잠시 제쳐두고, 이 블로그 초창기의 전통적인 흐름으로 돌아가 보겠습니다 … 그런데 이제 “JVG (Jesse–Victor–Gharabaghi) 알고리즘”(예, 저자들이 자신들의 이름을 따서 명명했습니다)이라는 것에 대해 논평을 달라는 여러 메시지를 받았습니다. 이 알고리즘은 Shor의 소인수분해 알고리즘에 비해 획기적인 개선이라고 소개되고 있으며, (대중 기사에 따르면) RSA‑2048을 단 5,000개의 물리적 큐비트만으로도 깨뜨릴 수 있다고 합니다.

JVG 알고리즘이 작동하지 않는 이유

논문을 살펴보면, Shor 알고리즘의 핵심 단계인 (x^r \bmod N)을 모든 (r)에 대해 중첩 상태로 계산하는 대신, 고전 컴퓨터에서 (x^r \bmod N) 값을 미리 계산하고 이를 양자 상태에 모두 로드한다는 새로운 아이디어가 제시됩니다.

가능한 (r)의 수는 지수적으로 많습니다. 모든 값을 계산하는 데는 지수 시간이 걸리고, 이를 양자 컴퓨터에 로드하는 데에도 역시 지수 시간이 필요합니다. 우리는 (n^2) 시간이라는 프라이팬에서 벗어나 (2^n) 시간이라는 불에 뛰어든 셈입니다. 이 방법은 아주 작은 수에 대해서만 승리하는 것처럼 보일 수 있지만, 큰 수에서는 절망적입니다.

같은 요점을 보다 정중하고 자세히 설명한 글을 보고 싶다면, Hacker News 토론이나 Postquantum.com 기사를 참고하세요.

의심스러운 주장에 대한 경고 신호

• 논문이 arXiv에 올라오지 않고 “Preprints.org”라는 사이트에 실렸습니다. 이는 제가 유명하게 만든 수학적 돌파구가 잘못됐다는 10가지 징후에 추가될 수 있습니다. arXiv에도 품질이 낮은 논문이 올라오긴 하지만, 대부분의 진정한 돌파구는 arXiv나 ECCC 혹은 IACR ePrint archive와 같은 신뢰할 만한 학술지에 실립니다.

• 간단한 Google 검색 결과, 이 주장은 클릭베이트와 링크 파밍을 하는 뉴스 사이트에서는 크게 부풀려지지만, 신뢰할 만한 과학 매체에서는 무시되고 있습니다—예, 평소 양자 과대광고 매체조차도 이 이야기를 다루지 않았습니다!

보통 이렇게 형편없는 경우, 자비로운 답은 그저 잊혀지게 두는 것입니다. 하지만 이번 경우는 지적 난동과 진실에 대한 전적인 무관심이 너무 심해 저자들에게 영구적인, 작은 부끄러움을 남겨 주는 것이 마땅하다고 생각합니다.