Lower Bounds for Randomized and Quantum Query Complexity Using Kolmogorov Arguments
From MaRDI portal
Publication:3614148
DOI10.1137/050639090zbMath1158.81319arXivquant-ph/0311189MaRDI 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
Related Items
Kolmogorov complexity and combinatorial methods in communication complexity, On the power of Ambainis lower bounds, Quantum counterfeit coin problems, On the black-box complexity of Sperner's Lemma, Adversary lower bounds for nonadaptive quantum algorithms, Polynomial degree vs. quantum query complexity, LOSSLESS QUANTUM DATA COMPRESSION AND QUANTUM KOLMOGOROV COMPLEXITY, Span-Program-Based Quantum Algorithm for Evaluating Unbalanced Formulas