The quantum adversary method and classical formula size power bounds

DOI10.1007/s00037-006-0212-7zbMath1132.68032arXivquant-ph/0501057OpenAlexW2123056342MaRDI QIDQ2458941

Sophie Laplante, Troy Lee, Mario Szegedy

Publication date: 5 November 2007

Published in: Computational Complexity (Search for Journal in Brave)

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

zbMATH Keywords

lower boundsquantum computingcommunication complexityadversary methodformula size

Mathematics Subject Classification ID

Quantum computation (81P68) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (11)

New bounds on the half-duplex communication complexity ⋮ Span-Program-Based Quantum Algorithm for Evaluating Unbalanced Formulas ⋮ Smallest Formulas for Parity of 2 k Variables Are Essentially Unique ⋮ A stronger LP bound for formula size lower bounds via clique constraints ⋮ Exploring the Limits of Subadditive Approaches: Parallels between Optimization and Complexity Theory ⋮ LOSSLESS QUANTUM DATA COMPRESSION AND QUANTUM KOLMOGOROV COMPLEXITY ⋮ BREAKING THE RECTANGLE BOUND BARRIER AGAINST FORMULA SIZE LOWER BOUNDS ⋮ On convex complexity measures ⋮ Smallest formulas for the parity of \(2^k\) variables are essentially unique ⋮ Algorithms and lower bounds for de morgan formulas of low-communication leaf gates ⋮ Evaluation of exact quantum query complexities by semidefinite programming

This page was built for publication: The quantum adversary method and classical formula size power bounds