Проблема Саймона

Не путать с задачами Саймона по математической физике.

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

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

Эта проблема приводит к разделению оракула между классами сложности BPP (сложность классического запроса с ограниченной ошибкой) и BQP (сложность квантового запроса с ограниченной ошибкой). Это то же самое разделение, которого достигает алгоритм Бернштейна-Вазирани , и оно отличается от разделения, обеспечиваемого алгоритмом Дойча-Йожсы , который разделяет P и EQP . В отличие от алгоритма Бернштейна-Вазирани, разделение алгоритма Саймона является экспоненциальным .

Поскольку эта проблема предполагает существование высокоструктурированного оракула «черного ящика» для достижения его ускорения, эта проблема не имеет практического значения. Однако без такого оракула невозможно легко доказать экспоненциальное ускорение, поскольку это доказывало бы, что P отличается от PSPACE .

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

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

$f(x)=f(y)$ тогда и только тогда, когда $x\oplus y\in \{0^{n},s\}$,

где $\oplus$ обозначает побитовое исключающее ИЛИ . Цель – выявить $s$ сделав как можно меньше запросов к $f(x)$ насколько это возможно. Обратите внимание, что

$a\oplus b=0^{n}$ тогда и только тогда, когда $a=b$

Более того, для некоторых $x$ и $s$ в $x\oplus y=s$, $y$ уникально (не равно $x$) тогда и только тогда, когда $s\neq 0^{n}$. Это означает, что $f$ два к одному, когда $s\neq 0^{n}$, и один к одному, когда $s=0^{n}$. Это также тот случай, когда $x\oplus y=s$ подразумевает $y=s\oplus x$, это означает, что $$f(x)=f(y)=f(x\oplus {s})$$который показывает, как $f$ является периодическим.

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

Пример

Следующая функция является примером функции, которая удовлетворяет требуемому свойству для $n=3$:

$x$	$f(x)$
000	101
001	010
010	000
011	110
100	000
101	110
110	101
111	010

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

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

$s=110$ также можно проверить с помощью входных строк 001 и 111, которые обе сопоставлены (посредством f) с одной и той же выходной строкой 010. Применение XOR к 001 и 111 дает 110, то есть $001\oplus 111=110=s$. Это дает то же решение $s=110$ как раньше.

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

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

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

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

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

Алгоритм в целом использует подпрограмму для выполнения следующих двух шагов:

1. Запустите квантовую подпрограмму ожидаемым $O(n)$ раз, чтобы получить список линейно независимых битовых строк $y_{1},...,y_{n-1}$.
2. Каждый $y_{k}$ удовлетворяет $y_{k}\cdot s=0$, поэтому мы можем решить полученную систему уравнений и получить $s$.

Квантовая подпрограмма

Квантовая схема (см. рисунок) — это реализация квантовой части алгоритма Саймона. Квантовая подпрограмма алгоритма использует преобразование Адамара. $$H^{\otimes n}|k\rangle ={\frac {1}{\sqrt {2^{n}}}}\sum _{j=0}^{2^{n}-1}(-1)^{k\cdot j}|j\rangle$$где $k\cdot j=k_{1}j_{1}\oplus \ldots \oplus k_{n}j_{n}$, где $\oplus$ обозначает XOR.

Во-первых, алгоритм начинается с двух регистров, инициализированных $|0\rangle ^{\otimes n}|0\rangle ^{\otimes n}$. Затем мы применяем преобразование Адамара к первому регистру, что дает состояние

${\frac {1}{\sqrt {2^{n}}}}\sum _{k=0}^{2^{n}-1}|k\rangle |0\rangle ^{\otimes n}.$

Запросить оракула $U_{f}$ чтобы получить состояние

${\frac {1}{\sqrt {2^{n}}}}\sum _{k=0}^{2^{n}-1}|k\rangle |f(k)\rangle$.

Примените еще одно преобразование Адамара к первому регистру. Это создаст состояние

${\frac {1}{\sqrt {2^{n}}}}\sum _{k=0}^{2^{n}-1}\left[{\frac {1}{\sqrt {2^{n}}}}\sum _{j=0}^{2^{n}-1}(-1)^{j\cdot k}|j\rangle \right]|f(k)\rangle =\sum _{j=0}^{2^{n}-1}|j\rangle \left[{\frac {1}{2^{n}}}\sum _{k=0}^{2^{n}-1}(-1)^{j\cdot k}|f(k)\rangle \right].$

Наконец, измеряем первый регистр (алгоритм работает и в том случае, если второй регистр измеряется раньше первого, но это необязательно). Вероятность измерения состояния $|j\rangle$ является $$\left|\left|{\frac {1}{2^{n}}}\sum _{k=0}^{2^{n}-1}(-1)^{j\cdot k}|f(k)\rangle \right|\right|^{2}$$Это связано с тем, что взятие величины этого вектора и возведение его в квадрат суммирует все вероятности всех возможных измерений второго регистра, которые должны иметь первый регистр как $|j\rangle$. Для нашего измерения есть два случая:

1. $s=0^{n}$ и $f$ является один в один.
2. $s\neq 0^{n}$ и $f$ это два к одному.

Для первого случая $$\left|\left|{\frac {1}{2^{n}}}\sum _{k=0}^{2^{n}-1}(-1)^{j\cdot k}|f(k)\rangle \right|\right|^{2}={\frac {1}{2^{n}}}$$поскольку в этом случае $f$ является взаимно однозначным, подразумевая, что диапазон $f$ является $\{0,1\}^{n}$, что означает, что суммирование ведется по каждому базисному вектору. Во втором случае обратите внимание, что существуют две строки: $x_{1}$ и $x_{2}$, такой, что $f(x_{1})=f(x_{2})=z$, где $z\in \mathrm {range} (f)$. Таким образом, $$\left|\left|{\frac {1}{2^{n}}}\sum _{k=0}^{2^{n}-1}(-1)^{j\cdot k}|f(k)\rangle \right|\right|^{2}=\left|\left|{\frac {1}{2^{n}}}\sum _{z\,\in \,\mathrm {range} (f)}((-1)^{j\cdot x_{1}}+(-1)^{j\cdot x_{2}})|z\rangle \right|\right|^{2}$$Кроме того, поскольку $x_{1}\oplus x_{2}=s$, $x_{2}=x_{1}\oplus s$, и так $${\begin{aligned}\left|\left|{\frac {1}{2^{n}}}\sum _{z\,\in \,\mathrm {range} (f)}((-1)^{j\cdot x_{1}}+(-1)^{j\cdot x_{2}})|z\rangle \right|\right|^{2}&=\left|\left|{\frac {1}{2^{n}}}\sum _{z\,\in \,\mathrm {range} (f)}((-1)^{j\cdot x_{1}}+(-1)^{j\cdot (x_{1}\oplus s)})|z\rangle \right|\right|^{2}\\&=\left|\left|{\frac {1}{2^{n}}}\sum _{z\,\in \,\mathrm {range} (f)}((-1)^{j\cdot x_{1}}+(-1)^{j\cdot x_{1}\oplus j\cdot s})|z\rangle \right|\right|^{2}\\&=\left|\left|{\frac {1}{2^{n}}}\sum _{z\,\in \,\mathrm {range} (f)}(-1)^{j\cdot x_{1}}(1+(-1)^{j\cdot s})|z\rangle \right|\right|^{2}\end{aligned}}$$Теперь это выражение легко вычислить. Напомним, что мы измеряем $j$. Когда $j\cdot s=1$, то это выражение будет иметь значение $0$, и когда $j\cdot s=0$, то это выражение будет $2^{-n+1}$.

Таким образом, как когда $s=0^{n}$ и когда $s\neq 0^{n}$, наши измерения $j$ удовлетворяет $j\cdot s=0$.

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

Мы запускаем квантовую часть алгоритма до тех пор, пока не получим линейно независимый список битовых строк. $y_{1},\ldots ,y_{n-1}$и каждый $y_{k}$ удовлетворяет $y_{k}\cdot s=0$. Таким образом, мы можем эффективно решить эту систему уравнений классическим способом и найти $s$.

Вероятность того, что $y_{1},y_{2},\dots ,y_{n-1}$ линейно независимы, по крайней мере $$\prod _{k=1}^{\infty }\left(1-{\frac {1}{2^{k}}}\right)=0.288788\dots$$Как только мы решим систему уравнений и получим решение $s'$, мы можем проверить, если $f(0^{n})=f(s')$. Если это правда, то мы знаем $s'=s$, с $f(0^{n})=f(0^{n}\oplus s)=f(s)$. Если это так, $f(0^{n})\neq f(s')$, то это означает, что $s=0^{n}$, и $f(0^{n})\neq f(s')$ с $f$ является один в один.

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

Явные примеры алгоритма Саймона для нескольких кубитов

Один кубит

Рассмотрим простейший пример алгоритма, где $n=1$. В этом случае входное состояние развивается через вентиль Адамара, и оракул приводит к состоянию (с точностью до перенормировки):

$|0\rangle |f(0)\rangle +|1\rangle |f(1)\rangle .$

Если $s=1$, то есть, $f(0)=f(1)$, то измерение второго регистра всегда дает результат $|f(0)\rangle$, и всегда приводит к схлопыванию первого регистра до состояния (вплоть до перенормировки):

$|0\rangle +|1\rangle .$

Таким образом, применение Адамара и измерение первого регистра всегда дают результат $|0\rangle$. С другой стороны, если $f$ является один к одному, то есть $s=0$, то измерение первого регистра после второго Адамара может привести как к $|0\rangle$ и $|1\rangle$, с равной вероятностью.

Мы выздоравливаем $s$ от результатов измерений, проверив, всегда ли мы измеряли $|0\rangle$, в этом случае $s=1$, или мы измерили оба $|0\rangle$ и $|1\rangle$ с равной вероятностью, и в этом случае мы заключаем, что $s=0$. Эта схема потерпит неудачу, если $s=0$ но мы, тем не менее, всегда находили результат $|0\rangle$, но вероятность этого события равна $2^{-N}$ с $N$ количество выполненных измерений, и, таким образом, его можно сделать экспоненциально малым за счет увеличения статистики.

Два кубита

Рассмотрим теперь случай с $n=2$. Начальная часть алгоритма приводит к состоянию (с точностью до перенормировки): $$|00\rangle |f(00)\rangle +|01\rangle |f(01)\rangle +|10\rangle |f(10)\rangle +|11\rangle |f(11)\rangle .$$Если $s=(00)$, значение $f$ инъективен, то нахождение $|f(x)\rangle$ во втором регистре всегда сжимает первый регистр до $|x\rangle$, для всех $x\in \{0,1\}^{2}$. Другими словами, применяя ворота Адамара и измеряя первые, регистрируются четыре результата. $00,01,10,11$ таким образом, обнаруживаются с равной вероятностью.

Предположим, с другой стороны $s\neq (00)$, например, $s=(01)$. Затем измеряем $|f(00)\rangle$ во втором регистре сворачивает первый регистр в состояние $|00\rangle +|10\rangle$. И вообще, измерение $|f(xy)\rangle$ дает $|x,y\rangle +|x,y\oplus 1\rangle =|x\rangle (|0\rangle +|1\rangle )$ в первом регистре. Таким образом, применение вентилей Адамара и измерение в первом регистре могут привести к результатам $00$ и $10$ с равными вероятностями.

Аналогичные рассуждения применимы и к другим случаям: если $s=(10)$ тогда возможные результаты $00$ и $01$, а если $s=(11)$ возможные результаты $00$ и $11$, совместимо с $j\cdot s=0$ правило обсуждается в общем случае.

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

Сложность

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

См. также

• Алгоритм Германа – Йожи