The quantum query complexity of approximating the median and related statistics
From MaRDI portal
Publication:2819571
DOI10.1145/301250.301349zbMath1345.68141OpenAlexW2029029634MaRDI QIDQ2819571
Publication date: 29 September 2016
Published in: Proceedings of the thirty-first annual ACM symposium on Theory of Computing (Search for Journal in Brave)
Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.38.9366
Quantum computation (81P68) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Quantum algorithms and complexity in the theory of computing (68Q12)
Related Items (40)
From Monte Carlo to quantum computation ⋮ Quantum approximation. I: Embeddings of finite-dimensional \(L_{p}\) spaces ⋮ Quantum complexity of parametric integration ⋮ Sharp error bounds on quantum Boolean summation in various settings ⋮ The power of various real-valued quantum queries ⋮ Average case quantum lower bounds for computing the Boolean mean ⋮ The quantum setting with randomized queries for continuous problems ⋮ The Sturm-Liouville eigenvalue problem and NP-complete problems in the quantum setting with queries ⋮ A lower bound for the Sturm-Liouville eigenvalue problem on a quantum computer ⋮ Improved algorithms for quantum identification of Boolean oracles ⋮ Quantum attribute-based encryption: a comprehensive study ⋮ Quantum and classical query complexities for generalized Deutsch-Jozsa problems ⋮ On a problem in quantum summation. ⋮ Quantum integration in Sobolev classes ⋮ Non-Boolean quantum amplitude amplification and quantum mean estimation ⋮ Quantum speed-up for unsupervised learning ⋮ Optimality proofs of quantum weight decision algorithms ⋮ Histogram-based segmentation of quantum images ⋮ Quantum lower bounds by quantum arguments ⋮ Quantum lower bounds by entropy numbers ⋮ On the complexity of the multivariate Sturm-Liouville eigenvalue problem ⋮ Quantum algorithms on Walsh transform and Hamming distance for Boolean functions ⋮ On the quantum and randomized approximation of linear functionals on function spaces ⋮ Quantum algorithm for the asymmetric weight decision problem and its generalization to multiple weights ⋮ Quantum complexity of integration ⋮ Development of a novel robust identification scheme for nonlinear dynamic systems ⋮ Polynomial degree vs. quantum query complexity ⋮ On the complexity of searching for a maximum of a function on a quantum computer ⋮ Randomized and quantum algorithms yield a speed-up for initial-value problems ⋮ On the power of Ambainis lower bounds ⋮ Adiabatic quantum counting by geometric phase estimation ⋮ Unnamed Item ⋮ Quantum Random Walks – New Method for Designing Quantum Algorithms ⋮ Quantum Chebyshev's Inequality and Applications ⋮ Classical and quantum complexity of the Sturm-Liouville eigenvalue problem ⋮ Improved bounds on the randomized and quantum complexity of initial-value problems ⋮ Complexity measures and decision tree complexity: a survey. ⋮ Quantum summation with an application to integration. ⋮ Testing Boolean Functions Properties ⋮ Quantum computation and quantum information
This page was built for publication: The quantum query complexity of approximating the median and related statistics
