Shor-Algorithmus

Einfache Sprache

Shor Factor Finding

	\begin{algorithm}
	\caption{Shor-Algortihmus}
	\begin{algorithmic}
	\Input $n\in\mathbb N$
	\Procedure{ShorFactorFinding}{$n$}
	\State $a = $\Call{PerfectPower}{$n$}
	\If{$a \not= 0$}
		\Return $a$
    \EndIf
    \State Choose a random $a$ with $1\leq a\leq n-1$
    \State $b = $\CALL{gcd}{$a,n$}
    \If{$b > 1$}
		\Return $b$
    \EndIf 
    \State $f(i) = a^i\mod n$
    \State $m = ?$
    \State $N = 2^{2m+2}$
    \State $k = $ \Call{ShorPeriodCore}{$N,f$}
    \State $r = $ \CALL{ShotPeriodPost}{$N,m,k, f$}
    \If{ $(2\not|r)$ or $(f(r) \not= 1)$}
	    \Return "fail"
    \EndIf
    \State $b = f(r/2)$
    \If{$1\leq b\leq n-1$}
	    \Return "fail"	    
    \EndIf
    \State $c = $\CALL{gcd}{$b-1,n$}
    \Return $c$
    \EndProcedure
	\end{algorithmic}
	\end{algorithm}

	\begin{algorithm}
	\caption{ShorPeriodCore}
	\begin{algorithmic}
	\Input $N\in\mathbb N$ mit $N=2^n$, Oracel $O_f$ for $f:\{0,\ldots,N-1\}\to\{0,1\}^m$
    \Procedure{ShortPeriodCore}{$N,f$}
    \State Initialize with $|0\rangle_n|0^m\rangle$
    \State Apply $H^{\otimes n}\otimes I^{\otimes m}$
    \Comment{State: $|+\rangle_n|0^m\rangle$} 
    \State Apply $O_f$
    \Comment{State: $\frac{1}{\sqrt{N}}\sum_{j<N}|j\rangle|f(j)\rangle=\frac{1}{\sqrt{N}}\sum_{j<r}\left(\sum_{s<K_j}|j+rs\rangle\right)|f(j)\rangle $ where $K_j = \lceil\frac{N-j}{r}\rceil$}
    \State Measure bits $n,\ldots,n+m-1$
    \Comment{Output: $f(j)$ for some $j<r$ (all with same probability). Let $K = K_j$. State: $\frac{1}{\sqrt{K}}\sum_{j<K}|j+rs\rangle$}
    \State Apply $F_n$ (Also $H^{\otimes n}$)
    \Comment{State:$\frac{1}{\sqrt{NK}}\sum_{k<K}\omega^{jk}\sum_{s<K}((\omega^{rk})^s|k\rangle$}
    \State Measure $k$
    \EndProcedure
	\end{algorithmic}
	\end{algorithm}

Hello everyone, is my understanding correct that for the shor-algorithm we choose m to be the smallest integer such that 2^m is larger than n. For me this follows from Remark a2987871848.

	\begin{algorithm}
	\caption{ShorPeriodPost}
	\begin{algorithmic}
	\Input $N,m,k\in\mathbb N$
    \Procedure{ShortPeriodCore}{$N,m,k$}
    \return \Call{FindFraction}{$\frac{k}{N},2^m$}
    \EndProcedure
    \Procedure{FindFraction}{$x,M$}
    \State Let $[p_0/q_0,\ldots,p_l/q_l] = $ \Call{Convergents}{$x$}
    \State Find the unique $i$ such that $q_i<M$ and $|x-\frac{p_i}{q_i}|\leq\frac{1}{2M^2}$
    \Return $q_i$
    \EndProcedure
    \Procedure{Convergents}{$x$}
    \State $p_{-2} = 0, p_{-1} = 1$
    \State $q_{-2} = 1, q_{-1} = 0$
    \State $i = -1$
    \State $x_0 = x$
    \State $c = []$
    \State $d = \textrm{FALSE}$
    \While{not $d$}
	    \State $i = i+1$
	    \State $a_i = \lfloor x_i\rfloor$
	    \State $p_i = a_ip_{i-1} + p_{i-2}$
	    \State $p_i = a_iq_{i-1} + q_{i-2}$
	    \State Append $p_i/q_i$ to $c$
	    \If{$a_i = x_i$}
		    \State $d = \textrm{true}$
		\Else
			\State $x_{i+1} = \frac{1}{x_i-a_i}$
        \EndIf
    \EndWhile
    \Return $c$
    \EndProcedure
	\end{algorithmic}
	\end{algorithm}