"Думаю, я сміливо можу сказати, що квантову механіку ніхто не розуміє", - Річард Фейнман
Тема квантових обчислень завжди приваблювала технічних письменників та журналістів. Її потенціал у галузі обчислень та складність надали їй якийсь містичний ореол. Занадто часто тематичні статті та інфографіка докладно описують всілякі перспективи цієї галузі, при цьому ледве порушуючи питання її практичного застосування: це може ввести в оману не надто уважного читача.
У науково-популярних статтях опускаються описи квантових систем та наводяться затвердження типу:
Звичайний біт може дорівнювати "1" або "0", але кубит може бути одночасно дорівнює "1" і "0".
Якщо вам дуже пощастить (у чому я не впевнений), то вам розкажуть, що:
Кубіт знаходиться у суперпозиції між «1» та «0».
Жодне з цих пояснень не видається правдоподібним, оскільки ми намагаємося сформулювати квантовомеханічний феномен за допомогою мовних засобів, створених у дуже традиційному світі. Щоб зрозуміло пояснити принципи квантових обчислень, необхідно застосувати іншу мову — математичну.
У цьому посібнику я розповім про математичні інструменти, необхідні для моделювання та розуміння квантових обчислювальних систем, а також про те, як ілюструвати та застосовувати логіку квантових обчислень. Більше того, я наведу приклад квантового алгоритму та розповім, у чому його перевага перед традиційним комп'ютером.
Я докладу всіх зусиль, щоб розповісти про все це зрозумілою мовою, але все ж таки сподіваюся, що у читачів цієї статті є базові уявлення про лінійну алгебру та цифрову логіку (про лінійну алгебру розповідається , про цифрову логіку ).
Для початку давайте пробіжимося за принципами цифрової логіки. Вона полягає в використанні електричних схем щодо обчислень. Щоб зробити наш опис абстрактнішим, спростимо стан електропроводу до «1» або «0», що відповідатиме станам «вкл» або «викл». Вибудувавши транзистори у певній послідовності, ми створимо так звані логічні елементи, що приймають одне або кілька значень вхідних сигналів і перетворюють їх на вихідний сигнал на основі певних правил булевої логіки.
Поширені логічні елементи та таблиці їх станів
На основі ланцюгів таких базових елементів можна створювати більш складні елементи, а на основі ланцюгів складніших елементів ми зрештою з великою часткою абстрактності можемо розраховувати на отримання аналога центрального процесора.
Як я вже згадував раніше, нам потрібний спосіб математичного відображення цифрової логіки. Для початку представимо математичну традиційну логіку. За допомогою лінійної алгебри класичні біти зі значеннями «1» і «0» можна подати у вигляді двох вектор-стовпців:
де цифри зліва вектор. Представивши наші біти в такий спосіб, ми можемо моделювати логічні операції над бітами з використанням векторних трансформацій. Зверніть увагу: незважаючи на те, що при використанні двох бітів в логічних елементах можна виконувати безліч операцій («І» (AND), «Не» (NOT), «Искл. Або» (XOR) та ін), при використанні одного біта можливе виконання лише чотирьох операцій: тотожне перетворення, заперечення, обчислення константи «0» та обчислення константи «1». При тотожному перетворенні біт залишається незмінним, при запереченні значення біта змінюється протилежне (з «0» на «1» чи з «1» на «0»), а обчислення константи «1» чи «0» встановлюють біт в «1» або "0" незалежно від його попереднього значення.
| Особистість | Тотожне перетворення |
| Заперечення | Заперечення |
| Constant-0 | Обчислення константи «0» |
| Constant-1 | Обчислення константи «1» |
На підставі запропонованого нами нового уявлення біта досить легко виконувати операції над відповідним бітом за допомогою векторної трансформації:
Перш ніж рушити далі, давайте звернемося до поняття , Що всього лише передбачає, що для забезпечення оборотності операції або логічного елемента необхідно визначити список значень вхідних сигналів на підставі вихідних сигналів та назв операцій, що використовуються. Таким чином можна зробити висновок, що тотожне перетворення і заперечення є оборотними, а операції з обчислення констант «1» і «0» — ні. Завдяки квантової механіки квантові комп'ютери використовують виключно оборотні операції, тому ми і зосередимося. Далі ми перетворимо незворотні елементи в оборотні, щоб забезпечити їх використання квантовим комп'ютером.
За допомогою окремих бітів можна уявити безліч бітів:
Тепер, коли ми маємо майже всі необхідні математичні уявлення, перейдемо до нашого першого квантового логічного елемента. Це оператор , або контрольоване "Ні" (NOT), який має велике значення в оборотних та квантових обчисленнях. Елемент CNOT застосовується до двох біт і повертає два біти. Перший біт призначається "керуючим", а другий - "контрольним". Якщо керуючий біт встановлено «1», контрольний біт змінює своє значення; якщо керуючий біт встановлено «0», контрольний біт не змінюється.
Цей оператор може бути представлений у вигляді наступного вектора перетворення:
Щоб продемонструвати все, з чим ми вже розібралися, я покажу варіанти застосування елемента CNOT щодо безлічі бітів:
p align="justify"> Резюмуємо вже сказане: у першому прикладі ми розкладаємо |10⟩ на частини його тензорного твору і використовуємо матрицю CNOT для отримання нового відповідного стану твору; потім ми факторизуємо його до |11⟩ відповідно до наведеної раніше таблиці значень CNOT.
Отже, ми згадали всі математичні правила, які допоможуть розібратися з традиційними обчисленнями та звичайними бітами, і нарешті можемо перейти до сучасних квантових обчислень та кубітів.
Якщо ви дочитали до цього місця, то я маю для вас гарну новину: кубити легко можна висловити математично. Загалом, якщо класичний біт (cbit) може встановлюватися в |1? або |0?, кубіт просто знаходиться в суперпозиції і до виміру може одночасно дорівнювати |0? і |1?. Після виміру він колапсує у |0⟩ або |1⟩. Іншими словами, кубит можна представити у вигляді лінійної комбінації |0⟩ та |1⟩ відповідно до наведеної нижче формули:
де a₀ и a₁ представляють, відповідно, амплітуди |0⟩ та |1⟩. Їх можна розглядати як «квантові ймовірності», які представляють ймовірність колапсування кубіту в будь-який стан після його вимірювання, оскільки в квантовій механіці об'єкт в суперпозиції колапсує в один зі станів після фіксації. Розкладемо цей вислів і отримаємо таке:
Щоб спростити своє пояснення, саме цим поданням я користуватимуся у цій статті.
Для цього кубіту шанс колапсування у значення a₀ після виміру дорівнює |a₀|², а шанс колапсування у значення a₁ дорівнює |a₁|². Наприклад, для наступного кубіту:
шанс колапсування в «1» дорівнює |1/√2|², або?, тобто 50/50.
Оскільки у класичній системі всі ймовірності у сумі повинні давати одиницю (для повноцінного розподілу ймовірностей), можна дійти невтішного висновку у тому, що квадрати абсолютних значень амплітуд |0⟩ і |1⟩ повинні у сумі становити одиницю. На підставі цієї інформації ми можемо скласти наступне рівняння:
Якщо ви знайомі з тригонометрією, то помітите, що це рівняння відповідає теоремі Піфагора (a²+b²=c²), тобто ми можемо графічно уявити можливі стани кубіту у вигляді точок на одиничному колі, а саме:
Логічні оператори та елементи застосовуються щодо кубітів так само, як і в ситуації з класичними бітами – на підставі матричної трансформації. Всі оборотні матричні оператори, які ми згадали до цього моменту, зокрема CNOT, можуть використовуватися для роботи з кубитами. Такі матричні оператори дозволяють використовувати кожну з амплітуд кубіту без його вимірювання та колапсування. Дозвольте навести приклад використання оператора заперечення до кубіту:
Перш ніж ми продовжимо, я нагадаю, що значення амплітуд a₀ та a₁ насправді є , тому стан кубіту найбільш точно можна відобразити на тривимірній одиничній сфері, також відомій як :
Проте, щоб спростити пояснення, ми обмежимося дійсними числами.
Здається, настав час обговорити деякі логічні елементи, які набувають сенсу виключно в контексті квантових обчислень.
Одним з найважливіших операторів є "елемент Адамара": він бере біт у стані "0" або "1" і ставить його у відповідну суперпозицію з 50%-шансом його колапсування в "1" або "0" після вимірювання.
Зверніть увагу, що в нижній правій частині оператора Адамара є негативне число. Це з тим, що результат застосування оператора залежить від значення вхідного сигналу: — |1⟩ чи |0⟩, і тому обчислення є оборотним.
Ще одним важливим моментом, пов'язаним з елементом Адамара, є його оборотність, тобто він може приймати кубит у відповідній суперпозиції і перетворити його на |0 чи |1?.
Це дуже важливо, оскільки дає нам можливість перетворення квантового стану без визначення стану кубіту — і, відповідно, без його колапсування. Так ми можемо структурувати квантові обчислення на основі детермінованого, а не ймовірнісного принципу.
Квантові оператори, що містять виключно дійсні числа, є власною протилежністю, тому ми можемо уявити результат застосування оператора до кубіту як перетворення в межах одиничного кола у вигляді машини станів:
Таким чином, кубит, стан якого представлений на схемі вище, після застосування операції Адамара перетворюється на стан, позначений відповідною стрілкою. Аналогічно, ми можемо сконструювати іншу машину станів, яка ілюструватиме перетворення кубіту при використанні оператора заперечення, як було показано вище (також відомого як оператор заперечення Паулі, або інверсія бітів), як показано нижче:
Щоб виконувати більш складні операції з нашим кубитом, можна використовувати ланцюжок безлічі операторів або застосувати елементи безліч разів. Приклад серійної трансформації на основі виглядає наступним чином:
Тобто, якщо ми починаємо з біту |0⟩, застосовуємо інверсію біта, а потім операцію Адамара, потім ще одну інверсію біта, і ще раз операцію Адамара, після чого фінальну інверсію біта, в результаті ми отримуємо вектор, наведений у правій частині ланцюга. Накладаючи різні машини станів одна на одну, ми зможемо починати з |0⟩ і відстежувати різнокольорові стрілки, відповідні кожного з перетворень, аби зрозуміти, як усе працює.
Раз ми зайшли так далеко, настав час розглянути один із типів квантових алгоритмів, а саме — , і показати його перевагу над класичною обчислювальною машиною. Варто зазначити, що алгоритм Дойча-Йожи є повністю детермінованим, тобто він повертає правильну відповідь у 100% випадків (на відміну багатьох інших квантових алгоритмів, заснованих на ймовірнісному визначенні кубитів).
Давайте уявимо, що у вас є чорна скринька, яка містить функцію/оператор над одним бітом (пам'ятайте — при використанні одного біта можливе виконання лише чотирьох операцій: тотожне перетворення, заперечення, обчислення константи «0» та обчислення константи «1»). Яка саме функція виконується у ящику? Ви не знаєте яка, проте можете перебрати скільки завгодно варіантів вхідних значень та оцінити результати на виході.
Скільки вхідних та вихідних сигналів доведеться прогнати через чорну скриньку, щоб з'ясувати, яка функція застосовується? Подумайте про це на секунду.
У випадку з класичним комп'ютером потрібно зробити 2 запити для визначення функції, що застосовується. Наприклад, якщо при введенні «1» ми отримуємо на виході «0», стає зрозуміло, що використовується функція обчислення константи «0», або функція заперечення, після чого вам доведеться змінити значення вхідного сигналу на «0» і подивитися, що вийде на виході.
У випадку з квантовим комп'ютером також потрібно два запити, оскільки вам, як і раніше, потрібні два різні вихідні значення для точного визначення функції, що застосовується до вхідного значення. Втім, якщо трохи переформулювати питання, виявиться, що квантові комп'ютери все ж таки мають серйозну перевагу: якби ви хотіли дізнатися, чи є функція постійною або змінною, перевага виявилася б на стороні квантових обчислювальних машин.
Функція, що застосовується в ящику, є змінною, якщо різні значення вхідного сигналу дають різні результати на виході (наприклад, тотожне перетворення та біта інверсія), а якщо вихідне значення не змінюється незалежно від вхідного значення, то функція є постійною (наприклад, обчислення константи "1" або обчислення константи "0").
Використовуючи квантовий алгоритм, ви зможете визначити, чи є функція в чорній скриньці постійною або змінною на підставі лише одного запиту. Але перш ніж докладно розглядати, як це зробити, нам потрібно знайти спосіб, що дозволить структурувати кожну з таких функцій на квантовому комп'ютері. Оскільки будь-які квантові оператори мають бути оборотними, ми одразу стикаємося з проблемою: функції обчислення констант «1» та «0» такими не є.
У квантових обчисленнях часто використовується таке рішення: додається додатковий вихідний кубит, який повертає будь-яке значення вхідного сигналу, отримане функцією.
| до: | після: |
|
|
|
Таким чином, ми можемо визначати вхідні значення виключно на підставі значення, що отримується на виході, а функція стає оборотною. Структура квантових ланцюгів створює потребу у додатковому вхідному биті. Для розробки відповідних операторів приймемо, що додатковий вхідний кубит встановлено |0⟩.
Застосувавши те ж уявлення квантової ланцюга, що ми використовували раніше, подивимося, як можна реалізувати кожен із чотирьох елементів (тотожне перетворення, заперечення, обчислення константи «0» і обчислення константи «1») з допомогою квантових операторів.
Наприклад, можна реалізувати функцію обчислення константи «0»:
Обчислення константи «0»:
Тут нам взагалі не потрібні оператори. Перший вхідний кубит (який ми прийняли рівним |0⟩) повертається з тим самим значенням, а друге вхідне значення повертає саме себе — як завжди.
З функцією обчислення константи «1» ситуація трохи інакша:
Обчислення константи «1»:
Оскільки ми прийняли, що перший вхідний кубит завжди встановлено |0⟩, в результаті застосування оператора біта інверсії він завжди дає на виході одиницю. І як завжди, другий кубит дає на виході своє ж значення.
Під час відображення оператора тотожного перетворення завдання починає ускладнюватись. Ось як це можна зробити:
Тотожне перетворення:
Використаний символ означає елемент CNOT: верхня лінія позначає контрольний біт, а нижня — керуючий. Нагадаю, що з використанні оператора CNOT значення контрольного біта змінюється, якщо керуючий біт дорівнює |1⟩, але залишається незмінним, якщо керуючий біт дорівнює |0⟩. Оскільки ми прийняли, що значення верхньої лінії завжди дорівнює |0⟩, її значення завжди присвоюється нижньої лінії.
Аналогічним чином діємо з оператором заперечення:
Заперечення:
Ми просто інвертуємо біт наприкінці вихідної лінії.
Тепер, коли ми розібралися з попереднім поданням, розглянемо конкретні переваги квантової обчислювальної машини перед традиційним комп'ютером, якщо йдеться про визначення константності або змінності функції, прихованої в чорній скриньці, з використанням лише одного запиту.
Для вирішення цього завдання за допомогою квантових обчислень за один запит необхідно перевести вхідні кубити в суперпозицію до передачі функції, як показано нижче:
Елемент Адамара повторно застосовується до результату використання функції, щоб вивести кубити із суперпозиції та зробити алгоритм детермінованим. Ми запускаємо систему може |00⟩ і з причин, про які я зараз розповім, отримуємо результат |11⟩, якщо функція є постійною. Якщо ж функція всередині чорного ящика змінна, після вимірювання система повертає результат |01⟩.
Щоб розібратися з рештою статті, звернімося до ілюстрації, яку я вже показував раніше:
Використовуючи оператор інверсії біта, а потім застосувавши елемент Адамара до обох вхідних значень, рівних |0⟩, ми забезпечимо їх переведення в однакову суперпозицію |0⟩ та |1⟩, а саме:
На прикладі передачі значення функції у чорному ящику легко продемонструвати, що обидві функції постійного значення дають на виході |11⟩.
Обчислення константи «0»:
Аналогічно, бачимо, що функція обчислення константи «1» також на виході |11⟩, тобто:
Обчислення константи «1»:
Зверніть увагу: на виході обидва значення дорівнюють |1⟩, оскільки -1² = 1.
За тим же принципом можна довести, що при використанні обох змінних функцій ми завжди отримуватимемо на виході |01⟩ (за умови використання однакового методу), хоча тут дещо складніше.
Тотожне перетворення:
Оскільки CNOT є двокубітним оператором, його не можна представити у вигляді простої машини станів, і тому необхідно визначити два вихідні сигнали на підставі тензорного твору обох вхідних кубітів та множення на матрицю CNOT за описаним раніше принципом:
За допомогою цього методу ми можемо також підтвердити отримання на виході значення |01⟩, якщо в чорній скриньці прихована функція заперечення:
Заперечення:
Таким чином, ми щойно продемонстрували ситуацію, в якій квантовий комп'ютер однозначно ефективніший, ніж звичайна обчислювальна машина.
Що ж далі?
Пропоную на цьому закінчити. Ми й так чудово попрацювали. Якщо ви зрозуміли все, про що я розповів, думаю, тепер ви непогано знаєтеся на основах квантових обчислень і квантової логіки, а також розумієте, чому в певних ситуаціях квантові алгоритми можуть виявитися ефективнішими за традиційні засоби обчислення.
Мій опис складно назвати повноцінним посібником з квантових обчислень та алгоритмів — це, швидше, коротке введення в математику і систему позначень, покликане розвіяти у читачів уявлення про предмет, що нав'язуються науково-популярними джерелами (серйозно, багато хто дійсно не може розібратися в ситуації!). Я не встиг торкнутися багатьох важливих тем — наприклад, таких як , комплексність значень амплітуди |0⟩ та |1⟩ та функціонування різних квантових логічних елементів при трансформації сферою Блоха.
Якщо ви хочете систематизувати та структурувати свої знання про квантові комп'ютери, наполегливо рекомендую вам прочитати Емми Штрубель: незважаючи на велику кількість математичних формул, у цій книзі квантові алгоритми розглядаються куди більш докладно.
Джерело: habr.com