Кріс Бернгардт. Квантові обчислення для всіх
Додано: Пон лютого 07, 2022 3:59 pm
Chris Bernhardt. Quantum Computing for Everyone. The MIT Press; Illustrated edition, 2019, 216 pages.
Відгуки
"Квантові обчислення для всіх – це дуже необхідна доза реальності та прямий шлях для серйозного новачка". ― «Нейче»
«Чи буде колись біт замінений кубітом? Квантові комп’ютери якраз вимальовуються на технічному горизонті. Цей важливий текст відчиняє двері для технічних читачів, щоб ті пройшли через галерею квантових ефектів, які ведуть до основ квантових обчислень». ― Ківейтін А. Дюдні, професор комп’ютерних наук Університету Західного Онтаріо
«Нещодавно в медіях зчинився страшенний галас із приводу майбутньої революції у квантових обчисленнях. Кріс Бернгардт майстерно створив цю коротку книжку, щоб навчити основ усіх, хто цікавиться цією захопливою сферою діяльності. Не очікується, що читач знатиме більше, ніж математику середньої школи, і водночас ця надзвичайно доступна книжка проведе вас через багато частин квантових обчислень». Носон С. Янофскі, професор Бруклінського коледжу, факультету комп'ютерних та інформаційних наук; співавтор книжки «Квантові обчислення для комп’ютерних науковців» і автор книжки «Зовнішні межі розуму».
Про автора
Кріс Бернгардт – професор математики Ферфілдського університету і автор «Тюрингового бачення: народження комп’ютерної науки» (MIT прес).
Доступний вступ до захопливої нової галузі обчислень, що пояснює такі теми, як кубіти, заплутаність і квантову телепортацію для широкого кола читачів.
Квантові обчислення — це прекрасне поєднання квантової фізики та комп’ютерної науки, що вбудовує деякі з найприголомшливіших ідей із фізики двадцятого століття в абсолютно новий спосіб мислення про обчислення. У цій книжці Кріс Бернгардт пропонує вступ до квантових обчислень, який доступний кожному, хто добре володіє математикою середньої школи. Він якомога зрозуміло для широкого кола читачів пояснює кубіти, заплутаність, квантову телепортацію, квантові алгоритми та інші пов’язані з квантами теми. Бернгардт, сам математик, максимально спрощує математику і наводить елементарні приклади, що ілюструють і як працює математика, і що вона означає.
Бернгардт вводить основну одиницю квантових обчислень, кубіт, і пояснює, як можна виміряти кубіт; обговорює заплутаність — яку, за його словами, легше описати математично, ніж словесно — і що це означає, коли заплутані два кубіти (цитуючи характеристику Айнштайна того, що відбувається, коли вимірювання одного заплутаного кубіта впливає на другий, як «жахливу дію на відстані»); і вводить квантову криптографію. Він підсумовує стандартні теми класичних обчислень — біти, вентилі та логіку — і описує геніальний комп’ютер Едварда Фредкіна з використанням більярдних куль. Він означує квантові вентилі, розглядає швидкість квантових алгоритмів і описує побудову квантових комп’ютерів. До кінця книжки читачі зрозуміють, що квантові обчислення та класичні обчислення не дві різні дисципліни, і що квантові обчислення – основна форма обчислень. Основна одиниця обчислення – кубіт, а не біт.
ЗМІСТ
Подяки
Вступ
1. Спін
Квантовий годинник
Вимірювання в одному напряму
Вимірювання в різних напрямах
Вимірювання
Випадковість
Фотони та поляризація
Висновки
2. Лінійна алгебра
Комплексні числа проти дійсних
Вектори
Діаграми векторів
Довжини векторів
Скалярне множення
Додавання векторів
Ортогональні вектори
Множення бра на кет
Бра-кети та довжини
Бра-кети та ортогональність
Ортонормальні базиси
Вектори як лінійні комбінації базисних векторів
Впорядковані базиси
Довжина вектора
Матриці
Матричні обчислення
Ортогональні та унітарні матриці
Інструментарій лінійної алгебри
3. Спін і кубіти
Ймовірність
Математика квантового спіну
Вектори еквівалентного стану
Базис, пов’язаний із заданим напрямом спіну
Обертання пристрою на 60°
Математична модель поляризації фотонів
Базис, пов'язаний із заданим напрямом поляризації
Експерименти з поляризованими фільтрами
Кубіти
Аліс, Боб та Ів
Амплітуди ймовірності та інтерференція
Аліс, Боб, Ів і протокол BB84
4. Заплутування
Кубіти Аліс та Боба не заплутані
Розрахунок незаплутаних кубітів
Розрахунок заплутаних кубітів
Надсвітлова комунікація
Стандартний базис для тензорних добутків
Як заплутати кубіти?
Використання CNOT-вентилів для заплутування кубітів
Заплутані квантові годинники
5. Белова нерівність
Заплутані кубіти в різних базисах
Доведення, що <…> рівне <…>
Айнштайн і локальний реалізм
Айнштайн і приховані змінні
Класичне пояснення заплутування
Белова нерівність
Відповідь квантової механіки
Класична відповідь
Вимірювання
Протокол Екерта для розподілу квантових ключів
6. Класична логіка, вентилі та схеми
Логіка
Булова алгебра
Функціональна повнота
Вентилі
Схеми
NAND – це універсальні вентилі
Вентилі та обчислення
Пам'ять
Оборотні обчислення
Обчислення з використанням більярдних куль
7. Квантові вентилі та схеми
Кубіти
CNOT-вентилі
Квантові вентилі
Квантові вентилі, що діють на один кубіт
Чи існують універсальні квантові вентилі?
Теорема про заборону клонування
Квантові обчислення проти класичних
Белова схема
Надщільне кодування
Квантова телепортація
Виправляння помилок
8. Квантові алгоритми
Класи складності P і NP
Чи швидші квантові алгоритми за класичні?
Складність запиту
Дойчів алгоритм
Кронекерів добуток Адамарових матриць
Алгоритм Дойча – Йожи
Саймонів алгоритм
Класи складності
Квантові алгоритми
9. Вплив квантових обчислень
Шорів алгоритм і криптоаналіз
Ґроверів алгоритм і пошук даних
Хемія та моделювання
Обладнання
Квантова перевага та паралельні всесвіти
Розрахунок
Індекс
Подяки
Я дуже вдячний багатьом людям за допомогу з книжкою. Мет Коулмен, Стів Лемей, Ден Раян, Кріс Стекер і троє анонімних рецензентів дуже уважно прочитали різні чернетки. Їхні пропозиції і виправлення надзвичайно покращили книжку. Я також дякую Марі Лі та її команді з «MIT прес» за всю підтримку та роботу, що перетворили попередній проєкт у цю книжку.
Вступ
Мета цієї книжки — дати вступ до квантових обчислень, який може зрозуміти кожен, хто добре володіє математикою середньої школи і готовий трішки попрацювати. Ми будемо вивчати кубіти, заплутаність, квантову телепортацію та квантові алгоритми, серед інших тем, пов’язаних із квантами. Мета полягає не в тому, щоб дати якесь туманне уявлення про ці поняття, а в тому, щоб зробити їх кришталево ясними.
Квантові обчислення часто з’являються в новинах: Китай телепортував кубіт із Землі на супутник; Шорів алгоритм поставив під загрозу наші поточні методи шифрування; квантовий розподіл ключів знову зробить шифрування безпечним; Ґроверів алгоритм пришвидшить пошук даних. Але що насправді все це означає? Як це все працює? Все це буде пояснене.
Чи можна це зробити без використання математики? Ні, ні, якщо ми хочемо дійсно зрозуміти, що відбувається. Основні ідеї походять із квантової механіки і часто суперечать здоровому глуздові. Спроби описати це словами не працюють, тому що ми не маємо жодного досвіду їх у нашому повсякденному житті. Що ще гірше, словесні описи часто створюють враження, що ми щось зрозуміли, а насправді ні. Хороша новина полягає в тому, що нам дійсно не потрібно вводити багато математики. Моя роль як математика полягає в тому, щоб максимально спростити математику — просто дотримуючись абсолютних основ — і навести елементарні приклади, щоб проілюструвати як вона використовується і що означає. Проте книжка, можливо, містить математичні ідеї, яких ви раніше не бачили, і, як загалом з усією математикою, нові поняття спочатку можуть здатися дивними. Важливо не проскакувати приклади, а уважно їх читати, проходячи кожен етап обчислень.
Квантове обчислення — це прекрасне поєднання квантової фізики з комп’ютерною наукою. Воно вводить деякі з найприголомшливіших ідей фізики ХХ століття в абсолютно новий спосіб мислення про обчислення. Основна одиниця квантових обчислень – кубіт. Ми побачимо, що таке кубіти і що стається, коли ми їх вимірюємо. Класичний біт — це або 0, або 1. Якщо він дорівнює 0 і ми його вимірюємо, ми отримуємо 0. Якщо це 1, і ми вимірюємо 1, ми отримуємо 1. В обох випадках біт залишається незмінним. З кубітами ситуація зовсім інакша. Кубіт може перебувати в одному з нескінченної кількості станів — суперпозиція як 0, так і 1 — але коли ми виміряємо його, як у класичному випадку, ми просто отримуємо одне з двох значень, 0 або 1. Акт вимірювання змінює кубіт. Проста математична модель точно все це описує.
Кубіти також можуть бути заплутаними. Коли ми проводимо вимірювання одного з них, це впливає на стан іншого. Знову ж таки, це те, чого ми не відчуваємо в повсякденному житті, але це чудово описується нашою математичною моделлю.
Ці три речі — суперпозиція, вимірювання та заплутаність — ключові ідеї квантової механіки. Коли ми дізнаємося, що вони означають, то зможемо побачити, як їх можна використовувати в обчисленнях. Саме тут проявляється людська винахідливість.
Математики часто описують доведення як красиві, що часто містять несподівані ідеї. Я точно так само ставлюся до багатьох тем, які ми розглядатимемо. Белова теорема, квантова телепортація, надщільне кодування — все це перлини. Схема виправляння помилок і Ґроверів алгоритм абсолютно дивовижні.
До кінця книжки ви повинні зрозуміти основні ідеї, які лежать в основі квантових обчислень, і побачите кілька геніальних і красивих конструкцій. Ви також зрозумієте, що квантові обчислення та класичні обчислення не дві різні дисципліни, а що квантові обчислення – фундаментальніша форма обчислень — все, що можна обчислити класично, можна обчислити на квантовому комп’ютері. Кубіт – основна одиниця обчислення, а не біт. Обчислення, по своїй суті, насправді означає квантові обчислення.
Нарешті, слід підкреслити, що ця книжка присвячена теорії квантових обчислень. Йдеться про програмне забезпечення, а не про апаратне. Ми коротко згадуємо апаратне забезпечення місцями і час від часу говоримо про те, як фізично заплутати кубіти, але ці теми лише відступи. Книжка не про те, як побудувати квантовий комп’ютер, а про те, як ним користуватися. Ось короткий опис її змісту.
Розділ 1. Основна одиниця класичних обчислень – біт. Біти можуть бути представлені будь-чим, що може перебувати в одному з двох можливих станів. Стандартний приклад – електричний вимикач, який може бути увімкненим або вимкненим. Основна одиниця квантових обчислень – кубіт. Він може бути представлений спіном електрона або поляризацією фотона, але властивості спіну і поляризації нам не такі знайомі, як перемикач у положенні увімкненого або вимкненого.
Ми розглянемо основні властивості спіну, починаючи з класичного експерименту Ото Штерна та Вальтера Ґерлаха, в якому вони вивчали магнетні властивості атомів срібла. Ми побачимо, що відбувається, коли ми вимірюємо спін у кількох різних напрямах. Вимірювання може вплинути на стан кубіта. З деякими вимірюваннями також пов’язана випадковість, що лежить в основі і яку нам потрібно буде пояснити.
Розділ закінчується показом того, що експерименти, аналогічні до експериментів зі спіном, можна проводити за допомогою поляризованих фільтрів і звичайного світла.
Розділ 2. Квантові обчислення засновані на галузі математики, яка називається лінійною алгеброю. На щастя, нам потрібно лише кілька понять. У цьому розділі представлена та описується потрібна нам лінійна алгебра, а також ілюструється, як вона буде використовуватися в дальших розділах.
Ми вводимо вектори та матриці й показуємо, як обчислити довжину векторів і як визначити, чи два вектори перпендикулярні. Розділ починається з простого розгляду елементарних операцій над векторами, а потім показується, як матриці дають простий спосіб виконати кілька цих обчислень одночасно.
Спочатку не очевидно, що цей матеріал буде корисний, але це так. Лінійна алгебра становить основу квантових обчислень. Через те що в решті книжки використовується математика, представлена тут, цей розділ необхідно прочитати уважно.
Розділ 3. У цьому розділі показано, як пов'язані попередні два розділи. Математична модель спіну або, що еквівалентно, поляризації дається за допомогою лінійної алгебри. Це дає змогу нам означити кубіт і точно описати, що відбувається, коли ми його вимірюємо.
Наведено кілька прикладів вимірювання кубітів у різних напрямах. Розділ закінчується вступом до квантової криптографії, описанням протоколу BB84.
Розділ 4. У цьому розділі описано, що означає переплутування двох кубітів. Заплутаність важко описати словами, але легко – математично. Нова математична ідея — тензорний добуток. Це найпростіший спосіб поєднання математичних моделей окремих кубітів, щоб отримати одну модель, яка описує набір кубітів.
Хоча математика проста, заплутаність — це не те, що ми відчуваємо в повсякденному житті. Коли вимірюється один із пари заплутаних кубітів, це впливає на другий кубіт. Це те, що Альберт Айнштайн, якому таке не сподобалося, назвав «жахливою дією на відстані». Розглянемо кілька прикладів.
Розділ закінчується показом того, що ми не можемо використовувати заплутаність, щоб комунікувати швидше за швидкість світла.
Розділ 5. Ми розглянемо занепокоєння Айнштайна з приводу заплутаності й чи може теорія прихованих змінних зберегти локальний реалізм. Ми розглянемо математику Белової нерівності — чудовий результат, який дає експериментальний спосіб визначити, чи слушний аргумент Айнштайна. Як відомо більшості людей, погляд Айнштайна був хибний, але навіть Бел думав, що він буде правильний.
Артур Екерт зрозумів, що налаштування для перевірки Белової нерівності також можна використовувати як для створення безпечного ключа, що буде використовуватися для криптографії, так і для перевірки наявності підслуховувачів. Завершується розділ описом цього криптографічного протоколу.
Розділ 6. Розділ починається зі стандартних тем в обчисленні: бітів, вентилів та логіки. Потім ми коротко розглянемо оборотні обчислення та ідеї Еда Фредкіна. Ми показуємо, що і вентилі Фредкіна, і вентилі Тофолі універсальні — ви можете створити закінчений комп’ютер, використовуючи лише вентилі Фредкіна (або вентилі Тофолі). Розділ завершується комп’ютером Фредкіна з використанням більярдних куль. Це насправді не потрібно для решти нашої історії, але його абсолютна оригінальність вимагає, щоб його розглянути.
Цей комп’ютер складається з куль, які стикаються одна з одною та різними стінками. Він створює образи частинок, які взаємодіють. Це одна з ідей, яка надихнула Річарда Файнмена зацікавитися ідеєю квантових обчислень. Файнмен написав деякі з найперших робіт на цю тему.
Розділ 7. У цьому розділі починається вивчення квантових обчислень за допомогою квантових схем. Означено квантові вентилі. Ми бачимо, як квантові вентилі діють на кубіт, і розуміємо, що ми розглядали ці ідеї весь час. Нам просто потрібно змінити нашу перспективу. Ми більше не думаємо про ортогональну матрицю, як вона діє на наш вимірювальний пристрій, а як діє на кубіт. Ми також довели деякі дивовижні результати щодо надщільного кодування, квантової телепортації, клонування та виправляння помилок.
Розділ 8. Це, мабуть, найскладніший розділ. У ньому ми розглянемо деякі квантові алгоритми і покажемо, як швидко вони можуть обчислити відповідь, якщо порівняти з класичними алгоритмами. Щоб говорити про швидкість роботи алгоритмів, нам потрібно ввести різні ідеї з теорії складності. Після того, як ми означили те, що називається складністю запиту, ми вивчаємо три квантові алгоритми і показуємо, що вони швидші стосовно цього типу складності, ніж їхні класичні аналоги.
Квантові алгоритми використовують структуру, що лежить в основі, розв’язуваної проблеми. Це набагато більше, ніж просто ідея квантового паралелізму — поміщення входових даних у суперпозицію всіх можливих станів. У цьому розділі представлено останню частину математичної техніки, Кронекерів добуток матриць. Але складність матеріалу насправді пов’язана з тим, що ми обчислюємо абсолютно по-новому і не маємо досвіду розв’язання задач із використанням цих нових ідей.
Розділ 9. Останній розділ розглядає вплив квантових обчислень на наше життя. Почнемо з короткого опису двох важливих алгоритмів, один винайшов Пітер Шор, інший — Лов Ґровер.
Шорів алгоритм дає спосіб розкласти велике число на добуток простих множників. Це може здатися не таким важливим, але наша безпека в інтернеті залежить від того, що цю задачу розв’язати. Можливість розкладати на множники добутки великих простих чисел загрожує нашим поточним методам захисту транзакцій між комп’ютерами. Можливо, пройде якийсь час, поки ми не отримаємо квантові комп’ютери, достатньо потужні, щоб розкласти на множники великі числа, які тепер використовуються, але загроза реальна, і вона вже змушує нас думати про те, як перепроєктувати способи, за допомогою яких комп’ютери можуть безпечно спілкуватися один з одним.
Ґроверів алгоритм призначений для спеціальних типів пошуку даних. Ми показуємо, як він працює для невеликого випадку, і вказуємо, як він працює загалом. І Ґроверів алгоритм, і Шорів важливі не тільки для проблем, які вони подужують, але й для нових ідей, які вони вносять. Ці основні ідеї впроваджувалися і впроваджуються в нове покоління алгоритмів.
Переглянувши алгоритми, ми змінюємо тему і коротко розглянемо, як квантові обчислення можна використовувати для моделювання квантових процесів. Хемія на найбазовішому рівні – квантова механіка. Класична обчислювальна хемія працює, беручи квантово-механічні рівняння і моделюючи їх за допомогою класичних комп’ютерів. Ці моделювання наближені й ігнорують дрібні деталі. Це добре працює в багатьох випадках, але деколи ні. І от тоді вам потрібні дрібні деталі, а квантові комп’ютери повинні мати можливість їх надати.
У цьому розділі також коротко розглядається створення реальних машин. Це галузь, яка дуже швидко розвивається. Перші машини виставляються на продаж. У хмарі є навіть одна машина, якою кожен може користуватися безплатно. Схоже, ми скоро вступимо в епоху квантової переваги. (Ми пояснюємо, що це означає.)
Книжка закінчується усвідомленням того, що квантові обчислення не новий тип обчислень, а відкриття справжньої природи обчислень.
Відгуки
"Квантові обчислення для всіх – це дуже необхідна доза реальності та прямий шлях для серйозного новачка". ― «Нейче»
«Чи буде колись біт замінений кубітом? Квантові комп’ютери якраз вимальовуються на технічному горизонті. Цей важливий текст відчиняє двері для технічних читачів, щоб ті пройшли через галерею квантових ефектів, які ведуть до основ квантових обчислень». ― Ківейтін А. Дюдні, професор комп’ютерних наук Університету Західного Онтаріо
«Нещодавно в медіях зчинився страшенний галас із приводу майбутньої революції у квантових обчисленнях. Кріс Бернгардт майстерно створив цю коротку книжку, щоб навчити основ усіх, хто цікавиться цією захопливою сферою діяльності. Не очікується, що читач знатиме більше, ніж математику середньої школи, і водночас ця надзвичайно доступна книжка проведе вас через багато частин квантових обчислень». Носон С. Янофскі, професор Бруклінського коледжу, факультету комп'ютерних та інформаційних наук; співавтор книжки «Квантові обчислення для комп’ютерних науковців» і автор книжки «Зовнішні межі розуму».
Про автора
Кріс Бернгардт – професор математики Ферфілдського університету і автор «Тюрингового бачення: народження комп’ютерної науки» (MIT прес).
Доступний вступ до захопливої нової галузі обчислень, що пояснює такі теми, як кубіти, заплутаність і квантову телепортацію для широкого кола читачів.
Квантові обчислення — це прекрасне поєднання квантової фізики та комп’ютерної науки, що вбудовує деякі з найприголомшливіших ідей із фізики двадцятого століття в абсолютно новий спосіб мислення про обчислення. У цій книжці Кріс Бернгардт пропонує вступ до квантових обчислень, який доступний кожному, хто добре володіє математикою середньої школи. Він якомога зрозуміло для широкого кола читачів пояснює кубіти, заплутаність, квантову телепортацію, квантові алгоритми та інші пов’язані з квантами теми. Бернгардт, сам математик, максимально спрощує математику і наводить елементарні приклади, що ілюструють і як працює математика, і що вона означає.
Бернгардт вводить основну одиницю квантових обчислень, кубіт, і пояснює, як можна виміряти кубіт; обговорює заплутаність — яку, за його словами, легше описати математично, ніж словесно — і що це означає, коли заплутані два кубіти (цитуючи характеристику Айнштайна того, що відбувається, коли вимірювання одного заплутаного кубіта впливає на другий, як «жахливу дію на відстані»); і вводить квантову криптографію. Він підсумовує стандартні теми класичних обчислень — біти, вентилі та логіку — і описує геніальний комп’ютер Едварда Фредкіна з використанням більярдних куль. Він означує квантові вентилі, розглядає швидкість квантових алгоритмів і описує побудову квантових комп’ютерів. До кінця книжки читачі зрозуміють, що квантові обчислення та класичні обчислення не дві різні дисципліни, і що квантові обчислення – основна форма обчислень. Основна одиниця обчислення – кубіт, а не біт.
ЗМІСТ
Подяки
Вступ
1. Спін
Квантовий годинник
Вимірювання в одному напряму
Вимірювання в різних напрямах
Вимірювання
Випадковість
Фотони та поляризація
Висновки
2. Лінійна алгебра
Комплексні числа проти дійсних
Вектори
Діаграми векторів
Довжини векторів
Скалярне множення
Додавання векторів
Ортогональні вектори
Множення бра на кет
Бра-кети та довжини
Бра-кети та ортогональність
Ортонормальні базиси
Вектори як лінійні комбінації базисних векторів
Впорядковані базиси
Довжина вектора
Матриці
Матричні обчислення
Ортогональні та унітарні матриці
Інструментарій лінійної алгебри
3. Спін і кубіти
Ймовірність
Математика квантового спіну
Вектори еквівалентного стану
Базис, пов’язаний із заданим напрямом спіну
Обертання пристрою на 60°
Математична модель поляризації фотонів
Базис, пов'язаний із заданим напрямом поляризації
Експерименти з поляризованими фільтрами
Кубіти
Аліс, Боб та Ів
Амплітуди ймовірності та інтерференція
Аліс, Боб, Ів і протокол BB84
4. Заплутування
Кубіти Аліс та Боба не заплутані
Розрахунок незаплутаних кубітів
Розрахунок заплутаних кубітів
Надсвітлова комунікація
Стандартний базис для тензорних добутків
Як заплутати кубіти?
Використання CNOT-вентилів для заплутування кубітів
Заплутані квантові годинники
5. Белова нерівність
Заплутані кубіти в різних базисах
Доведення, що <…> рівне <…>
Айнштайн і локальний реалізм
Айнштайн і приховані змінні
Класичне пояснення заплутування
Белова нерівність
Відповідь квантової механіки
Класична відповідь
Вимірювання
Протокол Екерта для розподілу квантових ключів
6. Класична логіка, вентилі та схеми
Логіка
Булова алгебра
Функціональна повнота
Вентилі
Схеми
NAND – це універсальні вентилі
Вентилі та обчислення
Пам'ять
Оборотні обчислення
Обчислення з використанням більярдних куль
7. Квантові вентилі та схеми
Кубіти
CNOT-вентилі
Квантові вентилі
Квантові вентилі, що діють на один кубіт
Чи існують універсальні квантові вентилі?
Теорема про заборону клонування
Квантові обчислення проти класичних
Белова схема
Надщільне кодування
Квантова телепортація
Виправляння помилок
8. Квантові алгоритми
Класи складності P і NP
Чи швидші квантові алгоритми за класичні?
Складність запиту
Дойчів алгоритм
Кронекерів добуток Адамарових матриць
Алгоритм Дойча – Йожи
Саймонів алгоритм
Класи складності
Квантові алгоритми
9. Вплив квантових обчислень
Шорів алгоритм і криптоаналіз
Ґроверів алгоритм і пошук даних
Хемія та моделювання
Обладнання
Квантова перевага та паралельні всесвіти
Розрахунок
Індекс
Подяки
Я дуже вдячний багатьом людям за допомогу з книжкою. Мет Коулмен, Стів Лемей, Ден Раян, Кріс Стекер і троє анонімних рецензентів дуже уважно прочитали різні чернетки. Їхні пропозиції і виправлення надзвичайно покращили книжку. Я також дякую Марі Лі та її команді з «MIT прес» за всю підтримку та роботу, що перетворили попередній проєкт у цю книжку.
Вступ
Мета цієї книжки — дати вступ до квантових обчислень, який може зрозуміти кожен, хто добре володіє математикою середньої школи і готовий трішки попрацювати. Ми будемо вивчати кубіти, заплутаність, квантову телепортацію та квантові алгоритми, серед інших тем, пов’язаних із квантами. Мета полягає не в тому, щоб дати якесь туманне уявлення про ці поняття, а в тому, щоб зробити їх кришталево ясними.
Квантові обчислення часто з’являються в новинах: Китай телепортував кубіт із Землі на супутник; Шорів алгоритм поставив під загрозу наші поточні методи шифрування; квантовий розподіл ключів знову зробить шифрування безпечним; Ґроверів алгоритм пришвидшить пошук даних. Але що насправді все це означає? Як це все працює? Все це буде пояснене.
Чи можна це зробити без використання математики? Ні, ні, якщо ми хочемо дійсно зрозуміти, що відбувається. Основні ідеї походять із квантової механіки і часто суперечать здоровому глуздові. Спроби описати це словами не працюють, тому що ми не маємо жодного досвіду їх у нашому повсякденному житті. Що ще гірше, словесні описи часто створюють враження, що ми щось зрозуміли, а насправді ні. Хороша новина полягає в тому, що нам дійсно не потрібно вводити багато математики. Моя роль як математика полягає в тому, щоб максимально спростити математику — просто дотримуючись абсолютних основ — і навести елементарні приклади, щоб проілюструвати як вона використовується і що означає. Проте книжка, можливо, містить математичні ідеї, яких ви раніше не бачили, і, як загалом з усією математикою, нові поняття спочатку можуть здатися дивними. Важливо не проскакувати приклади, а уважно їх читати, проходячи кожен етап обчислень.
Квантове обчислення — це прекрасне поєднання квантової фізики з комп’ютерною наукою. Воно вводить деякі з найприголомшливіших ідей фізики ХХ століття в абсолютно новий спосіб мислення про обчислення. Основна одиниця квантових обчислень – кубіт. Ми побачимо, що таке кубіти і що стається, коли ми їх вимірюємо. Класичний біт — це або 0, або 1. Якщо він дорівнює 0 і ми його вимірюємо, ми отримуємо 0. Якщо це 1, і ми вимірюємо 1, ми отримуємо 1. В обох випадках біт залишається незмінним. З кубітами ситуація зовсім інакша. Кубіт може перебувати в одному з нескінченної кількості станів — суперпозиція як 0, так і 1 — але коли ми виміряємо його, як у класичному випадку, ми просто отримуємо одне з двох значень, 0 або 1. Акт вимірювання змінює кубіт. Проста математична модель точно все це описує.
Кубіти також можуть бути заплутаними. Коли ми проводимо вимірювання одного з них, це впливає на стан іншого. Знову ж таки, це те, чого ми не відчуваємо в повсякденному житті, але це чудово описується нашою математичною моделлю.
Ці три речі — суперпозиція, вимірювання та заплутаність — ключові ідеї квантової механіки. Коли ми дізнаємося, що вони означають, то зможемо побачити, як їх можна використовувати в обчисленнях. Саме тут проявляється людська винахідливість.
Математики часто описують доведення як красиві, що часто містять несподівані ідеї. Я точно так само ставлюся до багатьох тем, які ми розглядатимемо. Белова теорема, квантова телепортація, надщільне кодування — все це перлини. Схема виправляння помилок і Ґроверів алгоритм абсолютно дивовижні.
До кінця книжки ви повинні зрозуміти основні ідеї, які лежать в основі квантових обчислень, і побачите кілька геніальних і красивих конструкцій. Ви також зрозумієте, що квантові обчислення та класичні обчислення не дві різні дисципліни, а що квантові обчислення – фундаментальніша форма обчислень — все, що можна обчислити класично, можна обчислити на квантовому комп’ютері. Кубіт – основна одиниця обчислення, а не біт. Обчислення, по своїй суті, насправді означає квантові обчислення.
Нарешті, слід підкреслити, що ця книжка присвячена теорії квантових обчислень. Йдеться про програмне забезпечення, а не про апаратне. Ми коротко згадуємо апаратне забезпечення місцями і час від часу говоримо про те, як фізично заплутати кубіти, але ці теми лише відступи. Книжка не про те, як побудувати квантовий комп’ютер, а про те, як ним користуватися. Ось короткий опис її змісту.
Розділ 1. Основна одиниця класичних обчислень – біт. Біти можуть бути представлені будь-чим, що може перебувати в одному з двох можливих станів. Стандартний приклад – електричний вимикач, який може бути увімкненим або вимкненим. Основна одиниця квантових обчислень – кубіт. Він може бути представлений спіном електрона або поляризацією фотона, але властивості спіну і поляризації нам не такі знайомі, як перемикач у положенні увімкненого або вимкненого.
Ми розглянемо основні властивості спіну, починаючи з класичного експерименту Ото Штерна та Вальтера Ґерлаха, в якому вони вивчали магнетні властивості атомів срібла. Ми побачимо, що відбувається, коли ми вимірюємо спін у кількох різних напрямах. Вимірювання може вплинути на стан кубіта. З деякими вимірюваннями також пов’язана випадковість, що лежить в основі і яку нам потрібно буде пояснити.
Розділ закінчується показом того, що експерименти, аналогічні до експериментів зі спіном, можна проводити за допомогою поляризованих фільтрів і звичайного світла.
Розділ 2. Квантові обчислення засновані на галузі математики, яка називається лінійною алгеброю. На щастя, нам потрібно лише кілька понять. У цьому розділі представлена та описується потрібна нам лінійна алгебра, а також ілюструється, як вона буде використовуватися в дальших розділах.
Ми вводимо вектори та матриці й показуємо, як обчислити довжину векторів і як визначити, чи два вектори перпендикулярні. Розділ починається з простого розгляду елементарних операцій над векторами, а потім показується, як матриці дають простий спосіб виконати кілька цих обчислень одночасно.
Спочатку не очевидно, що цей матеріал буде корисний, але це так. Лінійна алгебра становить основу квантових обчислень. Через те що в решті книжки використовується математика, представлена тут, цей розділ необхідно прочитати уважно.
Розділ 3. У цьому розділі показано, як пов'язані попередні два розділи. Математична модель спіну або, що еквівалентно, поляризації дається за допомогою лінійної алгебри. Це дає змогу нам означити кубіт і точно описати, що відбувається, коли ми його вимірюємо.
Наведено кілька прикладів вимірювання кубітів у різних напрямах. Розділ закінчується вступом до квантової криптографії, описанням протоколу BB84.
Розділ 4. У цьому розділі описано, що означає переплутування двох кубітів. Заплутаність важко описати словами, але легко – математично. Нова математична ідея — тензорний добуток. Це найпростіший спосіб поєднання математичних моделей окремих кубітів, щоб отримати одну модель, яка описує набір кубітів.
Хоча математика проста, заплутаність — це не те, що ми відчуваємо в повсякденному житті. Коли вимірюється один із пари заплутаних кубітів, це впливає на другий кубіт. Це те, що Альберт Айнштайн, якому таке не сподобалося, назвав «жахливою дією на відстані». Розглянемо кілька прикладів.
Розділ закінчується показом того, що ми не можемо використовувати заплутаність, щоб комунікувати швидше за швидкість світла.
Розділ 5. Ми розглянемо занепокоєння Айнштайна з приводу заплутаності й чи може теорія прихованих змінних зберегти локальний реалізм. Ми розглянемо математику Белової нерівності — чудовий результат, який дає експериментальний спосіб визначити, чи слушний аргумент Айнштайна. Як відомо більшості людей, погляд Айнштайна був хибний, але навіть Бел думав, що він буде правильний.
Артур Екерт зрозумів, що налаштування для перевірки Белової нерівності також можна використовувати як для створення безпечного ключа, що буде використовуватися для криптографії, так і для перевірки наявності підслуховувачів. Завершується розділ описом цього криптографічного протоколу.
Розділ 6. Розділ починається зі стандартних тем в обчисленні: бітів, вентилів та логіки. Потім ми коротко розглянемо оборотні обчислення та ідеї Еда Фредкіна. Ми показуємо, що і вентилі Фредкіна, і вентилі Тофолі універсальні — ви можете створити закінчений комп’ютер, використовуючи лише вентилі Фредкіна (або вентилі Тофолі). Розділ завершується комп’ютером Фредкіна з використанням більярдних куль. Це насправді не потрібно для решти нашої історії, але його абсолютна оригінальність вимагає, щоб його розглянути.
Цей комп’ютер складається з куль, які стикаються одна з одною та різними стінками. Він створює образи частинок, які взаємодіють. Це одна з ідей, яка надихнула Річарда Файнмена зацікавитися ідеєю квантових обчислень. Файнмен написав деякі з найперших робіт на цю тему.
Розділ 7. У цьому розділі починається вивчення квантових обчислень за допомогою квантових схем. Означено квантові вентилі. Ми бачимо, як квантові вентилі діють на кубіт, і розуміємо, що ми розглядали ці ідеї весь час. Нам просто потрібно змінити нашу перспективу. Ми більше не думаємо про ортогональну матрицю, як вона діє на наш вимірювальний пристрій, а як діє на кубіт. Ми також довели деякі дивовижні результати щодо надщільного кодування, квантової телепортації, клонування та виправляння помилок.
Розділ 8. Це, мабуть, найскладніший розділ. У ньому ми розглянемо деякі квантові алгоритми і покажемо, як швидко вони можуть обчислити відповідь, якщо порівняти з класичними алгоритмами. Щоб говорити про швидкість роботи алгоритмів, нам потрібно ввести різні ідеї з теорії складності. Після того, як ми означили те, що називається складністю запиту, ми вивчаємо три квантові алгоритми і показуємо, що вони швидші стосовно цього типу складності, ніж їхні класичні аналоги.
Квантові алгоритми використовують структуру, що лежить в основі, розв’язуваної проблеми. Це набагато більше, ніж просто ідея квантового паралелізму — поміщення входових даних у суперпозицію всіх можливих станів. У цьому розділі представлено останню частину математичної техніки, Кронекерів добуток матриць. Але складність матеріалу насправді пов’язана з тим, що ми обчислюємо абсолютно по-новому і не маємо досвіду розв’язання задач із використанням цих нових ідей.
Розділ 9. Останній розділ розглядає вплив квантових обчислень на наше життя. Почнемо з короткого опису двох важливих алгоритмів, один винайшов Пітер Шор, інший — Лов Ґровер.
Шорів алгоритм дає спосіб розкласти велике число на добуток простих множників. Це може здатися не таким важливим, але наша безпека в інтернеті залежить від того, що цю задачу розв’язати. Можливість розкладати на множники добутки великих простих чисел загрожує нашим поточним методам захисту транзакцій між комп’ютерами. Можливо, пройде якийсь час, поки ми не отримаємо квантові комп’ютери, достатньо потужні, щоб розкласти на множники великі числа, які тепер використовуються, але загроза реальна, і вона вже змушує нас думати про те, як перепроєктувати способи, за допомогою яких комп’ютери можуть безпечно спілкуватися один з одним.
Ґроверів алгоритм призначений для спеціальних типів пошуку даних. Ми показуємо, як він працює для невеликого випадку, і вказуємо, як він працює загалом. І Ґроверів алгоритм, і Шорів важливі не тільки для проблем, які вони подужують, але й для нових ідей, які вони вносять. Ці основні ідеї впроваджувалися і впроваджуються в нове покоління алгоритмів.
Переглянувши алгоритми, ми змінюємо тему і коротко розглянемо, як квантові обчислення можна використовувати для моделювання квантових процесів. Хемія на найбазовішому рівні – квантова механіка. Класична обчислювальна хемія працює, беручи квантово-механічні рівняння і моделюючи їх за допомогою класичних комп’ютерів. Ці моделювання наближені й ігнорують дрібні деталі. Це добре працює в багатьох випадках, але деколи ні. І от тоді вам потрібні дрібні деталі, а квантові комп’ютери повинні мати можливість їх надати.
У цьому розділі також коротко розглядається створення реальних машин. Це галузь, яка дуже швидко розвивається. Перші машини виставляються на продаж. У хмарі є навіть одна машина, якою кожен може користуватися безплатно. Схоже, ми скоро вступимо в епоху квантової переваги. (Ми пояснюємо, що це означає.)
Книжка закінчується усвідомленням того, що квантові обчислення не новий тип обчислень, а відкриття справжньої природи обчислень.