випадку системи з L кубітів, у неї 2L класичних станів (00000 ... (L-нулів), ... 00 001 (L-цифр), ..., 11111 ... (L-одиниць)), кожне з яких може бути виміряна з імовірностями 0-100%.
Таким чином, одна операція над групою кубітів зачіпає всі значення, які вона може приймати, на відміну від класичного біта. Це і забезпечує безпрецедентний паралелізм обчислень.
Обчислення
Спрощена схема обчислення на квантовому комп'ютері виглядає так: береться система кубітів, на якій записується початковий стан. Потім стан системи або її підсистем змінюється допомогою унітарних перетворень, виконують ті чи інші логічні операції. Наприкінці вимірюється значення, і це результат роботи комп'ютера. Роль проводів класичного комп'ютера грають кубіти, а роль логічних блоків класичного комп'ютера грають унітарні перетворення. Така концепція квантового процесора і квантових логічних вентилів була запропонована в 1989 році Девідом Дойчем. Також Девід Дойч в 1995 році знайшов універсальний логічний блок, за допомогою якого можна виконувати будь квантові обчислення.
Виявляється, що для побудови будь-якого обчислення достатньо двох базових операцій. Квантова система дає результат, тільки з деякою ймовірністю є правильним. Але за рахунок невеликого збільшення операцій в алгоритмі можна як завгодно наблизити ймовірність отримання правильного результату до одиниці.
За допомогою базових квантових операцій можна симулювати роботу звичайних логічних елементів, з яких зроблені звичайні комп'ютери. Тому будь-яку задачу, яка вирішена зараз, квантовий комп'ютер вирішить, і майже за такий же час. Отже, нова схема обчислень буде не слабкіше нинішньої.
Чим же квантовий комп'ютер краще класичного? Велика частина сучасних ЕОМ працюють за такою ж схемою: n біт пам'яті зберігають стан, і кожний такт часу змінюються процесором. У квантовому випадку система з n кубітів знаходиться в стані, що є суперпозицією всіх базових станів, тому зміна системи стосується всіх 2n базових станів одночасно. Теоретично нова схема може працювати набагато (в експоненціальне число раз) швидше класичною. Практично (квантовий) алгоритм Гровера пошуку в базі даних показує квадратичний приріст потужності проти класичних алгоритмів.
Алгоритми
Алгоритм Гровера lt;http://ru.wikipedia/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%93%D1%80%D0%BE%D0%B2%D0%B5%D1%80%D0%B0gt; дозволяє знайти рішення рівняння за час.
Алгоритм Шора lt;http://ru.wikipedia/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%A8%D0%BE%D1%80%D0%B0gt; дозволяє розкласти натуральне число n на прості множники за полиномиальное lt;http://ru.wikipedia/wiki/%D0%9F%D0%BE%D0%BB%D0%B8%D0%BD%D0%BE%D0%BC%D0%B8%D0%B0%D0%BB%D1%8C%D0%BD%D1%8B%D0%B9_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BCgt; від log (n) час.
-алгоритми Залки Візнера lt;http://ru.wikipedia/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%97%D0%B0%D0%BB%D0%BA%D0%B8_%E2%80%94_%D0%92%D0%B8%D0%B7%D0%BD%D0%B5%D1%80%D0%B0gt; дозволяє моделювати унітарну еволюцію квантової системи частинок за майже лінійний час з використанням кубіт.
-алгоритми Дойча Йожі lt;http://ru.wikipedia/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%94%D0%BE%D0%B9%D1%87%D0%B0_%E2%80%94_%D0%99%D0%BE%D0%B6%D0%B8gt; дозволяє «за одне обчислення» визначити, чи є функція двійковій змінної f (n) постійної (f1 (n)=0, f2 (n)=1 незалежно отn) або «збалансованої» (f3 (0)=0, f3 (1 )=1; f4 (0)=1, f4 (1)=0).
Алгоритм Саймона lt;http://ru.wikipedia/w/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%A1%D0%B0%D0%B9%D0%BC%D0%BE%D0%BD%D0%B0amp;action=editamp;redlink=1gt; вирішує проблему чорного ящика lt;http://ru.wikipedia/wiki/%D0%A7%D1%91%D1%80%D0%BD%D1%8B%D0%B9_%D1%8F%D1%89%D0%B8%D0%BAgt; експоненціально швидше, ніж будь-який класичний алгоритм, включаючи імовірнісні алгоритми.
Було показано, що не для всякого алгоритму можливо «квантове прискорення». Більш того, можливість отримання квантового прискорення для довільного класичного алгоритму є великою рідкістю.
Квантова телепортація
Алгоритм телепортації реалізує точний перенос стану одного кубіта (або системи) на інший. У найпростішій схемі використовуються 3 кубіта: телепортіруемий кубіт і заплутана пара, один кубіт якої знаходиться на іншій стороні. Відзначимо, що в результаті роботи алгоритму первісний стан джерела зруйнується - це приклад дії загального принципу неможливості клонування lt;http://ru.wikipedia/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%BE_%D0%B7%D0%B0%D0%BF%D1%80%D0%B5%D1%82%D0%B5_%D0%BA%D0%BB%D0%BE%D0%BD%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D1%8Fgt;- Неможливо створити точну копію квантового стану, не зруйнувавши оригінал. Не вийде скопіюват...
