Lesson plan

BHT algorithm

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.

Back to article

Article summary

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.

Key claims

No claims recorded.

Discussion questions

  1. Summarise the article in your own words. Which single claim would you verify first, and why?
  2. Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
  3. If two sources disagreed about one of these facts, what would you need in order to trust one over the other?

Bibliography

No sources recorded.

Key claims and bibliography are generated from the same tracked claims and sources as the article page.