Podcasts about d wave two

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

Materials Available here: https://media.defcon.org/DEF%20CON%2023/DEF%20CON%2023%20presentations/DEFCON-23-John-Seymour-Quantum-Classification-of-Malware-UPDATED.pdf Whitepaper here: https://media.defcon.org/DEF%20CON%2023/DEF%20CON%2023%20presentations/DEFCON-23-John-Seymour-Quantum-Classification-of-Malware-WP-UPDATED.pdf "Quantum" Classification of Malware John Seymour Ph.D. student, University of Maryland, Baltimore County Quantum computation has recently become an important area for security research, with its applications to factoring large numbers and secure communication. In practice, only one company (D-Wave) has claimed to create a quantum computer which can solve relatively hard problems, and that claim has been met with much skepticism. Regardless of whether it is using quantum effects for computation or not, the D-Wave architecture cannot run the standard quantum algorithms, such as Grover’s and Shor’s. The D-Wave architecture is instead purported to be useful for machine learning and for heuristically solving NP-Complete problems. We'll show why the D-Wave and the machine learning problem for malware classification seem especially suited for each other. We also explain how to translate the classification problem for malicious executables into an optimization problem which a D-Wave machine can solve. Specifically, using a 512-qubit D-Wave Two processor, we show that a minimalist malware classifier, with cross-validation accuracy comparable to standard machine learning algorithms, can be created. However, even such a minimalist classifier incurs a surprising level of overhead. John Seymour is a Ph.D. student at the University of Maryland, Baltimore County, where he performs research at the intersection of machine learning and information security. He's mostly interested in avoiding and helping others avoid some of the major pitfalls in machine learning, especially in dataset preparation (seriously, do people still use malware datasets from 1998?) In 2014, he completed his Master’s thesis on the subject of quantum computation applied to malware analysis. He currently works at CyberPoint International, a company which performs network and host-based machine learning, located in Baltimore, MD.

In this nerdy episode, we discuss the D-Wave Two quantum computer that recently went online. To warm up the audience, we open with a game concept related to natural language processing and semantic analysis.