вступление

Наилучший способ описания квантового алгоритма обычным компьютерным ученым - это «загадка, окутанная тайной, внутри загадки». В этой статье я надеюсь ответить на фундаментальный вопрос, который время от времени задает себе каждый компьютерный ученый: «Что-то происходит?», Но о более ограниченном объеме квантовых алгоритмов.

Полезные ресурсы, которые я нашел по пути:

  • Замечательная вводная серия блогов о квантовых вычислениях
  • Квантовые алгоритмы через линейную алгебру [Книга на 200 страниц, в которой теория строится с нуля. В целом я считаю, что она была довольно хорошей и удобочитаемой, и большая часть этой статьи взята из этой книги.]
  • Квантовые алгоритмы: обзор
  • Квантовые вычисления и квантовая информация [Описанная как Библия для квантовых вычислений, но во многом похожая на настоящую Библию, она довольно длинная, поэтому я еще не прочитал ее полностью.]

Фон

Что вы должны знать, прежде чем это читать?

Оказывается, квантовые вычисления очень похожи на машинное обучение (читай: линейная алгебра). При этом, чтобы получить максимальную отдачу от этого поста, было бы неплохо, если бы вы знали некоторую линейную алгебру - но я хочу сделать это доступным, поэтому я постараюсь ограничить необходимую техническую подготовку и объяснять все по ходу.

О каком уровне абстракции мы говорим?

Обычно, когда кто-то говорит об алгоритме, большинство людей думают о чем-то вроде

def cool_sort (my_list):

if is_sorted (my_list): вернуть my_list

вернуть cool_sort (random_shuffle (my_list))

И это могло бы сделать что-то вроде

cool_sort ([3,2,1]) = [1, 2, 3]

Но в этом посте мы рассматриваем алгоритмы гораздо более низкого уровня - саму схему. Элементы, имеющиеся в нашем распоряжении, больше похожи на сумматоры, ALU и т. Д. Например, полусумматор - это логическая схема, которая просто складывает два бита вместе. Функция выглядит примерно так

Half_Add (0, 0) = 00

Half_Add (0, 1) = 01

Half_Add (1, 0) = 01

Half_Add (1, 1) = 10

И это делается через схемы и выглядит примерно так:

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

Позже, когда мы будем говорить об этих U-матрицах, просто имейте в виду, что это физические схемы, работающие на физических кубитах. Это тоже алгоритмы, и я буду использовать «квантовые алгоритмы» и «квантовые схемы» как синонимы.

Вопрос о создании хорошего квантового чипа, языка программирования и т. Д. Все еще остается открытым. Если вам интересно разработать квантовый компьютер с полным стеком, обязательно ознакомьтесь с серией блогов, на которую я ссылался выше.

Создание квантовой схемы

Механика

В общем, функция принимает какие-то входные данные, выполняет некоторые полезные вычисления и выдает результат. Квантовые алгоритмы не являются исключением. В квантовом случае - вход - это некоторые квантовые биты, наша программа - это некоторые матрицы U1, U2, U3,…, а выход - те же квантовые биты, которые у нас были раньше, но, надеюсь, мы проделали некоторую полезную работу, и новое состояние из этих квантовых битов есть что-то значимое.

Основная механика квантовой схемы на самом деле довольно проста - это всего лишь линейная алгебра и крошечный бит вероятности.

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

Схема квантовой схемы выглядит так

  • Начнем с базового входного вектора, назовем его X.
  • Умножаем его на связку квадратных матриц U1, U2, U3,…, Un. Получается что-то вроде
    Un Un-1… U3 U2 U1 X = Y
  • Выборка вывода пропорциональна | Y | ** 2, где ** 2 - квадратный элемент. Итак, если Y ^ T было [1/2, 1/2, 1/2, 1/2], то поэлементный квадрат будет [1/4, 1/4, 1/4, 1/4] и у вас равная вероятность каждого исхода. Это также верно, если Y было [1/2, 1/2, -1/2, -1/2] или даже [1/2, 1/2, 1/2 i, 1/2 i]. И этот выборочный результат Y - результат вашего алгоритма!
  • Вуаля! Похлопайте себя по спине, потому что вы только что выполнили квантовый алгоритм!

Есть несколько правил, которые нам нужно придерживаться, чтобы сделать этот алгоритм действующим.

  • ||X||^2 = 1
  • U унитарен [что означает (U ^ T) U = I или U * U = I, если U имеет сложные элементы].

Видеть? Очень просто. Теперь мы выработаем некоторую математическую интуицию, а затем я расскажу вам, как это относится ко всему, а затем мы ретушируем схему с нашим новым удивительным пониманием.

Итак, давайте сначала сделаем небольшой обзор некоторой линейной алгебры, и мы увидим, как это связано с этими унитарными матрицами.

Если мы вспомним, определитель матрицы измеряет, как матрица изменяет пространство, в котором она работает. Итак, если у нас есть матрица A с det (A) = 2, то одна единица пространства перед этим удвоится в размере, как только вы примените A. Или, если det (A) = 0, то одна единица пространства будет полностью уничтожена, когда вы применить A, и именно поэтому A не является обратимым, если и только если det (A) = 0, потому что, как только пространство будет уничтожено, вы не сможете его не уничтожить. Этот эффект на изменение размера пространства является причиной того, почему определитель появляется в многовариантном уравнении изменения переменных, потому что вам необходимо масштабировать в зависимости от того, как система уравнений изменяет размер пространства.

Итак, одно свойство унитарных матриц состоит в том, что | det (U) | = 1. Это означает, что наша унитарная матрица будет хорошо сохранять вещи, и она не будет ничего растягивать или сжимать - она ​​просто перемещает вещи. Фактически, если мы говорим о R ^ 2, то единственными возможными унитарными матрицами, которые у нас есть, являются идентичность, вращения относительно начала координат и скручивания относительно других векторов или некоторая комбинация вращений и скручиваний. Но хотя вектор сейчас указывает куда-то еще, он все еще такой же длины.

Итак, геометрически мы можем интерпретировать наш алгоритм так: мы начинаем с вектора, который лежит на единичной окружности, и наше преобразование должно удерживать его на единичной окружности. Таким образом, к концу применения всех этих матриц мы имеем || Y || ^ 2 = 1, и когда мы делаем выборку через квадратично-нормированные элементы, мы выбираем из допустимого распределения вероятностей. Ура!

Визуально это выглядит как синие стрелки на этой картинке, красные стрелки не важны для того, что нам нужно визуализировать.

Как мы видим, мы применяем различные Us к синему вектору, но он остается на круге, он просто указывает в разные стороны!

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

Давайте начнем с простого - если у нас есть кубит, мы можем измерить его как 0 или 1. Но кубит не обязательно должен быть детерминированным 0 или 1. У нас может быть кубит, так что есть некоторая вероятность, что он будет быть 0 или 1. Первое, что вам нужно сделать, это представить их непосредственно как вероятности, которые будут выглядеть как вектор [a, b], где a + b = 1, а a, b ›= 0. Но, как вы, возможно, догадались из того, о чем я говорил выше, мы также можем представить его [x, y], где | x | ^ 2 + | y ​​| ^ 2 = 1, а наш кубит равен 0 с вероятностью | x | ^ 2 и 1 с вероятностью | y | ^ 2. И оказывается, так лучше.

Следует отметить, что для 1 бита нам потребовались две переменные состояния, одна для 0 и одна для 1, и, как правило, для n бит нам нужны векторы размером 2 ^ n, потому что нам нужна одна строка для каждого возможного состояния.

Если вы посмотрите на 2-битный случай, то нас интересуют векторы, которые представляют [00, 01, 10, 11] или в 3-битном случае [000, 001, 010, 011, 100, 101, 110, 111].

[Помимо технических вопросов, не стесняйтесь игнорировать эту часть: если бы это были вероятности, нам потребовались бы только значения (2 ^ n) -1. Это связано с тем, что вероятности должны составлять в сумме единицу, и поэтому вы всегда можете выяснить, какое из них будет последним, если у вас есть все остальные значения. Но в общем случае в квантовом случае мы используем комплексные числа, и поэтому вы смотрите на | x1 | ^ 2 + | x2 | ^ 2 +…. = 1. Это означает, что, хотя величину последнего значения всегда можно вычислить, по той же причине, по которой мы всегда могли вычислить его для вероятностей, значение все равно необходимо указать, потому что это может быть любой вектор с этой величиной. ].

Итак, базис рассматриваемого нами векторного пространства выглядит так (в 2-битном случае) [E00, E01, E10, E11]. Вектор [1, 0, 0,0] означает, что у нас наверняка есть кубит 00, а вектор [1/2, 1/2, 1/2, 1/2] означает, что если мы измерили наш кубит, то в 25% случаев это будет 00, 01, 10 или 11.

Итак, давайте ретушируем схему квантового алгоритма.

  • Начнем с базового входного вектора, назовем его X, где || X || ^ 2 = 1

X - векторное представление состояния наших входных кубитов, поэтому || X || ^ 2 = 1. Почти во всех наших квантовых алгоритмах мы хотим начать с кубитов, состояние которых нам известно. Поскольку нет никакой неопределенности относительно того, какое состояние является векторным представлением, будет что-то вроде [1, 0, 0, 0] или [0, 1, 0, 0].

  • Применим наши унитарные матрицы U1, U2,… Un, чтобы получить результат
    Un-1… U3 U2 U1 X = Y

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

  • Выясните новое состояние наших кубитов, выбрав результат пропорционально | Y | ** 2

Y - это новое представление состояния наших кубитов, и когда мы измеряем наши кубиты, мы заставляем их принимать определенное значение, например 00 или 11. Это то же самое, что и выбор одного из наших базисных векторов E00, E01 и т. Д. Затем | Y | ** 2 просто говорит нам, насколько вероятно, что мы увидим каждую возможную конфигурацию кубитов, и поэтому эта процедура выборки эквивалентна измерению системы.

Алгоритм Дойча-Йозса

Из Википедии алгоритм Дойча-Йозса - это пчелиные колени, потому что:

Проблема Дойча – Йожи специально разработана, чтобы быть простой для квантового алгоритма и сложной для любого детерминированного классического алгоритма. Мотивация состоит в том, чтобы показать проблему черного ящика, которая может быть эффективно решена квантовым компьютером без ошибок, тогда как детерминированный классический компьютер потребует экспоненциально много запросов к черному ящику для решения проблемы.

Основная идея состоит в том, что нам нужен алгоритм, который может определить, является ли некоторая логическая функция F постоянной функцией. Эта функция F принимает на входе n битов и возвращает на выходе один бит или, альтернативно, истину или ложь.

Математически это выглядит как

F:{0,1}^n ->{0, 1}

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

В этом сообщении в блоге мы поговорим о простом случае, когда F - однобитовая функция, поэтому F: {0,1} - ›{0,1}.

Прежде всего, нужно немного поработать, прежде чем мы поговорим об алгоритме, и было бы хорошо, если бы это не мешало нам, чтобы нам не приходилось делать это посередине, так что давайте сделаем это. Теперь есть четыре возможных однобитовых F: F (x) = x, F (x) = not x, F (x) = 0 и F (x) = 1. Но нас интересует другой объект, связанный с F. В этом разделе xy означает x concat y, и оба они являются битами. Нас интересует функция G, где

G_F (xy) = x concat (F (x) XOR y)

Итак, если F является тождеством,
G_I (00) = 0 concat (F (0) XOR 0) = 0 concat (0 XOR o) = 00

Давайте создадим несколько матриц таблицы истинности G для каждого возможного F. Помните, наш базис [E00, E01, E10, E11] ^ T. Итак, если мы посмотрим на G * [1, 0, 0, 0] ^ T, это то же самое, что и G (00), и G * [0, 0, 1, 0] ^ T скажет нам, что произошло, если бы произошло G (10). Поскольку один конкретный вход для G будет иметь один конкретный выход, мы ожидаем, что каждая строка будет иметь только одну единицу, указывающую, какими будут выходные биты.

Давайте рассмотрим наглядный пример. Рассмотрим случай, когда F (x) = not x

Тогда G выглядит как

G (00) = 0 concat (F (0) XOR o) = 0 concat (1 XOR 0) = 01

G (01) = 0 concat (F (0) XOR 1) = 0 concat (1 XOR 1) = 00

G (10) = 1 concat (F (1) XOR o) = 1 concat (0 XOR 0) = 10

G (11) = 1 concat (F (1) XOR 1) = 1 concat (0 XOR 1) = 11

Итак, матрица G_not выглядит как

И аналогично, другие значения G выглядят так (G_T - G true, G_F - G false, и G_I - идентичность G)

Теперь создание G - вот где кажется, что мы жульничаем. Я сказал, что мы можем реализовать этот алгоритм с одним вызовом функции, но очевидно, что нам нужно было оценить все возможные значения функций, чтобы получить G, и мы собираемся использовать G в нашем алгоритме - так что сделал ли я более одного вызова в алгоритме?

Ответ - нет. G предназначен только для бухгалтерского учета. Если мы посмотрим на схему самого алгоритма Дойча-Йозса, она выглядит так:

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

Со всем весельем, у нас есть это в стороне, мы можем представить наш алгоритм

  1. Возьмем X = [0, 1, 0, 0] ^ T (Итак, мы начинаем с кубитов 01)
  2. Применить H4
  3. Применить G
  4. Применить R
  5. Измерьте выход и посмотрите на первый бит

Где H4 и R [Примечание: я забыл нормировочную константу на H4, чтобы сделать ее унитарной, но это просто означает, что норма всех этих векторов будет c вместо 1, и нам действительно не хватало 1 / c]

Давайте сделаем пошаговое руководство по этому

Если мы посмотрим на H4X, мы получим следующие результаты

Результирующий вектор [1, -1, 1, -1] ^ T означает, что если бы мы измеряли сейчас, у нас есть 25% шанс увидеть кубит в любом состоянии - 00, 01, 10, 11. Итак, мы взяли наш начальный вектор и почти «равномерно» распределили его по всем возможным состояниям - но даже если бы мы измеряли равномерно, в пространстве больше структуры, так как некоторые записи имеют разные знаки!

Теперь, если мы посмотрим на GH4X для всех возможных G, мы получим

Это похоже на беспорядок, но это будет иметь смысл после того, как мы применим следующую матрицу.

RGH4X тогда выглядит следующим образом

Теперь произошло кое-что действительно интересное - если вы заметили True и False, которые являются единственными способами, которыми F является постоянным, сопоставьте только с E00 и E01, а Not и Identity сопоставьте с E10 и E11. Итак, если F была функцией True или False, мы не знаем, будет ли вывод нашей программы 00 или 01, поскольку это произойдет с вероятностью 50/50, но мы знаем, что первый бит всегда будет равен 0. Точно так же для I и Not существует вероятность 50/50, что это будет 10 или 11, но опять же, первый бит всегда равен 1. Это означает, что если мы посмотрим на самый левый бит вывода, мы сможем определить, является ли F было постоянно или нет!

Магия кванта

Теперь, когда у нас есть все необходимое, есть две причины, по которым квантовые алгоритмы круты.

  1. Представление, которое мы выбрали (ну, мать-природа выбрала для нас), намного сильнее, чем простые оценки вероятности, и может выражать более сложные вещи.
  2. Qubits хранит «дистрибутивы», а не экземпляры

Причина, по которой я написал алгоритм до этого раздела, заключается в том, что мы видим обе причины в самом алгоритме.

Сначала давайте посмотрим на представление, но в контексте алгоритма Дойча-Йозса. Если бы мы измеряли после GHX, это было бы не очень интересно. Каждый вектор отличается, но каждый компонент каждого вектора имеет одинаковую величину. Любая функция F заставит это действовать одинаково в этой точке алгоритма - равные шансы измерить любое состояние. Так что с вероятностной точки зрения это не очень интересно, все они представляют собой просто однородные распределения. Таким образом, мы не могли ничего сделать в этот момент, потому что все распределения одинаковы, и поэтому мы ничего не можем сделать с наблюдением, чтобы выяснить, из какого оно произошло.

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

И если задуматься, есть один способ представить равномерное распределение по N числам, а именно вектор вероятности [1 / N, 1 / N,…, 1 / N], но пространство x, где || x | | ^ 2 = 1, существует бесконечно много точек, которые могут представлять это распределение всей формы [e ^ (ia) / sqrt (N), e ^ (ib) / sqrt (N), e ^ (ic) / sqrt (N),…] и даже включает то, что было раньше с точкой [1 / sqrt (N), 1 / sqrt (N),…]. Так что это круто, потому что у вас есть распределения, которые с вероятностной точки зрения одинаковы, но означают разные вещи и по-разному взаимодействуют.

Вторая действительно крутая часть заключается в том, что кубиты хранят «распределения», а не экземпляры. Чтобы проверить это, давайте рассмотрим шаг, на котором мы применили G к H4X.

Давайте вспомним, как выглядит H4X

И мы видим, что часть наших кубитов находится в каждой возможной конфигурации. Затем, когда мы умножаем G на H4X, мы получаем вызов G для каждого возможного состояния. Четыре по цене одного! (Или в общем случае 2 ^ n по цене 1!)

Чтобы лучше в этом убедиться, давайте посмотрим, что было бы классическим аналогом. Помните, ранее я упоминал, что если у вас есть детерминированная логическая функция, то, используя нашу матрицу таблицы истинности, вы можете выполнить один поиск за один раз - это то же самое, что и выполнение G * E, где E ^ T является одним из следующие за [1, 0, 0, 0], [0, 1, 0, 0], [0, 0, 1, 0] или [0, 0, 0, 1]. Таким образом, эквивалентная классическая операция

Что больше соответствует тому, что мы ожидали - нам нужно 4 оценки F, чтобы определить, все ли выходы равны.

Но поскольку кубиты не приобретают ценности, пока мы их не измерим, мы можем уйти от некоторых безумных вещей.

Итак, в заключение, используя лучшее представление и имея возможность переносить больше состояний, вы можете уйти от некоторых довольно крутых вещей!

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