GI-Radar 267: Quo vadis Quantencomputing?

Sehr geehrte Leserinnen und Leser,

in den Kurzmitteilungen geht es in dieser Ausgabe unter anderem um das Thema Open Data. Im Thema im Fokus beschäftigen wir uns intensiv mit Quantencomputern. Über eine neue Initiative zur Stärkung der Hochschulen für Angewandte Wissenschaften innerhalb der GI lesen Sie etwas in den GI-Mitteilungen. Das Fundstück setzt sich kritisch mit dem Weltbild auseinander, das uns in aktuellen Science-Fiction-Serien gezeigt wird.

Wir wünschen Ihnen viel Spaß mit dieser Ausgabe!

auf gi-radar.de weiterlesen

KURZMITTEILUNGEN

NSA hilft beim sicheren Arbeiten im Homeoffice (heise). Die National Security Agency hat Empfehlungen veröffentlicht, wie Konfigurationen für ein sicheres Arbeiten im Homeoffice aussehen sollten. Darin gibt sie Hilfestellungen, wie IPsec und VPN-Verbindungen abgesichert werden können.  weiterlesen

Berliner Datenschutzbehörde legt Leitfaden zu Videokonferenzdiensten vor (FAZ). Die Berliner Datenschutzbeauftragte hat die beliebtesten Webkonferenzdienste unter die Lupe genommen und nach einem Ampelsystem bewertet. Kaum ein System hat bei dieser Prüfung Bestand.  weiterlesen*

Tech-Konzerne widersetzen sich chinesischem Sicherheitsgesetz (Standard). Die großen Tech-Konzerne haben beschlossen, keine Daten ihrer Nutzerinenn und Nutzer an Behörden in Hongkong weiterzugeben. Mit dem Sicherheitsgesetz verstößt China nach Ansicht von Menschenrechtsorganisationen gegen die Autonomie Hongkongs.  weiterlesen

Modell soll Corona-Ausbruch vorhersagen (New York Times, engl.). Amerikanische Wissenschaftler forschen an Algorithmen, die den Ausbruch von Pandemien vorhersagen sollen. Anhand von Nachrichten in den sozialen Netzwerken wird versucht, die Wahrscheinlichkeit zu errechnen, wann und wo mit einem Ausbruch zu rechnen ist.  weiterlesen

Bäume gießen mit Open Data (Berliner Zeitung). Das Schlagwort „Open Data“ meint, offizielle Daten öffentlich zu machen. Wer welche Daten veröffentlicht, liegt häufig im Belieben der Städte. Manche Stadt veröffentlicht die Standorte der Altglascontainer, andere Städte stellen die Daten der Verkehrsflüsse zur Verfügung. Angesichts der trockenen Monate sollen nun die Standorte der Berliner Bäume und deren Wohlbefinden veröffentlicht werden, um die Bevölkerung zum Gießen zu animieren.  weiterlesen

* Artikel ist ggf. nur mit deaktiviertem Adblocker lesbar.

THEMA IM FOKUS

Quo vadis Quantencomputing? Quantencomputing verspricht nichts Geringeres als die Etablierung eines neuen Ansatzes Berechnungen durchzuführen. Dieser soll den Vorstoß in neue Anwendungsgebiete der Informatik erlauben, umgesetzt durch Computer, die auf den Gesetzen der Quantenmechanik beruhen. Zum Einsatz kommen sollen Algorithmen für dieses neue Berechnungsmodell, die mit ihrer Leistungsfähigkeit Problemstellungen adressieren, deren praktische Lösbarkeit bisher außer Reichweite lag. Wie steht es um diese Vision und wo stehen und gehen wir auf dem Weg dorthin?

Nach wegbereitenden Resultaten wie dem No-Cloning-Theorem in den 1960er und 1970er Jahren, existiert die explizite Formulierung des Konzepts eines Quantencomputers seit den 1980er Jahren. Es geht zurück auf Ideen von Paul Benioff und Richard Feynman. Sie sahen in diesen Maschinen vor allem das Potenzial, Simulationen quantenmechanischer physikalischer Systeme gegenüber „klassischen Computern“ (damit bezeichnen wir hier heutige Rechner sowie äquivalente Rechenmodelle wie Turingmaschinen) zu beschleunigen. Nach einigen eher akademischen Problemen, deren theoretische Lösung mit dem Quantencomputing-Paradigma beginnend mit dem Algorithmus von Deutsch demonstriert wurde, fand die Thematik in den 1990er Jahren mit den Arbeiten von Peter Shor und Lov Grover große Beachtung. Mit Quantenalgorithmen für das Faktorisierungsproblem und die sogenannte unstrukturierte Datenbanksuche gab es nun bereits zwei Beispiele für Verfahren, die einer Lösung mit klassischen Computern allem Anschein nach überlegen sind und einen exponentiellen bzw. polynomiellen Speed-up gegenüber etablierten Verfahren bieten. Darüber hinaus stellen sie für erstere der genannten Problemstellungen die Sicherheit der Public-Key-Infrastruktur in Frage und riefen damit sogar Geheimdienste auf den Plan.

Seither ist der Quantenalgorithmen-Zoo (https://quantumalgorithmzoo.org/) bereits in den 2000er Jahren erheblich angewachsen und adressiert eine ganze Reihe von Problemtypen und Problemstellungen. Im Kern vieler Algorithmen stecken dabei die Ideen der beiden Pioniere in der einen oder anderen Form – etwa die Quanten-Fouriertransformation. Eine hervorragende Übersicht zu diesen nun quasi schon „klassischen“ Themen des Quantencomputings und der Quanteninformation findet man etwa im Standardwerk von Michael A. Nielsen und Isaac L. Chuang. Die meisten dieser Verfahren haben gemein, dass sie einen universellen und fehlerkorrigierten Quantencomputer benötigen, um praktisch zu skalieren bzw. zu funktionieren.

Etwa das Jahr 2010 markiert ein Umdenken hin zu praktischeren Problemstellungen, die insbesondere in den Bereichen Optimierung und Maschinelles Lernen, aber auch bei der Simulation physikalischer Systeme zu finden sind. In diese Zeit fällt – nach ersten Implementierungen um die Jahrtausendwende – die verstärkte praktische Entwicklung von Quantenrechnern, beginnend mit Quantenannealern als Implementierungen des Adiabatischen Quantencomputing-Modells, und ab etwa 2015 zunehmend durch Implementierungen des immer stärker fokussierten Gate-Modells.

Angewandtes Quantencomputing. Die heute oft genannten Rechner, vertreten etwa mit dem IBM Q System, der Implementierung von Rigetti oder auch dem Sycamore-Prozessor von Google, sind allesamt Vertreter dieses Rechenmodells. Im Jahr 2018 prägte John Preskill für die mit diesen Maschinen andauernde Phase den Begriff NISQ-Ära des Quantencomputings („Noisy Intermediate-Scale Quantum“). Er bezeichnet damit Quantenrechner mit 50–100 Qubits und nur begrenzten Möglichkeiten zur Fehlerkorrektur. Diese erlauben eine Ausführung beliebig tiefer Schaltkreise zwar noch nicht, können aber für bestimmte Aufgaben die Leistung klassischer Computer bereits übertreffen – wie etwa jener für die Quantensupremacy-Demonstration im Oktober 2019 eingesetzte 53-Qubit Prozessor von Google. Dennoch wurde die Informatik-Welt dadurch noch nicht tiefgreifend verändert. Eine synthetische Aufgabe konnte in 200 Sekunden mittels Sycamore-Chip gelöst werden, anstelle – je nach Lesart in 10000 Jahren (Aussage Google) oder 2,5 Tagen (Aussage IBM) – bei Ausführung auf dem zu dieser Zeit leistungsfähigsten klassischen Supercomputer Summit von IBM. Dies markiert also immerhin einen Speed-up um den Faktor 1080 bis 1,578 Mrd.

Die NISQ-Ära hat auch auf algorithmischer Seite verstärkte Anstrengungen hervorgebracht – etwa verschiedene Verfahren des überwachten Lernens und der kombinatorischen Optimierung für diese Maschinen, die Entwicklung verschiedener Frameworks zur Implementierung der Algorithmen und erste anwendungsorientierte Fachbücher zur Thematik (vgl. Maria Schuld und Francesco Petruccione zum überwachten Lernen und Jack D. Hidary zu Anwendungen des Quantencomputings).

Hybride Algorithmen für Maschinelles Lernen und Optimierung. Die heutigen Algorithmen ordnen sich dabei in das Schema der sogenannten hybriden quanten-klassischen Algorithmen bzw. variierbaren Schaltkreise ein. Hierbei wird ein nicht allzu tiefgeschichteter parametrierter Quantenschaltkreis durch einen klassischen Rechner unter Variation dieser Parameter iterativ mehrfach ausgeführt. Der klassische Anteil des Algorithmus optimiert dabei die Ausgabe des Quantenschaltkreises bezüglich einer Zielfunktion – etwa mittels Gradientenabstieg oder unter Anwendung anderer klassischer Optimierungsverfahren.

Nach diesem Prinzip arbeiten die derzeit vielversprechendsten Algorithmen – z.B. VQE (Variational Quantum Eigensolver), verschiedene QNN-Varianten (Quantum Neural Network) oder auch QAOA (Quantum Approximate Optimization Algorithm), und bedienen mit Simulation, Maschinellem Lernen und kombinatorischer Optimierungdrei potenzielle Anwendungsgebiete moderner Quantenalgorithmen. Die Leistungsfähigkeit klassischer Algorithmen auf diesen Gebieten wird dabei am ehesten bei der Simulation physikalischer Systeme erreicht, da der Ressourcenverbrauch zur Simulation von Quantensystemen mit klassischen Rechnern unter Anwendung aktueller (und wohl auch künftiger) Verfahren exponentiell wächst.

Für Optimierungsverfahren und ML-Algorithmen ist die Leistungsfähigkeit gegenwärtiger Implementierungen i.d.R. noch nicht in die Nähe klassischer Verfahren gelangt, aber die Liste der verfügbaren Algorithmen ist bereits lang. Sie beinhaltet neben den schon genannten Verfahren Quantenvarianten von SVMs, PCA, Boltzmann-Maschinen, Reinforcement Learning, Bayesscher Inferenz, Convolutional NN oder Rekurrenten NN, die unter Nutzung quantenspezifischer algorithmischer Strategien wie z.B. Amplitudenverstärkung gegenüber ihren klassischen Verwandten gemäß theoretischer Analysen eine polynomielle oder gar superpolynomielle Beschleunigung realisieren.

Potenziale und Grenzen. Erhebliche Potenziale des Quantencomputing-Ansatzes und der entsprechenden Algorithmen bestehen in eben diesen Verbesserungen des Laufzeitverhaltens und der Speicheranforderungen von Algorithmen. Darüber hinaus kommen einige Arbeiten zu dem Ergebnis, dass Quantenverfahren auch andere Vorzüge gegenüber klassischen Algorithmen haben können, beim Maschinellen Lernen etwa in puncto Generalisierungsfähigkeit.

Die Vorteile von Quantenverfahren basieren im Wesentlichen auf der Nutzung der Ressourcen Superposition und Verschränkung als grundlegende Eigenschaften der Quantenwelt, zu denen es bei den Berechnungsmodellen klassischer Computer keine Äquivalente gibt. Gute Quantenalgorithmen nutzen diese Eigenschaften geschickt aus, um Quantenzustände – also den Speicherzustand des Quantencomputers – so zu manipulieren, dass das Ergebnis der gewünschten Rechnung möglichst zügig erzeugt wird, was bei vielen Verfahren übrigens nur mit einer bestimmten Wahrscheinlichkeit gelingt: Quantencomputing ist inhärent probabilistisch. Die Komplexitätsklasse der Probleme, für deren Lösung es einen effizienten Quantenalgorithmus gibt, heißt BQP (Bounded Error Quantum Polynomial Time) – die Klasse der Probleme, die auf einem Quantenrechner mit Fehlerwahrscheinlichkeit höchstens 1/3 in Polynomialzeit lösbar sind. BQP enthält die klassischen Komplexitätsklassen P, da Quantencomputer klassische Rechner effizient simulieren können, und BPP (Bounded Error Probabilistic Polynomial Time) – das „klassische Äquivalent“ zu BQP – jedoch nach allem was wir wissen und annehmen (etwa P≠NP) nicht die Klasse der NP-vollständigen Probleme. Diese bleiben also auch für Quantencomputer „schwierig“.

Weiterhin ist bekannt, dass BQP in der Klasse PSPACE der klassisch mit einem polynomiellen Platzbedarf lösbaren Probleme enthalten ist, und der Beweis dessen durch die Simulation eines Quantenschaltkreises mit einem klassischen Rechner macht direkt klar, dass Quantencomputer die Klasse der entscheidbaren Sprachen nicht erweitern, da sie eben allesamt von klassischen Rechnern simuliert werden können; vermutlich aber eben nicht alle auch effizient. Somit sind die Grenzen des Quantencomputing-Ansatzes in Bezug auf Effizienz und Berechenbarkeit in diesem Rahmen „grob“ abschätzbar. Was bleibt sind signifikante Vorteile für Quantenrechner bei der Anwendung auf Probleme wie die Faktorisierung natürlicher Zahlen, die – vermutlich – nicht in BPP, wohl aber in BQP liegen. Weitere relevante Vertreter dieser Problemklasse gilt es zu identifizieren. Klar ist auch, dass diese Komplexitätsbetrachtungen polynomielle Speed-ups unberücksichtigt lassen, diese also generell erlauben, was praktisch dann erheblichen Vorteilen entsprechen kann.

Für einige Verfahren des Maschinellen Lernens werden wie beschrieben Speed-ups unterschiedlichen Ausmaßes erwartet. Bei Problemstellungen der Optimierung geht man von ähnlichen Resultaten aus. Komplexitätsbetrachtungen des Quantencomputings sind heute in vielen Details untersetzt, vgl. etwa https://complexityzoo.uwaterloo.ca/Complexity_Zoo:Q. Beachten Sie z.B. das spannende Resultat MIP*=RE einer neuen Charakterisierung der Menge der rekursiv aufzählbaren Sprachen von Ji et al. vom Januar 2020 (https://arxiv.org/abs/2001.04383).

Quantenhardware und Quantenvolumen. Kaum betrachtet wurde in dieser kurzen Einstimmung bisher das Thema Quantenhardware. Fakt ist, dass die Entwicklung von Quantenhardware große Fortschritte macht und auch weiterhin erwarten lässt. Prinzipiell verdoppelt sich – von Verlusten durch Fehlerkorrektur usw. einmal abgesehen – die Leistung eines Quantencomputers mit der Hinzunahme eines einzelnen weiteren Qubits. Eine Größe, die die Leistungsfähigkeit von Quantenrechnern repräsentieren soll und neben der Anzahl der Qubits auch Fehlerraten, die Konnektivität zwischen Qubits sowie darüber hinausgehende Parameter einbezieht, ist das sogenannte Quantenvolumen. Dessen exponentielles Wachstum soll das Moorsche Gesetz ablösen. IBM strebt eine jährliche Verdopplung dieser Leistungskenngröße an. Beim 28-Qubit-Rechner IBM Raleigh liegt sie derzeit bei 32 (Stand Januar 2020); Honeywell beansprucht ein Quantenvolumen von 64 für den eigenen Quantenrechner (Stand Juni 2020).

Es findet also ein spannendes Rennen statt. Neben den genannten Protagonisten gibt es eine Reihe weiterer, die ebenfalls an eigenen Quantenmaschinen arbeiten. Mit der Weiterentwicklung der Hardware (vgl. neben den genannten Unternehmen auch Microsoft, AQT, Xanadu, etc.), der Algorithmen wie oben beschrieben, der Programmiersprachen (etwa Python, Q# oder Silq) und der Software-Frameworks (z.B. Cirq, Qiskit, PennyLane, TensorFlow Quantum) werden Quantenrechner aller Voraussicht nach weiterhin zügig an Leistung gewinnen und damit immer relevanter werden und – so zumindest die Erwartung – Bereiche der Überlegenheit gegenüber klassischen Rechnern immer deutlicher markieren.

GI-Arbeitskreis „Quantencomputing“. Das ist Grund genug für die GI, das Thema auch in unserer Fachgesellschaft intensiver zu betrachten und einen Arbeitskreis „Quantencomputing“ ins Leben zu rufen.

Wir laden Sie herzlich zum Austausch im Rahmen dieses AK ein – diejenigen, die sich ebenfalls mit dem Thema Quantencomputing auseinandersetzen oder dies vorhaben, sind aufgerufen, sich bei Prof. Dr. Jörg Lässig (joerg.laessig@iosb-ast.fraunhofer.de), Fraunhofer IOSB-AST und Hochschule Zittau/Görlitz zu melden. Wir danken ihm für die Zusammenstellung des vorliegenden Artikels. Feedback, Ideen und Anregungen zum Thema sind ausdrücklich erwünscht.

GI-MELDUNGEN

Steffen Friedrich erhält Verdienstorden der Bundesrepublik. Steffen Friedrich, langjähriger Sprecher des Fachausschusses für informatische Bildung an Schulen in der GI, Aktivist in Sachsen in Sachen Informatik an der Schule und unermüdlicher Streiter für eine fundierte Vermittlung informatischer Inhalte, ist mit dem Verdienstorden der Bundesrepublik ausgezeichnet worden. Wir freuen uns und gratulieren ihm.  weiterlesen

Unterstützung für Mentoring-Team gesucht. Unser Mentoring-Programm wächst und gedeiht. Ins Leben gerufen vom GI-Beirat für den wissenschaftlichen Nachwuchs und den GI-Junior-Fellows, ist es ein vergleichsweise kleines Team, das sich um alles kümmert: Außendarstellung, Matching, Technik, Kommunikation mit Mentorinnen, Mentoren und Mentees, Zeitplanung, Fragebogenerstellung … also um das ganze Kleine hinter der großen Idee. Hier sind wir nun auf der Suche nach Interessierten, die Lust haben, uns dabei zu unterstützen. Einmal im Monat besprechen wir via Webkonferenz die Aufgaben. Bei Interesse bitte Meldung an das Mentoring-Team!  weiterlesen

Hochschulen für Angewandte Wissenschaften (HAW) in der GI. Der GI-Beirat für Professorinnen und Professoren an HAWs hat sich im GI-Präsidium vorgestellt und die Situation der HAWs und der dort Studierenden in Deutschland skizziert. Von Semesterwochenstunden über Forschungsgelder und Kooperationen mit Unternehmen gab es vielerlei zu lernen. Der Beirat möchte sich nun stärker vernetzen und sucht nach Interessierten.  weiterlesen

Fachleute für die grafische Modellierung gesucht. Im Rahmen des von der GI mitgetragenen Forschungsprojektes KEA-Mod wird ein Kompetenzmodell für die grafische Modellierung in der (Wirtschafts-) Informatik entwickelt. Das Ziel ist, die Kompetenzorientierung in Lern- und Prüfungssituationen in den Hochschulen zu erhöhen. Unterstützen Sie bitte das Projektteam bei der Kompetenzmodellerstellung durch Ihre Teilnahme an der Online-Befragung.  weiterlesen

Kolleginnen und Kollegen gesucht! Die Geschäftsstellen in Bonn und Berlin suchen weiterhin Unterstützung. In Bonn suchen wir jemanden, der sich in der Finanzbuchhaltung um die administrative Projektabwicklung kümmert, in Berlin suchen wir eine Projektleitung für die KI-Forschungs-Convention.  weiterlesen

Neues Informatik Spektrum zu vertrauenswürdiger Kommunikation ist da. Vor einiger Zeit haben wir Sie hier im Radar zu vertrauenswürdiger Kommunikation mittels dezentralen Technologien befragt. Aus dieser Umfrage hat Präsidiumsmitglied Andrea Herrmann ein ganzes Informatik Spektrum auf die Beine gestellt, das verschieden Aspekte und Technologien beleuchtet und vorstellt.  weiterlesen

FUNDSTÜCK

Der digitale Körper in der Cloud: Serien „denken“ die Zukunft. Digitale Mitbewohner wurden bereits in früheren Serien erdacht, ebenso wie der autonome Kühlschrank. Heutige Science Fiction-Serien nehmen die heutige Technologie und denken sie weiter. Es wird befürchtet, dass die Privatsphäre künftig komplett verschwindet und damit Science Fiction realistischer ist, als uns lieb sein kann.   Zum Fundstück (golem.de, 15 min)

Welches Fundstück hat Sie zuletzt inspiriert? Senden Sie uns Ihre Ideen!

Dies war Ausgabe 267 des GI-Radars. Zusammengestellt hat sie Dominik Herrmann, der das auch mit einem Quantenrechner nicht schneller geschafft hätte. Die Mitteilungen hat GI-Geschäftsführerin Cornelia Winter zusammengetragen. Das nächste GI-Radar erscheint am 24. Juli 2020.

Im GI-Radar berichten wir alle zwei Wochen über ausgewählte Informatik-Themen. Wir sind sehr an Ihrer Meinung interessiert. Für Anregungen und Kritik haben wir ein offenes Ohr, entweder per E-Mail (redaktion@gi-radar.de) oder über das Feedback-Formular bei SurveyMonkey. Links und Texte können Sie uns auch über Twitter (@informatikradar) zukommen lassen.