Séance de cours

Algorithme de recherche d'ordre

Graph Chat

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

Description

Cette séance de cours couvre l'algorithme de recherche d'ordre, qui vise à trouver la période d'une fonction modulo N. L'algorithme implique la prise d'un entier x et la recherche du plus petit r tel que x^r 1 (mod N). Il explore l'application de l'estimation de la phase quantique (EPQ) à l'opérateur unitaire U, en se concentrant sur la recherche efficace de la période. La séance de cours s'inscrit dans le processus d'application des portes C-U et de codage efficace. Différents exemples et preuves sont fournis pour illustrer le fonctionnement et l'efficacité de l'algorithme.

Source officielle

Proximité ontologique

Informatique théorique

Theory of computation: Informatique quantique

Concepts associés (32)

Algorithme de Shor

En arithmétique modulaire et en informatique quantique, l’algorithme de Shor est un algorithme quantique conçu par Peter Shor en 1994, qui factorise un entier naturel N en temps O et en espace . Beaucoup de cryptosystèmes à clé publique, tels que le RSA, deviendraient vulnérables si l'algorithme de Shor était un jour implanté dans un calculateur quantique pratique. Un message chiffré avec RSA peut être déchiffré par factorisation de sa clé publique N, qui est le produit de deux nombres premiers.

Porte quantique

En informatique quantique, et plus précisément dans le modèle de de calcul, une porte quantique (ou porte logique quantique) est un circuit quantique élémentaire opérant sur un petit nombre de qubits. Les portes quantiques sont les briques de base des circuits quantiques, comme le sont les portes logiques classiques pour des circuits numériques classiques. Contrairement à de nombreuses portes logiques classiques, les portes logiques quantique sont « réversibles ».

Informatique quantique

L'informatique quantique est le sous-domaine de l'informatique qui traite des calculateurs quantiques et des associés. La notion s'oppose à celle d'informatique dite « classique » n'utilisant que des phénomènes de physique classique, notamment de l'électricité (exemple du transistor) ou de mécanique classique (exemple historique de la machine analytique). En effet, l'informatique quantique utilise également des phénomènes de la mécanique quantique, à savoir l'intrication quantique et la superposition.

Algorithme d'estimation de phase quantique

En informatique quantique, l’algorithme d'estimation de phase quantique est un permettant d'estimer la valeur propre (ou sa phase, ce qui, dans ce cas précis, est équivalent) d'un opérateur unité associée à un vecteur propre donné. Les valeurs propres d'un opérateur unitaire U, agissant sur m bits, sont de module 1. Si est un vecteur propre de U, nous avons donc . Le but de cet algorithme est de trouver la valeur de la phase correspondant à un vecteur propre donné, ceci avec une précision de n bits (la phase n'a pas nécessairement une valeur exacte).

Opérateur unitaire

En analyse fonctionnelle, un opérateur unitaire est un opérateur linéaire U d'un espace de Hilbert tel queUU = UU = Ioù U* est l'adjoint de U, et I l'opérateur identité. Cette propriété est équivalente à : U est une application d' dense et U préserve le produit scalaire ⟨ , ⟩. Autrement dit, pour tous vecteurs x et y de l'espace de Hilbert, ⟨Ux, Uy⟩ = ⟨x, y⟩ (ce qui entraîne que U est linéaire). D'après l'identité de polarisation, on peut remplacer « U préserve le produit scalaire » par « U préserve la norme » donc par « U est une isométrie qui fixe 0 ».

Afficher plus

Séances de cours associées (64)

Estimation de la phase quantique

Explique l'algorithme de l'estimation de la phase quantique (QPE) et sa complexité à l'aide de deux registres et de portes SWAP.

Estimation de la phase quantique : Fondements et applications

Explore les fondamentaux, les défis et les applications de l'estimation de phase quantique dans le calcul quantique.

Informatique Quantique: Fondamentaux et Applications

Couvre les principes fondamentaux de l'informatique quantique, y compris la réalisation de qubits, les ordinateurs quantiques évolutifs, la communication quantique et les algorithmes quantiques.

Quantum et nanocomputing

Couvre les bases de la théorie des nombres, du cryptage RSA et de l'algorithme de recherche de période de Shor.

Quantum et nanocomputing

Déplacez-vous dans les fondamentaux du calcul quantique, y compris l'enchevêtrement, les portes quantiques et les algorithmes, en mettant l'accent sur les transformations unitaires et la cohérence quantique.

Afficher plus

Concepts associés (32)

Algorithme de Shor

Porte quantique

Informatique quantique

Algorithme d'estimation de phase quantique

Opérateur unitaire

Afficher plus