Квантова абетка: Комп'ютер

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

Приводом для цієї теми стала новина про те, що фізикам з MIT вдалося вперше реалізувати квантовий алгоритм Шора в масштабованій системі. На наші запитання про те, що це означає, відповідав співробітник РКЦ, завідувач лабораторією надпровідних матеріалів Національного дослідницького технологічного університету «МІСіС» і професор Технологічного інституту Карлсруе Олексій Устинов.

Що таке квантові обчислення і чим вони відрізняються від класичних?

Відрізняються поданням даних, в першу чергу, і методом обробки цих даних. Звичайні обчислення працюють зі звичні нам «0» і «1», які можна уявити у вигляді двох сторін однієї монети, або «орел», або «решка». Квантові обчислення працюють з даними, які представляються у вигляді багатьох станів, навіть нескінченної кількості станів. І замість «орла» і «решки» можна уявити собі кульку, яку можна повертати різними сторонами, причому навколо різних осей. Оскільки статків у такої кульки нескінченна кількість, дані зовсім по-іншому виглядають. Незвичайність ще й у тому, що якщо ми захочемо виміряти стан, що зберігається в кульці, то побачимо лише одне зі значень. Наприклад, що він повернуть в якусь одну сторону: на північ або на південь. Але якщо ми проведемо вимірювання багаторазово, що побачимо певний статистичний розподіл між цими полюсами. Звучить складно, але суть в тому, що в квантовому комп'ютері самі дані представлені зовсім в іншому вигляді і це тому і операції з цими даними виглядають зовсім по-іншому.

У квантових алгоритмах використовується звичайна логіка, якою користуються люди з часів Арістотеля або якась своя, квантова?

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

Якісь схожі на класичну обчислювальну логіку операції є і в квантовій: наприклад, операція «заперечення» переводить систему з одного стану в інший. Є операції, які за назвою схожі з класичними, але працюють по-іншому, оскільки оперують зовсім іншими даними. Наприклад, є типові операції, пов'язані зі зміною стану двох кубітів, так звані двох-кубітні гейти. Використовуються і операції, яких немає в класичному комп'ютері - «умовне заперечення», коли стан одного кубіта змінюється залежно від стану іншого.

Квантовий комп'ютер завжди швидший за звичайний? Для яких завдань квантовий комп'ютер непридатний і простіше використовувати звичайний?

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

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

Як працює алгоритм Шора?

Алгоритм Шора - це квантовий алгоритм розкладання числа на прості множники, тобто факторизації. Далі потрібно вдаватися в досить тонкі подробиці, але якщо зовсім грубо, то алгоритм Шора заснований на квантовому перетворенні Фур'є, яке використовують багато алгоритмів, що працюють більш ефективно саме на квантовому комп'ютері. Алгоритм Шора влаштований по-іншому, працює не прямим перебором, а перебором, використовуючи багато станів. І при цьому кількість спроб виявляється меншою, ніж на класичному комп'ютері. Важливо, що якщо на класичному комп'ютері кількість спроб при розкладанні числа екпоненційно залежить самого числа, то при використанні алгоритму Шора час, який потрібен для обчислень, залежить від числа за ступенем, а не за експоненційним законом. А степенева залежність зростає, як ви знаєте, набагато повільніше експоненціальної.

Computer Laboratory, University of Cambridge