Lower bounds of a quantum search for an extreme point

DOI10.1098/RSPA.1999.0397zbMATH Open0935.68016arXivquant-ph/9806001OpenAlexW1989726495WikidataQ56060112 ScholiaQ56060112MaRDI QIDQ4262186FDOQ4262186

Authors: Yuri Ozhigov 

Publication date: 12 September 1999

Published in: Proceedings of the Royal Society of London. Series A: Mathematical and Physical Sciences (Search for Journal in Brave)

Abstract: We show that Durr-Hoyer's quantum algorithm of searching for extreme point of integer function can not be sped up for functions chosen randomly. Any other algorithm acting in substantially shorter time $o(sqrt{2}^n)$ gives incorrect answer for the functions with the single point of maximum chosen randomly with probability converging to 1. The lower bound as $Omega(sqrt{2}^n/b)$ was established for the quantum search for solution of equations $f(x)=1$ where $f$ is a Boolean function with $b$ such solutions chosen at random with probability converging to 1.

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

Recommendations

• Lower Bounds for Local Search by Quantum Arguments
• Lower bounds for local search by quantum arguments
• On the complexity of searching for a maximum of a function on a quantum computer
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Exact quantum lower bound for Grover's problem

zbMATH Keywords

quantum algorithmsearching

Mathematics Subject Classification ID

Searching and sorting (68P10) Nonnumerical algorithms (68W05)

Cited In (3)

• A low failure rate quantum algorithm for searching maximum or minimum
• On the complexity of searching for a maximum of a function on a quantum computer
• Quantum Existence Testing and Its Application for Finding Extreme Values in Unsorted Databases

This page was built for publication: Lower bounds of a quantum search for an extreme point

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