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

DOI10.1007/S11128-015-0954-8zbMATH Open1317.81063arXiv1409.1416OpenAlexW2049869894MaRDI QIDQ2355587FDOQ2355587

Authors: Li Yang, Hongwei Li 

Publication date: 24 July 2015

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

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.

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

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

zbMATH Keywords

quantum algorithmBernstein-Vazirani algorithminfluence of Boolean function

Mathematics Subject Classification ID

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

Cites Work

• Probability Inequalities for Sums of Bounded Random Variables
• Quantum algorithms revisited
• Exponential Separation for One-Way Quantum Communication Complexity, with Applications to Cryptography
• A structure theorem for Boolean functions with small total influences
• Quantum complexity theory
• Title not available (Why is that?)
• Quantum algorithms for testing and learning Boolean functions

Cited In (24)

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

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)