2014/04/30 by Hong-Wei Li, Hongwei Li, Li Yang
Computer Science · Mathematics · Physics and Astronomy · #Algorithm #Boolean expression #Boolean function #Boolean network #Coding theory and cryptography #Computability, Logic, AI Algorithms #Computer science #Discrete mathematics #Function (biology) #Mathematics #Maximum satisfiability problem #Quantum #Quantum Computing Algorithms and Architecture #Quantum algorithm #Quantum mechanics #quant-ph
paper · pdf · doi:10.1017/s0960129516000013
16 pages
arxiv created 2015/01/20 · openalex publication_date 2016/02/09 · arxiv updated 2016/02/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
A quantum algorithm to determine approximations of linear structures of Boolean functions is presented and analysed. Similar results have already been published (see Simon's algorithm) but only for some promise versions of the problem, and it has been shown that no exponential quantum speedup can be obtained for the general (no promise) version of the problem. In this paper, no additional promise assumptions are made. The approach presented is based on the method used in the Bernstein–Vazirani algorithm to identify linear Boolean functions and on ideas from Simon's period finding algorithm. A proper combination of these two approaches results here to a polynomial-time approximation to the linear structures set. Specifically, we show how the accuracy of the approximation with high probability changes according to the running time of the algorithm. Moreover, we show that the time required for the linear structure determine problem with high success probability is related to so called relative differential uniformity δ f of a Boolean function f . Smaller differential uniformity is, shorter time is needed.