Quantum Algorithm (3) - Deutsch's algorithm
이번 게시글에서는 Quantum Algorithm 중 하나인 Deutsch's algorithm에 관해 알아봅니다.
1985년 David Deutsch가 발표한 Deutsch Algorithm은 양자컴퓨팅 역사에서 매우 중요한 이정표입니다. 이는 양자 알고리즘이 고전 알고리즘보다 빠를 수 있다는 것을 증명한 최초의 알고리즘 입니다. 비록 실용적인 응용을 하기에는 제한적인 알고리즘이지만, 양자컴퓨팅의 잠재력을 보여준 첫 번째 사례로서 의미가 있습니다.
Alice가 함수 f : { 0 , 1 } → { 0 , 1 } f: \{0,1\} \rightarrow \{0,1\} f : { 0 , 1 } → { 0 , 1 }
함수 f ( 0 ) f(0) f ( 0 ) f ( 1 ) f(1) f ( 1 ) 분류 f 0 f_0 f 0 0 0 상수함수 f 1 f_1 f 1 1 1 상수함수 f 2 f_2 f 2 0 1 균형함수 f 3 f_3 f 3 1 0 균형함수
상수함수 : 모든 입력에 대해 동일한 출력 (f 0 , f 1 f_0, f_1 f 0 , f 1 균형함수 : 절반의 입력은 0, 나머지 절반은 1을 출력 (f 2 , f 3 f_2, f_3 f 2 , f 3
문제
우리는 Alice가 가지고 있는 함수가 **상수함수(constant)**인지 **균형함수(balanced)**인지 판별해야 합니다.
고전적으로 이 문제를 해결하려면
f ( 0 ) f(0) f ( 0 ) 만약 f ( 0 ) = 0 f(0) = 0 f ( 0 ) = 0 f 0 f_0 f 0 f 2 f_2 f 2
둘을 구분하려면 f ( 1 ) f(1) f ( 1 )
의 과정을 거처야 하고, 이는 최소 2번의 Query가 필요 함을 의미합니다.
고전적 결정 트리 다이어그램
양자컴퓨팅에서는 모든 연산이 **가역적(reversible)**이어야 하므로, 단일 입력-출력 함수를 직접 구현할 수 없습니다. 대신 다음과 같은 양자 오라클을 구성합니다:
F i : ∣ x ⟩ ∣ y ⟩ → ∣ x ⟩ ∣ y ⊕ f i ( x ) ⟩ F_i: |x\rangle|y\rangle \rightarrow |x\rangle|y \oplus f_i(x)\rangle F i : ∣ x ⟩ ∣ y ⟩ → ∣ x ⟩ ∣ y ⊕ f i ( x )⟩
F_i quantum gate
여기서 ⊕ \oplus ⊕
각 오라클의 동작:
∣ 0 ⟩ ∣ 0 ⟩ → ∣ 0 ⟩ ∣ f i ( 0 ) ⟩ |0\rangle|0\rangle \rightarrow |0\rangle|f_i(0)\rangle ∣0 ⟩ ∣0 ⟩ → ∣0 ⟩ ∣ f i ( 0 )⟩ ∣ 0 ⟩ ∣ 1 ⟩ → ∣ 0 ⟩ ∣ 1 ⊕ f i ( 0 ) ⟩ |0\rangle|1\rangle \rightarrow |0\rangle|1 \oplus f_i(0)\rangle ∣0 ⟩ ∣1 ⟩ → ∣0 ⟩ ∣1 ⊕ f i ( 0 )⟩ ∣ 1 ⟩ ∣ 0 ⟩ → ∣ 1 ⟩ ∣ f i ( 1 ) ⟩ |1\rangle|0\rangle \rightarrow |1\rangle|f_i(1)\rangle ∣1 ⟩ ∣0 ⟩ → ∣1 ⟩ ∣ f i ( 1 )⟩ ∣ 1 ⟩ ∣ 1 ⟩ → ∣ 1 ⟩ ∣ 1 ⊕ f i ( 1 ) ⟩ |1\rangle|1\rangle \rightarrow |1\rangle|1 \oplus f_i(1)\rangle ∣1 ⟩ ∣1 ⟩ → ∣1 ⟩ ∣1 ⊕ f i ( 1 )⟩
Deutsch Algorithm의 핵심은 다음 양자 회로입니다:
Deutsch Algorithm Diagram
∣ 0 ⟩ |0\rangle ∣0 ⟩ ∣ 1 ⟩ |1\rangle ∣1 ⟩
그럼 이것이 어떻게 가능한지 자세히 살펴보도록 하겠습니다.
위의 다이어그램 그림을 보면 ∣ 01 ⟩ |01\rangle ∣01 ⟩ ∣ x ⟩ |x\rangle ∣ x ⟩ ∣ 0 ⟩ |0\rangle ∣0 ⟩ ∣ y ⟩ |y\rangle ∣ y ⟩ ∣ 1 ⟩ |1\rangle ∣1 ⟩
1단계: 초기 상태
∣ ψ 0 ⟩ = ∣ 0 ⟩ ∣ 1 ⟩ |\psi_0\rangle = |0\rangle|1\rangle ∣ ψ 0 ⟩ = ∣0 ⟩ ∣1 ⟩
2단계: Hadamard 게이트 적용
∣ ψ 1 ⟩ = H ∣ 0 ⟩ ⊗ H ∣ 1 ⟩ = 1 2 ( ∣ 0 ⟩ + ∣ 1 ⟩ ) ⊗ 1 2 ( ∣ 0 ⟩ − ∣ 1 ⟩ ) |\psi_1\rangle = H|0\rangle \otimes H|1\rangle = \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle) \otimes \frac{1}{\sqrt{2}}(|0\rangle - |1\rangle) ∣ ψ 1 ⟩ = H ∣0 ⟩ ⊗ H ∣1 ⟩ = 2 1 ( ∣0 ⟩ + ∣1 ⟩) ⊗ 2 1 ( ∣0 ⟩ − ∣1 ⟩)
= 1 2 ( ∣ 00 ⟩ − ∣ 01 ⟩ + ∣ 10 ⟩ − ∣ 11 ⟩ ) = \frac{1}{2}(|00\rangle - |01\rangle + |10\rangle - |11\rangle) = 2 1 ( ∣00 ⟩ − ∣01 ⟩ + ∣10 ⟩ − ∣11 ⟩)
Hadamard 게이트가 H = 1 2 ( 1 1 1 − 1 ) H = \frac{1}{\sqrt{2}} \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix} H = 2 1 ( 1 1 1 − 1 ) ∣ 0 ⟩ = ( 1 0 ) |0\rangle = \begin{pmatrix} 1 \\ 0 \end{pmatrix} ∣0 ⟩ = ( 1 0 ) ∣ 1 ⟩ = ( 0 1 ) |1\rangle = \begin{pmatrix} 0 \\ 1 \end{pmatrix} ∣1 ⟩ = ( 0 1 )
3단계: Oracle F i F_i F i
Oracle을 통과한 후:
∣ ψ 2 ⟩ = 1 2 ( ∣ 0 , f i ( 0 ) ⟩ − ∣ 0 , 1 ⊕ f i ( 0 ) ⟩ + ∣ 1 , f i ( 1 ) ⟩ − ∣ 1 , 1 ⊕ f i ( 1 ) ⟩ ) |\psi_2\rangle = \frac{1}{2}(|0,f_i(0)\rangle - |0,1 \oplus f_i(0)\rangle + |1,f_i(1)\rangle - |1,1 \oplus f_i(1)\rangle) ∣ ψ 2 ⟩ = 2 1 ( ∣0 , f i ( 0 )⟩ − ∣0 , 1 ⊕ f i ( 0 )⟩ + ∣1 , f i ( 1 )⟩ − ∣1 , 1 ⊕ f i ( 1 )⟩)
이를 정리하면:
∣ ψ 2 ⟩ = 1 2 ( ∣ 0 ⟩ ( ∣ f i ( 0 ) ⟩ − ∣ 1 ⊕ f i ( 0 ) ⟩ ) + ∣ 1 ⟩ ( ∣ f i ( 1 ) ⟩ − ∣ 1 ⊕ f i ( 1 ) ⟩ ) ) |\psi_2\rangle = \frac{1}{2}(|0\rangle(|f_i(0)\rangle - |1 \oplus f_i(0)\rangle) + |1\rangle(|f_i(1)\rangle - |1 \oplus f_i(1)\rangle)) ∣ ψ 2 ⟩ = 2 1 ( ∣0 ⟩ ( ∣ f i ( 0 )⟩ − ∣1 ⊕ f i ( 0 )⟩) + ∣1 ⟩ ( ∣ f i ( 1 )⟩ − ∣1 ⊕ f i ( 1 )⟩))
위상 킥백(Phase Kickback) 활용
핵심 관찰: ∣ f i ( x ) ⟩ − ∣ 1 ⊕ f i ( x ) ⟩ |f_i(x)\rangle - |1 \oplus f_i(x)\rangle ∣ f i ( x )⟩ − ∣1 ⊕ f i ( x )⟩
∣ f i ( x ) ⟩ − ∣ 1 ⊕ f i ( x ) ⟩ = ( − 1 ) f i ( x ) ( ∣ 0 ⟩ − ∣ 1 ⟩ ) |f_i(x)\rangle - |1 \oplus f_i(x)\rangle = (-1)^{f_i(x)}(|0\rangle - |1\rangle) ∣ f i ( x )⟩ − ∣1 ⊕ f i ( x )⟩ = ( − 1 ) f i ( x ) ( ∣0 ⟩ − ∣1 ⟩)
f i ( x ) f_i(x) f i ( x ) f i ( x ) = 0 f_i(x)=0 f i ( x ) = 0 ( ∣ 0 ⟩ − ∣ 1 ⟩ ) (|0\rangle - |1\rangle) ( ∣0 ⟩ − ∣1 ⟩) f i ( x ) = 1 f_i(x)=1 f i ( x ) = 1 ( ∣ 1 ⟩ − ∣ 0 ⟩ ) (|1\rangle - |0\rangle) ( ∣1 ⟩ − ∣0 ⟩)
어떻게 보면 부호 역할을 한다고 생각해도 좋습니다.
따라서:
∣ ψ 2 ⟩ = 1 2 ( ∣ 0 ⟩ ( ∣ f i ( 0 ) ⟩ − ∣ 1 ⊕ f i ( 0 ) ⟩ ) + ∣ 1 ⟩ ( ∣ f i ( 1 ) ⟩ − ∣ 1 ⊕ f i ( 1 ) ⟩ ) ) |\psi_2\rangle = \frac{1}{2}(|0\rangle(|f_i(0)\rangle - |1 \oplus f_i(0)\rangle) + |1\rangle(|f_i(1)\rangle - |1 \oplus f_i(1)\rangle)) ∣ ψ 2 ⟩ = 2 1 ( ∣0 ⟩ ( ∣ f i ( 0 )⟩ − ∣1 ⊕ f i ( 0 )⟩) + ∣1 ⟩ ( ∣ f i ( 1 )⟩ − ∣1 ⊕ f i ( 1 )⟩))
\left|0\right\rangle \otimes (-1)^{f_i(0)} (\left|0\right\rangle - \left|1\right\rangle) + \left|1\right\rangle \otimes (-1)^{f_i(1)} (\left|0\right\rangle - \left|1\right\rangle)
\right)
= 1 2 ( ( − 1 ) f i ( 0 ) ∣ 0 ⟩ + ( − 1 ) f i ( 1 ) ∣ 1 ⟩ ) ⊗ 1 2 ( ∣ 0 ⟩ − ∣ 1 ⟩ ) = \frac{1}{\sqrt{2}}((-1)^{f_i(0)}|0\rangle + (-1)^{f_i(1)}|1\rangle) \otimes \frac{1}{\sqrt{2}}(|0\rangle - |1\rangle) = 2 1 (( − 1 ) f i ( 0 ) ∣0 ⟩ + ( − 1 ) f i ( 1 ) ∣1 ⟩) ⊗ 2 1 ( ∣0 ⟩ − ∣1 ⟩)
4단계: 첫 번째 큐비트에 Hadamard 적용
F i F_i F i 1 2 ( ( − 1 ) f i ( 0 ) ∣ 0 ⟩ + ( − 1 ) f i ( 1 ) ∣ 1 ⟩ ) \frac{1}{\sqrt{2}}((-1)^{f_i(0)}|0\rangle + (-1)^{f_i(1)}|1\rangle) 2 1 (( − 1 ) f i ( 0 ) ∣0 ⟩ + ( − 1 ) f i ( 1 ) ∣1 ⟩)
Hadamard 게이트 적용:
H ⋅ 1 2 ( ( − 1 ) f i ( 0 ) ∣ 0 ⟩ + ( − 1 ) f i ( 1 ) ∣ 1 ⟩ ) H \cdot \frac{1}{\sqrt{2}}((-1)^{f_i(0)}|0\rangle + (-1)^{f_i(1)}|1\rangle) H ⋅ 2 1 (( − 1 ) f i ( 0 ) ∣0 ⟩ + ( − 1 ) f i ( 1 ) ∣1 ⟩)
= 1 2 ( ( − 1 ) f i ( 0 ) + ( − 1 ) f i ( 1 ) ) ∣ 0 ⟩ + 1 2 ( ( − 1 ) f i ( 0 ) − ( − 1 ) f i ( 1 ) ) ∣ 1 ⟩ = \frac{1}{2}((-1)^{f_i(0)} + (-1)^{f_i(1)})|0\rangle + \frac{1}{2}((-1)^{f_i(0)} - (-1)^{f_i(1)})|1\rangle = 2 1 (( − 1 ) f i ( 0 ) + ( − 1 ) f i ( 1 ) ) ∣0 ⟩ + 2 1 (( − 1 ) f i ( 0 ) − ( − 1 ) f i ( 1 ) ) ∣1 ⟩
※ ∣ + ⟩ |+\rangle ∣ + ⟩ ∣ − ⟩ |-\rangle ∣ − ⟩ ∣ 0 ⟩ |0\rangle ∣0 ⟩ ∣ 1 ⟩ |1\rangle ∣1 ⟩ ∣ + ⟩ = 1 2 ( ∣ 0 ⟩ + ∣ 1 ⟩ ) \left| + \right\rangle = \frac{1}{\sqrt{2}} \left( \left| 0 \right\rangle + \left| 1 \right\rangle \right) ∣ + ⟩ = 2 1 ( ∣ 0 ⟩ + ∣ 1 ⟩ ) ∣ − ⟩ = 1 2 ( ∣ 0 ⟩ − ∣ 1 ⟩ ) \left| - \right\rangle = \frac{1}{\sqrt{2}} \left( \left| 0 \right\rangle - \left| 1 \right\rangle \right) ∣ − ⟩ = 2 1 ( ∣ 0 ⟩ − ∣ 1 ⟩ )
함수 f i ( 0 ) f_i(0) f i ( 0 ) f i ( 1 ) f_i(1) f i ( 1 ) ( − 1 ) f i ( 0 ) + ( − 1 ) f i ( 1 ) (-1)^{f_i(0)} + (-1)^{f_i(1)} ( − 1 ) f i ( 0 ) + ( − 1 ) f i ( 1 ) ( − 1 ) f i ( 0 ) − ( − 1 ) f i ( 1 ) (-1)^{f_i(0)} - (-1)^{f_i(1)} ( − 1 ) f i ( 0 ) − ( − 1 ) f i ( 1 ) 측정 결과 f 0 f_0 f 0 0 0 1 + 1 = 2 1 + 1 = 2 1 + 1 = 2 1 − 1 = 0 1 - 1 = 0 1 − 1 = 0 0 f 1 f_1 f 1 1 1 − 1 + ( − 1 ) = − 2 -1 + (-1) = -2 − 1 + ( − 1 ) = − 2 − 1 − ( − 1 ) = 0 -1 - (-1) = 0 − 1 − ( − 1 ) = 0 0 f 2 f_2 f 2 0 1 1 + ( − 1 ) = 0 1 + (-1) = 0 1 + ( − 1 ) = 0 1 − ( − 1 ) = 2 1 - (-1) = 2 1 − ( − 1 ) = 2 1 f 3 f_3 f 3 1 0 − 1 + 1 = 0 -1 + 1 = 0 − 1 + 1 = 0 − 1 − 1 = − 2 -1 - 1 = -2 − 1 − 1 = − 2 1
첫 번째 큐비트를 관측하면 각각의 경우에 따라 다음과 같은 결과를 얻습니다.
위의 표를 보면, f 0 f_0 f 0 f 1 f_1 f 1 f 2 f_2 f 2 f 3 f_3 f 3
측정 결과에 따른 판별:
측정값 0 : 상수함수 (f 0 f_0 f 0 f 1 f_1 f 1 측정값 1 : 균형함수 (f 2 f_2 f 2 f 3 f_3 f 3
Quantum algorithm이 classical algorithm보다 더 적은 query로 해결이 가능했던 이유는 아래와 같습니다.
중첩 상태 활용 : 입력을 중첩 상태로 준비하여 모든 가능한 입력을 동시에 처리위상 정보 활용 : 함수값을 진폭의 위상으로 인코딩간섭 효과 : Hadamard 게이트를 통해 위상 정보를 측정 가능한 확률로 변환
방법 Query 복잡도 비고 고전적(classical) 2 최악의 경우 모든 입력을 확인해야 함 양자(quantum) 1 한 번의 Oracle 호출로 해결
Deutsch Algorithm은 Deutsch-Jozsa Algorithm 으로 일반화됩니다:
입력 : n n n f : { 0 , 1 } n → { 0 , 1 } f: \{0,1\}^n \rightarrow \{0,1\} f : { 0 , 1 } n → { 0 , 1 } 문제 : 함수가 상수함수인지 균형함수인지 판별고전 복잡도 : 최악의 경우 2 n − 1 + 1 2^{n-1} + 1 2 n − 1 + 1 양자 복잡도 : 1번의 Query
이는 양자컴퓨팅의 지수적 가속 을 보여주는 첫 번째 예시입니다.
이후 게시글에서 Deutsch-Jozsa Algorithm에 대해 더 자세히 다룰 예정입니다.
인위적 문제 : 실제 응용에서는 함수가 상수 또는 균형이라는 보장이 없음제한적 실용성 : 현실의 문제에 직접 적용하기 어려움오류 민감성 : 노이즈가 있는 환경에서는 우위가 감소
패러다임 전환 : 양자 알고리즘이 고전 알고리즘을 능가할 수 있음을 최초로 증명기법 개발 : 중첩과 간섭을 활용한 알고리즘 설계의 기본 패턴 제시이론적 기반 : Shor, Grover 등 후속 양자 알고리즘의 이론적 토대 마련
Deutsch Algorithm은 비록 간단하고 실용성이 제한적이지만, 양자컴퓨팅 분야에서 매우 중요한 위치를 차지합니다. 이 알고리즘을 통해 우리는:
양자 중첩 과 간섭 이 어떻게 계산적 우위를 만들어내는지 이해할 수 있습니다Query Complexity 관점에서 양자 알고리즘을 분석하는 방법을 학습할 수 있습니다더 복잡한 양자 알고리즘의 기본 구조와 원리를 파악할 수 있습니다
양자컴퓨팅을 처음 접하는 학습자에게 Deutsch Algorithm은 양자 세계의 신비로운 힘을 처음으로 체험할 수 있는 관문과 같은 존재입니다. 비록 작은 문제이지만, 그 안에는 양자컴퓨팅의 핵심 아이디어들이 모두 담겨 있습니다.
양자 알고리즘 타임라인
