Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1404.0611 · Mathematical Structures in Computer Science

A quantum algorithm to approximate the linear structures of Boolean functions

Hongwei Li, Li Yang

Published Feb 9, 2016• 23 citations
arXivHTMLPDF

Abstract

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δfof a Boolean functionf. Smaller differential uniformity is, shorter time is needed.

DOI
10.1017/s0960129516000013

Related papers

A Fast Quantum Algorithm for the Affine Boolean Function Identification

Ahmed Younes

Bernstein-Vazirani algorithm (the one-query algorithm) can identify a completely specified linear Boolean function using a single query to the oracle with certainty. The first aim of the paper is to show that if the provided Boolean function is affine, then one more query to the oracle (the two-query algorithm) is required to identify the affinity of the function with certainty. The second aim of the paper is to show that if the provided Boolean function is incompletely defined, then the one-query and the two-query algorithms can be used as bounded-error quantum polynomial algorithms to identify certain classes of incompletely defined linear and affine Boolean functions respectively with probability of success at least $2/3$.

arXiv:1407.6402•Jul 23, 2014•1 citation

Quantum algorithms for testing Boolean functions

Dominik Floess, Erika Andersson, Mark S. Hillery

We discuss quantum algorithms, based on the Bernstein-Vazirani algorithm, for finding which variables a Boolean function depends on. There are 2^n possible linear Boolean functions of n variables; given a linear Boolean function, the Bernstein-Vazirani quantum algorithm can deterministically identify which one of these Boolean functions we are given using just one single function query. The same quantum algorithm can also be used to learn which input variables other types of Boolean functions depend on, with a success probability that depends on the form of the Boolean function that is tested, but does not depend on the total number of input variables. We also outline a procedure to futher amplify the success probability, based on another quantum algorithm, the Grover search.

arXiv:1006.1423•Electronic Proceedings in Theoretical Computer Science•Jun 9, 2010•15 citations

Quantum algorithms for highly non-linear Boolean functions

Martin Rötteler

Attempts to separate the power of classical and quantum models of computation have a long history. The ultimate goal are exponential separations for computational (promise) problems, however, these do not come a dime a dozen: while there were some early successes in the form of hidden subgroup problems for abelian groups–which generalizes Shor’s factoring algorithm perhaps most faithfully–only for a handful of non-abelian groups efficient quantum algorithms were found. Recently, problems have gotten increased attention that seek to identify hidden sub-structures of other combinatorial and algebraic objects besides groups, notably the quantum algorithms by Childs, Schulman, and Vazirani for shifted subset problems for spheres over a finite field. In this paper we provide new examples for exponential separations by considering hidden shift problems that are defined for several classes of highly non-linear Boolean functions. These so-called bent functions arise in cryptography, where their property of having perfectly flat Fourier spectra on the Boolean hypercube gives them resilience against certain types of attack. We present quantum algorithms that solve the hidden shift problems for several well-known classes of bent functions in polynomial time with a constant number of queries, while the classical query complexity is shown to be exponential. Our approach uses a technique that exploits the duality between bent functions and their Fourier transforms. We also give a quantum algorithm that solves the hidden shift problem for quadratic forms that might be of independent interest. This algorithm can also be used to find approximating polynomials and shifts for functions with large Gowers U3 norm. 1 1

•Jan 1, 2008•24 citations

Quantum algorithms for testing and learning Boolean functions

Dominik Floess, Erika Andersson, Mark S. Hillery

We discuss quantum algorithms based on the Bernstein–Vazirani algorithm for finding which input variables a Boolean function depends on. There are 2 n possible linear Boolean functions of n input variables; given a linear Boolean function, the Bernstein–Vazirani quantum algorithm can deterministically identify which one of these Boolean functions we are given using just one single function query. We show how the same quantum algorithm can also be used to learn which input variables any other type of Boolean function} depends on. The success probability of learning that the function depends on a particular input variable depends on} the form of the Boolean function that is tested, but does not depend on the total number of input variables. We also outline a procedure based on another quantum algorithm, the Grover search, to amplify further the success probability. Finally, we discuss quantum algorithms for learning the exact form of certain quadratic and cubic Boolean functions.

Mathematical Structures in Computer Science•Feb 28, 2013•8 citations

Investigating the linear structure of Boolean functions based on Simon's period-finding quantum algorithm

Li Yang, Hongwei Li

It is believed that there is no efficient classical algorithm to determine the linear structure of Boolean function. We investigate an extension of Simon's period-finding quantum algorithm, and propose an efficient quantum algorithm to determine the linear structure of Boolean function.

arXiv:1306.2008•Jun 9, 2013•2 citations

Quantum Query Algorithms

Walid E. Gomaa

This presentation gives a comprehensive overview of quantum query algorithms, beginning with an introduction to the query model of computation where input is accessed via an oracle function. It then details several foundational quantum algorithms that demonstrate a quantum advantage over classical approaches: Deutsch's problem is solved with a single query using phase kickback to determine if a function is constant or balanced; the Deutsch-Jozsa algorithm extends this to n-bit inputs, efficiently distinguishing constant from balanced functions with one query versus an exponential need classically; the Bernstein-Vazirani algorithm identifies a hidden string with one query, outperforming classical linear requirements; and Simon's algorithm, which finds a hidden period in a two-to-one function with a linear number of queries, showcases an exponential speedup over the best classical probabilistic algorithms.

•Nov 19, 2025•0 citations
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δfof a Boolean functionf. Smaller differential uniformity is, shorter time is needed.
Bernstein-Vazirani algorithm (the one-query algorithm) can identify a completely specified linear Boolean function using a single query to the oracle with certainty. The first aim of the paper is to show that if the provided Boolean function is affine, then one more query to the oracle (the two-query algorithm) is required to identify the affinity of the function with certainty. The second aim of the paper is to show that if the provided Boolean function is incompletely defined, then the one-query and the two-query algorithms can be used as bounded-error quantum polynomial algorithms to identify certain classes of incompletely defined linear and affine Boolean functions respectively with probability of success at least 2/32/32/3.
We discuss quantum algorithms, based on the Bernstein-Vazirani algorithm, for finding which variables a Boolean function depends on. There are 2^n possible linear Boolean functions of n variables; given a linear Boolean function, the Bernstein-Vazirani quantum algorithm can deterministically identify which one of these Boolean functions we are given using just one single function query. The same quantum algorithm can also be used to learn which input variables other types of Boolean functions depend on, with a success probability that depends on the form of the Boolean function that is tested, but does not depend on the total number of input variables. We also outline a procedure to futher amplify the success probability, based on another quantum algorithm, the Grover search.
Attempts to separate the power of classical and quantum models of computation have a long history. The ultimate goal are exponential separations for computational (promise) problems, however, these do not come a dime a dozen: while there were some early successes in the form of hidden subgroup problems for abelian groups–which generalizes Shor’s factoring algorithm perhaps most faithfully–only for a handful of non-abelian groups efficient quantum algorithms were found. Recently, problems have gotten increased attention that seek to identify hidden sub-structures of other combinatorial and algebraic objects besides groups, notably the quantum algorithms by Childs, Schulman, and Vazirani for shifted subset problems for spheres over a finite field. In this paper we provide new examples for exponential separations by considering hidden shift problems that are defined for several classes of highly non-linear Boolean functions. These so-called bent functions arise in cryptography, where their property of having perfectly flat Fourier spectra on the Boolean hypercube gives them resilience against certain types of attack. We present quantum algorithms that solve the hidden shift problems for several well-known classes of bent functions in polynomial time with a constant number of queries, while the classical query complexity is shown to be exponential. Our approach uses a technique that exploits the duality between bent functions and their Fourier transforms. We also give a quantum algorithm that solves the hidden shift problem for quadratic forms that might be of independent interest. This algorithm can also be used to find approximating polynomials and shifts for functions with large Gowers U3 norm. 1 1
We discuss quantum algorithms based on the Bernstein–Vazirani algorithm for finding which input variables a Boolean function depends on. There are 2 n possible linear Boolean functions of n input variables; given a linear Boolean function, the Bernstein–Vazirani quantum algorithm can deterministically identify which one of these Boolean functions we are given using just one single function query. We show how the same quantum algorithm can also be used to learn which input variables any other type of Boolean function} depends on. The success probability of learning that the function depends on a particular input variable depends on} the form of the Boolean function that is tested, but does not depend on the total number of input variables. We also outline a procedure based on another quantum algorithm, the Grover search, to amplify further the success probability. Finally, we discuss quantum algorithms for learning the exact form of certain quadratic and cubic Boolean functions.
This presentation gives a comprehensive overview of quantum query algorithms, beginning with an introduction to the query model of computation where input is accessed via an oracle function. It then details several foundational quantum algorithms that demonstrate a quantum advantage over classical approaches: Deutsch's problem is solved with a single query using phase kickback to determine if a function is constant or balanced; the Deutsch-Jozsa algorithm extends this to n-bit inputs, efficiently distinguishing constant from balanced functions with one query versus an exponential need classically; the Bernstein-Vazirani algorithm identifies a hidden string with one query, outperforming classical linear requirements; and Simon's algorithm, which finds a hidden period in a two-to-one function with a linear number of queries, showcases an exponential speedup over the best classical probabilistic algorithms.