Récemment, j'ai lu à propos de «bogosort quantique» sur certains wiki. L'idée de base est que, comme bogosort, nous mélangeons simplement notre tableau et espérons qu'il sera trié «par accident» et réessayé en cas d'échec.

La différence est que maintenant, nous avons un « quantum magique », nous pouvons donc simplement essayer toutes les permutations à la fois dans des «univers parallèles» et «détruire tous les mauvais univers» où le tri est mauvais.

Maintenant, évidemment, cela ne fonctionne pas. Le quantum est la physique, pas la magie. Les principaux problèmes sont

1. Les «univers parallèles» ne sont qu'une interprétation des effets quantiques, pas quelque chose que l'informatique quantique exploite. Je veux dire, nous pourrions utiliser des chiffres durs ici, l'interprétation ne fera qu'embrouiller les choses ici, je pense.

2. «Détruire tous les mauvais univers» est un peu comme la correction d'erreur qubit, un problème très difficile en informatique quantique.

3. Le genre Bogo reste stupide. Si nous pouvons accélérer le tri via le quantum, pourquoi ne pas le baser sur un bon algorithme de tri ? (Mais nous avons besoin de hasard, mon voisin proteste! Oui, mais ne pouvez-vous pas penser à un meilleur algorithme classique qui repose sur le hasard ?)

Bien que cet algorithme soit principalement une blague, il pourrait s'agir d'une `` blague éducative '', comme le bogosort `` classique '', car la différence entre le meilleur des cas, le pire des cas et la complexité moyenne des cas pour les algorithmes randomisés est facile et très claire ici. (pour mémoire, le meilleur cas est , nous sommes très chanceux mais nous devons toujours vérifier que notre réponse est correcte en scannant le tableau, le temps prévu est tout simplement horrible (IIRC, proportionnel au nombre de permutations, donc ) et le pire des cas, c'est qu'on ne termine jamais)$\Theta(n)$$O(n!)$

Alors, que pouvons-nous apprendre du «bogosort quantique»? En particulier, existe-t-il de vrais algorithmes quantiques similaires ou s'agit-il d'une impossibilité théorique ou pratique? De plus, y a-t-il eu des recherches sur les «algorithmes de tri quantique»? Sinon, pourquoi?

AVERTISSEMENT: le bogosort quantique est un algorithme de plaisanterie

Permettez-moi de dire brièvement l'algorithme:

• Étape 1: En utilisant un algorithme de randomisation quantique, randomisez la liste / tableau, de sorte qu'il n'y ait aucun moyen de savoir dans quel ordre est la liste jusqu'à ce qu'elle soit observée. Cela divisera l'univers en univers ; cependant, la division n'a aucun coût, car elle se produit constamment de toute façon.$O(N!)$

• Étape 2: Vérifiez si la liste est triée. Sinon, détruisez l'univers (en négligeant la possibilité physique réelle).

Maintenant, tous les univers restants contiennent des listes / tableaux qui sont triés.

Pire complexité du cas :$O(N)$

(nous ne considérons que les univers qui peuvent observer que la liste est triée)

Complexité moyenne / meilleure :$O(1)$

L'un des problèmes majeurs de cet algorithme est l'énorme possibilité d'agrandissement des erreurs comme Nick Johnson le mentionne ici :

Cet algorithme a cependant un problème beaucoup plus important. Supposons qu'une fois sur 10 milliards de fois, vous conclurez par erreur qu'une liste est triée lorsqu'elle ne l'est pas. Il y en a 20! façons de trier une liste de 20 éléments. Après le tri, les univers restants seront celui dans lequel la liste a été triée correctement et les 2,4 millions d'univers dans lesquels l'algorithme a conclu à tort que la liste a été triée correctement. Donc, ce que vous avez ici est un algorithme pour grossir massivement le taux d'erreur d'une pièce de machine.

Les «univers parallèles» sont une interprétation très simplifiée des effets quantiques , pas quelque chose que l'informatique quantique exploite.

Je ne sais pas vraiment ce que vous entendez par «interprétation très simplifiée des effets quantiques». Les sources ( ceci et cela ) que j'ai trouvées sur Internet concernant le bogosort quantique ne mentionnent pas explicitement qu'elles utilisent l'interprétation alternative de QM, c'est-à-dire l' interprétation d'Everett à laquelle vous pourriez penser. En fait, je ne sais même pas comment coller ensemble l'interprétation d'Everett et le bogosort quantique (en utilisant la post-sélection, comme certaines personnes l'ont commenté). Quoi qu'il en soit, juste une note: dans la cosmologie traditionnelle, il est largement admis qu'il existe plus d'un univers et il existe même des classifications pour eux, appelés les quatre niveaux de Max Tegmark et Brian Greene 'Théories cycliques . Lisez l'article Wiki sur Multivers pour plus de détails.

'Détruire tous les mauvais univers' est un peu comme la correction d'erreur qubit, un problème très difficile dans l'informatique quantique.

Bien sûr, c'est en fait beaucoup plus difficile, et nous ne nous attendons pas à détruire les univers littéralement. Le bogosort quantique n'est qu'un concept théorique, sans applications pratiques (que je connaisse).

Le genre Bogo reste stupide. Si nous pouvons accélérer le tri via le quantum, pourquoi ne pas le baser sur un bon algorithme de tri? (Mais nous avons besoin de hasard, mon voisin proteste! Oui, mais ne pouvez-vous pas penser à un meilleur algorithme classique qui repose sur le hasard?)

Oui, cela reste stupide . Cela semble avoir commencé comme une "blague éducative" comme vous l'avez dit. J'ai essayé de trouver l'origine de ce type, ou des articles universitaires pertinents, mais je n'en ai pas trouvé. Cependant, même le bogosort classique est stupide dans le sens où il est largement considéré comme l'un des algorithmes de tri les plus inefficaces. Pourtant, il a été étudié, purement par intérêt éducatif.

En particulier, existe-t-il de vrais algorithmes quantiques similaires ou s'agit-il d'une impossibilité théorique ou pratique?

Pas que je sache. De tels algorithmes sont en effet des possibilités théoriques, mais certainement pas pratiques (du moins pas encore).

De plus, y a-t-il eu des recherches sur les «algorithmes de tri quantique»? Sinon, pourquoi?

Il y a en effet eu des recherches sur le "tri quantique". Mais le problème avec de tels algorithmes de tri est que tout algorithme de tri quantique basé sur la comparaison prendrait au moins des étapes , ce qui est déjà réalisable par les algorithmes classiques. Ainsi, pour cette tâche, les ordinateurs quantiques ne sont pas meilleurs que les ordinateurs classiques. Cependant, dans les tris délimités par l'espace, les algorithmes quantiques surpassent leurs homologues classiques. Ceci et ceci sont deux articles pertinents.$\Omega (N\log N)$