Rechenkomplexität messen

Als Nächstes besprechen wir einen mathematischen Rahmen, mit dem sich die Rechenkomplexität messen lässt – eng zugeschnitten auf die Bedürfnisse dieses Kurses. Die Algorithmenanalyse und die Berechnungskomplexität sind eigenständige Fachgebiete, die zu diesen Konzepten noch viel mehr zu sagen haben.

Als Ausgangspunkt betrachten wir die folgende Abbildung aus der vorigen Lektion, die eine sehr abstrakte Darstellung einer Berechnung zeigt.

Die Berechnung selbst kann auf verschiedene Weisen modelliert oder beschrieben werden, etwa durch ein in Python geschriebenes Computerprogramm, eine Turingmaschine, einen Booleschen Schaltkreis oder einen Quantenschaltkreis. Unser Fokus liegt auf Schaltkreisen (sowohl Booleschen als auch Quantenschaltkreisen).

Kodierungen und Eingabelänge

Beginnen wir mit der Ein- und Ausgabe eines Berechnungsproblems, die wir als binäre Zeichenketten annehmen. Es könnten auch andere Symbole verwendet werden, aber der Einfachheit halber beschränken wir uns hier auf binäre Eingabe- und Ausgabezeichenketten. Über binäre Zeichenketten lassen sich eine Vielzahl interessanter Objekte kodieren, mit denen sich die von uns betrachteten Probleme befassen – etwa Zahlen, Vektoren, Matrizen und Graphen sowie Listen dieser und anderer Objekte.

Um beispielsweise nichtnegativen ganzen Zahlen zu kodieren, können wir die Binärdarstellung verwenden. Die folgende Tabelle zeigt die Binärkodierung der ersten neun nichtnegativen ganzen Zahlen sowie die Länge (also die Gesamtzahl der Bits) jeder Kodierung.

Zahl	Binärkodierung	Länge
0	0	1
1	1	1
2	10	2
3	11	2
4	100	3
5	101	3
6	110	3
7	111	3
8	1000	4

Diese Kodierung lässt sich leicht auf positive und negative ganze Zahlen erweitern, indem wir den Darstellungen optional ein Vorzeichenbit anhängen. Manchmal ist es auch praktisch, führende Nullen in Binärdarstellungen nichtnegativer ganzen Zahlen zu erlauben, die den kodierten Wert zwar nicht ändern, aber erlauben, Darstellungen auf eine feste Zeichenketten- oder Wortlänge aufzufüllen.

Die Binärdarstellung ist eine gebräuchliche und effiziente Methode zur Darstellung nichtnegativer ganzer Zahlen. Wenn wir wollten, könnten wir aber auch eine andere Weise wählen, etwa die in der folgenden Tabelle vorgeschlagenen Alternativen. Die Details dieser Alternativen sind für unsere Diskussion nicht wichtig – der Punkt ist lediglich, zu verdeutlichen, dass wir bei der Wahl von Kodierungen tatsächlich Optionen haben.

Zahl	Unäre Kodierung	Lexikografische Kodierung
0	$\varepsilon$	$\varepsilon$
1	0	0
2	00	1
3	000	00
4	0000	01
5	00000	10
6	000000	11
7	0000000	000
8	00000000	001

(In dieser Tabelle steht das Symbol $\varepsilon$ für die leere Zeichenkette, die keine Symbole enthält und die Länge null hat. Um eine naheliegende Verwechslung zu vermeiden, verwenden wir ein eigenes Symbol wie $\varepsilon$ für die leere Zeichenkette, statt buchstäblich nichts zu schreiben.)

Andere Eingabetypen, wie Vektoren und Matrizen oder komplexere Objekte wie Molekülbeschreibungen, können ebenfalls als binäre Zeichenketten kodiert werden. Genau wie bei nichtnegativen ganzen Zahlen können verschiedene Kodierungsverfahren gewählt oder entwickelt werden. Unabhängig davon, welches Verfahren wir zur Kodierung von Eingaben für ein bestimmtes Problem wählen, verstehen wir die Länge einer Eingabezeichenkette als Maß für die Größe der zu lösenden Probleminstanz.

Die Anzahl der Bits, die benötigt werden, um eine nichtnegative ganze Zahl $N$ in Binärdarstellung auszudrücken, wird manchmal als $\operatorname{lg}(N)$ bezeichnet und durch folgende Formel gegeben:

$$\operatorname{lg}(N) = \begin{cases} 1 & N = 0\\ 1 + \lfloor \log_2 (N) \rfloor & N \geq 1 \end{cases}$$

Wenn wir die Binärdarstellung zur Kodierung der Eingabe des ganzzahligen Faktorisierungsproblems verwenden, beträgt die Eingabelänge für die Zahl $N$ daher $\operatorname{lg}(N)$. Beachte insbesondere, dass die Länge (oder Größe) der Eingabe $N$ nicht $N$ selbst ist. Für große $N$ benötigen wir bei weitem nicht so viele Bits, um $N$ binär darzustellen.

Formal gesehen sollte bei jedem Berechnungsproblem oder jeder Rechenaufgabe ein konkretes Kodierungsverfahren für alle als Ein- oder Ausgabe auftretenden Objekte festgelegt sein. Dadurch können Berechnungen, die interessante Probleme lösen, abstrakt als Transformationen von binären Eingabezeichenketten in binäre Ausgabezeichenketten betrachtet werden.

Die Details der Kodierung von Objekten als binäre Zeichenketten müssen auf irgendeiner Ebene für diese Berechnungen relevant sein. In der Regel machen wir uns bei der Analyse der Rechenkomplexität aber nicht allzu viele Gedanken darüber, um uns nicht in Nebensächlichkeiten zu verlieren. Die grundlegende Überlegung ist, dass wir davon ausgehen, dass der Rechenaufwand für die Konvertierung zwischen „vernünftigen" Kodierungsverfahren im Vergleich zu den Kosten der eigentlichen Problemlösung vernachlässigbar ist. In den Fällen, in denen das nicht zutrifft, können (und sollten) die Details präzisiert werden.

Eine sehr einfache Berechnung beispielsweise konvertiert zwischen der Binärdarstellung einer nichtnegativen ganzen Zahl und ihrer lexikografischen Kodierung (die wir nicht im Detail erklärt haben, die sich aber aus der obigen Tabelle ableiten lässt). Aus diesem Grund würde sich die Rechenkomplexität der ganzzahligen Faktorisierung nicht wesentlich ändern, wenn wir für die Eingabe $N$ von einer dieser Kodierungen zur anderen wechseln würden. Die Kodierung nichtnegativer ganzer Zahlen in unärer Notation hingegen erfordert exponentiell mehr Symbole und gilt daher nicht als „vernünftiges" Kodierungsverfahren.

Elementare Operationen

Betrachten wir nun die eigentliche Berechnung, die durch das blaue Rechteck in der obigen Abbildung dargestellt wird. Die Rechenkomplexität messen wir, indem wir die Anzahl der elementaren Operationen zählen, die jede Berechnung benötigt. Intuitiv ist eine elementare Operation eine solche, die eine kleine, feste Anzahl von Bits oder Qubits betrifft und schnell und einfach ausgeführt werden kann – etwa die Berechnung des UND zweier Bits. Im Gegensatz dazu lässt sich die Ausführung der Funktion factorint vernünftigerweise nicht als elementare Operation betrachten.

Formal gesehen gibt es je nach verwendetem Berechnungsmodell unterschiedliche Definitionen dafür, was eine elementare Operation ausmacht. Unser Fokus liegt auf Schaltkreismodellen, insbesondere auf Quanten- und Booleschen Schaltkreisen.

Universelle Gate-Mengen

Bei schaltkreisbasierten Berechnungsmodellen wird in der Regel jedes Gate als elementare Operation betrachtet. Damit stellt sich die Frage, welche Gates in unseren Schaltkreisen zulässig sind. Beschränken wir uns zunächst auf Quantenschaltkreise: Bisher haben wir in dieser Reihe verschiedene Gates kennengelernt, darunter $X$-, $Y$-, $Z$-, $H$-, $S$- und $T$-Gates, SWAP-Gates, gesteuerte Versionen von Gates (einschließlich Controlled-NOT-, Toffoli- und Fredkin-Gates) sowie Gates, die Standardbasismessungen darstellen. Im Zusammenhang mit dem CHSH-Spiel haben wir auch einige zusätzliche Rotations-Gates kennengelernt.

Wir haben auch Query-Gates im Kontext des Abfragemodells besprochen und festgestellt, dass jede unitäre Operation $U$, die auf beliebig viele Qubits wirkt, als Gate betrachtet werden kann – aber beide Optionen lassen wir für diese Diskussion außer Acht. Wir arbeiten nicht im Abfragemodell (die Implementierung von Query-Gates mit elementaren Operationen wird jedoch später in der Lektion besprochen), und das Betrachten beliebiger unitärer Gates, die möglicherweise auf Millionen von Qubits wirken, als elementare Operationen führt nicht zu sinnvollen oder realistischen Vorstellungen von Rechenkomplexität.

Beschränken wir uns auf Quantengates, die auf eine kleine Anzahl von Qubits wirken: Ein Ansatz zur Entscheidung, welche als elementar gelten sollen, wäre die Ausarbeitung eines präzisen Kriteriums – aber das ist nicht der Standardansatz und auch nicht der hier gewählte. Stattdessen treffen wir einfach eine Wahl.

Hier ist eine Standardwahl, die wir als Standard-Gate-Menge für Quantenschaltkreise übernehmen:

• Einzel-Qubit-Unitär-Gates aus dieser Liste: $X,$ $Y,$ $Z,$ $H,$ $S,$ $S^{\dagger},$ $T,$ und $T^{\dagger}$
• Controlled-NOT-Gates
• Einzel-Qubit-Standardbasismessungen

Eine häufige Alternative ist, Toffoli-, Hadamard- und $S$-Gates als elementar zu betrachten, zusätzlich zu Standardbasismessungen. Manchmal werden alle Einzel-Qubit-Gates als elementar angesehen, was aber zu einem unrealistisch mächtigen Modell führt, wenn die Genauigkeit der Gate-Ausführung nicht angemessen berücksichtigt wird.

Die unitären Gates unserer Standard-Sammlung bilden eine sogenannte universelle Gate-Menge. Das bedeutet, dass wir jede unitäre Operation auf beliebig vielen Qubits mit beliebiger Genauigkeit annähern können, und zwar ausschließlich mit Schaltkreisen aus diesen Gates. Die Definition der Universalität stellt dabei keine Anforderungen an die Kosten solcher Approximationen, also die Anzahl der benötigten Gates aus unserer Menge. Tatsächlich zeigt ein relativ einfaches Argument aus dem mathematischen Konzept des Maßes, dass die meisten unitären Operationen extrem hohe Kosten haben müssen. Den Beweis der Universalität von Quanten-Gate-Mengen zu führen ist keine triviale Angelegenheit und wird in diesem Kurs nicht behandelt.

Für Boolesche Schaltkreise betrachten wir AND-, OR-, NOT- und FANOUT-Gates als elementare Operationen. Wir brauchen eigentlich nicht sowohl AND- als auch OR-Gates – mithilfe der De Morganschen Gesetze können wir eines durch das andere ersetzen, indem wir NOT-Gates an alle drei Ein-/Ausgangsleitungen anlegen – aber es ist dennoch üblich und praktisch, beide zuzulassen. AND-, OR-, NOT- und FANOUT-Gates bilden eine universelle Menge für deterministische Berechnungen, d. h. jede Funktion von einer beliebigen festen Anzahl von Eingabebits zu einer beliebigen festen Anzahl von Ausgabebits lässt sich mit diesen Gates implementieren.

Das Prinzip der verzögerten Messung

Standardbasismessungs-Gates können innerhalb von Quantenschaltkreisen auftreten, aber manchmal ist es praktisch, sie bis zum Ende zu verschieben. So können wir Quantenberechnungen als bestehend aus einem unitären Teil (der die eigentliche Berechnung darstellt) betrachten, gefolgt von einer einfachen Auslesephase, in der Qubits gemessen und die Ergebnisse ausgegeben werden. Dies ist immer möglich, sofern wir bereit sind, für jede Standardbasismessung ein zusätzliches Qubit hinzuzufügen. In der folgenden Abbildung illustriert der Schaltkreis rechts, wie dies für das Gate links geschehen kann.

Konkret wird das klassische Bit im linken Schaltkreis durch ein Qubit im rechten Schaltkreis ersetzt (initialisiert im Zustand $\vert 0\rangle$), und die Standardbasismessung wird durch ein Controlled-NOT-Gate ersetzt, gefolgt von einer Standardbasismessung am untersten Qubit. Der Punkt ist, dass die Standardbasismessung im rechten Schaltkreis ans Ende des Schaltkreises verschoben werden kann. Falls das klassische Bit im linken Schaltkreis später als Kontrollbit verwendet wird, kann stattdessen das unterste Qubit im rechten Schaltkreis als Kontrolle dienen, und der Gesamteffekt ist derselbe. (Wir gehen davon aus, dass das klassische Bit im linken Schaltkreis nach der Messung nicht durch eine weitere Messung überschrieben wird – aber falls doch, könnten wir einfach ein neues klassisches Bit verwenden, anstatt ein bereits genutztes zu überschreiben.)

Schaltkreisgröße und -tiefe

Schaltkreisgröße

Die Gesamtzahl der Gates in einem Schaltkreis wird als Größe dieses Schaltkreises bezeichnet. Wenn die Gates in unseren Schaltkreisen elementare Operationen darstellen, gibt die Größe eines Schaltkreises die Anzahl der benötigten elementaren Operationen an – mit anderen Worten: seine Rechenkomplexität. Wir schreiben $\operatorname{size}(C)$ für die Größe eines gegebenen Schaltkreises $C$.

Betrachten wir als Beispiel den folgenden Booleschen Schaltkreis zur Berechnung des XOR zweier Bits.

Die Größe dieses Schaltkreises beträgt 7, da er insgesamt 7 Gates enthält. (FANOUT-Operationen werden nicht immer als Gates gezählt, aber für diese Lektion zählen wir sie als Gates.)

Zeit, Kosten und Schaltkreistiefe

Zeit ist eine entscheidend wichtige Ressource bzw. eine begrenzende Größe bei Berechnungen. Die obigen Beispiele, etwa die Aufgabe, RSA1024 zu faktorisieren, unterstreichen diese Sichtweise. Die Funktion factorint scheitert nicht grundsätzlich daran, RSA1024 zu faktorisieren – es fehlt uns schlicht die Zeit, sie zu Ende laufen zu lassen.

Das Konzept der Rechenkomplexität, aufgefasst als die Anzahl der elementaren Operationen, die zur Durchführung einer Berechnung benötigt werden, soll ein abstraktes Maß für die zur Ausführung einer Berechnung benötigte Zeit sein. Jede elementare Operation erfordert eine gewisse Zeit zur Ausführung, und je mehr davon eine Berechnung benötigt, desto länger dauert sie in der Regel. Der Einfachheit halber setzen wir Rechenkomplexität und die zur Ausführung von Algorithmen benötigte Zeit weiterhin gleich.

Beachte jedoch, dass die Größe eines Schaltkreises nicht unbedingt direkt der Ausführungszeit entspricht. In unserem Booleschen Schaltkreis zur Berechnung des XOR zweier Bits könnten beispielsweise die beiden FANOUT-Gates gleichzeitig ausgeführt werden, ebenso die beiden NOT-Gates sowie die beiden AND-Gates. Eine andere Möglichkeit, die Effizienz von Schaltkreisen zu messen und dabei diese Möglichkeit der Parallelisierung zu berücksichtigen, ist die Tiefe. Das ist die minimale Anzahl von Schichten von Gates innerhalb des Schaltkreises, wobei die Gates jeder Schicht auf verschiedenen Leitungen arbeiten. Äquivalent dazu ist die Tiefe eines Schaltkreises die maximale Anzahl von Gates auf einem beliebigen Pfad von einer Eingangsleitung zu einer Ausgangsleitung. Für den obigen Schaltkreis beispielsweise beträgt die Tiefe 4.

Die Schaltkreistiefe ist eine Möglichkeit, die Laufzeit paralleler Berechnungen zu formalisieren. Es ist ein fortgeschrittenes Thema, und es gibt sehr ausgefeilte Schaltkreiskonstruktionen, die darauf abzielen, die für bestimmte Berechnungen erforderliche Tiefe zu minimieren. Es gibt auch einige faszinierende offene Fragen zur Schaltkreistiefe. (Zum Beispiel ist über die zur Berechnung von GGTs erforderliche Schaltkreistiefe noch vieles unbekannt.) Wir werden in dieser Reihe nicht viel mehr über Schaltkreistiefe sagen, außer einigen interessanten Fakten dazu, aber es sei ausdrücklich festgehalten, dass Parallelisierung eine potenzielle Quelle von Rechenvorteilen ist.

Unterschiedliche Kosten für verschiedene Gates

Ein letzter Hinweis zur Schaltkreisgröße und Rechenkomplexität: Es ist möglich, verschiedenen Gates unterschiedliche Kosten zuzuweisen, anstatt jeden Gate als gleich gewichtet zu betrachten.

Beispielsweise werden FANOUT-Gates bei Booleschen Schaltkreisen häufig als kostenlos angesehen – das heißt, man könnte FANOUT-Gates mit null Kosten bewerten. Als weiteres Beispiel: Im Abfragemodell, wo wir die Anzahl der Abfragen zählen, die ein Schaltkreis an eine Eingabefunktion (in Form einer Black Box) richtet, weisen wir Query-Gates effektiv Einheitskosten zu und anderen Gates, wie Hadamard-Gates, null Kosten. Ein letztes Beispiel ist, dass wir Gates manchmal unterschiedliche Kosten zuweisen, je nachdem, wie schwierig sie zu implementieren sind, was je nach verwendeter Hardware variieren kann.

All diese Optionen sind in unterschiedlichen Kontexten sinnvoll, aber für diese Lektion halten wir es einfach und verwenden die Schaltkreisgröße als Maß für die Rechenkomplexität.

Kosten als Funktion der Eingabelänge

Wir interessieren uns vor allem dafür, wie die Rechenkomplexität skaliert, wenn die Eingaben immer größer werden. Daher stellen wir die Kosten von Algorithmen als Funktionen der Eingabelänge dar.

Schaltkreisfamilien

Eingaben für ein gegebenes Berechnungsproblem können in der Länge variieren und potenziell beliebig groß werden. Jeder Schaltkreis hingegen hat eine feste Anzahl von Gates und Leitungen. Wenn wir also Algorithmen in Form von Schaltkreisen denken, benötigen wir in der Regel unendlich große Familien von Schaltkreisen, um Algorithmen darzustellen. Unter einer Schaltkreisfamilie verstehen wir eine Folge von Schaltkreisen, die an Größe zunehmen und immer längere Eingaben verarbeiten können.

Stellen wir uns zum Beispiel vor, wir haben einen klassischen Algorithmus für die ganzzahlige Faktorisierung, wie den von factorint verwendeten. Wie alle klassischen Algorithmen lässt sich dieser Algorithmus mit Booleschen Schaltkreisen implementieren – aber dazu benötigen wir für jede mögliche Eingabelänge einen eigenen Schaltkreis. Wenn wir die resultierenden Schaltkreise für verschiedene Eingabelängen betrachten, sehen wir, dass ihre Größen natürlicherweise mit der Eingabelänge wachsen – was widerspiegelt, dass die Faktorisierung von 4-Bit-Ganzzahlen viel einfacher ist und weitaus weniger elementare Operationen erfordert als die Faktorisierung von 1024-Bit-Ganzzahlen.

Dies führt dazu, dass wir die Rechenkomplexität eines Algorithmus durch eine Funktion $t$ darstellen, wobei $t(n)$ die Anzahl der Gates in dem Schaltkreis ist, der den Algorithmus für $n$-Bit-Eingaben implementiert. Formal ist ein Algorithmus im Booleschen Schaltkreismodell durch eine Folge von Schaltkreisen $\{C_1, C_2, C_3,\ldots\}$ beschrieben, wobei $C_n$ das betreffende Problem für $n$-Bit-Eingaben löst (oder allgemeiner für Eingaben, deren Größe durch $n$ parametrisiert ist), und die Kostenfunktion $t$ ist definiert als

$$t(n) = \operatorname{size}(C_n).$$

Für Quantenschaltkreise ist die Situation ähnlich: Für immer längere Eingaben werden immer größere Schaltkreise benötigt.

Beispiel: Ganzzahlige Addition

Zur weiteren Veranschaulichung betrachten wir kurz das Problem der ganzzahligen Addition, das deutlich einfacher ist als die ganzzahlige Faktorisierung oder sogar die Berechnung von GGTs.

Ganzzahlige Addition

Eingabe: ganze Zahlen $N$ und $M$
Ausgabe: $N+M$

Wie könnten wir Boolesche Schaltkreise zur Lösung dieses Problems entwerfen?

Der Einfachheit halber beschränken wir uns auf den Fall, dass $N$ und $M$ nichtnegative ganze Zahlen sind, die durch $n$-Bit-Zeichenketten in Binärdarstellung repräsentiert werden. Wir erlauben beliebig viele führende Nullen in diesen Kodierungen, sodass gilt:

$$0\leq N,M\leq 2^n - 1.$$

Die Ausgabe ist eine $(n+1)$-Bit-Binärzeichenkette, die die Summe darstellt – das ist die maximale Anzahl von Bits, die wir zur Darstellung des Ergebnisses benötigen.

Wir beginnen mit einem Algorithmus – dem Standardalgorithmus für die Addition von Binärdarstellungen –, der das Basis-2-Analogon zu dem Verfahren ist, das in Grundschulen auf der ganzen Welt gelehrt wird. Dieser Algorithmus lässt sich mit Booleschen Schaltkreisen wie folgt implementieren.

Ausgehend von den niedrigstwertigen Bits können wir deren XOR berechnen, um das niedrigstwertige Bit der Summe zu ermitteln. Dann berechnen wir das Übertragsbit, das das UND der beiden niedrigstwertigen Bits von $N$ und $M$ ist. Diese beiden Operationen zusammen werden manchmal als Halbaddierer bezeichnet.

Mit dem XOR-Schaltkreis, den wir nun mehrfach gesehen haben, zusammen mit einem AND-Gate und zwei FANOUT-Gates können wir einen Halbaddierer mit 10 Gates bauen. Wenn wir uns anders entschieden und XOR-Gates in unsere elementaren Operationen aufgenommen hätten, würden wir 1 AND-Gate, 1 XOR-Gate und 2 FANOUT-Gates für einen Halbaddierer benötigen.

Bei den höherwertigen Bits gehen wir ähnlich vor, berücksichtigen aber diesmal das Übertragsbit aus der vorangegangenen Position. Durch Hintereinanderschalten zweier Halbaddierer und Berechnung des ODER der von ihnen erzeugten Übertragebits erhalten wir einen sogenannten Volladdierer.

Dafür werden insgesamt 21 Gates benötigt: 2 AND-Gates, 2 XOR-Gates (jedes erfordert 7 Gates zur Implementierung), ein OR-Gate und 4 FANOUT-Gates.

Durch Hintereinanderschalten der Volladdierer erhalten wir schließlich einen Booleschen Schaltkreis für die Addition nichtnegativer ganzer Zahlen. Der folgende Schaltkreis beispielsweise berechnet die Summe zweier 4-Bit-Ganzzahlen.

Im Allgemeinen werden dafür

$$21 (n-1) + 10 = 21 n - 11$$

Gates benötigt. Hätten wir XOR-Gates in unsere elementaren Operationen aufgenommen, würden wir $2n-1$ AND-Gates, $2n-1$ XOR-Gates, $n-1$ OR-Gates und $4n-2$ FANOUT-Gates benötigen, also insgesamt $9n-5$ Gates. Zählen wir zusätzlich FANOUT-Gates nicht mit, sind es $5n-3$ Gates.

Asymptotische Notation

Einerseits ist es gut zu wissen, wie viele Gates genau für verschiedene Berechnungen benötigt werden, wie im obigen Beispiel der ganzzahligen Addition. Diese Details sind wichtig für den tatsächlichen Bau der Schaltkreise.

Andererseits werden wir sehr schnell von Details überwältigt, wenn wir alle uns interessierenden Berechnungen auf diesem Detailniveau analysieren – einschließlich solcher, die weitaus komplizierter als die Addition sind. Um die Dinge handhabbar zu halten und Nebensächlichkeiten bewusst auszublenden, verwenden wir bei der Algorithmenanalyse typischerweise die Landau-Notation (auch Big-O-Notation). Mit dieser Notation können wir die Wachstumsordnung von Funktionen ausdrücken.

Formal schreiben wir, wenn wir zwei Funktionen $g(n)$ und $h(n)$ haben, $g(n) = O(h(n))$, falls eine positive reelle Zahl $c > 0$ und eine positive ganze Zahl $n_0$ existieren, sodass

$$g(n) \leq c\cdot h(n)$$

für alle $n \geq n_0$ gilt. Üblicherweise wird $h(n)$ so einfach wie möglich gewählt, damit die Notation das asymptotische Verhalten einer Funktion in einfachen Worten beschreibt. Zum Beispiel gilt $17 n^3 - 257 n^2 + 65537 = O(n^3)$.

Diese Notation lässt sich auf Funktionen mit mehreren Argumenten recht unkompliziert erweitern. Wenn wir beispielsweise zwei Funktionen $g(n,m)$ und $h(n,m)$ auf positiven ganzen Zahlen $n$ und $m$ haben, schreiben wir $g(n,m) = O(h(n,m))$, falls eine positive reelle Zahl $c > 0$ und eine positive ganze Zahl $k_0$ existieren, sodass

$$g(n,m) \leq c\cdot h(n,m)$$

für alle $n+m \geq k_0$ gilt.

Dieses Konzept auf das Beispiel der nichtnegativen ganzzahligen Addition angewendet: Es existiert eine Familie Boolescher Schaltkreise $\{C_1, C_2,\ldots,\}$, wobei $C_n$ zwei $n$-Bit-Ganzzahlen addiert, mit $\operatorname{size}(C_n) = O(n)$. Dies zeigt das wesentliche Merkmal, wie die Komplexität der Addition mit der Eingabelänge skaliert: linear.

Beachte auch, dass es nicht auf das spezifische Detail ankommt, ob wir XOR-Gates die Kosten 1 oder 7 zuweisen. Im Allgemeinen erlaubt uns die Landau-Notation, Aussagen über Rechenkomplexität zu treffen, die von solchen Details auf niedriger Ebene unabhängig sind.

Weitere Beispiele

Hier sind einige weitere Beispiele für Probleme aus der algorithmischen Zahlentheorie, beginnend mit der Multiplikation.

Ganzzahlige Multiplikation

Eingabe: ganze Zahlen $N$ und $M$
Ausgabe: $NM$

Boolesche Schaltkreise für dieses Problem zu erstellen ist schwieriger als für die Addition – aber wenn wir an den Standardmultiplikationsalgorithmus denken, können wir auf Schaltkreise der Größe $O(n^2)$ kommen (unter der Annahme, dass $N$ und $M$ beide als $n$-Bit-Binärdarstellungen repräsentiert sind). Allgemeiner gilt: Hat $N$ $n$ Bits und $M$ $m$ Bits, existieren Boolesche Schaltkreise der Größe $O(nm)$ zur Multiplikation von $N$ und $M$.

Tatsächlich gibt es andere Multiplikationsverfahren, die besser skalieren. So kann der Schönhage-Strassen-Multiplikationsalgorithmus genutzt werden, um Boolesche Schaltkreise zur Multiplikation zweier $n$-Bit-Ganzzahlen mit Kosten $O(n \operatorname{lg}(n) \operatorname{lg}(\operatorname{lg}(n)))$ zu erstellen. Der erhebliche Overhead dieser Methode macht sie jedoch nur für Zahlen mit Zehntausenden von Bits praktisch.

Ein weiteres grundlegendes Problem ist die Division, womit wir die Berechnung von Quotient und Rest bei gegebenem Divisor und Dividenden meinen.

Ganzzahlige Division

Eingabe: ganze Zahlen $N$ und $M\neq0$
Ausgabe: ganze Zahlen $q$ und $r$ mit $0\leq r < |M|$ und $N = q M + r$

Die Kosten der ganzzahligen Division sind ähnlich wie bei der Multiplikation: Hat $N$ $n$ Bits und $M$ $m$ Bits, existieren Boolesche Schaltkreise der Größe $O(nm)$ zur Lösung dieses Problems. Und wie bei der Multiplikation sind asymptotisch überlegene Methoden bekannt.

Nun können wir bekannte Algorithmen zur GGT-Berechnung mit denen für Addition und Multiplikation vergleichen. Der euklidische Algorithmus zur Berechnung des GGT einer $n$-Bit-Zahl $N$ und einer $m$-Bit-Zahl $M$ benötigt Boolesche Schaltkreise der Größe $O(nm)$, ähnlich wie die Standardalgorithmen für Multiplikation und Division. Ähnlich wie bei Multiplikation und Division sind auch asymptotisch schnellere GGT-Algorithmen bekannt – darunter solche, die $O(n(\operatorname{lg}(n))^2 \operatorname{lg}(\operatorname{lg}(n)))$ elementare Operationen erfordern, um den GGT zweier $n$-Bit-Zahlen zu berechnen.

Eine etwas aufwändigere Berechnung aus der Zahlentheorie ist die modulare Exponentiation.

Ganzzahlige modulare Exponentiation

Eingabe: ganze Zahlen $N,$ $K,$ und $M$ mit $K\geq 0$ und $M\geq 1$
Ausgabe: $N^K \hspace{1mm} (\text{mod }M)$

Mit $N^K\hspace{1mm} (\text{mod }M)$ meinen wir den Rest bei der Division von $N^K$ durch $M$, also die eindeutige ganze Zahl $r$ mit $0\leq r < M$ und $N^K = q M + r$ für eine ganze Zahl $q$.

Hat $N$ $n$ Bits, $M$ $m$ Bits und $K$ $k$ Bits, kann dieses Problem von Booleschen Schaltkreisen der Größe $O(k m^2 + nm)$ gelöst werden. Das ist keineswegs offensichtlich. Die Lösung besteht nicht darin, zuerst $N^K$ zu berechnen und dann den Rest zu nehmen, was exponentiell viele Bits allein zur Speicherung der Zahl $N^K$ erfordern würde. Stattdessen kann der Potenzierungsalgorithmus (auch bekannt als binäre Methode und wiederholtes Quadrieren) verwendet werden, der die Binärdarstellung von $K$ nutzt, um die gesamte Berechnung modulo $M$ durchzuführen. Sind $N$, $M$ und $K$ alle $n$-Bit-Zahlen, ergibt sich ein $O(n^3)$-Algorithmus – also ein kubischer Algorithmus. Und wieder sind komplexere, aber asymptotisch schnellere Algorithmen bekannt.

Kosten der ganzzahligen Faktorisierung

Im Gegensatz zu den soeben besprochenen Algorithmen sind bekannte Algorithmen für die ganzzahlige Faktorisierung viel aufwändiger – wie wir es aus der früheren Diskussion in dieser Lektion erwarten würden.

Ein einfacher Ansatz zur Faktorisierung ist die Probedivision, bei der ein Algorithmus die Liste $2,\ldots,\sqrt{N}$ nach einem Primfaktor einer Eingabezahl $N$ durchsucht. Dies erfordert im schlechtesten Fall $O(2^{n/2})$ Iterationen, wenn $N$ eine $n$-Bit-Zahl ist. Jede Iteration erfordert eine Probedivision, was mit einem Standardalgorithmus für ganzzahlige Division $O(n^2)$ elementare Operationen pro Iteration bedeutet. Wir erhalten Schaltkreise der Größe $O(n^2 2^{n/2})$, was exponentiell in der Eingabelänge $n$ ist.

Es gibt Algorithmen für die ganzzahlige Faktorisierung mit besserer Skalierung. Das zuvor erwähnte Zahlkörpersieb beispielsweise, ein Algorithmus, der Zufälligkeit nutzt, benötigt nach allgemeiner Ansicht (aber ohne strengen Beweis)

$$2^{O(n^{1/3} (\operatorname{lg}(n))^{2/3})}$$

elementare Operationen, um $n$-Bit-Ganzzahlen mit hoher Wahrscheinlichkeit zu faktorisieren. Zwar ist es durchaus bemerkenswert, dass $n$ in diesem Ausdruck nur mit dem Exponenten $1/3$ auftritt, aber die Tatsache, dass es überhaupt im Exponenten erscheint, führt weiterhin zu schlechter Skalierung – und erklärt zum Teil, warum RSA1024 außerhalb seines Anwendungsbereichs liegt.

Polynomialer versus exponentieller Aufwand

Klassische Algorithmen für ganzzahlige Addition, Multiplikation, Division und die Berechnung des größten gemeinsamen Teilers ermöglichen es uns, diese Probleme für Eingaben mit Tausenden von Bits im Handumdrehen zu lösen. Addition hat linearen Aufwand, während die anderen drei Probleme quadratischen Aufwand haben (oder subquadratischen Aufwand bei asymptotisch schnellen Algorithmen). Die modulare Exponentiation ist aufwändiger, lässt sich aber immer noch recht effizient mit kubischem Aufwand bewältigen (oder subkubisch bei asymptotisch schnellen Algorithmen).

All das sind Beispiele für Algorithmen mit polynomialem Aufwand, d. h. sie haben Kosten $O(n^c)$ für eine feste Konstante $c > 0$. Als grobe Näherung erster Ordnung gelten Algorithmen mit polynomialem Aufwand abstrakt als effiziente Algorithmen.

Im Gegensatz dazu haben bekannte klassische Algorithmen für die ganzzahlige Faktorisierung exponentiellen Aufwand. Manchmal wird der Aufwand des Zahlkörpersiebs als subexponentiell bezeichnet, weil $n$ im Exponenten mit dem Faktor $1/3$ auftritt, aber in der Komplexitätstheorie ist es üblicher, diesen Begriff für Algorithmen zu reservieren, deren Aufwand

$$O\bigl(2^{n^{\varepsilon}}\bigr)$$

für jedes $\varepsilon > 0$ beträgt. Die sogenannten NP-vollständigen Probleme sind eine Klasse von Problemen, für die kein polynomialer Algorithmus bekannt ist (und allgemein angenommen wird, dass keiner existiert). Eine schaltkreisbasierte Formulierung der Exponentialzeithypothese postuliert sogar noch Stärkeres: dass kein NP-vollständiges Problem einen subexponentiellen Algorithmus haben kann.

Die Gleichsetzung von Algorithmen mit polynomialem Aufwand und effizienten Algorithmen muss als grobe Abstraktion verstanden werden. Natürlich wäre es übertrieben, einen Algorithmus, dessen Aufwand wie $n^{1000}$ oder $n^{1000000}$ für Eingaben der Länge $n$ skaliert, als effizient zu bezeichnen. Aber selbst ein Algorithmus mit einem Aufwand von $n^{1000000}$ tut etwas Cleveres, um exponentiellen Aufwand zu vermeiden, der im Allgemeinen bei Algorithmen erwartet wird, die auf „roher Gewalt" oder „erschöpfender Suche" basieren. Selbst die ausgefeiltesten Varianten des Zahlkörpersiebs beispielsweise scheitern daran, diese exponentielle Skalierung zu vermeiden. Algorithmen mit polynomialem Aufwand hingegen nutzen die Problemstruktur auf eine Art und Weise aus, die eine exponentielle Skalierung verhindert.

In der Praxis ist die Identifizierung eines Algorithmus mit polynomialem Aufwand für ein Problem nur ein erster Schritt hin zu echter Effizienz. Durch algorithmische Verbesserungen können Algorithmen mit polynomialem Aufwand und großen Exponenten manchmal erheblich verbessert werden, sodass der Aufwand auf ein „vernünftigeres" polynomiales Niveau sinkt. Manchmal werden Dinge einfacher, wenn klar ist, dass sie möglich sind – die Identifizierung eines polynomialen Algorithmus für ein Problem kann auch den Anstoß für noch effizientere Algorithmen geben.

Wenn wir uns mit den Vorteilen des Quantencomputings gegenüber dem klassischen Computing befassen, richten wir unsere Aufmerksamkeit in der Regel zunächst auf exponentielle Vorteile oder zumindest superpolynomiale Vorteile – idealerweise finden wir Quantenalgorithmen mit polynomialem Aufwand für Probleme, für die kein klassischer Algorithmus mit polynomialem Aufwand bekannt ist. Theoretische Vorteile dieser Größenordnung haben die größten Chancen, zu tatsächlichen praktischen Vorteilen zu führen – aber solche Vorteile zu identifizieren ist eine äußerst schwierige Herausforderung. Bislang sind nur wenige Beispiele bekannt, aber die Suche geht weiter.

Polynomiale (aber nicht superpolynomiale) Vorteile in der Rechenkomplexität von Quanten- gegenüber klassischen Algorithmen sind ebenfalls interessant und sollten nicht abgetan werden – aber angesichts der aktuellen Lücke zwischen Quanten- und klassischer Computertechnologie erscheinen sie derzeit weniger überzeugend. Eines Tages könnten sie jedoch bedeutsam werden. Grovers Algorithmus beispielsweise, der in einer späteren Lektion behandelt wird, bietet einen quadratischen Vorteil von Quanten- gegenüber klassischen Algorithmen für die sogenannte unstrukturierte Suche und hat das Potenzial für breite Anwendungen.

Versteckte Kosten der Schaltkreisberechnung

Abschließend sei noch ein letzter Punkt erwähnt, dem wir in diesem Kurs aber nicht weiter nachgehen werden. Es gibt eine „versteckte" Rechenkomplexität beim Arbeiten mit Schaltkreisen, die die Spezifikationen der Schaltkreise selbst betrifft. Mit zunehmender Eingabelänge werden immer größere Schaltkreise benötigt – aber um diese zu implementieren, müssen wir irgendwie an die Beschreibungen dieser Schaltkreise gelangen.

Bei allen besprochenen oder in späteren Lektionen diskutierten Beispielen gibt es einen zugrundeliegenden Algorithmus, aus dem die Schaltkreise abgeleitet werden. In der Regel folgen die Schaltkreise einer Familie einem grundlegenden Muster, das sich leicht auf immer größere Eingaben extrapolieren lässt – etwa das Hintereinanderschalten von Volladdierern für Boolesche Additionsschaltkreise oder das Ausführen von Schichten aus Hadamard-Gates und anderen Gates in einem einfach beschreibbaren Muster.

Aber was passiert, wenn mit den Mustern in den Schaltkreisen selbst unvertretbar hohe Berechnungskosten verbunden sind? Zum Beispiel könnte die Beschreibung jedes Elements $C_n$ in einer Schaltkreisfamilie im Prinzip durch eine extrem schwer zu berechnende Funktion von $n$ bestimmt sein.

Die Antwort lautet: Das ist tatsächlich ein Problem – und daher müssen wir Schaltkreisfamilien, die echte effiziente Algorithmen darstellen sollen, über den polynomialen Aufwand hinaus weiteren Einschränkungen unterwerfen. Die Eigenschaft der Uniformität für Schaltkreise trägt dem Rechnung, indem sie in verschiedenen präzisen Formulierungen fordert, dass die Beschreibung jedes Schaltkreises in einer Familie effizient berechenbar ist. Alle hier besprochenen Schaltkreisfamilien besitzen diese Eigenschaft – aber dies ist dennoch ein wichtiger Punkt, den man beim formalen Studium von Schaltkreismodellen der Berechnung im Auge behalten sollte.