پیشنویس:رده پیچیدگی زمان چند جملهای کوانتومی با خطای محدود
ظاهر
![Diagram of randomised complexity classes](http://upload.wikimedia.org/wikipedia/commons/thumb/9/9e/Randomised_Complexity_Classes_2.svg/220px-Randomised_Complexity_Classes_2.svg.png)
در نظریه پیچیدگی رایانشی یا نظریه پیچیدگی محاسباتی، رده زمان چند جملهای کوانتومی با خطای محدود (bounded-error quantum polynomial time) یا به اختصار انگلیسی BQP، رده پیچیدگی از مسائل تصمیم است که توسط رایانه کوانتومی در زمان چند جملهای، با خطای حداکثر ۱/۳ برای تمام نمونهها شدنی است. این رده، نمونه کوانتومی رده پیچیدگی BPP است.
یک مسئله تصمیم را عضوی از رده زچک (BQP) میدانیم، اگر یک الگوریتم کوانتومی (الگوریتمی که توسط یک رایانه کوانتومی اجرا شود) وجود داشته باشد که درباره آن مسئله با احتمال زیاد تصمیم بگیرد و حتماً در زمان چند جملهای اجرا شود. این الگوریتم، قطعاً در زمان چند جملهای با احتمال ۲/۳ صحیح خواهد بود.
الگوریتم BQP (1 اجرا) | ||
---|---|---|
≥ 2/3 | ≤ 1/3 | |
≤ 1/3 | ≥ 2/3 | |
الگوریتم BQP ( k اجرا) | ||
> 1 − 2 − ck | < 2 - ck | |
< 2 - ck | > 1 − 2 − ck | |
برای مقداری ثابت c > 0 |