human
Algorithme de Grover URL_0 Je suis déconcerté par cet algorithme de recherche. Quelqu'un a une idée ? Explique comme si j'avais cinq ans.
gpt
J'ai l'impression que l'article de wikipedia est truffé de très petites erreurs : > L'algorithme nécessite un espace d'états H à N dimensions, qui peut être fourni par n = log2 N qubits. Je m'attendrais à ce qu'un espace d'états à N dimensions sur lequel vous pouvez prendre un super-état soit N qubits, pas log2 N. D'un autre côté, si la solution est de prendre un vecteur d'état aléatoire et de l'incrémenter en fonction de sa présence dans un groupe donné de solutions possibles, alors je le comprends. > Effectuez les "itérations de Grover" suivantes r(N ) fois . La fonction r(N ) , qui est asymptotiquement O(N½ ) , est décrite ci-dessous . Je m'attendrais à ce que la fonction r(N ) renvoie une valeur pour N qui est asymptotiquement N^1/2 . Je ne sais pas ce que la complexité algorithmique de la fonction calculant la fréquence d'exécution de l'opération a à voir avec cela ; J'espère que c'est négligeable pour tout N raisonnable. -------------------- Laissez-moi essayer une explication simple sur ce que j'en comprends. ( ça va être ELI20 - et - un - CS - diplômé , mais supportez - moi ) . Vous avez un groupe d'articles (disons 16777216 articles, un joli chiffre rond) et vous voulez en trouver un. Vous créez un vecteur d'état de 24 qubits qui sont tous également susceptibles d'être 1 ou 0 initialement. Ensuite , vous évaluez en parallèle la justesse de la moitié d' entre eux en supposant qu'un qubit donné est un 1 ou un 0 . Une moitié d'entre eux sera légèrement plus vraie que l'autre, donc vous augmentez la probabilité que ce qubit tombe à 1 (ou 0) à un peu plus. Après plusieurs itérations , la probabilité statistique que le vecteur de 24 qubits se réduise au résultat correct est asymptotiquement 1 . Je ne sais pas encore où me situer dans la logique sqrt(N ) . Cela a à voir avec l'augmentation de la probabilité et je peux voir qu'elle augmente avec la longueur du vecteur, mais je m'attendrais à ce qu'elle soit logarithmiquement basée sur cela, pas sur une racine carrée. Cela a-t-il un peu de sens ?