Quantum lower bounds by quantum arguments
From MaRDI portal
Publication:5895206
DOI10.1145/335305.335394zbMath1296.68053OpenAlexW1969454810MaRDI QIDQ5895206
Publication date: 26 September 2014
Published in: Proceedings of the thirty-second annual ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/335305.335394
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Quantum algorithms and complexity in the theory of computing (68Q12)
Related Items
A lower bound on the quantum query complexity of read-once functions ⋮ Quantum separation of local search and fixed point computation ⋮ Quantum query as a state decomposition ⋮ All Classical Adversary Methods are Equivalent for Total Functions ⋮ Quantum algorithm for lexicographically minimal string rotation ⋮ Intricacies of quantum computational paths ⋮ Being a permutation is also orthogonal to one-wayness in quantum world: impossibilities of quantum one-way permutations from one-wayness primitives ⋮ Quantum and Randomized Lower Bounds for Local Search on Vertex-Transitive Graphs ⋮ Quantum vs Classical Proofs and Subset Verification ⋮ Entanglement rates and the stability of the area law for the entanglement entropy ⋮ Entropy lower bounds for quantum decision tree complexity ⋮ Quantum and classical tradeoffs
