Wie würde ich das Quantenorakel in Deutschs Algorithmus implementieren?

Ich versuche, den Algorithmus von Deutsch zu simulieren (elementarer Fall des Deutsch-Josza-Algorithmus), und ich bin mir nicht ganz sicher, wie ich das für die Funktion des Algorithmus erforderliche Quantenorakel implementieren würde, ohne den Zweck des Algorithmus zu vereiteln und "zu schauen". bei was die eingegebene Funktion ist, durch Auswertung der Funktion.

Hier gibt es zwei Fragen. Der erste fragt, wie Sie dies tatsächlich in Code implementieren könnten, und der zweite fragt, was der Sinn ist, wenn Sie wissen, welches Orakel Sie übergeben.

Implementierung

Der wahrscheinlich beste Weg ist, eine Funktion zu erstellen, IsBlackBoxConstantdie das Orakel als Eingabe verwendet und dann das Programm Deutsch Oracle ausführt, um festzustellen, ob es konstant ist. Sie können das Orakel nach dem Zufallsprinzip auswählen, wenn Sie möchten. Hier ist es, implementiert in Q #:

operation IsBlackBoxConstant(blackBox: ((Qubit, Qubit) => ())) : (Bool)
{
    body
    {
        mutable inputResult = Zero;
        mutable outputResult = Zero;

        // Allocate two qbits
        using (qbits = Qubit[2])
        {
            // Label qbits as inputs and outputs
            let input = qbits[0];
            let output = qbits[1];

            // Pre-processing
            X(input);
            X(output);
            H(input);
            H(output);

            // Send qbits into black box
            blackBox(input, output);

            // Post-processing
            H(input);
            H(output);

            // Measure both qbits
            set inputResult = M(input);
            set outputResult = M(output);

            // Clear qbits before release
            ResetAll(qbits);
        }

        // If input qbit is 1, then black box is constant; if 0, is variable
        return One == inputResult;
    }
}

Was ist der Sinn?

Komplexität der Abfrage

Die Komplexität der Berechnungen ist ein Bereich, in dem Algorithmen nach der Menge der Ressourcen klassifiziert werden, die sie als Funktion der Eingabegröße verbrauchen. Diese Ressourcen umfassen Zeit (gemessen in Schritten / Anweisungen), Speicher und auch etwas, das als Abfragekomplexität bezeichnet wird . Die Komplexität der Abfrage hängt davon ab, wie oft ein Algorithmus eine Black-Box-Orakelfunktion abfragen muss.

$n$$2^{n-1}$

$2^{n-1}$

Anwendungen in der realen Welt

Wenn Sie kein Komplexitätstheoretiker sind, interessiert Sie die Komplexität von Abfragen möglicherweise nicht so sehr und Sie möchten stattdessen wissen, warum das Deutsch-Orakel-Problem in einer Welt ohne Regeln wichtig ist, in der Sie in die Black Box schauen dürfen. Der Versuch, ein Orakelproblem als Nicht-Orakel-Problem zu analysieren, ist mit Schwierigkeiten verbunden, und ich glaube nicht, dass jemand die Frage nach dem besten klassischen Algorithmus für das Deutsche Orakel-Problem gelöst hat, wenn Sie die Orakelschaltung analysieren dürfen. Sie könnten denken - was gibt es zu analysieren? Es gibt nur vier mögliche Schaltkreise! In der Tat ist es viel komplizierter.

Wenn wir uns die einfachste Darstellung des Ein-Bit-Deutsch-Orakels ansehen , ist die Gate-Konstruktion wie folgt:

$C_{1,0}$

$X_0C_{1,0}$

$\mathbb{I}_4$

$X_0$

Dies ist jedoch keineswegs die einzige Möglichkeit, die Orakel zu implementieren. All dies kann mit Hunderten, Tausenden oder sogar Millionen von Logikgattern umgeschrieben werden! Alles, was zählt, ist die kumulative Wirkung dieser Logikgatter, die der obigen einfachen Konstruktion entspricht. Betrachten Sie die folgende alternative Implementierung von Constant-1:

$H_0Z_0H_0$

Es stellt sich heraus, dass für jede Eingabe, die Sie jemals geben könnten:

$H_0Z_0H_0|\psi\rangle = X_0|\psi\rangle$

$H_0Z_0H_0$$X_0$

$H_0Z_0H_0 = \begin{bmatrix} \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} & \frac{-1}{\sqrt{2}} \end{bmatrix} \begin{bmatrix} 1 & 0 \\ 0 & -1 \end{bmatrix} \begin{bmatrix} \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} & \frac{-1}{\sqrt{2}} \end{bmatrix} = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} = X_0$

Also haben wir:

$(H_0(Z_0(H_0|\psi\rangle))) = (((H_0Z_0)H_0)|\psi\rangle) = X_0|\psi\rangle$

$H_0Z_0H_0$$X_0$

Wichtig aus historischen und pädagogischen Gründen

In erster Linie ist das Deutsch-Oracle-Problem aus historischen und pädagogischen Gründen wichtig. Es ist der erste Algorithmus, der den Schülern beigebracht wird, weil er der einfachste ist und die Quantenbeschleunigung zu demonstrieren scheint, solange Sie nicht zu viele Fragen stellen. Es dient auch als guter Ausgangspunkt, um Simons Periodizitätsproblem und dann Shors Algorithmus zu lernen.

Es gibt keine Möglichkeit, das Orakel so zu bauen, dass der Sinn des deutschen Algorithmus nicht zunichte gemacht wird - deshalb handelt es sich um einen orakelbasierten Algorithmus.

$x$$f(x)$$f(0)=f(1)$

$f(x)$$1 \leq x \leq N$$f(x)$$y$$f(x+y)=f(x)$$f(x)$

Der Punkt ist also, dass orakelbasierte Algorithmen beweisen, dass Sie eine Beschleunigung erzielen können, wenn Sie ein Problem mit dieser Struktur haben (dh wenn Sie nur eine bestimmte Eigenschaft einer Funktion lernen möchten), aber es sagt Ihnen nicht, ob Ein solches Problem besteht.

Wenn Sie also Deutsch implementieren möchten, ist jede Art, das Orakel zu tun, in Ordnung - es ist ein "Proof-of-Principle" -Algorithmus und führt nicht zu einer tatsächlichen Beschleunigung eines echten Problems (zumindest keine, die wir kennen).

Auf der IBM Q Experience-Seite finden Sie zwei Beispiele zum Algorithmus . Sie zeigen ein Beispiel für eine Funktion. Dies könnte Sie für Ihre Simulationen inspirieren, hoffe ich.

Ich habe kein Beispiel für den Algorithmus von Deutsch zur Hand, aber hier und hier finden Sie zwei Tutorials, die Sie durch die Implementierung des Deutsch-Jozsa-Algorithmus und der in Q # verwendeten Orakel führen.

Die Idee für diese beiden Algorithmen ist dieselbe: Sie müssen dem Algorithmus das Orakel als eine an anderer Stelle implementierte Operation bereitstellen. Auf diese Weise weiß der Algorithmus nicht, welches Orakel ihm gegeben wird, und hat keine andere Möglichkeit, das Orakel zu "betrachten", als es aufzurufen. Diese Tutorials haben auch ein Gurtzeug, das zählt, wie oft das Orakel aufgerufen wird. Wenn Ihre Lösung es mehrmals aufruft, besteht es den Test nicht.

Zugegeben, dies hat immer noch ein Problem, das Orakelalgorithmen häufig haben: Ein Mensch kann die Implementierung des Tests und des bestandenen Orakels betrachten und die Antwort herausfinden, indem er herausfindet, welches Orakel implementiert ist. Dem kann durch zufällige Auswahl der Orakelauswahl entgegengewirkt werden, wie DaftWullie vorgeschlagen hat.

Ich denke, diese ahelwerAntwort berührt einige der Arten, wie wir über die Komplexität von Algorithmen denken. Angesichts der Tatsache, dass wir in der realen Welt buchstäblich keine "Orakel" haben, die wir abfragen möchten, fragen Sie sich vielleicht, warum wir uns über die Komplexität der Abfragen oder die Idee von Orakeln überhaupt Gedanken machen würden. Ich werde versuchen, eine Perspektive zu geben und insbesondere zu beschreiben, wie Sie versuchen könnten, Wege zu finden, um ein "Deutsch-Josza-Orakel" so zu konstruieren, dass Sie nicht das Gefühl haben, zu betrügen.

(Wie bereits erwähnt Norbert Schuch, gibt es für das Deutsch-Problem, das der elementare Fall von Deutsch-Josza ist, nicht viel Raum für Einsichten, aber ich gehe davon aus, dass Ihre Frage zu Orakeln auch allgemeiner gilt. Darauf werde ich hier eingehen.)

Eine Intuition über Orakel

Das Konzept eines Orakels ist eine Möglichkeit, die Art und Weise, wie wir über Rechenprobleme sprechen, zu vereinfachen.

Die ursprüngliche Anwendung des Orakelkonzepts bestand darin, hypothetisch zu überlegen, was wir tun könnten, wenn wir schwierige oder sogar unmögliche Probleme lösen könnten, ohne uns dazu zu verpflichten, wie wir es auch im Prinzip tun könnten. In Bezug auf die Komplexität der Berechnungen heutzutage - insbesondere bei der Quantenberechnung, z. B.  bei Deutsch-Josza, Bernstein-Vazirani und anderen Orakelproblemen - ist die Situation anders: Das Orakel beschreibt eine Funktion, die die Grundlage des Problems bildet. Die Tatsache, dass es sich um ein Orakel handelt, ist eine Möglichkeit zu strukturieren, wie wir die Funktion beschreiben, die im Zentrum des Problems steht: Nicht, dass wir niemals darüber nachdenken dürfen, wie die Funktion berechnet wird, sondern dass diese Informationen einfach nicht als Teil bereitgestellt werden des Problems, und dass wir uns nicht mit der Zeit oder anderen Komplexität befassen, die mit dieser Funktion verbunden sind.

Wenn wir diesen Ansatz wählen, können wir tatsächlich Antworten erhalten, die sich auf sehr schwierige Fragen bei der Berechnung beziehen. Zum Beispiel wissen Sie vielleicht, dass wir weder P  ≠  NP noch P  =  NP beweisen können , aber dass wir zeigen können , dass es Orakel A gibt, so dass wir zeigen können, dass P ^A  ≠  NP ^{A ist} . Was das Orakel A hier tut, ist nicht, einem Computer (genauer gesagt einer deterministischen Turing-Maschine oder einer nichtdeterministischen Turing-Maschine) zu helfen, ein Problem zu lösen - es stellt das Problem dar, das der Computer lösen muss. Die Tatsache , dass wir in einigen Fällen nachweisen können , dass P ^A ≠  NP ^A bedeutet nicht, dass P sich wirklich von NP unterscheidet : Es bedeutet nur, dass die Verwendung von Nichtdeterminismus eine wichtige Ressource für ein Rechenmodell ist - es ermöglicht Ihnen, einige Probleme effizient zu lösen, und es gibt keine Möglichkeit generisch, um Nichtdeterminismus auf einem deterministischen Computer effizient zu simulieren. Wenn Sie also das Problem im Zusammenhang mit der Berechnung von A lösen möchten, benötigen Sie unbedingt einige Informationen über die Struktur einer Funktion, die A effizient berechnen kann .

Dies ist eines der wichtigsten Dinge, um die es bei Orakeln geht: Sie ermöglichen es Ihnen, darüber zu sprechen, wie Rechenmodelle Probleme lösen können oder nicht , wenn Sie nur begrenzte Informationen über das Problem erhalten.

Verwenden von Orakelalgorithmen zur Lösung von Nicht-Orakel-Problemen

Der Deutsch-Josza-Algorithmus oder der Bernstein-Vazirani-Algorithmus sind im Prinzip keine Algorithmen, die man für sich selbst ausführt. (Nun, nicht wirklich - siehe nächster Abschnitt.) Sie stehen für Möglichkeiten, wie Sie ein Problem lösen können . Welche Probleme lösen sie? Mit ihnen können Sie bestimmte Merkmale einer Funktion entdecken, an der Sie interessiert sind - ob sie konstant / ausgeglichen ist oder welcher Vektor in einer linearen Funktion mit Skalarwert für Vektoren zugeordnet ist.

Auf welchen Funktionen führen Sie sie aus? - Sie führen sie für jede Funktion aus, für die Sie an der Antwort interessiert sind.

Die Beschreibung dieser als orakelbasierte Algorithmen ist nebensächlich. Die Orakelprobleme ermöglichen es Ihnen grundsätzlich zu wissen, dass Sie mit einem idealen Quantencomputer das Problem lösen können, selbst wenn Sie nur sehr wenig über die Funktion wissen , vorausgesetzt, Sie können die Funktion in der Praxis tatsächlich effizient bewerten. Um eine solche Funktion tatsächlich bewerten zu können, benötigen Sie natürlich eine Beschreibung, wie dies zu tun ist, und Sie haben mehr Informationen als in der Orakeleinstellung. Das hindert Sie jedoch nicht daran, denselben Algorithmus zu verwenden.

Was passiert, wenn Sie mehr Informationen als in der Orakeleinstellung haben, ist, dass es plötzlich andere Möglichkeiten gibt , das Problem zu lösen. Insbesondere könnte es möglich werden, das Problem klassisch effizient zu lösen . (Dies ist die gleiche Beobachtung wie bei P ^A  ≠  NP ^A : Es beweist, dass es Probleme in NP gibt , für deren Lösung jeder effiziente deterministische Algorithmus zumindest tatsächliche Strukturinformationen erfordern würde - also, wenn Sie eine Beschreibung bereitstellen Es ist möglich, dass das Problem bei einer effizient berechenbaren Funktion und nicht bei einem „Orakel“ liegtP. ) Dies bedeutet, dass der Quantenalgorithmus möglicherweise nicht den gleichen Vorteil gegenüber klassischen Algorithmen bei der Lösung des von Ihnen gestellten Problems hat - und tatsächlich kann es sein, dass der klassische Ansatz besser ist (insbesondere bei den Geräten, die wir derzeit haben).

Nur weil Sie einen Quantenalgorithmus haben, um etwas zu lösen, heißt das nicht, dass dies unbedingt der beste Weg ist, etwas zu lösen. Dies gilt sicherlich für den Deutsch-Josza-Algorithmus: Selbst in der Orakeleinstellung ist die Verwendung von Zufälligkeit fast genauso gut, und es ist viel besser, da wir noch keine großen zuverlässigen Quantencomputer haben! Aber dann wieder...

Ein Orakel "implementieren"

Der Zweck der Implementierung des Deutsch-Josza-Algorithmus ist der gleiche wie die Implementierung von " Hallo Welt! " - nicht um ein dringendes ungelöstes Problem zu lösen, sondern um die Verwendung eines Tools zu üben, von dem Sie erwarten, dass es für andere Dinge nützlich ist.

Um das Codieren zu üben, sollten Sie sich absolut entspannt und wohl fühlen mit der Idee , ein Orakel zu implementieren, und mit der Idee, dass der Computer das Orakel bewertet . Im Prinzip ist dies der Punkt, an dem Sie arbeiten möchten. Selbst wenn Sie einen klassischen Emulator verwenden, bei dem der klassische Computer tatsächlich alle Zweige der Überlagerung auswertet und so explizit die Antwort auf ein Problem findet, um so zu tun, als wäre es ein Quantencomputer, der etwas umständlicher agiert sei es - Sie üben, wie man ein Werkzeug verwendet, das für andere Dinge nützlich sein kann und das eines Tages nicht auf einem klassischen Computer ausgeführt wird.

Wie sollten Sie Ihr Orakel implementieren?

(i) Wenn Sie sich wirklich der Idee verschrieben haben, dass Sie gerade erst üben, müssen Sie nicht so tun, als würden Sie etwas Magisches tun. Überlegen Sie sich einfach eine Möglichkeit, die Orakelfunktion zu implementieren, auch wenn es für den zufälligen Beobachter offensichtlich ist, ob das Ergebnis konstant oder ausgeglichen ist. Sie versuchen nur, die Realisierung eines Algorithmus zu üben - machen Sie sich keine Sorgen, dass jemand Sie beschuldigt, ein Betrüger zu sein, dass Sie so tun, als würden Sie Krebs heilen, aber tatsächlich mit Lego spielen. Man kann nie wurde so zu tun , Krebs zu heilen, und Sie werden mit Lego durch bewusste Wahl zu spielen. Umfassen Sie das und tun Sie es einfach.

$f(x) = g(x,r)$$r$$g(x,r)$$x$$r$und wo es nicht offensichtlich ist, wie man es klassisch löst, ist nicht trivial.

• $g(x,r) = x \cdot r$$x,r \in \{0,1\}^n$$g(x,r)$$f(x)$$f(x)$$r \ne 0$

• Es ist denkbar, dass die obige Konstruktion etwas ausgearbeitet / verschleiert werden könnte, um eine Konstruktion zu erhalten, die garantiert entweder eine konstante Funktion oder eine ausgeglichene Funktion bewertet, und wo welche dieser beiden auftritt, ist nicht offensichtlich oder sogar schwierig - aber ich kann ' Ich denke im Moment nicht daran, wie.

Denken Sie daran, dass dies tatsächlich sehr schwierig ist - aber wenn Sie einen Weg finden, dies zu tun, könnte es sich sehr lohnen: Bravyi, Gossett und Koening haben so etwas für das Bernstein-Vazirani-Problem getan, und es hat ihnen erlaubt eine kleine, aber bedingungslose Trennung zwischen Quanten- und klassischer Komplexität zu zeigen, was eines der interessantesten Ereignisse in der Quantenkomplexität in den letzten Jahren war.

TL; DR

• Schwitzen Sie nicht über die Tatsache, dass Sie ein Orakel "bewerten".

• Wenn Sie über irgendetwas schwitzen, machen Sie sich nur Sorgen, dass eine tatsächliche Beschreibung der Funktion es möglich machen könnte, dasselbe Problem ohne einen Quantencomputer leicht zu lösen.

• Wenn Ihre Motivation nur darin besteht, sich mit Quantenprogrammierung zu üben, machen Sie sich darüber keine Sorgen. Speichern Sie Ihre Sorgen für würdigere Probleme wie die globale Erwärmung. In der Zwischenzeit genießen Sie es, mit Legos zu spielen, während Sie an etwas mehr bauen.