Квантовий комп'ютер

Представлення кубіта за допомоги сфери Блоха.

У класичному комп'ютері для оперування інформацією використовуються елементарні двійкові розряди — біти. Фізична реалізація біта ґрунтується на тому принципі, що потенціал напруги може бути або вище певного рівня (це відповідатиме значенню біта 1) або нижче (0).

У квантовому комп'ютері інформація також, як правило, представляється за допомоги двійкових елементів. Як такі елементи використовуються фізичні системи з двома можливими станами, що описуються в квантовій механіці за допомогою двовимірного комплексного простору. Для опису подібної системи використовують позначення Дірака, де першому станові відповідає квантовомеханічний вектор стану ${\displaystyle |0\rangle }$, а другому — інший вектор ${\displaystyle |1\rangle }$. Роль подібної квантової системи із двома станами може грати зокрема спін електрона, який має дві можливі конфігурації — «спін вгору» і «спін вниз». В подібному ключі можуть бути використані енергетичні рівні атомів або молекул, або напрямок струму в кільцевому надпровіднику.

Такий елемент, що використовується для представлення інформації в квантовому комп'ютері, дістав окрему назву квантовий біт (англ. quantum bit, qubit), або скорочено кубіт, що підкреслює його квантовомеханічну природу. Важливою властивістю кубіта є можливість накладання декількох станів, або їх суперпозиція. Це означає, що кубіт необов'язково знаходиться саме у стані ${\displaystyle |0\rangle }$ або ${\displaystyle |1\rangle }$, як це має місце для бітів у класичному комп'ютері. Стан кубіта може бути представлений довільним вектором ${\displaystyle |\psi \rangle }$ у вищезазначеному двовимірному комплексному просторі[11]:

${\displaystyle |\psi \rangle =a|0\rangle +b|1\rangle }$

за тим самим принципом, як в оптиці описуються дві когерентні хвилі, що накладаються одна на одну. Таким чином, існує принципова різниця між кубітом та класичним ймовірнісним бітом (тобто, таким класичним бітом, що набуває випадково одне зі значень 0 або 1). В оптиці це еквівалентно різниці між некогерентними та когерентними хвилями: у першому випадку додаються інтенсивності хвиль, у другому — амплітуди (як це відбувається, наприклад, у голографії). a і b є довільними комплексними числами, на які без обмеження загальності накладаються умови нормування:

${\displaystyle |a|^{2}+|b|^{2}=1.}$

З математичної точки зору, числа ${\displaystyle P(0)=|a|^{2}=|\langle 0|\psi \rangle |^{2}}$ та ${\displaystyle P(1)=|b|^{2}=|\langle 1|\psi \rangle |^{2}}$ дорівнюють ймовірностям отримання відповідно значення 0 або 1 при вимірюванні кубіта, що знаходиться у стані ${\displaystyle |\psi \rangle }$. Однак, як вже було зазначено, не можна інтерпретувати кубіт як такий, що завжди знаходиться із певною ймовірністю виключно у стані ${\displaystyle |0\rangle }$ або ${\displaystyle |1\rangle }$, і ні в якому іншому: така поведінка відповідає класичному ймовірнісному бітові і може бути змодельована на класичному комп'ютері, що випадково генерує результат 0 або 1 (тобто, використовуючи генератор випадкових чисел). З точки зору теоретичної фізики, подібний класичний ймовірнісний біт підкоряється законам статистичної фізики, тому, на відміну від квантовомеханічного випадку, його стан являє собою некогерентну суміш двох відповідних станів.

У свою чергу, стан кубіта являє собою когерентну суперпозицію двох відповідних станів:

${\displaystyle P(\psi )=||\psi \rangle |^{2}=|a|^{2}+|b|^{2}+2\operatorname {Re} [a^{*}b\langle 0|1\rangle ],}$

де ${\displaystyle \operatorname {Re} [...]}$ позначає дійсну частину комплексного числа, ${\displaystyle a^{*}}$ — комплексно спряжене до a число, ${\displaystyle \langle 0|1\rangle }$ — скалярний добуток векторів станів 0 і 1.

Як і у випадку класичних бітів, N кубітів можна об'єднати у квантовий регістр, причому стан такого квантового регістра описуватиметься за допомогою ${\displaystyle 2^{N}}$-вимірного гільбертова простору. Базисом цього простору природно обираються всі можливі комбінації тензорних добутків N однокубітових базисних векторів ${\displaystyle |0\rangle }$ і ${\displaystyle |1\rangle }$. Наприклад, базисом для регістра, що складається з двох кубітів, буде набір з чотирьох векторів ${\displaystyle |00\rangle }$, ${\displaystyle |01\rangle }$, ${\displaystyle |10\rangle }$ і ${\displaystyle |11\rangle }$. Довільний стан квантового регістра матиме вигляд суперпозиції всіх його базисних векторів:

${\displaystyle |\psi _{N}\rangle =\sum _{i_{1},\dots ,i_{N}}c_{i_{1}\dots i_{N}}\,(|i_{1}\rangle \otimes |i_{2}\rangle \otimes \dots \otimes |i_{N}\rangle )\,,}$

де ${\displaystyle |i_{j}\rangle }$ — i-ий базисний вектор j-го кубіта, а ${\displaystyle c_{i_{1}\dots i_{N}}}$ — комлексні числа, що відовідають компонентам ${\displaystyle |\psi _{N}\rangle }$ уздовж відповідної комбінації однокубітових базисних векторів. Взагалі кажучи, у такому розкладі дозволені також суми та різниці станів декількох ${\displaystyle n\leq N}$ кубітів, на відміну від класичного регістра, де окремі біти з'являється лише у вигляді конкретного базисного стану, тобто, увесь класичний регістр являє собою просто набір з нулів та одиниць.

Важливою властивістю квантового регістра є той факт, що його стан не завжди є простою комбінацією незалежних один від одного станів окремих кубітів: зокрема, можна розглянути наступний стан двокубітового регістра (один зі станів Белла):

${\displaystyle |\Psi ^{+}\rangle ={\frac {1}{\sqrt {2}}}(|0\rangle \otimes |1\rangle +|1\rangle \otimes |0\rangle ),}$

який не можна звести до простого тензорного добутку станів першого та другого кубіта. Те ж саме можна сказати й про інший подібний стан двох кубітів:

${\displaystyle |\Psi ^{-}\rangle ={\frac {1}{\sqrt {2}}}(|0\rangle \otimes |1\rangle -|1\rangle \otimes |0\rangle ).}$

Про такі стани кажуть, що вони є сплутаними, а факт наявності таких станів носить назву квантової заплутаності (англ. quantum entanglement, нім. Quantenverschränkung).

Існування явища квантової заплутаності дає право говорити про те, що квантовий комп'ютер є набагато потужнішим за класичний, оскільки він здатен розв'язувати певні задачі набагато швидше, ніж це робить класичний комп'ютер. Наприклад, для зберігання N-бітового регістра класичний комп'ютер оперує N класичними бітами. Але аналогічний квантовий регістр описується вектором у ${\displaystyle 2^{N}}$-вимірному просторі, тому має бути задано ${\displaystyle 2^{N}}$ комплексних коефіцієнтів. У цьому випадку дуже важливим є той факт, що за великих N значення ${\displaystyle 2^{N}}$ є набагато більшим за N, тому часто принцип суперпозиції трактується як такий, що дозволяє зберігати в N-кубітовому регістрі одночасно всі ${\displaystyle 2^{N}}$ чисел від 0 до ${\displaystyle 2^{N}-1}$. Однак це твердження вводить в оману: оскільки результатом вимірювання стану квантового регістра завжди є один з його можливих базисних станів, то з допомогою теореми Холево можна довести, що максимально доступна кількість інформації, яку можна добути з одного кубіта, дорівнює одному бітові, як і в класичному випадку. Утім, слушним є твердження, що потужність квантових паралельних обчислень за принципом суперпозиції виходить за рамки можливостей, що надають класичні паралельні обчислення.

Квантовий вентиль CNOT — оборотний логічний елемент, що реалізує операцію «Контрольоване НЕ».

В класичному комп'ютері за допомогою логічних елементів (вентилів, англ. gates) можна виконувати елементарні операції над бітами, а комбінування вентилів дає можливість виконувати більш складні операції, наприклад, додавання двійкових чисел. Фізично логічні вентилі реалізовуються в класичному комп'ютері за допомогою певних пристроїв, зокрема транзисторів, а інформація в свою чергу передається у вигляді електричного сигналу, що проходить через ці пристрої.

Обчислення на квантовому комп'ютері принципово відрізняються від класичних: квантовий вентиль (англ. quantum gate) є не просто технічним пристроєм, а являє собою певну елементарну фізичну дію над одним або декількома кубітами. Конкретний вигляд цієї фізичної маніпуляції залежить передусім від фізичної природи кубіта: наприклад, спін електрона може змінити орієнтацію при накладанні магнітного поля, а атом — перейти у збуджений стан під впливом лазерного імпульса. Таким чином, квантові вентилі не являють собою окремі пристрої, а реалізуються як певні маніпуляції над квантовим регістром у необхідний проміжок часу, які зручно зображати у вигляді квантових схем при описі квантових алгоритмів.

З точки зору квантової механіки, квантовий вентиль є унітарним оператором ${\displaystyle {\hat {U}}}$, що діє на стан квантового регістра ${\displaystyle |\psi \rangle }$:

${\displaystyle |\psi \rangle \rightarrow {\hat {U}}|\psi \rangle .}$

Таким чином, квантовий вентиль можна представити у вигляді унітарної матриці. Наприклад, квантовий вентиль, що змінює стан кубіта на протилежний (заперечення НЕ), буде представлений у випадку двовимірного простору наступною матрицею:

${\displaystyle {\hat {U}}={\begin{pmatrix}0&1\\1&0\end{pmatrix}}.}$

Більш складними є квантові вентилі, що змінюють стани двох та більше кубітів, як, наприклад, вентиль CNOT (контрольоване НЕ), що діє у просторі ${\displaystyle \mathbb {C} ^{4}}$ двох кубітів за правилом: ${\displaystyle |00\rangle \to |00\rangle ,}$  ${\displaystyle |01\rangle \to |01\rangle ,}$  ${\displaystyle |10\rangle \to |11\rangle }$ та ${\displaystyle |11\rangle \to |10\rangle }$, тобто, змінюючи стан другого кубіта на протилежний, якщо перший кубіт знаходиться у стані ${\displaystyle |1\rangle }$, і залишаючи його таким самим, якщо, навпаки, перший кубіт знаходиться у стані ${\displaystyle |0\rangle }$.

Для опису квантових алгоритмів часто використовується квантова схема, що може включати в себе безліч різних квантових вентилів, які застосовуються до квантового регістра в чіткій послідовності. Наприклад, такі алгоритми, як квантове перетворення Фур'є або алгоритм Шора можна наочно зобразити у вигляді схеми, що складається з послідовності простих квантових вентилів — операторів Адамара, операторів зсуву фази та інших. Тобто, математично квантова схема являє собою складне унітарне перетворення, матриця якого є добутком матриць окремих квантових вентилів, що входять до неї.