Super-polynomial quantum speed-ups for boolean evaluation trees with hidden structure

DOI10.1145/2090236.2090258zbMath1347.68154arXiv1101.0796OpenAlexW1965858702MaRDI QIDQ2826061

Avinatan Hassidim, Bohua Zhan, Shelby Kimmel

Publication date: 7 October 2016

Published in: Proceedings of the 3rd Innovations in Theoretical Computer Science Conference (Search for Journal in Brave)

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

zbMATH Keywords

span programsNAND treesuper-polynomial quantum speed-up

Mathematics Subject Classification ID

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

Related Items

Quantum algorithms for learning symmetric juntas via the adversary bound

Cites Work

• Unnamed Item
• The reproducible properties of correct forecasts
• The dimensions of individual strings and sequences
• Effective Strong Dimension in Algorithmic Information and Computational Complexity
• The Complexity of Forecast Testing
• The Well-Calibrated Bayesian
• Asymptotic calibration
• Dimension in Complexity Classes
• Universal prediction
• THE FRACTIONAL DIMENSION OF A SET DEFINED BY DECIMAL PROPERTIES