Problema de función lineal oculta

El problema de la función lineal oculta es un problema de búsqueda que generaliza el problema de Bernstein-Vazirani . ^{[ 1 ]} En el problema de Bernstein-Vazirani, la función oculta se especifica implícitamente en un oráculo ; mientras que en el problema de la función lineal oculta 2D (HLF 2D), la función oculta se especifica explícitamente mediante una matriz y un vector binario. El HLF 2D se puede resolver exactamente mediante un circuito cuántico de profundidad constante restringido a una cuadrícula bidimensional de cúbits que utiliza compuertas de entrada con fan-in acotadas, pero no se puede resolver mediante ningún circuito clásico de tamaño subexponencial y profundidad constante que utilice compuertas de umbral sesgadas de entrada con fan-in no acotadas . ^{[ 2 ] [ 3 ]} Mientras que el problema de Bernstein-Vazirani se diseñó para demostrar una separación de oráculos entre las clases de complejidad BQP y BPP , el HLF 2D se diseñó para demostrar una separación explícita entre las clases de circuitos.${\displaystyle QNC^{0}}$y${\displaystyle NC^{0}}$(${\displaystyle QNC^{0}\nsubseteteq NC^{0}}$). ^{[ 1 ]}

Dado${\displaystyle A\in \mathbb {F} _{2}^{n\times n}}$(una matriz binaria triangular superior de tamaño${\displaystyle n\times n}$) y${\displaystyle b\in \mathbb {F} _{2}^{n}}$(un vector binario de longitud${\displaystyle n}$),

definir una función${\displaystyle q:\mathbb {F} _{2}^{n}\to \mathbb {Z} _{4}}$:

${\displaystyle 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}},}$

y

${\displaystyle {\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 \}}.}$

Existe un${\displaystyle z\in \mathbb {F} _{2}^{n}}$de tal manera que

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

Encontrar${\displaystyle z}$. ^{[ 1 ]}

Con 3 registros; la primera posesión${\displaystyle A}$, el segundo contiene${\displaystyle b}$y el tercero portando un${\displaystyle n}$-estado de cúbito, el circuito tiene compuertas controladas que implementan ${\displaystyle U_{q}=\prod _{1<i<j<n}CZ_{ij}^{A_{ij}}\cdot \bigotimes _{j=1}^{n}S_{j}^{b_{j}}}$desde los dos primeros registros hasta el tercero.

Este problema puede resolverse mediante un circuito cuántico,${\displaystyle H^{\otimes n}U_{q}H^{\otimes n}\mid 0^{n}\rangle }$, donde H es la puerta Hadamard , S es la puerta S y CZ es la puerta CZ . Se resuelve mediante este circuito porque con${\displaystyle p(z)=\left|\langle z|H^{\otimes n}U_{q}H^{\otimes n}|0^{n}\rangle \right|^{2}}$,${\displaystyle p(z)>0}$si y solo si${\displaystyle z}$es una solución. ^{[ 1 ]}

• Implementación del problema de la función lineal oculta