Span programs for functions with constant-sized 1-certificates

DOI10.1145/2213977.2213985zbMath1286.81043DBLPconf/stoc/Belovs12arXiv1105.4024OpenAlexW2002296566WikidataQ29396605 ScholiaQ29396605MaRDI QIDQ5415466

Aleksandrs Belovs

Publication date: 13 May 2014

Published in: Proceedings of the forty-fourth annual ACM symposium on Theory of computing (Search for Journal in Brave)

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

zbMATH Keywords

quantum algorithms

Mathematics Subject Classification ID

Quantum computation (81P68) Quantum algorithms and complexity in the theory of computing (68Q12)

Related Items (23)

Improving quantum query complexity of Boolean matrix multiplication using graph collision ⋮ Optimal parallel quantum query algorithms ⋮ Quantum algorithm for triangle finding in sparse graphs ⋮ Quantum Complexity of Boolean Matrix Multiplication and Related Problems ⋮ Approximate span programs ⋮ Quantum algorithms for finding constant-sized sub-hypergraphs ⋮ Unnamed Item ⋮ Fooling views: a new lower bound technique for distributed computations under congestion ⋮ Quantum Query Algorithms are Completely Bounded Forms. ⋮ Quantum algorithm design: techniques and applications ⋮ Quantum Query Algorithms Are Completely Bounded Forms ⋮ On the power of non-adaptive learning graphs ⋮ Improved quantum query algorithms for triangle detection and associativity testing ⋮ Quantum Lower Bounds for Tripartite Versions of the Hidden Shift and the Set Equality Problems ⋮ Quantum algorithm for the multicollision problem ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Quantum Algorithms for Classical Probability Distributions ⋮ Unnamed Item ⋮ Extended learning graphs for triangle finding ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Quantum algorithms for learning symmetric juntas via the adversary bound

This page was built for publication: Span programs for functions with constant-sized 1-certificates