Quantum algorithms for learning symmetric juntas via the adversary bound

DOI10.1007/s00037-015-0099-2zbMath1329.68115arXiv1311.6777OpenAlexW1990290564MaRDI QIDQ2351390

Aleksandrs Belovs

Publication date: 23 June 2015

Published in: Computational Complexity (Search for Journal in Brave)

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

zbMATH Keywords

computational learning theorycombinatorial group testingsemi-definite optimizationquantum query algorithmsrepresentation theory of the symmetric group

Mathematics Subject Classification ID

Computational learning theory (68Q32) Semidefinite programming (90C22) Quantum computation (81P68) Symmetric groups (20B30) Quantum algorithms and complexity in the theory of computing (68Q12)

Related Items

Approximate Degree in Classical and Quantum Computing, Learning bounds for quantum circuits in the agnostic setting, Learning quantum finite automata with queries, EXPONENTIAL IMPROVEMENT IN PRECISION FOR SIMULATING SPARSE HAMILTONIANS, On the power of non-adaptive learning graphs, Quantum vs Classical Proofs and Subset Verification, Quantum Algorithms for Classical Probability Distributions, Unnamed Item, Unnamed Item, Quantum algorithm for learning secret strings and its experimental demonstration

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the power of non-adaptive learning graphs
• Quantum counterfeit coin problems
• Adversary lower bounds for nonadaptive quantum algorithms
• Nonadaptive quantum query complexity
• Complexity measures and decision tree complexity: a survey.
• Oracles and queries that are sufficient for exact learning
• Queries and concept learning
• The quantum query complexity of the hidden subgroup problem is polynomial
• Quantum algorithms for learning and testing juntas
• Improved bounds on quantum learning algorithms
• Super-polynomial quantum speed-ups for boolean evaluation trees with hidden structure
• Span Programs and Quantum Algorithms for st-Connectivity and Claw Detection
• Span-program-based quantum algorithm for evaluating formulas
• Quantum lower bounds for the collision and the element distinctness problems
• Exponential algorithmic speedup by a quantum walk
• Learning DNF over the Uniform Distribution Using a Quantum Example Oracle
• Quantum Complexity Theory
• A ‘Pretty Good’ Measurement for Distinguishing Quantum States
• Equivalences and Separations Between Quantum and Classical Learnability
• Span Programs and Quantum Query Complexity: The General Adversary Bound Is Nearly Tight for Every Boolean Function
• Testing juntas nearly optimally
• STACS 2004
• Span programs for functions with constant-sized 1-certificates
• Quantum Query Complexity of State Conversion
• Improved Quantum Query Algorithms for Triangle Finding and Associativity Testing
• Quantum lower bounds by quantum arguments