Table des matières
13 relations: Algorithme de Shor, BPP (complexité), Classe de complexité, Décomposition en produit de facteurs premiers, Inégalité de Chernoff, Logarithme discret, Ordinateur quantique, P (complexité), Polynôme, Polynôme de Jones, Problème à promesse, Problème de décision, Théorie de la complexité (informatique théorique).
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((\log N)^3) et en espace O(\log N).
Voir BQP et Algorithme de Shor
BPP (complexité)
En informatique théorique, plus précisément en théorie de la complexité, la classe BPP (bounded-error probabilistic polynomial time) est la classe de problèmes de décision décidés par une machine de Turing probabiliste en temps polynomial, avec une probabilité d'erreur dans la réponse inférieure à 1/3.
Classe de complexité
En informatique théorique, et plus précisément en théorie de la complexité, une classe de complexité est un ensemble de problèmes algorithmiques dont la résolution nécessite la même quantité d'une certaine ressource.
Voir BQP et Classe de complexité
Décomposition en produit de facteurs premiers
Décomposition du nombre 864 en facteurs premiers En mathématiques et plus précisément en arithmétique, la décomposition en produit de facteurs premiers, aussi connue comme la factorisation entière en nombres premiers ou encore plus couramment la décomposition en facteurs premiers, consiste à chercher à écrire un entier naturel non nul sous forme d'un produit de nombres premiers.
Voir BQP et Décomposition en produit de facteurs premiers
Inégalité de Chernoff
En théorie des probabilités, l'inégalité de Chernoff permet de majorer la queue d'une loi de probabilité, c'est-à-dire qu'elle donne une valeur maximale de la probabilité qu'une variable aléatoire dépasse une valeur fixée.
Voir BQP et Inégalité de Chernoff
Logarithme discret
Le logarithme discret est un objet mathématique utilisé en cryptologie.
Voir BQP et Logarithme discret
Ordinateur quantique
qubits et la deuxième un qubit, les boîtes représentent des opérations, et le diagramme se lit de gauche à droite correspondant à la chronologie des opérationshttps://blogs.msdn.microsoft.com/visualstudio/2018/12/01/qubits-in-qsharp/. Un ordinateur quantique, calculateur quantique, processeur quantique ou système informatique quantique, utilise les propriétés quantiques de la matière, telles que la superposition et l'intrication, afin d'effectuer des opérations sur des données.
Voir BQP et Ordinateur quantique
P (complexité)
La classe P, aussi noté parfois PTIME ou DTIME(nO(1)), est une classe très importante de la théorie de la complexité, un domaine de l'informatique théorique et des mathématiques.
Polynôme
Courbe représentative d'une fonction cubique. En mathématiques, un polynôme est une expression formée uniquement de produits et de sommes de constantes et d'indéterminées (aussi appelées variables), habituellement notées X, Y, Z, etc.
Voir BQP et Polynôme
Polynôme de Jones
Le polynôme de Jones en théorie des nœuds est un invariant polynomial des nœuds (incomplet) introduit par Vaughan Jones en 1984.
Problème à promesse
Dans la théorie de la complexité computationnelle, un problème à promesse est une généralisation d'un problème de décision où l'entrée doit appartenir à un sous-ensemble donné de toutes les entrées possibles (la promesse ou précondition), et la sortie reste binaire.
Voir BQP et Problème à promesse
Problème de décision
En informatique théorique, un problème de décision est une question mathématique dont la réponse est soit « oui », soit « non ».
Voir BQP et Problème de décision
Théorie de la complexité (informatique théorique)
P est la classe des problèmes décidés en temps polynomial par une machine de Turing déterministe. La théorie de la complexité est le domaine des mathématiques, et plus précisément de l'informatique théorique, qui étudie formellement le temps de calcul, l'espace mémoire (et plus marginalement la taille d'un circuit, le nombre de processeurs, l'énergie consommée…) requis par un algorithme pour résoudre un problème algorithmique.
Voir BQP et Théorie de la complexité (informatique théorique)