개념
양자역학의 중첩과 얽힘을 활용한 알고리즘. 1994년 쇼어가 고전 컴퓨터로 푼 수 없는 RSA를 풀 수 있음을 증명 — 인터넷 보안의 미래에 그림자가 드리움.
한 호흡으로 이해하기
"양자 중첩과 얽힘을 이용해 고전 컴퓨터로 불가능한 속도에 도달." 1994년 쇼어 알고리즘 — 큰 수 인수분해를 지수 시간 → 다항 시간. RSA 암호의 미래 위협. 1996년 그로버 알고리즘 — 검색 √N 가속. 양자 우위(quantum advantage)는 2019년 구글이 처음 시연.
한눈에 보기
알고리즘 | 문제 | 고전 시간 | 양자 시간 | 의미 |
|---|---|---|---|---|
Deutsch (1985) / Deutsch-Jozsa (1992) | f가 상수인지 균형인지 | O(2ⁿ⁻¹+1) | O(1) | 양자가 본질적으로 빠름 첫 증명 |
Shor (1994) | 큰 수 N 인수분해 | exp(O(n^(1/3))) | O(n³) | RSA·인터넷 암호 위협 |
Grover (1996) | 비정렬 데이터에서 검색 | O(N) | O(√N) | 검색 제곱근 가속 |
HHL (2009) | 선형방정식 Ax=b | O(N) | O(log N) | 머신러닝·시뮬레이션 가속 |
Quantum supremacy (Google 2019) | 랜덤 회로 샘플링 | ~10,000년 | 200초 | 양자 우위 첫 시연 |
문제 종류에 따라 양자가 지수 가속(Shor), 제곱근 가속(Grover), 동등(대부분의 일상 문제) — 모든 게 빨라지는 것은 아니다.
핵심 식
중첩 + 얽힘 = 지수적 가속
핵심 순간
도이치 — 양자 컴퓨터의 원형
데이비드 도이치가 양자 튜링 기계 개념 발표. 양자 컴퓨터의 이론적 시작.
쇼어 알고리즘 — RSA의 종말 예고
피터 쇼어가 큰 수를 빠르게 인수분해하는 양자 알고리즘 발견. 모든 RSA 암호가 위협받음.
그로버 — 제곱근 가속
암호 해독·검색에서 √N 가속. 대칭 키 암호의 키 길이를 두 배로 늘려야 함.
구글 — 양자 우월성 주장
Google Sycamore가 53큐비트로 고전 슈퍼컴퓨터로 1만 년 걸리는 작업을 200초에 수행. (논쟁적)
오늘날의 응용
포스트양자 암호(현재 암호 대체), 신약 개발 시뮬레이션, 최적화, 머신러닝(QML), 양자 화학.
MathVoyage 너머로
불러오는 중…