On the complexity of searching for a maximum of a function on a quantum computer

DOI10.1007/S11128-006-0011-8MaRDI QIDQ2491387zbMATH OpenOpenAlexFDO

Authors Maciej Goćwin

Publication date 29 May 2006

Published in Quantum Information Processing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/quant-ph/0507060

zbMATH Keywords

Numerical optimizationoptimal algorithmquantum computingquery complexity

Mathematics Subject Classification ID

Numerical optimization and variational techniques (65K10) Quantum computation (81P68)

Abstract: We deal with a problem of finding maximum of a function from the Holder class on a quantum computer. We show matching lower and upper bounds on the complexity of this problem. We prove upper bounds by constructing an algorithm that uses the algorithm for finding maximum of a discrete sequence. To prove lower bounds we use results for finding logical OR of sequence of bits. We show that quantum computation yields a quadratic speed-up over deterministic and randomized algorithms.

Recommendations

• Lower bounds of a quantum search for an extreme point
• Quantum complexity of integration
• Quantum and classical query complexities of local search are polynomially related
• Quantum complexity of the approximation for the classes \({\mathcal B}(W^r_p([0,1]^d))\) and \({\mathcal B}(H^r_p([0,1]^d))\)
• On the query complexity of finding a local maximum point.

Cites work

• Classical and quantum complexity of the Sturm-Liouville eigenvalue problem
• scientific article; zbMATH DE number 1256737 (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?)
• Improved bounds on the randomized and quantum complexity of initial-value problems
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Quantum approximation. II: Sobolev embeddings
• Quantum complexity of integration
• Quantum integration in Sobolev classes
• Quantum lower bounds by polynomials
• Quantum summation with an application to integration.
• Randomized and quantum algorithms yield a speed-up for initial-value problems
• Strengths and Weaknesses of Quantum Computing
• The quantum query complexity of approximating the median and related statistics
• The Sturm-Liouville eigenvalue problem and NP-complete problems in the quantum setting with queries

Cited in

(1)

• Lower bounds of a quantum search for an extreme point

This page was built for publication: On the complexity of searching for a maximum of a function on a quantum computer

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