이 포스트의 내용은 Qiskit Textbook | Quantum States and Qubits - The Case for Quantum을 통해 공부한 흔적임을 밝힙니다.

양자 컴퓨팅을 사용하면 고전적인 컴퓨터로는 풀 수 없던 어떤 문제를 해결할 수 있다.
이것을 이해하기 위해서는 그런 문제를 해결하는데 얼마나 많은 컴퓨팅적 노력이 필요한지 고려해야 한다.

덧셈의 복잡도

간단한 덧셈 알고리즘부터 살펴보자.

$n$자리 수의 덧셈은 한 자리의 두 숫자를 더하는 단순한 연산의 집합으로 이루어진다.
복잡도를 측정하기 위해서는 몇 개의 기본 덧셈이 존재하는지,
그리고 이것이 $n$과 어떤 관계가 있는지 생각해보아야 한다.
한 자리의 두 숫자를 더하는 기본 덧셈의 개수를 $c(n)$라고 하자.

최선의 경우, 받아올림이 없는 경우에는 오직 $n$번의 연산으로 충분하다.
최악의 경우, 매번 받아올림이 있다면 이에 대한 추가 연산으로 $2n$번의 연산이 필요하다.
즉, $n \leq c(n) \leq 2n$임을 알 수 있다.

빅 오 표기법 Big O Notation

$c(n)$은 $n$이 증가함에 따라 선형적으로 증가한다고 결론지을 수 있다.
좀 더 일반화하면, $n$에 대한 선형 함수를 통해 $c(n)$의 상한값을 찾을 수 있다.
상한값은 주로 빅 오 표기법으로 나타낸다.
$n$에 대한 선형 함수로 상한값을 구할 수 있다면 $O(n)$,
$n$에 대한 이차 함수로 상한값을 구할 수 있다면 $O(n^2)$, 이런 식이다.
이것은 입력값의 증가에 따른 자원/실행시간을 비교하는 데 유용하다.

몇 진법을 사용하는가에 따라 얼마나 걸리는지가 차이가 날 수 있지만
진법 변환은 선형적인 연산이기에 빅 오 표기법에서는 고려하지 않는다.

복잡성 이론 Complexity Theory

복잡성 이론은 알고리즘의 성능을 분석하는데 이용되는,
알고리즘 실행에 필요한 계산 노력에 대한 연구다.
어떤 문제를 해결할 수 있는 가장 복잡도가 낮은 알고리즘을 찾기 위해 복잡도를 측정한다.

덧셈의 복잡도가 $O(n)$이라는 것은 이미 알아 보았고,
곱셈의 경우 이보다 복잡해 $O(n^2)$의 복잡도를 가진다.
그런데 소인수분해의 경우 훨씬 더 복잡하다.
소인수분해의 잘 알려진 알고리즘은 $O(e^{n^{1/3}})$보다 복잡하다.
이것은 지수 복잡도를 가지고 있기에 입력값이 증가할수록 복잡도가 매우 빠르게 상승한다.
예를 들어,
2140324650240744961264423072839333563008614715144755017797754920881418023447140136643345519095804679610992851872470914587687396261921557363047454770520805119056493106687691590019759405693457452230589325976697471681738069364894699871578494975937497937
라는 숫자의 덧셈이나 곱셈은 일반 컴퓨터를 통해 빠르게 구할 수 있지만
이것의 소인수분해는 슈퍼컴퓨터로 2700년 걸린다.

공식적으로 알고리즘의 복잡도 정의는 사용되는 계산의 이론적 모델에 따라 달라진다.
각 모델에는 그 알고리즘이 수행하는 기본 연산 집합이 존재한다.
불리언 회로와 튜링 머신, 그리고 RAM은 각자 다른 기본 연산 집합을 가진다.
그런데 이들은 모두 이산값에 대한 이산화된 조작에 기반한 디지털 계산 모델로,
어느 하나가 다른 것을 시뮬레이션 하는 것은 쉽게 할 수 있다.
따라서 복잡도를 따질 땐 다른 모델의 특별한 경우를 고려하기 보다는
일반적으로 사용되는 디지털 컴퓨터의 복잡도를 이야기하는 걸로 충분하다.

디지털 컴퓨터를 넘어

현재로서는 디지털 컴퓨터의 연산이 가장 널리 사용되고 있지만,
연속적으로 변하는 매개변수의 정밀한 조작을 기반으로 하는 아날로그 컴퓨터와 같은
다른 형태의 컴퓨처도 연구되어 사용된 바 있다.
아날로그 컴퓨터는 디지털 컴퓨터에서 다루기 어려운 문제를 신속하게 풀 수 있었음에도 불구하고
매우 작고 감지가 불가능한 오류로 인해 계산이 망가질 수 있어 상용화되지는 못했다.

디지털 컴퓨터의 견고함과 아날로그 컴퓨터의 미묘한 조작을 결합하여
이상적인 계산 모델을 제안하기 위해 양자 역학을 살펴볼 수 있다.
큐비트는 이산적인 출력을 갖지만 연속 매개변수로만 기술될 수 있는 상태로 존재하기도 한다.
이는 양자 시스템이 가진 파동 입자 이중성의 한 사례다.

큐비트에 적용되는 게이트를 기본 연산으로 하는 양자 컴퓨터는
디지털도 아날로그도 아닌 고유한 것이라고 할 수 있다.
양자 컴퓨터는 디지털 컴퓨터와는 완전히 다른 복잡도를 가지고 문제를 해결할 것이며
기존 컴퓨터보다 기하급수적으로 빠르게 계산할 수 있는 유일한 기술이다.

양자 컴퓨터를 사용할 경우

큐비트와 양자 게이트를 사용할 때,
디지털과 아날로그의 고전적인 알고리즘과는 근본적으로 다른 새로운 알고리즘이 필요하다.

그것을 할 수 잇는 방법 중 하나로, 전역 속성을 결정할 수 있는 함수가 있는 경우가 있다.
예를 들어, 어떤 함수 $f(x)$가 최소가 되게 하는 $x$를 찾고 싶다거나
주기적인 함수 $f(x)$의 주를 찾고 싶은 경우가 있을 수 있다.
디지털 컴퓨터 알고리즘에서는 전역 속성에 대한 충분한 정보를 얻기 위해
다양한 입력값을 일일이 넣어가며 계산해봐야 했지만
양자 컴퓨터에서는 중첩 상태를 생성해 많은 입력을 동시에 적용할 수 있다.
그렇다고 출력도 그렇게 한 번에 여러 개씩 얻을 수 있는 건 아니지만
찾고자 하는 전역 속성을 양자 간섭 효과를 통해 빠르게 찾아낼 수 있다.

그로버 알고리즘은 탐색 속도를 $O(N)$에서 $O(N^{(1/2)})$로 줄일 수 있으며
소인수분해 알고리즘의 경우 $O(e^{n^{1/3}})$보다 복잡하던 걸 $O(n^3)$으로 풀 수 있다.

디지털 알고리즘으로 풀 수 있는 문제를 덜 복잡하게 풀 수 있을 뿐만 아니라
양자 문제를 해결하는 데도 양자 알고리즘을 사용할 수 있다.
양자 상태 표현의 수는 큐비트가 늘어남에 따라 기하급수적으로 늘어난다.
따라서 이것을 디지털 컴퓨터에서 다루려면 비용이 많이 든다.
하지만 양자 컴퓨터에서는 $n$개의 큐비트를 표현하기 위해 $n$개의 큐비트로 충분하다.
따라서 이를 통해 분자 및 기본 입자 같은 양자 시스템을 연구하고 보다 잘 이해할 수 있다.