Перегляд вихідного коду сторінки Квантова схема

{{Недоліки|<br/>Відсутні джерела, останній розділ — проблема зі стилем}}

'''Квантова схема'''&nbsp;— це модель для [[Квантові обчислення|квантових обчислень]], в якому обчислення є послідовністю [[Квантовий вентиль|квантових вентилів]], які є оборотними перетвореннями на [[Квантова механіка|квантово-механічному]] {{Не перекладено|Квантовий регістр|аналогу|en|Quantum register}} ''n''&nbsp;— [[біт]]ного [[Регістр процесора|регістра]]. Цю аналогічну структуру називають ''n''-[[кубіт]]овим регістром.

Графічне зображення елементів квантових ланцюгів описується за допомогою варіанту [[Графічне позначення Пенроуза|графічної нотації Пенроуза]]. 1986 року [[Річард Філіпс Фейнман|Річард Фейнман]] використовував ранню версію нотації квантової схеми.<ref name="feynman">{{Cite journal|author=Feynman|first=Richard P.|year=1986|title=Quantum mechanical computers|journal=Foundations of Physics|publisher=Springer Science and Business Media LLC|volume=16|issue=6|pages=507–531|bibcode=1986FoPh...16..507F|doi=10.1007/bf01886518|issn=0015-9018}}</ref>

== Оборотні класичні логічні вентилі ==

Елементарні [[логічні вентилі]] класичного комп'ютера, крім вентиля [[Інвертор (логічний вентиль)|НЕ]], не є [[Оборотні обчислення|оборотними]]. Так, наприклад, для вентиля [[І]] не завжди можна відновити два вхідні біти з вихідного біта; наприклад, якщо вихідний біт дорівнює 0, ми з цього не можемо визначити, чи є вхідні біти 0,1 або 1,0 або 0,0.

Однак оборотні вентилі в класичних комп'ютерах легко будуються для бітових рядків будь-якої довжини; більше того, вони насправді представляють практичний інтерес, оскільки необоротні вентилі завжди повинні збільшувати фізичну [[Ентропія|ентропію]]. Оборотний вентиль&nbsp;— це оборотна функція для ''n''&nbsp;— бітових даних, яка повертає ''n''&nbsp;— бітових даних, де ''n''&nbsp;— бітові дані є [[Рядок (програмування)|рядком]] бітів ''x''<sub>1</sub>, ''x''<sub>2</sub>, …, ''x''<sub>''n''</sub> довжини ''n''. Набір бітових даних ''n''&nbsp;— це простір {0,1}<sup>''n''</sup>, який складається з 2<sup>''n''</sup> рядків 0 і 1.

Точніше: ''n''&nbsp;— бітовий оборотний вентиль&nbsp;— це [[Бієкція|бієктивне]] відображення ''f'' із множини {0,1}<sup>''n''</sup> з ''n'' -бітових даних на себе. Прикладом такого оборотного затвора ''f'' є відображення, яке застосовує фіксовану перестановку до своїх входів.
У практичній інженерії зазвичай вивчають вентилі лише для малих значень ''n'', напр. ''n''=1, ''n''=2 або ''n''=3. Ці вентилі легко описати таблицями.

== Квантові логічні вентилі ==

Щоб визначити квантові вентилі, нам спочатку потрібно визначити квантову заміну ''n''&nbsp;— бітового даного. Квантована версія класичного ''n''&nbsp;— бітового простору {0,1}<sup>''n''</sup>&nbsp;— це [[Гільбертів простір]]

: <math>H_{\operatorname{QB}(n)}= \ell^2(\{0,1\}^n).</math>

Це за визначенням простір комплекснозначимих функцій над {0,1}<sup>''n''</sup> і, природно, є [[Передгільбертів простір|внутрішнім добутком простору]]. Цей простір також можна розглядати як такий, що складається з лінійних суперпозицій класичних бітових рядків. Зверніть увагу, що ''H''<sub>QB(''n'')</sub>&nbsp;— це векторний простір над комплексними числами [[Розмірність простору|розмірності]] 2<sup>''n''</sup>. Елементи цього простору називаються ''n''&nbsp;— кубітами.

Використовуючи нотацію Дірака ([[Нотація бра-кет]]), якщо ''x''<sub>1</sub>, ''x''<sub>2</sub>, …, ''x''<sub>''n''</sub>&nbsp;— це класичний бітовий рядок, то

: <math> | x_1, x_2, \cdots,x_n \rangle \quad </math>

є спеціальним ''n''&nbsp;— кубітом, що відповідає функції, яка відображає цей класичний бітовий рядок до 1, а всі інші бітові рядки&nbsp;— до 0; ці 2<sup>''n''</sup> спеціальні ''n''&nbsp;— кубіти називаються ''обчислювальними базовими станами''. Всі ''n''&nbsp;— кубіти&nbsp;— це комплексні лінійні комбінації цих обчислювальних базових станів.

Квантові логічні вентилі, на відміну від класичних логічних вентилів, завжди оборотні. Для цього потрібен особливий вид оборотної функції, а саме [[Унітарність (фізика)|унітарне]] відображення, тобто лінійне перетворення комплексного [[Внутрішній добуток|внутрішнього добутку простору]], що зберігає внутрішній добуток Ерміта. Квантовий вентиль ''n''&nbsp;— кубітовий (оборотний)&nbsp;— це [[Унітарний оператор|унітарне відображення]] ''U'' з ''n''&nbsp;— кубітового простору ''H''<sub>QB(''n'')</sub> на себе.

Як правило, нас цікавлять вентилі лише для малих значень '' n ''.

Оборотний ''n''&nbsp;— бітовий класичний логічний вентиль створює оборотний ''n''&nbsp;— бітовий квантовий вентиль таким чином: кожному оборотному ''n''&nbsp;— бітовому логічному вентилю ''f'' відповідає квантовий вентиль ''W''<sub>''f''</sub>, який визначається наступним чином:
: <math> W_f (| x_1, x_2, \cdots, x_n \rangle) = | f (x_1, x_2, \cdots, x_n) \rangle. </math>

Зверніть увагу, що ''W''<sub>''f''</sub> переставляє обчислювальні базисні стани.

Особливе значення має вентиль керований NOT (також званий [[CNOT]]) ''W''<sub>CNOT</sub>, визначений на 2 кубітах. Іншими прикладами квантових логічних вентилів, похідних від класичних, є [[вентиль Тоффолі]] та [[вентиль Фредкіна]].

Однак гільбертово-просторова структура кубітів допускає багато квантових вентилів, які не наводяться класичними. Наприклад, відносний фазовий зсув&nbsp;— це 1 кубітовий вентиль, отриманий множенням на унітарну матрицю:

: <math> U_\theta =\begin{bmatrix} e^{i \theta} & 0 \\ 0 & 1 \end{bmatrix}, </math>

тому
 
: <math> U_\theta | 0 \rangle = e^{i \theta}  | 0 \rangle \quad U_\theta | 1 \rangle = | 1 \rangle. </math>

== Оборотні логічні схеми ==
{{main | Оборотні обчислення}}

Концептуально немає різниці між оборотною ''n''&nbsp;— бітовою схемою та оборотним ''n''&nbsp;— бітовим логічним вентилем: будь-що із них є просто інвертованою функцією на просторі ''n''-бітових даних. Однак, як згадувалося в попередньому розділі, з технічних причин ми хотіли б мати невелику кількість простих оборотних вентилів, які можна скласти для складання будь-якої оборотної схеми.

Щоб пояснити цей процес складання, припустимо, у нас є оборотний ''n''&nbsp;— бітовий вентиль ''f'' і оборотний ''m''&nbsp;— бітовий вентиль ''g''. Їхнє з'єднання означає створення нової схеми шляхом підключення деякого набору ''k'' виходів ''f'' до деякого набору ''k'' входів ''g'', як на малюнку нижче. На цьому малюнку ''n''=5, ''k''=3 та ''m''=7. Отримана схема також є оборотною і працює на ''n''+''m'' &minus; ''k'' бітах.

<center>
[[Файл:Reversible circuit composition.svg|175px]]
</center>

Ми будемо позначати цю схему як ''класичну збірку'' (ця концепція відповідає технічному визначенню в новаторському документі Кітаєва, наведеному нижче). Складаючи ці оборотні машини, важливо забезпечити, щоб проміжні машини також були оборотними. Ця умова гарантує, що «проміжне» «сміття» не створюється.

Тепер можна показати, що вентиль Тоффолі є універсальним вентилем. Це означає, що будь-якого заданого оборотного класичного ''n''&nbsp;— бітового ланцюга ''h'', ми можемо побудувати класичну збірку вентилів Тоффолі вищезазначеним способом, щоб отримати (''n'' + ''m'') -бітову схему ''f'' таку, що
: <math> f(x_1, \ldots, x_n, \underbrace{0, \dots, 0}) = (y_1, \ldots, y_n, \underbrace{0, \ldots , 0})</math>
де існують ''m'' введених нульових входів і
: <math>(y_1, \ldots, y_n) = h(x_1, \ldots, x_n)</math>.

Зверніть увагу, що кінцевий результат завжди має рядок нулів ''m'' як [[Допоміжний біт|допоміжних бітів]]. Жодного «сміття» ніколи не виробляється, і тому це обчислення справді таке, яке у фізичному сенсі не породжує ентропії. Це питання ретельно обговорюється в статті Китаева.

Більш загально, будь-яка функція ''f'' (бієктивна чи ні) може бути змодельована схемою вентилів Тоффолі. Очевидно, що якщо відображення не може бути [[Ін'єкція (математика)|ін'єктивним]], в якийсь момент моделювання (наприклад, на останньому кроці) має бути створено деяке «сміття».

Для квантових схем можна визначити подібну композицію [[Квантовий вентиль|кубітових вентилів]]. Тобто, аналогічно до будь-якої ''класичної збірки'', як зазначено вище, ми можемо створити оборотну квантову схему, коли замість ''f'' ми маємо ''n''&nbsp;— кубітовий вентиль ''U'' і на місці ''g'' ми маємо ''m''&nbsp;— кубітовий вентиль ''W''. Див. Ілюстрацію нижче:

<center>
[[Файл:Quantum circuit composition.svg|300px]]
</center>

Той факт, що з'єднання вентилів таким чином породжує унітарне відображення на кубітовому просторі ''n''+''m'' &minus; ''k'', легко перевірити. У реальному квантовому комп'ютері фізичний зв'язок між вентилями є головною інженерною проблемою, оскільки це одне з місць, де може відбуватися [[декогеренція]].

Існують також теореми про універсальність для певних наборів добре відомих вентилів; така теорема універсальності існує, наприклад, для пари, що складається з одного кубітового фазового затвора ''U''<sub>θ</sub>, згаданого вище (для відповідного значення θ), разом із 2-кубітовим [[CNOT]] ''W''<sub>CNOT</sub>. Однак теорема універсальності для квантового випадку дещо слабша, ніж для класичного випадку; вона стверджує лише, що будь-яка оборотна ''n''&nbsp;— кубітова схема може бути довільно апроксимована схемою, зібраною з цих двох елементарних вентилів. Зверніть увагу, що існує [[Незліченна множина|незліченно]] багато можливих одинарних кубітових фазових вентилів, по одному на кожен можливий кут θ, тому всі вони не можуть бути представлені скінченною схемою, побудованою з { ''U''<sub>θ</sub>, ''W''<sub>CNOT</sub> }.

== Квантові обчислення ==
Квантові схеми використовуються для виконання обчислень. Оскільки багато важливих числових задач зводяться до обчислення унітарного перетворення ''U'' на [[Скінченновимірний простір|скінченновимірному просторі]] (відоме [[дискретне перетворення Фур'є]] є яскравим прикладом), можна було б очікувати, що якась квантова схема може бути спроектована для здійснення перетворення ''U''. В принципі, потрібно лише підготувати ''n''-кубітовий стан ψ як відповідну суперпозицію обчислювальних базових станів для вхідних даних та виміряти вихід ''U''ψ. На жаль, з цим є дві проблеми:

* Не можна виміряти фазу ψ в будь-якому обчислювальному базовому стані, тому немає можливості прочитати повну відповідь. Це носить характер [[Вимірювання (квантова механіка)|вимірювання в квантовій механіці]].
* Неможливо ефективно підготувати вхідний стан ψ.

Це не заважає використовувати квантові схеми для дискретного перетворення Фур'є як проміжні етапи в інших квантових схемах, але використання є більш тонким. Насправді квантові обчислення є ''імовірнісними''.

Тепер ми пропонуємо математичну модель того, як квантові схеми можуть імітувати ''імовірнісні'', але класичні обчислення. Розглянемо ''r''&nbsp;— кубітову схему ''U'' з простором регістра ''H''<sub>QB(''r'')</sub>. Таким чином, ''U'' є унітарним відображенням
: <math>H_{\operatorname{QB}(r)} \rightarrow
H_{\operatorname{QB}(r)}.</math>

* ''Вхідний регістр'' ''X''={0,1}<sup>''m''</sup> з ''m'' (класичних) бітів.
* ''Вихідний регістр'' ''Y''={0,1}<sup>''n''</sup> з ''n'' (класичних) бітів.

Вміст ''x'' = ''x''<sub>1</sub>, …, ''x''<sub>''m''</sub> класичного вхідного регістра використовується для ініціалізації якимось чином кубітового ([[Квантовий регістр|квантового]]) регістра. В ідеалі це було б зроблено у обчислювальному базисі стану
: <math> |\vec{x},0\rangle= | x_1, x_2, \cdots, x_{m}, \underbrace{0, \dots, 0} \rangle, </math>
де ''r''&nbsp;— ''m'' встановлені в нуль входи. Тим не менше, ця ідеальна ініціалізація абсолютно нереальна. Припустимо отже, що ініціалізація&nbsp;— це змішаний стан, заданий деяким оператором щільності ''S'', який знаходиться поблизу ідеалізованого входу в якійсь відповідній метриці, наприклад
: <math> \operatorname{Tr}\left(\big||\vec{x},0\rangle \langle \vec{x},0 | - S\big|\right) \leq \delta. </math>

Аналогічно, простір стану вихідного регістра, пов'язаного з кубітовим регістром, спостережуване ''А,'' оцінене як значення ''Y''. Зауважимо, що спостережувані в квантовій механіці зазвичай визначаються в термінах проективних мір у '''R'''; якщо трапляється дискретна змінна, проективна міра зменшується до сімейства {E<sub> λ </sub>}, проіндексованого за деяким параметром λ зі зліченної множини. Аналогічно, ''Y'', що оцінюється спостережуваним, може бути пов'язана з сімейством попарно ортогональних проєкцій {Ey}, яке індексується елементами '' Y ''. такими як
: <math> I = \sum_{y \in Y} \operatorname{E}_y. </math>

Враховуючи змішаний стан ''S'', відповідна міра ймовірності на ''Y'' дана як:
: <math> \operatorname{Pr}\{y\} = \operatorname{Tr}(S \operatorname{E}_y ). </math>

Функція ''F'':''X'' → ''Y'' обчислюється за схемою ''U'': ''H''<sub>QB(''r'')</sub> → ''H''<sub>QB(''r'')</sub> з точністю до ε якщо і тільки якщо для всіх бітових рядків ''x'' довжини ''m''
: <math>\left\langle \vec{x},0 \big| U^* \operatorname{E}_{F(x)} U
\big|\vec{x},0 \right\rangle = \left\langle \operatorname{E}_{F(x)} U( |\vec{x},0\rangle) \big|  U( |\vec{x},0\rangle) \right\rangle \geq 1 - \epsilon.</math>

Тому
: <math> \left| \operatorname{Tr} (S U^* \operatorname{E}_{F(x)} U) - \left\langle \vec{x},0 \big| U^* \operatorname{E}_{F(x)} U
\big|\vec{x},0 \right\rangle\right|\leq \operatorname{Tr} (\big||\vec{x},0\rangle \langle \vec{x},0 | - S\big|) \| U^* \operatorname{E}_{F(x)} U \| \leq \delta </math>

таке що:
: <math>\operatorname{Tr} (S U^* \operatorname{E}_{F(x)} U) \geq 1 - \epsilon - \delta.</math>

'''Теорема'''. Якщо ε + δ < 1/2, тоді розподіл імовірності
: <math> \operatorname{Pr}\{y\} = \operatorname{Tr} (SU^* \operatorname{E}_{y} U)</math>

на ''Y'' може бути використаний для визначення ''F'' (''x'') із довільно малою ймовірністю помилки шляхом вибору більшості для досить великого обсягу вибірки. Зокрема, слід взяти незалежні вибірки ''k'' з розподілу ймовірностей Pr на ''Y'' і обрати значення, з яким погоджується більше половини зразків. Імовірність того, що значення ''F''(''x'') буде обране більше, ніж ''k''/2 рази, становить принаймні
: <math> 1 - e^{- 2 \gamma^2 k}, </math>
де γ = 1/2&nbsp;— ε - δ.

Це випливає із застосування [[Нерівність Чернова|межі Чернова]].

== Див. також ==
* [[Квантовий алгоритм]]

== Примітки ==
{{reflist}}

== Посилання ==
* [https://cquic.unm.edu/resources/ Q-circuit] {{Webarchive|url=https://web.archive.org/web/20190323101451/https://cquic.unm.edu/resources/ |date=23 березня 2019 }}&nbsp;— це макропакет для накреслення квантових схем в LaTeX.
* [https://wybiral.github.io/quantum Симулятор квантових схем (Davy Wybiral)] {{Webarchive|url=https://web.archive.org/web/20210128151507/https://wybiral.github.io/quantum/ |date=28 Січня 2021 }} редактор і симулятор квантових схем на основі браузера.
* [http://www.quantumplayground.net/ Quantum Computing Playground] {{Webarchive|url=https://web.archive.org/web/20210116170957/http://www.quantumplayground.net/ |date=16 Січня 2021 }} середовище квантових сценаріїв на основі браузера.
* [http://algorithmicassertions.com/quirk Quirk&nbsp;— Quantum Circuit Toy] {{Webarchive|url=https://web.archive.org/web/20161225063122/http://algorithmicassertions.com/quirk |date=25 Грудня 2016 }} редактор і симулятор квантових схем на основі браузера.

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

{{Перспективні технології|квантові=так}}

[[Категорія:Квантова інформатика]]