‘JVG algorithm’은 작은 수에서만 이기는 것처럼 보인다
Source: Hacker News
Introduction
AI 종말론 같은 정규 프로그램을 잠시 멈추고 이 블로그 초창기의 전통적인 흐름으로 돌아오게 되어 죄송합니다… 하지만 지금까지 여러 사람에게서 “JVG (Jesse–Victor–Gharabaghi) 알고리즘”[https://www.preprints.org/manuscript/202510.1649/v1]에 대해 논평해 달라는 메시지를 받았습니다(네, 저자들이 자신들의 이름을 따서 명명했습니다). 이 알고리즘은 Shor의 소인수분해 알고리즘에 비해 엄청난 개선을 이룬 것으로 제시되며, 대중 기사에 따르면 RSA‑2048을 물리적 큐비트 5,000개만으로도 깨뜨릴 수 있다고 합니다.
자세히 살펴보면, 이 논문의 핵심 아이디어는 Shor 알고리즘의 핵심 단계인 모든 (r)에 대해 (x^r \bmod N)을 중첩 상태로 계산하는 대신, 고전 컴퓨터에서 (x^r \bmod N) 값을 미리 계산해 두고 이를 모두 양자 상태에 로드한다는 것입니다.
Why the JVG algorithm doesn’t work
(r)의 경우의 수는 지수적으로 많습니다. 모든 경우를 계산하는 데는 지수 시간이 걸리며, 이를 양자 컴퓨터에 로드하는 데에도 지수 시간이 소요됩니다. 우리는 (n^2) 시간이라는 프라이팬에서 벗어나 (2^n) 시간이라는 불에 뛰어든 셈입니다. 이는 아주 작은 수에 대해서만 승리하는 것처럼 보일 수 있지만, 큰 수에 대해서는 절망적입니다.
같은 점을 더 정중하고 자세히 설명한 글을 보고 싶다면, Hacker News 토론이나 Postquantum.com 기사를 참고하세요.
Signs that the claim is dubious
- 비‑arXiv 매체 – 이 논문은 arXiv, ECCC, IACR 대신 “Preprints.org”에 게재되었습니다. 저는 이를 제 유명한 수학적 돌파구가 잘못됐다는 10가지 징후에 추가했습니다. arXiv에도 질 낮은 논문이 올라오긴 하지만, 신뢰할 만한 돌파구 대부분은 arXiv 혹은 위에 열거된 저장소에 나타납니다.
- 클릭베이트 증폭 – 간단한 Google 검색 결과를 보면, 이 주장이 저품질 클릭베이트 뉴스 사이트에서 끊임없이 확대되고 있는 반면, 평판 좋은 과학 매체(그리고 심지어 일반적인 양자 과대광고 사이트조차)에서는 무시되고 있음을 알 수 있습니다.
이 정도로 형편없는 경우, 자비로운 답은 그저 잊혀지게 두는 것입니다. 그러나 이번 경우는 지적 난동 수준과 진실에 대한 전면적인 무관심이 영구적이고 공개적인 기록으로 남을 만큼 심각합니다.
Further reading
- 원본 프리프린트: “JVG (Jesse–Victor–Gharabaghi) algorithm” – Preprints.org
- 양자 종말론을 주장하는 대중 기사 – BriefGlance
- Hacker News 토론 – link
- Postquantum.com 분석 – link
- 수학적 돌파구가 잘못됐다는 10가지 징후 – Scott Aaronson 블로그