Simons-Algorithmus

Simons-Algorithm

Einfache Sprache

Idee Simons Algorithmus

	\begin{algorithm}
	\caption{Simons Alorithm}
	\begin{algorithmic}
	\Input build-in oracle $O_{f}$ for a $\oplus$-periodic function $f:\{0,1\}^n\to\{0,1\}^{n-1}$
	\Procedure{Simon}{$O_{f}$}
	\For{$i = 0$ \textbf{ to } $k_n-1$}
		\State $b_i=$ \Call{SimonSub}{$O_{f}$}
		\Comment{Produces a random $b_i$ with $b_i\odot a=0$.}
    \EndFor
    \State Solve the system of equations $b_i\odot a=0\quad i<r$ for $a$
    \If{$a$ is a unique solution ($a\not=0^n$)}
	    \Return $a$
	\Else
		\Return fail
    \EndIf
    \EndProcedure
    \Procedure{SimonSub}{$O_{f}$}
    \State Initialize with $|0\rangle^{2n-1}$
    \State Apply $H^{\otimes n}\otimes I^{n-1}$
    \State Apply $O_f$
    \State Measure bits $n,\ldots, 2n-2$.
    \State Apply $H^{\otimes n}$
    \State Measure $b_0,\ldots,b_{n-1}$ ($=b$)
    \Return $b$
    \EndProcedure       
	\end{algorithmic}
	\end{algorithm}