Проблема Саймонса - Simons problem

Не путать с Проблемы Саймона в математической физике.

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

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

Задача ставится в модели сложность дерева решений или сложность запроса и был задуман Дэниел Саймон в 1994 году. Саймон выставил квантовый алгоритм, обычно называется Алгоритм Саймона, который решает проблему экспоненциально быстрее, чем любой детерминированный или вероятностный классический алгоритм, требующий экспоненциально меньшего времени вычислений (точнее, запросов), чем лучший классический вероятностный алгоритм. В алгоритме Саймона для квантового алгоритма требуется линейное количество запросов, а не экспоненциальное количество запросов, необходимых для классического вероятностного алгоритма. Эта проблема дает разделение оракула между классами сложности BPP и BQP, в отличие от разделения, предусмотренного Алгоритм Дойча – Йожи, который разделяет п и EQP. Разделение является экспоненциальным (относительно оракула) между квантовой сложностью и классической сложностью запроса с ограниченной ошибкой. Проблема Саймона не доказывает, а скорее демонстрирует, что существует оракул, относительно которого. Оракул, используемый в проблеме Саймона, - это черный ящик, который мы учитываем при вычислениях.

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

Описание проблемы

Учитывая функцию (реализованную черный ящик или оракул) ${\displaystyle f:\{0,1\}^{n}\rightarrow \{0,1\}^{n}}$, обещал удовлетворить свойство, что для некоторого ненулевого ${\displaystyle s\in \{0,1\}^{n}}$ и все ${\displaystyle x,y\in \{0,1\}^{n}}$,

${\displaystyle f(x)=f(y)}$ если и только если ${\displaystyle x\oplus y\in \{0^{n},s\}}$ или же ${\displaystyle {\displaystyle x=y\otimes s}}$

Цель состоит в том, чтобы идентифицировать s и определить, ${\displaystyle s=0^{n}}$ или же ${\displaystyle s\neq 0^{n}}$ запросив f (x).

Здесь, ${\displaystyle s=0^{n}}$ классифицирует взаимно однозначную функцию.

Если ${\displaystyle s\neq 0^{n}}$ , функция является функцией два к одному, такой что ${\displaystyle {\displaystyle x\oplus y\in \{0^{n},s\}}}$

Другими словами, ${\displaystyle f}$ функция два к одному такая, что ${\displaystyle f(x)=f(x\oplus s)}$, для всех ${\displaystyle x\in \{0,1\}^{n}}$ куда ${\displaystyle s\in \{0,1\}^{n}}$ неизвестно.

Цель

Важно помнить, что цель проблемы Саймона - уменьшить количество запросов к черному ящику, чтобы мы могли определять s экспоненциально быстро.

Пример

Например, если ${\displaystyle n=3}$, то следующая функция является примером функции, которая удовлетворяет требуемому и только что упомянутому свойству:

${\displaystyle x}$	${\displaystyle f(x)}$
000	101
001	010
010	000
011	110
100	000
101	110
110	101
111	010

В этом случае, ${\displaystyle s=110}$ (т.е. решение). Легко проверить, что каждый вывод ${\displaystyle f}$ встречается дважды, и две входные строки, соответствующие любому заданному выходу, имеют побитовое исключающее ИЛИ, равное ${\displaystyle s=110}$.

Например, входные строки ${\displaystyle 010}$ и ${\displaystyle 100}$ оба сопоставлены ( ${\displaystyle f}$) в ту же строку вывода ${\displaystyle 000}$. ${\displaystyle {\displaystyle f(010)=000}}$ и ${\displaystyle {\displaystyle f(100)=000}}$. Если мы применим XOR к 010 и 100, мы получим 110, то есть ${\displaystyle {\displaystyle 010\oplus 100=110=s}.}$${\displaystyle s=110}$ также можно проверить с помощью входных строк 001 и 111, которые обе отображаются (с помощью f) в одну и ту же строку вывода 010. Если мы применим XOR к 001 и 111, мы получим 110, то есть ${\displaystyle 001\oplus 111=110=s}$. Это дает такое же решение ${\displaystyle s=110}$ мы решили раньше.

В этом примере функция f действительно является функцией два к одному, где ${\displaystyle {\displaystyle s\neq 0^{n}}}$.

Для однозначной функции ${\displaystyle f(x)=f(y)}$ такой, что ${\displaystyle f(1)=1,f(2)=2,f(3)=3,etc.}$

Сложность проблемы

Интуитивно это очень сложно решить «классическим» способом, даже если использовать случайность и допускать небольшую вероятность ошибки. Интуиция, стоящая за твердостью, довольно проста: если вы хотите решить проблему классическим образом, вам нужно найти два разных входа. ${\displaystyle x}$ и ${\displaystyle y}$ для которого ${\displaystyle f(x)=f(y)}$. В функции не обязательно должна быть какая-либо структура ${\displaystyle f}$ это поможет нам найти два таких входа: более конкретно, мы можем узнать кое-что о ${\displaystyle f}$ (или что он делает) только тогда, когда для двух разных входов мы получаем один и тот же результат. В любом случае нам нужно будет угадать ${\displaystyle {\displaystyle \Omega ({\sqrt {2^{n}}})}}$ различных входов, прежде чем можно будет найти пару, на которой ${\displaystyle f}$ принимает тот же результат, что и проблема дня рождения. Поскольку классически, чтобы найти s со 100% уверенностью, потребовалось бы проверить до ${\displaystyle 2^{n-1}+1}$ входных данных, задача Саймона пытается найти s с использованием меньшего количества запросов, чем этот классический метод.

Обзор алгоритма Саймона

Идея

Идея высокого уровня, лежащая в основе алгоритма Саймона, состоит в том, чтобы «исследовать» (или «выбрать») квантовую схему (см. Рисунок ниже) «достаточно раз», чтобы найти ${\displaystyle n-1}$ (линейно независимый ) п-битовые строки, то есть

${\displaystyle y_{1},y_{2},\dots ,y_{n-1}\in \{0,1\}^{n},}$

такие, что выполняются следующие уравнения

${\displaystyle \left\{{\begin{aligned}y_{1}\cdot s&=0\\y_{2}\cdot s&=0\\&\,\,\,\vdots \\y_{n-1}\cdot s&=0\end{aligned}}\right.}$

куда ${\displaystyle y_{i}\cdot s}$ это по модулю 2 скалярное произведение; то есть, ${\displaystyle y_{i}\cdot s=y_{i1}s_{1}\oplus y_{i2}s_{2}\oplus \dots \oplus y_{in}s_{n}}$, и ${\displaystyle y_{ij},s_{j}\in \{0,1\}}$, за ${\displaystyle i=1,\dots ,n-1}$ и для ${\displaystyle j=1,\dots ,n}$.

Итак, эта линейная система содержит ${\displaystyle n-1}$ линейные уравнения в ${\displaystyle n}$ неизвестные (т. е. части ${\displaystyle s\in \{0,1\}^{n}}$), и цель - решить его, чтобы получить ${\displaystyle s}$, и ${\displaystyle s}$ фиксируется для данной функции ${\displaystyle f}$. Не всегда есть (единственное) решение.

Квантовая схема Саймона

Квантовая схема, представляющая / реализующая алгоритм Саймона

Квантовая схема (см. Рисунок) - это реализация (и визуализация) квантовой части алгоритма Саймона.

Сначала готовится квантовое состояние всех нулей (это легко сделать). Штат ${\displaystyle |0\rangle }$ представляет ${\displaystyle |0^{n}\rangle }$ куда ${\displaystyle n}$ - количество кубитов. Половина этого состояния затем преобразуется с помощью преобразования Адамара. Затем результат передается в оракул (или «черный ящик»), который знает, как вычислить ${\displaystyle f}$. Где ${\displaystyle U_{f}}$ действует на два регистра как ${\displaystyle |x\rangle |0^{n}\rangle \rightarrow |x\rangle |f(x)\rangle }$. После этого часть вывода, производимого оракулом, преобразуется с помощью другого преобразования Адамара. Наконец, выполняется измерение итогового квантового состояния в целом. Именно во время этого измерения мы извлекаем n-битные строки, ${\displaystyle y_{1},y_{2},\dots ,y_{n-1}\in \{0,1\}^{n}}$, упомянутые в предыдущем подразделе.

Алгоритм Саймона можно рассматривать как итерационный алгоритм (который использует квантовую схему), за которым следует (возможно) классический алгоритм для поиска решения линейной системы уравнений.

Алгоритм Саймона

В этом разделе подробно объясняется каждая часть алгоритма Саймона. При чтении каждого из следующих подразделов может быть полезно посмотреть на изображение квантовой схемы Саймона выше.

Вход

Алгоритм Саймона начинается с ввода ${\displaystyle |0^{n}\rangle \otimes |0^{n}\rangle =|0^{n}\rangle |0^{n}\rangle }$, куда ${\displaystyle |0^{n}\rangle }$ квантовое состояние с ${\displaystyle n}$ нули.

(Символ ${\displaystyle \otimes }$ - типичный символ, используемый для обозначения тензорное произведение. Чтобы не загромождать обозначения, символ ${\displaystyle \otimes }$ иногда опускается: например, в предыдущем предложении ${\displaystyle |0^{n}\rangle \otimes |0^{n}\rangle }$ эквивалентно ${\displaystyle |0^{n}\rangle |0^{n}\rangle }$. В этой статье он (часто) используется для устранения двусмысленности или во избежание путаницы.)

Пример

Так, например, если ${\displaystyle n=2}$, то начальный ввод

${\displaystyle |0^{2}\rangle \otimes |0^{2}\rangle =|00\rangle \otimes |00\rangle =(|0\rangle \otimes |0\rangle )\otimes (|0\rangle \otimes |0\rangle )=|0\rangle \otimes |0\rangle \otimes |0\rangle \otimes |0\rangle =|0000\rangle =|0^{4}\rangle =|0^{2n}\rangle }$.

Первое преобразование Адамара

После этого ввод (как описано в предыдущем подразделе) преобразуется с помощью Преобразование Адамара. В частности, Преобразование Адамара ${\displaystyle H^{\otimes n}}$ (в тензорное произведение может также применяться к матрицам) применяется к первому ${\displaystyle n}$ кубиты, то есть в «частичное» состояние ${\displaystyle |0^{n}\rangle }$, так что составное состояние после этой операции

${\displaystyle |\Psi \rangle =\left(H^{\otimes n}|0^{n}\rangle \right)\otimes |0^{n}\rangle =\left(\sum _{x\in \{0,1\}^{n}}{\frac {1}{\sqrt {2^{n}}}}\left|x\right\rangle \right)\otimes \left|0^{n}\right\rangle =\left({\frac {1}{\sqrt {2^{n}}}}\sum _{x\in \{0,1\}^{n}}\left|x\right\rangle \right)\otimes \left|0^{n}\right\rangle ={\frac {1}{2^{\frac {n}{2}}}}\sum _{x\in \{0,1\}^{n}}\left(\left|x\right\rangle \otimes \left|0^{n}\right\rangle \right)}$

куда ${\displaystyle x\in \{0,1\}^{n}}$ обозначает любую n-битную строку (т.е. суммирование производится по любой n-битовой строке). Период, термин ${\displaystyle {\frac {1}{\sqrt {2^{n}}}}}$ может быть исключен из суммирования, потому что он не зависит от ${\displaystyle x}$ (т.е. это константа относительно ${\displaystyle x}$), и ${\displaystyle {\frac {1}{\sqrt {2^{n}}}}={\frac {1}{2^{\frac {n}{2}}}}}$.

Пример

Предположим (снова) ${\displaystyle n=2}$, то вход ${\displaystyle |0000\rangle }$ и преобразование Адамара ${\displaystyle H^{\otimes 2}}$ является

${\displaystyle H^{\otimes 2}={\frac {1}{\sqrt {2}}}{\begin{bmatrix}1&1\\1&-1\end{bmatrix}}\otimes {\frac {1}{\sqrt {2}}}{\begin{bmatrix}1&1\\1&-1\end{bmatrix}}={\frac {1}{\sqrt {2}}}{\begin{bmatrix}{\frac {1}{\sqrt {2}}}{\begin{bmatrix}1&1\\1&-1\end{bmatrix}}&{\frac {1}{\sqrt {2}}}{\begin{bmatrix}1&1\\1&-1\end{bmatrix}}\\{\frac {1}{\sqrt {2}}}{\begin{bmatrix}1&1\\1&-1\end{bmatrix}}&-\left({\frac {1}{\sqrt {2}}}{\begin{bmatrix}1&1\\1&-1\end{bmatrix}}\right)\end{bmatrix}}={\frac {1}{2}}{\begin{bmatrix}1&1&1&1\\1&-1&1&-1\\1&1&-1&-1\\1&-1&-1&1\end{bmatrix}}}$

Если мы сейчас применим ${\displaystyle H^{\otimes 2}}$ к первому ${\displaystyle |00\rangle }$, т.е. в состояние

${\displaystyle |00\rangle ={\begin{bmatrix}1\\0\\0\\0\end{bmatrix}}}$

мы получаем

${\displaystyle {\begin{aligned}H^{\otimes 2}|00\rangle &={\frac {1}{2}}{\begin{bmatrix}1&1&1&1\\1&-1&1&-1\\1&1&-1&-1\\1&-1&-1&1\end{bmatrix}}{\begin{bmatrix}1\\0\\0\\0\end{bmatrix}}={\frac {1}{2}}{\begin{bmatrix}1\\1\\1\\1\end{bmatrix}}\\[6pt]&={\frac {1}{2}}\left({\begin{bmatrix}1\\0\\0\\0\end{bmatrix}}+{\begin{bmatrix}0\\1\\0\\0\end{bmatrix}}+{\begin{bmatrix}0\\0\\1\\0\end{bmatrix}}+{\begin{bmatrix}0\\0\\0\\1\end{bmatrix}}\right)={\frac {1}{2}}\left(|00\rangle +|01\rangle +|10\rangle +|11\rangle \right)={\frac {1}{2^{2/2}}}\sum _{x\in \{0,1\}^{2}}\left|x\right\rangle \end{aligned}}}$

Чтобы получить окончательное составное квантовое состояние, мы можем теперь тензорное произведение ${\displaystyle H^{\otimes 2}|00\rangle }$ с ${\displaystyle |00\rangle }$, то есть

${\displaystyle {\begin{aligned}\left(H^{\otimes 2}|00\rangle \right)\otimes |00\rangle &=\left({\frac {1}{2}}\sum _{x\in \{0,1\}^{2}}\left|x\right\rangle \right)\otimes |00\rangle ={\frac {1}{2}}\left(|00\rangle +|01\rangle +|10\rangle +|11\rangle \right)\otimes |00\rangle \\[6pt]&={\frac {1}{2}}\left(|00\rangle \otimes |00\rangle +|01\rangle \otimes |00\rangle +|10\rangle \otimes |00\rangle +|11\rangle \otimes |00\rangle \right)={\frac {1}{2}}\sum _{x\in \{0,1\}^{2}}\left(\left|x\right\rangle \otimes |00\rangle \right).\end{aligned}}}$

Oracle

Затем мы вызываем оракул или черный ящик (${\displaystyle U_{f}}$ на картинке выше) для вычисления функции ${\displaystyle f}$ на преобразованном входе ${\displaystyle |\Psi \rangle ={\frac {1}{2^{n/2}}}\sum _{x\in \{0,1\}^{n}}\left(\left|x\right\rangle \otimes \left|0^{n}\right\rangle \right)}$, чтобы получить состояние

${\displaystyle |\Psi \rangle '={\frac {1}{2^{n/2}}}\sum _{x\in \{0,1\}^{n}}\left(\left|x\right\rangle \otimes \left|f(x)\right\rangle \right)}$

Второе преобразование Адамара

Затем мы применяем преобразование Адамара ${\displaystyle H^{\otimes n}}$ к состояниям первого ${\displaystyle n}$ кубиты состояния ${\displaystyle |\Psi \rangle '}$, чтобы получить

${\displaystyle {\begin{aligned}|\Psi \rangle ''&={\frac {1}{2^{n/2}}}\sum _{x\in \{0,1\}^{n}}\left(\left(H^{\otimes n}\left|x\right\rangle \right)\otimes \left|f(x)\right\rangle \right)\\[4pt]&={\frac {1}{2^{n/2}}}\sum _{x\in \{0,1\}^{n}}\left(\left({\frac {1}{2^{n/2}}}\sum _{y\in \{0,1\}^{n}}(-1)^{x\cdot y}\left|y\right\rangle \right)\otimes \left|f(x)\right\rangle \right)={\frac {1}{2^{n}}}\sum _{x\in \{0,1\}^{n}}\left(\sum _{y\in \{0,1\}^{n}}\left((-1)^{x\cdot y}\left|y\right\rangle \otimes \left|f(x)\right\rangle \right)\right)\end{aligned}}}$

куда ${\displaystyle (-1)^{x\cdot y}}$ может быть ${\displaystyle -1}$ или же ${\displaystyle 1}$, в зависимости от ${\displaystyle x\cdot y=x_{1}y_{1}+\dots +x_{n}y_{n}}$, куда ${\displaystyle x_{i},y_{i}\in \{0,1\}}$, за ${\displaystyle i=1,\dots ,n}$. Так, например, если ${\displaystyle x=101}$ и ${\displaystyle y=111}$, тогда ${\displaystyle x\cdot y=1*1+0*1+1*1=2}$, которое является четным числом. Таким образом, в этом случае ${\displaystyle (-1)^{x\cdot y}=(-1)^{1*1+0*1+1*1}=(-1)^{2}=1}$, и ${\displaystyle {x\cdot y}}$ всегда неотрицательное число.

Интуицию, лежащую в основе применяемого здесь обратного преобразования Адамара, можно найти на Конспект лекций CMU

А теперь перепишем

${\displaystyle |\Psi \rangle ''={\frac {1}{2^{n}}}\sum _{x\in \{0,1\}^{n}}\left(\sum _{y\in \{0,1\}^{n}}\left((-1)^{x\cdot y}\left|y\right\rangle \otimes \left|f(x)\right\rangle \right)\right)}$

следующее

${\displaystyle |\Psi \rangle ''=\sum _{y\in \{0,1\}^{n}}\left(\left|y\right\rangle \otimes \left({\frac {1}{2^{n}}}\sum _{x\in \{0,1\}^{n}}\left((-1)^{x\cdot y}\left|f(x)\right\rangle \right)\right)\right)}$

Эта манипуляция будет удобна для понимания объяснений в следующих разделах. Порядок суммирования изменен на обратный.

Измерение

После выполнения всех ранее описанных операций в конце схемы измерение выполняется.

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

• ${\displaystyle x\oplus y=0^{n}}$ или же
• ${\displaystyle x\oplus y=s}$, куда ${\displaystyle s\neq 0^{n}}$.

Первый случай

Давайте сначала проанализируем (частный) случай ${\displaystyle x\oplus y=0^{n}}$, что обозначает ${\displaystyle f}$ является (по требованию) один к одному функции (как описано выше в «описании проблемы»).

Помните, что квантовое состояние до измерения

${\displaystyle \sum _{y\in \{0,1\}^{n}}\left|y\right\rangle \otimes \left({\frac {1}{2^{n}}}\sum _{x\in \{0,1\}^{n}}\left((-1)^{x\cdot y}\left|f(x)\right\rangle \right)\right)}$

Теперь вероятность того, что результат измерения в каждой строке ${\displaystyle y\in \{0,1\}^{n}}$ является

${\displaystyle p_{y}={{\Bigg \|}{\frac {1}{2^{n}}}\sum _{x\in \{0,1\}^{n}}\left((-1)^{x\cdot y}\left|f(x)\right\rangle \right){\Bigg \|}}^{2}={\frac {1}{2^{n}}}}$

Это следует из

${\displaystyle {{\Bigg \|}{\frac {1}{2^{n}}}\sum _{x\in \{0,1\}^{n}}\left((-1)^{x\cdot y}\left|f(x)\right\rangle \right){\Bigg \|}}^{2}={{\Bigg \|}{\frac {1}{2^{n}}}\sum _{x\in \{0,1\}^{n}}\left((-1)^{x\cdot y}\left|x\right\rangle \right){\Bigg \|}}^{2}}$

потому что два вектора различаются только порядком их записей, учитывая, что ${\displaystyle f}$ является один к одному.

Значение правой части, то есть

${\displaystyle {{\Bigg \|}{\frac {1}{2^{n}}}\sum _{x\in \{0,1\}^{n}}\left((-1)^{x\cdot y}\left|x\right\rangle \right){\Bigg \|}}^{2}}$

легче увидеть ${\displaystyle {\frac {1}{2^{n}}}}$.

Таким образом, когда ${\displaystyle x\oplus y=0^{n}}$, результат - просто равномерно распределены ${\displaystyle n}$-битовая строка.

Второй случай

А теперь разберем случай ${\displaystyle x\oplus y=s}$, куда ${\displaystyle s\neq 0^{n}}$. В этом случае, ${\displaystyle f}$ является функцией два к одному, то есть есть два входа, которые сопоставляются с одним и тем же выходом ${\displaystyle f}$.

Анализ, выполненный в первом случае, все еще действителен для этого второго случая, то есть вероятность измерить любую заданную строку ${\displaystyle y\in \{0,1\}^{n}}$ все еще можно представить как

${\displaystyle p_{y}={{\Bigg \|}{\frac {1}{2^{n}}}\sum _{x\in \{0,1\}^{n}}\left((-1)^{x\cdot y}\left|f(x)\right\rangle \right){\Bigg \|}}^{2}}$

Однако во втором случае нам все еще нужно выяснить, что это за значение ${\displaystyle p_{y}}$ является. Давайте разберемся, почему, в следующих пояснениях.

Позволять ${\displaystyle A=f(\{0,1\}^{n})}$, образ ${\displaystyle f}$. Позволять ${\displaystyle z\in A}$ (т.е. ${\displaystyle z}$ какой-то вывод функции ${\displaystyle f}$), то для каждого ${\displaystyle x_{1}\in \{0,1\}^{n}}$, есть один (и только один) ${\displaystyle x_{2}\in \{0,1\}^{n}}$, так что ${\displaystyle f(x_{1})=f(x_{2})=z}$; кроме того, у нас также есть ${\displaystyle x_{1}\oplus x_{2}=s}$, что эквивалентно ${\displaystyle x_{2}=s\oplus x_{1}}$ (см. раздел «Описание проблемы» выше для обзора этой концепции).

Следовательно, мы имеем

${\displaystyle p_{y}={{\Bigg \|}{\frac {1}{2^{n}}}\sum _{x\in \{0,1\}^{n}}\left((-1)^{x\cdot y}\left|f(x)\right\rangle \right){\Bigg \|}}^{2}={{\Bigg \|}{\frac {1}{2^{n}}}\sum _{z\in A}\left(((-1)^{x_{1}\cdot y}+(-1)^{x_{2}\cdot y})\left|z\right\rangle \right){\Bigg \|}}^{2}}$

При условии ${\displaystyle x_{2}=s\oplus x_{1}}$, то можно переписать коэффициент ${\displaystyle (-1)^{x_{1}\cdot y}+(-1)^{x_{2}\cdot y}}$ следующее

${\displaystyle (-1)^{x_{1}\cdot y}+(-1)^{x_{2}\cdot y}=(-1)^{x_{1}\cdot y}+(-1)^{(x_{1}\oplus s)\cdot y}}$

При условии ${\displaystyle (x_{1}\oplus s)\cdot y=(x_{1}\cdot y)\oplus (s\cdot y)}$, то мы можем записать выражение выше как

${\displaystyle (-1)^{x_{1}\cdot y}(1+(-1)^{y\cdot s})}$

Так, ${\displaystyle p_{y}}$ в дальнейшем можно записать как

${\displaystyle p_{y}={{\Bigg \|}{\frac {1}{2^{n}}}\sum _{z\in A}\left((-1)^{x_{1}\cdot y}(1+(-1)^{y\cdot s})\left|z\right\rangle \right){\Bigg \|}}^{2}}$

Нечетное число

Сейчас если ${\displaystyle y\cdot s=y_{1}s_{1}+\dots +y_{n}s_{n}}$ нечетное число, то ${\displaystyle (-1)^{y\cdot s}=-1}$. В таком случае,

${\displaystyle (-1)^{x_{1}\cdot y}(1+(-1)^{y\cdot s})=(-1)^{x_{1}\cdot y}(1-1)=0}$

Следовательно, мы имеем

${\displaystyle p_{y}={{\Bigg \|}{\frac {1}{2^{n}}}\sum _{z\in A}\left((-1)^{x_{1}\cdot y}(1+(-1)^{y\cdot s})\left|z\right\rangle \right){\Bigg \|}}^{2}=0}$

При условии ${\displaystyle p_{y}=0}$, то у нас никогда не бывает этого дела, то есть нет строки ${\displaystyle y\in \{0,1\}^{n}}$ в этом случае видна (после измерения).

(Это тот случай, когда мы имеем деструктивное вмешательство.)

Четное число

Если вместо этого ${\displaystyle y\cdot s}$ - четное число (например, ноль), то ${\displaystyle (-1)^{y\cdot s}=1}$. В таком случае,

${\displaystyle (-1)^{x_{1}\cdot y}(1+(-1)^{y\cdot s})=(-1)^{x_{1}\cdot y}2}$

Итак, у нас есть

${\displaystyle p_{y}={{\Bigg \|}{\frac {1}{2^{n}}}\sum _{z\in A}\left((-1)^{x_{1}\cdot y}(2)\left|z\right\rangle \right){\Bigg \|}}^{2}={{\Bigg \|}{\frac {2}{2^{n}}}\sum _{z\in A}\left((-1)^{x_{1}\cdot y}\left|z\right\rangle \right){\Bigg \|}}^{2}={{\Bigg \|}{\frac {1}{2^{n-1}}}\sum _{z\in A}\left((-1)^{x_{1}\cdot y}\left|z\right\rangle \right){\Bigg \|}}^{2}}$

В случае конструктивное вмешательство,

${\displaystyle {\frac {2}{2^{n}}}=2*2^{-n}=2^{1}*2^{-n}=2^{-n+1}=2^{-(n-1)}={\frac {1}{2^{n-1}}}}$Итак, в общем, для этого второго случая мы имеем следующие вероятности

${\displaystyle p_{y}={{\Bigg \|}{\frac {1}{2^{n}}}\sum _{x\in \{0,1\}^{n}}\left((-1)^{x\cdot y}\left|f(x)\right\rangle \right){\Bigg \|}}^{2}={\begin{cases}{\frac {1}{2^{n-1}}}&\quad {\text{if }}y\cdot s{\text{ is even}}\\0&\quad {\text{if }}y\cdot s{\text{ is odd}}\\\end{cases}}}$

Классическая постобработка

Когда мы запускаем схему (операции), описанную выше, возможны два случая:

• в (частном) случае, когда ${\displaystyle x\oplus y=0^{n}}$, результаты измерения в каждой строке ${\displaystyle y\in \{0,1\}^{n}}$ с вероятностью ${\displaystyle p_{y}={\frac {1}{2^{n}}}}$

• в случае ${\displaystyle x\oplus y=s}$ (куда ${\displaystyle s\neq 0^{n}}$) вероятность получить каждую строку ${\displaystyle y\in \{0,1\}^{n}}$ дан кем-то

${\displaystyle p_{y}={\begin{cases}{\frac {1}{2^{n-1}}}&\quad {\text{if }}y\cdot s{\text{ is even}}\\0&\quad {\text{if }}y\cdot s{\text{ is odd}}\\\end{cases}}}$

Таким образом, в обоих случаях результатом измерения является некоторая строка ${\displaystyle y\in \{0,1\}^{n}}$ это удовлетворяет ${\displaystyle s\cdot y=0}$, а распределение униформа по всем строкам, которые удовлетворяют этому ограничению.

Достаточно ли этой информации, чтобы определить ${\displaystyle s}$? Ответ - «да», при условии, что процесс (см. Выше) повторяется несколько раз (и допускается небольшая вероятность отказа). В частности, если вышеуказанный процесс запущен ${\displaystyle n-1}$ раз мы получаем ${\displaystyle n-1}$ струны ${\displaystyle y_{1},y_{2},\dots ,y_{n-1}\in \{0,1\}^{n}}$, так что

${\displaystyle {\begin{cases}y_{1}\cdot s&=0\\y_{2}\cdot s&=0\\&\vdots \\y_{n-1}\cdot s&=0\end{cases}}}$

Это система ${\displaystyle n-1}$ линейные уравнения в ${\displaystyle n}$ неизвестные (т. е. части ${\displaystyle s}$), а цель - решить ее, чтобы получить ${\displaystyle s}$. Обратите внимание, что каждый из ${\displaystyle y_{1},y_{2},\dots ,y_{n-1}\in \{0,1\}^{n}}$ то, что мы получаем после каждого измерения (для каждого «раунда» процесса), конечно же, является результатом измерения, поэтому он известен (в конце каждого «раунда»).

Мы получаем только единственное ненулевое решение ${\displaystyle s}$ если нам "повезет" и ${\displaystyle y_{1},y_{2},\dots ,y_{n-1}\in \{0,1\}^{n}}$ линейно независимы. Вероятность того, что ${\displaystyle y_{1},y_{2},\dots ,y_{n-1}}$ линейно независимы, не менее

${\displaystyle \prod _{k=1}^{\infty }\left(1-{\frac {1}{2^{k}}}\right)=0.288788\dots >{\frac {1}{4}}}$

Если у нас есть линейная независимость, мы можем решить систему, чтобы получить возможное решение ${\displaystyle s'\neq 0^{n}}$ и проверить это ${\displaystyle f(0^{n})=f(s')}$. Если ${\displaystyle f(0^{n})=f(s')}$, мы знаем это ${\displaystyle s=s'}$, и проблема решена. Если ${\displaystyle f(0^{n})\neq f(s')}$, это должно быть так ${\displaystyle s=0^{n}}$ (потому что, если бы это было не так, единственное ненулевое решение линейных уравнений было бы ${\displaystyle s}$). В любом случае, когда у нас есть линейная независимость, мы можем решить проблему.

Сложность

Алгоритм Саймона требует ${\displaystyle O(n)}$ запросов к черному ящику, тогда как для классического алгоритма потребуется как минимум ${\displaystyle \Omega (2^{n/2})}$ запросы. Также известно, что алгоритм Саймона оптимален в том смысле, что любой квантовый алгоритм для решения этой проблемы требует ${\displaystyle \Omega (n)}$ запросы.^[1][2]

Смотрите также

• Алгоритм Дойча – Йожи

Рекомендации

1. Koiran, P .; Несме, В .; Портье, Н. (2007), "Сложность квантового запроса абелевой проблемы скрытой подгруппы", Теоретическая информатика, 380 (1–2): 115–126, Дои:10.1016 / j.tcs.2007.02.057, получено 2011-06-06
2. Koiran, P .; Несме, В .; Портье, Н. (2005), "Квантовая нижняя оценка сложности запроса проблемы Саймона", Proc. ИКАЛП, 3580: 1287–1298, arXiv:Quant-ph / 0501060, Bibcode:2005квант.ч..1060K, получено 2011-06-06