Open Source im professionellen Einsatz
Linux-Magazin Online Artikel/
447

Algorithmus Advanced

Der Deutsch-Jozsa-Algorithmus beantwortet die Frage, ob eine Funktion f konstant (zum Beispiel f(x)=0) oder alternierend ist (zum Beispiel f(0)=0, f(1)=1, f(2)=0, ...).

Mit einem klassischen Rechner sind mindestens zwei Aufrufe der algebraischen Funktion f nötig, um die Frage zu beantworten. Der Deutsch-Jozsa-Algorithmus hingegen liefert die richtige Antwort mit nur einem einzelnen Funktionsaufruf (Listing 4). Dieser einfache Quantenalgorithmus ist also jedem klassischen Algorithmus überlegen.

Der Grund ist, dass der Deutsch-Jozsa-Algorithmus nach einem Aufruf der algebraischen Funktion alle möglichen Eingangswerte in eine Superposition bringt und damit auch alle Funktionswerte in einer Superposition vorliegen. Die Funktion wird praktisch für alle Werte gleichzeitig ausgewertet. Welcher Fall (konstant oder alternierend) vorliegt, kann über die Variable constant gesteuert werden. Um den binären Endzustand zu erreichen, wird die Superposition nach dem Funktionsaufruf wieder aufgehoben und das Ergebnis gemessen. Ist die Funktion konstant, liefert die Messung eine 1, ist sie alternierend, eine 0.

Listing 4: Der Deutsch-Jozsa-Algorithmus

#include <quantum.h>
#include <time.h>
#include <stdlib.h>
#include <stdio.h>

void f (quantum_reg *reg)
{
  int constant = 0;
  if(!constant)
    quantum_cnot(0, 2, reg);
}

int main ()
{
  quantum_reg reg;
  srand(time(0));
  reg = quantum_new_qureg(5, 3);
  quantum_hadamard(0, &reg);
  quantum_hadamard(1, &reg);
  quantum_hadamard(2, &reg);
  f(&reg);
  quantum_hadamard(0, &reg);
  quantum_hadamard(1, &reg);
  printf("Ergebnis: %i\n", quantum_bmeasure(0, &reg));
  return 0;
}

Immer grüßt die Dekohärenz

Um auch die in einem Quantencomputer unvermeidbaren Fehler durch Dekohärenz zu berücksichtigen, schaltet der Programmierer die Dekohärenz-Effekte zu Beginn der Simulation ein:

quantum_set_decoherence(0.1);

Damit wird nach jedem Quantengatter ein zufälliger Phasenfehler auf jedes Qubit angewendet. Der Parameter der Funktion gibt die Stärke des Phasenfehlers an.

Allerdings ist der simulierte Quantencomputer der Dekohärenz nicht hoffnungslos ausgeliefert. Quantenfehlerkorrekur-Verfahren (quantum error correction, QEC) sind in der Lage, die Auswirkungen von Fehlern durch Dekohärenz einzudämmen. QEC kann in Libquantum bequem mit

quantum_qec_encode(1, 3, &reg);

aktiviert werden. Der erste Parameter bezeichnet das verwendete Verfahren (hier der Steane-Algorithmus). Der zweite Parameter gibt die Anzahl der mit QEC zu schützenden Qubits an. Nach der Rechnung kann QEC mittels

quantum_qec_decode(1, 3, &reg);

wieder abgeschaltet werden und Messungen können wie gewohnt vor sich gehen.

Vergleich der Erfolgswahrscheinlichkeiten für den Deutsch-Jozsa-Algorithmus unter Berücksichtigung von Dekohärenz und QEC.

Abbildung 3 zeigt die Auswirkungen von Dekohärenz und QEC auf eine Variante des Deutsch-Jozsa-Algorithmus. Ohne Dekohärenz wird stets das richtige Ergebnis gemessen. Finden dagegen die Fehler durch Dekohärenz Berücksichtigung, aber keine QEC wird durchgeführt, sinkt die Wahrscheinlichkeit für das richtige Ergebnis deutlich ab. Bei Verwendung von QEC steigt die Wahrscheinlichkeit wieder an.

Der Endzustand des Shor-Algorithmus ist ein typisches Beispiel für einen Zustand mit nur wenigen relevanten Basiszuständen.
Die Ausgabe des Programms aus Listing 1 zeigt von links nach rechts: Die Amplitude des Basiszustands, den Basiszustand in Dirac-Notation, die Wahrscheinlichkeit des Basiszustands in Dezimalform und schließlich den Basiszustand in Binärdarstellung.

Linux-Magazin kaufen

Einzelne Ausgabe
 
Abonnements
 
TABLET & SMARTPHONE APPS
Bald erhältlich
Get it on Google Play

Deutschland

Ähnliche Artikel

  • Quantenrechner simulieren, Teil 1

    Die quelloffene C-Bibliothek Libquantum ermöglicht simuliertes Quantencomputing auf einem gewöhnlichen PC. Der erste Teil des zweiteiligen Artikels führt in Quantencomputing ein und endet mit einer allgemeinen Beschreibung von Libquantum. Der zweite Teil zeigt an einem Beispiel, was sich mit der Libquantum-Bibliothek anstellen lässt.

  • Quantenrechner simulieren - jetzt auch mit Hamilton

    Die C-Bibliothek Libquantum erreicht Version 1.0.0 und erhält gleichzeitig eine neue Entwicklerversion 1.1.0. Die GPL-Software hilft, quantenmechanische Systeme auf normalen Rechnern zu simulieren.

  • IBM Q: Qubits as a Service

    Für kommerzielle Zwecke will IBM in den kommenden Jahren über seine Cloud den Zugriff auf stärkere Quantencomputer anbieten. Angepeilt sind rund 50 Qubit.

  • Programmbibliothek für Quantensimulation springt auf Version 0.9.1

    Die C-Bibliothek Libquantum springt nach fast drei Jahren von Version 0.2.4 auf 0.9.1. An Bord ist ein neues API, mit dem sich quantenmechanische Zustände simulieren lassen.

  • Intel investiert 50 Millionen in Quantencomputer

    Intel, die Forschungseinheit QuTech der Delft University of Technology und die Niederländische Organisation für Angewandte Naturwissenschaftliche Forschung (TNO) arbeiten zukünftig eng in der Erforschung von Quantencomputern zusammen. Im Rahmen der zehnjährigen Kooperationsvereinbarung investiert Intel 50 Million US-Dollar sowohl am Universitätsstandort in Delft als auch in den Intel-eigenen Standorten weltweit.

comments powered by Disqus

Ausgabe 05/2017

Digitale Ausgabe: Preis € 7,62
(inkl. 19% MwSt.)

Artikelserien und interessante Workshops aus dem Magazin können Sie hier als Bundle erwerben.