М.Г. Иванов - Как понимать квантовую механику, страница 62

Однако извлечь из L кубитов мы по-прежнему можемне более L классических битов информации. По этой причине квантовыйпараллелизм оказывается не столь эффективным, как это может показатьсяна первый взгляд.10.6. Логика и вычисления10.6.1. Логика классическаяКлассическая логика изучает функции двоичных переменных (классических битов): каждый аргумент такой функции пробегает два значения5 Дэвид Дойч утверждает в своих статьях и книгах, что многомировая интерпретация квантовой механики является стандартной для физиков, работающих в области квантовых вычислений. Д. Дойч также является автором философской книги «Структура реальности», рассматривающей современную науку с точки зрения квантовой механики по Эверетту, эволюции поДарвину и теории познания по Попперу (познание как естественный отбор среди научныхтеорий).324ГЛАВА 10(0 и 1, «да» и «нет», «ложь» и «истина»), и значение самой функции такжеможет принимать те же два значения.

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

При этом линия, идущая от выхода, может разветвляться. Графическая схема может иметь несколько внешних входныхлиний, на которые подаются входные данные и несколько выходных — накоторые выдаётся результат вычисления. Входные линии схемы (они также могут разветвляться) могут подключаться к выходным линиям схемы,а также к входным линиям логических вентилей.Доказано, что для описания любого вычисления достаточно применить конечное число разновидностей логических вентилей, например, «и»,«или», «не»:0001«и»:1011→→→→0001«или»:101100,01→→→→01,11«не»:0→1.1→0Более того, достаточно одного универсального вида логических вентилей«не-и»:0001«не-и»:1011→→→→11,10«не-и»(•, •) = «не»(«и»(•, •)).10.6.2. Вычисления и необратимостьОписанные выше логические схемы представляют собой графическоеописание процесса вычислений, который может быть реализован на некотором классическом вычислительном устройстве.

То есть логические схе-10.6. Л ОГИКАИ ВЫЧИСЛЕНИЯ325мы — описания физических процессов, которые реализуют данное вычисление.Поскольку линии логической схемы могут разветвляться, произвольная информация в логических схемах может копироваться.

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

Тем не менее любое классическое вычислениеможет быть модифицировано так, чтобы каждый шаг выполнялся обратимым образом, и всё вычисление в целом также было обратимым.Для обратимых классических вычислений вход и выход всегда содержат одинаковое количество бит L и любое вычисление можно рассматривать как некоторое взаимно-однозначное отображение (перестановку) множества всех входов (состоит из 2L элементов) на себя.Такую перестановку можно представить матрицей 2L × 2L , в каждойстроке и в каждом столбце которой имеется ровно одна единица, а остальные элементы — нули.

Такая матрица является унитарной (обратима и сохраняет скалярное произведение), а значит может быть реализована как оператор эволюции некоторой квантовой системы с пространством состоянийLHL = C2 (см. рис. 10.1).10.6.4. Обратимые вычисленияДля записи обратимых вычислений удобно использовать обратимыелогические операции (они не подпадают под определение логической опе-326ГЛАВА 10рации, данное выше). Обратимые логические операции являются взаимнооднозначными отображениями множества входов (множество состояний lбитов, которое имеет 2l состояний) на множество выходов, которое также имеет 2l состояний и может быть записано как множество состояний lбитов.Обратимая логическая операция можетбыть изображена графически (рис.

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

4.4.4 «Сравнение разных обозначений*»), и, действительно,действие такого вентиля на квантовую систему соответствует действиюсоответствующего унитарного оператора.Доказано, что любое классическое вычисление может быть сделанообратимым. При этом достаточно применить конечное число разновидностей обратимых логических вентилей, например, достаточно одного универсального вентиля Тоффоли («дважды управляемого не», есть и другиеуниверсальные обратимые вентили):«вентиль Тоффоли»:000 →001 →010 →011 →000,001,010,011,100101110111→ 100,→ 101,.→ 111,→ 110При применении вентиля Тоффоли первые два бита определяют применятьли операцию «не» ко третьему биту, сами первые два бита передаются совхода на выход без изменений.Обратимые вентили типа вентиля Тоффоли могут быть реализованыв виде классических, или квантовых устройств.

Однако такой вентиль переводит базисное состояние (в котором состояние всех битов задаётся как 0или 1 и биты не зависят друг от друга) снова в базисные состояния.То есть в процессе таких вычислений (вычислений в базисных состояниях) нигде не появляются квантовые суперпозиции и квантовая запутанность. Единственное преимущество квантовой реализации таких вычислений — теоретическая возможность вычисления без генерации энтропии, т.

е.без диссипации энергии. Генерация энтропии и нагрев будут обязательно10.6. Л ОГИКА327И ВЫЧИСЛЕНИЯпроисходить только при необратимой очистке памяти и приготовлении исходного состояния компьютера.10.6.5. Вентили сугубо квантовыеЧтобы построить универсальный квантовый компьютер в смысле приведённого выше определения, необходимо дополнить описанный выше вентиль Тоффоли несколькими сугубо квантовыми вентилями. Обычно берутоднобитовые вентилиeiασx ,eiασy ,eiασz ,H=√12√12√12− √12.Вентиль H называется вентилем Адамара.

Доказано, что, используя перечисленные вентили, можно воспроизвести любое унитарное преобразование на пространстве состояний входа (пространстве состояний L кубитов)с любой наперёд заданной точностью. Более того, вместо трёхбитового вентиля Тоффоли («дважды управляемое не») достаточно применения болеепростого двухбитового вентиля, например, вентиля «управляемое не»0001«управляемое не»:1011→→→→0001.1110В операции «управляемое не» первый бит определяет применять ли операцию «не» ко второму биту, сам первый бит передаётся со входа на выходбез изменений.Иногда количество вентилей, применяемых для описания квантовогокомпьютера стремятся сократить, например можно зафиксировать α в вентиле eiασx каким-то одним значением, несоизмеримым с 2π, а остальныезначения получать многократными повторениями.

Для практических целейтакое «упрощение» не слишком полезно, особенно если квантовые вентили воспроизводятся с конечной точностью. Наоборот, при изложении техили иных алгоритмов может быть полезно вводить новые вентили, например, N -битную версию «управляемого не», для которой «не» применяетсяк последнему биту, если все остальные биты равны 1.10.6.6. Обратимость и уборка «мусора»Переписывание какого-либо необратимого алгоритма в обратимом виде может привести к тому, что в схеме появятся дополнительные выход-328ГЛАВА 10ные биты, которые будет нести дополнительную информацию, которая ненужна для вычислений, но которая необходима, чтобы сделать вычисленияобратимыми.То есть результат вычисления можно записать так:Û |вход, 0 .. .

0, 0 .. . 0 = |вход, выход, вспомогательная информация.выходдоп. ячейки«мусор»Вспомогательная информация может мешать интерференции квантовыхсостояний, поэтому предпочтительно было бы иметь процесс вида. . 0 = |вход, выход, 0 . . . 0.Û |вход, 0 .. . 0, 0 .выходдоп. ячейкиЭто не нарушает обратимости оператора Û , т. к. вся информация, необходимая для обращения вычисления, уже содержится в подсистеме ячеек«вход».Доказано, что любое классическое вычисление всегда можно провестиобратимым образом так, чтобы все дополнительные ячейки памяти, которые не используются для записи входа и выхода, в начале и конце процессабыли в состоянии 0 («ложь», «нет», «спин вниз» и т.

п.).10.6.7. Исправление ошибокКак правило, мы не можем «подсматривать» за промежуточными состояниями квантового компьютера, работающего в суперпозиции базисныхсостояний, чтобы не разрушить суперпозицию и не испортить вычисления. Однако, если мы заранее знаем, что на каком-то этапе вычисленийв определённой ячейке обязательно должен быть 0, мы можем это проверить, и состояние квантового компьютера от этого не изменится.Если квантовые вентили реализуются не идеально точно, реальное состояние может чуть-чуть отличаться от желаемого, и мы можем вместо 0обнаружить 1. Это будет означать ошибку квантового компьютера. Если мыв самом деле обнаружим 0, то «неправильная» часть волновой функции системы обнулится и мы, убедившись что ошибки пока нет, увеличим вероятность успешного завершения вычисления.