1992年に発表されたDeutsch-Jozsaアルゴリズムは、可能などんな古典アルゴリズムに対しても指数関数的な高速化を証明した最初の量子アルゴリズムでした。ただし、それは意図的に構成された問題に対してのみのことです。ある隠れた関数が、定数関数（どの入力に対しても同じ出力を返す）かバランス関数（全入力のうちちょうど半分に対して0を、残り半分に対して1を返す）のいずれかであると保証されているとき、古典アルゴリズムは最悪の場合、どちらであるかを判定するのに最大で2^(n-1) + 1回のクエリを必要とします。それに対してDeutsch-Jozsaアルゴリズムは、入力レジスタを重ね合わせ状態にし、その関数を量子オラクルとして適用し、干渉を利用することで、定数関数の場合だけ、あるいはバランス関数の場合だけに特定の測定結果が生じるようにし、たった1回のクエリで答えを決定します。このアルゴリズムに知られている実用上の応用はありません。その重要性は歴史的かつ教育的なものです。オラクルへのクエリと干渉という中核的なメカニズムを実証し、それが後にGroverやShorのような本当に有用なアルゴリズムの土台となりました。通常は、関連するBernstein-VaziraniアルゴリズムやSimonのアルゴリズムとあわせて、Grover探索へ進む前の、量子クエリ計算量への標準的な入門として教えられています。