Algorytm Simona to kwantowy algorytm, który dostarcza rozwiązania dla przedstawionego poniżej problemu.
Problem
Rozważmy funkcję:
f
:
{
0
,
1
}
n
−
>
{
0
,
1
}
m
{\displaystyle f:\{0,1\}^{n}->\{0,1\}^{m}}
gdzie
m
⩾
n
−
1.
{\displaystyle m\geqslant n-1.}
Konieczne jest sprawdzenie, czy istnieje taki
s
∈
{
0
,
1
}
n
∖
{
0
(
n
)
}
{\displaystyle s\in \{0,1\}^{n}\setminus \{0^{(}n)\}}
tak, że:
∀
x
′
≠
x
(
f
(
x
′
)
=
f
(
x
)
⇔
x
′
=
x
⊕
s
)
{\displaystyle \forall _{x’\neq x}(f(x’)=f(x)\Leftrightarrow x’=x\oplus s).}
Rozwiązanie klasyczne
Nie ma możliwości rozwiązania tego problemu z złożonością obliczeniową niższą niż wykładnicza.
Rozwiązanie kwantowe
Rozwiązanie polega na wykorzystaniu systemu kwantowego, który niezależnie wykonuje n-krotne operacje.
Przebiega to w następujący sposób:
|
ϕ
0
⟩
=
|
0
(
n
)
⟩
|
0
(
m
)
⟩
{\displaystyle |\phi _{0}\rangle =|0^{(n)}\rangle |0^{(m)}\rangle }
|
ϕ
1
⟩
=
H
⊗
n
|
ϕ
0
⟩
=
1
2
n
∑
i
=
0
2
n
−
1
|
i
⟩
|
0
(
m
)
⟩
,
{\displaystyle |\phi _{1}\rangle =H^{\otimes n}|\phi _{0}\rangle ={\frac {1}{\sqrt {2^{n}}}}\sum _{i=0}^{2^{n}-1}|i\rangle |0^{(m)}\rangle ,}
gdzie
|
i
⟩
∈
{
0
,
1
,
.
.
.2
n
−
1
}
{\displaystyle |i\rangle \in \{0,1,…2^{n}-1\}}
jest liczbą zakodowaną na pierwszych
n
{\displaystyle n}
bitach
|
ϕ
2
⟩
=
U
f
|
ϕ
1
⟩
=
U
f
1
2
n
∑
i
=
0
2
n
−
1
|
i
⟩
|
0
(
m
)
⟩
=
1
2
n
∑
i
=
0
2
n
−
1
|
i
⟩
|
f
(
i
)
⟩
{\displaystyle |\phi _{2}\rangle =U_{f}|\phi _{1}\rangle =U_{f}{\frac {1}{\sqrt {2^{n}}}}\sum _{i=0}^{2^{n}-1}|i\rangle |0^{(m)}\rangle ={\frac {1}{\sqrt {2^{n}}}}\sum _{i=0}^{2^{n}-1}|i\rangle |f(i)\rangle }
|
ϕ
3
⟩
=
H
⊗
n
|
ϕ
2
⟩
=
1
2
n
∑
i
=
0
2
n
−
1
∑
j
=
0
2
n
−
1
(
−
1
)
i
j
|
i
⟩
|
f
(
j
)
⟩
{\displaystyle |\phi _{3}\rangle =H^{\otimes n}|\phi _{2}\rangle ={\frac {1}{2^{n}}}\sum _{i=0}^{2^{n}-1}\sum _{j=0}^{2^{n}-1}(-1)^{ij}|i\rangle |f(j)\rangle }
Taką procedurę należy powtarzać n-krotnie, wykonując pomiar stanu pierwszego rejestru po każdym cyklu. W wyniku tych operacji powinniśmy uzyskać n liniowo niezależnych wektorów w
{
0
(
n
)
}
,
{\displaystyle \{0^{(}n)\},}
które, włożone do układu równań jednorodnych w przestrzeni
Z
2
{\displaystyle \mathbb {Z} _{2}
powinny zwrócić jako rozwiązanie poszukiwaną
s
.
{\displaystyle s.}
Bibliografia
Krzysztof Giaro, Marcin Kamiński, Wprowadzenie do algorytmów kwantowych, Akademicka Oficyna Wydawnicza EXIT, Warszawa 2003, ISBN 83-87674-57-5.
Daniel R. Simon, On the Power of Quantum Computation, SIAM Journal on Computing, Volume 26, Issue 5, 1997, s. 1474–1483 ISSN 0097-5397.
