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

DOI10.1016/S0020-0190(00)00069-7zbMath1339.68093arXivquant-ph/9904107OpenAlexW2024588775MaRDI QIDQ294804

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 complexityBoolean functionsquantum computation

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)

Related Items (9)

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 ⋮ Complexity of quantum circuits via sensitivity, magic, and coherence ⋮ 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