HHL Algorithm for Tensor-Decomposable Matrices

Abstract

We use the HHL algorithm to retrieve a quantum state holding the algebraic normal form (ANF) of a Boolean function. Unlike the standard HHL applications, we do not describe the cipher as an exponentially big system of equations. Rather, we perform a set of small matrix inversions which correspond to the Boolean Möbius transform. This creates a superposition holding information about the ANF in the form |𝒜𝑓⟩=1𝐶∑2𝑛−1𝐼=0𝑐𝐼|𝐼⟩, where 𝑐𝐼 is the coefficient of the ANF and C is a scaling factor. The procedure has a time complexity of 𝒪̃ (𝑛) for a Boolean function with n-bit input. We also propose two approaches by which some information about the ANF can be extracted from such a state. Next, we use a similar approach, the Dual Boolean Möbius transform, to compute the preimage under the algebraic transition matrix. We show that such a matrix is well-suited for the HHL algorithm when the attacker gets oracle access in the Q2 setting to the Boolean function.