М. Нильсен, И. Чанг - Квантовые вычисления и квантовая информация (1156771), страница 64

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 64)

Напомним, что класс РЯРАСЕ был определен в гл. 3 как класс задач разрешения, которые могут быть решены на машине Тьюринга с использованием объема памяти, полиномиально зависящего от размера задачи, и без ограничений на время. Что касается ВЯР, то это — квантовый класс сложности, состоящий из задач разрешения, которые могут быть решены с ограниченной вероятностью ошибки с помощью квантовой схемы полиномиального размера.

Если выражаться более формально, то язык Ь лежит в классе ВЯР тогда и только тогда, когда существуег имеющее полиномиэльный размер однородное семейство квантовых схем, которые принимают строки, принаддежащие языку, с вероятностью не менее 3/4 и отвергают строки, ему не принадлежащие, с вероятностью также не менее 3/4. Это означает, что на вход квантовых схем поступают двоичные строки, а в конце схемы измеряется один кубит; если в результате измерения получается О, то строка принята, если 1, то отвергнута.

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

Поэтому в определении класса ВЯР 256 Глава 4. Квантовые схемы используется целое семейство схем: для каждой длины входного слова — своя схема. При этом мы налагаем на эти схемы два дополнительных условия. Во. первых, размер схемы, которую мы применяем ко входной строке х Е Ь, должен быть ограничен сверху полиномом от длины х.

Во-вторых, семейство схем должно быть однородна«м в том смысле, как данный термин употребляется в подразд. 3.1.2. Это означает следующее. Пусть дана строка х длиной и, и мы хотим построить схему, выясняющую, лежит ли она в языке Ь. Так вот, необходимо иметь алгоритм для построения такой схемы, точнее говоря, должна существовать машина Тьюринга, выдающая описание искомой схемы.

Указанное ограничение может показаться техническим, и на практике оно почти всегда тривиальным образом выполняется, но оно ограждает нас от патологических контрпримеров, подобных описанным в подразд. 3.1.2. (У читателя может также возникнуть вопрос, о какой машине Тьюринга шла речь в этом определении — классической или квантовой; оказывается, это неважно — см. равд. «История и дополнительная литературам) Один изнаиболее значительных результатов в квантовой теории сложности состоит в том, что Вь4Р С РЯРАСЕ. Поскольку ясно, что ВРР С ВЯР, где ВРР— классический класс сложности, состоящий из задач разрешения, которые можно решить эа полиномиальное время на классической машине Тьюринга с ограниченной вероятностью ошибки, имеется цепочка включений ВРР С ВЯР С РЯРАСЕ.

Если бы удалось доказать, что ВЯР ф ВРР (неформально это означает, что квантовые компьютеры эффективнее классических), тем самым было бы доказано и то, что ВРР ф РЯРАСЕ. Однако в данный момент неизвестно, совпадают ли классы ВРР и РЯРАСЕ, и ответ на этот вопрос явился бы прорывом в теоретической информатике. Так что, если бы удалось доказать, что квантовые компьютеры эффективнее классических, это повлекло бы интересные последствия и для классической теории сложности. К сожалению, это означает и то, что доказать неравенство ВРР ф РЯРАСЕ будет очень трудно. Но почему же Вь)Р С РЯРАСЕ? Вот неформальный набросок доказательства (ссылку на источник, содержащий строгое доказательство, см.

в разделе «История и дополнительная литератураэ). Пусть имеется и-кубитовый квантовый компьютер и мы выполняем квантовое вычисление с использованием р(п) элементов, где р(п) — многочлен от п. Предполагая, что квантовая схема начинает работу в состоянии ~0), объясним, как, используя лишь полиномиальную память, оценить с помощью классического компьютера вероятность того, что конечным состоянием схемы будет ~у). Пусть в процессе вычисления использовались элементы У«, Уэ,..., У„, Ур(п) (в указанном порядке). Тогда вероятность того, что конечным состоянием будет ~у), равна квадрату модуля числа (р! У„„, "У2У1!О), (4.86) и эта вероятность может быть посчитана классическим компьютером на полиномиэльной памяти.

Основная идея состоит в том, чтобы между каждой парой соседних сомножителей вставить соотношение полноты 2, ~х) (х~ = 1 и получить 4.6. Модель квантовых схем вычислений 257 (Ии,<„, ". и,и,)о) (у!Ур<~>!яр(„) 1)(яг(„) 1~5/р<„> 1... Уг)х|)(я~!У1/О). (4.87) Поскольку отдельные унитарные элементы, входящие в эту сумму, — элемент Адамара, ПнОт и т. п., ясно, что каждое слагаемое можно с высокой точностью вычислить с помощью классического компьютера на полиномиэльной памяти; значит, и всю сумму можно вычислить, используя полиномиальную память, поскольку после прибавления очередного слагаемого к промежуточному итогу это слагаемое можно стереть.

Конечно, описанный алгоритм является довольном медленным (ведь число слагаемых в сумме экспонеициэльно), но объем используемой памяти при этом полиномиален, так что ВЯР С РЯРАСЕ, что н требовалось доказать. С помощью аналогичной процедуры на классическом компьютере можно моделировать произвольное квантовое вычисление, какова бы ни была его длина. Значит, класс задач, разрешимых на квантовом компьютере без ограничений на время и память, не больше, чем класс задач, разрешимых на классическом компьютере. Иными словами, квантовые компьютеры не отменяют тезис Черча — Тьюринга: любой алгоритм может быть выполнен на машине Тьюринга. Конечно, квантовые компьютеры могут оказаться значительно более эффекгаиенымп, чем классические, что поставит под сомнение усиленяэв2 тезис Черча-Тьюринга, согласно которому любой алгоритм можно эффективно моделировать на вероятностной машине Тьюринга.

4.6 Модель квантовых схем вычислений В данной книге понятие «квантовый компьютер» означает «модель вычислений, основанная на квантовых схемах», и в этой главе мы подробно обсудили квантовые схемы, основные элементы, из которых они состоят, универсальные наборы элементов, а также некоторые приложения. Прежде чем перейти к рассмотрению более сложных применений, суммируем основные положения модели квантовых схем. 1.

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

гл. 10) классические вычисления бувут использоваться для повышения эффективности. Хотя в принципе любое классическое вычисление может быть выполнено на квантовом компьютере, может оказаться удобнее некоторые вычисления делать на классическом компьютере. а 258 Глава 4. Квантовые схемы 2. Пространство состояний. Квантовый компьютер работает с определенным числом кубитов (обозначим его и). Соответствующее пространство состояний является 2"-мерным комплексным гильбертовым пространством. «Разложимые» состояния вида ~зм..., х„), где кч = О, 1, известны как элементы еьичис«ита«ьного йииса. Если х — число с двоичной записью зм...,х„, то через ~з) обозначается соответствующее состояние, принадлежащее вычислительному базису.

3. Возможность приготовления состояний из вычислительного базиса. Предполагается, что любое состояние ~хы..., х„) из вычислительного базиса можно приготовить не более чем за и шагов. 4. Возможность выполнения квантовых элементов. Элементы можно применять к любому нужному множеству кубитов, и можно реализовать универсальный набор элементов. Например, элемент «лнот можно применить к любой паре кубитов. Элементы Адамара, сдвига фазы, скот и х/8 образуют универсальный набор элементов, с помощью которого можно аппроксимировать любую унитарную операцию, и тем самым он универсален. Существуют и другие универсальные наборы.

б. Возможность измерения в вычислительном базисе. В вычислительном базисе можно измерять один или несколько кубитов. Модель квантовых схем эквивалентна многим другим моделям в том смысле, что для одинаковых задач требуется примерно одинаковый объем ресурсов. В качестве простого примера, иллюстрирующего обшую идею, попытаемся выяснить, дает ли экономию ресурсов переход на трехуровневые квантовые системы взамен двухуровневых кубитов. Хотя использование трехуровневых квантовых систем (кутрип»ов) и может принести небольшое преимущество, с теоретической точки зрения им можно пренебречь. Менее тривиальный пример: было показано, что «квантовая машина Тьюринг໠— квантовое обобщение классической машины Тьюринга — эквивалентна как вычислительная модель квантовым схемам.

Мы здесь не рассматриваем квантовые машины Тьюринга; заинтересованный читатель найдет соответствующие ссылки в разделе «История и дополнительная литература». Несмотря на простоту и привлекательность модели квантовых схем, необходимо иметь в виду ее возможные недостатки, модификации и расширения. Так, отнюдь не самоочевидно, что обоснованы допущения относительно пространства состояний и начального состояния. В рассматриваемой модели все формулируется в терминах конечномерных пространств, но не исключена, что можно получить больше, если рассматривать системы с бесконечномерным пространством состояний.

Характеристики

Список файлов книги