A quantum algorithm for approximating the influences of Boolean functions and its applications

DOI10.1007/S11128-015-0954-8MaRDI QIDQ2355587zbMATH OpenOpenAlexFDO

Authors Li Yang, Hongwei Li

Publication date 24 July 2015

Published in Quantum Information Processing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1409.1416

zbMATH Keywords

Bernstein-Vazirani algorithminfluence of Boolean functionquantum algorithm

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12) Quantum computation (81P68)

Abstract: We investigate the influences of variables on a Boolean function $f$ based on the quantum Bernstein-Vazirani algorithm. A previous paper (Floess et al. in Math. Struct. in Comp. Science 23: 386, 2013) has proved that if a $n$-variable Boolean function $f(x_1,ldots,x_n)$ does not depend on an input variable $x_i$, using the Bernstein-Vazirani circuit to $f$ will always obtain an output $y$ that has a $0$ in the $i$th position. We generalize this result and show that after one time running the algorithm, the probability of getting a 1 in each position $i$ is equal to the dependence degree of $f$ on the variable $x_i$, i.e. the influence of $x_i$ on $f$. On this foundation, we give an approximation algorithm to evaluate the influence of any variable on a Boolean function. Next, as an application, we use it to study the Boolean functions with juntas, and construct probabilistic quantum algorithms to learn certain Boolean functions. Compared with the deterministic algorithms given by Floess et al., our probabilistic algorithms are faster.

Recommendations

• Quantum algorithms for testing and learning Boolean functions
• Quantum algorithms for testing Boolean functions
• Quantum algorithms for learning the algebraic normal form of quadratic Boolean functions
• An exact quantum algorithm for testing Boolean functions with one uncomplemented product of two variables
• Lower bounds of quantum black-box complexity and degree of approximating polynomials by influence of Boolean variables

Cites work

• A structure theorem for Boolean functions with small total influences
• Exponential Separation for One-Way Quantum Communication Complexity, with Applications to Cryptography
• scientific article; zbMATH DE number 5485570 (Why is no real title available?)
• Probability Inequalities for Sums of Bounded Random Variables
• Quantum algorithms for testing and learning Boolean functions
• Quantum algorithms revisited
• Quantum complexity theory

Cited in

(24)

• Efficient quantum algorithms of finding the roots of a polynomial function
• Creating very true quantum algorithms for quantum energy based computing
• Quantum cryptography based on the Deutsch-Jozsa algorithm
• Quantum cryptography, quantum communication, and quantum computer in a noisy environment
• A classical probability space exists for the measurement theory based on the truth values
• Necessary and sufficient condition for quantum computing
• Quantum communication based on an algorithm of determining a matrix
• Quantum algorithms on Walsh transform and Hamming distance for Boolean functions
• Quantum algorithm for determining a complex number string
• Quantum cryptographic property testing of multi-output Boolean functions
• Solving Bernstein and Vazirani's problem with the 2-bit permutation function
• Some theoretically organized algorithm for quantum computers
• Quantum algorithm for the root-finding problem
• Kochen-Specker theorem as a precondition for quantum computing
• Quantum algorithms for learning the algebraic normal form of quadratic Boolean functions
• scientific article; zbMATH DE number 2051219 (Why is no real title available?)
• Quantum algorithms for testing and learning Boolean functions
• Quantum algorithms for testing Boolean functions
• scientific article; zbMATH DE number 6297720 (Why is no real title available?)
• Distributed Bernstein-Vazirani algorithm
• Quantum Talagrand, KKL and Friedgut's theorems and the learnability of quantum Boolean functions
• Generalization of the Bernstein-Vazirani algorithm beyond qubit systems
• A quantum algorithm for testing and learning resiliency of a Boolean function
• New method of calculating a multiplication by using the generalized Bernstein-Vazirani algorithm

This page was built for publication: A quantum algorithm for approximating the influences of Boolean functions and its applications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2355587)