Lower Bounds for Randomized and Quantum Query Complexity Using Kolmogorov Arguments

DOI10.1137/050639090MaRDI QIDQ3614148zbMATH OpenOpenAlexFDO

Authors Sophie Laplante, Frédéric Magniez

Publication date 16 March 2009

Published in SIAM Journal on Computing (Search for Journal in Brave)

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

zbMATH Keywords

adversary methodKolmogorov complexitylower boundsquantum computingquery complexity

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Quantum computation (81P68)

Abstract: We prove a very general lower bound technique for quantum and randomized query complexity, that is easy to prove as well as to apply. To achieve this, we introduce the use of Kolmogorov complexity to query complexity. Our technique generalizes the weighted, unweighted methods of Ambainis, and the spectral method of Barnum, Saks and Szegedy. As an immediate consequence of our main theorem, adversary methods can only prove lower bounds for boolean functions $f$ in $O(min(sqrtn{C}_0(f),sqrtn{C}_1(f)))$, where $C_0,C_1$ is the certificate complexity, and $n$ is the size of the input. We also derive a general form of the ad hoc weighted method used by Hoyer, Neerbek and Shi to give a quantum lower bound on ordered search and sorting.

Recommendations

• Quantum lower bounds by quantum arguments
• Logical Approaches to Computational Barriers
• Quantum lower bounds by quantum arguments
• Explicit relation between all lower bound techniques for quantum query complexity
• Explicit relation between all lower bound techniques for quantum query complexity

Cited in

(24)

• A quantum evolving secret sharing scheme
• Polynomial degree vs. quantum query complexity
• Improved bounds on the randomized and quantum complexity of initial-value problems
• The quantum query complexity of approximating the median and related statistics
• Explicit relation between all lower bound techniques for quantum query complexity
• Explicit relation between all lower bound techniques for quantum query complexity
• scientific article; zbMATH DE number 5899233 (Why is no real title available?)
• Lossless quantum data compression and quantum Kolmogorov complexity
• scientific article; zbMATH DE number 6667586 (Why is no real title available?)
• All classical adversary methods are equivalent for total functions
• Span-program-based quantum algorithm for evaluating unbalanced formulas
• Complexity Upper Bounds for Classical Locally Random Reductions Using a Quantum Computational Argument
• Kolmogorov Complexity and Combinatorial Methods in Communication Complexity
• The polynomial method strikes back: tight quantum query bounds via dual polynomials
• Mathematical Foundations of Computer Science 2004
• Kolmogorov complexity and combinatorial methods in communication complexity
• On the power of Ambainis lower bounds
• Logical Approaches to Computational Barriers
• Quantum attribute-based encryption: a comprehensive study
• Quantum counterfeit coin problems
• Quantum sabotage complexity
• On the black-box complexity of Sperner's Lemma
• The quantum setting with randomized queries for continuous problems
• Adversary lower bounds for nonadaptive quantum algorithms

This page was built for publication: Lower Bounds for Randomized and Quantum Query Complexity Using Kolmogorov Arguments

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