Квантовий комп'ютер

Материал из МДПУ Вікіпедія | MDPU Wikipedia
Перейти к навигации Перейти к поиску
Файл:Квантовий реґістр.png
3 кубіти квантового регістра проти 3 бітів звичайного.

Квáнтовий комп'ю́тер — фізичний обчислювальний пристрій, функціонування якого ґрунтується на принципах квантової механіки, зокрема, принципі суперпозиції та явищі квантової заплутаності. Такий пристрій відрізняється від звичайного транзисторного комп'ютера зокрема тим, що класичний комп'ютер оперує даними, закодованими у двійкових розрядах (бітах), кожен з яких завжди перебуває в одному з двох станів (0 або 1), коли квантовий комп'ютер використовує квантові біти (кубіти), які можуть знаходитися у суперпозиції станів. Інформатико-теоретичною моделлю такого обчислювального пристрою є квантова машина Тюрінга, або універсальний квантовий комп'ютер, яка була розроблена Девідом Дойчем у 1985 році[1]. Квантовий комп'ютер має низку спільних ознак із недетермінованим та ймовірнісним комп'ютерами, але ці пристрої не є тотожними. Вважається, що вперше ідею використання принципів квантової механіки для виконання обчислень висловили Юрій Манін у книзі «Обчислювальне і необчислювальне» у 1980 році[2] та Річард Фейнман у лекції на Першій конференції з фізики обчислень у МТІ в 1981 році[3][4], хоча пропозиції використання напівцілих спінів як найпростіших обчислювальних елементів лунали і раніше[5].

Теоретично квантовий комп'ютер здатний розв'язувати певні задачі набагато швидше, ніж звичайні комп'ютери, наприклад, задачу факторизації цілих чисел або ефективного моделювання квантової системи багатьох тіл. Існує низка Шаблон:Нп, наприклад, алгоритм Шора, Шаблон:Нп та інші, виконання яких займає набагато менше часу, ніж виконання будь-якого ймовірнісного класичного алгоритму[6]. Однак, за наявності великого об'єму обчислювальних ресурсів класичний комп'ютер здатен моделювати будь-який квантовий алгоритм, якщо він не порушує тезу Чорча — Тюрінга[7].

Теоретичні засади

Кубіти

Докладніше: Кубіт
Файл:Bloch Sphere.svg
Представлення кубіта за допомоги сфери Блоха.

У класичному комп'ютері для оперування інформацією використовуються елементарні двійкові розряди — біти. Фізична реалізація біта ґрунтується на тому принципі, що потенціал напруги може бути або вище певного рівня (це відповідатиме значенню біта 1) або нижче (0).

У квантовому комп'ютері інформація також, як правило, представляється за допомоги двійкових елементів. Як такі елементи використовуються фізичні системи з двома можливими станами, що описуються в квантовій механіці за допомогою двовимірного комплексного простору. Для опису подібної системи використовують позначення Дірака, де першому станові відповідає квантовомеханічний вектор стану <math>|0 \rangle</math>, а другому — інший вектор <math>|1 \rangle</math>. Роль подібної квантової системи із двома станами може грати зокрема спін електрона, який має дві можливі конфігурації — «спін вгору» і «спін вниз». В подібному ключі можуть бути використані енергетичні рівні атомів або молекул, або напрямок струму в кільцевому надпровіднику.

Такий елемент, що використовується для представлення інформації в квантовому комп'ютері, дістав окрему назву квантовий біт (англ. quantum bit, qubit), або скорочено кубіт, що підкреслює його квантовомеханічну природу. Важливою властивістю кубіта є можливість накладання декількох станів, або їх суперпозиція. Це означає, що кубіт необов'язково знаходиться саме у стані <math>|0 \rangle</math> або <math>|1 \rangle</math>, як це має місце для бітів у класичному комп'ютері. Стан кубіта може бути представлений довільним вектором <math>|\psi\rangle</math> у вищезазначеному двовимірному комплексному просторі[8]:

<math> |\psi\rangle = a|0\rangle + b|1\rangle </math>

за тим самим принципом, як в оптиці описуються дві когерентні хвилі, що накладаються одна на одну. Таким чином, існує принципова різниця між кубітом та класичним ймовірнісним бітом (тобто, таким класичним бітом, що набуває випадково одне зі значень 0 або 1). В оптиці це еквівалентно різниці між некогерентними та когерентними хвилями: у першому випадку додаються інтенсивності хвиль, у другому — амплітуди (як це відбувається, наприклад, у голографії). a і b є довільними комплексними числами, на які без обмеження загальності накладаються умови нормування:

<math> |a|^2 + |b|^2 = 1.</math>

З математичної точки зору, числа <math>P(0) = |a|^2 = |\langle 0 | \psi\rangle|^2</math> та <math>P(1) = |b|^2 = |\langle 1 | \psi\rangle|^2</math> дорівнюють ймовірностям отримання відповідно значення 0 або 1 при вимірюванні кубіта, що знаходиться у стані <math>| \psi\rangle</math>. Однак, як вже було зазначено, не можна інтерпретувати кубіт як такий, що завжди знаходиться із певною ймовірністю виключно у стані <math>|0 \rangle</math> або <math>|1 \rangle</math>, і ні в якому іншому: така поведінка відповідає класичному ймовірнісному бітові і може бути змодельована на класичному комп'ютері, що випадково генерує результат 0 або 1 (тобто, використовуючи генератор випадкових чисел). З точки зору теоретичної фізики, подібний класичний ймовірнісний біт підкоряється законам статистичної фізики, тому, на відміну від квантовомеханічного випадку, його стан являє собою некогерентну суміш двох відповідних станів.

У свою чергу, стан кубіта являє собою когерентну суперпозицію двох відповідних станів:

<math> P(\psi) = ||\psi\rangle|^2 = |a|^2 + |b|^2 + 2 \operatorname{Re}[a^{*}b\langle 0 | 1 \rangle],</math>

де <math>\operatorname{Re}[...]</math> позначає дійсну частину комплексного числа, <math>a^{*}</math> — комплексно спряжене до a число, <math>\langle 0 | 1 \rangle</math> — скалярний добуток векторів станів 0 і 1.

Квантовий регістр і квантова заплутаність

Докладніше: Сплутані квантові стани

Як і у випадку класичних бітів, N кубітів можна об'єднати у квантовий регістр, причому стан такого квантового регістра описуватиметься за допомогою <math>2^N</math>-вимірного гільбертова простору. Базисом цього простору природньо обираються всі можливі комбінації тензорних добутків N однокубітових базисних векторів <math>|0\rangle</math> і <math>|1\rangle</math>. Наприклад, базисом для регістра, що складається з двох кубітів, буде набір з чотирьох векторів <math>|00\rangle</math>, <math>|01\rangle</math>, <math>|10\rangle</math> і <math>|11\rangle</math>. Довільний стан квантового регістра матиме вигляд суперпозиції всіх його базисних векторів:

<math>|\psi_N\rangle =\sum_{i_1,\dots ,i_N}c_{i_1\dots i_N}\,(|i_1\rangle \otimes |i_2\rangle \otimes \dots \otimes |i_N\rangle )\,,</math>

де <math>|i_j\rangle</math> — i-ий базисний вектор j-го кубіта, а <math>c_{i_1\dots i_N}</math> — комлексні числа, що відовідають компонентам <math>|\psi_N\rangle</math> уздовж відповідної комбінації однокубітових базисних векторів. Взагалі кажучи, у такому розкладі дозволені також суми та різниці станів декількох <math>n\le N</math> кубітів, на відміну від класичного регістра, де окремі біти з'являється лишу у вигляді конкретного базисного стану, тобто, увесь класичний регістр являє собою просто набір з нулів та одиниць.

Важливою властивістю квантового регістра є той факт, що його стан не завжди є простою комбінацією незалежних один від одного станів окремих кубітів: зокрема, можна розглянути наступний стан двокубітового регістра (один зі станів Белла):

<math>|\Psi^{+}\rangle =\frac{1}{\sqrt{2}} (|0\rangle \otimes |1\rangle + |1\rangle \otimes |0\rangle),</math>

який не можна звести до простого тензорного добутку станів першого та другого кубіта. Те ж саме можна сказати й про інший подібний стан двох кубітів:

<math>|\Psi^{-}\rangle =\frac{1}{\sqrt{2}} (|0\rangle \otimes |1\rangle - |1\rangle \otimes |0\rangle).</math>

Про такі стани кажуть, що вони є сплутаними, а факт наявності таких станів носить назву квантової заплутаності (англ. quantum entanglement, нім. Quantenverschränkung).

Існування явища квантової заплутаності дає право говорити про те, що квантовий комп'ютер є набагато потужнішим за класичний, оскільки він здатен розв'язувати певні задачі набагато швидше, ніж це робить класичний комп'ютер. Наприклад, для зберігання N-бітового регістра класичний комп'ютер оперує N класичними бітами. Але аналогічний квантовий регістр описується вектором у <math>2^N</math>-вимірному просторі, тому має бути задано <math>2^N</math> комплексних коефіцієнтів. У цьому випадку дуже важливим є той факт, що за великих N значення <math>2^N</math> є набагато більшим за N, тому часто принцип суперпозиції трактується як такий, що дозволяє зберігати в N-кубітовому регістрі одночасно всі <math>2^N</math> чисел від 0 до <math>2^N-1</math>. Однак це твердження вводить в оману: оскільки результатом вимірювання стану квантового регістра завжди є один з його можливих базисних станів, то з допомогою Шаблон:Нп можна довести, що максимально доступна кількість інформації, яку можна добути з одного кубіта, дорівнює одному бітові, як і в класичному випадку. Утім, слушним є твердження, що потужність квантових паралельних обчислень за принципом суперпозиції виходить за рамки можливостей, що надають класичні паралельні обчислення.

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

Докладніше: Квантовий вентиль
Файл:CNOT gate.svg
Квантовий вентиль CNOT — оборотний логічний елемент, що реалізує операцію «Контрольоване НЕ».

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

Обчислення на квантовому комп'ютері принципово відрізняються від класичних: квантовий вентиль (англ. quantum gate) є не просто технічним пристроєм, а являє собою певну елементарну фізичну дію над одним або декількома кубітами. Конкретний вигляд цієї фізичної маніпуляції залежить передусім від фізичної природи кубіта: наприклад, спін електрона може змінити орієнтацію при накладанні магнітного поля, а атом — перейти у збуджений стан під впливом лазерного імпульса. Таким чином, квантові вентилі не являють собою окремі пристрої, а реалізуються як певні маніпуляції над квантовим регістром у необхідний проміжок часу, які зручно зображати у вигляді квантових схем при описі квантових алгоритмів.

З точки зору квантової механіки, квантовий вентиль є унітарним оператором <math>\hat{U}</math>, що діє на стан квантового регістра <math>|\psi\rangle</math>:

<math> |\psi\rangle \rightarrow \hat{U}|\psi\rangle. </math>

Таким чином, квантовий вентиль можна представити у вигляді унітарної матриці. Наприклад, квантовий вентиль, що змінює стан кубіта на протилежний (заперечення НЕ), буде представлений у випадку двовимірного простору наступною матрицею:

<math> \hat{U} = \begin{pmatrix}0&1\\1&0\end{pmatrix}. </math>

Більш складними є квантові вентилі, що змінюють стани двох та більше кубітів, як, наприклад, вентиль CNOT (контрольоване НЕ), що діє у просторі <math>\mathbb C^4</math> двох кубітів за правилом: <math>|00\rangle\to |00\rangle ,</math>  <math>|01\rangle\to |01\rangle ,</math>  <math>|10\rangle\to |11\rangle </math> та <math>|11\rangle \to |10\rangle</math>, тобто, змінюючи стан другого кубіта на протилежний, якщо перший кубіт знаходиться у стані <math>|1\rangle</math>, і залишаючи його таким самим, якщо, навпаки, перший кубіт знаходиться у стані <math>|0\rangle</math>.

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

Передумови для створення

Наявна елементна база, побудована на «кремнієвих» технологіях, дозволить триматися на такому рівні зростання зовсім недовго. Основним зі встановлених природою обмежень є тепло, яке виділяє будь-який електроприлад. Яким би незначним не було тепло, при зменшенні розмірів «приладу» воно все одно буде перешкоджати, особливо, коли ці розміри вимірюються мікронами чи частками мікрон. Ідея використання в комп'ютерах ефекту надпровідності виникла давно, але до 80-х років залишалася не більш, як привабливою, екстравагантною ідеєю. Дослідження показали, що відсутність тепловиділення — не основна перевага надпровідникової комп'ютерної техніки; хоча саме вона і дозволяє в тисячу разів збільшити швидкодію і щільність заповнення. Використовуючи квантові ефекти, які виникають при надпровідності, комп'ютер може оперувати кількабітовими «зразками». Електрон, який пробігає мережею такого комп'ютера, буде одночасно виконувати роль і «ключа», і носія інформації. Структура квантового комп'ютера, його логіка стануть геть іншими, а сам комп'ютер матиме більше можливостей. Лихарєв вважає, що потенційним ринком для таких комп'ютерів будуть не «персоналки» чи текстові процесори, а мережеві комп'ютерні пристрої типу робочої станції.

Реалізації квантового комп'ютера

Файл:DWave 128chip.jpg
Зразок процесора D-Wave Systems, який складається із 128 надпровідних логічних елементів.

Створені реально квантові комп'ютери досі оперували з дуже незначною кількістю кубітів. У 2007 році оголошене створення квантового комп'ютера із 16 кубітами.[9]

В листопаді 2017 року компанія IBM представила прототип квантового комп'ютера з 50 кубіт. В представленому прототипі час когерентності кубіт (час, протягом якого вони можуть залишатись в стані суперпозиції та виконувати корисні обчислення) вдалось збільшити до 90 мікросекунд[10]. Основна частина цього прототипу (його «ядро») було показане компанією на виставці CES 2018[11].

9 січня 2018 року на виставці CES 2018 компанія Intel представила чип квантового комп'ютера на 49 кубіт з назвою Tangle Lake. В процесорі використані надпровідні ланцюги, робоча температура яких дорівнює 20 мілікельвін[12].

Квантові комп'ютери на оптичних чипах

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

На відміну від звичайних бітів чи транзисторів, які можуть бути представлені одночасно лише в одній з двох форм (1 або 0), кубіт може існувати у кількох формах одночасно і, таким чином, може використовуватись для зберігання та обробки набагато більшого обсягу інформації у більшому ступені.

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

«З використання системи двох часток ми отримуємо можливість виконувати експонентно складніші обчислення ніж досі», говорить професор (Джеремі О'Брайєн). «Це — початок досліджень у новій сфері квантової інформаційної науки, що прокладає шлях до квантових комп'ютерів, котрі допоможуть вирішити складніші наукові завдання.»

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

«Тепер, коли ми маємо змогу напряму реалізувати та спостерігати рух двох фотонів перед нами відкривається шлях до приладів з використанням трьох- та багатьох фотонів і результати мають бути більш ніж просто вражаючими», каже професор О'Брайєн. «Щоразу як ми додаємо фотон, ми дістаємо змогу вирішувати по експоненті все складніші задачі, тобто якщо однофотонна система має 10 відсоткову ефективність, то двофотонна — 100 відсоткову, а трифотонна 1000 і т. д.»[13]

Складність квантових обчислень

Докладніше: Квантова теорія складності обчислень
Файл:BQP complexity class diagram uk.svg
Очікуваний взаємозв'язок між класом BQP та іншими основними класами складності[14].

Клас складності задач, які можна ефективно розв'язати на квантовому комп'ютері, позначається BQP. Цей клас містить усі задачі, що можна розв'язати на квантовому комп'ютері за поліноміальний час за певної дозволеної обмеженої імовірності помилки (англ. bounded-error, quantum, polynomial). Оскільки квантові комп'ютери працюють лише за імовірнісними алгоритмами, то клас BQP є квантовим аналогом класу BPP — усі задачі, які можна розв'язати на класичному комп'ютері за поліноміальний час за певної дозволеної обеженої імовірності помилки (англ. bounded-error, probabilistic, polynomial). Кажуть, що квантовий комп'ютер може «розв'язати» задачу, якщо в результаті з високою ймовірністю отримується правильна відповідь. Якщо при цьому квантовий комп'ютер розв'язує задачу за поліноміальний час, то така задача належить класу BQP.

Клас BQP належить класові складності P# (або, точніше, приєднаному класові проблем вибору P#P)[15], який у свою чергу є підкласом PSPACE. Крім того, очікується, що BQP не перетинається з класом NP-повних задач і повністю містить клас P, однак це не доведено. Зокрема, задачі факторизації та дискретного логарифмування входять до класу BQP, і при цьому очікується, що вони входять до класу NP, але не належать класові BPP і, отже, класові P. Також очікується, що обидві задачі не є NP-повними. Існує поширена думка, що квантові комп'ютери можуть розв'язувати NP-повні задачі за поліноміальний час, але це твердження не доведене і, взагалі кажучи, вважається помилковим[15].

Хоча описаний квантовий комп'ютер може працювати швидше за класичний, він також не здатний розв'язувати задачі, які не можна розв'язати на класичному комп'ютері за наявності достатньої кількості пам'яті та часу (хоча цей об'єм ресурсів може бути недосяжним на практиці). Машина Тюрінга може імітувати квантовий комп'ютер, тому описаний квантовий комп'ютер ніколи не зможе розв'язати таку задачу, як, наприклад, проблему зупинки. Існування «стандартних» квантових комп'ютерів не спростовує тези Черча — Тюрінга. Припускалося, що теорії квантової гравітації, такі, як М-теорія та петльова квантова гравітація, дозволяють побудувати навіть швидші комп'ютери. Але в даний час визначення обчислення в квантовій гравітації є відкритою проблемою у зв'язку з проблемою часу: не існує очевидного способу описати, що для спостерігача означає ввести вхідні дані до комп'ютера, а потім отримати результат.

Мови програмування

Докладніше: Квантове програмування

Для програмування квантових комп'ютерів створені спеціалізовані мови програмування, які дозволяють запис квантового алгоритму з використанням конструкцій високого рівня[16]. Завдання квантових мов не полягає у тому, щоб надати інструмент для програмістів, а в тому, щоб надати інструменти для дослідників, щоб зрозуміти краще, як працюють квантові обчислення і як формально доводити коректність квантових алгоритмів.

Можна виділити дві основні групи квантових мов програмування: імперативні квантові мови програмування і функційні квантові мови програмування. Найвідомішими представниками першої групи є QCL[17] і LanQ.[18]

Ведеться робота з розробки функційних мов програмування для квантових обчислень. Приклади включають QPL Селінджера,[19] і Haskell-подібну мову QML, розроблену Алтенкірчом і Ґретажем.[20][21] Квантові мови програмування високого рівня, засновані на лямбда-численні, були запропоновані ван Тондером,[22] Селінджером і Валіроном[23] Аріґі і Довеком[24].

Примітки

  1. Шаблон:±. Quantum Theory, the Church-Turing Principle and the Universal Quantum Computer // Proc. R. Soc. Lond A. — 1985. — Шаблон:Бскор. — Шаблон:Бскор. (рос. переклад: )
  2. Шаблон:±. Simulating physics with computers // International Journal of Theoretical Physics. — 1982. — Шаблон:Бскор, Шаблон:Бскор. — Шаблон:Бскор. (рос. переклад: )
  3. Шаблон:±. Quantum mechanical computers // Foundations of Physics. — 1986. — Шаблон:Бскор, Шаблон:Бскор. — Шаблон:Бскор. (рос. переклад: )
  4. Шаблон:±. Space-time structure in high energy interactions // Fundamental Interactions at High Energy. — 1969. — Шаблон:Бскор.
  5. Шаблон:±. On the power of quantum computation // Foundations of Computer Science, 1994 Proceedings., 35th Annual Symposium. — Шаблон:Бскор.
  6. Шаблон:Публікація
  7. Слід зазначити, що у цьому випадку ми розглядаємо лише чисті стани кубіта, тобто такі стани, що повністю визначені з точки зору квантової механіки. Взагалі кажучи, стан кубіта може бути мішаним — некогерентною сумішшю декількох чистих станів, що не може бути описана окремим вектором стану. В такому випадку для опису кубіта використовується формалізм матриці густини.
  8. Ошибка Lua: не удаётся создать процесс: proc_open(/var/log/nginx/wikiinfo_lua.error.log): failed to open stream: Permission denied
  9. Ошибка Lua: не удаётся создать процесс: proc_open(/var/log/nginx/wikiinfo_lua.error.log): failed to open stream: Permission denied
  10. Ошибка Lua: не удаётся создать процесс: proc_open(/var/log/nginx/wikiinfo_lua.error.log): failed to open stream: Permission denied
  11. Ошибка Lua: не удаётся создать процесс: proc_open(/var/log/nginx/wikiinfo_lua.error.log): failed to open stream: Permission denied
  12. Оптичний чип дозволяє новий підхід до квантових обчислень Обнаружена петля в шаблонах: Шаблон:Ref-info
  13. Шаблон:Публікація
  14. 15,0 15,1 Шаблон:±. Quantum Complexity Theory // SIAM Journal on Computing. — 1997. — Шаблон:Бскор, Шаблон:Бскор. — Шаблон:Бскор. — DOI:10.1137/S0097539796300921.
  15. Ошибка Lua: не удаётся создать процесс: proc_open(/var/log/nginx/wikiinfo_lua.error.log): failed to open stream: Permission denied
  16. Ошибка Lua: не удаётся создать процесс: proc_open(/var/log/nginx/wikiinfo_lua.error.log): failed to open stream: Permission denied
  17. Ошибка Lua: не удаётся создать процесс: proc_open(/var/log/nginx/wikiinfo_lua.error.log): failed to open stream: Permission denied
  18. Пітер Селінджер, «На шляху до квантової мови програмування», Mathematical Structures in Computer Science(Математичні структури в інформатиці) 14(4):527-586, 2004.
  19. Джонатан Ґретаж Дослідження QBL
  20. T. Altenkirch, V. Belavkin, J. Grattage, A. Green, A. Sabry, J. K. Vizzotto, QML: Функціональна мова програмування Quantum Шаблон:Webarchive
  21. Андре ван Тондер, «Лямбда-числення для квантових обчислень», SIAM J. Comput., 33(5), 1109—1135. (27 стор.), 2004. Також доступна за посиланням arXiv: quant-ph/0307150
  22. Peter Selinger and Benoît Valiron, «A lambda calculus for quantum computation with classical control», Mathematical Structures in Computer Science 16(3):527-552, 2006.
  23. Pablo Arrighi, Gilles Dowek, «Лінійно-алгебраїчне лямбда-числення. високий порядок, кодування і збіжність», 2006

Література

Посилання

Шаблон:Sister

Шаблон:Квантовий комп'ютер Шаблон:Перспективні технології Шаблон:Інформатика

Категорія:Квантова електроніка Категорія:Квантовий комп'ютер Категорія:Теоретична інформатика