A Quantum Algorithm for Finding the Minimum

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.

2 pages

References in corpus (1)

• Strengths and Weaknesses of Quantum Computing

Cited by in corpus (109)

• Quantum Machine Learning
• Quantum algorithms: an overview
• Quantum computing for finance
• Quantum Computation in Quantum-Hall Systems
• Grover Adaptive Search for Constrained Polynomial Binary Optimization
• Quantum Algorithm Implementations for Beginners
• Quantum Computation
• Recent advances for quantum classifiers
• Implementation of quantum imaginary-time evolution method on NISQ devices: Nonlocal approximation
• Advances in Quantum Reinforcement Learning
• Quantum Algorithms for Jet Clustering
• Quantum machine learning for data scientists
• The Hidden Subgroup Problem - Review and Open Problems
• Quantum Machine Learning for Finance
• Low depth mechanisms for quantum optimization
• Quantum speedup of the Travelling Salesman Problem for bounded-degree graphs
• Quantum anomaly detection in the latent space of proton collision events at the LHC
• Machine learning \& artificial intelligence in the quantum domain
• An All-Pair Quantum SVM Approach for Big Data Multiclass Classification
• Lyapunov control-inspired strategies for quantum combinatorial optimization
• Advances in quantum machine learning
• Quantum Computation Beyond the Circuit Model
• Quantum Algorithm for Higher-Order Unconstrained Binary Optimization and MIMO Maximum Likelihood Detection
• Quantum Computing: Lecture Notes
• Quantum Differentially Private Sparse Regression Learning
• Quantum Dimensionality Reduction by Linear Discriminant Analysis
• K-Means Clustering on Noisy Intermediate Scale Quantum Computers
• A Grover search-based algorithm for the list coloring problem
• Gate-based Quantum Computing for Protein Design
• Dynamic Grover Search: Applications in Recommendation systems and Optimization problems
• Quantum algorithm for Neighborhood Preserving Embedding
• Numerical Evidence for Exponential Speed-up of QAOA over Unstructured Search for Approximate Constrained Optimization
• Threshold-Based Quantum Optimization
• An optimized quantum minimum searching algorithm with sure-success probability and its experiment simulation with Cirq
• A Study of Parallel Self-Organizing Map
• Quantum speedup for track reconstruction in particle accelerators
• Improving Quantum Query Complexity of Boolean Matrix Multiplication Using Graph Collision
• Prospective Algorithms for Quantum Evolutionary Computation
• A Quantum-Search-Aided Dynamic Programming Framework for Pareto Optimal Routing in Wireless Multihop Networks
• The Quantum Version Of Classification Decision Tree Constructing Algorithm C5.0
• Quantum exploration algorithms for multi-armed bandits
• Quantum algorithms for scientific computing
• Near-Optimal Quantum Algorithms for Multivariate Mean Estimation
• Strength and Weakness in Grover's Quantum Search Algorithm
• Trajectory optimization using quantum computing
• Quantum-accelerated constraint programming
• Quantum Algorithms for String Processing
• Introducing Structure to Expedite Quantum Search
• A Benchmarking Study of Quantum Algorithms for Combinatorial Optimization
• Quantum Algorithms for Reinforcement Learning with a Generative Model
• Optimizing Gate Decomposition for High-Level Quantum Programming
• Transit facility allocation: Hybrid quantum-classical optimization
• Small quantum computers and large classical data sets
• A Digital Quantum Algorithm for Jet Clustering in High-Energy Physics
• On proving the robustness of algorithms for early fault-tolerant quantum computers
• Trials and Tribulations of Developing Hybrid Quantum-Classical Microservices Systems
• Amplitude amplification-inspired QAOA: Improving the success probability for solving 3SAT
• Quantum basin hopping with gradient-based local optimisation
• A quantum algorithm for solving 0-1 Knapsack problems
• Amplitude Amplification for Optimization via Subdivided Phase Oracle
• Fast Classical and Quantum Algorithms for Online $k$-server Problem on Trees
• A Quantum Algorithm for Finding $k$-Minima
• Quantum matching pursuit: A quantum algorithm for sparse representations
• Quantum Computing Applications for Flight Trajectory Optimization
• Speedup of iterated quantum search by parallel performance
• Quantum Algorithms for the Pathwise Lasso
• Quantum-inspired attribute selection algorithm: A Fidelity-based Quantum Decision Tree
• Design of gates for quantum computation: the three-spin XOR gate in terms of two-spin interactions
• Robust quantum minimum finding with an application to hypothesis selection
• An Optimized Quantum Maximum or Minimum Searching Algorithm and its Circuits
• Distributed Quantum Computing Utilizing Multiple Codes on Imperfect Hardware
• (Almost) tight bounds for randomized and quantum Local Search on hypercubes and grids
• Quantifying Grover speed-ups beyond asymptotic analysis
• Canonical Construction of Quantum Oracles
• Quantum and Classical Algorithms for Approximate Submodular Function Minimization
• Basic quantum subroutines: finding multiple marked elements and summing numbers
• Theoretical Analyses of Quantum Counting against Decoherence Errors
• Preparing Many Copies of a Quantum State in the Black-Box Model
• Quantum Approximation Optimization Algorithm for the Trellis based Viterbi Decoding of Classical Error Correcting Codes
• Quantum Alphatron: quantum advantage for learning with kernels and noise
• Spectral sparsification of matrix inputs as a preprocessing step for quantum algorithms
• Quantum Circuit for Calculating Mobius-like Transforms Via Grover-like Algorithm
• Quantum Generative Training Using Rényi Divergences
• Quantum Algorithm for Dynamic Programming Approach for DAGs. Applications for Zhegalkin Polynomial Evaluation and Some Problems on DAGs
• Optimizing Quantum Search with a Binomial Version of Grover's Algorithm
• Quantum Algorithm for Online Convex Optimization
• Quantum Algorithms for the Shortest Common Superstring and Text Assembling Problems
• Quantum Differential Cryptanalysis
• The quantum version of the shifted power method and its application in quadratic binary optimization
• Quantum algorithms for matrix scaling and matrix balancing
• Machine learning methods in quantum computing theory
• Binary Subdivision for Quantum Search
• Quantum Algorithms for Matrix Products over Semirings
• Robust String Matching in O(\sqrt{N}+M) Quantum Queries
• On the Complexity of Searching Maximum of a Function on a Quantum Computer
• Quantum Query Complexity of Dyck Languages with Bounded Height
• Global Optimum Search in Quantum Deep Learning
• Improved Quantum Query Upper Bounds Based on Classical Decision Trees
• Improved Classical and Quantum Algorithms for the Shortest Vector Problem via Bounded Distance Decoding
• Reflection-Based Adiabatic State Preparation
• Asymptotic Quantum Search and a Quantum Algorithm for Calculation of a Lower Bound of the Probability of Finding a Diophantine Equation That Accepts Integer Solutions
• Quantum optimisation via maximally amplified states
• Graph comparison via nonlinear quantum search
• Quantum complexity of minimum cut
• Linear Order Matrix Inversion Method with Help from Quantum Searching Algorithm
• Parts of Speech Tagging in NLP: Runtime Optimization with Quantum Formulation and ZX Calculus
• Quantum Algorithms for Unsupervised Machine Learning and Neural Networks
• On the quantum complexity of approximating median of continuous distribution
• Quantum Speedup for the Minimum Steiner Tree Problem