Deutsch-Jozsa in One Query

Decide whether a black-box function is constant or balanced with a single evaluation instead of exponentially many.

The promise

You are given f: {0,1}^n -> {0,1} promised to be either constant (same output for all inputs) or balanced (0 on exactly half the inputs, 1 on the other half). Classically the worst case needs 2^(n-1)+1 queries. Deutsch-Jozsa needs one.

Circuit

• Put n input qubits in |0> and one output qubit in |1>.
• Hadamard everything.
• Apply the phase oracle U_f, which stamps (-1)^f(x) onto |x>.
• Hadamard the input register and measure it.

The read-out rule

If all n input qubits measure 0, the function is constant. Any other pattern means balanced. The interference from the final Hadamards routes all amplitude to |0..0> exactly when f is constant.

import numpy as np
from itertools import product
n=3
def dj(f):
    N=2**n; psi=np.ones(N)/np.sqrt(N)
    for x in range(N): psi[x]*=(-1)**f(x)   # phase oracle
    H=np.array([[1,1],[1,-1]])/np.sqrt(2)
    Hn=np.array([1])
    for _ in range(n): Hn=np.kron(Hn,H)
    return np.round((Hn@psi)**2,3)
print(dj(lambda x:0)[0])          # 1.0 -> constant
print(dj(lambda x:bin(x).count('1')%2)[0])  # 0.0 -> balanced

Perspective

Deutsch-Jozsa is contrived - the promise is strong and the problem has no practical use - but it was the first clean proof that a quantum algorithm can beat every classical one on query count, and it introduced phase kickback and interference as computational tools.