Podcasts about logikgattern

In dieser Episode vollenden wir das CLOCK-Modul unseres SAP-1 Computers. Wir konzentrieren uns darauf die beiden Arbeitsmodi des Moduls, den kontinuierlichen Modus aus WAD001 und den Einzelschrittmodus aus WAD002, zusammenzuführen. Hierfür bauen wir ein Schaltnetz aus verschiedenen Logikgattern nach Ben Eaters Vorbild auf.

Im Anschluss ihres Erasmus-Auslandsjahr in Lyon hat sich Alexandra Krause als angehende Physikerin in den Bereich der Quanteninformatik vertieft. Dazu hat sie im Rahmen der Gulasch Programmiernacht (GPN16) des Entropia e.V. in der Hochschule für Gestaltung und dem ZKM in Karlsruhe über Quantum Speedup (video) vorgetragen und Zeit gefunden, uns auch im Podcast etwas über das Thema zu erzählen. Im Gegensatz zur klassischen Physik gelten in der Quantenmechanik eigene Regeln: So geht es hier um Teilchen in der Größenordnung von Atomen, wo die Begriffe Teilchen und Welle verschwimmen und der quantenmechanische Zustand unbeobachtet nur noch als Zustandsgemisch beschrieben werden kann. Genau diese Eigenschaft will man sich beim Quantencomputer zu Nutze machen, wo gegenüber dem klassischen digitalen Computer, der immer auf einzelnen festen Zuständen in Bits mit Logikgattern rechnet, der Quantenrechner pro Schritt in Qubits auf allen Zuständen gleichzeitig operiert. Das eigentliche Ergebnis erhält man dort erst bei der Messung, wodurch sich der reine Zustand des Quantensystems einstellt. Der Grover-Algorithmus ist eine bekannte Anwendung für einen Quantencomputer, der Datenbanken schneller als klassische Verfahren durchsuchen kann. Der Shor-Algorithmus kann hingegen mit einer Quanten-Fouriertransformation in polynomialer Zeit Zahlen in ihre Primfaktoren zerlegen kann. Damit werden viele assymetrische Kryptoverfahren wie das RSA-Verfahren obsolet, da sie auf der Schwierigkeit der klassischen Faktorisierung basieren. Shor hat in der gleichen Publikation auch ein Verfahren zur effizienten Berechnung von diskreten Logarithmen auf Quantencomputern veröffentlicht, so dass auch Kryptoverfahren auf elliptischen Kurven durch Quantencomputer gebrochen werden, die neben dem RSA-Verfahren Basis für viele Kryptowährungen sind. Zum jetzigen Zeitpunkt ist es der Experimentalphysik noch nicht gelungen, allgemeine Quantensysteme in einer Größe zu erschaffen, die für sinnvolle Anwendungen der Verfahren erforderlich wären. Die Schwierigkeit liegt darin, den Quantenzustand einzelner Qubits von der Umwelt abzukoppeln und nur für die Berechnung zu verwenden, wenn doch alles in der Umgebung in Bewegung ist. In der Größe weniger Qubits, die allgemeine Quantencomputer bisher erreichen konnten, wurden Zahlen wie 15 und 21 erfolgreich faktorisiert. Eine Hoffnung besteht hier auf dem adiabatischen Quantencomputer auf Basis adiabatischen Theorems, der von der Firma D-Wave Systems gebaut, und 2011 mit unvergleichlich vielen 128 Qubits auf den Markt gebracht wurde. Das Problem ist dabei, dass adiabatischen Quantencomputer im normalen Arbeitszustand keine universellen Quantencomputer sind, und hauptsächlich Optimierungsprobleme lösen können. Universelle Quantencomputer können im Circuit model anschaulich jedes herkömmliches Programm abbilden: Jedes klassische Logik-Gatter kann durch Hinzufügen weiterer Ausgänge reversibel werden, und dann als eine unitäre Abbildung oder Matrizen im Quantencomputer realisiert werden. Unitäre Abbildungen sind lineare Abbildungen mit der Eigenschaft, dass sie das komplexe Skalarprodukt zweier Vektoren nach der Abbildung erhalten, d.h. Vektoren behalten die gleiche Länge, und zwei Vektoren behalten den gleichen Winkel zueinander. Der Nachteil des reversiblen Ansatzes ist jedoch, dass dafür womöglich viele Bits benötigt werden, wenn man die Abbildungen nicht zuvor zusammenfassen kann. Theoretisch kann der adiabatische Quantencomputer auch universell sein, nur ist dazu ideal eine ungestörte Umgebung Voraussetzung, was in Realität nicht erreicht werden kann. Es verbleiben Optimierungsprobleme, die über den Hamiltonoperator abgebildet werden können: physikalische Prozesse möchten den energetisch niedrigsten Zustand zu erreichen. Ein Beispiel sind hier Minimalflächen, wie sie von Seifenhäuten und Seifenblasen angenommen werden- und auch zum Bau des Olympiageländes in München genutzt wurden. Im Schülerlabor für Mathematik in Karlsruhe kann man auch viele Experimente dazu durchführen. Wenn man ein Optimierungsproblem lösen möchte, so sind lokale Minima ein Problem- in ihrer Umgebung erscheinen sie als Lösung, sie sind es jedoch insgesamt betrachtet nicht. Eine Möglichkeit die lokalen Minima zu umgehen ist das Verfahren des Simulated Annealing. Hier wird durch externe Störquellen begünstigt, dass lokale Minima verlassen werden, um das globale Minimum zu erreichen. In Quantensystemen spielt hier beim Quantum Annealing zusätzlich der Tunneleffekt eine besondere Rolle, wodurch die Störung noch leichter von lokalen Minima hinweg streut. Dadurch ist das Quantum Annealing prinzipiell und aus der Theorie schneller- oder zumindest nicht langsamer- als das Simulated Annealing. Dabei ist das Quantum Annealing natürlich nur auf einem Quantencomputer effizient umsetzbar. Das ist dabei ein Beispiel für eine Quantensimulation auf einem Quantencomputer in dem Forschungsfeld, das sich mit der Abbildung und Simulation von Quantensystemen befasst. Damit ist der adiabatische Quantencomputer auf eine kleinere Klasse von lösbaren Problemen beschränkt, jedoch soll er dieses mit einer erheblichen höheren Anzahl von Qubits durchführen können- zur Zeit der Aufnahme waren dies mit dem D-Wave Two etwa 512 Qubits. Die Frage, ob diese adiabatischen Quantencomputer mit dieser großen Anzahl von Qubits wirklich als Quantencomputer arbeiten, wurde wissenschaftlich diskutiert: Im Artikel Evidence for quantum annealing with more than one hundred qubits legen die Autoren dar, dass der betrachtete adiabatische Quantencomputer starke Anzeichen für die tatsächliche Umsetzung des Quantum Annealing zeigt. In wie weit jedoch nun eine quantenbedingte Beschleunigung feststellen ist, diskutieren T. Rønnow und Mitautoren in der Arbeit Defining and detecting quantum speedup. Sie erhielten das ernüchternde Ergebnis, dass eine Beschleunigung durch Nutzung des betrachteten Quantensystems nicht eindeutig nachgewiesen werden konnte. Dagegen argumentierten V. Denchev et al. in What is the Computational Value of Finite Range Tunneling?, dass eine 100'000'000-fache Beschleunigung mit hoher Wahrscheinlichkeit gegenüber einem Einprozessor-System nachgewiesen werden kann. Ein Problem bei der Analyse ist, dass die betrachteten Algorithmen für den Quantencomputer in den Bereich der probabilistischen Algorithmen fallen, die Ergebnisse also eine Fehlerwahrscheinlichkeit besitzen, die durch mehrfache Ausführung verringert werden kann. In der Kryptographie werden probabilistische Primzahltests sehr häufig eingesetzt, die auch in diese Klasse der Algorithmen fallen. So wurde im ersten Paper das Verhalten des Quantencomputers in einer Vielzahl von Versuchen mit simulierten Algorithmen verglichen und mit hoher Wahrscheinlichkeit festgestellt, dass der D-Wave-Rechner tatsächlich den Quantum Annealing Algorithmus ausführt. Über den D-Wave-Rechner ist bekannt, dass die einzelnen Qubits durch supraleitende Ringe abgebildet sind und die beiden Stromlaufrichtungen die superpositionierten Zustände darstellen. Die Kopplung zwischen Qubits und nach außen erfolgt durch Spulen, die über die entstehenden Magnetfelder mit den Strömen in den Ringen interagieren. Die Kopplung zwischen Qubits wird damit durch die parametrisierte Kopplung der Spulen realisiert. Für klassische Algorithmen und parallelisierte Computersysteme beschreibt der Begriff des Speedup die Effizienzsteigerung durch Nutzung einer erhöhten Parallelisierung. Je nach Algorithmus gibt es nach Amdahls Gesetz logische Grenzen, wo weitere Parallelisierung keine Gewinn mehr erzielt. Entsprechend besteht der Wunsch den Begriff des Quantum Speedup analog zu definieren und nachzuweisen: Diesen Ansatz verfolgten T. Rønnow und Mitautoren und definierten verschiedene Klassen von Quantum Speedup, wobei der adiabatische D-Wave Quantencomputer für sie nur Anzeichen für ein potentielles Speed-up ergab. Das ist ein ernüchterndes Ergebnis, wobei die Autoren klar weiteren Forschungsbedarf sahen. Hier war das Paper von V. Denchev und Mitautoren eine große Überraschung, wo dem D-Wave 2X Rechner mit hoher Wahrscheinlichkeit eine Beschleunigung von 10^8 nachgesagt wurde. Neben den Annealing-Verfahren kam hier auch Quantum Monte Carlo zum Einsatz. Im Ergebnis erhielten sie für die Annealing-Verfahren ein asymptotisches Speed-Up, das sich für größere Problemstellungen einstellt, für Quantum Monte Carlo eine von der Problemgröße unabhängige Beschleunigung gegenüber einem klassischen Single-core Rechner. Diese Aussagen trafen aber schnell auf Widerstand und den Nachweis, dass ein im Paper betrachtetes Problem mit anderen Algorithmen teilweise auf einem klassischen Rechner vielfach schneller gelöst werden kann als auf dem Quantencomputer. Literatur und weiterführende Informationen S. Boixo, et al.: Evidence for quantum annealing with more than one hundred qubits, Nature Physics 10.3: 218-224, 2014. T. Rønnow, et al.: Defining and detecting quantum speedup, Science 345.6195: 420-424, 2014. V. Denchev, et al.: What is the Computational Value of Finite Range Tunneling? arXiv preprint arXiv:1512.02206, 2015. R. Harris, R., et al.: Compound Josephson-junction coupler for flux qubits with minimal crosstalk, Physical Review B 80.5: 052506, 2009. S. Ritterbusch: Digitale Währungen, Gespräch mit G. Thäter im Modellansatz Podcast, Folge 32, Fakultät für Mathematik, Karlsruher Institut für Technologie (KIT), 2014. http://modellansatz.de/digitale-waehrungen E. Dittrich: Schülerlabor, Gespräch mit G. Thäter im Modellansatz Podcast, Folge 103, Fakultät für Mathematik, Karlsruher Institut für Technologie (KIT), 2016. http://modellansatz.de/schuelerlabor Bernd Fix: Post-Quantum Krypto, Afra-Berlin.de, Vortrag am 13.12.2013. F. Rieger, F. von Leitner: Fnord Jahresrückblick, 32c3, Vortrag am 29.12.2015. S. Aaronson: Google, D-Wave, and the case of the factor-10^8 speedup for WHAT? Blog-Post mit Updates 16.5.2013-16.12.2015. Quantum Annealing Solver für den Laptop

Seit 2002 veranstaltet der Entropia e.V. in Karlsruhe jährlich die Gulaschprogrammiernacht, das ist ein mehrtägiger Kongress, wo Nerds, Häcksen und Maker ihre Projekte vorstellen, Erfahrungen austauschen und Vorträgen lauschen. Die GPN15 fand Anfang Juni 2015 im ZKM und der HfG Karlsruhe statt, und zog diesmal auch Mathe-Begeisterte an: Florian Gilges ist mit dem Life Science Lab als Schüler nach Karlsruhe gekommen, und will unter anderem Näherungen an die Kreiszahl effizient berechnen. Dazu baut er sich einen eigenen Computer. Im Gespräch mit Sebastian Ritterbusch erklärt er uns, wie er dazu logische Gatter aus rotem Erz baut. Zunächst ist die Kreiszahl (Pi) als das Verhältnis von Umfang zu Durchmesser eines beliebigen Kreises definiert und ermöglicht uns mit der Formel auch aus dem Radius die Fläche eines Kreises zu berechnen. Da Pi jedoch eine sogenannte irrationale und transzendente Zahl ist (d.h. dass nach dem Komma unendlich viele Stellen folgen, die keine Wiederholung aufweisen), lässt sich der Wert nie exakt angeben. Um nun eine Näherung für Pi zu berechnen, lassen sich verschiedene Verfahren verwenden: Ein Kreis wird gezeichnet und Umfang und Durchmesser gemessen, das Verhältnis ist dann eine Näherung an Pi. Eine andere Möglichkeit ist die Berechnung durch eine Winkelfunktion: Der Arkustangens hat bei 1 den Wert . Nimmt man also die Taylorentwicklung des Arkustangens mit x=1 und multipliziert mit 4, erhält man Pi. Neben der (von der Konvergenzgeschwindigkeit) relativ ineffizienten Taylor-Reihe gibt es noch viele weitere Verfahren, die ebenfalls Pi annähern. Die Berechnung will Florian in Minecraft durchführen, und baut sich dafür einen Rechner innerhalb dieses Spiels. Aber wie kann ein einfaches Spiel so etwas bieten? Schließlich ist Minecraft nur eine Nachahmung unserer Welt mit ganz natürlichen Ressourcen. So bietet eine Minecraft-Welt verschiedene Vegetations- und Klimazonen und verschieden Landschaften und Umgebungen, wie z.B. Laubwälder, Nadelwälder, Steppen, Wüsten, Schneegebiete, uvm. Es gibt jedoch auch Stoffe, die es in unserer Welt nicht gibt: Einer davon ist Redstone. Dieser besondere Stoff kann in Höhlen tief unter der Erde als Erz gefunden werden und gibt abgebaut ein Pulver, das ähnliche Eigenschaften, wie elektrische Leitungen hat. Aus Redstone-Pulver und weiteren Materialien, die man in der Welt findet, lassen sich Logikelemente bauen: Inverter, Verstärker, Verzögerer und Vergleicher. Diese Basiselemente können vom Spieler in die Welt gebaut und zu großen Schaltungen zusammengesetzt werden. Angefangen bei einfachen Speichern und Signalstärkespeichern (Redstone-Energie hat 16 Stufen von 0 bis 15), bis hin zu Logikgattern, wie UND-Gatter, XOR-Gatter und Flip-Flops. Kurzum lassen sich mit den Basiselementen alle Komponenten für einen Computer zusammenstellen, aber auch einfachere Dinge, wie Code-Schlösser und Tür-Steuerungen sind möglich. Doch so einfach, wie es nun erscheint, ist es nicht, denn jedes Basiselement hat eine Verzögerung von mindestens einer Zehntel- bis vier Zehntelsekunden. Das bedeutet, dass der Computer sehr langsam wird und Berechnungen sehr aufwendig werden. Deshalb ist Optimierung sehr wichtig, indem an jeder Stelle die Bauteile effizienter gemacht werden und die Mathematik zur Berechung ebenfalls (für den Computer) effizienter gestaltet wird. Hier konnte Florian das XOR-Gatter und den Programm-Zähler aus Halbaddierern und Volladdierern durch intelligente Kniffe deutlich beschleunigen. Eine weitere Möglichkeit besteht auch in der Nutzung von redundanten Binärdarstellungen, die bei einer großen Anzahl von Additionen große Geschwindigkeitsvorteile bringen können. Neben der Optimierung der Hardware ist auch die Optimierung der Software wichtig, was zur Mathematik zurückführt: Berechnungen wie Multiplikationen, Potenzen oder Wurzeln sind auf Logikebene komplizierte Operationen, auch wenn unsere Taschenrechner die Aufgaben in Sekundenbruchteilen lösen. Der einfachste Weg für die Multiplikation ist, dass man eine Additionskette bildet: . Führt man dieses Verfahren mit größeren Zahlen durch, wächst der Aufwand linear. Ein anderes Verfahren ist die schriftliche Multiplikation, aber es geht noch effizienter: Die Russische Bauernmultiplikation. Mit etwas Übung lassen sich so, wenn gerade kein Taschenrechner da ist, auch große Zahlen multiplizieren. Für den Computer sind jedoch beide Verfahren durch das Binärsystem äquivalent. Komplizierter sind dann schon Wurzeln. Diese lassen sich nicht so leicht berechnen, wie eine Addition oder Multiplikation. Ein mögliches Näherungsverfahren ist das Heron-Verfahren. Es gibt jedoch auch das schriftliche Wurzelziehen, das im Binärsystem leicht zu implementieren ist. Florian hat sich diese Techniken aus Videos wie dem Youtube-Kanal Schoolseasy selbst angelernt.