양자 컴퓨팅 10 - Quantum Algorithm(Deutsch's algorithm)

양자 컴퓨팅 포스트 보러가기

0. Introduction

지난 포스트에서는 노이즈 채널에서의 큐비트의 오류를 교정하는 방법을 알아봤다.

이번에는 전통적인 알고리즘과 양자 알고리즘의 차이를 알아보고 그 알고리즘 중 하나를 알아본다.

우선 전통적인 컴퓨팅 알고리즘 중에는 유명한 것들이 있는데, 탐색 알고리즘이라든지 소인수 분해 등이 대표적이다.
다른 포스트에서 다룰 내용이지만 양자 컴퓨팅 알고리즘을 사용하면 이 문제들을 더 빠른 시간 내에 해결할 수 있다.

1. P vs NP

우선 알고리즘을 논하기 전에 복잡도 분류체계를 알아보고자 한다.

밀레니엄 문제로 잘 알려진 P-NP 문제라는 것이 있다. 그 P와 NP이다.

P 문제란, 다항시간 내에 답을 얻어낼 수 있는 문제를 말한다.(예를 들어, n*n 행렬곱 문제)
NP 문제란, 주어진 예시 답안에 대해서 이 예시 답안이 문제의 정답이 될 수 있는 지를 다항시간 내에 얻어낼 수 있는 문제를 말한다. (예를 들어, 논리 연산)

쉽게 말해, P 문제는 다항시간 알고리즘이 있는 문제, NP 문제는 다항시간 검산 알고리즘이 있는 문제를 말한다.

따라서 P 문제는 NP 문제라는 것을 자명하게 알 수 있다. (\(P\subset NP\))
하지만 NP 문제가 P 문제인 것은 밝혀지지 않았다. 증명할 수 있는지 없는지도 밝혀지지 않았다. (\(NP\subset(?) P\))
이를 밝히는 것이 P-NP 문제이다.

NP class를 세분화 해서 볼 수 있는데, NP-Hard라는 것과 NP-Complete라는 것이 있다.

NP-Complete는 NP이지만, NP-Hard가 NP인 것은 아니다.

NP-Hard 문제란, 모든 NP 문제가 다항시간 내에 환원(변환)될 수 있는 문제를 말한다.
예를 들어, A 문제가 B 문제를 풂으로서 해결될 수 있다면 A는 B로 환원될 수 있다고 말한다.
이 예시에서 알 수 있겠지만 NP-Hard는 적어도 NP보다 어렵다는 것을 알 수 있다.

NP-Complete 문제란, NP이면서 NP-Hard인 문제를 말한다.

이 문제 분류를 \(P\neq NP\)와 \(P=NP\)에 따라서 포함관계를 그려보면 아래 그림과 같다.

2. Deutsch’s algorithm

도이치 알고리즘은 현재 실용성은 거의 없다고 하지만, 첫 번째 양자 알고리즘이라는 것에서 의미가 있다.

이 알고리즘에서 측정하고자 하는 복잡도는 쿼리(Query) 복잡도이다.

• 문제를 해결하기 위해 얼마나 많은 질문이 필요한가?

도이치 알고리즘에서 해결하고자 하는 문제는 아래와 같다.
앨리스가 \(f:\{0,\ 1\} \rightarrow \{0,\ 1\}\)인 함수를 갖고 있을 때 우리는 이 \(f\)가 상수함수(constant)인지 균형함수(balanced)인지를 찾아내야하는 문제이다.
조건은 아래와 같다.

• \(f(0)\)이나 \(f(1)\)의 값을 앨리스에게 물어봐 답을 얻을 수 있다.
• 질문과 답 한 쌍은 1개의 쿼리 비용을 소모한다.

여기서 말하는 상수함수는 input에 관계없이 항상 0 또는 1인 함수를 말하고, 균형함수는 input에 대한 output의 0과 1의 비율이 동일한 함수를 말한다.

앨리스가 가진 함수의 유형은 아래 표와 같이 총 네 가지 경우가 존재한다.

	input : 0	input : 1	Constant/Balanced
\(f_0\)	0	0	Constant
\(f_1\)	1	1	Constant
\(f_2\)	0	1	Balanced
\(f_3\)	1	0	Balanced

위 표를 보면 알 수 있겠지만, 우리의 생각으로 보나 고전적인 컴퓨터로 문제를 해결하는 경우나 모두, 함수의 유형을 결정하기 위해서는 적어도 2회 이상의 질의가 필요하다.

도이치 알고리즘에서는 이 문제를 어떻게 해결할지 알아보자.

2-1. Quantum version

도이치 알고리즘에서는 다음과 같은 양자 게이트를 도입한다.

위 게이트를 기반으로 아래와 같은 회로를 구성하면 1회의 쿼리로 이 문제를 해결할 수 있다.

수식으로 정리해보면 아래와 같다.
Input qubits에 Hadamard게이트를 통과시키면, \((H\otimes H)(|01>) = |+-> = \frac{1}{2}(|00>-|01>+|10>-|11>)\) 이고,
\(F_i\)게이트를 통과키시면,

\(\begin{align} &(F_i)(\frac{1}{2}(|00>-|01>+|10>-|11>)) \notag \\ &=\frac{1}{2}(|0f_i(0)>-|0(1\oplus f_i(0))>+|1f_i(1)>-|1(1\oplus f_i(1))>) \notag \\ &=\frac{1}{2}(|0(f_i(0)-1\oplus f_i(0))>+|1(f_i(1)-1\oplus f_i(0))>) \notag \\ &=\frac{1}{2}(|0>\otimes (-1)^{f_i(0)}(|0>-|1>) + |1>\otimes (-1)^{f_i(1)}(|0>-|1>)) \notag \\ &=\frac{1}{\sqrt{2}}((-1)^{f_i(0)}|0>+(-1)^{f_i(1)}|1>)\otimes \frac{1}{\sqrt{2}}(|0>-|1>) \notag \\ \end{align}\)

라는 결과를 얻게 되고 첫 번째 큐비트를 H게이트에 통과시키면 아래 표와 같은 결과를 얻을 수 있다.

	input : 0	input : 1	\(1^{\mathrm{st}}\)qubit	Constant/Balanced
\(f_0\)	0	0	$$|0>$$	Constant
\(f_1\)	1	1	$$-|0>$$	Constant
\(f_2\)	0	1	$$|1>$$	Balanced
\(f_3\)	1	0	$$-|1>$$	Balanced

위 표를 보면 알겠지만, 첫 번째 큐비트의 측정 결과가 0이면 상수함수, 1이면 균형함수라고 말 할 수 있다.
따라서 오직 1개의 질의만으로 문제를 해결할 수 있게 된다.

2-2. Deutsch-Jozsa’s algorithm

도이치 알고리즘은 2개의 질의 -> 1개의 질의로 비용을 줄인 알고리즘이다. 하지만 이는 그렇게 효율적인 것으로 보이지 않는다.
그렇다면 이 알고리즘을 일반화 하여 n개의 input에 대한 문제로 확장하여 함수 \(f:\{0,\ 1\}^n \rightarrow \{0,\ 1\}\)의 유형을 결정하는 문제로 만든다면 이를 해결하는 효율적인 알고리즘을 떠올릴 수 있다.

이 문제를 고전적인 방식으로 해결하려고 한다면, 적어도 \(2^{n-1}+1\)회의 질의가 필요할 것이다. 하지만 도이치-조사 알고리즘에 따르면 1회의 쿼리만으로 문제를 해결할 수 있음이 밝혀졌다.
이는 지수적인 속도 향상을 의미한다.

이에 대한 자세한 과정은 다음 포스트에서 n-큐비트 H게이트 변환에 대해서 알아보고 다루도록 하겠다.

후기)드디어 양자 컴퓨팅의 알고리즘에 대해서 다뤘는데요, 아직까지는 쉬운 내용에 속합니다. 뒷부분부터는 살짝 이해하기가 어렵더군요. 하지만 수식으로 따라가다보면 받아들일 수 있을 겁니다.

오타 혹은 잘못된 정보가 있다면 댓글 이메일 등등으로 알려주시면 감사하겠습니다. (꾸벅)