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

DOI10.1016/S0020-0190(00)00069-7zbMATH Open1339.68093arXivquant-ph/9904107OpenAlexW2024588775MaRDI QIDQ294804FDOQ294804

Authors: Yaoyun Shi 

Publication date: 16 June 2016

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

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• On the Power of Quantum Computation
• Rapid solution of problems by quantum computation
• On the degree of Boolean functions as real polynomials
• Sensitivity vs. block sensitivity of Boolean functions
• Pseudo-average block sensitivity equals average sensitivity
• On the Influence of Single Participant in Coin Flipping Schemes
• Title not available (Why is that?)
• Sensitivity vs. block sensitivity (an average-case study)

Cited In (16)

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

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)