<commit_before>\chapter{Algorithmus von Simon\label{chapter:simon}} 
\lhead{Algorithmus von Simon} 
\begin{refsection} 
\chapterauthor{<NAME> und <NAME>}

\section{Einleitung} 

In diesem Kapitel wird der Algorithmus von Simon vorgestellt.  Es wird zuerst
gezeigt, welches Problem sich damit l"osen l"asst und wie dieses Problem auf
einem klassischen Computer gel"ost werden kann. Danach wird der eigentlich
Algorithmus gezeigt. Schliesslich wird noch gezeigt, warum dieser Algorithums so
bedeutend ist.

\section{Problem} 

Gegeben ist eine unbekannte Funktion $f$, welche einen Bit String entgegennimmt
und einen neuen Bit String liefert.  Formal ausgedrückt bedeutet dies:
\[
    f\colon\{0,0\}^n\to\{0,1\}^n
\]

Die Defintion der Funktion ist auch bekannt:
\[
    f(x) = x \notin s
\]

Es wird einer 


Von der Funktion $f$ ist bekannt, dass sie bijektiv ist und dass es ein
$s\in\{0,1\}^n$ gibt, so dass: \[ f(x) = f(x) \leftrightarrow x \oplus y = s \]

Die Funktion hat damit zwei Urbilder falls $s \notin 0^n$, wobei $s$ die
Periode darstellt. Die Aufgabe ist nun $s$ zu finden.

\section{L"osung}

\subsection{Klassisch}

Auf einem klassischen Computer k"onnte diese Aufgabe mit durchprobieren gel"ost
werden. Dabei wird f"ur alle $x$ das Resultut $f(x)$ ausgewertet, solange ein
Resultate doppelt vorkommt. Mit dem vorhandenen $x$ und $x + s$ kann nun $s$
bestimmt werden. Dabei m"ussen $2^{n/2}$ Werte ausprobiert werden.

\subsection{Quantencomputer}

Auf einem Quantencomputer kann dieses Problem effizienter gel"ost werden.
Daf"ur wurde ein Algorithmus von Simon vorgestellt, im Folgenden wird dieser
genauer erklärt.

% TODO Kiru: Bild hier einfügen

F"ur den Algorithmus sind zwei Register notwendig. Als erstes werden diese mit
0 initialisiert.

\[ 
    |a\rangle=|0 ... 0 \rangle 
\]
\[
    |b\rangle=|0 ... 0 \rangle 
\]

Nun wird die Hadamard-Transformation auf dem ersten Register
angewendet, um diese in eine Superposition von allen möglichen Werten von $0
- 2^n$ zu bringen.

\[ 
    H|a\rangle=\frac{1}{\sqrt{2^n}} \sum_{x\in\{0,1\}^n}{|x\rangle}
\]
 
Nun wird die unbekannte Funktion $f$ angewendet und das Resultat $f(x)$ ins
zweite Register gespeichert. Die beiden Register befinden sich nun im Zustand:

\begin{align*}
  & |a\rangle = \frac{1}{\sqrt{2^n}} \sum_{x\in\{0,1\}^n} {|x\rangle} \\
  & |b\rangle = |f(x)\rangle \\
\end{align*}

Nun wird das zweite Register gemessen. Das Resultat von $f(x)$ ist irrelevant.
Was wichtiger ist, ist der Zustand des ersten Registers.  Dieser befindet sich
im Falle von $s\in0^n$ im Zustand:

\[
    |a\rangle = |f(x)\rangle
\]

Im Falle von $s \in \{0,1\}^n$ befindet sich dieser im Zustand:
\[
    |a\rangle = \frac{1}{\sqrt{2}} ( |x\rangle + |x \oplus s \rangle )
\]

Falls nun das erste Register gemessen wird, liefert diese entweder $x$ oder $x
\oplus s$. Um bei der Messung nur das $x \oplus s$ herauszumessen wird nun
wieder die Hadamard Operation angewendet und wie folgt vereinfacht:

\begin{align*}
    &H^{ \otimes n } \biggl( 
                     \frac{1}{\sqrt{2}} |x\rangle + 
                     \frac{1}{\sqrt{2}} |x \oplus s\rangle 
                     \biggr)
    = H^{ \otimes n } \frac{1}{\sqrt{2}} |x\rangle + 
       H^{ \otimes n } \frac{1}{\sqrt{2}} |x \oplus s\rangle 
    \\ 
    &= \frac1{\sqrt{2}} ( H^{ \otimes n } |x\rangle + H^{ \otimes n } |x \oplus s\rangle )
    \\
    &= \frac1{\sqrt{2}}
       \biggl( \frac1{\sqrt{2}^n} \sum_{z \in \{0,1\}^n} {( (-1)^{x \cdot z} |z\rangle )} + 
               \frac1{\sqrt{2}^n}  \sum_{z \in \{0,1\}^n} { ( (-1)^{(x \oplus s) \cdot z } |z\rangle)}
       \biggr)
    \\
    &= \frac1{\sqrt{2^{n + 1}}}
       \biggl( \sum_{z \in \{0,1\}^n}  { 
                   (-1)^{x \cdot z} |z\rangle + (-1)^{(x \oplus s) \cdot z } |z\rangle 
               } 
       \biggr)
    \\
    &= \frac1{\sqrt{2^{n + 1}}}
       \biggl( \sum_{z \in \{0,1\}^n}  { 
                  (-1)^{x \cdot z} |z\rangle + (-1)^{(x \cdot z) \oplus ( s \cdot z) } |z\rangle 
               } 
       \biggr)
    \\
    &= \frac1{\sqrt{2^{n + 1}}}
       \biggl( 
          \sum_{z \in \{0,1\}^n}  { (-1)^{x \cdot z} ( 1 + (-1)^{ s \cdot z}) |z\rangle } 
       \biggr)
    \\
\end{align*}

Es werden nun zwei F"alle unterschieden. Falls $s \cdot z = 1$ ist, dann gilt:
\begin{align*}
    &\frac1{\sqrt{2^{n + 1}}}
      \sum_{z \in \{0,1\}^n}  { (-1)^{x \cdot z} ( 1 + (-1)^{ s \cdot z}) |z\rangle } 
    \\
    &= 
    \frac1{\sqrt{2^{n + 1}}}
      \sum_{z \in \{0,1\}^n}  { (-1)^{x \cdot z} ( 1 + (-1)^1) |z\rangle } 
    \\
    &= 
    \frac1{\sqrt{2^{n + 1}}}
      \sum_{z \in \{0,1\}^n}  { (-1)^{x \cdot z} (0) |z\rangle } 
    \\
    &=
    0 |z\rangle
\end{align*}

Dies zeigt, dass die Wahrscheinlichkeit diesen Fall zu messen gleich 0 ist und
somit nie auftritt. Der zweite Fall ist $s \cdot z = 0$, dann gilt:

\begin{align*}
    &\frac1{\sqrt{2^{n + 1}}}
      \sum_{z \in \{0,1\}^n}  { (-1)^{x \cdot z} ( 1 + (-1)^{ s \cdot z}) |z\rangle } 
    \\
    &= 
    \frac1{\sqrt{2^{n + 1}}}
      \sum_{z \in \{0,1\}^n}  { (-1)^{x \cdot z} ( 1 + (-1)^0) |z\rangle } 
    \\
    &= 
    \frac1{\sqrt{2^{n + 1}}}
      \sum_{z \in \{0,1\}^n}  { (-1)^{x \cdot z} (2) |z\rangle } 
    \\
    &= 
    \frac{2}{\sqrt{2^{n + 1}}} 
      \sum_{z \in \{0,1\}^n}  { (-1)^{x \cdot z}|z\rangle } 
    &= 
    \frac1{\sqrt{2^{n - 1}}} 
      \sum_{z \in \{0,1\}^n}  { (-1)^{x \cdot z}|z\rangle } 
\end{align*}

Bei der Messung des ersten Registers wird nun ein n-String $z$ gemessen mit der
Bedingung, dass $s \cdot z = 0$ ist. Die Wahrscheinlichkeit daf"ur liegt bei:
\[
    |\frac1{\sqrt{2^{n - 1}}}|^2 = \frac1{2^{n-1}} 
\]

Bei genauer "Uberglegung macht dies auch Sinn, denn falls $s \notin \{0,1\}^n$
ist, gibt es genau $2^{n-1}$ M"oglich $z$-Werte. Die Wahrscheinlichkeit einen
solchen zu messen ist also gleich-verteilt.

Der Algorithmus von Simon liefert nun einen Wert $z$. Um den genauen Wert von
$s$ zu bestimmen, wird nun der Algorithmus $n-1$-Mal wiederholt, somit liegen
nun $n-1$ Gleichung vor und der Wert $s$ kann mittels Gauss berechnet werden.

\section{Schlussfolgerung}

Der Algorithmus von Simon zeigt auf, dass mittels eines Quantencomputers die
Anzahl der Aufrufe der Funktion $f$ auf $O(n)$ reduziert werden k"onnen. Die
Anzahl der Schritte, welche f"ur die effektive Berechnung von $s$ ben"otigt
werden, h"angt vom l"osen des linearen Gleichungssystems mit Gaußscher
Elimination ab, also $O(n^3)$.

%\section{Warum ist dies relevant?}

\printbibliography[heading=subbibliography] \end{refsection}

<commit_msg>Ausführlicher erklärt<commit_after>\chapter{Algorithmus von Simon\label{chapter:simon}} 
\lhead{Algorithmus von Simon} 
\begin{refsection} 
\chapterauthor{<NAME> und <NAME>}

\section{Einleitung} 

In diesem Kapitel wird der Algorithmus von Simon vorgestellt.  Es wird zuerst
gezeigt, welches Problem sich damit l"osen l"asst und wie dieses Problem auf
einem klassischen Computer gel"ost werden kann. Danach wird der eigentlich
Algorithmus gezeigt. Schliesslich wird noch gezeigt, warum dieser Algorithums so
bedeutend ist.

\section{Problem} 

Gegeben ist eine unbekannte Funktion $f$, welche einen n-Bit langen String
entgegen nimmt und einen neuen Bit String liefert. Formal ausgedr"uckt bedeutet
dies:

\[
    f\colon\{0,1\}^n\to\{0,1\}^n
\]

Die Defintion der Funktion ist auch bekannt:

\[
    f(x) = x \oplus s
\]

Die Eingabe wird also eine Und-Verkn"ufung mit dem Werte und einer unbekannten
Konstant $s$ gemacht.  Gesucht ist nun $s$. Fall $s = 0^n$ ist, dann liefert
diese Funktion f"ur jeden Wert von $x$ jeweils unterschiedliche Werte von
$f(x)$, sie ist also bijektiv.

Falls nun sonst was anders ist, also $s \in \{0,1\}^n, s \neq 0^n$, liefert die
Funktion f"ur zwei $x$ denselben Wert $f(x)$. Formal kann dies so definiert
werden:

\[ 
    f(x) = f(y) \leftrightarrow x \oplus y = s 
\]

In diesem Fall die Funktion ist also nicht bijektiv, jedoch periodisch, wobei
$s$ die Period darstellt. Der Kern des Problem ist, dass eine m"oglicherweise
Periodische Funktion gegeben ist und die Periode gesucht ist.

% TODO -> Grafik mit x -> y ( periodisch und nicht periodisch )

\section{L"osung}

\subsection{Klassisch}

Wie w"urde man dise Aufgabe auf einem klassichen Computer l"osen? Ein naiver
Ansatz w"are alle M"oglichen Werten auszuprobieren. Die folgende Tabelle zeigt
f"ur eine Beispielfunktion $f$ die Resultate.


\begin{center}
   \begin{tabular}{ l | c  }
    \hline
     x   & f(x) \\ \hline
     000 & 000  \\ \hline
     001 & 001  \\ \hline
     010 & 010  \\ \hline
     011 & 011  \\ \hline
     100 & 000  \\ \hline
     101 & 001  \\ \hline
     110 & 010  \\ \hline
     111 & 011  \\ \hline
     \hline
    \end{tabular}
\end{center}


Was ist nun die Periode? Die Frage l"asst sich einfach beantworten. Es m"ussen
nur zwei Werte $f(x)$ gefunden werden, die identisch sind. In diesem beispiel
sind es $f(000) = 000$ und $f(100) = 000$. 

Nun kommt die obige Gleichung zum Zug:

\[
    f(000) = f(100) \leftrightarrow 000 \oplus 100 = s = 011
\]

Wie effizient ist dieser Algorithmus? Es m"ussen alle M"oglichen Eingaben
ausprobiert werden. Bei der L"ange $3$ wurden $2^3$ Inputs generiert. Bei einem
$n$ Bit String werden also $2^n$ Inputs generiert. 

Bei genauer "Uberlegung war beim Beispiel nur $f(000)$ und $f(0001)$ relevant.
Die Funktion muss nur solange aufgerufen werden, bis zwei Werte identisch sind.
Es gen"ugt daher $n^{1/2}$ Werte auszuprobieren.

% TODO Grafik -> Wachstum mit 2^n/2
% TDOO Grafik kommentierne und "uberleitung zum Quantencomputer

\subsection{Quantencomputer}

Auf einem Quantencomputer kann dieses Problem effizienter gel"ost werden.
Daf"ur wurde ein Algorithmus von <NAME> vorgestellt, im Folgenden wird
dieser genauer erkl"art.

% TODO Bild vom Schaltkreis.

Die Grundidee des Algorithmus ist es alle M"oglichken Werte von $x$ auf einmal
auszuprobieren und zwei Werte f"ur $f(x)$ zu finden, die identisch sind.

F"ur den Algorithmus sind zwei Register notwendig. Als erstes werden diese mit
0 initialisiert.

\begin{align*}
    |a\rangle=|0 ... 0 \rangle 
    \\
    |b\rangle=|0 ... 0 \rangle 
\end{align*}

Um nun alle Werte auf einmal zu erzeugen, wir die Hadamard-Transformation auf
dem ersten Register angewendet. Diese befindet sich in einer Superpostion,
indem alle M"oglichen Werten von $x$ mit der gleichen Wahrscheinlichkeit
auftreten.

\[ 
    H|a\rangle=\frac{1}{\sqrt{2^n}} \sum_{x\in\{0,1\}^n}{|x\rangle}
\]
 
Nun wird die unbekannte Funktion $f$ angewendet und das Resultat $f(x)$ ins
zweite Register gespeichert. Die beiden Register befinden sich nun im Zustand:

\begin{align*}
  & |a\rangle = \frac{1}{\sqrt{2^n}} \sum_{x\in\{0,1\}^n} {|x\rangle} \\
  & |b\rangle = |f(x)\rangle \\
\end{align*}

Im ersten Register sind alle M"oglichen Werte $x$ representiert und im zweiten
Register deren $f(x)$. Nun wird das zweite Register $|b\rangle$ gemessen. Bei
der Messung wird nun ein Resultat $f(x)$ herausgelesen. Gleichzeitig wird auch
das erste Register $|a\rangle$ beeinflusst.

Das Resultat der Messung des ersten Registers ist nicht relevant. Viel
wichtiger ist nun der Zustand des ersten Registers. Dieser befindet sich im

Falle von $s = 0$ im Zustand:
\[
    |a\rangle = |f(x)\rangle
\]
Dies ist auch logisch, denn falls  die Funktion ist bijektiv, f"ur jeden $f(x)$
gibt es nur einen $x$

Was f"ur das L"osen des Problems relevanter ist aber falls die unbekannte
Funktion eine Periode hat. Denn im Falle von $s \in \{0,1\}^n$ befindet sich
das erste Register im Zustand:
\[
    |a\rangle = \frac{1}{\sqrt{2}} ( |x\rangle + |x \oplus s \rangle )
\]

Dies sagt aus, dass bei der Messung des ersten Registers entweder $x$ oder $x
\oplus s$ herausgelesen wird. Das Problem ist nun, dass es sich nicht
unterschieden lässt, um welchen Wert es sich handelt. Denn falls $x$ gemessen
wird ist nicht klar, dass diser nicht $x \oplus s$ ist. Es hilft auch nicht
$s$ zu finden.

Um bei der Messung den Wert nicht zu bekommen wird ein Trick verwendet. Dafür
wird nochmals die Hadamard-Operation auf dem ersten Register angewendet.

\begin{align*}
    &H^{ \otimes n } \biggl( 
                     \frac{1}{\sqrt{2}} |x\rangle + 
                     \frac{1}{\sqrt{2}} |x \oplus s\rangle 
                     \biggr)
    \\
    &= H^{ \otimes n } \frac{1}{\sqrt{2}} |x\rangle + 
       H^{ \otimes n } \frac{1}{\sqrt{2}} |x \oplus s\rangle 
    \\ 
    &= \frac1{\sqrt{2}} ( H^{ \otimes n } |x\rangle + H^{ \otimes n } |x \oplus s\rangle )
    \\
    &= \frac1{\sqrt{2}}
       \biggl( \frac1{\sqrt{2}^n} \sum_{z \in \{0,1\}^n} {( (-1)^{x \cdot z} |z\rangle )} + 
               \frac1{\sqrt{2}^n}  \sum_{z \in \{0,1\}^n} { ( (-1)^{(x \oplus s) \cdot z } |z\rangle)}
       \biggr)
    \\
    &= \frac1{\sqrt{2^{n + 1}}}
       \biggl( \sum_{z \in \{0,1\}^n}  { 
                   (-1)^{x \cdot z} |z\rangle + (-1)^{(x \oplus s) \cdot z } |z\rangle 
               } 
       \biggr)
    \\
    &= \frac1{\sqrt{2^{n + 1}}}
       \biggl( \sum_{z \in \{0,1\}^n}  { 
                  (-1)^{x \cdot z} |z\rangle + (-1)^{(x \cdot z) \oplus ( s \cdot z) } |z\rangle 
               } 
       \biggr)
    \\
    &= \frac1{\sqrt{2^{n + 1}}}
       \biggl( 
          \sum_{z \in \{0,1\}^n}  { (-1)^{x \cdot z} ( 1 + (-1)^{ s \cdot z}) |z\rangle } 
       \biggr)
    \\
\end{align*}

Es werden nun zwei F"alle unterschieden. Falls $s \cdot z = 1$ ist, dann gilt:
\begin{align*}
    &\frac1{\sqrt{2^{n + 1}}}
      \sum_{z \in \{0,1\}^n}  { (-1)^{x \cdot z} ( 1 + (-1)^{ s \cdot z}) |z\rangle } 
    \\
    &= 
    \frac1{\sqrt{2^{n + 1}}}
      \sum_{z \in \{0,1\}^n}  { (-1)^{x \cdot z} ( 1 + (-1)^1) |z\rangle } 
    \\
    &= 
    \frac1{\sqrt{2^{n + 1}}}
      \sum_{z \in \{0,1\}^n}  { (-1)^{x \cdot z} (0) |z\rangle } 
    \\
    &=
    0 |z\rangle
\end{align*}

Dies zeigt, dass die Wahrscheinlichkeit diesen Fall zu messen gleich 0 ist und
somit nie auftritt. Der zweite Fall ist $s \cdot z = 0$, dann gilt:

\begin{align*}
    &\frac1{\sqrt{2^{n + 1}}}
      \sum_{z \in \{0,1\}^n}  { (-1)^{x \cdot z} ( 1 + (-1)^{ s \cdot z}) |z\rangle } 
    \\
    &= 
    \frac1{\sqrt{2^{n + 1}}}
      \sum_{z \in \{0,1\}^n}  { (-1)^{x \cdot z} ( 1 + (-1)^0) |z\rangle } 
    \\
    &= 
    \frac1{\sqrt{2^{n + 1}}}
      \sum_{z \in \{0,1\}^n}  { (-1)^{x \cdot z} (2) |z\rangle } 
    \\
    &= 
    \frac{2}{\sqrt{2^{n + 1}}} 
      \sum_{z \in \{0,1\}^n}  { (-1)^{x \cdot z}|z\rangle } 
    \\
    &= 
    \frac1{\sqrt{2^{n - 1}}} 
      \sum_{z \in \{0,1\}^n}  { (-1)^{x \cdot z}|z\rangle } 
\end{align*}

Mit diesem Trick, wiid nun ein Wert $z$ gemessen mit der Eigenschaft:
\[
    s \cdot z = 0
\]

Bei der Messung des ersten Registers wird nun ein n-String $z$ gemessen mit der
Bedingung, dass $s \cdot z = 0$ ist. Die Wahrscheinlichkeit daf"ur liegt bei:
\[
    |\frac1{\sqrt{2^{n - 1}}}|^2 = \frac1{2^{n-1}} 
\]

Bei genauer "Uberglegung macht dies auch Sinn, denn falls $s \notin \{0,1\}^n$
ist, gibt es genau $2^{n-1}$ M"oglich $z$-Werte. Die Wahrscheinlichkeit einen
solchen zu messen ist also gleich-verteilt.

Der Algorithmus von Simon liefert nun einen Wert $z$. Um den genauen Wert von
$s$ zu bestimmen, wird nun der Algorithmus $n-1$-Mal wiederholt, somit liegen
nun $n-1$ Gleichung vor und der Wert $s$ kann mittels Gauss berechnet werden.

\begin{align*}
    s \cdot z_{1} = 0
    \\
    s \cdot z_{2} = 0
    \\
    s \cdot z_{3} = 0
    \\
    ...
    \\
    s \cdot z_{n} = 0
\end{align*}


\section{Schlussfolgerung}

% TODO: Grafik für linear und beispiel zeigen

Der Algorithmus von Simon zeigt auf, dass mittels eines Quantencomputers die
Anzahl der Aufrufe der Funktion $f$ auf $O(n)$ reduziert werden k"onnen. Die
Anzahl der Schritte, welche f"ur die effektive Berechnung von $s$ ben"otigt
werden, h"angt vom l"osen des linearen Gleichungssystems mit Gaußscher
Elimination ab, also $O(n^3)$.

%\section{Warum ist dies relevant?}

\printbibliography[heading=subbibliography] \end{refsection}


{'fraction_non_alphanumeric': 0.15921927952805323, 'fraction_numerical': 0.02504079327224802, 'mean_word_length': 2.743246417665022, 'pattern_counts': {'":': 0, '<': 8, '<?xml version=': 0, '>': 11, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '1511113', 'n_tokens_mistral': 6375, 'n_tokens_neox': 6229, 'n_words': 1935}