Hidden linear function problem

The hidden linear function problem, is a search problem that generalizes the Bernstein–Vazirani problem.^[1] In the Bernstein–Vazirani problem, the hidden function is implicitly specified in an oracle; while in the 2D hidden linear function problem (2D HLF), the hidden function is explicitly specified by a matrix and a binary vector. 2D HLF can be solved exactly by a constant-depth quantum circuit restricted to a 2-dimensional grid of qubits using bounded fan-in gates but can't be solved by any sub-exponential size, constant-depth classical circuit using unbounded fan-in AND, OR, and NOT gates.^[2] While Bernstein–Vazirani's problem was designed to prove an oracle separation between complexity classes BQP and BPP, 2D HLF was designed to prove an explicit separation between the circuit classes ${\displaystyle QNC^{0}}${\displaystyle QNC^{0}} and ${\displaystyle NC^{0}}${\displaystyle NC^{0}} (${\displaystyle QNC^{0}\nsubseteq NC^{0}}${\displaystyle QNC^{0}\nsubseteq NC^{0}}).^[1]

Given ${\displaystyle A\in \mathbb {F} _{2}^{n\times n}}${\displaystyle A\in \mathbb {F} _{2}^{n\times n}}(an upper- triangular binary matrix of size ${\displaystyle n\times n}${\displaystyle n\times n}) and ${\displaystyle b\in \mathbb {F} _{2}^{n}}${\displaystyle b\in \mathbb {F} _{2}^{n}} (a binary vector of length ${\displaystyle n}${\displaystyle n}),

define a function ${\displaystyle q:\mathbb {F} _{2}^{n}\to \mathbb {Z} _{4}}${\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}},}${\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}},}

and

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

There exists a ${\displaystyle z\in \mathbb {F} _{2}^{n}}${\displaystyle z\in \mathbb {F} _{2}^{n}} such that

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

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

With 3 registers; the first holding ${\displaystyle A}${\displaystyle A}, the second containing ${\displaystyle b}${\displaystyle b} and the third carrying an ${\displaystyle n}${\displaystyle n}-qubit state, the circuit has controlled gates which implement ${\displaystyle U_{q}=\prod _{1<i<j<n}CZ_{ij}^{A_{ij}}\cdot \bigotimes _{j=1}^{n}S_{j}^{b_{j}}}${\displaystyle U_{q}=\prod _{1<i<j<n}CZ_{ij}^{A_{ij}}\cdot \bigotimes _{j=1}^{n}S_{j}^{b_{j}}} from the first two registers to the third.

This problem can be solved by a quantum circuit, ${\displaystyle H^{\otimes n}U_{q}H^{\otimes n}\mid 0^{n}\rangle }${\displaystyle H^{\otimes n}U_{q}H^{\otimes n}\mid 0^{n}\rangle }, where H is the Hadamard gate, S is the S gate and CZ is CZ gate. It is solved by this circuit because with ${\displaystyle p(z)=\left|\langle z|H^{\otimes n}U_{q}H^{\otimes n}|0^{n}\rangle \right|^{2}}${\displaystyle p(z)=\left|\langle z|H^{\otimes n}U_{q}H^{\otimes n}|0^{n}\rangle \right|^{2}}, ${\displaystyle p(z)>0}${\displaystyle p(z)>0} iff ${\displaystyle z}${\displaystyle z} is a solution.^[1]

• Implementation of the hidden linear function problem

• Quantum algorithms
• Quantum complexity theory
• Computational complexity theory

• Articles with short description
• Short description matches Wikidata
• Use dmy dates from June 2020