Lower Bounds for Randomized and Quantum Query Complexity Using Kolmogorov Arguments

DOI10.1137/050639090zbMath1158.81319arXivquant-ph/0311189OpenAlexW2051165831MaRDI QIDQ3614148

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

Kolmogorov complexitylower boundsquantum computingquery complexityadversary method

Mathematics Subject Classification ID

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

Related Items (11)

On the black-box complexity of Sperner's Lemma ⋮ Span-Program-Based Quantum Algorithm for Evaluating Unbalanced Formulas ⋮ Quantum attribute-based encryption: a comprehensive study ⋮ LOSSLESS QUANTUM DATA COMPRESSION AND QUANTUM KOLMOGOROV COMPLEXITY ⋮ Kolmogorov complexity and combinatorial methods in communication complexity ⋮ Polynomial degree vs. quantum query complexity ⋮ On the power of Ambainis lower bounds ⋮ Adversary lower bounds for nonadaptive quantum algorithms ⋮ Quantum counterfeit coin problems ⋮ A quantum evolving secret sharing scheme ⋮ Unnamed Item

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