On the power of non-adaptive learning graphs
From MaRDI portal
Publication:488054
DOI10.1007/s00037-014-0084-1zbMath1314.68134arXiv1210.3279OpenAlexW2029495732MaRDI QIDQ488054
Ansis Rosmanis, Aleksandrs Belovs
Publication date: 23 January 2015
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1210.3279
semidefinite optimizationquantum computingadversary methodquery algorithms\(k\)-sum problemtriangle problem
Related Items
Optimal parallel quantum query algorithms, Quantum algorithms for finding constant-sized sub-hypergraphs, 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, Extended learning graphs for triangle finding, Unnamed Item, Quantum algorithms for learning symmetric juntas via the adversary bound
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Improved quantum query algorithms for triangle detection and associativity testing
- On the power of Ambainis lower bounds
- Orthogonal arrays. Theory and applications
- Complexity measures and decision tree complexity: a survey.
- Quantum algorithms for learning symmetric juntas via the adversary bound
- The quantum query complexity of the hidden subgroup problem is polynomial
- QUANTUM QUERY COMPLEXITY OF CONSTANT-SIZED SUBGRAPH CONTAINMENT
- Adversary lower bound for the k-sum problem
- Search via Quantum Walk
- Quantum lower bounds for the collision and the element distinctness problems
- Quantum Algorithms for the Triangle Problem
- Span programs for functions with constant-sized 1-certificates
- Quantum Walk Algorithm for Element Distinctness
- Quantum Query Complexity of State Conversion
- A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem
- Quantum cryptanalysis of hash and claw-free functions
- Quantum lower bounds by quantum arguments
