Algorithme de Bernstein-Vazirani

L'algorithme de Bernstein–Vazirani, qui résout le problème de Bernstein–Vazirani est un algorithme quantique inventé par Ethan Bernstein et Umesh Vazirani en 1992[1].

Pour les articles homonymes, voir Bernstein.

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] :

Avec un calculateur quantique, une seule requête sera suffisante[2] :

Appliquer une transformée de Hadamard aux qubits pour obtenir :

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 à .

Références

(en) Cet article est partiellement ou en totalité issu de la page de Wikipédia en anglais intitulée « Bernstein–Vazirani algorithm » (voir la liste des auteurs).

  1. Ethan Bernstein and Umesh Vazirani, « Quantum Complexity Theory », SIAM Journal on Computing, vol. 26, no 5, , p. 1411–1473 (DOI 10.1137/S0097539796300921)
  2. S 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, (DOI 10.1088/1367-2630/aab341)
  • Portail de l'informatique théorique
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.