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

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

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)

Cites Work

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

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)