{
  "id": "enwiki-001345499270",
  "slug": "bht-algorithm",
  "title": "BHT algorithm",
  "qid": "",
  "lead": "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.",
  "body": "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. ==Algorithm== 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, n 1/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 n 1/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. ==See also== Element distinctness problem Grover's algorithm ==References==",
  "categories": [
    "23603337",
    "26220375",
    "46972413"
  ],
  "license": "CC BY-SA 4.0",
  "source_uri": "https://en.wikipedia.org/w/index.php?oldid=1345499270",
  "content_hash": "",
  "created_at": null,
  "updated_at": 1774521079.0,
  "claims": [],
  "contradictions": [],
  "confidence": 0.6,
  "csl": {
    "id": "enwiki-001345499270",
    "type": "webpage",
    "title": "BHT algorithm",
    "author": [
      {
        "family": "Anticloud FZ LLE",
        "literal": "Anticloud FZ LLE"
      }
    ],
    "container-title": "encyclopegia.org",
    "publisher": "Anticloud FZ LLE",
    "publisher-place": "Dubai, United Arab Emirates",
    "URL": "https://encyclopegia.org/a/bht-algorithm",
    "issued": {
      "date-parts": [
        [
          2026,
          11,
          19
        ]
      ]
    },
    "accessed": {
      "date-parts": [
        [
          2026,
          11,
          19
        ]
      ]
    },
    "license": "CC BY-SA 4.0",
    "DOI": "eo1:enwiki-001345499270",
    "isBasedOn": "https://en.wikipedia.org/w/index.php?oldid=1345499270",
    "note": "Immutable snapshot enwiki-001345499270"
  }
}