Квантовые алгоритмы

ЛЕКЦИЯ 19. Квантовые алгоритмы

19.1 В чем проблема?

19.2 Компьютерное моделирование физических процессов. Дискретизация. Ограничение, накладываемое на классический компьютер. Полиномиальный класс задач Р.

19.3 Моделирование времени. Алгоритм клеточного автомата.

19.4 Моделирование вероятности. Экспоненциальный рост объема вычислительного устройства. Класс задач NP.

19.5 Элементарные логические операции над кубитами. Унитарность. Формализм операторов рождения и уничтожения.

19.6 Моделирование квантовых эффектов. Квантовый компьютер и построение его гамильтониана. Эволюция состояния К.К. Программный счетчик (курсор)

19.7  Недостатки компьютера и необратимые потери энергии.

19.8 Квантовый регистр. Случай N кубитов.

Рекомендуемые материалы

Говоря о квантовых алгоритмах, как о наборе вычислительных процедур, основанных на законах квантовой механики, в первую очередь хотелось бы остановиться на принципиальном вопросе об обоснованности таких вычислений вообще. Впервые, по-видимому это было сделано Ричардом Фейнманом в начале 80-ых годов. Вопрос, который он ставил звучал приблизительно так: как построить гамильтониан физической системы, которую можно рассматривать в качестве компьютера?

Прежде чем ответить на этот вопрос, рассмотрим сами предпосылки обращения к квантовой механике как к теории, способной дать новые вычислительные алгоритмы.

О каком же компьютере идет речь, когда говорят о моделировании законов физики? В науке о вычислениях обычно не рассматривается вопрос о конкретном вычислительном устройстве - речь идет об универсальном компьютере. Поэтому вопрос перефразируется так - могут ли законы физики быть смоделированы при помощи универсального компьютера? Будем считать, что элементы такого компьютера локально соединены между собой, но пусть это не будет бесконечно большое число соединений.

Какого рода физические законы мы хотим моделировать на этом компьютере? Прежде всего - законы в классическом приближении, когда работают локальные дифференциальные уравнения. Но реальный мир - это квантовый мир, поэтому хотелось бы симулировать квантовую физику. Что же за симуляции мы будем рассматривать? Это, конечно, аппроксимационное моделирование, в котором строятся численные алгоритмы решения дифференциальных уравнений. Затем компьютер производит вычисления на основе этих алгоритмов и мы получаем примерное представление о том как работает физика. Это законный подход, но речь пойдет о другом. Хочется говорить о том, насколько возможно точное моделирование, т.е. так как это происходит на самом деле в природе. Если существование такой возможности было бы доказано и такой тип компьютера стал бы реальностью, то оказалось бы, что все, что происходит в ограниченном объеме пространства и времени точно бы анализировалось за ограниченное число логических операций. Очевидно, что существующие физические теории не позволяют сделать это. В противном случае мы бы работали с бесконечно малыми элементами пространства, бесконечно большими длинами волн, суммировались бесконечные ряды и т.д., т.е. если бы такое предположение было бы верным, то законы физики не работали.

Но теперь мы имеем представление о том, как модифицировать законы физики. Например, мы должны изменить наше представление о том, что пространство непрерывно и представлять его как решетку, т.е. ввести дискретизацию. Дискретизация означает, что элемент пространства можно описать конечным числом, а время описывается прерывистыми скачками… Посмотрим каким бы был в этом случае физический мир и как бы представлялась задача о его моделировании. Во-первых, возникла бы проблема того, что скорость света слегка зависела бы от направления; кроме того появились бы другие элементы анизотропии, которые можно было бы зарегистрировать экспериментально. Эта анизотропия могла бы быть очень малой. Конечно, физическое знание всегда неполно и всегда можно сказать, что можно построить модель, выводы которой лежат вне области, доступной на сегодняшний день. Можно предположить, что такая анизотропия будет обнаружена в будущем. С точки зрения физики было бы очень красиво, если можно предсказать новый результат, совместимый с существующими теориями и известными фактами и не находящий пока объяснения, но похоже, таких примеров в настоящее время нет (ситуация в физике в конце XIX начале ХХ века была не такой - имелись экспериментальные результаты, несовместимые с физическими теориями). Поэтому возражений против анизотропии, в принципе, нет. Вопрос только в величине такой анизотропии.

Другой важный момент заключается в том, что законы природы обратимы, а правила компьютерных вычислений - нет. Однако это утверждение может быть оспорено - компьютерные вычисления могут быть сделаны обратимыми и соответствующие методы очень пригодятся нам в дальнейшем. Это то самое место на котором изменяются взаимоотношения между физикой и вычислениями: появляются новые возможности для вычислений. Более того, возможно, что эти новые вычислительные возможности позволят нам понять что-то о физике.

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

Моделирование времени.

Для этого потребуется ввести дискретизацию времени. Известно, что при физических измерениях не может быть достигнута бесконечная точность, поэтому потребуем дискретизацию в масштабах 10^-27сек. При необходимости эта величина может быть сделана еще меньше!

Один из способов моделирования времени состоит в том, что компьютер переходит от состояния к состоянию, например, в модели клеточных автоматов. Такое требование не противоречит нашей интуиции о ходе времени - мы переходим от одного состояния к другому. В этом смысле время невозможно моделировать вообще (как в модели клеточного автомата[1]) - его можно лишь имитировать (есть очевидная разница между имитацией и моделированием - полет шмеля может имитировать каждый, но далеко не каждый знает как построить модель, описывающую этот процесс). Тогда возникает следующий вопрос - можно ли время моделировать, а не имитировать? Представим себе мир с пространственно-временной точки зрения, т.е. когда представляющие точки распределены в пространстве и времени (заглядывая вперед во времени). Тогда мы могли бы сказать, что компьютер работает по правилу: состояние s_i в пространственно-временной точке дается функцией , определенной в некоторых соседних с i точках.

Видно, что если эта функция устроена так, что ее значение в точке i зависит от значения в нескольких точках, находящихся позади во времени (т.е. в более ранние моменты),  то мы просто должны переопределить описание клеточного автомата. Это так, поскольку вы вычисляете какое-то значение в т. i на основе значений в предыдущих точках, а тех - опять в предыдущих точках, значит можно вычислить все следующие значения двигаясь в определенном порядке. Но можно представить себе более сложную модель компьютера, работающего с более общим классом функций - обобщенных связей между пространственно-временными точками. Если F зависит от всех точек как в прошлом, так и в будущем, что будет в этом случае? Как в этом случае можно представить действие физических законов?

Как устроены современные теории. Замечено, что во многих физических теориях соответствующие математические уравнения сильно упрощаются, если, скажем, частицам, разрешается двигаться назад во времени (электрон - позитрон) или вообще существуют связи, соединяющие прошлое и будущее объектов. Можно ли в этом случае построить компьютер, работающий по такому алгоритму? Предположим, что мы знаем такую функцию F_i и эта функция зависит, в том числе, от переменных, расположенных в будущие моменты времени. Как тогда упорядочить данные, чтобы они автоматически удовлетворяли упомянутым выше уравнениям? Может статься, что это вообще невозможно. В случае клеточного автомата это возможно, поскольку из данного ряда можно получить следующий ряд, и затем опять следующий ряд и т.д. - т.е. мы указали способ как это сделать

Тогда,

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

Моделирование вероятности

Говоря о квантовой механике, мы признаем, что здесь имеем дело лишь возможностью предсказывать вероятности.

Один из способов получить компьютер, моделирующий вероятностные теории - описание чего-то, что происходит с определенной вероятностью, - это рассчитать эту вероятность и интерпретировать полученное число для представления реальности. Например, предположим, что частица имеет вероятность P(x, t) находиться в точке х во время t. Типичный случай - когда вероятность удовлетворяет дифференциальному уравнению, скажем уравнению диффузии:

.

Теперь можно дискретизировать время и координату, а, возможно, и саму вероятность и решать это дифференциальное уравнение как мы решаем обычные уравнения теории поля, создавая для этого алгоритм, работающий в дискретной модели. Во первых, здесь появляется проблема с дискретизацией вероятности.  Если мы собираемся ограничиться к цифрами (разрядами), это означает, что когда вероятность какого-нибудь события становится меньше чем 2^-к , то мы говорим, что этого никогда не произойдет. На практике, так оно и есть. Если вероятность события меньше, чем 10^-20, мы говорим, что оно никогда не произойдет или не будет происходить слишком часто. Но на самом деле здесь имеется определенная трудность. Если мы рассматриваем много частиц, скажем, R в системе, то мы должны описывать вероятность при условии, что частицы находятся в точках  в момент t. Так описывается вероятность для системы. Поэтому нам нужно к-разрядное число для каждой конфигурации системы, для каждой из R “конфигураций” величины х. Поэтому, если у нас есть N пространственных точек (в смысле клеточного автомата), нам необходимо описать N^R конфигураций. На самом деле мы считаем, что в каждой точке пространства имеется информация типа электрического поля и проч., поэтому R окажется такого же порядка что и N если количество информации, выраженное в битах, совпадает с числом точек в пространстве. Следовательно, мы получаем порядка N^N конфигураций, которое необходимо описать, для того чтобы получить вероятность. Значит эта величина окажется гораздо большей, чем размер нашего компьютера, который порядка N.

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

Существует ли другая возможность? Мы не можем ожидать вычисления вероятности некой конфигурации для вероятностной теории. Но другой способ моделирования вероятностных процессов в природе состоит в построении компьютера самого по себе описывающегося вероятностным образом! В таком компьютере выход не является однозначной функцией входа. Тогда можно попробовать моделировать природу так: компьютер начинает работу с определенного состояния - начального состояния, если угодно, и приходит к конечному состоянию с той же вероятностью, что и реальный процесс, который начинается с соответствующего начального состояния и приходит к конечному состоянию. Как мы узнаем чему равна вероятность? Мы видим, что природа непредсказуема. Тогда как мы хотим собираемся предсказать результат с помощью компьютера? Мы не можем, это непредсказуемо, если процесс вероятностный. Но что мы действительно можем сделать в вероятностной системе - это повторить эксперимент в природе много раз. Повторяя один и тот же эксперимент в компьютере много раз (что не займет больше времени, чем это занимает в таком же природном процессе) мы получим частоту повторения конечного состояния пропорциональную количеству испытаний с приблизительно таким же исходом (плюс - минус корень из числа испытаний n), как это случается в природе. Другими словами, можно представить машину, которая моделирует природную систему и в которой происходит в точности то же самое, что и в природе. Но если бы мы повторяли определенный эксперимент достаточное число раз, чтобы определить природную вероятность, то мы также можем проделать соответствующий эксперимент и на компьютере и получим соответствующую вероятность с соответствующей точностью (где точность определяется статистикой).

Теперь давайте подумаем о характеристиках локального вероятностного компьютера, который может моделировать природу (под природой будем понимать квантовые системы).  Одна из характеристик - это то, как какая-то величина ведет себя в локальной области в пренебрежении тем, что происходит в других областях. Например, предположим, что имеются переменные в системе, которые описывают весь мир , причем, переменные x_A - это те, которыми интересуемся мы - вокруг нас, а x_B - остальные переменные вселенной. Если нас интересует вероятность того, что что-то произойдет “вокруг нас”, т.е. в т. х_А , мы должны проинтегрировать общую вероятность по “лишним” переменным. Если мы уже вычислили эту вероятность, то нам осталось выполнить интегрирование:

,

что само по себе довольно трудно. Однако если мы симитировали вероятность, это становится очень просто: нам ничего не нужно делать для вычисления интеграла - мы просто отбросим все значения вероятности от переменной х_В, просто глядя на нужную нам область х_А. Следовательно такая величина будет иметь природные характеристики: если она локальна, то можно обнаружить, что происходит в данной области, не посредством интегрирования или какой-нибудь другой процедуры, а  просто отбрасывая все, что происходит в других местах, что вообще не является операцией.

Итак, мы подошли к вопросу о том, как моделировать с помощью компьютера квантово-механические эффекты. Квантовая механика описывает эффекты посредством дифференциальных уравнений относительно волновой функции . Если у нас имеется одна частица,  является функцией x и t и такое дифференциальное уравнение можно смоделировать как то вероятностное уравнения, которое было выписано выше. Так можно моделировать уравнение Шредингера для одной частицы. Но полное описание квантовой механики дается волновой функцией , которая является амплитудой вероятности найти частицы в точках и поэтому не может быть смоделирована на обычном компьютере, как имеющая слишком много переменных. В этом обычном компьютере число элементов пропорционально R или N. Такая же проблема возникает и с вероятностным описанием в классической физике. Как же можно моделировать квантовую механику? Есть два способа это сделать. Можно отказаться от правила, по которому работает компьютер. Мы говорим: давайте сделаем компьютер из квантово-механических элементов, которые удовлетворяют законам квантовой механики. Другой путь такой - пусть компьютер будет логическим универсальным автоматом.

Прежде всего заметим, что законы квантовой физики обратимы во времени, поэтому мы должны рассматривать квантовые вычислительные устройства, подчиняющиеся законам обратимости. Напомним, что одним из выводов науки о вычислениях (computer science) является факт, что универсальное вычислительное устройство может быть сделано на основе соответствующей сложной сети элементарных логических элементов. В классическом компьютере проводники, соединяющие ЛЭ должны быть идеальными, и переносить токи, вызывающие падения напряжения на сопротивлениях, которые соответствуют двум уровням “1” и “0”.

Напоминание о классических вычислениях

Эти элементарные логические элементы могут быть лишь элементами “NOT” и “AND”. На самом деле достаточно лишь одного элемента “NAND = NOT  AND”, который при наличии на одном входе единицы выполняет операцию NOT  над значением другого входа. Эти элементы показаны на рис. 1. Поскольку в классическом компьютере проводники играют существенную роль, мы можем рассматривать и два других элементарных ЛЭ, которые называются “FAN OUT” (размножитель, веер, копировальное устройство и проч. - Рис. 1в)  - когда один провод раздваивается и “EXCHANGE” (Рис. 1г)- когда проводники перекрещиваются. А вообще, операции NOT и AND реализуются с помощью транзисторов (Рис. 1д, е).

Что определяет минимум свободной энергии, которая затрачивается при работе идеального компьютера, собранного на основе этих элементарных ЛЭ? Например, при работе элемента AND его выходной сигнал принимает два логических значения, соответствующих двум уровням напряжения или тока. При его переключении энтропия меняется на величину . При постоянной температуре такое изменение энтропии приводит к выделению тепла . Долгое время эта величина считалась пределом энергозатрат, приходящихся на один бит. Вообще же, проблема выделения тепла в современной вычислительной технике играет важную роль. Оказывается, что современные транзисторные схемы выделяют тепла порядка . В основном, это происходит из-за того, что логические уровни обеспечиваются падением напряжения на резисторах! Энергетически было бы значительно выгоднее, если бы энергия запасалась бы в реактивных элементах, таких как конденсаторах или катушках,  - ее можно ,было бы преобразовывать. Но современная технология, ориентированная на кремниевые чипы, пока не в состоянии решить эту проблему.

Даже в природной копирующей машине - молекуле ДНК затрачивается порядка 100кТ при воспроизводства одного бита информации - величина все еще на порядок превышающая предельный уровень КТln2! В квантовых системах биты записываются не на системах, состоящих из 10¹¹ атомов, как в классических транзисторах, а на одном атоме - кубите.

Ч.Беннет впервые показал, что если элементарные ЛЭ будут сделаны обратимыми, то названный предел окажется преодолимым, а затраты свободной энергии окажутся независимыми от уровня сложности всего устройства или числа шагов, которое необходимо выполнить для решения той или иной задачи.

В классических вычислениях известны три обратимых ЛЭ. Это “NOT” - однобитовый ЛЭ (Рис.2а), Управляемое НЕ или CNOT - двухбитовый ЛЭ (Рис.2.б) - операция сложения по модулю два. Как известно, сам по себе CNOT не является обратимым. Однако, если сохранить значение контрольного бита а, то CNOT становится обратимым.

Заметим, что ЛЭ “FAN OUT” можно получить из CNOT”. Если b = 0, то значение, записанное на контрольном входе а копируется на выход  (Рис.2.в). Операция EXCHANGE также реализуема на CNOT (Рис.2г).

Для построения универсального классического компьютера необходим трехбитовый элемент или ЛЭ Тоффоли. Он называется CCNOT. Значение бита мишени с меняется на противоположное, если оба контрольных бита а и b установлены в 1 (Рис.3). Если сохранять значение контрольных битов, то ЛЭ Тоффоли является обратимым.

Любой логический элемент может быть построен на основе комбинаций трех перечисленных основных ЛЭ. Но оказывается, чтобы добиться обратимости любого ЛЭ, необходимо в его устройство, кроме той функции, которую он выполняет, добавлять нечто еще. Этот добавок называется “garbage” или отход. Более того, существуют простые соображения, которые показывают, что размер “мусорного ящика” должен совпадать с размером входных данных (в битах). Рассмотрим некое обратимое логическое устройство, преобразующее n входных битов в n выходных. Пусть решение задачи, которое осуществляет это логическое устройство требует присутствие на выходе k битов информации, при наличии на входе m битов. Оказывается, что при этом необходимо иметь (на входе) пустой регистр, состоящий из k нулей! Тогда, рассматривая задачу как преобразование n входных битов в n выходных, мы видим, что размер “мусорного ящика” совпадает с размером входных данных m , а его содержимое - входные данные - это цена, которую нужно платить за обратимость.

Квантовый компьютер

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

Насколько маленьким должен быть такой компьютер? Т.е. насколько маленьким может быть носитель числа? Естественно, что число будет представляться битом. Будем записывать бит на двухуровневой системе. Фейнман назвал ее “атомом”. Мы называем ее кубитом. Тогда n-битовое число представляется состоянием регистра или набором n двухуровневых систем. В зависимости от того, в каком из двух состояний  находится кубит, меняется и значение всего числа или регистра, на котором оно записано. Соответственно, число может быть прочитано, определяя или измеряя состояние составляющих регистр кубитов. Рассмотрим, например, устройство квантового ЛЭ CCNOT. Пусть G представляет некую операцию, производимую над тремя атомами a, b и c. Эта операция преобразует начальное состояние атомов a, b и c в конечное состояние . Таким образом, связь между конечным и начальным состояниями и осуществляется функцией, которую мы хотим построить. Заметим, что мы не производим перемещение кубитов из одной точки в другую. Мы просто изменяем их. В классическом компьютере это происходит по-другому. Между начальным и конечным состояниями имеются реальные проводники, по которым текут токи. В нашем случае все обстоит гораздо проще. С начала мы имеем три кубита (атома) в некоем состоянии, а в результате операции G это состояние меняется и кубиты принимают значения . Математически эта операция выражается в том, что выход  есть результат действия G на вход. Известно, что в квантовой механике операторы, изменяющие состояния, должны быть линейными. Поэтому мы полагаем, что G - это линейный оператор. Он представляется матрицей, причем почти все матричные элементы  равны нулю (см. таблицу истинности для ЛЭ Тоффоли). Ясно, что такая операция будет обратимой, поскольку обеспечивается условием . Таким образом, G - эрмитова матрица (кроме того, она еще и действительная матрица , но это только в данном конкретном случае CCNOT).

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

Например, мы хотим записать матрицу, соответствующую NOT. Матрица A_a имеет вид

Это 2х2 матрица может быть реализована множеством способов (мы рассматривали фазовую пластинку в пол-длины волны). Рассмотрим здесь метод, развитый Фейнманом - метод операторов рождения и уничтожения. Будем использовать нестандартные обозначения, чтобы не путать операторы с использованными уже буквами.

Матрица, соответствующая оператору :

4

уничтожает 1, записанный на атоме а и преобразует его в 0. Соответственно,  - это оператор, преобразующий состояние  в состояние . Однако, если исходное состояние атома было , оператор  дает число 0, т.е. действуя на состояние, он не изменяет его, а просто дает “пустое состояние” - число 0.

Действительно

,    

Сопряженный оператор дается матрицей

.

Этот оператор, действуя на состояние “0” дает состояние “1”: . Действуя же на состояние , поскольку более “высоких” состояний нет, он дает численный нуль.

Обращаю внимание, что эти обозначения не являются стандартными для операторов рождения () и уничтожения ().

Любой оператор, представимый матрицей 2х2, может быть представлен в терминах этих операторов  и . Например, произведение  дается матрицей

Этот оператор дает 1 для состояния  и 0 - для состояния . Т.е. оператор N дает число, которое представляет состояние атома.  Произведение операторов  представляется матрицей

и дает о для состояния , для состояния  дает 1.

Имеется также диагональная матрица

,

с помощью которой можно записать известное выражение

.

Используя формализм операторов рождения и уничтожения, можно записать матрицу для NOT: . Естественно, что эта матрица обратима (унитарна): .

Аналогично можно записать выражение для матрицы, описывающей действие оператора CNOT:

.

Первое слагаемое в этом выражении  выделяет условие, при котором на входе а записана единица: а = 1; тогда мы хотим, чтобы ко входу b применялось преобразование NOT. Второе слагаемое выделяет условие, при котором на входе а находится 0; при этом ко входу b применяется тождественное преобразование I.

Следующий вопрос, неизбежно появляется при рассмотрении результата действия нескольких элементарных ЛЭ. Что из себя представляет матрица логического устройства, состоящего из набора элементарных ЛЭ, т.е. как весь объект в целом действует на входное состояние? Т.е. мы хотим представить результат в виде:

.

Можно показать, что в этом случае матрица М будет являться произведением матриц, описывающих действие всех последовательных элементарных ЛЭ:

Такая матрица будет унитарной, поскольку все составляющие ее матрицы унитарны. Поэтому вся операция в целом будет обратима.

Таким образом общая задача формулируется так. Пусть А₁, А₂, А₃,….А_к - последовательность необходимых элементарных операций в некотором логическом устройстве, которое действует на n атомов. Мы хотим построить матрицу М размером , которая будет отвечать всей операции в целом. Каким образом можно построить такое физическое устройство, если мы знаем как работают простейшие элементы?

Вообще в квантовой механике временная эволюция состояния (выходного состояния) дается формулой:

,

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

Добавим к n атомам, находящимся в нашем регистре, совершенно новый набор к + 1 атомов, которые будут отвечать за “положения программного счетчика”. Обозначим как q_i и q*_i  операторы рождения и уничтожения для точки программы i когда i меняется от 0 до к. Физически это можно реализовать с помощью электрона, двигающегося от одного свободного места к другому. Если положение i уже занято электроном, то назовем это состояние , если положение свободно, то это состояние . Наш гамильтониан принимает вид:

Здесь операция А применяется к регистру n атомов, а операторы q действуют на программный счетчик.

Первое, на что можно обратить внимание, это что если все программные места свободны, т.е. все программные атомы находятся в состоянии , ничего не происходит, т.к. каждый член в гамильтониане начинается с оператора уничтожения и, поэтому, дает 0.

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

Пусть в начальный момент место 0 занято, т.е. находится в состоянии  (и, поэтому, все остальные находятся в состояниях ). Если в итоге, в некоторый момент времени t место к окажется в состоянии  (поэтому все другие - в состояниях), то мы делаем вывод, что на  n-регистр подействовала матрица M, которая равна А_к…А₂А₁, как мы и хотели. Это получается следующим образом. Предположим, что регистр начинает работу в каком-нибудь начальном состоянии  и, что “место 0” программного счетчика занято. Тогда единственный член в полном гамильтониане, который будет действовать первым, (т.к. гамильтониан работает в последовательные моменты времени) - это первый член . Оператор q₀ изменит состояние “места 0” на “свободно”, в то время как  изменит “место 1” на “занято” Таким образом, член  просто передвигает занятое место из положения 0 в положение 1. Но все это умножается на матрицу А₁, которая действует только на регистр n атомов, и, поэтому умножает начальное состояние регистра n атомов на А₁.

Далее, гамильтониан действует во второй раз. Тогда первый член не даст ничего, поскольку q₀ дает 0 на “месте 0” (из-за того, что это место свободно). Теперь работает второй член (прости господи) , который опять передвинет занятое место - будем его называть курсором. Курсор передвинется из положения 1 в положение 2, а на регистр действует матрица А₂ - т.е. в целом мы получили матрицу А₂А₁, подействовавшую на регистр.

Таким образом, поскольку гамильтониан (первая строчка) действует в последовательные моменты времени, курсор будет передвигаться от 0 до к, а последовательное действие матриц А_i на регистр как раз и даст общую матрицу М.

Заметим однако, что гамильтониан должен быть эрмитовым, поэтому должна оставаться операция комплексного сопряжения всех операторов. Предположим, что для данного состояния, мы получили позицию курсора в “положении 2”, следовательно, мы имеем матрицу А₂А₁, подействовавшую на регистр. Теперь q₂ , который передвинет занятое положение на следующую позицию, не обязательно возникает из первой строчки - он может прийти из второй, т.е. из члена , который передвинет курсор назад из положения 2 в положение 1! Когда это происходит, на регистр действует оператор А₂*, поэтому полный оператор, действующий на регистр, в этом случае оказывается А₂* А₂А₁ .Но А₂* А₂ = 1, откуда весь оператор вырождается в значение А₁. Поэтому ясно, что когда курсор вернулся в “положение 1” полный результат оказывается таким, как будто бы на регистр подействовал только оператор А₁! Тогда по мере продвижения курсора разными членами в гамильтониане вперед и назад, операция А накапливается, либо вновь редуцируется.

На некотором этапе, например, когда курсор находится в положении j, матрицы от А_i до A_j подействовали поочередно на регистр. Совершенно неважно каким путем курсор пришел в “положение j“- из “положения 0” до “j“ или пройдя дальше и вернувшись назад, или возвращаясь назад, а потом вперед и т.д. - важно, что он оказался в “положении j”. Поэтому, верным оказывается утверждение, что если курсор оказался в положении к, мы имеем общий результат для регистра n атомов, состоящий в том, что матрица М подействовала на начальное состояние - как мы и хотели.

Как мог бы работать такой компьютер? Начнем с того, что поместим входные данные (биты) во входной регистр, а курсор 0 в “положение 0” (т.е. “положение 0” занято). Затем, проверим положение к, например, с помощью рассеяния электронов, свободно оно или занято (имеет ли курсор). В момент, когда мы обнаружили курсор в положении к, уберем курсор так, что он не сможет вернуться в программную строку. Тогда мы знаем, что регистр содержит выходные данные. Мы можем измерить их в удобное для нас время. Конечно существуют некие внешние параметры, задействованные в процедуре измерения и определяющие её, которые не являются частями компьютера. При этом мы говорим, что компьютер вступает во взаимодействие с внешним миром и при загрузке данных, и при чтении результата.

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

Недостатки компьютера и необратимые потери энергии.

Вообще имеется много неидеальностей такого устройства, но главная из них заключается в том, что коэффициенты связи оказываются неодинаковыми вдоль программной строки. Строка настолько длинная, что при реальном вычислении небольшие нерегулярности будут вызывать малые вероятности рассеяния и волны не будут распространяться строго по “баллистическим траекториям”, при этом беспорядочно двигаясь вперед и назад.

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

Рассмотрим простой пример. Рассмотрим регистр, построенный из трех классических битов. Такой 3-х битовый регистр может хранить одно из восьми различных чисел - от нуля до семи, т.е. находиться в одном из восьми состояний: 000, 001, 011,...111. Но квантовый регистр, составленный из трех кубитов, может одновременно хранить до восьми чисел. Поскольку регистр представляет собой суперпозицию. Примечательно, что восемь различных чисел могут физически присутствовать в одном регистре одновременно На самом деле, это не более удивительно, чем одновременное присутствие состояний  и  в одном кубите:

Каждое из восьми состояний имеет соответствующую вероятность быть обнаруженным, например, состояние  имеет вероятность .

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

"Мировой экономический кризис 1929 - 1933 гг." - тут тоже много полезного для Вас.

При добавлении кубитов к регистру его емкость по отношению к хранению квантовой информации растет экспоненциально: четыре кубита могут хранить 16 различных чисел одновременно, и т.д. В общем случае N кубитов хранят 2^N чисел. Так регистр из 250 кубитов - совместное состояние 250 двухуровневых атомов хранит одновременно больше чисел, чем количество атомов во вселенной. Заметим, что это заниженная оценка количества квантовой информации, поскольку элементы суперпозиции присутствуют в непрерывно изменяемой пропорции, которая определяется взаимными фазами тех или иных состояний.

Например, если кубиты - это атомы, то подействовав на них подобранными по длительности и интенсивности лазерными импульсами (модель Цолера-Цирака), можно повлиять на соответствующие состояния освещаемых атомов (кубитов). Тогда начальная суперпозиция закодированных чисел превратиться в другую суперпозицию. В процессе такой эволюции каждое число в суперпозиции подвергается воздействию, так что получается, что производится большой объем параллельных вычислений В этом состоит принцип параллелизма, введенный Д.Дойчем. Следовательно квантовый компьютер за один шаг вычислений может провести одну операцию, например, над 2^N различными (входными) числами. А результатом будет - представляться соответствующей суперпозицией на выходе. Для выполнения аналогичной задачи классический компьютер должен повторить вычисления 2^N раз или использовать 2^N параллельно работающих процессоров. 

ЛИТЕРАТУРА

1. Simulating physics with computers, Internat. J. Theoret. Phys. 21, 467-488 (1982).

2.  Quantum mechanical computers, Found.Phys. 16, 507-531(1986).

[1] Ñîãëàñíî ìîäåëè êëåòî÷íîãî àâòîìàòà ïðîñòðàíñòâî ðàçáèâàåòñÿ íà íàáîð êëåòîê; åñòü ïðàâèëî èçìåíåíèÿ âåëè÷èíû, çàïèñàííîé â  êàæäîé êëåòêå; ñîñòîÿíèÿ â êàæäîé êëåòêå ìåíÿþòñÿ îäíîâðåìåííî ïðè êàæäîì ñëåäóþùåì øàãå.