Квантова схема

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

Однак оборотні вентилі в класичних комп'ютерах легко будуються для бітових рядків будь-якої довжини; більше того, вони насправді представляють практичний інтерес, оскільки необоротні вентилі завжди повинні збільшувати фізичну ентропію. Оборотний вентиль - це оборотна функція для n - бітових даних, яка повертає n - бітових даних, де n - бітові дані є рядком бітів x₁, x₂, ..., x_n довжини n. Набір бітових даних n - це простір {0,1}ⁿ, який складається з 2ⁿ рядків 0 і 1.

Точніше: n - бітовий оборотний вентиль - це бієктивне відображення f із множини {0,1}ⁿ з n -бітових даних на себе. Прикладом такого оборотного затвора f є відображення, яке застосовує фіксовану перестановку до своїх входів. У практичній інженерії зазвичай вивчають вентилі лише для малих значень n, напр. n=1, n=2 або n=3. Ці вентилі легко описати таблицями.

Щоб визначити квантові вентилі, нам спочатку потрібно визначити квантову заміну n - бітового даного. Квантована версія класичного n - бітового простору {0,1}ⁿ - це Гільбертів простір

${\displaystyle H_{\operatorname {QB} (n)}=\ell ^{2}(\{0,1\}^{n}).}$

Це за визначенням простір комплекснозначимих функцій над {0,1}ⁿ і, природно, є внутрішнім добутком простору. Цей простір також можна розглядати як такий, що складається з лінійних суперпозицій класичних бітових рядків. Зверніть увагу, що H_QB(n) - це векторний простір над комплексними числами розмірності 2ⁿ. Елементи цього простору називаються n - кубітами.

Використовуючи нотацію Дірака (Нотація бра-кет), якщо x₁, x₂, ..., x_n - це класичний бітовий рядок, то

${\displaystyle |x_{1},x_{2},\cdots ,x_{n}\rangle \quad }$

є спеціальним n - кубітом, що відповідає функції, яка відображає цей класичний бітовий рядок до 1, а всі інші бітові рядки - до 0; ці 2ⁿ спеціальні n - кубіти називаються обчислювальними базовими станами. Всі n - кубіти - це комплексні лінійні комбінації цих обчислювальних базових станів.

Квантові логічні вентилі, на відміну від класичних логічних вентилів, завжди оборотні. Для цього потрібен особливий вид оборотної функції, а саме унітарне відображення, тобто лінійне перетворення комплексного внутрішнього добутку простору, що зберігає внутрішній добуток Ерміта. Квантовий вентиль n - кубітовий (оборотний) - це унітарне відображення U з n - кубітного простору H_QB(n) на себе.

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

Оборотний n - бітовий класичний логічний вентиль створює оборотний n - бітовий квантовий вентиль таким чином: кожному оборотному n - бітовому логічному вентилю f відповідає квантовий вентиль W_f, який визначається наступним чином:

${\displaystyle W_{f}(|x_{1},x_{2},\cdots ,x_{n}\rangle )=|f(x_{1},x_{2},\cdots ,x_{n})\rangle .}$

Зверніть увагу, що W_f переставляє обчислювальні базисні стани.

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

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

${\displaystyle U_{\theta }={\begin{bmatrix}e^{i\theta }&0\\0&1\end{bmatrix}},}$

тому

${\displaystyle U_{\theta }|0\rangle =e^{i\theta }|0\rangle \quad U_{\theta }|1\rangle =|1\rangle .}$

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

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

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

Тепер можна показати, що вентиль Тоффолі є універсальним вентилем. Це означає, що будь-якого заданого оборотного класичного n - бітового ланцюга h, ми можемо побудувати класичну збірку вентилів Тоффолі вищезазначеним способом, щоб отримати (n + m) -бітову схему f таку, що

${\displaystyle f(x_{1},\ldots ,x_{n},\underbrace {0,\dots ,0} )=(y_{1},\ldots ,y_{n},\underbrace {0,\ldots ,0} )}$

де існують m введених нульових входів і

${\displaystyle (y_{1},\ldots ,y_{n})=h(x_{1},\ldots ,x_{n})}$.

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

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

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

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

Існують також теореми про універсальність для певних наборів добре відомих вентилів; така теорема універсальності існує, наприклад, для пари, що складається з одного кубітного фазового затвора U_θ, згаданого вище (для відповідного значення θ), разом із 2-кубітовим CNOT W_CNOT. Однак теорема універсальності для квантового випадку дещо слабша, ніж для класичного випадку; вона стверджує лише, що будь-яка оборотна n - кубітна схема може бути довільно апроксимована схемою, зібраною з цих двох елементарних вентилів. Зверніть увагу, що існує незліченно багато можливих одинарних кубітових фазових вентилів, по одному на кожен можливий кут θ, тому всі вони не можуть бути представлені скінченною схемою, побудованою з { U_θ, W_CNOT }.

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

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

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

Тепер ми пропонуємо математичну модель того, як квантові схеми можуть імітувати імовірнісні, але класичні обчислення. Розглянемо r - кубітову схему U з простором регістра H_QB(r). Таким чином, U є унітарним відображенням

${\displaystyle H_{\operatorname {QB} (r)}\rightarrow H_{\operatorname {QB} (r)}.}$

• Вхідний регістр X={0,1}^m з m (класичних) бітів.
• Вихідний регістр Y={0,1}ⁿ з n (класичних) бітів.

Вміст x = x₁, ..., x_m класичного вхідного регістра використовується для ініціалізації якимось чином кубітового (квантового) регістра. В ідеалі це було б зроблено у обчислювальному базисі стану

${\displaystyle |{\vec {x}},0\rangle =|x_{1},x_{2},\cdots ,x_{m},\underbrace {0,\dots ,0} \rangle ,}$

де r - m встановлені в нуль входи. Тим не менше, ця ідеальна ініціалізація абсолютно нереальна. Припустимо отже, що ініціалізація - це змішаний стан, заданий деяким оператором щільності S, який знаходиться поблизу ідеалізованого входу в якійсь відповідній метриці, наприклад

${\displaystyle \operatorname {Tr} \left({\big |}|{\vec {x}},0\rangle \langle {\vec {x}},0|-S{\big |}\right)\leq \delta .}$

Аналогічно, простір стану вихідного регістра, пов'язаного з кубітовим регістром, спостережуване А, оцінене як значення Y . Зауважимо, що спостережувані в квантовій механіці зазвичай визначаються в термінах проективних мір у R; якщо трапляється дискретна змінна, проективна міра зменшується до сімейства {E _λ }, проіндексованого за деяким параметром λ зі зліченної множини. Аналогічно, Y , що оцінюється спостережуваним, може бути пов'язана з сімейством попарно ортогональних проекцій {Ey}, яке індексується елементами Y . такими як

${\displaystyle I=\sum _{y\in Y}\operatorname {E} _{y}.}$

Враховуючи змішаний стан S, відповідна міра ймовірності на Y дана як:

${\displaystyle \operatorname {Pr} \{y\}=\operatorname {Tr} (S\operatorname {E} _{y}).}$

Функція F:X → Y обчислюється за схемою U: H_QB(r) → H_QB(r) з точністю до ε якщо і тільки якщо для всіх бітових рядків x довжини m

${\displaystyle \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 .}$

Тому

${\displaystyle \left|\operatorname {Tr} (SU^{*}\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 }$

таке що:

${\displaystyle \operatorname {Tr} (SU^{*}\operatorname {E} _{F(x)}U)\geq 1-\epsilon -\delta .}$

Теорема. Якщо ε + δ < 1/2, тоді розподіл імовірності

${\displaystyle \operatorname {Pr} \{y\}=\operatorname {Tr} (SU^{*}\operatorname {E} _{y}U)}$

на Y може бути використаний для визначення F (x) із довільно малою ймовірністю помилки шляхом вибору більшості для досить великого обсягу вибірки. Зокрема, слід взяти незалежні вибірки k з розподілу ймовірностей Pr на Y і обрати значення, з яким погоджується більше половини зразків. Імовірність того, що значення F(x) буде обране більше, ніж k/2 рази, становить принаймні

${\displaystyle 1-e^{-2\gamma ^{2}k},}$

де γ = 1/2 - ε - δ.

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

• Q-circuit - це макропакет для накреслення квантових схем в LaTeX.
• Симулятор квантових схем (Davy Wybiral) редактор і симулятор квантових схем на основі браузера.
• Quantum Computing Playground середовище квантових сценаріїв на основі браузера.
• Quirk - Quantum Circuit Toy редактор і симулятор квантових схем на основі браузера.