Quantum Minimum Finding

Overview

Quantum minimum finding locates the smallest value in an unsorted list of N numbers using about the square root of N queries, where a classical computer must look at about N entries. It works by calling Grover's search repeatedly, each time asking whether any entry is smaller than the best one found so far.

The result is a quadratic speedup for one of the most basic operations in computing, finding an extreme value. Because minimum and maximum finding are subroutines inside many larger algorithms, including graph algorithms, clustering, and optimization, this algorithm is widely used as a building block.

The problem it solves

Find the index of the minimum element in an unsorted list of N items — classically requires O(N) comparisons.

History and background

Christoph Dürr and Peter Høyer posted the algorithm in 1996, soon after Grover's search algorithm appeared, in a paper called A Quantum Algorithm for Finding the Minimum. Their analysis showed that the expected number of queries is proportional to the square root of N and that the algorithm succeeds with probability at least one half, which can be boosted by repetition.

The method rests on the exponential-search variant of Grover's algorithm by Boyer, Brassard, Høyer, and Tapp, which handles the case where the number of solutions is unknown. Later work by Dürr, Heiligman, Høyer, and Mhalla applied it to graph problems such as minimum spanning trees and shortest paths in 2004, and Ambainis and others used related ideas for quantum walk algorithms. A matching lower bound of the order of the square root of N follows from the general optimality of Grover's algorithm.

How it works

Picks a random element as the current minimum. Uses Grover's search to find any element smaller than it. Repeats this until no smaller element is found. Requires O(√N) oracle calls on average.

Finding the minimum can be rephrased as a sequence of search problems. Pick any entry as a candidate. Ask whether there is an entry smaller than the candidate. If yes, find one with Grover's algorithm and make it the new candidate. Keep going until no smaller entry exists.

The key observation is that the number of entries smaller than the candidate shrinks as the candidate improves, and Grover's search is fastest when many solutions exist. If the candidate is chosen at random, then on average its rank is in the middle of the list, so the first search has about half of the entries as solutions and is quick. Each success moves the candidate to a better rank, and the expected total work is dominated by the final stages, where few entries are smaller, which cost about the square root of N in total.

A careful analysis shows that the sum of the costs over all rounds is a geometric-like series that adds up to a constant times the square root of N, rather than the square root of N times the number of rounds.

Step by step

1. Choose a random index y as the current threshold, and read the value T of y.
2. Define the oracle that marks every index i with T of i less than the current threshold value.
3. Run Grover's search with an unknown number of solutions, using the exponential schedule of iteration counts, to find a marked index.
4. If a marked index i is found, set y equal to i and return to step 2 with the new threshold.
5. If no marked index is found after a time proportional to the square root of N, conclude that y is the minimum.
6. Output the index y and its value, which is correct with probability at least one half, and repeat the whole procedure to increase confidence.

A worked example

Take a list of 1,000,000 numbers in no particular order. A classical algorithm reads every entry, a million operations. The quantum algorithm picks a random starting entry, which has expected rank around 500,000. Grover's search for a smaller entry succeeds quickly because half of the list qualifies. After the first improvement, the threshold's rank is around a quarter of the way, then an eighth, and so on, each round costing more because fewer entries qualify.

The total number of Grover iterations is a small multiple of the square root of 1,000,000, which is 1,000. The original analysis gives a constant factor around 22 for the leading term, so a practical run uses a few tens of thousands of oracle calls, versus a million classically.

Complexity and resources

What hardware it needs

• A fault-tolerant computer able to run Grover iterations over a large index register.
• Quantum random access memory for the list, or a function that computes the entries coherently.
• A reversible comparator to mark entries smaller than the threshold.

Applications

• Subroutine in graph algorithms for connectivity, minimum spanning trees, and shortest paths, with polynomial speedups.
• Nearest-neighbor and clustering steps, such as assigning points to the closest center.
• Optimization by exhaustive search over a candidate set, for example in discrete optimization with a computable objective.
• A component in quantum algorithms for machine learning and combinatorial search.

Limitations and caveats

• The speedup is quadratic, which can be negated by the overhead of error correction and by data loading.
• The data must be accessible coherently, which is a problem for large classical lists.
• The success probability is constant for one run, so repetition is needed for high confidence.
• For structured problems, classical algorithms may exploit structure and beat the unstructured bound.

Common misconceptions

• It does not sort the list. It finds only the minimum.
• It does not look at all entries at once and compare them. It uses interference to amplify small entries.
• It cannot beat the square root bound for unstructured data.

How it compares

• Grover's algorithm finds a marked item, while minimum finding finds the smallest, using repeated Grover searches.
• Quantum counting and amplitude estimation give other order statistics, such as the median, with similar speedups.
• Classical algorithms for sorted or structured data can find extremes in logarithmic time.

Real-world impact

Useful for optimization problems where finding the best solution requires scanning many candidates — a component in quantum branch-and-bound algorithms for combinatorial optimization.

Why it matters

Minimum finding turns Grover's search from a yes-or-no tool into a way of solving optimization problems over unstructured candidate sets. It is the cleanest example of a reduction from optimization to search, and it shows the quadratic speedup extends to many problems built from comparison.

It also illustrates the careful design of quantum algorithms with unknown numbers of solutions, a recurring difficulty that the exponential schedule solves.

Frequently asked questions

Keep learning

• Related algorithm: Grover's Algorithm
• Related algorithm: Quantum Amplitude Amplification
• Related algorithm: Quantum Counting
• Related algorithm: Quantum k-Means Clustering

This page is written for educational purposes. Complexity statements describe the best known results at the time of review (September 30, 2026), and research in this area moves quickly, so check recent papers before relying on a specific bound.

← Back to Algorithms Database