양자컴퓨팅, IT쟁이의 눈으로 다시 보기 (4)

Eng version ← Click!

눈에 자주 띄는 양자 알고리즘만 골라서 뜯어보기

양자컴퓨팅을 보다 보니 모르는 것들이 너무 많았다. 용어들과 친숙해지는 것도 어려웠지만, 알고리즘은 너무나도 생소하고 복잡해서 정리 한번 해야겠다고 생각했다.

그 많은 알고리즘을 다 살펴볼 수는 없고, 공부하다가 눈에 가장 많이 띄던 것들만 선별해서 살펴볼까 한다.

글로 얼마나 쉽게 풀어쓸 수 있을지 모르겠지만, 그림과 함께 설명하면 조금이라도 더 쉽게 풀리지 않을까? 알고리즘이 복잡하긴 해도, 어떤 목적으로 쓰는지를 알고 회로도를 이해하면 어떤 원리로 목적한 바를 만들어내는지 알 수 있겠다는 생각으로 써 내려가 본다.

물론 수학적인 접근도 좋지만, 나는 IT쟁이니까.

Essential Algorithm

가장 기본? 하지만 정말 중요한 알고리즘 두 개만 살펴보고자 한다.

• QFT
• QPE

QFT (Quantum Fourier Transform)

데이터를 파동의 위상(phase) 정보로 변환하여 양자 상태의 중첩(superposition) 안에 저장한다. 즉, 큐비트의 진폭(Amplitude)으로 표현되던 0과 1의 정보를 복소수 평면상의 위상(Phase) 각도로 매핑.

쉽게 표현하면, 데이터를 위상으로 바꿈.

Use Cases

• 양자 알고리즘을 구축하기 위한 핵심 엔진
• Shor’s Algorithm: 거대한 수의 소인수분해를 고전 컴퓨터보다 월등히 빠르게 처리
• QPE (Quantum Phase Estimation): 특정 양자 연산의 위상을 찾아냄. 양자 화학이나 HHL 알고리즘의 기반

QFT Circuit

📷 이미지 ② — QFT 회로

1. q_2가 H게이트를 통과하며 중첩 상태가 됨
2. q_1의 값이 1이라면 q_2의 위상을 90도 회전시킴 — P(pi/2). q_1의 값이 0이라면 아무 일도 발생하지 않음
3. q_0의 값이 1이라면 q_2의 위상을 45도 회전시킴 — P(pi/4). q_0의 값이 0이라면 아무 일도 발생하지 않음. q_2의 위상(가능한 각도): (0, 45, 90, 135, 180, 225, 270, 315)
4. q_1이 H게이트를 통과하며 중첩 상태가 됨
5. q_0의 값이 1이라면 q_1의 위상을 90도 회전시킴 — P(pi/2). q_0의 값이 0이라면 아무 일도 발생하지 않음. q_1의 위상(가능한 각도): (0, 90, 180, 270)
6. q_0이 H게이트를 통과하며 중첩 상태가 됨. q_0의 위상(가능한 각도): (0, 180)
7. q_0과 q_2의 상태를 서로 교환

최종적으로 위의 QFT circuit을 통과하면

• q_0의 위상은 (0, 45, 90, 135, 180, 225, 270, 315)
• q_1의 위상은 (0, 90, 180, 270)
• q_2의 위상은 (0, 180)

QPE (Quantum Phase Estimation)

위상(Phase)을 찾아내어 디지털 데이터(0과 1)로 추출해 내는 알고리즘. 방향으로 보면 QFT의 반대다. QFT가 데이터를 위상으로 바꾼다면, QPE는 위상을 데이터로 읽어낸다. (실제로 QPE 회로 안에는 역 QFT가 핵심 부품으로 들어가 있다.)

Use Cases

• Shor’s Algorithm: 소인수분해를 위해 함수의 주기(Period)를 알아내는 핵심 엔진
• 양자 화학 및 물질 시뮬레이션: 분자나 원자의 바닥 상태 에너지를 매우 정밀하게 계산
• HHL 알고리즘: 선형 방정식을 풀기 위해 행렬의 고유값을 찾아 역수를 취하는 과정의 기반

QPE Circuit

1. q_0이 H게이트를 통과하며 중첩 상태가 됨. q_1이 H게이트를 통과하며 중첩 상태가 됨. q_2가 X게이트를 통과하며 값이 1이 됨
2. q_0이 1일 때 타겟인 q_2에 P(pi/2) 회전 연산을 가함 (= q_0의 위상을 90도 회전시킴). q_2가 X게이트 때문에 1이 되었기 때문에 P에서 Phase kickback이 일어나, q_2의 위상은 바뀌지 않고 q_0의 위상이 바뀌게 됨. P게이트가 1을 만나면 Phase kickback을 일으킴 (각 게이트마다 조건이 다 다름 = 복잡). q_0이 0이라면 아무 일도 발생하지 않음. q_0의 위상: (90) — 기준점인 0도는 생략하고 q_0의 상대위상이 90도로 확정되었다고 표현
3. q_1이 1일 때 타겟인 q_2에 P(pi) 회전 연산을 가함. 역시 Phase kickback으로 q_2의 위상은 바뀌지 않고 q_1의 위상이 180도 회전함. q_1이 0이라면 아무 일도 발생하지 않음. q_1의 위상: (180)
4. q_0과 q_1의 위상을 서로 맞바꿈. q_0의 위상: (180), q_1의 위상: (90)
5. q_1이 H게이트를 통과하며 위상을 값으로 변환시킴. q_1은 H게이트를 두 번째 통과했기 때문에 위상은 없어지고 값을 갖게 됨. 90도의 위상을 가진 q_1이 중첩 상태가 되었기에 간섭 효과로 인해 파동이 요동치게 됨. q_0: 180, q_1: 위상 측정 불가
6. q_0이 1이라면 q_1의 위상을 -90도 회전시킴 — P(-pi/2). q_1은 q_0과 위상을 맞바꾸었고 과거 q_0에는 P(pi/2) 영향이 있었기 때문에, P(-pi/2)를 통해 과거 영향을 받았던 90도의 잡음을 상쇄시켜 q_1의 파동을 정리해줌. q_0: 180, q_1: 위상 측정 불가
7. q_0이 H게이트를 통과하며 위상을 값으로 변환시킴. q_0은 H게이트를 두 번째 통과했기 때문에 위상은 없어지고 값을 갖게 됨. q_0: 위상 측정 불가, q_1: 위상 측정 불가
8. q_0과 q_1의 상태를 M게이트를 통해 읽어냄 = c: 0 1에 저장. q_0: 위상 소멸, q_1: 위상 소멸

NISQ (Noisy Intermediate Scale Quantum)

슈퍼컴퓨터를 뛰어넘을 잠재력은 있지만, 아직 에러를 스스로 고치지 못해 계산을 길게 할 수 없는 불완전한 상태의 양자 컴퓨터라고 이해하면 될 것 같다.

이 시대의 대표적인 사용법이 바로 하이브리드 알고리즘이다. 양자 컴퓨터는 힌트만 던져주고, 복잡한 계산과 조율은 고전 컴퓨터에게 넘기는 방식.

아래의 알고리즘을 살펴보려고 한다.

• QAOA & LR-QAOA
• VQE & QC-AFQMC

QAOA & LR-QAOA

QAOA (Quantum Approximate Optimization Algorithm)

수많은 경우의 수 중에서 가장 좋은 해답을 찾는 조합 최적화(Combinatorial Optimization) 문제를 풀기 위해 고안된 하이브리드 양자 알고리즘.

양자 회로 내의 매개변수를 고전 컴퓨터의 Optimizer가 반복적으로 조정하면서, 정답이 나올 확률을 최대로 끌어올리는 방식으로 작동한다.

Use Cases

• 물류 및 배송 경로 최적화 (Logistics): 수많은 배송지 중 가장 빠른 최단 경로 찾기
• 금융 포트폴리오 (Finance): 위험을 최소화하고 수익을 극대화하는 최적의 자산 배분 조합 찾기
• 스케줄링 (Scheduling): 공장 가동 시간이나 교대 근무표 등을 가장 효율적으로 짜는 작업

QAOA Circuit

• q_0이 H게이트를 통과하며 중첩 상태가 됨
• q_1이 H게이트를 통과하며 중첩 상태가 됨
• q_0이 1일 때 타겟인 q_1의 상태를 뒤집음 — CNOT
• q_1의 위상을 2γ(감마)만큼 회전시킴 — Rz(2*γ)
• q_0이 1일 때 타겟인 q_1의 상태를 다시 뒤집어 원래대로 복구함 — CNOT. 두 큐비트의 상태가 서로 다를 때(01, 10)와 같을 때(00, 11)를 구분해 냄
• 문제의 조건에 맞춰 파동에 γ(감마)라는 페널티 혹은 보상 위상(점수)을 부여
• q_0이 Rx(2*β) 게이트를 통과하며 파동이 섞임
• q_1이 Rx(2*β) 게이트를 통과하며 파동이 섞임. Rx 게이트는 β(베타)라는 각도를 사용해 위상을 섞어 간섭 효과를 일으킴. 간섭 효과를 통해 오답 파동은 상쇄 간섭으로 지우고, 정답 파동은 보강 간섭으로 증폭시킴

LR-QAOA (Linear Ramp Quantum Approximate Optimization Algorithm)

기존 QAOA는 Layer를 거칠 때마다 고전 컴퓨터가 가장 좋은 감마와 베타 각도를 찾기 위해 수많은 반복 최적화를 거쳐야 했다. 이 과정이 시간적, 자원적 병목이 되는 건 당연하다.

반면, LR-QAOA는 이 고전 컴퓨터의 뺑뺑이(최적화) 과정을 없애버린 버전이다.

대신, gamma 값은 0에서부터 일정하게 증가시키고, beta 값은 최대치에서 0으로 일정하게 감소시키는, 미리 정해진 직선 코스(Linear Ramp)를 큐비트들에게 대입한다.

Use Cases

• Overhead Free Optimization: 고전 컴퓨터의 개입 없이, 미리 짜인 램프 스케줄대로 회로를 한 번에 쭉 실행하여 물류, 금융 등의 최적화 문제를 훨씬 적은 시간에 풀어낼 때 사용
• Scalable Quantum Benchmarking: 파라미터를 무작위로 찾는 변수가 없고 결과가 결정론적이기 때문에, 서로 다른 양자 컴퓨터(IBM, IonQ, Quantinuum 등)에 똑같은 스케줄의 LR-QAOA를 돌려보고 ’어떤 하드웨어가 더 깊은 회로를 에러 없이 버티는가?’를 비교하는 Stress Test 도구로 쓰임

VQE & QC-AFQMC

VQE (Variational Quantum Eigensolver)

양자 컴퓨터와 고전 컴퓨터가 협력하여, 복잡한 시스템의 가장 안정적인 상태(최저 에너지 상태, 즉 바닥 상태)를 찾는 하이브리드 양자 알고리즘.

고전 컴퓨터가 양자 회로의 파라미터를 반복적으로 조절하며, 에너지가 가장 낮게 나오는 최적의 양자 상태를 찾아내는 원리다.

Use Cases

• 양자 화학 (Chemistry): 복잡한 분자나 원자의 바닥 상태 에너지를 정확히 계산하여 화학 반응을 시뮬레이션
• 신소재 개발 (Novel Materials): 배터리, 촉매 등 고전 컴퓨터로는 구조를 계산하기 벅찬 새로운 물질이나 신약을 안정적으로 설계

VQE Circuit

• q_0이 Ry게이트를 통과하며 고전 컴퓨터가 정해준 각도(θ[0])만큼 Y축으로 회전함. 이 회전을 통해 q_0은 50:50 반반(H게이트)이 아니라, 각도에 비례하는 특정한 확률을 가진 중첩 상태가 됨
• q_1이 Ry게이트를 통과하며 고전 컴퓨터가 정해준 각도(θ[1])만큼 Y축으로 회전하여 특정한 확률을 가진 중첩 상태가 됨
• q_0이 1이라면 타겟인 q_1의 상태를 뒤집음 — CNOT. q_0이 0이라면 아무 일도 발생하지 않음
• 얽혀 있는 상태의 q_0이 두 번째 Ry게이트를 통과하며 새로운 각도(θ[2])만큼 한 번 더 회전함
• 얽혀 있는 상태의 q_1이 두 번째 Ry게이트를 통과하며 새로운 각도(θ[3])만큼 한 번 더 회전함

계산된 에너지가 최저점이 아니라면, 고전 컴퓨터가 θ[0]~θ[3]의 각도 값을 살짝 수정한 뒤 처음부터 다시 실행. 에너지가 더 이상 떨어지지 않을 때까지 무한 반복!

QC-AFQMC (Quantum-Classical Auxiliary-Field Quantum Monte Carlo)

양자 컴퓨터의 VQE 가설과 고전 컴퓨터의 계산 능력(AFQMC)을 결합한 하이브리드 알고리즘.

고전 컴퓨터가 사용하는 AFQMC라는 계산법은 분자의 에너지를 잘 맞추지만, 초기 방향성을 잡아줄 Trial State(초기의 가설)가 없으면 수학적 오류(부호 문제, sign problem)가 커지는 약점이 있다.

반대로 양자 컴퓨터(VQE)는 이런 복잡한 State는 잘 만들어 내지만, 노이즈가 많아서 끝까지 계산하면 값이 틀어진다.

작동 원리: 그래서 양자 컴퓨터(VQE)가 완벽에 가까운 가설 상태(Trial State)만 만들어내고, 고전 컴퓨터(AFQMC)가 그것을 넘겨받아 최종 에너지를 도출해 내는 방법.

Use Cases

• 강한 상관관계 물질 시뮬레이션 (Strongly Correlated Materials): 전자들끼리 서로 밀고 당기는 힘이 너무 복잡해서 기존 슈퍼컴퓨터로는 풀 수 없었던 전이 금속 화합물, 촉매, 고온 초전도체 등의 성질을 정확히 규명할 때 사용
• NISQ의 한계 돌파 (Overcoming NISQ): 양자 컴퓨터가 노이즈 때문에 VQE 단독으로는 완벽한 정답(화학적 정확도)을 내지 못하는 상황이라도, VQE가 기준만 잘 잡아주면 고전 AFQMC가 이를 보정하여 결과를 만들어줌. 즉, 현재의 불완전한 양자 컴퓨터로도 실용적인 결과를 뽑아낼 수 있게 해주는 고전+양자 연합군

FTQC (Fault Tolerant Quantum Computing)

에러가 발생하면 스스로 고치는 능력을 갖추어, 길고 복잡한 연산도 해내는 진짜 양자 컴퓨터. FTQC는 불안정한 Physical Qubit들을 하나로 뭉쳐서, 깨지지 않는 1개의 Logical Qubit를 만들어낸다.

흔히 사람들이 얘기하는 ‘RSA 암호 체계가 붕괴될 수 있다’, ‘cryptocurrency가 깨질 수 있다’ 같은 것들은 FTQC가 완성되면 일어날 수도 있다고들 하지만, 진짜로 그렇게 될지는 잘 모르겠다. 이미 양자내성암호(PQC) 표준화가 진행 중이기도 하고, 그때가 되면 암호화가 더 고도화되지 않을까?

FTQC에서는 아래의 알고리즘을 살펴보려고 한다.

• Shor’s Algorithm
• Grover’s Algorithm

Shor’s Algorithm

1994년 이 알고리즘을 발표한 수학자 Peter Shor의 이름에서 따왔다.

고전 컴퓨터로는 우주의 나이만큼 시간이 걸려도 풀기 힘든 큰 숫자의 소인수분해를, 양자 컴퓨터를 이용해 순식간에 풀어내는 전설적인 양자 알고리즘.

• 핵심 원리: 소인수분해라는 수학 문제를, 파동의 Period Finding이라는 물리학 문제로 변환
• QPE와 QFT가 핵심으로 사용됨. 복잡하게 얽힌 파동을 QFT에 통과시켜 위상값을 뽑아내고, 고전 컴퓨터가 이 값을 단서로 삼아 최종 소수를 계산함

Use Cases

• Breaking RSA Encryption: 가장 유명하고 치명적인 use case. 현재 전 세계의 은행, 이메일, HTTPS는 ’큰 숫자를 소인수분해하기 매우 어렵다’는 점에 의존하는 RSA 암호를 사용한다. 쇼어 알고리즘이 완성되는 순간, 지구상의 거의 모든 디지털 자물쇠가 열리게 된다고 한다
• Breaking ECC: 소인수분해뿐만 아니라, 비트코인 등 암호화폐에서 사용하는 타원곡선 암호(ECC)의 기반인 Discrete Logarithm Problem 역시 쇼어 알고리즘으로 풀어낼 수 있다고 한다
• Catalyst for Post Quantum Cryptography (PQC): 쇼어 알고리즘은 아직 하드웨어 한계(NISQ) 때문에 제대로 실행되지 않지만, 그 이론적 존재만으로도 전 세계 정부와 기업들이 양자 컴퓨터로도 뚫을 수 없는 양자내성암호(PQC)를 개발하고 표준화하려는 노력 중
• FTQC Benchmark: 쇼어 알고리즘은 에러 없이 수천, 수만 번의 양자 게이트 연산을 버텨야만 답을 낼 수 있다. 따라서 ’우리가 만든 양자 컴퓨터가 암호 해독 규모의 쇼어 알고리즘을 돌렸어’라는 말은, 곧 완벽한 에러 정정(QEC)이 가능한 진정한 FTQC 시대가 열렸음을 증명하는 뜻이기도 하다

Grover’s Algorithm

1996년 이 알고리즘을 고안한 컴퓨터 과학자 Lov Grover의 이름에서 유래했다.

정렬되지 않은 방대한 데이터베이스에서 원하는 정답을 찾을 때, 고전 컴퓨터보다 훨씬 빠르게 정답을 찾아내는 양자 탐색 알고리즘. (제곱근의 속도)

고전 컴퓨터가 100개의 상자를 하나씩 열어봐야 해서 최대 100번의 시도가 필요하다면, 그로버 알고리즘은 단 10번 만에 정답을 찾아낼 수 있다.

• 핵심 원리: Amplitude Amplification. 모든 데이터를 중첩 상태로 깔아놓은 뒤, Oracle이라는 장치가 정답의 파동(위상)만 반대로 뒤집는다. 그리고 Diffuser라는 장치가 파동들의 평균을 기준으로 뒤집힌 파동을 반사시켜, 오답들의 확률은 깎아내고 정답의 확률(진폭)만 증폭시킨다. 이 과정을 몇 번 반복하면 정답 확률이 거의 100%에 도달한다

Use Cases

• Unstructured Database Search: Index나 규칙 없이 뒤죽박죽 섞여 있는 데이터 더미에서 특정한 조건에 맞는 데이터를 찾을 때 사용
• Symmetric Key & Hash Cryptanalysis: 쇼어 알고리즘이 RSA를 부순다면, 그로버 알고리즘은 AES 같은 대칭키 암호나 SHA 같은 해시 함수를 위협한다. 비밀번호를 무작위로 대입해서 푸는 시간(Brute-force attack)을 제곱근으로 단축시켜버리기 때문에, 보안 업계는 그로버 알고리즘에 대비해 기존 암호키의 길이를 두 배(예: AES-128에서 AES-256으로) 늘려서 대응하고 있다
• Speeding up NP-Complete Search: 외판원 순회 문제(가장 짧은 배달 경로 찾기), 스케줄링, 스도쿠 퍼즐처럼 경우의 수는 미친 듯이 많은데 딱 떨어지는 공식이 없는 문제들의 무차별 탐색을 제곱근 수준으로 단축하는 데 쓰임
• Quantum Machine Learning Subroutines: 머신러닝에서 패턴을 인식하거나 Anomaly를 탐지할 때, 방대한 특징(Feature) 공간을 탐색하는 시간을 크게 줄여주는 엔진 역할

후하~~~ 길고 긴 호흡이었다. 쳐다보면 쳐다볼수록 할게 더 늘어나는거 같다.

QC연구한 사람들, 정말 존경스럽다. 진짜 미치지 않고서야…..

Part 5 ← Click!