Span Programs and Quantum Query Complexity: The General Adversary Bound Is Nearly Tight for Every Boolean Function

DOI10.1109/FOCS.2009.55zbMath1292.68070arXiv0904.2759MaRDI QIDQ5171199

Publication date: 25 July 2014

Published in: 2009 50th Annual IEEE Symposium on Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0904.2759

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Quantum computation (81P68) Quantum algorithms and complexity in the theory of computing (68Q12)

Related Items (27)

Construction of a class of quantum Boolean functions based on the Hadamard matrix ⋮ A query-efficient quantum algorithm for maximum matching on general graphs ⋮ Span-Program-Based Quantum Algorithm for Evaluating Unbalanced Formulas ⋮ A strong direct product theorem for quantum query complexity ⋮ Optimal parallel quantum query algorithms ⋮ All Classical Adversary Methods are Equivalent for Total Functions ⋮ Approximate span programs ⋮ Quantum attribute-based encryption: a comprehensive study ⋮ Optimal direct sum results for deterministic and randomized decision tree complexity ⋮ Quantum algorithms for finding constant-sized sub-hypergraphs ⋮ Unnamed Item ⋮ Quantum Query Algorithms are Completely Bounded Forms. ⋮ Quantum Query Algorithms Are Completely Bounded Forms ⋮ Unnamed Item ⋮ Quantum Lower Bounds for Tripartite Versions of the Hidden Shift and the Set Equality Problems ⋮ Fourier concentration from shrinkage ⋮ Quantum counterfeit coin problems ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A quantum evolving secret sharing scheme ⋮ Superlinear Advantage for Exact Quantum Algorithms ⋮ Quantum Algorithms for Classical Probability Distributions ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Algorithms and lower bounds for de morgan formulas of low-communication leaf gates ⋮ Graph approach to quantum systems ⋮ Quantum algorithms for learning symmetric juntas via the adversary bound

This page was built for publication: Span Programs and Quantum Query Complexity: The General Adversary Bound Is Nearly Tight for Every Boolean Function