BQP

BQP

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 computación cuántica cuya cota superior en tiempo es polinómica para resolver ese problema, tal que la probabilidad de obtener una respuesta equivocada es menor de 25%.

El nivel de error de 1/4 es arbitrario, cualquier valor real k tal que 0 < k < 1/2 podría ser utilizado sin cambiar el conjunto BQP. La idea es que si la probabilidad de error es pequeña, la ejecución del algoritmo un número suficiente de veces lleva a una probabilidad exponencialmente pequeña de que la mayoría de las ejecuciones sean erróneas.

El número de qubits en el computador depende del tamaño del problema. Por ejemplo, ya se conocen algoritmos para factorizar un entero de n bits utilizando solo 2n qubits.

La computación cuántica ha despertado interés debido a que problemas que se supone no pertenecen a P pertenecen a la clase BQP. Actualmente solo se han clasificado tres de esos problemas:

La clase QBP se define basándose en un computador cuántico. La clase correspondiente para una máquina de Turing se llama BPP.

BQP contiene a P y a BPP y está contenida en PP y en PSPACE.

Obtenido de "BQP"

Wikimedia foundation. 2010.

Игры ⚽ Поможем написать курсовую

Mira otros diccionarios:

  • 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 — 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 …   Wikipédia en Français

  • 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

Compartir el artículo y extractos

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