Hidden linear function problem

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

define a function ${\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}},}$

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

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

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

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

With 3 registers; the first holding ${\displaystyle A}$, the second containing ${\displaystyle b}$ and the third carrying an ${\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}}}$ 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 }$, 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)>0}$ iff ${\displaystyle z}$ is a solution.[1]

• Implementation of the hidden linear function problem