Reference articles on history, science, culture and more
Surprise meSurprise meSubscribe
Encyclopedia

BHT algorithm

Quantum algorithm

Wikipedia contributorsAdapted for Fathomly · View authors
1 min read
Source updated March 26, 2026

In quantum computing, the Brassard-Høyer-Tapp (BHT) algorithm is a quantum algorithm that solves the collision problem. In this problem, one is given n and an 2-to-1 function f:\,\{1,\ldots ,n\}\rightarrow \{1,\ldots ,n\} and needs to find two inputs that f maps to the same output. The BHT algorithm only makes O(n^{1/3}) queries to f, which matches the lower bound of \Omega (n^{1/3}) in the black box model. The algorithm can be generalized to r-to-1 function with a complexity of O\left(\left({\frac {n}{r}}\right)^{1/3}\right).

The algorithm was discovered by Gilles Brassard, Peter Høyer, and Alain Tapp in 1997. It uses Grover's algorithm, which was discovered the year before.

01Algorithm

Intuitively, the algorithm combines the square root speedup from the birthday paradox using (classical) randomness with the square root speedup from Grover's (quantum) algorithm.

First, n1/3 inputs to f are selected at random and f is queried at all of them. If there is a collision among these inputs, then we return the colliding pair of inputs. Otherwise, all these inputs map to distinct values by f. Then Grover's algorithm is used to find a new input to f that collides. Since there are n inputs to f and n1/3 of these could form a collision with the already queried values, Grover's algorithm can find a collision with O\left({\sqrt {\frac {n}{n^{1/3}}}}\right)=O(n^{1/3}) extra queries to f.

Watch videos about BHT algorithmExplainers and documentaries on YouTube (opens in a new tab)

Sources and credits

This article is adapted from the Wikipedia article “BHT algorithm”, written by its contributors and licensed under CC BY-SA 4.0. Fathomly has changed the layout, removed citation markers, navigation and maintenance notices, and adjusted punctuation. This adapted version is shared under the same license. For references, see the original article.

Fathomly is not affiliated with or endorsed by the Wikimedia Foundation. Spotted a problem? Tell us.

Continue exploring

Related topics

Element distinctness problem

In computational complexity theory, the element distinctness problem or element uniqueness problem is the problem of determining whether all the elements of a list are distinct. It is a well studied problem in many different models of computation.

Grover's algorithm

In quantum computing, Grover's algorithm, also known as the quantum search algorithm, is a quantum algorithm for unstructured search that finds with high probability the unique input to a black box function that produces a particular output value, using just O {\displaystyle O({\sqrt {N}})} evaluations of the function, where N {\displaystyle N} is the size of the function's domain. It was devised by an Indian-American computer scientist Lov Grover in 1996.