양자 알고리즘 개요 — 언제 고전보다 빠른가
지난 4편까지 우리는 양자컴퓨터의 기초를 다졌습니다. 큐비트가 중첩 상태로 여러 값을 동시에 가질 수 있고, 얽힘으로 큐비트들이 서로 연결되며, 양자 간섭을 통해 정답의 확률을 높일 수 있다는 것을 배웠습니다. 하지만 여기서 자연스럽게 떠오르는 질문이 있습니다. 그래서 양자컴퓨터가 모든 문제를 빠르게 풀까요?
답은 아니오입니다. 양자컴퓨터의 속도 향상은 '특정 구조를 가진 문제'에만 적용됩니다. 암호 해독, 데이터 검색, 분자 시뮬레이션 같은 특정 영역에서는 고전 컴퓨터를 압도하지만, 대부분의 일상적인 계산 문제에서는 고전 컴퓨터와 큰 차이가 없습니다. 이 경계를 이해하는 것이 양자컴퓨팅의 실제 가능성과 한계를 아는 첫걸음입니다.
오늘은 계산 복잡도 이론의 렌즈를 통해, 양자 우위가 정확히 언제, 어떤 조건에서 발생하는지를 살펴봅시다.
계산 복잡도란 무엇인가
컴퓨터 과학에서 '복잡도'는 문제를 푸는 데 필요한 자원(시간, 메모리)을 의미합니다. 같은 문제도 알고리즘에 따라 걸리는 시간이 천차만별입니다. 예를 들어 100명 중에서 특정 사람을 찾는다고 생각해봅시다. 무작정 한 명씩 확인하면 최악의 경우 100번을 확인해야 합니다. 하지만 이름순으로 정렬된 명단이 있다면 이진 검색으로 약 7번만 확인하면 됩니다. 같은 검색 문제인데도 알고리즘에 따라 효율이 달라집니다.
계산 복잡도 이론은 이런 '자원 소비의 본질적 한계'를 분류합니다. 어떤 문제는 다항식 시간(polynomial time) 안에 풀 수 있고, 어떤 문제는 지수 시간(exponential time)이 필요합니다. 이 분류가 중요한 이유는, 문제의 크기가 커질수록 이 차이가 극적으로 벌어지기 때문입니다. 크기 100인 문제에서 다항식과 지수 알고리즘의 차이는 크지만, 크기 1000인 문제에서는 지수 알고리즘은 사실상 불가능해집니다.
P, NP, BQP — 세 가지 복잡도 클래스
계산 복잡도 이론의 세 핵심 클래스를 이해하면, 양자컴퓨터가 할 수 있는 것과 할 수 없는 것이 명확해집니다.
P 클래스 (Polynomial time)는 고전 컴퓨터가 다항식 시간 안에 '풀 수 있는' 문제들입니다. 정렬, 최단 경로 찾기, 소수 판별(현대적 알고리즘) 등이 여기 속합니다. 크기 n인 문제를 푸는 데 n², n³, n⁵ 같은 시간이 걸리는 문제들이죠. 일반적으로 '효율적으로 풀 수 있다'고 간주하는 문제들입니다.
NP 클래스 (Nondeterministic Polynomial time)는 고전 컴퓨터가 '검증하기는 쉽지만 풀기는 어려운' 문제들입니다. 가장 유명한 예가 외판원 문제(Traveling Salesman Problem, TSP)입니다. 100개 도시를 모두 방문하는 최단 경로를 찾는 것은 어렵지만, 누군가 경로를 제시하면 그것이 최단인지 확인하는 것은 쉽습니다. 다른 예로는 큰 수의 인수분해(어떤 두 소수의 곱이 주어진 수와 같은지 확인하는 것은 쉽지만, 인수를 찾는 것은 어렵다)가 있습니다.
P와 NP의 관계는 컴퓨터 과학의 가장 큰 미해결 문제입니다. P = NP인가? 즉, 검증하기 쉬운 모든 문제가 풀기도 쉬울까요? 일반적인 믿음은 '아니다'이지만, 아직 증명되지 않았습니다.
BQP 클래스 (Bounded-error Quantum Polynomial time)는 양자컴퓨터가 다항식 시간 안에 '높은 확률로 풀 수 있는' 문제들입니다. 핵심은 '높은 확률'이라는 부분입니다. 양자컴퓨터는 확률적 답변을 제공하므로, 오류 확률이 1/3 이하인 답을 다항식 시간에 얻을 수 있는 문제들이 BQP에 속합니다.
양자 우위가 발생하는 조건
이제 핵심 질문으로 돌아옵시다. 양자컴퓨터는 언제 고전 컴퓨터보다 빠를까요?
첫 번째 조건은 문제의 구조입니다. 양자컴퓨터는 특정 구조를 가진 문제에만 우위를 보입니다. 이 구조란 무엇일까요?
주기 찾기(Period Finding)를 생각해봅시다. 어떤 함수가 주기적인 패턴을 반복한다면, 그 주기를 찾는 것이 문제입니다. 고전 컴퓨터는 함수를 여러 번 호출해야 하지만, 양자컴퓨터는 양자 푸리에 변환(Quantum Fourier Transform, QFT)이라는 기법으로 주기를 한 번에 찾을 수 있습니다. 이것이 Shor 알고리즘(소인수분해 알고리즘)의 핵심입니다.
검색(Search)도 양자 우위가 있는 영역입니다. 정렬되지 않은 데이터베이스에서 특정 항목을 찾는 경우, 고전 컴퓨터는 평균적으로 N/2번을 확인해야 합니다. 하지만 Grover 알고리즘을 사용하면 양자컴퓨터는 √N번만 확인하면 됩니다. 100만 개 항목을 검색할 때 고전은 50만 번, 양자는 1000번이면 됩니다.
샘플링(Sampling)은 좀 더 미묘합니다. 특정 확률 분포에서 샘플을 뽑는 것이 문제인데, 양자컴퓨터는 양자 상태를 이용해 고전 컴퓨터보다 빠르게 샘플을 생성할 수 있습니다. 이것이 Google의 '양자 우월성' 주장의 기반이 되었습니다.
반대로 양자컴퓨터가 우위를 보이지 못하는 문제도 있습니다. 정렬, 그래프 경로 최적화, 대부분의 머신러닝 문제들은 현재까지 양자 알고리즘이 고전 알고리즘을 크게 능가하지 못합니다. 왜일까요? 이들 문제는 '특정 구조'가 없거나, 양자 간섭을 활용할 수 있는 패턴이 명확하지 않기 때문입니다.
Shor과 Grover — 양자 우위의 구체적 사례
Shor 알고리즘과 Grover 알고리즘은 양자 우위의 두 가지 대표적 사례입니다.
Shor 알고리즘은 1994년 피터 쇼어가 발표했습니다. 이 알고리즘은 큰 수의 소인수를 다항식 시간에 찾을 수 있습니다. 고전 컴퓨터는 2048비트 수를 인수분해하는 데 수백만 년이 걸리지만, 양자컴퓨터는 수시간이면 충분합니다. 이것이 현재의 RSA 암호화를 위협하는 이유이며, 양자 내성 암호(Post-Quantum Cryptography) 개발을 촉발한 원인입니다.
Grover 알고리즘은 1996년 로브 그로버가 발표했습니다. 이 알고리즘은 정렬되지 않은 데이터베이스에서 검색을 √N 시간에 수행합니다. 고전 컴퓨터가 O(N) 시간이 필요한 것과 비교하면, 이는 제곱근만큼의 속도 향상입니다. Grover 알고리즘은 암호 해독, 데이터 마이닝, 최적화 문제에 광범위하게 적용될 수 있습니다.
두 알고리즘 모두 양자 간섭이 핵심입니다. Shor 알고리즘은 양자 푸리에 변환으로 주기를 간섭시켜 증폭하고, Grover 알고리즘은 진폭 증폭(Amplitude Amplification)으로 정답의 확률을 높입니다. 이들은 지난 4편에서 배운 '양자 간섭'이 실제로 어떻게 계산 속도를 높이는지 보여주는 구체적 사례입니다.
NISQ 단계에서의 현실
지금까지 우리가 논의한 Shor과 Grover 알고리즘은 '이상적인' 양자컴퓨터를 가정합니다. 하지만 현재 우리가 가진 양자컴퓨터는 NISQ(Noisy Intermediate-Scale Quantum) 단계에 있습니다. IBM, Google, IonQ 같은 기업들이 제공하는 양자컴퓨터는 수십 개에서 수백 개의 큐비트를 가지고 있지만, 오류율이 높고 데코히런스로 인해 계산 시간이 제한됩니다.
NISQ 단계에서는 완전한 Shor 알고리즘을 실행할 수 없습니다. 큰 수를 인수분해하려면 수천 개의 논리 큐비트가 필요하지만, 현재 양자컴퓨터는 물리 큐비트 수백 개로도 충분한 정확도를 유지하기 어렵습니다. 대신 NISQ 단계에서는 변분 양자 알고리즘(Variational Quantum Algorithm, VQA)과 QAOA(Quantum Approximate Optimization Algorithm) 같은 하이브리드 접근법이 주목받고 있습니다. 이들은 양자 회로와 고전 최적화를 결합하여, 현재의 노이즈 있는 양자컴퓨터에서도 실용적인 결과를 얻으려고 합니다.
즉, 이론적 양자 우위와 실제 양자컴퓨터 사이에는 큰 간격이 있습니다. 양자 우위는 충분히 큰 오류 정정 능력을 갖춘 양자컴퓨터가 나타날 때 비로소 현실화될 것입니다.
양자 우위가 불명확한 영역들
흥미롭게도, 양자컴퓨터가 우위를 보일 것으로 예상되지만 아직 증명되지 않은 문제들도 많습니다.
머신러닝과 데이터 분석은 양자컴퓨터의 유망한 응용 분야로 자주 언급됩니다. 양자 상태의 고차원 특성을 이용하면 데이터 패턴을 빠르게 찾을 수 있을 것 같습니다. 하지만 현재까지 양자 머신러닝 알고리즘이 고전 알고리즘을 명확히 능가하는 경우는 드뭅니다. 데이터를 양자 상태로 인코딩하는 것 자체가 비용이 크기 때문입니다.
분자 시뮬레이션은 다릅니다. 양자 시스템을 시뮬레이션하는 데 고전 컴퓨터는 지수 시간이 필요하지만, 양자컴퓨터는 다항식 시간에 할 수 있습니다. 이것은 '양자 시스템은 양자컴퓨터로 시뮬레이션하는 것이 자연스럽다'는 파인만의 직관과 일치합니다. 약물 설계, 배터리 개발, 촉매 설계 같은 산업 응용이 가능할 것으로 기대됩니다.
최적화 문제도 미묘합니다. 많은 실제 문제(포트폴리오 최적화, 로지스틱 최적화)는 NP-hard 범주에 속합니다. 양자컴퓨터가 이들을 완벽히 풀 수 있을지는 불명확하지만, 고전 휴리스틱보다 나은 근사해를 빠르게 찾을 수 있을 가능성이 있습니다.
왜 모든 문제에 양자 우위가 있지 않을까?
이 질문의 답은 근본적입니다. 양자컴퓨터의 우위는 '양자 간섭'이 의미 있게 작동할 수 있는 문제 구조에만 제한됩니다.
생각해봅시다. 양자 간섭은 정답의 진폭을 높이고 오답의 진폭을 낮추는 메커니즘입니다. 이것이 가능하려면 문제가 어떤 '대칭성'이나 '패턴'을 가져야 합니다. 주기 찾기는 주기라는 명확한 패턴이 있고, 검색은 정답이 하나라는 구조가 있습니다. 하지만 일반적인 최적화 문제나 정렬 문제는 이런 구조가 없습니다.
또 다른 이유는 양자 상태 인코딩의 비용입니다. 고전 데이터를 양자 상태로 변환하고, 계산 후 다시 고전 결과로 추출하는 과정 자체가 오버헤드를 만듭니다. 이 오버헤드가 양자 계산의 이득을 상쇄할 수 있습니다.
마지막으로, 측정의 확률성도 고려해야 합니다. 양자컴퓨터는 확률적 답변을 제공하므로, 높은 확률로 정답을 얻으려면 여러 번 실행해야 할 수 있습니다. 이것이 Grover 알고리즘의 √N 이득을 제한합니다.
산업과 투자의 관점
양자 우위의 경계를 이해하는 것은 투자 관점에서도 중요합니다. 현재 양자컴퓨팅 산업은 Shor 알고리즘의 위협(암호 해독)과 Grover 알고리즘의 가능성(검색, 최적화)을 중심으로 움직입니다.
IBM, Google, IonQ 같은 기업들은 NISQ 단계에서 실용적 가치를 찾기 위해 QAOA, VQA 같은 하이브리드 알고리즘에 투자하고 있습니다. 이들은 완벽한 양자 우위를 기대하기보다는, 고전 컴퓨터보다 10~20% 빠른 근사해를 찾는 것을 목표로 합니다. 금융 포트폴리오 최적화, 약물 발견, 배터리 설계 같은 산업 문제에서 이 수준의 개선도 상당한 경제적 가치를 만들 수 있습니다.
또한 양자 내성 암호(Post-Quantum Cryptography) 표준화가 진행 중입니다. NIST가 2022년 발표한 PQC 표준은 양자컴퓨터 시대에 대비하는 산업의 실질적 움직임을 보여줍니다. 이는 사이버 보안 기업들에게 새로운 기회를 제공합니다.
📚 관련 글
양자컴퓨터의 우위는 '모든 문제'가 아닌 '특정 구조를 가진 문제'에만 존재하며, 이 경계를 정확히 아는 것이 양자컴퓨팅의 실제 가능성을 판단하는 첫걸음입니다.
슈로 🐾