Comment permuter (remanier) une entrée de n bits?

Je m'intéresse à un algorithme quantique qui obtient en entrée une séquence de n bits et qui produit en sortie une version remaniée (permutée) de cette séquence de n bits.

Par exemple, si l'entrée est 0,0,1,1 (donc n = 4 dans ce cas), les réponses possibles sont:

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

Notez qu'une seule sortie doit être générée qui est choisie au hasard parmi toutes les sorties valides possibles.

Comment cela peut-il être mis en œuvre au mieux dans un algorithme quantique ?

Une solution pour cela est déjà proposée dans le cadre d'une des réponses pour Comment créer un algorithme quantique qui produit 2 séquences de n bits avec un nombre égal de 1 bits? . Mais le problème avec cette solution est que cela nécessite environ qubits d'aide qui deviennent rapidement énormes si n est grand.$\binom{n}2$

Remarque:

• Veuillez ne pas fournir d'algorithme classique sans expliquer comment les étapes de l'algorithme classique peuvent être mappées sur un ordinateur quantique universel.
• pour moi, il existe 2 bonnes façons d'interpréter "choisi au hasard parmi toutes les bonnes sorties possibles" : (1) chaque bonne sortie possible a une chance égale d'être choisie. (2) chaque bonne sortie possible a une chance> 0 d'être choisie.

Cela pourrait être fait avec qubits supplémentaires le long de ces lignes:$\lceil\log n\rceil$

1. Transformez les qubits supplémentaires pour qu'ils encodent un nombre choisi uniformément au hasard.$k\in\{0,\ldots,n-1\}$

2. Décaler cycliquement les qubits d'entrée fois.$k$

3. Laissez le dernier des qubits d'entrée d'origine être fixé en sortie et récapitulez sur les restants d'entre eux.$n-1$

Il s'agit d'un algorithme classique, mais vous pouvez bien sûr l'exécuter sur un ordinateur quantique, comme Norbert l'a suggéré dans un commentaire. (L'aspect de la question catégorique sur l'algorithme quantique n'est toujours pas clair pour moi, donc si l'exécution d'un algorithme classique tel que celui que j'ai suggéré sur un ordinateur quantique n'est pas suffisant, il serait utile que la question soit être clarifié.)

Notez que parce que la question demande une sortie aléatoire, l'algorithme va devoir générer l'entropie à un moment donné, probablement par le biais de mesures ou d'effectuer d'autres opérations non unitaires sur des qubits (comme les initialiser). Dans l'algorithme ci-dessus, c'est la première étape qui génère l'entropie: quel que soit l'état des qubits supplémentaires avant l'opération de l'étape 1, ils doivent avoir l'état une fois l'étape 1 effectuée (avec

$\frac{1}{\sqrt{3}} ( |001\rangle + |010\rangle + |100\rangle)$$001$$010$$100$

$|001\rangle$$\left| {3 \atop 1} \right\rangle = \frac{1}{\sqrt{3}} (|001\rangle + |010\rangle + |100\rangle)$$|010\rangle$$|100\rangle$

Une astuce pour produire une permutation quantique d'une entrée triée consiste à préparer d'abord un "état de permutation" en appliquant un réseau de tri à une liste de valeurs de départ chacune dans une superposition uniforme. Le réseau de tri produira des qubits contenant les graines triées, mais également des qubits contenant les comparaisons du réseau de tri. L'état de permutation n'est que les qubits de comparaison. Pour l'appliquer à votre entrée, vous exécutez simplement l'entrée via le réseau de tri en sens inverse. Notez qu'il y a quelques détails délicats ici; voir l'article " Techniques améliorées pour la préparation des états propres des hamiltoniens fermioniques ". Il faudrait généraliser cette technique pour travailler sur des entrées avec des valeurs répétées, au lieu de seulement des valeurs uniques.

$\left| {n \atop k} \right\rangle$$n$$k$ bits de jeu) que vous voulez produire. La principale différence est que vous exécuteriez le circuit de compression quantique en sens inverse, et il attend un nombre codant "combien y en a-t-il?" au lieu de "donnez-moi un état avec le nombre correct de ceux".

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

Un ordinateur quantique peut effectuer des calculs classiques. L'algorithme optimal serait de:

1. Choisissez n'importe quel bit (le plus rapide auquel vous pouvez accéder).
2. Trouvez un bit qui a la valeur opposée (si à l'étape 1 vous avez obtenu un 0, trouvez un 1)
3. Changez-les (0 devient 1 et 1 devient 0).

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