2005/07/06 by Maciej Goćwin, Gocwin, Maciej
Computer Science · #Computability, Logic, AI Algorithms #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Physics (quant-ph)
paper · pdf · doi:10.48550/arxiv.quant-ph/0507060
openalex publication_date 2005/07/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.