Span Programs and Quantum Query Complexity: The General Adversary Bound Is Nearly Tight for Every Boolean Function
From MaRDI portal
Publication:5171199
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
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
