М. Нильсен, И. Чанг - Квантовые вычисления и квантовая информация (1156771), страница 57
Текст из файла (страница 57)
Вовторых, показывается, что существует небольшой по размеру набор элементов квантовых схем, являющийся уииверсольпььи в том смысле, что любое квантовое вычисление может быть реализовано с помощью схемы, составленной из этих элементов. По ходу изложения у нас будет случай рассмотреть и много других фундаментальных результатов, относящихся к квантовым вычислениям. В открывающем главу рэзд. 4.1 содержится обзор квантовых алгоритмов, причем особое внимание уделяется тому, какие алгоритмы известны и какие общие принципы лежат в их основе. В равд.
4.2 подробно описываются операции над одним кубитом. Несмотря на простоту, такие операции предоставляют богатые возможности для построения примеров и разработки технических приемов, и их необходимо изучить подробно. Рэзд. 4.3 посвящен выполнению условиых. унитарных операций над несколькими кубитами, а в резд. 4.4 обсуждается измерение в модели квантовых схем. Затем все эти ингредиенты соединяются в равд. 4.6, где формулируется и доказывается теорема универсальности. В равд. 4.6 еще раз рассматриваются все основные компоненты квантовых.
вычислений и обсуждаются возможные варианты модели квантовых схем, а также важный вопрос о сравнении эффективности классического и квантового компьютеров. Завершающий главу равд. 4.7 посвящен важному и поучительному приложению квантовых вычислений, а именно — моделированию реальных квантовых систем. Данная глава, содержащая большое количество упражнений, для изучения, вероятно, наиболее сложная, так что объясним, почему следует затратить труд на ее освоение.
Научиться работать с основными элементами квантовых схем нетрудно, но для этого необходимо знать большое количество простых результатов и владеть техническими приемами, что поможет перейти к более трудной задаче разработки квантовых алгоритмов. По этой причине глава насыщена примерами и во многих случаях читателю предлагается самостоятельно восполпить детали. Можно ознакомиться с упрощенным (но несколько поверхностным) обзором первооснов квантовых вычислений, для этого следует начать изучение материала с равд. 4.6.
4.1 Квантовые алгоритмы Зачем нужен квантовый компьютер? Нам всем знакомо отчаяние, когда обнаруживается, что для решения некоторой задачи не хватает вычислительных 4.1. Квантовые алгоритмы 223 возможностей. Собственно говоря, многие интересные задачи нельзя решить яа классическом компьютере не из-за их неразрешимости, а потому, что объем требуемых ресурсов выражается астрономическим числом. Созлание квантовых компьютеров дает надежду на то, что можно будет реализовать новые алгоритмы, которые позволят решать задачи, требующие чрезмерно больших ресурсов при использовании классического компьютера.
На момент написания книги известны два широких класса квантовых алгоритмов, соответствующих этим ожиданиям. Первый из них основан на принадлежащем Шору кеантпоеам преобразовании Фурье и включает замечательные алгоритмы решения задач факторизации и вычисления дискретного логарифма с экспоненциальным ускорением по сравнению с наилучшими известными классическими алгоритмами. Второй класс алгоритмов связан с алгоритмом Гравера для кванпзоеого поиска.
Эти алгоритмы обеспечивают квадратичное ускорение наилучших возможных классических алгоритмов, но не столь поразительное, как в первом случае. Алгоритм квантового поиска важен ввиду широкого использования поиска в классических алгоритмах, так что во многих случаях оказывается возможным прямое преобразование классического алгоритм в более быстрый квантовый. На рис. 4.1 представлены известные в настоящее время квантовые алгоритмы и некоторые примеры их применения. Разумеется, в основе приведенной диаграммы лежат квантовое преобразование Фурье и квантовый поиск.
Особенно интересен алгоритм квантового перечисления. Этот алгоритм, представляющий собой остроумную комбинацию из квантового поиска и преобразования Фурье, может быть использован для более быстрой, чем это возможно в случае использования классического компьютера, оценки числа решений задачи поиска. Рис. 4.1. Основные квантовые алгоритмы и ик взаимосвязь (а также некоторые приложения) Алгоритм квантового поиска имеет много потенциальных приложений, некоторые из них приведены на рисунке. Так его можно использовать для более быстрого, чем на классическом компьютере, нахождения статистик (например, наименьшего элемента) в неупорядоченном наборе данных.
С его помощью 224 Глава 4. Квантовые схемы можно ускорить алгоритмы для решения некоторых задач класса ХР— тех задач, для которых не известен лучший алгоритм, чем прямой перебор. Наконец, его применение позволит ускорить поиск ключа к таким криптосистемам, как широко используемая 1Эа1а Епсгур11оп Зьапс1эгс1 (РЕЯ).
Эти и другие приложения будут рассмотрены в гл 6. Квантовое преобразование Фурье также имеет много интересных приложений. С его помощью можно решить задачи вычисления дискретного логарифма и факторизации. Это в свою очередь позволяет "взломать" с помощью квантового компьютера многие из наиболее популярных криптосистем, включая НЗА. Помимо этого, оказывается, что преобразование Фурье тесно связано с важной математической задачей о скрытой подгруппе (обобщение задачи нахождения периода периодической функции). Квантовому преобразованию Фурье и некоторым его приложениям, в том числе быстрым квантовым алгоритмам для факторизации и вычисления дискретного логарифма, посвящена гл.
5. Почему известно так мало квантовых алгоритмов, превосходящих свои классические аналоги? Ответ состоит в том, что разработка хорошего квантового алгоритма является, похоже, трудной задачей. На это имеются по меньшей мере две причины. Прежде всего разработка любых алгоритмов — классических или квантовых — непростое дело! История показывает, что даже в очень простых на первый взгляд задачах, подобных умножению двух чисел, зачастую приходится проявлять изобретательность для того, чтобы получить алгоритм, близкий к оптимальному. Искать хорошие квантовые алгоритмы трудно вдвойне, поскольку при этом необходимо удовлетворить дополнительное условие: квантовые алгоритмы должны быть лучше, чем известные классические.
Вторая состоит в том, что наша интуиция гораздо лучше приспособлена к классическому миру, чем к квантовому. Если исходить из интуиции, то построенные алгоритмы будут классическими. Чтобы получались хорошие квантовые алгоритмы, необходимы особал интуиция и особые ухищрения. Более глубокому изучению квантовых алгоритмов будет посвящена следующая глава.
Здесь же мы введем эффективный и мощный язык для их описания — язык квантовых схем, которые являются агрегатами из конечного набора компонентов и описывают вычислительные процедуры. Эта конструкция позволяет нам оценить качество алгоритма или через общее количество элементов в схеме, или через глубину схемы.
Вместе с языком схем вводится и набор приемов, позволяющих упростить разработку алгоритмов и достичь их концептуального понимания. 4.2 Операции на одном кубите Рассмотрение нашего инструментария для квантовых вычислений начнем с операций на простейшей возможной квантовой системе — одном кубите. Понятие кубита было введено в подразд. 1.3.1. Напомним вкратце, о чем там шла речь. Кубит — это вектор )ф) = а(0)+6(1), параметризованный двумя комплексными числами, удовлетворяющими условию (а)з+)6(з = 1. Операции над кубитами 4.2.
Операции на одном кубите 225 должны сохранять эту нормализацию и тем самым описываются унитарными матрицами 2 х 2, из которых одними из наиболее полезных являются матрицы Паули; стоит выписать их еще раз: — — (4.1) В дальнейшем большую роль будут играть три других квантовых элемента: оператор Адамара (обозначаемый символом «Н» ), оператор сдвига фазы («Я») и элемент н/8 («Т»): ,/ ' ' ' О ехр(1я/4) Вот два полезных алгебраических факта, которые стоит помнить: Н = (Х + Я)/~/2 и Я = Т2. Можно задаться вопросом почему Т называется элементом и/8, если в определении присутствует л/4? Причина заключается в том, что с точностью до не играющей роли общей фазы элемент Т есть матрица, на диагонали которой стоят числа ехрфиг/8): Т = ехр(' /8) ~ ехр(-вя/8) 0 0 ехр(1я/8) ) ' (4.3) в в ЭШ2 СОЗВ е-«в/ О 0 «в/2 Н (д) ьпе / =сов-1 — 1з1п-Х= -ых2 О,, д 2 2 (4.4) Нэ(д) — = е ' =соя-1 — 1еш-У= 2 2 (4.5) д Н,(д) изе «вл/2 = сов-1 — вэ1п-т = 2 2 (4.6) откуда и возникло в свое время название «я/8».
Все же данный термин является довольно неудачным, и мы часто будем называть этот элемент просто «элемент Т». Напомним также, что кубит в состоянии а)0) + Ь(1) можно представить себе как точку (д, ~р) на единичной сфере, где а = сое(д/2), Ь = ечв э1п(д/2), а число а можно считать действительным, поскольку общая фаза состояния ненаблюдаема. Это — уже обсуждавшееся в гл. 1 представление на сфере Блоха, и вектор (сов <р э1п д, е1п <р сов д, соэ д) называется блоховским.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
