НОУ ІНТУЇТ | лекція | Принципи квантових обчислень

  1. Квантові алгоритми і квантові обчислення, їх переваги Як і в класичних обчисленнях, обробку інформації...
  2. Технічні вимоги до елементної бази квантового процесора

Квантові алгоритми і квантові обчислення, їх переваги

Як і в класичних обчисленнях, обробку інформації шляхом застосування квантових логічних операцій можна описувати по-різному:

  • як виконання в певній послідовності елементарних перетворень, тобто як послідовне застосування до наявних даних (операндам) ряду операторів, - в цьому випадку говорять про квантових програмах або алгоритмах;
  • як послідовну обробку потоку даних в мережі квантових логічних вентилів або "гейтов" (від англ. gate), - тоді говорять про квантових схемах.

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

Доведено, що з квантових вентилів можна побудувати квантові логічні схеми для обчислення будь-якої класичної функції. Вважається, що для квантових обчислень має силу навіть "посилений" теза Черча-Тьюринга-Дойча, а саме: за допомогою квантових логічних схем (квантових алгоритмів) можна змоделювати будь-який фізичний процес, обмежений в просторі і часі.

Обґрунтовано ряд функціонально повних наборів квантових логічних операцій (вентилів).

У 1997 р була детально розроблена одна з можливих теоретичних моделей універсальної квантової машини Тьюрінга [Bernstein E., Vazirani UV Quantum complexity theory. // Society for Industrial and APPLIED Mathematics Journal on Computing. - 1997. - v. 26, No. 5. - P. 1411-1473].

Однак серйозну увагу наукового співтовариства до квантових обчислень було залучено лише тоді, коли були запропоновані алгоритми квантових обчислень для задач, непосильних для найпотужніших класичних ЕОМ.

Першим з них був квантовий алгоритм факторизації, тобто розкладання багатозначних цілих чисел на прості множники, запропонований в 1994 р П. Шором. Найбільш ефективний з відомих класичних алгоритмів факторизації вимагає для вирішення цього завдання кількість обчислювальних операцій порядку Першим з них був квантовий алгоритм факторизації, тобто  розкладання багатозначних цілих чисел на прості множники, запропонований в 1994 р П , де - константа, - кількість десяткових знаків в розкладається на множники числі. уже при задача не може бути вирішена за розумний час навіть на найпотужніших багатопроцесорних сучасних суперкомп'ютерах. На цьому факті заснований, до речі, дуже популярний нині криптографічний протокол RSA, що забезпечує надійний захист важливої ​​інформації від сторонніх осіб. Квантовий алгоритм П. Шора вимагає для вирішення цього завдання кількість квантових обчислювальних операцій, що не експоненціально, а тільки полиномиально залежить від . Тому квантовий комп'ютер, до складу якого входять близько 1000 кубітів, з тактовою частотою близько 1 ГГц був би здатний впоратися з факторизації цілих чисел довжиною 200 десяткових знаків вже за кілька хвилин!

Алгоритм П. Шора став справжнім відкриттям для обчислювальної математики. Адже виявилося, що класи складності завдань для класичних і для квантових обчислень не співпадають, що квантові обчислення деяких важливих типів завдань можуть бути набагато ефективнішими, ніж класичні.

Це підтвердив і опублікований Л. Гровером в 1996 р алгоритм швидкого пошуку в неструктурованою базі даних. У той час як класичний пошук потрібного запису вимагає в середньому Це підтвердив і опублікований Л операцій, де - загальне число записів, запропонований Л. Гровером квантовий алгоритм дозволяє знайти потрібну запис приблизно за квантових операцій.

Ефективність алгоритмів П. Шора і Л. Гровера заснована на використанні істотних переваг сплетених станів і експоненціально зростаючого квантового паралелізму обробки інформації в таких станах.

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

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

І в результаті стало очевидним те, що працювати над практичною реалізацією квантових обчислень безсумнівно слід. Тому кінець ХХ - початок ХХІ ст. ознаменувалися значною активізацією досліджень і розробок квантових алгоритмів, підходів до програмування квантових обчислень, а також шляхів реалізації кубітів і квантових схем.

Декогеренції і квантова корекція помилок

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

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

За тривалий час вектор стану може неконтрольовано "дрейфувати" досить далеко. А це змінює зв'язок його фази з фазами інших кубітів. Має місце поступова втрата когерентності. А час від часу збіг декількох зовнішніх впливів діє як процес зчитування: кубіт стрибком переходить в одне зі своїх базових станів. У разі взаємодії ряду кубітів, особливо в сплетених станах, це призводить до непередбаченої зміни стану всього квантового регістра. І чим більше кубітів в регістрі, тим частіше має місце втрата когерентності. Це явище називають "декогеренції" (від англ. "Decoherence"). Через це в квантових обчисленнях відбуваються помилки, і далі еволюція квантового процесора стає вже неконтрольованою.

Щоб легше зрозуміти, що таке декогеренції, знову погляньте на Мал. 8.2 і уявіть собі, що під одним з поплавців промайнула рибка або на нього випадково впав листочок, в результаті чого фаза його коливань, а може і частота, трохи збилися. Ясно, що результат інтерференції хвиль зміниться, а оскільки всі поплавки сплетені, то це трохи вплине і на коливання інших поплавців.

На щастя, однак, виявилося, що з руйнівним впливом декогеренції можна успішно боротися за допомогою добре продуманих методів кодування, періодичного контролю, своєчасного виявлення та квантової корекції помилок.

Методи виявлення і корекції збоїв і помилок були добре розроблені вже в класичній обчислювальній техніці, де на практиці доведено високу ефективність "надлишкового" кодування, коли п біт даних спеціальними способами кодуються ( Методи виявлення і корекції збоїв і помилок були добре розроблені вже в класичній обчислювальній техніці, де на практиці доведено високу ефективність надлишкового кодування, коли п біт даних спеціальними способами кодуються (   ) -Бітний кодом ) -Бітний кодом. Це дозволяє ефективно виявляти одно-, дво- і навіть многобітовие помилки і коригувати їх. Подібна ідея використовується і в квантовому випадку. Правда, квантова корекція помилок виявилася набагато складнішою, адже мова йде не про бітах, а про кубітах, - разом з усіма їх особливостями. Додатково ускладнює справу неможливість "клонування", тобто створення декількох копій стану кубітів.

Є, однак, і специфічно квантові переваги. Наприклад, уже в разі одного кубіта можна вважати допустимими не всі його квантові стану. Сферу Блоха ( Мал. 8.1 ) Можна розбити на окремі ділянки, наприклад, аппроксимируя її правильним многогранником, і вважати допустимими лише квантові стану, які представлені векторами, проведеними до центру граней. Якщо через зовнішні впливів вектор стану зміститься за деякий час (період контролю) зі свого допустимого положення, але залишиться в межах межі, то при періодичному контролі він може бути примусово повернутий до центр межі, що дозволяє підтримувати допустимий стан кубіта незмінним як завгодно довго .

Ефективні методи кодування, діагностики відхилень і їх квантової корекції вже знайдені і детально розроблені. Ми не станемо тут їх пояснювати, так як це - завдання іншого курсу лекцій. Зазначимо лише, що знайдені методи дозволяють підтримувати контрольований процес квантових обчислень як завгодно довго, якщо ймовірність помилки при виконанні однієї квантової логічної операції нижче певного рівня - близько однієї помилки на 104-105 квантових операцій.

Програма періодичного контролю, виявлення, діагностики та квантової корекції помилок повинна запускатися на початку квантових обчислень і працювати у фоновому режимі. Через необхідність надлишкового кодування значно (іноді в кілька разів) зростає і сумарна кількість необхідних для квантових обчислень кубітів. Але завдяки цьому квантові обчислення стають практично можливими навіть при наявності декогеренції.

Технічні вимоги до елементної бази квантового процесора

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


Мал.8.4.

Функціональна схема апаратури для квантових обчислень: 1 - класична швидкодіюча ЕОМ; 2 - квантовий процесор; 3, 4 - пристрої запису інформації в квантові регістри; 5 - пристрій управління квантовими операціями; 6 - пристрій зчитування інформації з кубітів

Цикл роботи комплексу починається з "ініціалізації" - занесення в першу частину квантового регістра через пристрій 3 потрібного набору початкових даних. Відповідні кубіти переводяться при цьому в свідомо задані базові квантові стану. Через пристрій 4 всі інші кубіти переводяться в базове квантовий стан "0". Далі за допомогою пристрою 5 спочатку виконується перетворення Уолша-Адамара, внаслідок чого квантовий регістр переходить в одне з максимально сплетених станів. А потім виконується ряд передбачених програмою квантових операцій, в ході яких відбуваються цілеспрямовані взаємоузгоджені перетворення одночасно мільярдів і мільярдів мільярдів комплексних амплітуд. Досягається такий ступінь паралелізму, яка "і не снилася" класичним комп'ютерам.

Коли перетворення закінчуються, за допомогою пристрою 6 інформація зчитується з кубітів і передається в класичний комп'ютер. Програмою роботи може бути передбачено також проміжне зчитування стану лише кількох або навіть одного з усіх кубітів. За результатами проміжного зчитування вибирається одне з багатьох можливих продовжень програми, і цикл повторюється.

Передбачається і багаторазове повторення однієї програми при різних варіантах початкових даних. Такого роду комплекс забезпечує ефективне об'єднання переваг як класичних, так і квантових обчислень.

Елементна база практично корисного квантового процесора повинна відповідати таким технічним вимогам:

  • процесор повинен складатися не менше ніж з приблизно 1000 слабо взаємодіючих кубітів, оскільки лише в цьому випадку економічно виправдовуються витрати на його реалізацію в порівнянні з сучасними класичними суперкомпьютерами;
  • повинна бути забезпечена можливість надійної запису інформації, якщо не в кожен, то в значне число кубітів, і проміжного зчитування стану деяких кубітів, а також зчитування кінцевого результату з усієї вихідної частини квантового регістра;
  • квантовий процесор повинен бути настільки добре ізольований від зовнішніх впливів, що визначають його декогеренції, щоб гарантований час збереження когерентності було достатнім для виконання принаймні 104-105 квантових логічних операцій;
  • в процесорі повинна бути забезпечена можливість контрольованого виконання функціонально повного набору квантових логічних операцій;
  • ефективне надлишкове кодування і фонові програми діагностики та квантової корекції помилок повинні підтримувати процес квантових обчислень досить довго;
  • до складу процесора повинні входити досить швидкі і надійні шини зв'язку;
  • в процесорі повинна бути оперативна пам'ять для зберігання і повторного використання проміжних результатів обчислень.