Концепция квантового параллелизма мощна, и ее нетрудно понять. Мы объясним это в этой статье. Но, несмотря на некоторое разочарование, создать квантовый алгоритм, превосходящий классический, сложно. Вот почему у нас пока нет большого зоопарка квантовых алгоритмов. Здесь мы потратим некоторое время на обсуждение проблем и рассмотрим некоторые решения. Для тех, кто не знаком с квантовыми операторами, сначала обратитесь к Части 3 нашей серии статей о квантовых вычислениях.
Квантовый параллелизм
Возможности квантового параллелизма можно резюмировать в следующей матрице. Мы применяем унитарную операцию для управления кубитом (ами) за один шаг (на практике полиномиальные шаги).
Поскольку количество компонентов в вычислительной базе экспоненциально увеличивается с увеличением количества кубитов, квантовый параллелизм предлагает возможность вычисления f (x) со всеми допустимыми значениями x одновременно. .
Подготовьте и закрепите наложение
К сожалению, есть несколько серьезных проблем, которые ограничивают типы проблем, которыми мы можем воспользоваться. Его успех зависит от:
- Можем ли мы подготовить состояние суперпозиции за полиномиальное время?
- Можем ли мы объединить суперпозиции, чтобы мы могли также измерить их за полиномиальное время?
- Сможем ли мы найти для этого унитарные операторы?
Давайте проиллюстрируем эту концепцию дальше. Мы сосредоточимся на общей картине и поэтому не будем беспокоиться, если некоторые детали упущены. Квантовый алгоритм может состоять из трех этапов перед выполнением измерения.
Сначала мы готовим суперпозицию, чтобы воспользоваться квантовым параллелизмом. Когда он оказывается в многомерном пространстве, мы создаем много места для манипуляций. Затем мы консолидируем суперпозицию перед измерением. Давайте рассмотрим подробнее.
Самый распространенный и эффективный способ подготовки суперпозиции - вентиль Адамара. Например, мы применяем n вентилей Адамара параллельно, чтобы подготовить n кубитов за один шаг:
В приведенном ниже примере n = 3 и суперпозиция выглядит следующим образом:
Затем нам нужно уточнить суперпозицию так, чтобы коэффициенты в суперпозиции были загружены числами, которые нам нужны для решения проблемы. Чтобы продемонстрировать квантовое превосходство, мы хотим сделать это за полиномиальное время для этого экспоненциального числа коэффициентов.
Это первая серьезная проблема, и зачастую это невозможно. Мы ошибочно ожидаем, что сможем реализовать универсальный квантовый алгоритм, который легко преодолеет проклятие экспоненциальной сложности. Часто ученые вводят функции Oracle, чтобы продемонстрировать квантовое превосходство, упрощая или игнорируя какую-то часть проблемы. Для новичков это становится большим разочарованием, когда понимают, что такие функции Oracle не могут быть эффективно реализованы в общем контексте или что для продемонстрированных реализаций нет потенциального применения. Если вы попросите более практических примеров для функции Oracle, вы можете упустить причину, по которой эта функция вообще существует. Но не расстраивайтесь. Усилия по разработке алгоритмов с функциями Oracle приносят плоды. Решая достаточно проблем, мы разрабатываем такие алгоритмы, как алгоритм Шора, демонстрирующий реальную эффективность квантовых вычислений. Функции Oracle - это ступеньки, которые ведут нас к другим важным алгоритмам.
Корень проблемы очень прост. Если мы относимся к проблеме как к общей проблеме, нам нужно обрабатывать все возможности. Мы не можем предполагать, что данные имеют определенную структуру. Мы не можем избежать проклятия загрузки и изучения каждой информации. Чтобы достичь квантового превосходства, данные, касающиеся проблемы, должны иметь структуру, позволяющую загружать необходимую информацию за полиномиальное время.
Алгоритм Шора решает проблему разложения на простые множители за полиномиальное время и, что более важно, взламывает шифрование RSA. Мы обсудим детали в следующих статьях, но представим здесь общую картину. Факторизация на простые множители находит множители N, состоящие из двух простых чисел. Например, простые множители для 15 равны 3 и 5. Самый быстрый классический алгоритм факторизации простых множителей имеет порядок
где n - количество бит для N.
Мы можем закодировать экспоненциально количество информации в коэффициентах вычислительной базы:
Но мы хотим загрузить необходимые коэффициенты за полиномиальное время. Самая сложная часть алгоритма Шора - найти период функции по модулю во втором регистре ниже. (Регистр - это просто набор кубитов.)
Для a = 7 это выглядит так:
Функция по модулю - это периодическая функция с повторяющимся шаблоном. Это создает структуру, которую мы ищем. В алгоритме Шора мы можем подготовить аналогичный (приближенный) вариант кубитов выше за полиномиальное время! После применения обратного квантового преобразования Фурье (IQFT) к первому регистру мы вычисляем период функции по модулю. Схема ниже демонстрирует, как мы готовим суперпозицию. Затем следует IQFT для вычисления периода.
Хорошая новость в том, что и то, и другое можно сделать за полиномиальное время. Это захватывающий прорыв в исследованиях квантовых вычислений! Ни один классический алгоритм не известен с такой же эффективностью. Используя структуру проблемы, мы используем квантовые методы, чтобы избавиться от проклятия экспоненциальной сложности. Фактически, квантовые алгоритмы до алгоритма Шора обычно считаются игрушечными экспериментами. После алгоритма Шора он привлекает не только академические инвестиции.
Но помните, многие проблемы не могут найти такого перерыва. Не так-то просто разработать алгоритмы с экспоненциальным ускорением по сравнению с классическим аналогом.
Измерения
В классических вычислениях результаты хранятся в переменных, и компьютер просто их считывает. Как мы получаем информацию из квантовых схем? Напомним, что природа не предоставляет средств для прямого доступа к амплитуде (коэффициенту) суперпозиции. Вместо этого мы проводим измерения и получаем ответ из измеренных состояний. Давайте рассмотрим несколько простых возможностей.
Допустим, результатом вычисления должно быть значение 010. Одна из возможностей состоит в том, что алгоритм увеличивает амплитуду α2 для базы вычисления | 010⟩. Таким образом, если повторить расчет много раз, ответом будет наиболее измеренное значение кубита. то есть 010. Таким образом, алгоритм должен увеличить амплитуду до | 010⟩, в противном случае мы должны повторить вычисление и измерение экспоненциальное количество раз, чтобы быть уверенным, какие измерения являются наиболее вероятными.
Другими словами, нам нужно закрепить суперпозицию. Увеличив амплитуду нашего ответа намного выше, мы можем найти ответ, сказав, что повторим расчет только 1000 раз. Конечно, если нам не повезет, наши измерения все равно могут быть неправильными. Но потом мы всегда сможем проверить ответ. Для многих проблем найти решение сложно, но проверить решение намного проще (это характеры проблем NP).
В теории сложности вычислений квантовое полиномиальное время с ограниченной ошибкой (BQP) определяется как класс задач, которые решаются квантовыми вычислениями за полиномиальное время с вероятностью менее 1/3 того, что ответ будет неверным. в каждом пробеге. Это класс алгоритмов, которым хотят заниматься квантовые компьютеры.
Классический компьютер против квантовый компьютер
Классические компьютеры создают базовый набор операций, таких как NOT, NAND и XOR, для построения операций. В квантовых компьютерах мы выполняем линейную алгебру с операторами. Мы можем сделать это быстро с экспоненциальным объемом информации, если операторы унитарны.
Поскольку мы используем в операторе комплексные числа, мы можем создавать уравнения, очень похожие на многие существующие уравнения.
Например, выполнение приведенного ниже дискретного преобразования Фурье (ДПФ) в квантовых компьютерах просто.
Оказывается, это важно для квантовых вычислений. Например, алгоритм Шора зависит от квантового преобразования Фурье для определения периода функции. Далее мы подробно рассмотрим квантовые ворота, фундаментальный строительный блок квантовых алгоритмов.
