Wie wird eine n-Bit-Eingabe permutiert (neu gemischt)?

Ich interessiere mich für einen Quantenalgorithmus, der als Eingabe eine n-Bit-Sequenz erhält und als Ausgabe eine neu gemischte (permutierte) Version dieser n-Bit-Sequenz erzeugt.

Wenn die Eingabe z. B. 0,0,1,1 ist (in diesem Fall also n = 4), lauten die möglichen Antworten:

• 0,0,1,1
• 0,1,0,1
• 0,1,1,0
• 1,0,0,1
• 1,0,1,0
• 1,1,0,0

Beachten Sie, dass nur eine Ausgabe generiert werden sollte, die zufällig aus allen möglichen gültigen Ausgaben ausgewählt wird.

Wie kann dies am besten in einen Quantenalgorithmus implementiert werden ?

Eine Lösung hierfür wird bereits als Teil einer der Antworten für Wie erstelle ich einen Quantenalgorithmus, der 2 n-Bit-Sequenzen mit der gleichen Anzahl von 1-Bit erzeugt? . Das Problem bei dieser Lösung ist jedoch, dass dies ungefähr $\binom{n}2$ Hilfe-Qubits erfordert, die schnell riesig werden, wenn n groß ist.

Hinweis:

• Bitte geben Sie keinen klassischen Algorithmus an, ohne zu erklären, wie die Schritte des klassischen Algorithmus auf einen universellen Quantencomputer abgebildet werden können.
• Für mich gibt es zwei gute Möglichkeiten, "zufällig aus allen möglichen guten Ergebnissen ausgewählt" zu interpretieren : (1) Jedes mögliche gute Ergebnis hat die gleiche Chance, ausgewählt zu werden. (2) Jeder mögliche gute Output hat eine Chance> 0 gewählt zu werden.

könnte mit ⌈ log n ⌉ zusätzlichen Qubits in dieser Richtung geschehen :$\lceil\log n\rceil$

1. Transformiere die zusätzlichen Qubits so, dass sie eine Zahl codieren , die gleichmäßig zufällig gewählt wird.$k\in\{0,\ldots,n-1\}$

2. Verschieben Sie die Eingangs-Qubits zyklisch mal.$k$

3. Lassen Sie die letzte der ursprünglichen Eingangs Qubits als Ausgang und rekursiv auf dem verbleibenden fixiert werden von ihnen.$n-1$

Dies ist ein klassischer Algorithmus, aber Sie können ihn natürlich auf einem Quantencomputer ausführen, wie Norbert in einem Kommentar vorgeschlagen hat. (Der Aspekt der Frage, bei dem es darum geht, dass der Algorithmus ein Quantenalgorithmus ist, ist mir immer noch nicht klar. Wenn es also nicht ausreicht, einen klassischen Algorithmus wie den, den ich auf einem Quantencomputer vorgeschlagen habe, auszuführen, wäre dies für die Frage hilfreich geklärt werden.)

Beachten Sie, dass der Algorithmus, da in der Frage eine zufällige Ausgabe angefordert wird, irgendwann Entropie erzeugen muss, vermutlich durch Messungen oder andere nicht einheitliche Operationen an Qubits (wie z. B. deren Initialisierung). Im obigen Algorithmus ist es der erste Schritt, der die Entropie erzeugt: Unabhängig vom Zustand der zusätzlichen Qubits, bevor die Operation in Schritt 1 ausgeführt wird, sollten sie den Zustand nachdem Schritt 1 ausgeführt wurde (mitdas in binär codiert ist, sagen wir mal).

Hinweis: In dieser Antwort wird davon ausgegangen, dass die Permutation kohärent sein soll , dh, Sie möchten $\frac{1}{\sqrt{3}} ( |001\rangle + |010\rangle + |100\rangle)$$001$$010$$100$

$|001\rangle$. Wenn Sie aber auch den GHZ-Zustand für den Eingang|ausgeben wollen 010⟩und| 100⟩, das wird nicht funktionieren. Sie können nicht mehrere Eingangszustände an denselben Ausgangszustand senden (ohne Dekohärenz). Solange Sie sagen "Ich kümmere mich nur um sortierte aufsteigende Eingaben wie 0000111, aber nicht um 1110000 oder 0010110; Sie können damit machen, was Sie wollen", ist dies in Ordnung.$\left| {3 \atop 1} \right\rangle = \frac{1}{\sqrt{3}} (|001\rangle + |010\rangle + |100\rangle)$$|010\rangle$$|100\rangle$

Ein Trick zum Erzeugen einer Quantenpermutation einer sortierten Eingabe besteht darin, zuerst einen "Permutationszustand" durch Anwenden eines Sortiernetzwerks auf eine Liste von Startwerten in jeweils einheitlicher Überlagerung herzustellen. Das Sortiernetzwerk gibt Qubits aus, die die sortierten Startwerte enthalten, aber auch Qubits, die die Vergleiche des Sortiernetzwerks enthalten. Der Permutationszustand besteht nur aus den Vergleichs-Qubits. Um sie auf Ihre Eingabe anzuwenden, führen Sie die Eingabe einfach in umgekehrter Reihenfolge durch das Sortiernetzwerk. Beachten Sie, dass es hier einige knifflige Details gibt. siehe die Veröffentlichung " Verbesserte Techniken zur Herstellung von Eigenzuständen fermionischer Hamiltonianer ". Sie müssten diese Technik verallgemeinern, um Eingaben mit wiederholten Werten zu bearbeiten, anstatt nur eindeutige Werte.

$\left| {n \atop k} \right\rangle$$n$$k$

$|0001\rangle$$\frac{1}{\sqrt{4}}$$\left| {4 \atop 1} \right\rangle$$|0011\rangle$$\left| {4 \atop 2} \right\rangle$$\frac{1}{\sqrt{6}}$

Ein Quantencomputer kann klassische Berechnungen durchführen. Der optimale Algorithmus wäre:

1. Wählen Sie ein beliebiges Bit (das schnellste, auf das Sie zugreifen können).
2. Suchen Sie ein Bit mit dem entgegengesetzten Wert (wenn Sie in Schritt 1 eine 0 erhalten haben, suchen Sie eine 1).
3. Schalten Sie sie um (0 wird 1 und 1 wird 0).

$N$$\mathcal{O}(N)$$n^{\textrm{th}}$$\mathcal{O}\left(\sqrt{N}\right)$