Квантовые вычисления — это простые слова и Квантовый алгоритм

Хронология квантовых вычислений

Текущая версия страницы пока не проверялась опытными участниками и может значительно отличаться от версии, проверенной 21 сентября 2021 года; проверки требуют 7 правок.

Идея квантовых вычислений была независимо предложена Юрием Маниным и Ричардом Фейнманом в начале 1980-х. С тех пор была проделана колоссальная работа для построения работающего квантового компьютера.

1960-еПравить

• представил вентиль Тоффоли, который является популярным квантовым вентилем при построении обратимых схем квантовых компьютеров.
• 1984 — Чарльз Беннетом и Жилем Брассард предложили первый протокол квантового распределения ключа — BB84.
• 1985 — Дэвид Дойч впервые описал квантовую машину Тьюринга.

1990-еПравить

• 2000Первый работающий пяти кубитный ЯМР-компьютер был продемонстрирован в Мюнхенском техническом университете.Первое выполнение нахождения порядка (что является важной частью алгоритма Шора) продемонстрировано в исследовательском центре компании IBM и в Стэнфордском университете.Первый работающий семи кубитный ЯМР-компьютер был продемонстрирован в Лос-Аламосской национальной лаборатории
• Первый работающий пяти кубитный ЯМР-компьютер был продемонстрирован в Мюнхенском техническом университете.
• Первое выполнение нахождения порядка (что является важной частью алгоритма Шора) продемонстрировано в исследовательском центре компании IBM и в Стэнфордском университете.
• Первый работающий семи кубитный ЯМР-компьютер был продемонстрирован в Лос-Аламосской национальной лаборатории
• 2001Первое полное выполнение алгоритма Шора продемонстрировано в исследовательском центре компании IBM и в Стэнфордском университете. Число 15 было факторизовано квантовым компьютером, используя массив из 1018 идентичных молекул, каждая из которых содержала семь активных ядерных спинов.
• Первое полное выполнение алгоритма Шора продемонстрировано в исследовательском центре компании IBM и в Стэнфордском университете. Число 15 было факторизовано квантовым компьютером, используя массив из 1018 идентичных молекул, каждая из которых содержала семь активных ядерных спинов.

2010-еПравить

• 2019IBM представила первый в мире коммерческий квантовый компьютер — IBM Q System One.
• IBM представила первый в мире коммерческий квантовый компьютер — IBM Q System One.

2020-еПравить

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

ВведениеПравить

История квантовых вычислений началась в начале 1980-х годов, когда физик Пол Бениофф предложил квантово-механическую модель машины Тьюринга в 1980 году.

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

Квантовый компьютер использует для вычисления не обычные (классические) алгоритмы, а процессы квантовой природы, так называемые квантовые алгоритмы, использующие квантовомеханические эффекты, — такие как квантовый параллелизм и квантовая запутанность.

Если классический процессор в каждый момент может находиться ровно в одном из состояний   (обозначения Дирака), то квантовый процессор в каждый момент находится одновременно во всех этих базисных состояниях, при этом в каждом состоянии   — со своей комплексной амплитудой  . Это квантовое состояние называется «квантовой суперпозицией» данных классических состояний и обозначается как

Квантовое состояние   может изменяться во времени двумя принципиально различными путями:

• Унитарная квантовая операция (квантовый вентиль, англ. ), в дальнейшем просто операция.
• Измерение (наблюдение).

Если классические состояния   есть пространственные положения группы электронов в квантовых точках, управляемых внешним полем  , то унитарная операция есть решение уравнения Шрёдингера для этого потенциала.

Измерение есть случайная величина, принимающая значения   с вероятностями   соответственно. В этом состоит квантовомеханическое правило Борна. Измерение есть единственная возможность получения информации о квантовом состоянии, так как значения   нам непосредственно недоступны. Измерение квантового состояния не может быть сведено к унитарной шрёдингеровской эволюции, так как, в отличие от последней, оно необратимо. При измерении происходит так называемый коллапс волновой функции  , физическая природа которого до конца не ясна. Спонтанные вредоносные измерения состояния в ходе вычисления ведут к декогерентности, то есть отклонению от унитарной эволюции, что является главным препятствием при построении квантового компьютера (см. физические реализации квантовых компьютеров).

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

ТеорияПравить

Основная статья: Кубит

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

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

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

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

Если измерить только первый кубит квантовой системы, находящейся в состоянии  , получится:

• с вероятностью   первый кубит перейдёт в состояние  , а второй — в состояние  ,
• с вероятностью   первый кубит перейдёт в состояние  , а второй — в состояние  .

В первом случае измерение даст состояние  , во втором — состояние  .

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

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

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

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

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

Основные квантовые алгоритмы:

• алгоритм Гровера: позволяет найти решение уравнения   за время  ;
• алгоритм Шора: позволяет разложить натуральное число n на простые множители за полиномиальное от log n время;
• алгоритм Залки — Визнера позволяет моделировать унитарную эволюцию квантовой системы   частиц за почти линейное время с использованием   кубитов;
• алгоритм Дойча — Йожи позволяет «за одно вычисление» определить, является ли функция двоичной переменной f(n) постоянной (f1(n) = 0, f2(n) = 1 независимо от n) или «сбалансированной» (f3(0) = 0, f3(1) = 1; f4(0) = 1, f4(1) = 0);
• решает проблему чёрного ящика экспоненциально быстрее, чем любой классический алгоритм, включая вероятностные алгоритмы.

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

Один кубит можно представить в виде электрона в двухъямном потенциале, так что   означает нахождение его в левой яме, а   — в правой. Это называется кубит на зарядовых состояниях. Общий вид квантового состояния такого электрона:  . Зависимость его от времени есть зависимость от времени амплитуд  ; она задаётся уравнением Шрёдингера вида  , где гамильтониан   имеет в силу одинакового вида ям и эрмитовости вид
  для некоторой константы  , так что вектор   есть собственный вектор этого гамильтониана с собственным значением 0 (так называемое основное состояние), а   — собственный вектор со значением   (первое возбуждённое состояние). Никаких других собственных состояний (с определённым значением энергии) здесь нет, так как наша задача двумерная.

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

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

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

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

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

Возможные примененияПравить

Практическое осуществление квантового компьютера основано на манипулировании на микроскопическом уровне и с грандиозной точностью многоэлементной физической системой с непрерывными степенями свободы. Очевидно, что для достаточно большой системы, квантовой или классической, эта задача становится невыполнимой, именно поэтому такие системы переходит из ведения микроскопической физики в область статистической физики. Представляет ли система из N = 103÷105 квантовых спинов, необходимая чтобы превзойти классический компьютер в решении ограниченного числа специальных задач, достаточно большой в этом смысле? Сможем ли мы когда-либо научиться контролировать 10300 (по меньшей мере) амплитуд, определяющих квантовое состояние такой системы? Мой ответ — нет, никогда.

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

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

• Твердотельные квантовые точки на полупроводниках: в качестве логических кубитов используются либо зарядовые состояния (нахождение или отсутствие электрона в определённой точке), либо направление электронного и/или ядерного спина в данной квантовой точке. Управление через внешние потенциалы или лазерным импульсом.
• Сверхпроводящие элементы (джозефсоновские переходы, СКВИДы и др.). В качестве логических кубитов используются присутствие/отсутствие куперовской пары в определённой пространственной области. Управление: внешний потенциал/магнитный поток.
• Смешанные технологии: использование заранее приготовленных запутанных состояний фотонов для управления атомными ансамблями или как элементы управления классическими вычислительными сетями.

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

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

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