Deutsch-Jozsa 算法发表于 1992 年，是第一个被证明相对于任何可能的经典算法都具有指数级加速的量子算法，不过这只针对一个刻意构造出来的问题。给定一个被保证要么是常数函数（对每个输入都返回相同输出）、要么是平衡函数（对恰好一半的输入返回 0、另一半返回 1）的隐藏函数，经典算法在最坏情况下最多需要 2^(n-1) + 1 次查询才能判断是哪一种，而 Deutsch-Jozsa 算法只需一次查询就能给出答案，方法是把输入寄存器置于叠加态，把该函数作为一个量子预言机来施加，并利用干涉，使得只有常数函数或只有平衡函数才会产生某个特定的测量结果。这个算法本身没有已知的实际应用。它的重要性是历史性和教学性的：它展示了预言机查询加干涉这一核心机制，而后来真正有用的算法，比如 Grover 算法和 Shor 算法，正是建立在这一机制之上；它通常会与相关的 Bernstein-Vazirani 算法和 Simon 算法一起作为量子查询复杂度的标准入门内容来讲授，之后才会进入 Grover 搜索算法。