제10장: “양자 알고리즘의 기초”
쇼어 알고리즘과 그루버 알고리즘, 현대 세상을 어떻게 휘저어놓을까?
양자컴퓨터에 대한 이야기가 어느 정도 익숙해지면, 사람들이 가장 자주 언급하는 알고리즘으로 “쇼어 알고리즘”과 “그루버 알고리즘”이라는 두 가지 이름이 올라온다. 이 둘은 사실상 양자 알고리즘의 상징처럼 여겨지는데, 그 이유는 고전 컴퓨터로는 정말 엄청나게 오래 걸릴 문제들을 상대적으로 짧은 시간 안에 풀 수 있는 가능성을 제시했기 때문이다. 간단히 말해, 쇼어 알고리즘은 소인수분해 문제를, 그루버 알고리즘은 검색 문제를 획기적으로 단축할 수 있다고 알려져 있다. 그런데 과연 어떻게 이런 일이 가능한지, 그리고 왜 이것이 ‘미래의 열쇠’로 불릴 만큼 중요한지 살펴보면, 양자컴퓨터가 갖는 파급력이 한층 와 닿는다.
이미 앞서, 양자컴퓨터가 “중간 계산 과정을 들여다볼 수 없는 방식으로, 큐비트와 양자게이트를 활용한다”는 이야기가 나왔다. 중첩 상태와 확률 진폭, 얽힘 같은 독특한 현상이 ‘동시에 여러 가능성을 시험’해 볼 수 있는 길을 열어 주고, 이를 잘 설계하면 기존 슈퍼컴퓨터가 몇십 년, 몇백 년 걸릴 문제도 짧은 시간에 해결할 수 있다는 것이 핵심 개념이다. 쇼어 알고리즘이 보여 주는 놀라운 점은, 너무나 커서 사람이 읽기도 힘든 대수(예를 들어 자릿수가 수백 자에 달하는 대형 정수)를 빠르게 소인수분해할 수 있다는 사실이다. 고전적으로 소인수분해는 체계적으로 나눠보는 데 엄청난 시간이 걸린다. 그런데 양자컴퓨터라면 특정 양자게이트 배열을 통해 수많은 가능성을 병렬적으로 시험하고, 측정 단계에서 원하는 소인수를 상당히 빠르게 얻어낼 수 있다.
이 소인수분해 능력이 왜 문제냐 하면, 현대 암호학의 상당 부분이 바로 “큰 수를 소인수로 잘 나눌 수 없는” 수학적 난제에 의존하기 때문이다. 예를 들어, 우리가 쓰는 전자서명이나 인터넷 뱅킹 같은 시스템도 대부분 큰 소인수분해 문제를 기반으로 만들어졌다. 만약 쇼어 알고리즘이 실용적인 규모(수백~수천 큐비트)의 양자컴퓨터에서 돌 수 있다면, 현재 우리가 안전하다고 믿는 암호체계가 순식간에 뚫릴 수도 있다. 예를 들어, 병아리가 알껍질을 깨고 나오듯이, 어떤 난공불락 문제라도 양자 알고리즘이라면 간단히 부숴 버릴 수 있다는 비유가 등장하는 이유다.
쇼어 알고리즘의 원리 (이해하려 하지 말고, 참고용으로만 보자.)하지만 “모든 문제를 다 부술 수 있다”는 건 아니다. 오히려 쇼어 알고리즘은 ‘소인수분해’라는 아주 구체적인 문제에서 강력하다는 점이 중요하다. 그럼에도, 소인수분해 문제는 현대 보안 체계 전반에 연결되어 있기 때문에, 그 영향력이 실로 어마어마하다. 이 때문에 전 세계 정부와 기업이 양자컴퓨팅 발전 속도에 촉각을 곤두세우고 있으며, 기존 암호체계를 대체할 ‘양자내성(Quantum-Resistant) 암호’ 연구도 활발하게 진행되고 있다. 말하자면, 쇼어 알고리즘이 등장함으로써 “양자컴퓨터가 정말 온다면 세상이 크게 바뀔 것”이라는 메시지가 확실해진 셈이다.
그러면 그루버 알고리즘이란 무엇이길래 쇼어 알고리즘과 함께 그렇게 많이 언급될까? 쇼어 알고리즘이 소인수분해 문제를 다룬다면, 그루버 알고리즘은 “검색” 문제를 크게 단축한다고 알려져 있다. 예를 들어, 우리가 도서관에서 특정 책 한 권을 찾으려 할 때, 고전적으로는 책을 하나씩 열어 확인해 봐야 할 수도 있다. 컴퓨터 검색이 발전하면서 이런 일이 쉬워졌다고 생각할 수 있지만, 사실 구조화되지 않은 데이터(정말 뒤죽박죽 섞여 있는 리스트)에서 특정 항목을 찾아내는 일은 여전히 많은 연산을 필요로 한다. 그루버 알고리즘은 이런 검색 과정을 양자컴퓨터의 중첩 상태를 활용해 “제곱근만큼” 빠르게 만들 수 있다고 주장한다.
그루버 알고리즘의 원리 (이해하려 하지 말고, 참고용으로만 보자.)물론 “제곱근만큼 빠르다”는 말이 막연할 수도 있겠지만, 데이터 양이 천문학적으로 늘어날수록 이 차이가 엄청나게 커진다. 예를 들어, 리스트가 1조 개의 항목을 갖고 있다고 할 때, 고전 컴퓨터는 최대 1조 번 정도는 뒤져봐야 답을 찾겠지만, 그루버 알고리즘은 대략 100만 번 정도로 줄어들 수 있다(물론 정확한 수치는 다소 단순화한 예시지만, 큰 그림은 그렇다). 이것은 대용량 데이터 검색, 빅데이터 분석, 인공지능 학습 등 여러 분야에서 중요한 의미를 지닌다. 데이터가 계속 폭발적으로 쌓이고 있는 현실을 생각하면, “검색 속도가 제곱근만큼 빨라진다”는 말 자체가 대단한 혁신처럼 느껴질 수 있다.
이 두 알고리즘이 “양자알고리즘의 양대 축”이라 불리는 이유는, 소인수분해 문제와 검색 문제 모두 현재의 디지털 사회에서 엄청난 중요성을 지니기 때문이다. 검색은 구글이나 네이버 같은 인터넷 포털, 대기업의 빅데이터 처리, 인공지능 모델 훈련 등에 직결된다. 소인수분해는 은행 거래, 전자 정부 시스템, 각종 암호화폐 관련 보안에 깊숙이 연결되어 있다. 따라서 둘 중 어느 쪽이 먼저 실용화되든, 그 여파가 우리의 삶 곳곳에서 느껴질 가능성이 높다.
다만 여기서 기억해야 할 점은, 쇼어나 그루버 알고리즘이 ‘양자’라는 도구를 쓴다고 해서 오만 가지 문제를 다 해결하는 만능열쇠는 아니라는 사실이다. 양자알고리즘도 문제 유형에 따라 천차만별이어서, 일부 문제에는 큰 강점을 발휘하지만 다른 분야에는 별 소득이 없을 수도 있다. 게다가 이런 놀라운 알고리즘이 실현되려면, 안정적인 수백~수천 큐비트가 필요한데, 현재 연구 수준으로는 아직 갈 길이 남아 있다. 정교한 오류정정 기술과 대규모 큐비트 제어가 가능해지는 시점이 언제인지에 따라, 쇼어나 그루버 알고리즘이 실제로 얼마나 ‘파괴적’인 결과를 내놓을지는 달라질 것이다.
그럼에도 “이 문제가 천 년쯤 지나야 풀릴 거라고 생각했는데, 양자컴퓨터라면 몇 분도 안 걸릴지도 모른다”라는 상상이 주는 충격은 상당히 크다. 일상생활에서 우리가 챙겨야 할 보안이나, 거대한 데이터 쌓임 속에서 원하는 정보를 효율적으로 검색하는 일 같은 문제들이, 기술 발전 한 번에 뒤집힐 수도 있다는 이야기이기 때문이다. 그래서 양자알고리즘, 특히 쇼어 알고리즘과 그루버 알고리즘이 각종 과학 잡지와 뉴스에서 끊임없이 인용되는 것이다.
결론적으로, 양자컴퓨팅의 미래를 전망할 때 반드시 언급되는 두 주인공이 쇼어와 그루버라는 데는 의심의 여지가 없다. 쇼어 알고리즘은 “우리가 안전하다고 믿는 암호체계를 한순간에 무너뜨릴 수도 있다”는 가능성을 열어 줬고, 그루버 알고리즘은 “어마어마한 데이터를 더 빨리 뒤져볼 수 있다”는 희망을 심어 줬다. 이 둘은 각각 암호학과 검색이라는, 디지털 시대를 지탱하는 가장 중요한 기둥들을 정면으로 공략하며, 앞으로 다가올 미래가 양자기술에 달려 있을지도 모른다는 메시지를 던지고 있다.
★ 쇼어 알고리즘과 그루버 알고리즘에 대해 더욱 자세히 알고싶다면? (영문)
쇼어 알고리즘의 이해
https://medium.com/@sanchit.madane.2003/shors-algorithm-bf431cac2f24
그루버 알고리즘의 이해
https://murshedsk135.medium.com/grovers-algorithm-quantum-leap-in-search-efficiency-996023862769
