Ceci est une version archivée de cette page, en date du 26 janvier 2022 à 10:14 et modifiée en dernier par Kiwilak(discuter | contributions). Elle peut contenir des erreurs, des inexactitudes ou des contenus vandalisés non présents dans la version actuelle.
C'est une version restreinte de l'algorithme de Deutsch-Jozsa dans laquelle, au lieu de distinguer deux classes de fonctions, on essaie de retrouver une chaîne secrète encodée dans une fonction[2]. Il a été conçu pour prouver la distinction entre les classes de complexitéBQP et BPP[1].
Enoncé du problème
Soit un oracle qui implémente une fonction dans laquelle est un produit scalaire entre et une chaîne secrète modulo 2, . Quelle est la valeur de ?
Algorithme
En informatique "classique", la méthode la plus efficace pour retrouver la chaîne secrète consiste à évaluer la fonction fois avec comme valeurs d'entrée pour tout [2] :
Ensuite, appliquer l'oracle qui transforme . Cela peut être simulé au moyen de l'oracle standard qui transforme en appliquant l'oracle à ( représente une addition modulo 2).
Cela transforme la superposition en :
Une nouvelle transformée de Hadamard est appliquée à chaque qubit, de telle sorte que :
pour les qubits où , l'état est converti de à
pour les qubits où , l'état est converti de à
Pour obtenir , une mesure selon la base standard () est effectuée sur les qubits.
L'algorithme peut donc être représenté ainsi, où représente la transformée de Hadamard sur qubits :
La raison pour laquelle l'état final est est que, pour un donné :
Puisque est vraiment seulement quand , cela signifie que la seule amplitude non nulle correspond à .
↑ ab et cS D Fallek, C D Herold, B J McMahon, K M Maller, K R Brown, and J M Amini, « Transport implementation of the Bernstein–Vazirani algorithm with ion qubits », New Journal of Physics, vol. 18, (DOI10.1088/1367-2630/aab341)