М. Нильсен, И. Чанг - Квантовые вычисления и квантовая информация (1156771), страница 63
Текст из файла (страница 63)
Теперь мы можем доказать, что любая однокубитовая операция может быть с произвольной точностью аппроксимирована с помощью элементов Адамара и я/8. Простые алгебраические выкладки показывают, что для любого а имеем НВа(а)Н = В,ь(а), (4.78) где гл — единичный вектор, идущий в нэправлеиии(сое х, — егп х, соэ к), откуда следует, что 3 (4.79) Однако (с учетом упр. 4.11) всякий унитарный однокубитовый оператор У можно записать в виде У = Ва()3)В,ь( г)Ва(б) (4.80) (с точностью до несущественного общего фазового множителя).
Формулы (4.76) и (4.79) вместе с неравенством (4.63) показывают, что для подходящих целых положительных чисел пг~ пз и лэ имеем 4.5. Универсальные квантовые элементы 251 Е(Ц Ка(В) "НЯа(В)) НЯ„-(В)"') ( е. (4.81) Таким образом, для любого унитарного однокубитового оператора П и любого е ) О можно аппроксимировать П с ошибкой, не превосходящей е, с помощью схемы, состоящей из элементов Адамара и я/8. Коль скоро элементы я/8 и Адамара позволяют аппроксимировать любой однокубитовый унитарный оператор, из рассуждений в подразд. 4.5.2 вытекает, что можно аппроксимировать и любую т-элементную квантовую схему. А именно, если схема состоит из т элементов, являющихся либо скот, либо однокубитовыми операторами, ее можно аппроксимировать с помощью элементов Адамара, скот и я/8 (в дальнейшем мы увидим, что использование элемента сдвига фазы позволяет сделать это приближение устойчивым к ошибкам, но для доказательства универсальности это уточнение не является необходимым).
Если ошибка не должна превосходить е для схемы в целом, то этого можно добиться, аппроксимируя каждый однокубитовый унитарный оператор с точностью до е/ти: неравенство (4.83) показывает, что для схемы в целом ошибка будет не больше е. Насколько эффективна описанная процедура аппроксимации квантовых схем с помощью конечного набора элементов? Это — важный вопрос. Предположим, например, что для аппроксимации однокубитового оператора с точностью е требуется П(2~~') элементов из нашего набора; тогда для аппроксимации т-элементной схемы, о которой шла речь в предыдущем абзаце, потребуется П(ш2 ~') элементов — экспоненциельно больше, чем исходный размер схемы! В действительности, однако, скорость сходимости гораздо выше.
Интуитивно ясно, что последовательность углов Вь заполняет интервал [О;2я) более или менее равномерно, так что для аппроксимации однокубитового оператора требуется 6(1/е) элементов. Если принять такую оценку, то число элементов, необходимое для аппроксимации т-элементной схемы, равно 9(та~/г). Это— квадратичное увеличение размера схемы, что может оказаться приемлемым для многих приложений. Замечательно, что на самом деле скорость сходимости гораздо выше.
Теорема Солоеея-Кпулаееа (см. Приложении 3) гласит, что любой однокубитовый унитарный оператор может быть приближен с точностью г с использованием 0(1о8'(1/е)) элементов из нашего конечного набора, где с — константа, примерно равная 2. Тем самым из этой теоремы следует, что для аппроксимации с точностью е схемы, состоящей из т элементов скот и однокубитовых унитарных операторов, достаточно 0(т 1ой'(т/е)) элементов из конечного набора, что дает лишь полулогарифмическое увеличение раэмера схемы, которое, повидимому, приемлемо для всех приложений. Подведем итоги. Было показано, что набор, состоящий из элементов Адамара, сдвига фазы, скот и я/8, универсален для квантовых вычислений в том смысле, что любую схему, состоящую из скот и однокубитовых унитарных операторов, можно с хорошей точностью аппроксимировать с помощью схемы, содержащей только элементы из этого набора. Более того, это приближение 252 Глава 4.
Квантовые схемы может быть реализовано эффективно в том смысле, что размер схемы увеличивается в количество раз, которое полиномиально относительно 1ой(т/е), где нз — количество элементов в исходной схеме и е — точность приближения. Упражнение 4.41.
В этом и двух следующих упражнениях изложена конструкция, показывающая, что семейство, состоящее из элементов Адамара, сдвига фазы, скот и Тоффоли, является универсальным. Покажите, что схема на рис. 4.17 производит над третьим (управляемым) кубитом операцию В,(д), где созд = 3/5, если результаты обоих измерений равны нулю, а в противном случае применяет к управляелюму кубиту операцию Я. Проверьте, что вероятность того,что результаты обоих измерений равны нулю, равна 5/З,и объясните, как с помощью многократного применения этой схемы и элемента ю = Я~ можно получить ус,(д) с вероятностью, стремящейся к единице . /0) /0) Рис. 417.
Если результаты обоих измерений равны нулю, вта схема применяет к управляемому кубиту оператор гг,(о), где совэ = 3/5 Если результаты измерений другие, используется оператор Я 'Упражнение 4.42 (иррациональность д). Пусть соэ д = 3/5. Докажите от противного, что д несоизмеримо с 2я.
1. Пользуясь тем, что ем = (3+ 4з)/5, покажите, что если д рационально, то существует такое целое положительное число т, что (3+ 4г)™ = 5'". 2. Покажите, что (3+ 4з) ы 3+ 4т( пюс1 5) для всех оз > О, и выведите отсюда, что равенство (3+ 4з)гл = 5гл невозможно. 'Упражнение 4.43. Выведите из результатов двух предыдущих упражнений, что набор, состоящий из элементов Адамара, сдвига фазы, Тоффоли и скот, универсален для квантовых вычислений.
Упражнение 4.44. Покажите, что трехкубитовый элемент С, определяемый приведенной на рисунке схемой, универсален при иррациональном ст. 4.5. Универсальные квантовые элементы 253 Упражнение 4.45. Пусть Н вЂ” унитарное преобразование, реализованное с помощью и-кубитовой квантовой схемы, состоящей из элементов Н, Я, скот и Тоффоли. Покажите, что Н имеет вид 2 "~зМ, где л — целое число, а М— матрица размера 2" х 2", элементы которой — комплексные числа с целыми действительной и мнимой частями. Выполните то же упражнение с элементом я/8 вместо элемента Тоффоли.
4.5.4 Трудность аппроксимации общего унитарного оператора в общем случае Было показано, что произвольное унитарное преобразование на и кубит можно выполнить, используя ограниченный набор элементов. Всегда ли можно сделать это эффективно? Иными словами: существует ли для данного унитарного преобразования У на п кубитах, аппроксимирующая его схема, размер которой полиномиален по и? Ответ на этот вопрос — решительное «нет»; естественно, ббльшая часть унитарных преобразований может быть реализована только очень неэффективным образом. Чтобы понять причину этого явления, заДадимся следующим вопросом: сколько требуется элементов, чтобы создать провзвольное п-кубитовое состояние? Простой подсчет показывает, что, вообще говоря, требуемое количество экспоненциально.
Предположим, что в нашем распоряжении имеется д разных элементов, каждый из которых действует не более чем на / входных кубитов. Числа / и д определяются используемым оборудованием и поэтому могут считаться постоянными. Пусть у нас имеется квантовая схема из тл элементов, на вход которой подано состояние ~0)" из вычислительного базиса. Каждый элемент может перевести этот вектор в одно из ~'и''1 э не более чем ~ ) = 0(п1») состояний, так что схема из тп элементов может Ы вычислить не более 0(птэ"') различных состояний.
Пусть теперь мы хотим приблизить состояние ~«») с точностью до а Идея доказательства состоит в том, чтобы покрыть множество всех возможных состояний набором «кружков» радиуса е (рис. 4.18), а затем показать, что количество кружков растет дважды экспоненциельно по и; сравнив с экспоненциапьным количеством всевозможных состояний, которые можно получить на т элементах, получим желаемый результат.
Заметим, что пространство векторов состояний и кубитов можно рассматривать как единичную (2"+' — 1)-мерную сферу. Действительно, пусть состояние и кубит имеет амплитуды ф, = Х +Л"у, где Ху и У1 — действительная и мнимая части ~-й амплитуды. Условие нормализации для квантовых состояний можно записать в виде ~ (Х + 1' ) = 1, а это и есть условие того, что точка лежит на единичной сфере в 2"+'-мерном вещественном пространстве, т. е. на (2""' — 1)-мерной сфере.
Аналогичным образом, площадь поверхности «кружка» радиуса е с центром ~«Д) примерно равна объему, ограничиваемому (2"+1 — 2)-мерной сферой радиуса е. Пользуясь формулами Я»1т) = 2х<"+'Неть/7Яс + 1)/2) для площади поверхности Й-мерной сферы радиуса т и ЪЦт) = 2х<"+П!зть»1/Ил+ 1)ГЯЙ+ 1)/2)) для объема (л + 1)-мерного шара радиуса т, получим, что количество «кружков», 254 Глава 4. Квантовые схемы Рис. 4.18.
Покрытие множества возможных состояний кружками постоянного радиуса необходимое для покрытия всего пространства состояний, примерно равно Яг-+~-1(1) 1/яГ(2п — -')(2"+1 — 1) (4.82) уг-+ -э(е) Г(2п)ег-+~-1 ей"е~-1 (4.83) Как мы помним, что с помощью пз элементов можно покрыть лишь 0(от опт) кружков, поэтому для того, чтобы можно было покрыть все екружки» ради- уса е, необходимо выполнение условия (4.84) откуда следует (2" 1о8(1/е) [, 1о8(п) (4.85) где à — обычная гамма-функция. Однако Г(2" — 1) > Г(2")/2", так что число «кружков не меньше чем 4.5. Универсальные квантовые элементы 255 Значит, существуют состояния п кубитов, которые можно аппроксимировать с точностью е с помощью не менее чем П(2" 1ой(1/е)/!об(и)) операций. Это экспоненциально по п, и тем самым это трудно в смысле сложности вычислений (см.
гл. 3). Более того, отсюда непосредственно следует, что существуют и-кубнтовые унитарные операторы У, для аппроксимации которых схемой Ъ' (при условии Е(0, У) < е) требуется П(2" 1об(1/е)/!оя(п)) элементов. В то же время из нашего доказательства универсальности и теоремы Соловея-Китаева вытекает, что любой и-кубитовый унитарный оператор У может быть аппроксимирован с точностью е с помощью 0(пз4" 1об'(пэ4" /с)) элементов. Таким образом, описанная выше универсальная конструкция оптимальна с точностью «до полинома»; к сожалению, она не помогает понять, какие унитарные операции могут быть эффективно вычислены в модели квантовых схем. 4.5.5 Сложность квантовых вычислений Гл. 3 была посвящена сложности вычислений на классических компьютерах. Неудивительно, что и применительно к квантовым компьютерам было бы интересно развить теорию сложности, которая давала бы ответ на вопрос, какие ресурсы требуются для квантовых вычислений, а также сравнить эту теорию с классической теорией сложности.
Пока что в этом направлении сделаны лишь первые шаги, но эта тема, несомненно, еще принесет множество открытий будущим исследователям. Мы же ограничимся изложением только одиного результата из квантовой теории сложности, а именно: установим связь между квантовым классом сложности ВЯР и классическим классом сложности РЯРАСЕ. Обсудим этот результат неформально; более подробное рассмотрение содержится к статье Бернштейна и Вазирани (см. раздел «История и дополнительная литература» в конце главы).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
