Lower bounds of quantum black-box complexity and degree of approximating polynomials by influence of Boolean variables
From MaRDI portal
Publication:294804
DOI10.1016/S0020-0190(00)00069-7zbMath1339.68093arXivquant-ph/9904107OpenAlexW2024588775MaRDI QIDQ294804
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
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Quantum algorithms and complexity in the theory of computing (68Q12)
Related Items (max. 100)
On the average sensitivity of the weighted sum function ⋮ Unbounded-error quantum query complexity ⋮ The Gaussian surface area and noise sensitivity of degree-\(d\) polynomial threshold functions ⋮ Quantum lower bounds by quantum arguments ⋮ Improved bounds on quantum learning algorithms ⋮ The simplified weighted sum function and its average sensitivity ⋮ Entropy lower bounds for quantum decision tree complexity ⋮ Complexity measures and decision tree complexity: a survey.
Cites Work
- Pseudo-average block sensitivity equals average sensitivity
- Sensitivity vs. block sensitivity (an average-case study)
- On the degree of Boolean functions as real polynomials
- Sensitivity vs. block sensitivity of Boolean functions
- On the Influence of Single Participant in Coin Flipping Schemes
- Rapid solution of problems by quantum computation
- On the Power of Quantum Computation
- Unnamed Item
- Unnamed Item
This page was built for publication: Lower bounds of quantum black-box complexity and degree of approximating polynomials by influence of Boolean variables
