Třída BQP

V teorii algoritmů je třída složitosti BQP (z anglického  bounded error quantum polynomial time ) třída problémů řešitelnosti , které lze vyřešit kvantovým počítačem v polynomiálním čase (doba pro práci na úloze závisí polynomiálně na velikosti vstupní data), přičemž je zajištěna pravděpodobnost získání správné odpovědi alespoň 2/3 pro jakýkoli vstup. Je to kvantová obdoba třídy BPP .

Jinými slovy, problém patří do třídy BQP, pokud existuje kvantový algoritmus (algoritmus pro kvantový počítač), který tento problém řeší s vysokou pravděpodobností a je zaručeno, že poběží za dobu ne delší než polynomiální. Při libovolném běhu algoritmu by pravděpodobnost získání nesprávné odpovědi neměla být větší než 1/3.

Významní představitelé

Zájem o kvantové výpočty a počítače je způsoben některými problémy, které jsou ve třídě BQP, ale jejichž příslušnost do třídy P není známa:

• Faktorizace čísel  - Shorův algoritmus [1]
• Diskrétní logaritmus [1]
• Simulace kvantových systémů s více částicemi ( Feynmanův problém , někdy také univerzální kvantový simulátor)

Vztahy s jinými třídami

Poznámky

1. ↑ 1 2 arXiv: quant-ph/9508027v2 Polynomiální-časové algoritmy pro prvofaktorizaci a diskrétní logaritmy na kvantovém počítači , Peter W. Shor . Získáno 4. listopadu 2010. Archivováno z originálu 4. prosince 2014. (neurčitý)

Literatura

• "Algoritmy pro kvantové výpočty: diskrétní logaritmy a faktoring" PW Shor, AT&T Bell Labs. doi:10.1109/SFCS.1994.365700

Odkazy

• A. Kh. Shen, M. N. Vyaly, Kurz přednášek "Klasické a kvantové výpočty". Přednáška 8: Definice kvantového počítání. Příklady // Intuit.ru, 03/15/2007