양자역학 레포트 - 양자컴퓨터의 핵심 알고리즘과 그 응용 사례를 설명하시오.

I. 서론

양자 알고리즘을 배우기 전에는 큐비트를 많이 모으면 계산이 자동으로 빨라질 거라고 생각했다. 알고리즘을 하나씩 따라가 보니 속도를 만드는 쪽은 하드웨어 숫자보다 문제 구조와 회로 설계였다. 같은 중첩을 써도 어떤 문제에서는 큰 이득이 생기고, 다른 문제에서는 고전 계산보다 나을 이유가 없다. 양자컴퓨터의 대표 알고리즘을 이해할 때도 이름을 외우기보다 어떤 수학적 구조를 이용해 어떤 진폭을 키우는지 보는 편이 훨씬 잘 남는다. 쇼어와 그로버는 이론적 양자 가속을 보여 주는 대표 사례이고, VQE와 QAOA는 현재의 잡음 많은 장비에서 실험되는 하이브리드 알고리즘이라는 점에서 서로 역할이 다르다.

II. 본론

1) 주기와 진폭을 이용하는 쇼어·그로버 알고리즘

쇼어 알고리즘은 큰 정수의 소인수분해를 양자컴퓨터에서 다항 시간에 처리할 수 있음을 보여 준 알고리즘이다. 핵심은 숫자를 직접 하나씩 나눠 보는 데 있지 않고, 소인수분해 문제를 특정 함수의 주기를 찾는 문제로 바꾸는 데 있다. 양자 회로는 여러 입력을 중첩으로 준비하고 함수값과 얽히게 한 뒤 양자 푸리에 변환을 이용해 주기와 관련된 정보를 측정 확률에 모은다. 측정 결과를 고전 계산으로 후처리하면 원래 정수의 인수를 찾을 수 있다. 공개키 암호 일부가 인수분해 난이도에 기대고 있기 때문에 쇼어 알고리즘은 암호학에서 특히 큰 의미를 갖는다.

쇼어 알고리즘의 유명세 때문에 양자컴퓨터가 현재 암호를 곧바로 깨는 듯한 오해도 생긴다. 실제로는 큰 수를 다루려면 오류정정된 논리 큐비트와 매우 긴 회로를 안정적으로 실행할 수 있어야 한다. 현재 장비는 그 수준에 이르지 못했다. 그래도 알고리즘의 이론적 의미는 분명하다. 고전적으로 어려운 문제의 복잡도 등급을 양자 계산이 바꿀 수 있다는 사실을 구체적으로 보여 줬기 때문이다. 보안 분야가 양자내성암호 전환을 서두르는 배경도 장기적으로 이 가능성을 무시하기 어렵기 때문이다.

그로버 알고리즘은 구조가 다른 탐색 문제를 다룬다. N개의 후보 가운데 조건을 만족하는 항목을 찾을 때 고전적인 무작위 탐색은 평균적으로 N에 비례하는 확인이 필요하지만 그로버 알고리즘은 약 제곱근 N번 수준의 질의로 답을 찾을 수 있다. 방법은 정답 상태의 위상을 뒤집는 오라클과 평균을 기준으로 진폭을 반사시키는 연산을 번갈아 적용하는 것이다. 반복할수록 정답 상태의 진폭이 커져 측정했을 때 정답이 나올 확률이 높아진다. 지수적 가속은 아니지만 매우 큰 탐색공간에서는 제곱근 수준의 차이도 상당하다.

2) 현재 장비에 맞춘 VQE와 QAOA의 반복 구조

VQE는 분자와 물질의 바닥상태 에너지를 구하는 문제에서 많이 연구된다. 양자컴퓨터가 매개변수화된 회로로 시험 상태를 만들고 해밀토니안의 기댓값을 측정하면, 고전 최적화기가 에너지가 더 낮아지도록 매개변수를 바꾼다. 양자와 고전 계산이 번갈아 돌아가는 구조다. 변분 원리에 따르면 시험 상태의 에너지는 실제 바닥상태 에너지보다 낮아질 수 없으므로 최적화를 잘하면 바닥상태에 가까운 값을 찾을 수 있다. 이 방식은 회로를 비교적 얕게 설계할 수 있어 현재 장비에서 실험하기 좋다는 장점이 있다.