BQP

BQP
Les relations supposées entre BQP et les autres classes de complexité[1].

En théorie de la complexité des algorithmes BQP (Bounded error Quantum Polynomial time) est la classe des problème de décision qui peuvent être résolus par un calculateur quantique en un temps polynômial, avec une probabilité d'erreur d'au plus 1/3 dans tous les cas. Elle est le pendant quantique de la classe classique de complexité BPP.

De même que pour les autres classes de complexité probabilistes, dites en "bounded error", le choix de la probabilité 1/3 d'erreur est arbitraire. On peut exécuter l'algorithme un nombre constant de fois, et prendre la majorité des votes pour obtenir n'importe quelle probabilité de réussite désirée, en utilisant les inégalités de Chernoff. Une analyse détaillée montre que la classe de complexité reste inchangée en autorisant un risque d'erreur inférieur à 1/2 − nc d'une part, et supérieur à 2nc d'autre part, c étant une constante positive quelconque et n la longueur des données en entrée de l'algorithme.

Calcul quantique

La classe de complexité BQP est l'objet d'études intensives car certains problèmes présentant un intérêt pratique sont démontrés dans BQP, mais sont supposés en dehors de P (classe des problèmes qui peuvent être résolus par l'informatique classique en un temps polynômial).

Parmi les exemples les plus significatifs :


Références

  1. Michael Nielsen and Isaac Chuang (2000). Quantum Computation and Quantum Information. Cambridge: Cambridge University Press. ISBN 0-521-63503-9.
  2. a et b arXiv:quant-ph/9508027v2 Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, Peter W. Shor

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article BQP de Wikipédia en français (auteurs)

Игры ⚽ Поможем написать реферат

Regardez d'autres dictionnaires:

  • BQP — Saltar a navegación, búsqueda En Teoría de la complejidad computacional, BQP representa la clase de algoritmos que pueden ser resueltos en un computador cuántico en tiempo polinómico con un margen de error promedio inferior a 1/4. Dicho de otra… …   Wikipedia Español

  • BQP — In computational complexity theory BQP stands for Bounded error, Quantum, Polynomial time . It denotes the class of decision problems solvable by a quantum computer in polynomial time, with an error probability of at most 1/3 for all instances.… …   Wikipedia

  • BQP — Die Komplexitätsklasse BQP (bounded error quantum polynomial time) ist ein Begriff aus der Komplexitätstheorie, einem Teilgebiet der Theoretischen Informatik. Zu BQP gehören alle Probleme, die auf einem Quantencomputer in Polynomialzeit mit einer …   Deutsch Wikipedia

  • BQP — En Teoría de la complejidad computacional, BQP representa la clase de algoritmos que pueden ser resueltos en un computador cuántico en tiempo polinómico con un margen de error promedio inferior a 1/4. Dicho de otra forma, existe un algoritmo de… …   Enciclopedia Universal

  • BQP (Komplexitätsklasse) — Die Komplexitätsklasse BQP (bounded error quantum polynomial time) ist ein Begriff aus der Komplexitätstheorie, einem Teilgebiet der Theoretischen Informatik. Zu BQP gehören alle Probleme, die auf einem Quantencomputer in Polynomialzeit mit einer …   Deutsch Wikipedia

  • bqp — ISO 639 3 Code of Language ISO 639 2/B Code : ISO 639 2/T Code : ISO 639 1 Code : Scope : Individual Language Type : Living Language Name : Busa …   Names of Languages ISO 639-3

  • BQP — abbr. Bounded probability Quantum Polynomial (complexity theory, quantum computing) …   Dictionary of abbreviations

  • Класс BQP — Примерное положение BQP на карте классов NP, P, PSPACE. В теории алгоритмов классом сложности BQP (от англ.& …   Википедия

  • Quantenprozessor — Ein Quantencomputer bzw. Quantenrechner ist ein Computer, dessen Funktion auf den besonderen Gesetzen der Quantenmechanik beruht. Im Unterschied zum Digitalrechner arbeitet er auf der Basis quantenmechanischer Zustände, und die Verarbeitung… …   Deutsch Wikipedia

  • Quantenrechner — Ein Quantencomputer bzw. Quantenrechner ist ein Computer, dessen Funktion auf den besonderen Gesetzen der Quantenmechanik beruht. Im Unterschied zum Digitalrechner arbeitet er auf der Basis quantenmechanischer Zustände, und die Verarbeitung… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”