Учитывая функцию (реализованную черным ящиком или оракулом) с обещанием, что для каких-то неизвестных , для всех ,
- если и только если ,
Цель состоит в том, чтобы идентифицировать s , выполняя как можно меньше запросов к f (x) .
Еще одна распространенная постановка этой проблемы - различение случай, когда функция взаимно однозначна, из случай, когда функция взаимно однозначна и удовлетворяет .
Пример
Например, если , то следующая функция является примером функции, которая удовлетворяет требуемому и только что упомянутому свойству:
| |
---|
000 | 101 |
001 | 010 |
010 | 000 |
011 | 110 |
100 | 000 |
101 | 110 |
110 | 101 |
111 | 010 |
В таком случае, (т.е. решение). Легко проверить, что каждый вывод встречается дважды, и две входные строки, соответствующие любому заданному выходу, имеют побитовое исключающее ИЛИ, равное .
Например, входные строки а также оба сопоставлены ( ) в ту же строку вывода . а также . Если мы применим XOR к 010 и 100, мы получим 110, то есть также можно проверить с помощью входных строк 001 и 111, которые обе отображаются (посредством f) в одну и ту же выходную строку 010. Если мы применим XOR к 001 и 111, мы получим 110, то есть . Это дает такое же решение мы решили раньше.
В этом примере функция f действительно является функцией два к одному, где.
Для индивидуальной функции такой, что
Сложность проблемы
Интуитивно это очень сложно решить «классическим» способом, даже если использовать случайность и допускать небольшую вероятность ошибки. Интуиция, стоящая за твердостью, довольно проста: если вы хотите решить проблему классическим способом, вам нужно найти два разных входа. а также для которого . В функции не обязательно должна быть какая-либо структура. это поможет нам найти два таких входа: более конкретно, мы можем узнать кое-что о (или что он делает) только тогда, когда для двух разных входов мы получаем один и тот же результат. В любом случае нам нужно будет угадать различные входы, прежде чем можно будет найти пару, на которой принимает тот же результат, что и в задаче о дне рождения . Поскольку классически, чтобы найти s со 100% уверенностью, потребовалось бы проверить довходных данных, задача Саймона заключается в поиске s с использованием меньшего количества запросов, чем этот классический метод.
Идея
Идея высокого уровня, лежащая в основе алгоритма Саймона, состоит в том, чтобы «исследовать» (или «выбрать») квантовую схему (см. Рисунок ниже) «достаточно раз», чтобы найти ( линейно независимые ) n- битные строки, то есть
такие, что выполняются следующие уравнения
где - скалярное произведение по модулю 2 ; это,, а также , для и для .
Итак, эта линейная система содержит линейные уравнения в неизвестные (т. е. части ), и цель состоит в том, чтобы решить его, чтобы получить , а также фиксируется для данной функции . Не всегда есть (единственное) решение.
Квантовая схема Саймона
Квантовая схема, представляющая / реализующая алгоритм Саймона
Квантовая схема (см. Рисунок) - это реализация (и визуализация) квантовой части алгоритма Саймона.
Сначала готовится квантовое состояние всех нулей (это легко сделать). Штат представляет где количество кубитов. Затем половина этого состояния преобразуется с помощью преобразования Адамара. Затем результат передается в оракул (или «черный ящик»), который умеет вычислять. Где действует на два регистра как . После этого часть вывода, производимого оракулом, преобразуется с помощью другого преобразования Адамара. Наконец, выполняется измерение итогового квантового состояния в целом. Именно во время этого измерения мы извлекаем n- битные строки,, упомянутые в предыдущем подразделе.
Алгоритм Саймона можно рассматривать как итерационный алгоритм (который использует квантовую схему), за которым следует (возможно) классический алгоритм для поиска решения линейной системы уравнений.
В этом разделе подробно объясняется каждая часть алгоритма Саймона. При чтении каждого из следующих подразделов может быть полезно взглянуть на изображение квантовой схемы Саймона выше.
Вход
Алгоритм Саймона начинается с ввода , где квантовое состояние с нули.
(Символ - типичный символ, используемый для представления тензорного произведения . Чтобы не загромождать обозначения, символ иногда опускается: например, в предыдущем предложении эквивалентно . В этой статье он (часто) используется для устранения двусмысленности или во избежание путаницы.)
Пример
Так, например, если , то начальный ввод
- .
Первое преобразование Адамара
После этого входные данные (как описано в предыдущем подразделе) преобразуются с использованием преобразования Адамара . В частности, преобразование Адамара ( тензорное произведение также может применяться к матрицам) применяется к первому кубиты, то есть в «частичное» состояние , так что составное состояние после этой операции
где обозначает любую n- битную строку (т. е. суммирование производится по любой n- битной строке). Термин может быть исключен из суммирования, потому что он не зависит от (т.е. это константа по отношению к ), а также .
Пример
Предположим (снова) , то вход и преобразование Адамара является
Если мы сейчас применим к первому , т.е. в состояние
мы получаем
Чтобы получить окончательное составное квантовое состояние, мы можем теперь тензорное произведение с участием , это
Oracle
Затем мы вызываем оракул или черный ящик ( на картинке выше), чтобы вычислить функцию на преобразованном входе , чтобы получить состояние
Второе преобразование Адамара
Затем мы применяем преобразование Адамара к состояниям первого кубиты состояния , чтобы получить
где может быть или же , в зависимости от , где , для . Так, например, если а также , тогда , которое является четным числом. Таким образом, в этом случае, а также всегда является неотрицательным числом.
Интуиция, лежащая в основе применяемого здесь обратного преобразования Адамара, может быть найдена в конспектах лекций CMU.
А теперь перепишем
следующим образом
Эта манипуляция будет удобна для понимания объяснений в следующих разделах. Порядок суммирования изменен на обратный.
Измерение
После выполнения всех ранее описанных операций в конце схемы выполняется измерение .
Теперь есть два возможных случая, которые мы должны рассмотреть отдельно.
- или же
- , где .
Первый случай
Давайте сначала проанализируем (частный) случай , что обозначает является (по требованию) однозначной функцией (как объяснено выше в «описании проблемы»).
Помните, что квантовое состояние до измерения
Теперь вероятность того, что результат измерения в каждой строке является
Это следует из
потому что два вектора различаются только порядком их записей, учитывая, что это один-к-одному .
Значение правой части, то есть
легче увидеть .
Таким образом, когда , результат - это просто равномерно распределенный -битовая строка.
Второй случай
А теперь разберем дело , где . В таком случае, является функцией два к одному, то есть есть два входа, которые сопоставляются с одним и тем же выходом .
Анализ, выполненный в первом случае, все еще действителен для этого второго случая, то есть вероятность измерить любую заданную строку все еще можно представить как
Однако во втором случае нам все еще нужно выяснить, что это за значение является. Давайте разберемся, почему, в следующих пояснениях.
Позволять , образ . Позволять (т.е. какой-то вывод функции ), то для каждого , есть один (и только один) , такое что ; кроме того, у нас также есть, что эквивалентно (см. раздел «Описание проблемы» выше для обзора этой концепции).
Следовательно, мы имеем
Учитывая, что , то можно переписать коэффициент следующим образом
Учитывая, что , то мы можем далее записать выражение выше как
Так, в дальнейшем можно записать как
Нечетное число
Сейчас если нечетное число, тогда . В этом случае,
Следовательно, мы имеем
Учитывая, что , то у нас никогда не бывает этого дела, то есть нет строки виден (после измерения) в этом случае.
(Это тот случай, когда у нас есть деструктивная интерференция .)
Четное число
Если вместо этого - четное число (например, ноль), то . В этом случае,
Итак, у нас есть
В случае конструктивного вмешательства ,
. Итак, в общем, для этого второго случая у нас есть следующие вероятности
Классическая постобработка
Когда мы запускаем схему (операции) выше, возможны два случая:
- в (частном) случае, когда (т.е. ) результаты измерений в каждой строке с вероятностью
- в случае (где ) вероятность получить каждую строку дан кем-то
Таким образом, в обоих случаях результат измерения представляет собой некую строку это удовлетворяет , и распределение является равномерным по всем строкам, которые удовлетворяют этому ограничению.
Достаточно ли этой информации, чтобы определить ? Ответ - «да», при условии, что процесс (см. Выше) повторяется несколько раз (и допускается небольшая вероятность отказа). В частности, если вышеуказанный процесс запущен раз мы получаем струны , такое что
Это система линейные уравнения в неизвестные (т. е. части ), и цель состоит в том, чтобы решить его, чтобы получить . Обратите внимание, что каждый из то, что мы получаем после каждого измерения (для каждого «раунда» процесса), конечно же, является результатом измерения, поэтому он известен (в конце каждого «раунда»).
Мы получаем только единственное ненулевое решение если нам "повезет" и линейно независимы. Вероятность того, что линейно независимы, не менее
Если у нас есть линейная независимость, мы можем решить систему, чтобы получить возможное решение и проверить это . Если, мы знаем это , и проблема решена. Если, это должно быть так (потому что, если бы это было не так, единственное ненулевое решение линейных уравнений было бы ). В любом случае, когда у нас есть линейная независимость, мы можем решить проблему.