Encyclopedia

Hidden linear function problem

Search problem in quantum mechanics

Wikipedia contributorsAdapted for Fathomly · View authors

1 min read
Source updated August 11, 2026

The hidden linear function problem, is a search problem that generalizes the Bernstein-Vazirani problem. 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 biased threshold gates. 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 $QNC^{0}$ and $NC^{0}$ ( $QNC^{0}\nsubseteq NC^{0}$ ).

012D HLF problem statement

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

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

and

${\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 $z\in \mathbb {F} _{2}^{n}$ such that

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

Find $z$ .

022D HLF algorithm

With 3 registers; the first holding $A$ , the second containing $b$ and the third carrying an $n$ -qubit state, the circuit has controlled gates which implement $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, $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 $p(z)=\left|\langle z|H^{\otimes n}U_{q}H^{\otimes n}|0^{n}\rangle \right|^{2}$ , $p(z)>0$ iff $z$ is a solution.

Watch videos about Hidden linear function problemExplainers and documentaries on YouTube (opens in a new tab)

Sources and credits

This article is adapted from the Wikipedia article “Hidden linear function problem”, written by its contributors and licensed under CC BY-SA 4.0. Fathomly has changed the layout, removed citation markers, navigation and maintenance notices, and adjusted punctuation. This adapted version is shared under the same license. For references, see the original article.

Fathomly is not affiliated with or endorsed by the Wikimedia Foundation. Spotted a problem? Tell us.