Американський математик і фізик угорського походження Йоганн фон Нейман (1903 1957).

Американський фізик-теоретик Річард Філліпс Фейнман (1918-1988).

Американський математик Пітер Шор, фахівець в області квантових обчислень. Запропонував квантовий алгоритм швидкого факторизации великих чисел.

Американський математик Лов Гровер, автор квантового алгоритму швидкого пошуку в базі даних.

Квантовий біт, або кубіт. Станів і відповідають, наприклад, напрямки спина атомного ядра вгору або вниз.

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

<

>

ВСТУП, АБО ТРОХИ ПРО ЗАХИСТ ІНФОРМАЦІЇ

Як ви думаєте, на яку програму в світі продано найбільшу кількість ліцензій? Чи не ризикну наполягати, що знаю правильну відповідь, але мені точно відомий один невірний: це не яка-небудь з версій Microsoft Windows. Найпоширенішу операційну систему випереджає скромний продукт фірми RSA Data Security, Inc. - програма, яка реалізує алгоритм шифрування з відкритим ключем RSA, названий так на честь його авторів - американських математиків Ривеста, Шаміра і Адельмана.

Справа в тому, що алгоритм RSA вбудований в більшість продаваних операційних систем, а також в безліч інших додатків, що використовуються в різних пристроях - від смарткарт до стільникових телефонів. Зокрема, є він і в Microsoft Windows, а значить, поширений свідомо ширше цієї популярної операційної системи. Щоб виявити сліди RSA, наприклад, в браузері Internet Explorer (програмі для перегляду www-сторінок в мережі Інтернет), достатньо відкрити меню "Довідка" (Help), увійти в підменю "Про програму" (About Internet Explorer) і переглянути список використовуваних продуктів інших фірм. Ще один поширений браузер Netscape Navigator теж використовує алгоритм RSA. Взагалі, важко знайти відому фірму, що працює в області високих технологій, яка не купила б ліцензію на цю програму. На сьогоднішній день фірма RSA Data Security, Inc. продала вже понад 450 мільйонів (!) ліцензій.

Чому ж алгоритм RSA виявився такий важливий?

Уявіть, що вам необхідно швидко обмінятися повідомленням з людиною, що знаходиться далеко. Завдяки розвитку Інтернету такий обмін став доступний більшості теперішніх людей - треба тільки мати комп'ютер з модемом або мережевою картою. Природно, що, обмінюючись інформацією по мережі, ви б хотіли зберегти свої повідомлення в таємниці від сторонніх. Однак повністю захистити протяжну лінію зв'язку від прослуховування неможливо. Значить, при посилці повідомлення, потрібно зашифрувати, а при отриманні - розшифрувати. Але як вам і вашому співрозмовнику домовитися про те, яким ключем ви будете користуватися? Якщо послати ключ до шифру по тій же лінії, підслуховує зловмисник легко його перехопить. Можна, звичайно, передати ключ з якої-небудь іншої лінії зв'язку, наприклад відправити його телеграмою. Але такий метод зазвичай незручний і до того ж не завжди надійний: іншу лінію теж можуть прослуховувати. Добре, якщо ви і ваш адресат заздалегідь знали, що будете обмінюватися шифровками, і тому заблаго-тимчасово передали один одному ключі. А як бути, наприклад, якщо ви хочете послати конфіденційне комерційну пропозицію можливого ділового партнера або купити по кредитній картці товар, який сподобався в новому Інтернет-магазині?

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

Якраз така криптографічний схема і застосовується в алгоритмі RSA - найпоширенішому методі шифрування з відкритим ключем. Причому для створення пари відкритого і закритого ключів використовується наступна важлива гіпотеза. Якщо є два великих (що вимагають більше сотні десяткових цифр для запису свого) простих числа M і K, то знайти їх добуток N = MK не складе великих труднощів (для цього навіть не обов'язково мати комп'ютер: досить акуратний і терпляча людина зможе перемножити такі числа з допомогою ручки і паперу). А ось вирішити зворотну задачу, тобто, знаючи велику кількість N, розкласти його на прості множники M і K (так звана задача факторизації) - практично неможливо! Саме з цією проблемою зіткнеться зловмисник, який вирішив "зламати" алгоритм RSA і прочитати зашифровану з його допомогою інформацію: щоб дізнатися закритий ключ, знаючи відкритий, доведеться обчислити M або K.

Для перевірки справедливості гіпотези про практичну складності розкладання на множники великих чисел проводилися і досі ще проводяться спеціальні конкурси. Рекордом вважається розкладання всього лише 155-значного (512-бітного) числа. Обчислення велися паралельно на багатьох комп'ютерах протягом семи місяців 1999 року. Якби це завдання виконувалася на одному сучасному персональному комп'ютері, було б потрібно приблизно 35 років машинного часу! Розрахунки показують, що з використанням навіть тисячі сучасних робочих станцій і кращого з відомих на сьогодні обчислювальних алгоритмів одне 250-значне число може бути розкладено на множники приблизно за 800 тисяч років, а 1000-значне - за 1025 (!) Років. (Для порівняння вік Всесвіту дорівнює ~ 1010 років.)

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

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

ЯК ВСЕ ПОЧИНАЛОСЯ?

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

У 1960-і роки американський фізик Р. Ландауер, який працював в корпорації IBM, намагався звернути увагу наукового світу на те, що обчислення - це завжди певний фізичний процес, а значить, неможливо зрозуміти межі наших обчислювальних можливостей, не уточнивши, якій фізичній реалізації вони відповідають. На жаль, в той час серед вчених панував погляд на обчислення як на якусь абстрактну логічну процедуру, вивчати яку слід математикам, а не фізикам.

У міру поширення комп'ютерів вчені, які займалися квантовими об'єктами, прийшли до висновку про практичну неможливість безпосередньо розрахувати стан еволюціонує системи, що складається всього лише з декількох десятків взаємодіючих частинок, наприклад молекули метану (СН4). Пояснюється це тим, що для повного опису складної системи необхідно тримати в пам'яті комп'ютера експоненціально велике (по числу частинок) кількість змінних, так званих квантових амплітуд. Виникла парадоксальна ситуація: знаючи рівняння еволюції, знаючи з достатньою точністю всі потенціали взаємодії часток один з одним і початковий стан системи, практично неможливо обчислити її майбутнє, навіть якщо система складається лише з 30 електронів в потенційній ямі, а в розпорядженні є суперкомп'ютер з оперативною пам'яттю , число бітів якої дорівнює кількості атомів у видимій області Всесвіту (!). І в той же час для дослідження динаміки такої системи можна просто поставити експеримент з 30 електронами, помістивши їх в задані потенціал і початковий стан. На це, зокрема, звернув увагу російський математик Ю. І. Манін, що вказав в 1980 році на необхідність розробки теорії квантових обчислювальних пристроїв. У 1980-ті роки цю ж проблему вивчали американський фізик П. Біньова, явно показав, що квантова система може робити обчислення, а також англійський учений Д. Дойч, теоретично розробив універсальний квантовий комп'ютер, що перевершує класичний аналог.

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

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

У 1996 році колега Шора по роботі в Lucent Technologies Л. Гровер запропонував квантовий алгоритм швидкого пошуку в невпорядкованою базі даних. (Приклад такої бази даних - телефонна книга, в якій прізвища абонентів розташовані не за алфавітом, а довільним чином.) Завдання пошуку, вибору оптимального елемента серед численних варіантів дуже часто зустрічається в економічних, військових, інженерних задачах, в комп'ютерних іграх. Алгоритм Гровера дозволяє не тільки прискорити процес пошуку, але і збільшити приблизно в два рази число параметрів, що враховуються при виборі оптимуму.

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

ПРИСТРІЙ квантовий комп'ютер

Перш ніж розповісти, як же влаштований квантовий комп'ютер, згадаємо основні особливості квантових систем (див. Також "Наука і життя" № 8, 1998 р .; № 12, 2000 г.).

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

квантовий біт

Основний осередок квантового комп'ютера - квантовий біт, або, скорочено, кубіт (q-біт). Це квантова частинка, що має два базових стани, які позначаються 0 і 1 або, як прийнято в квантовій механіці, і. Двом значенням кубіта можуть відповідати, наприклад, основне і порушену стану атома, напряму вгору і вниз спина атомного ядра, напрямок струму в надпровідний кільці, два можливих положення електрона в напівпровіднику і т.п.

квантовий регістр

Квантовий регістр влаштований майже так само, як і класичний. Це ланцюжок квантових бітів, над якими можна проводити одно- і двухбітовий логічні операції (подібно застосуванню операцій НЕ, 2 І-НЕ і т.п. в класичному регістрі).

До базових станів квантового регістра, утвореного L кубитами, відносяться, так само як і в класичному, всі можливі послідовності нулів і одиниць довжиною L. Усього може бути 2L різних комбінацій. Їх можна вважати записом чисел в двійковій формі від 0 до 2L-1 і позначати. Однак ці базові стану не вичерпують всіх можливих значень квантового регістра (на відміну від класичного), оскільки існують ще й стану суперпозиції, що задаються комплексними амплітудами, пов'язаними умовою нормування. Класичного аналога у більшості можливих значень квантового регістра (за винятком базових) просто не існує. Стану класичного регістра - лише жалюгідна тінь всього багатства станів квантового комп'ютера.

Уявіть, що на регістр здійснюється зовнішній вплив, наприклад, в частину простору подані електричні імпульси або спрямовані лазерні промені. Якщо це класичний регістр, імпульс, який можна розглядати як обчислювальну операцію, змінить L змінних. Якщо ж це квантовий регістр, то той же імпульс може одночасно перетворити до змінних. Таким чином, квантовий регістр, в принципі, здатний обробляти інформацію в разів швидше в порівнянні зі своїм класичним аналогом. Звідси відразу видно, що маленькі квантові регістри (L <20) можуть служити лише для демонстрації окремих вузлів і принципів роботи квантового комп'ютера, але не принесуть великої практичної користі, оскільки не зможуть обігнати сучасні ЕОМ, а коштувати будуть явно дорожче. Насправді квантове прискорення зазвичай значно менше, ніж наведена груба оцінка зверху (це пов'язано зі складністю отримання великої кількості амплітуд і зчитування результату), тому практично корисний квантовий комп'ютер повинен містити тисячі кубітів. Але, з іншого боку, зрозуміло, що для досягнення дійсного прискорення обчислень немає необхідності збирати мільйони квантових бітів. Комп'ютер з пам'яттю, яка вимірюється всього лише в кілокубітах, буде в деяких завданнях незрівнянно швидше, ніж класичний суперкомп'ютер з терабайтами пам'яті.

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

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

КВАНТОВІ КОМП'ЮТЕРИ СЬОГОДНІ

Прототипи квантових комп'ютерів існують вже сьогодні. Правда, поки що експериментально вдається збирати лише невеликі регістри, що складаються всього з декількох квантових бітів. Так, нещодавно група, очолювана американським фізиком І. Чангом (IBM), оголосила про збірку 5-бітового квантового комп'ютера. Безсумнівно, це великий успіх. На жаль, існуючі квантові системи ще не здатні забезпечити надійні обчислення, так як вони або недостатньо керовані, або дуже схильні до впливу шумів. Однак фізичних заборон на побудову ефективного квантового комп'ютера немає, необхідно лише подолати технологічні труднощі.

Існує кілька ідей і пропозицій, як зробити надійні і легко керовані квантові біти.

І. Чанг розвиває ідею про використання в якості кубітів спинив ядер деяких органічних молекул.

Російський дослідник М. В. Фейгельман, що працює в Інституті теоретичної фізики ім. Л. Д. Ландау РАН, пропонує збирати квантові регістри з мініатюрних надпровідного кових кілець. Кожне кільце виконує роль кубіта, а станам 0 і 1 відповідають напряму електричного струму в кільці - за годинниковою стрілкою і проти неї. Перемикати такі кубіти можна магнітним полем.

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

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

ПОГЛЯД У МАЙБУТНЄ

Спробуємо уявити, як міг би виглядати майбутній квантовий комп'ютер. Ймовірно, великий (масштабований) комп'ютер буде містити тисячі керуючих елементів, що діють локально на кожен кубіт. Яким чином могло б здійснюватися цей вплив? Швидше за все, за допомогою електричних імпульсів, що подаються на мікроелектроди, підведені до кубітів. Можливо також оптичне управління пучками світла, сфокусованими на кубітах. Однак в цьому випадку важко уникнути паразитного впливу на сусідні кубіти дифракційних країв сфокусованого пучка. Що стосується електричних методів, то вони вже давно і широко застосовуються в мікроелектроніці для управління класичні кими логічними елементами. Тому їх використання видається найбільш перспективним і для створення масштабованих квантових комп'ютерів. (Можливо, звичайно, що в результаті якогось технологічного прориву з'явиться ще і третій варіант. Однак революційні відкриття важко піддаються прогнозу.)

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

А що ж стане з класичними комп'ютерах терамі? Відімруть вони? Навряд чи. І для класичних, і для квантових комп'ютерів знайдуться свої сфери застосування. Хоча, судячи з усього, співвідношення на ринку буде все ж поступово зміщуватися в бік останніх.

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

Автор висловлює подяку лову Гроверу і Пітеру Шору за люб'язно надані матеріали і підтримку при написанні статті.

ЩО ЧИТАТИ про квантовий комп'ютер

Для більш глибокого освоєння цієї теми можна прочитати оглядову статтю Е. Ріффель, В. Полак "Основи квантових обчислень", опубліковану в видаваному в Росії журналі "Квантові комп'ютери і квантові обчислення" (№ 1, 2000 г.). (До речі, це перший і поки єдиний в світі журнал, присвячений квантових обчислень. Додаткову інформацію про нього можна дізнатися в Інтернеті за адресою http://rcd.ru/qc .). Освоївши цю роботу, ви зможете читати наукові статті з квантових обчислень.

Кілька велика попередня математична підготовка буде потрібно при читанні книги А. Китаєва, А. Шеня, М. Млявого "Класичні і квантові обчислення" (М .: МЦНМО-ЧеРо, 1999).

Ряд принципових аспектів квантової механіки, істотних для проведення квантових обчислень, розібраний в книзі В. В. Белокурова, О. Д. Тимофіївській, О. А. Хрустальова "Квантова телепортація - звичайне диво" (Іжевськ: РГД, 2000).

У видавництві РХД готується до виходу у вигляді окремої книги переклад огляду А. Стіна, присвячений квантових комп'ютерів.

По вівторках з 15.00 в конференц-залі Фізико-технологічного інституту РАН в Москві проходить семінар "Квантовий комп'ютер". Інформацію про те, як взяти участь в семінарі, можна дізнатися в Інтернеті за адресою http://qc.ipt.ac.ru .

Наступна література буде корисна не тільки в пізнавальному, а й в історичному плані:

1) Ю. І. Манін. Обчислюваних і невичіслімое.

- М .: Сов. радіо, 1980.

2) І. фон Нейман. Математичні основи квантової механіки.

- М .: Наука, 1964.

3) Р. Фейнман. Моделювання фізики на комп'ютерах // Квантовий комп'ютер і квантові обчислення:

Зб. в 2-х т. - К: РХД, 1999. Т. 2, с. 96-123.

4) Р. Фейнман. Квантово-механічні комп'ютери

// Там же, с. 123.-156.

Див. У номері на ту ж тему

Квантові біти і вентилі