A Quantum Algorithm for Finding the Minimum

1996/07/18 by Christoph Durr, Durr, Christoph, Peter Hoyer +1 · 36 citations
Computer Science · Physics and Astronomy · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Physics (quant-ph) #cs.DS #quant-ph

paper · pdf · doi:10.48550/arxiv.quant-ph/9607014

2 pages

arxiv created 1999/01/07 · arxiv updated 2009/11/30

Abstract

We give a quantum algorithm to find the index y in a table T of size N such that in time O(c sqrt N), T[y] is minimum with probability at least 1-1/2^c.

Cited by

• A Grover-compatible manifold optimization algorithm for quantum search
• Constraint-oriented biased quantum search for general constrained combinatorial optimization problems
• Dequantizing Short-Path Quantum Algorithms
• Quantum Algorithm for Searching for the Longest Segment and the Largest Empty Rectangle
• Machine Learning by Adiabatic Evolutionary Quantum System
• Quantum Deep Learning Still Needs a Quantum Leap
• Coherence Fraction in Grover Search Algorithm
• Hybrid Quantum-Classical Detection for RIS-Assisted SC-FDE via Grover Adaptive Search
• Parameterized quantum algorithms for closest string problems
• Quantum Search in Superposed Quantum Lattice Gas Automata and Lattice Boltzmann Systems
• End-to-End Quantum Algorithm for Topology Optimization in Structural Mechanics
• Quantum Sparse Recovery and Quantum Orthogonal Matching Pursuit
• Hybrid Sequential Quantum Computing
• Quantum walks through generalized graph composition
• A Quantum Algorithm For Computing Contextuality Bounds
• A Quantum Bagging Algorithm with Unsupervised Base Learners for Label Corrupted Datasets
• Efficient Maximum Clique Detection via Grover's Algorithm with Real-time Global Size Tracking
• Traq: Estimating the Quantum Cost of Classical Programs
• Expressivity Limits in Quantum Walk-based Optimization
• Quantum Algorithms for Finite-horizon Markov Decision Processes
• Grover's algorithm is an approximation of imaginary-time evolution
• Quantum Algorithms for Projection-Free Sparse Convex Optimization
• Quantum Algorithm for Apprenticeship Learning
• Model Predictive Path Integral Control as a Quantum Query Problem
• Quantum Speedups for Polynomial-Time Dynamic Programming Algorithms
• Protein folding with an all-to-all trapped-ion quantum computer
• Quantum Machine Learning
• Efficient QAOA Architecture for Solving Multi-Constrained Optimization Problems
• Hybrid Quantum-Classical Maximum-Likelihood Detection via Grover-based Adaptive Search for RIS-assisted Broadband Wireless Systems
• Solving the Shortest Vector Problem in 2^0.6039n Time via Mid-point Hessian
• A quantum unstructured search algorithm for discrete optimisation: the use case of portfolio optimisation
• Improved Quantum Algorithms for Reinforcement Learning Under a Generative Model
• Quantum-Accelerated Self-Consistent Field: A Hybrid Algorithm
• Quantum-Inspired Cournot Model
• Quantum Circuit Design for Decoded Quantum Interferometry
• IF-QAOA: A Penalty-Free Approach to Accelerating Constrained Quantum Optimization
• Quantum Combine and Conquer and Its Applications to Sublinear Quantum Convex Hull and Maxima Set Construction

Related

• A Quantum Algorithm for finding the Maximum
• A Quantum Algorithm for Finding k-Minima
• Quantum algorithm for finding minimum values in a Quantum Random Access Memory
• Robust quantum minimum finding with an application to hypothesis selection
• Constant-Time Quantum Algorithm For The Unstructured Search Problem