Polynomial-time quantum algorithms for finding the linear structures of Boolean function
In this paper, we present quantum algorithms to solve the linear structures of Boolean functions. Suppose Boolean function \(f\): \(\{0, 1\}^{n}\rightarrow \{0, 1\}\) is given as a black box. There exists an unknown n-bit string \(\alpha \) such that \(f(x)=f(x\oplus \alpha )\). We do not know the n-bit string \(\alpha \), excepting the Hamming weight \(W(\alpha )=m, 1\le m\le n\). Find the string \(\alpha \). In case \(W(\alpha )=1\), we present an efficient quantum algorithm to solve this linear construction for the general \(n\). In case \(W(\alpha )>1\), we present an efficient quantum algorithm to solve it for most cases. So, we show that the problem can be solved nearly in quantum polynomial times \(O(n^{2})\). From this view, the quantum algorithm is more efficient than any classical algorithm.
quantum algorithm linear structure boolean function quantum decoder