On the uselessness of quantum queries

DOI10.1016/J.TCS.2011.06.037zbMATH Open1267.68116OpenAlexW1870507853MaRDI QIDQ433109FDOQ433109

Authors David A. Meyer, James Pommersheim

Publication date 13 July 2012

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2011.06.037

zbMATH Keywords

computational complexityquantum algorithmsoracle query complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational learning theory (68Q32) Quantum algorithms and complexity in the theory of computing (68Q12) Quantum computation (81P68) Quantum measurement theory, state operations, state preparations (81P15)

Recommendations

• Quantum lower bounds by polynomials
• Nonadaptive quantum query complexity
• The power of various real-valued quantum queries
• Quantum and classical query complexities for generalized Deutsch-Jozsa problems
• Understanding quantum algorithms via query complexity

Cites work

• scientific article; zbMATH DE number 1030974 (Why is no real title available?)
• scientific article; zbMATH DE number 1775388 (Why is no real title available?)
• scientific article; zbMATH DE number 2103524 (Why is no real title available?)
• How to share a secret
• On the Power of Quantum Computation
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Quantum algorithms and the Fourier transform
• Quantum algorithms revisited
• Quantum interpolation of polynomials
• Quantum lower bounds by polynomials
• Quantum theory, the Church–Turing principle and the universal quantum computer
• Queries and concept learning
• Single-query learning from abelian and non-abelian Hamming distance oracles
• The geometry of quantum learning
• Unbounded-Error Quantum Query Complexity

Cited in

(5)

• Computation in a general physical setting
• Oracles and query lower bounds in generalised probabilistic theories
• Statistical properties of thermal state under quantum Hadamard transform
• Quantum algorithm for multivariate polynomial interpolation
• Multi-query quantum sums

This page was built for publication: On the uselessness of quantum queries

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q433109)