Lower bounds of quantum black-box complexity and degree of approximating polynomials by influence of Boolean variables

DOI10.1016/S0020-0190(00)00069-7MaRDI QIDQ294804zbMATH OpenOpenAlexFDO

Authors Yaoyun Shi

Publication date 16 June 2016

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

Full work available at URL https://arxiv.org/abs/quant-ph/9904107

zbMATH Keywords

sensitivitycomputational complexityquantum computationBoolean functions

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Quantum algorithms and complexity in the theory of computing (68Q12)

Abstract: We prove that, to compute a Boolean function $f$ on $N$ variables with error probability $epsilon$, any quantum black-box algorithm has to query at least $$ times, where $h{o}_f$ is the average influence of variables in $f$, and $$ is the average sensitivity. It's interesting to contrast this result with the known lower bound of $Omega(sqrt{S}_f)$, where $S_f$ is the sensitivity of $f$. This lower bound is tight for some functions. We also show for any polynomial $ildef$ that approximates $f$ with error probability $epsilon$, $deg(ildef)ge1/4(1-frac3epsilon1+epsilon{)}^{2}h{o}_{f}N$. This bound can be better than previous known lower bound of $Omega(sqrtB{S}_f)$ for some functions. Our technique may be of intest itself: we apply Fourier analysis to functions mapping ${0,1}^N$ to unit vectors in a Hilbert space. From this viewpoint, the state of the quantum computer at step $t$ can be written as $su{m}_{sin{0,1}^N,|s|let}hat{phi}_s(-1{)}^{scdotx}$, which is handy for lower bound analysis.

Recommendations

• How low can approximate degree and quantum query complexity be for total Boolean functions?
• Quantum lower bounds by polynomials
• SOFSEM 2005: Theory and Practice of Computer Science
• A lower bound on the quantum query complexity of read-once functions
• The polynomial method strikes back: tight quantum query bounds via dual polynomials

Cites work

• scientific article; zbMATH DE number 1256737 (Why is no real title available?)
• scientific article; zbMATH DE number 1406121 (Why is no real title available?)
• On the Influence of Single Participant in Coin Flipping Schemes
• On the Power of Quantum Computation
• On the degree of Boolean functions as real polynomials
• Pseudo-average block sensitivity equals average sensitivity
• Rapid solution of problems by quantum computation
• Sensitivity vs. block sensitivity (an average-case study)
• Sensitivity vs. block sensitivity of Boolean functions

Cited in

(16)

• The influence lower bound via query elimination
• The Gaussian surface area and noise sensitivity of degree-\(d\) polynomial threshold functions
• Complexity of quantum circuits via sensitivity, magic, and coherence
• Quantum lower bounds by quantum arguments
• scientific article; zbMATH DE number 5899233 (Why is no real title available?)
• A quantum algorithm for approximating the influences of Boolean functions and its applications
• Entropy lower bounds for quantum decision tree complexity
• Unbounded-error quantum query complexity
• Quantum lower bounds by polynomials
• Improved bounds on quantum learning algorithms
• Quantum Talagrand, KKL and Friedgut's theorems and the learnability of quantum Boolean functions
• On the average sensitivity of the weighted sum function
• Formula lower bounds via the quantum method
• How low can approximate degree and quantum query complexity be for total Boolean functions?
• Complexity measures and decision tree complexity: a survey.
• The simplified weighted sum function and its average sensitivity

This page was built for publication: Lower bounds of quantum black-box complexity and degree of approximating polynomials by influence of Boolean variables

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