WikiSort.ru - Не сортированное

Кубиты

Идея квантовых вычислений состоит в том, что квантовая система из L двухуровневых квантовых элементов (квантовых битов, кубитов) имеет 2^L линейно независимых состояний, а значит, вследствие принципа квантовой суперпозиции, пространство состояний такого квантового регистра является 2^L-мерным гильбертовым пространством. Операция в квантовых вычислениях соответствует повороту вектора состояния регистра в этом пространстве. Таким образом, квантовое вычислительное устройство размером L кубитов фактически задействует одновременно 2^L классических состояний.

Физическими системами, реализующими кубиты, могут быть любые объекты, имеющие два квантовых состояния: поляризационные состояния фотонов, электронные состояния изолированных атомов или ионов, спиновые состояния ядер атомов, и т. д.

Один классический бит может находиться в одном и только в одном из состояний ${\displaystyle |0\rangle }$ или ${\displaystyle |1\rangle }$ . Квантовый бит, называемый кубитом, находится в состоянии ${\displaystyle |\psi \rangle =a\,|0\rangle +b\,|1\rangle }$ , так что |a|² и |b|² — вероятности получить 0 или 1 соответственно при измерении этого состояния; ${\displaystyle a,b\in \mathbb {C} }$ ; |a|² + |b|² = 1. Сразу после измерения кубит переходит в базовое квантовое состояние, соответствующее классическому результату.

Пример:

Имеется кубит в квантовом состоянии ${\displaystyle {\tfrac {4}{5}}\,|0\rangle -{\tfrac {3}{5}}\,|1\rangle }$

В этом случае вероятность получить при измерении

0	составляет	(4/5)² = 16/25	= 0,64,
1	составляет	(−3/5)² = 9/25	= 0,36.

В данном случае при измерении мы получили 0 с вероятностью 0,64.

В результате измерения кубит переходит в новое квантовое состояние ${\displaystyle |0\rangle }$ , то есть при следующем измерении этого кубита мы получим 0 с единичной вероятностью (предполагается, что по умолчанию унитарная операция тождественна; в реальных системах это не всегда так).

Приведём для объяснения два примера из квантовой механики: 1) фотон находится в состоянии ${\displaystyle |\psi \rangle }$ суперпозиции двух поляризаций. Это состояние есть вектор в двумерной плоскости, систему координат в которой можно представлять как две перпендикулярные оси, так что ${\displaystyle a}$ и ${\displaystyle b}$ есть проекции ${\displaystyle |\psi \rangle }$ на эти оси; измерение раз и навсегда коллапсирует состояние фотона в одно из состояний ${\displaystyle |0\rangle }$ или ${\displaystyle |1\rangle }$ , причём вероятность коллапса равна квадрату соответствующей проекции. Полная вероятность получается по теореме Пифагора.

Перейдём к системе из двух кубитов. Измерение каждого из них может дать 0 или 1. Поэтому у системы есть 4 классических состояния: 00, 01, 10 и 11. Аналогичные им базовые квантовые состояния: ${\displaystyle |00\rangle ,|01\rangle ,|10\rangle ,|11\rangle }$ . И наконец, общее квантовое состояние системы имеет вид ${\displaystyle |\Psi \rangle =a\,|00\rangle +b\,|01\rangle +c\,|10\rangle +d\,|11\rangle }$ . Теперь |a|² — вероятность измерить 00 и т. д. Отметим, что |a|² + |b|² + |c|² + |d|² = 1 как полная вероятность.

Если мы измерим только первый кубит квантовой системы, находящейся в состоянии ${\displaystyle |\Psi \rangle }$ , у нас получится:

1. С вероятностью ${\displaystyle p_{0}=|a|^{2}+|b|^{2}}$ первый кубит перейдёт в состояние ${\displaystyle |0\rangle }$ , а второй — в состояние ${\displaystyle {\tfrac {1}{\sqrt {|a|^{2}+|b|^{2}}}}(a\,|0\rangle +b\,|1\rangle )}$ ,
2. С вероятностью ${\displaystyle p_{1}=|c|^{2}+|d|^{2}}$ первый кубит перейдёт в состояние ${\displaystyle |1\rangle }$ , а второй — в состояние ${\displaystyle {\tfrac {1}{\sqrt {|c|^{2}+|d|^{2}}}}(c\,|0\rangle +d\,|1\rangle )}$ .

В первом случае измерение даст состояние ${\displaystyle |\Psi _{0}\rangle =|0\rangle \otimes {\tfrac {1}{\sqrt {|a|^{2}+|b|^{2}}}}(a\,|0\rangle +b\,|1\rangle )}$ , во втором — состояние ${\displaystyle |\Psi _{1}\rangle =|1\rangle \otimes {\tfrac {1}{\sqrt {|c|^{2}+|d|^{2}}}}(c\,|0\rangle +d\,|1\rangle )}$ .

Мы снова видим, что результат такого измерения невозможно записать как вектор в гильбертовом пространстве состояний. Такое состояние, в котором участвует наше незнание о том, какой же результат получится на первом кубите, называют смешанным состоянием. В нашем случае такое смешанное состояние называют проекцией исходного состояния ${\displaystyle |\Psi \rangle }$ на второй кубит и записывают в виде матрицы плотности вида ${\displaystyle \rho _{2}=p_{0}\rho _{\Psi _{0}}+p_{1}\rho _{\Psi _{1}}}$ , где матрица плотности состояния ${\displaystyle |\psi \rangle }$ определяется как ${\displaystyle |\psi \rangle \langle \psi |}$ .

В общем случае системы из L кубитов у неё 2^L классических состояний (00000… (L нулей), …00001 (L цифр), … , 11111… (L единиц)), каждое из которых может быть измерено с вероятностями 0—1.

Таким образом, одна операция над группой кубитов вычисляется сразу над всеми возможными её значениями, в отличие от группы классических битов, когда может быть использовано лишь одно текущее значение. Это и обеспечивает беспрецедентный параллелизм вычислений.

Вычисление

Упрощённая схема вычисления на квантовом компьютере выглядит так: берётся система кубитов, на которой записывается начальное состояние. Затем состояние системы или её подсистем изменяется посредством унитарных преобразований, выполняющих те или иные логические операции. В конце измеряется значение, и это результат работы компьютера. Роль проводов классического компьютера играют кубиты, а роль логических блоков классического компьютера играют унитарные преобразования. Такая концепция квантового процессора и квантовых логических вентилей была предложена в 1989 году Дэвидом Дойчем. Также Дэвид Дойч в 1995 году нашёл универсальный логический блок, с помощью которого можно выполнять любые квантовые вычисления.

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

С помощью базовых квантовых операций можно симулировать работу обычных логических элементов, из которых сделаны обычные компьютеры. Поэтому любую задачу, которая решена сейчас, любой квантовый компьютер решит, и почти за такое же время^[10].

Большая часть современных ЭВМ работают по такой же схеме: n битов памяти хранят состояние и каждый такт времени изменяются процессором. В квантовом случае система из n кубитов находится в состоянии, являющемся суперпозицией всех базовых состояний, поэтому изменение системы касается всех 2ⁿ базовых состояний одновременно. Теоретически новая схема может работать намного (в экспоненциальное число раз) быстрее классической. Практически, например, квантовый алгоритм Гровера поиска в базе данных показывает квадратичный прирост мощности против классических алгоритмов

Алгоритмы

• Алгоритм Гровера позволяет найти решение уравнения ${\displaystyle f(x)=1,\ 0\leqslant x<N}$ за время ${\displaystyle O({\sqrt {N}})}$ .
• Алгоритм Шора позволяет разложить натуральное число n на простые множители за полиномиальное от log n время.
• Алгоритм Залки — Визнера позволяет моделировать унитарную эволюцию квантовой системы ${\displaystyle n}$ частиц за почти линейное время с использованием ${\displaystyle O(n)}$ кубитов.
• Алгоритм Дойча — Йожи позволяет «за одно вычисление» определить, является ли функция двоичной переменной f(n) постоянной (f₁(n) = 0, f₂(n) = 1 независимо от n) или «сбалансированной» (f₃(0) = 0, f₃(1) = 1; f₄(0) = 1, f₄(1) = 0).
• Алгоритм Саймона^[en] решает проблему чёрного ящика экспоненциально быстрее, чем любой классический алгоритм, включая вероятностные алгоритмы.

Было показано, что не для всякого алгоритма возможно «квантовое ускорение». Более того, возможность получения квантового ускорения для произвольного классического алгоритма является большой редкостью^[11].

Пример реализации операции CNOT на зарядовых состояниях электрона в квантовых точках

Любая квантовая операция может быть реализована при помощи логического вентиля «контролируемое отрицание» (CNOT) и поворота состояния одного кубита^[12][13].

Один кубит можно представить в виде электрона в двухъямном потенциале, так что ${\displaystyle |0\rangle }$ означает нахождение его в левой яме, а ${\displaystyle |1\rangle }$  — в правой. Это называется кубит на зарядовых состояниях. Общий вид квантового состояния такого электрона: ${\displaystyle |\Psi \rangle =\lambda _{0}|0\rangle +\lambda _{1}|1\rangle }$ . Зависимость его от времени есть зависимость от времени амплитуд ${\displaystyle \lambda _{0},\lambda _{1}}$ ; она задаётся уравнением Шрёдингера вида ${\displaystyle i\hbar {\tfrac {\partial }{\partial t}}\Psi =H\Psi }$ , где гамильтониан ${\displaystyle H}$ имеет в силу одинакового вида ям и эрмитовости вид ${\displaystyle {\begin{pmatrix}a&-a\\-a&a\end{pmatrix}}}$ для некоторой константы ${\displaystyle a}$ , так что вектор ${\displaystyle |{\tilde {0}}\rangle ={\tfrac {1}{\sqrt {2}}}(|0\rangle +|1\rangle )}$ есть собственный вектор этого гамильтониана с собственным значением 0 (так называемое основное состояние), а ${\displaystyle |{\tilde {1}}\rangle ={\tfrac {1}{\sqrt {2}}}(|0\rangle -|1\rangle )}$  — собственный вектор со значением ${\displaystyle 2a}$ (первое возбуждённое состояние). Никаких других собственных состояний (с определённым значением энергии) здесь нет, так как наша задача двумерная.

Поскольку каждое состояние ${\displaystyle |\Psi \rangle }$ переходит за время ${\displaystyle t}$ в состояние ${\displaystyle \lambda _{0}\exp(0t)|{\tilde {0}}\rangle +\lambda _{1}\exp(-2at/\hbar )|{\tilde {1}}\rangle }$ , то для реализации операции NOT (перехода ${\displaystyle |0\rangle \to |1\rangle }$ и наоборот достаточно просто подождать время ${\displaystyle t=\pi \hbar /(2a)}$ . То есть операция NOT реализуется просто естественной квантовой эволюцией кубита при условии, что внешний потенциал задаёт двухъямную структуру; это делается с помощью технологии квантовых точек.

Для реализации CNOT надо расположить два кубита (то есть две пары ям) перпендикулярно друг другу и в каждой из них расположить по отдельному электрону. Тогда константа ${\displaystyle a}$ для первой (управляемой) пары ям будет зависеть от того, в каком состоянии находится электрон во второй (управляющей) паре ям: если ближе к первой, то ${\displaystyle a}$ будет больше, если дальше — меньше. Поэтому состояние электрона во второй паре определяет время совершения NOT в первой яме, что позволяет снова выбрать нужную длительность времени для реализации операции CNOT.

Эта схема очень приблизительная и идеализирована; реальные схемы сложнее и их реализация представляет вызов экспериментальной физике.

Квантовая телепортация

Алгоритм телепортации реализует точный перенос состояния одного кубита (или системы) на другой. В простейшей схеме используются 3 кубита: телепортируемый кубит и запутанная пара, один кубит которой находится на другой стороне. Отметим, что в результате работы алгоритма первоначальное состояние источника разрушится — это пример действия общего принципа невозможности клонирования — невозможно создать точную копию квантового состояния, не разрушив оригинал. Не получится скопировать произвольное состояние, и телепортация — замена этой операции.

Телепортация позволяет передавать квантовое состояние системы с помощью обычных классических каналов связи. Таким образом можно, в частности, получить связанное состояние системы, состоящей из подсистем, удалённых на большое расстояние.

Приложения к криптографии

Благодаря огромной скорости разложения на простые множители квантовый компьютер позволит расшифровывать сообщения, зашифрованные широко применяемым криптографическим алгоритмом RSA. До сих пор этот алгоритм считается сравнительно надёжным, так как эффективный способ разложения чисел на простые множители для классического компьютера в настоящее время неизвестен. Для того, например, чтобы получить доступ к кредитной карте^{[прояснить]}, нужно разложить на два простых множителя число длиной в сотни цифр (даже для суперкомпьютеров выполнение этой задачи заняло бы в сотни раз больше времени, чем возраст Вселенной). Благодаря квантовому алгоритму Шора эта задача становится вполне осуществимой, если квантовый компьютер будет построен.

Применение идей квантовой механики уже открыло новую эпоху в области криптографии, так как методы квантовой криптографии открывают новые возможности в области передачи сообщений^[14]. Прототипы систем подобного рода находятся на стадии разработки^[15].

Исследования в области искусственного интеллекта

Квантовые компьютеры в теории хорошо подходят для нужд машинного обучения. Они манипулируют большими объёмами данных за один проход и способны моделировать нейронную сеть экспоненциального размера^[16]. В 2013 году корпорация Google объявила об открытии лаборатории по квантовым исследованиям в области искусственного интеллекта^[10]. Концерн Volkswagen ведёт исследования в сфере применения квантовых компьютеров для разработки беспилотного автомобиля и новых типов аккумуляторных батарей (используя квантовые компьютеры Google и D-Wave). В ноябре 2018 года концерн объявил о разработке системы управления дорожным движением (с интеграцией в неё беспилотных машин), работающей с использованием квантовых компьютеров D-Wave.^[17][18]

Молекулярное моделирование

Предполагается, что с помощью квантовых компьютеров станет возможно точное моделирование молекулярных взаимодействий и химических реакций. Химические реакции являются квантовыми по своей природе. Для классических компьютеров доступен обсчёт поведения только относительно простых молекул.^[19] По прогнозам экспертов, моделирование на квантовых компьютерах открывает новые перспективы для развития химической отрасли, в частности, при создании лекарств.^[20]

Принципы физической реализации

Главные технологии для квантового компьютера:

1. Твердотельные квантовые точки на полупроводниках: в качестве логических кубитов используются либо зарядовые состояния (нахождение или отсутствие электрона в определённой точке), либо направление электронного и/или ядерного спина в данной квантовой точке. Управление через внешние потенциалы или лазерным импульсом.
2. Сверхпроводящие элементы (джозефсоновские переходы, СКВИДы и др.). В качестве логических кубитов используются присутствие/отсутствие куперовской пары в определённой пространственной области. Управление: внешний потенциал/магнитный поток.
3. Ионы в вакуумных ловушках Пауля^[en] (или атомы в оптических ловушках). В качестве логических кубитов используются основное/возбуждённое состояния внешнего электрона в ионе. Управление: классические лазерные импульсы вдоль оси ловушки или направленные на индивидуальные ионы + колебательные моды ионного ансамбля. Эту схему предложили в 1994 году Петер Цоллер и Хуан Игнасио Сирак^[13][25].
4. Смешанные технологии: использование заранее приготовленных запутанных состояний фотонов для управления атомными ансамблями или как элементы управления классическими вычислительными сетями.

Основные проблемы, связанные с созданием и применением квантовых компьютеров:

• необходимо обеспечить высокую точность измерений;
• внешние воздействия (включая передачу полученных результатов) могут разрушить квантовую систему или внести в неё искажения.

Чем больше кубитов находятся в связанном состоянии, тем менее стабильной является система. Для достижения «квантового превосходства» требуется компьютер со многими десятками связанных кубитов, работающими стабильно и с малым числом ошибок. Вопрос о том, до какой степени возможно масштабирование такого устройства (так называемая «проблема масштабирования»), является предметом новой интенсивно развивающейся области — многочастичной квантовой механики. Центральным здесь является вопрос о природе декогерентности (точнее, о коллапсе волновой функции), который пока остаётся открытым. Различные трактовки этого процесса можно найти в книгах^[26][27][28].

На рубеже XX—XXI веков во многих научных лабораториях были созданы однокубитные квантовые процессоры (по существу, управляемые двухуровневые системы, о которых можно было предполагать возможность масштабирования на много кубитов).

Экспериментальные образцы

В конце 2001 года IBM заявила об успешном тестировании 7-кубитного квантового компьютера, реализованного с помощью ЯМР. На нём был исполнен алгоритм Шора и были найдены сомножители числа 15^[29].

В 2005 году группой Ю. Пашкина (кандидат физ.-мат. наук, старший научный сотрудник лаборатории сверхпроводимости г. Москвы) при помощи японских специалистов был построен двухкубитный квантовый процессор на сверхпроводящих элементах^[30].

В ноябре 2009 года физикам из Национального института стандартов и технологий в США впервые удалось собрать программируемый квантовый компьютер, состоящий из двух кубитов^[31].

В феврале 2012 года компания IBM сообщила о достижении значительного прогресса в физической реализации квантовых вычислений с использованием сверхпроводящих кубитов, соединённых с кремниевыми чипами, что, по мнению компании, позволит начать работы по созданию квантового компьютера^[32].

В апреле 2012 года группе исследователей из Южно-Калифорнийского университета, Технологического университета Дельфта, университета штата Айова, и Калифорнийского университета, Санта-Барбара, удалось построить двухкубитный квантовый компьютер на кристалле алмаза с примесями. Компьютер функционирует при комнатной температуре и теоретически является масштабируемым. В качестве двух логических кубитов использовались направления спина электрона и ядра азота соответственно. Для обеспечения защиты от влияния декогерентности была разработана целая система, которая формировала импульс микроволнового излучения определённой длительности и формы. При помощи этого компьютера реализован алгоритм Гровера для четырёх вариантов перебора, что позволило получить правильный ответ с первой попытки в 95 % случаев^[33][34].

В июле 2017 года группа физиков под руководством Михаила Лукина, сооснователя Российского квантового центра и профессора Гарвардского университета, создала программируемый 51-кубитный квантовый симулятор^[35]. Это самая сложная подобная система из существующих на тот момент. Авторы проверили работоспособность симулятора моделированием сложной системы из множества частиц — это позволило физикам предсказать некоторые ранее неизвестные эффекты^[36]. Примерно в это же время другая группа ученых из университета Мэриленд под руководством Кристофера Монро^[en] создала 53-кубитный симулятор, основанный на ионах в оптической ловушке^[37][38]. Однако обе эти системы не являются универсальным компьютером, а созданы для решения одной задачи^[39][37].

В ноябре 2017 года учёные IBM успешно построили и испытали прототип процессора с 50 кубитами^[40][41][42].

В январе 2018 года исполнительный директор компании Intel Брайан Кржанич сообщил о создании сверхпроводящего квантового чипа под кодовым именем «Tangle Lake», обладающего 49 кубитами. По его прогнозу, квантовые компьютеры помогут в создании лекарств, финансовом моделировании и составлении прогнозов погоды. Intel ведёт разработки квантовых компьютеров по двум направлениям: создание устройств на сверхпроводниках и кремниевых чипов со «спиновыми кубитами»^[43][44]

В марте 2018 года компания Google объявила, что ей удалось построить 72-кубитный квантовый процессор Bristlecone, имеющий низкую вероятность ошибок в вычислениях. Компания не раскрыла подробных характеристик устройства, однако утверждает, что оно позволяет достичь «квантового превосходства». Согласно специалистам Google, для того чтобы квантовый компьютер мог решать задачи, недоступные для «обычных» компьютеров, требуется соблюдение следующих условий: в его состав должно входить не менее 49 кубитов, «глубина» (англ. circuit depth) должна превышать 40 кубитов, а вероятность ошибки в двухкубитном логическом элементе должна быть не выше 0,5 %. Для построенного компьютера эти требования выполняются, за исключением доли ошибок (она составляет 0,6 %).^[45][46]

Адиабатические компьютеры D-Wave

Канадская компания D-Wave Systems с 2007 года заявляла о создании различных вариантов квантового компьютера: от 16-кубитного до 2000-кубитного. Компьютеры D-Wave пригодны для решения лишь узкого класса задач. Некоторые исследователи высказывали сомнения, что в компьютерах компании действительно достигается существенное «квантовое ускорение», однако компьютеры D-Wave (предлагаемые по ценам 10—15 млн USD) покупались компаниями Google, Lockheed Martin и Temporal Defense Systems, а также агентством NASA и Лос-Аламосской национальной лабораторией.^[47][48]

В декабре 2015 года специалисты компании Google подтвердили, что, согласно их исследованию, компьютер D-Wave использует квантовые эффекты. При этом в «1000-кубитном» компьютере кубиты в действительности организованы в кластеры по 8 кубитов каждый. Тем не менее, это позволило добиться быстродействия в 100 млн раз больше (по сравнению с обычным компьютером) в одном из алгоритмов.^[49]

Статьи

• Опенов Л. А. Спиновые логические вентили на основе квантовых точек // Соросовский образовательный журнал, 2000, т. 6, № 3, с. 93-98;
• G. Brassard, I. Chuang, S. Lloyd, C. Monroe. Quantum computing // PNAS. — 1998. — Vol. 95. — P. 11032—11033.
• Килин С. Я. Квантовая информация // УФН. — 1999. — Т. 169. — C. 507—527.
• Валиев К. А. Квантовые компьютеры: можно ли их сделать «большими»? // УФН. — 1999. — Т. 169. — C. 691—694.
• A. M. Steane, E. G. Rieffel. Beyond Bits: The Future of Quantum Information Processing // IEEE Computer. — January 2000. — P. 38—45.
• Kilin S.Ya. Quanta and information // Progress in optics. — 2001. — Vol. 42. — P. 1-90.
• Валиев К. А. Квантовые компьютеры и квантовые вычисления // УФН. — 2005. — Т. 175. — C. 3—39.
• T. D. Ladd, F. Jelezko, R. Laflamme, Y. Nakamura, C. Monroe, J. L. O’Brien. Quantum Computing // Nature. — 2010. — Vol. 464. — P. 45—53.
• Квантовый компьютер и квантовые вычисления. Глав. ред. В. А. Садовничий, Ижевск: ИЖТ, 1999. — 288с.

Книги

• Квантовые вычисления за и против / Под ред. Садовничего В. А.
• Квантовый компьютер и квантовые вычисления / Под ред. Садовничего В. А.
• Баумейстер Д., Экерт А., Цайлингер А. Физика квантовой информации. — М.: Постмаркет, 2002. — 376 с.
• Валиев К. А., А. А. Кокин. Квантовые компьютеры: надежды и реальность. — Ижевск: РХД, 2004. — 320 с.
• Дойч Д. Структура реальности. — Ижевск: РХД, 2001. — 400 с.
• Кайе Ф., Лафламм Р., Моска М. Введение в квантовые вычисления. — Ижевск: РХД, 2009. — 360 с.
• Китаев А., Шень А., Вялый М. Классические и квантовые вычисления. — М.: МЦНМО, 1999. — 192 с. (недоступная ссылка)
• Нильсен М., Чанг И. Квантовые вычисления и квантовая информация. — М.: Мир, 2006. — 824 с.
• Ожигов Ю. И. Квантовые вычисления. — М.: Макс Пресс, 2003. — 152 с.
• Ожигов Ю. И. Конструктивная физика. — Ижевск: РХД, 2010. — 424 с.
• Прескилл Дж. Квантовая информация и квантовые вычисления. — Ижевск: РХД, 2008-2011. — 464+312 с.
• Скотт Ааронсон. Квантовые вычисления со времен Демокрита = Scott Aaronson. Quantum Computing since Democritus. — М.: Альпина Нон-фикшн, 2017. — 494 p. — ISBN 978-5-91671-751-8. (Сайт курса - https://www.scottaaronson.com/democritus/)