Примірне положення BQP на карті класів NP, P, PSPACE.

В теорії алгоритмів класом складності BQP (від англ. bounded error quantum polynomial time ) Називається клас проблем розв'язності, які можуть бути вирішені квантовим комп'ютером за поліноміальний час (час роботи над завданням поліноміальних залежить від розміру вхідних даних), забезпечивши при цьому ймовірність отримання вірної відповіді як мінімум 2/3 для будь-якого входу. Є квантовим аналогом класу BPP.

Іншими словами, задача відноситься до класу BQP, якщо існує квантовий алгоритм (алгоритм для квантового комп'ютера), вирішальний дану проблему з високою ймовірністю і працюючий гарантовано не більш ніж за поліноміальний час. Для довільного запуску алгоритму ймовірність отримання невірної відповіді повинна бути не більше 1/3.


1. Важливі представники

Інтерес до квантових обчислень і комп'ютерам викликаний деякими завданнями, які знаходяться в класі BQP, але приналежність яких до класу P невідома:


2. Взаємовідносини з іншими класами

\ Mbox {P} \ subseteq \ mbox {BPP} \ subseteq \ mbox {BQP} \ subseteq \ mbox {AWPP} \ subseteq \ mbox {PP} \ subseteq \ mbox {PSPACE}

Примітки

Література

  • "Algorithms for quantum computation: discrete logarithms and factoring" PW Shor, AT & T Bell Labs. doi: 10.1109/SFCS.1994.365700