Проблема скрытой линейной функции

Проблема скрытой линейной функции — это задача поиска , которая обобщает проблему Бернштейна–Вазирани . В задаче Бернштейна – Вазирани скрытая функция неявно указана в оракуле ; в то время как в двумерной задаче скрытой линейной функции (2D HLF) скрытая функция явно задается матрицей и двоичным вектором. постоянной глубины, 2D HLF может быть решена точно с помощью квантовой схемы ограниченной двумерной сеткой кубитов с использованием ограниченных веерных вентилей , но не может быть решена с помощью любой субэкспоненциальной классической схемы постоянной глубины с использованием неограниченного веерования. в вентилях И , ИЛИ и НЕ . В то время как проблема Бернштейна-Вазирани была разработана для доказательства разделения оракула между классами сложности BQP и BPP , 2D HLF была разработана для доказательства явного разделения между классами схем. $QNC^{0}$ и $NC^{0}$ ( $QNC^{0}\nsubseteq NC^{0}$).

Постановка задачи 2D HLF

Данный $A\in \mathbb {F} _{2}^{n\times n}$(верхнетреугольная двоичная матрица размера $n\times n$) и $b\in \mathbb {F} _{2}^{n}$ ( двоичный вектор длины $n$),

определить функцию $q:\mathbb {F} _{2}^{n}\to \mathbb {Z} _{4}$:

$q(x)=(2x^{T}Ax+b^{T}x){\bmod {4}}=\left(2\sum _{i,j}A_{i,j}x_{i}x_{j}+\sum _{i}b_{i}x_{i}\right){\bmod {4}},$

и

${\mathcal {L}}_{q}={\Big \{}x\in \mathbb {F} _{2}^{n}:q(x\oplus y)=(q(x)+q(y)){\bmod {4}}~~\forall y\in \mathbb {F} _{2}^{n}{\Big \}}.$

Существует $z\in \mathbb {F} _{2}^{n}$ такой, что

$q(x)=2z^{T}x~~\forall x\in {\mathcal {L}}_{q}.$

Находить $z$.

Алгоритм 2D HLF

С 3 регистрами; первый холдинг $A$, второй содержит $b$ а третий несет $n$-кубитное состояние, схема имеет управляемые вентили , которые реализуют $U_{q}=\prod _{1<i<j<n}CZ_{ij}^{A_{ij}}\cdot \bigotimes _{j=1}^{n}S_{j}^{b_{j}}$ из первых двух регистров в третий.

Эту проблему можно решить с помощью квантовой схемы, $H^{\otimes n}U_{q}H^{\otimes n}\mid 0^{n}\rangle$, где H — вентиль Адамара , S — вентиль S , а CZ — вентиль CZ . Это решается этой схемой, потому что с $p(z)=\left|\langle z|H^{\otimes n}U_{q}H^{\otimes n}|0^{n}\rangle \right|^{2}$, $p(z)>0$ если только $z$ это решение.

Внешние ссылки

• Реализация задачи о скрытой линейной функции