도이치–조사 알고리듬 은 1992년 데이비드 도이치 와 리처드 조사가 제안하고 1998년 리차드 클리브, 아서 에케르트, 키아라 맥카벨로 및 마이클 모스카가 개선한 결정론적 양자 알고리듬이다.[1] [2] 기하급수적으로 빠른 양자 알고리듬의 첫 번째 예 중 하나로 역사적인 의미가 있다.[3]
도이치-조사 알고리듬으로 푸는 문제는, 양자 알고리듬에는 쉽고 결정적 고전 알고리듬에는 어렵도록 의도적으로 설계된 문제이다. 이는 양자 컴퓨터로 오류 없이 효율적으로 해결할 수 있는 블랙박스 문제인 반면, 결정론적 고전 컴퓨터는 문제를 해결하기 위해 블랙박스에 대한 기하급수적인 쿼리가 필요하다. 보다 자세히 설명하면, 양자 컴퓨터에서 다항식 시간 내에 정확하게 해결할 수 있는 문제 클래스인 EQP 와 P [4]
이 문제는 확률적 고전 컴퓨터에서 해결하기 쉽기 때문에 확률적 고전 컴퓨터에서 다항식 시간의 유계 오류로 해결할 수 있는 문제 클래스인 BPP BQP BPP 사이에 오라클이 분리되는 문제의 예이다.
문제 설명 [ 편집 ] 도이치-조사 문제에서 다음 함수를 구현하는 오라클 로 알려진 블랙박스 양자 컴퓨터가 주어져 있다:
f
:
{
0
,
1
}
n
→
{
0
,
1
}
{\displaystyle f\colon \{0,1\}^{n}\rightarrow \{0,1\}}
이 함수는
n
{\displaystyle n}
0
{\displaystyle 0}
1
{\displaystyle 1}
0
{\displaystyle 0}
1
{\displaystyle 1}
균형 함수 (정확히 정의역 의 원소들 절반에 대해
1
{\displaystyle 1}
0
{\displaystyle 0}
[1]
f
{\displaystyle f}
고전적인 해 [ 편집 ] 기존의 결정론적 알고리듬의 경우
n
{\displaystyle n}
f
{\displaystyle f}
무작위 알고리듬 의 경우, 충분히 큰
k
{\displaystyle k}
f
{\displaystyle f}
k
{\displaystyle k}
k
≥
1
{\displaystyle k\geq 1}
ϵ
≤
1
/
2
k
{\displaystyle \epsilon \leq 1/2^{k}}
f
{\displaystyle f}
f
{\displaystyle f}
도이치-조사 알고리듬은
n
=
1
{\displaystyle n=1}
불 함수
f
:
{
0
,
1
}
→
{
0
,
1
}
{\displaystyle f:\{0,1\}\rightarrow \{0,1\}}
[5]
을 일반화 하였다. 도이치가 원래 제안한 알고리듬은 사실 결정론적이지 않았다. 알고리듬은 절반의 확률로 성공했다. 1992년에 도이치와 조사는
n
{\displaystyle n}
도이치-조사 알고리듬에 대한 추가 개선 사항은 클레브와 다른 사람들에 의해 이루어졌다.[2]
f
{\displaystyle f}
[2]
도이치-조사 알고리듬이 작동하려면
x
{\displaystyle x}
f
(
x
)
{\displaystyle f(x)}
x
{\displaystyle x}
결어긋남 이 없는 양자 오라클이어야 한다. 또한
x
{\displaystyle x}
도이치-조사 알고리듬 양자 회로 알고리듬은
n
+
1
{\displaystyle n+1}
|
0
⟩
⊗
n
|
1
⟩
{\displaystyle |0\rangle ^{\otimes n}|1\rangle }
n
{\displaystyle n}
|
0
⟩
{\displaystyle |0\rangle }
|
1
⟩
{\displaystyle |1\rangle }
1
2
n
+
1
∑
x
=
0
2
n
−
1
|
x
⟩
(
|
0
⟩
−
|
1
⟩
)
{\displaystyle {\frac {1}{\sqrt {2^{n+1}}}}\sum _{x=0}^{2^{n}-1}|x\rangle (|0\rangle -|1\rangle )}
이때,
f
{\displaystyle f}
|
x
⟩
|
y
⟩
{\displaystyle |x\rangle |y\rangle }
|
x
⟩
|
y
⊕
f
(
x
)
⟩
{\displaystyle |x\rangle |y\oplus f(x)\rangle }
⊕
{\displaystyle \oplus }
2
{\displaystyle 2}
1
2
n
+
1
∑
x
=
0
2
n
−
1
|
x
⟩
(
|
0
⊕
f
(
x
)
⟩
−
|
1
⊕
f
(
x
)
⟩
)
{\displaystyle {\frac {1}{\sqrt {2^{n+1}}}}\sum _{x=0}^{2^{n}-1}|x\rangle (|0\oplus f(x)\rangle -|1\oplus f(x)\rangle )}
한편,
x
{\displaystyle x}
f
(
x
)
{\displaystyle f(x)}
0
{\displaystyle 0}
1
{\displaystyle 1}
1
2
n
+
1
∑
x
=
0
2
n
−
1
(
−
1
)
f
(
x
)
|
x
⟩
(
|
0
⟩
−
|
1
⟩
)
{\displaystyle {\frac {1}{\sqrt {2^{n+1}}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}|x\rangle (|0\rangle -|1\rangle )}
이 때, 마지막 큐비트
|
0
⟩
−
|
1
⟩
2
{\displaystyle {\frac {|0\rangle -|1\rangle }{\sqrt {2}}}}
1
2
n
∑
x
=
0
2
n
−
1
(
−
1
)
f
(
x
)
|
x
⟩
{\displaystyle {\frac {1}{\sqrt {2^{n}}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}|x\rangle }
부분만 고려하면 된다
다음으로, 첫 번째 큐비트에 아다마흐 변환을 적용하여
H
⊗
n
|
k
⟩
=
1
2
n
∑
j
=
0
2
n
−
1
(
−
1
)
k
⋅
j
|
j
⟩
{\displaystyle H^{\otimes n}|k\rangle ={\frac {1}{\sqrt {2^{n}}}}\sum _{j=0}^{2^{n}-1}(-1)^{k\cdot j}|j\rangle }
(여기서
k
⋅
j
{\displaystyle k\cdot j}
j
0
k
0
⊕
j
1
k
1
⊕
⋯
⊕
j
n
−
1
k
n
−
1
{\displaystyle j_{0}k_{0}\oplus j_{1}k_{1}\oplus \cdots \oplus j_{n-1}k_{n-1}}
1
2
n
∑
x
=
0
2
n
−
1
(
−
1
)
f
(
x
)
[
1
2
n
∑
y
=
0
2
n
−
1
(
−
1
)
x
⋅
y
|
y
⟩
]
=
∑
y
=
0
2
n
−
1
[
1
2
n
∑
x
=
0
2
n
−
1
(
−
1
)
f
(
x
)
(
−
1
)
x
⋅
y
]
|
y
⟩
.
{\displaystyle {\frac {1}{\sqrt {2^{n}}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}\left[{\frac {1}{\sqrt {2^{n}}}}\sum _{y=0}^{2^{n}-1}(-1)^{x\cdot y}|y\rangle \right]=\sum _{y=0}^{2^{n}-1}\left[{\frac {1}{2^{n}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}(-1)^{x\cdot y}\right]|y\rangle .}
이것으로부터 우리는 상태
k
{\displaystyle k}
|
1
2
n
∑
x
=
0
2
n
−
1
(
−
1
)
f
(
x
)
(
−
1
)
x
⋅
k
|
2
{\displaystyle \left|{\frac {1}{2^{n}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}(-1)^{x\cdot k}\right|^{2}}
로 측정됨을 알 수 있다.
|
0
⟩
⊗
n
{\displaystyle |0\rangle ^{\otimes n}}
k
=
0
{\displaystyle k=0}
|
1
2
n
∑
x
=
0
2
n
−
1
(
−
1
)
f
(
x
)
|
2
{\displaystyle {\bigg |}{\frac {1}{2^{n}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}{\bigg |}^{2}}
이다.
f
(
x
)
{\displaystyle f(x)}
보강 간섭 )이면 위 상태는
1
{\displaystyle 1}
상쇄 간섭 )이면
0
{\displaystyle 0}
f
(
x
)
{\displaystyle f(x)}
|
0
⟩
⊗
n
{\displaystyle |0\rangle ^{\otimes n}}
0
{\displaystyle 0}
도이치 알고리듬 [ 편집 ] 도이치 알고리듬은 일반 도이치-조사 알고리듬의
f
:
{
0
,
1
}
n
→
{
0
,
1
}
{\displaystyle f\colon \{0,1\}^{n}\rightarrow \{0,1\}}
n
=
1
{\displaystyle n=1}
f
(
0
)
=
f
(
1
)
{\displaystyle f(0)=f(1)}
f
(
0
)
⊕
f
(
1
)
{\displaystyle f(0)\oplus f(1)}
⊕
{\displaystyle \oplus }
XOR 게이트 로 볼 수도 있는
2
{\displaystyle 2}
0
{\displaystyle 0}
f
{\displaystyle f}
1
{\displaystyle 1}
f
{\displaystyle f}
2
{\displaystyle 2}
|
0
⟩
|
1
⟩
{\displaystyle |0\rangle |1\rangle }
1
2
(
|
0
⟩
+
|
1
⟩
)
(
|
0
⟩
−
|
1
⟩
)
.
{\displaystyle {\frac {1}{2}}(|0\rangle +|1\rangle )(|0\rangle -|1\rangle ).}
|
x
⟩
|
y
⟩
{\displaystyle |x\rangle |y\rangle }
|
x
⟩
|
f
(
x
)
⊕
y
⟩
{\displaystyle |x\rangle |f(x)\oplus y\rangle }
f
{\displaystyle f}
1
2
(
|
0
⟩
(
|
f
(
0
)
⊕
0
⟩
−
|
f
(
0
)
⊕
1
⟩
)
+
|
1
⟩
(
|
f
(
1
)
⊕
0
⟩
−
|
f
(
1
)
⊕
1
⟩
)
)
{\displaystyle {\frac {1}{2}}(|0\rangle (|f(0)\oplus 0\rangle -|f(0)\oplus 1\rangle )+|1\rangle (|f(1)\oplus 0\rangle -|f(1)\oplus 1\rangle ))}
=
1
2
(
(
−
1
)
f
(
0
)
|
0
⟩
(
|
0
⟩
−
|
1
⟩
)
+
(
−
1
)
f
(
1
)
|
1
⟩
(
|
0
⟩
−
|
1
⟩
)
)
{\displaystyle ={\frac {1}{2}}((-1)^{f(0)}|0\rangle (|0\rangle -|1\rangle )+(-1)^{f(1)}|1\rangle (|0\rangle -|1\rangle ))}
=
(
−
1
)
f
(
0
)
1
2
(
|
0
⟩
+
(
−
1
)
f
(
0
)
⊕
f
(
1
)
|
1
⟩
)
(
|
0
⟩
−
|
1
⟩
)
{\displaystyle =(-1)^{f(0)}{\frac {1}{2}}\left(|0\rangle +(-1)^{f(0)\oplus f(1)}|1\rangle \right)(|0\rangle -|1\rangle )}
를 얻는다.
마지막 큐비트와 전체 페이즈를 무시하므로 다음 항만 고려한다:
1
2
(
|
0
⟩
+
(
−
1
)
f
(
0
)
⊕
f
(
1
)
|
1
⟩
)
.
{\displaystyle {\frac {1}{\sqrt {2}}}(|0\rangle +(-1)^{f(0)\oplus f(1)}|1\rangle ).}
이 상태에 아다마흐 변환을 적용하면
1
2
(
|
0
⟩
+
|
1
⟩
+
(
−
1
)
f
(
0
)
⊕
f
(
1
)
|
0
⟩
−
(
−
1
)
f
(
0
)
⊕
f
(
1
)
|
1
⟩
)
{\displaystyle {\frac {1}{2}}(|0\rangle +|1\rangle +(-1)^{f(0)\oplus f(1)}|0\rangle -(-1)^{f(0)\oplus f(1)}|1\rangle )}
=
1
2
(
(
1
+
(
−
1
)
f
(
0
)
⊕
f
(
1
)
)
|
0
⟩
+
(
1
−
(
−
1
)
f
(
0
)
⊕
f
(
1
)
)
|
1
⟩
)
.
{\displaystyle ={\frac {1}{2}}((1+(-1)^{f(0)\oplus f(1)})|0\rangle +(1-(-1)^{f(0)\oplus f(1)})|1\rangle ).}
여기서,
f
(
0
)
⊕
f
(
1
)
=
0
{\displaystyle f(0)\oplus f(1)=0}
|
0
⟩
{\displaystyle |0\rangle }
f
(
0
)
⊕
f
(
1
)
=
1
{\displaystyle f(0)\oplus f(1)=1}
|
1
⟩
{\displaystyle |1\rangle }
f
(
x
)
{\displaystyle f(x)}
같이 보기 [ 편집 ] 외부 링크 [ 편집 ] 
![{\displaystyle {\frac {1}{\sqrt {2^{n}}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}\left[{\frac {1}{\sqrt {2^{n}}}}\sum _{y=0}^{2^{n}-1}(-1)^{x\cdot y}|y\rangle \right]=\sum _{y=0}^{2^{n}-1}\left[{\frac {1}{2^{n}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}(-1)^{x\cdot y}\right]|y\rangle .}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7a471bae4c512b7fa2014ba70f227d9eeaa476af)
