Интернет журныл о промышленности в Украине

Неможлива машина, яка знає відповіді наперед: чим чудові квантові комп'ютери

  1. неможливі машини
  2. квантове програмування
  3. Сувора реальність
  4. Ренегати і шарлатани
  5. Правда D-Wave

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

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

Аналітична компанія Gartner включила їх у список перспективних технологій , Які "вистрілять" в найближчі десять років. Засновники компанії Parallels, мабуть, поділяють цю думку, тому що кілька місяців тому заснували венчурний фонд, який інвестуватиме в розвиток квантових технологій. Тим часом Google і Lockheed Martin витрачають мільйони на пристрої, що використовують для роботи квантові ефекти. Як казав Вінні Пух, це "ж-ж-ж" неспроста!

неможливі машини

неможливі машини

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

Під час роботи квантового комп'ютера окремі кубіти пов'язані між собою ефектом квантової заплутаності (entanglement). Кілька пов'язаних кубітів з невизначеним значенням містять не одне число, а всі можливі числа, що уміщаються в осередку такої розрядності. Іншими словами, квантовий комп'ютер одночасно розглядає всі рішення задачі, і правильні, і помилкові.

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

Це роблять за допомогою квантових алгоритмів, які складаються зі спеціальних операцій, що впливають на кубіти. Асоціація з комп'ютерними програмами, яку, можливо, викличе слово "алгоритм", не дуже точна. Квантові алгоритми зовсім не схожі на програми. У них куди більше спільного з логічними схемами, що складаються з вентилів І, АБО і НЕ, тільки замість булевої алгебри вони використовують квантову логіку.

квантове програмування

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

Саме його працездатність перевіряв квантовий комп'ютер, розкладають на множники число 15

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

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

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

Коли те ж завдання вирішується на квантовому комп'ютері за допомогою алгоритму Шора, час обчислень зростає НЕ експоненціально, а набагато повільніше. Великі числа раніше факторізуются довше коротких, але не настільки довго, щоб і намагатися не варто.

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

Інший цікавий приклад - алгоритм Гровера, що дозволяє знайти потрібний елемент в невідсортованому списку з N елементів, виконавши лише N1 / 2 порівнянь. На звичайному комп'ютері для вирішення тієї ж завдання треба було б N порівнянь.

Для наочності припустимо, що в списку мільйон елементів. Звичайного комп'ютера, щоб відшукати один з них, необхідно виконати мільйон порівнянь. Квантовий комп'ютер, що використовує алгоритм Гровера, обійдеться тисячею. Це не експоненціальне прискорення, як в разі алгоритму Шора, але прибавка все одно відчутна.

Сувора реальність

Три атома берилію, використовувані в якості кубітів

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

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

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

Іони не стануть факторізовать числа лише тому, що їх назвали кубитами. Їм просто нічим це робити. Для виконання квантових операцій потрібно зовнішній вплив. Впливати на кубіти можна, наприклад, за допомогою лазера або мікрохвиль. Легко зрозуміти, що з невеликим числом кубіт таким методом ще можна впоратися, а от далі почнуться проблеми.

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

Ренегати і шарлатани

Ренегати і шарлатани

У 2007 році канадський стартап D-Wave оголосив про намір випустити перший комерційний квантовий комп'ютер. Намір підкріпили демонстрацією машини, яка, за запевненнями розробників, налічувала шістнадцять кубіт.

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

Уява вражала інше: наполеонівські плани D-Wave. До кінця року компанія мала намір довести число кубіт до 32, а до середини 2008 року впустити квантовий комп'ютер з 1024 кубитами.

Обіцянки D-Wave відрізнялися від суворої реальності, добре знайомої всім, хто займався дослідженнями в області квантових обчислень, як небо і земля. Стрибок таких масштабів був би дивом, а чудес, як відомо, не буває.

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

До D-Wave приклеївся ярлик "шарлатани", але компанія продовжувала працювати. Надто оптимістичний план довелося скорегувати. Машина, яка використовує, якщо вірити D-Wave, 128 кубітів, з'явилася не в 2008, а лише в 2011 році. Кілька місяців тому розрядність довели до 512.

У 2009 році D-Wave і Google провели спільну презентацію. Хартмут Невен, видатний фахівець в області розпізнавання осіб, що працює в Google, розповів про випробування самонавчального алгоритму для виділення автомобілів на знімках Street View. За твердженням Невена, квантове пристрій D-Wave впоралося з завданням краще, ніж традиційні комп'ютери в дата-центрах Google.

Такий розвиток подій трохи спантеличило скептиків. Результати, які оприлюднив Невен, що не доводили, що в D-Wave побудували справжній квантовий комп'ютер, проте відмести їх теж було не можна. Якщо D-Wave - це шахраї, то як же їм вдалося переманити на свою сторону зовсім дурних людей з Google?

У 2011 році корпорація Lockheed Martin, гігант військово-промислового комплексу США, оголосила про придбання 128-кубітной машини D-Wave за 10 мільйонів доларів. Можна було б припустити, що покупка здійснена з цікавості, проте історія на цьому не закінчилася.

У березні 2013 року в Lockheed Martin вирішили купити наступну модель квантового комп'ютера D-Wave. Перша покупка не просто задовольнила інтерес компанії - вона довела свою корисність. Виходить, в обіцянках D-Wave все ж є частка правди?

Правда D-Wave

Правда D-Wave

У D-Wave в результаті відступили і опублікували пару наукових робіт про свою машину. Попутно стало ясно, що це, по-перше, не квантовий комп'ютер в найпоширенішому розумінні цього слова, а по-друге, кубіти, про які йде мова в рекламі компанії, строго кажучи, не цілком кубіти.

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

Машина D-Wave не годиться для алгоритмів, які використовують квантові вентилі. Ні алгоритм Шора, ні алгоритм Гровера на ній не підуть. Замість цього вона використовує для роботи зовсім інший принцип - так звані адиабатические квантові обчислення. Це значно обмежує її можливості, але дозволяє не турбуватися про декогеренції та інші проблеми, які супроводжують звичайні квантові обчислювачі.

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

Ця оптимізаційна задача має на диво багато реальних застосувань. У D-Wave використовували свій пристрій для фолдинга білків, в Google вчили його розпізнавати образи, а в Lockheed Martin пристосували машину для верифікації критично важливого програмного забезпечення.

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

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