Deutsch–Jozsa Algorithm

The Deutsch–Jozsa algorithm decides whether a promised Boolean function is constant or balanced. One coherent oracle call turns its values into relative signs; interference then tests whether their average vanishes. It is a useful first example because the entire correctness proof can be followed through the amplitudes.

The comparison depends on the required accuracy. One exact quantum query replaces $2^{n-1}+1$ exact deterministic classical queries, but two randomized classical queries already suffice if error $1/3$ is allowed. This is a statement about oracle calls, with oracle construction and gate costs separate.

Helpful background. Quantum oracles defines a reversible Boolean query. Phase kickback explains why a minus-state answer qubit converts a bit flip into a phase. Query complexity compares fixed query caps and error requirements.

The constant-or-balanced promise

Fix $n\ge 1$, write $N=2^n$, and let

$$f:\{0,1\}^n\longrightarrow\{0,1\}.$$

The legal functions belong to one of two disjoint classes:

$$\begin{aligned} \text{constant:}\quad &|f^{-1}(1)|\in\{0,N\},\\ \text{balanced:}\quad &|f^{-1}(1)|=\frac N2. \end{aligned}$$

Equivalently, regard the truth table as an $N$-bit string. Its promised Hamming weight is $0$, $N/2$, or $N$, and the required output is the class label constant or balanced. There are

$$2+\binom{N}{N/2}$$

legal functions: two constant truth tables and $\binom{N}{N/2}$ balanced ones.

This is a promise on which oracle has been supplied, not a guarantee the circuit verifies. An arbitrary off-promise function need not receive a meaningful class label. The input-size conventions also matter: the address length is $n$, while the truth table contains $N=2^n$ values.

One oracle call and two Hadamard layers

The data register has $n$ qubits and the answer register has one. In that tensor order, the supplied query is

$$O_f|x,b\rangle=|x,b\oplus f(x)\rangle.$$

It is defined on every basis state and satisfies $O_f^2=I$. Starting with $|0^n\rangle|1\rangle$, apply Hadamards to all qubits, call $O_f$, and apply Hadamards to the data alone:

$$\begin{aligned} |0^n\rangle|1\rangle &\longmapsto \frac1{\sqrt N}\sum_x|x\rangle|{-}\rangle\\ &\longmapsto \frac1{\sqrt N}\sum_x(-1)^{f(x)}|x\rangle|{-}\rangle\\ &\longmapsto \sum_y A_f(y)|y\rangle|{-}\rangle. \end{aligned}$$

Measure the data. Return constant for $y=0^n$ and balanced otherwise. The sum over $N$ addresses still contains only one invocation of $O_f$.

The answer qubit returns to $|{-}\rangle$ after the oracle, while the data acquires relative phases $(-1)^{f(x)}$. The final Hadamards turn their mean into the amplitude of $0^n$. Here $M$ denotes computational-basis measurement.

Why the answer qubit returns

The answer state

$$|{-}\rangle = \frac{|0\rangle-|1\rangle}{\sqrt2}$$

is a $-1$ eigenstate of the bit flip $X$. Applying the oracle to one data basis state gives

$$\begin{aligned} O_f|x\rangle|{-}\rangle &= \frac{|x,f(x)\rangle-|x,1\mathbin\oplus f(x)\rangle}{\sqrt2}\\ &= (-1)^{f(x)}|x\rangle|{-}\rangle. \end{aligned}$$

Linearity then gives the post-query state

$$|\psi_f\rangle_X|{-}\rangle_B, \qquad |\psi_f\rangle_X = \frac1{\sqrt N}\sum_x(-1)^{f(x)}|x\rangle.$$

The answer register returns exactly, carries no residual function value, and factors from the data. What remains is a relative-phase pattern. This is not a readable list of all $N$ values: measuring $X$ immediately would still return only one uniformly distributed address.

Complementing the function multiplies the entire data state by $-1$:

$$|\psi_{f\mathbin\oplus1}\rangle=-|\psi_f\rangle.$$

That global sign is unobservable. The two constant functions must therefore lead to the same class decision, as the promise requires.

Walsh–Hadamard interference

For bit strings $x,y\in\{0,1\}^n$, define the mod-two inner product

$$x\cdot y = \bigoplus_{j=1}^n x_jy_j.$$

The $n$-qubit Hadamard transform acts as

$$H^{\otimes n}|x\rangle = \frac1{\sqrt N} \sum_y(-1)^{x\cdot y}|y\rangle.$$

Applying it to the oracle state produces the normalized Walsh coefficients

$$A_f(y) = \frac1N \sum_{x\in\{0,1\}^n} (-1)^{f(x)+x\cdot y}, \qquad \Pr(Y=y)=|A_f(y)|^2.$$

The factor is $1/N$, not $1/\sqrt N$: one factor of $1/\sqrt N$ comes from the uniform query state and the other from the final Hadamard transform.

Character orthogonality verifies normalization. Expanding the squared amplitudes gives

$$\begin{aligned} \sum_y|A_f(y)|^2 &= \frac1{N^2} \sum_{x,x'}(-1)^{f(x)+f(x')} \sum_y(-1)^{(x\mathbin\oplus x')\cdot y}\\ &= \frac1{N^2} \sum_{x,x'}(-1)^{f(x)+f(x')} N\,\delta_{x,x'}\\ &=1. \end{aligned}$$

The algorithm uses only $A_f(0^n)$, but the other coefficients explain the nonzero outcomes. A generic balanced function can distribute probability over several Walsh labels; balance alone does not encode a unique hidden word.

Exact classification and off-promise inputs

At the zero word, the character factor is one, so

$$\begin{aligned} A_f(0^n) &= \frac1N\sum_x(-1)^{f(x)}\\ &= \frac{\#\{x:f(x)=0\}-\#\{x:f(x)=1\}}N. \end{aligned}$$

If $f=0$ everywhere, then $A_f(0^n)=1$ and the final data state is $|0^n\rangle$. If $f=1$ everywhere, then $A_f(0^n)=-1$ and the state is $-|0^n\rangle$. In either constant case, measurement returns $0^n$ with certainty. If $f$ is balanced, the two cardinalities are equal, $A_f(0^n)=0$, and that outcome is impossible. Therefore

$$Y=0^n\Longleftrightarrow f\text{ is constant}$$

on the promise, with any $Y\ne0^n$ certifying balance.

Both promise classes are nonempty, so an ordinary zero-query procedure has no information about the label and cannot achieve worst-case success greater than $1/2$. Under the site’s zero-error convention, a never-wrong zero-query procedure cannot emit either class label, because the same output distribution must serve inputs from both classes. It must therefore report ? with probability one, exceeding the allowed inconclusive probability $1/2$. The one-query circuit is exact, so with the fixed query caps defined in query complexity,

$$Q_E(\mathrm{DJ}_n) =Q_0(\mathrm{DJ}_n) =Q_\varepsilon(\mathrm{DJ}_n) =1, \qquad 0\le\varepsilon<\frac12.$$

Outside the promise, if $w=|f^{-1}(1)|$, then

$$\Pr(Y=0^n) = \left(1-\frac{2w}{N}\right)^2.$$

This formula describes the circuit’s response to an off-promise truth table. It does not make one shot a test of arbitrary Hamming weight, and it does not certify that the supplier respected the promise.

Classical queries: exact answers versus bounded error

The deterministic exact bound

A deterministic exact algorithm queries distinct truth-table entries. It stops and returns balanced as soon as two different values have appeared. If the first $N/2+1$ answers are identical, the function cannot be balanced, so it returns constant. This gives the upper bound $N/2+1$.

The bound is necessary. After any transcript containing at most $N/2$ identical answers, two legal completions remain possible: the queried value can fill the entire table, producing a constant function, or exactly $N/2$ entries can take that value while the unqueried positions supply the opposite value, producing a balanced function. No deterministic decision tree can label both completions correctly from that transcript. Consequently,

$$D(\mathrm{DJ}_n) =\frac N2+1 =2^{n-1}+1.$$

This is exponential in the address length $n$ and linear in the truth-table size $N$. It is an exact-query theorem. The phrase “classical algorithms require exponentially many queries” is misleading unless the deterministic or zero-error requirement is stated.

The randomized comparison

Bounded error changes the picture. For a fixed cap $1\le q\le N$, query $q$ distinct uniformly random addresses. A mixed transcript proves the function balanced. For a balanced function, the probability of an all-equal transcript is

$$p_{N,q} = 2\frac{\binom{N/2}{q}}{\binom Nq},$$

where $\binom{N/2}{q}=0$ when $q>N/2$. On an all-equal transcript, return constant with probability

$$a_{N,q} = \frac1{1+p_{N,q}}.$$

A constant instance then has error $1-a_{N,q}$, while a balanced instance has error $a_{N,q}p_{N,q}$. The choice of $a_{N,q}$ equalizes them:

$$e^*_{N,q} = \frac{p_{N,q}}{1+p_{N,q}}, \qquad e^*_{N,0}=\frac12.$$

This risk is minimax optimal. Average any candidate algorithm over permutations of the $N$ addresses and over complementation of every truth-table bit. Symmetrization cannot increase its worst-case error. Repeated addresses add no information, and after $q$ distinct queries the symmetrized transcript is either mixed, which identifies balance, or all equal, which is compatible with both classes. The only remaining decision probability is $a$; minimizing $\max\{1-a,ap_{N,q}\}$ gives the value above.

For one query, $p_{N,1}=1$ and $e^*_{N,1}=1/2$. For two,

$$p_{N,2}=\frac{N-2}{2(N-1)}, \qquad e^*_{N,2}=\frac{N-2}{3N-4}<\frac13$$

for every $N\ge2$. Hence

$$R_{1/3}(\mathrm{DJ}_n)=2.$$

The honest comparison is now visible: exact quantum versus exact deterministic queries separates $1$ from $2^{n-1}+1$, whereas bounded-error quantum versus bounded-error randomized queries separates $1$ from $2$. The latter has no asymptotic query advantage.

For $N=8$, the following values show how a small allowed error changes the query count. At $q=0$ there is no observed transcript; guessing the class with a fair coin has error $1/2$.

Query cap $q$	Balanced all-equal probability $p_{8,q}$	Optimal worst-case error
$0$	No queries	$1/2$
$1$	$1$	$1/2$
$2$	$3/7$	$3/10$
$3$	$1/7$	$1/8$
$4$	$1/35$	$1/36$
$5$	$0$	$0$

For example, query two distinct uniform addresses. Unequal answers establish balance. After equal answers, return constant with probability $7/10$. A constant function has error $3/10$; a balanced function has error $(3/7)(7/10)=3/10$.

A nonlinear balanced example

Take $n=3$, $N=8$, and order truth-table positions as 000, 001, 010, 011, 100, 101, 110, 111. Enumerating all $2+\binom84=72$ promised functions verifies the exact decision criterion. A concrete nonlinear balanced instance is majority on three bits,

$$f(x)=1\quad\Longleftrightarrow\quad |x|\ge2,$$

with truth-table word 00010111. Its unnormalized Walsh vector, ordered by $y=000,001,\ldots,111$, is

$$W_f=(0,4,4,0,4,0,0,-4).$$

Because $A_f=W_f/8$, the final data state is

$$\frac{|001\rangle+|010\rangle+|100\rangle-|111\rangle}{2}.$$

Each displayed word has probability $1/4$, and $000$ has probability zero. The two constant functions instead give $|000\rangle$ and $-|000\rangle$.

The following integer calculation checks the complete three-bit promise and its Walsh normalization. Bit $x$ of mask stores the value at address $x$, so the majority truth table is hexadecimal 0xe8 in this encoding.

const N = 8;
const parity = (z) => {
  let p = 0;
  while (z) { p ^= z & 1; z >>= 1; }
  return p;
};

let promised = 0;
let majorityWalsh;
for (let mask = 0; mask < 256; mask++) {
  const f = (x) => (mask >> x) & 1;
  const weight = Array.from({ length: N }, (_, x) => f(x))
    .reduce((a, b) => a + b, 0);
  if (![0, 4, 8].includes(weight)) continue;
  promised++;
  const W = Array.from({ length: N }, (_, y) =>
    Array.from({ length: N }, (_, x) =>
      (f(x) ^ parity(x & y)) ? -1 : 1)
      .reduce((a, b) => a + b, 0));
  if (W.reduce((a, v) => a + v * v, 0) !== N * N) throw Error('norm');
  if ((weight === 4) !== (W[0] === 0)) throw Error('decision');
  if (mask === 0xe8) majorityWalsh = W;
}
if (promised !== 72) throw Error('promise count');
if (majorityWalsh.join(',') !== '0,4,4,0,4,0,0,-4') throw Error('spectrum');
console.log({ promised, majorityWalsh });

Gates, history and related problems

With the initial answer $|1\rangle$ supplied, the circuit uses $n+1$ visible qubits, $2n+1$ Hadamards, one oracle call and one measurement of the data register. Starting all qubits in zero adds an $X$ on the answer. Any workspace inside the oracle must also be counted. The Hadamards can run in parallel within each layer, but total depth includes the oracle, preparation and readout.

An arbitrary truth table has $2^n$ entries, so constructing its reversible circuit may be expensive. A compiled small example can demonstrate phase control and interference without establishing an asymptotic runtime advantage. Nor does the measurement reveal all the truth-table entries: it gives one promised class label.

Deutsch’s original 1985 one-bit procedure could be inconclusive with probability $1/2$. Deutsch and Jozsa’s 1992 generalization used two function-controlled-NOT calls. The exact one-query circuit above is the refinement by Cleve, Ekert, Macchiavello and Mosca, published in 1998 (preprint 1997).

For the affine functions $f_{a,b}(x)=a\cdot x\oplus b$, the same calculation gives $A_f(y)=(-1)^b\delta_{y,a}$. Recovering the hidden word $a$ is the Bernstein–Vazirani problem. Balance alone does not imply this affine form. Simon’s algorithm instead uses a many-bit value oracle and repeated samples to find a hidden XOR period. Statements about BQP and BPP require the definitions in quantum complexity classes, beyond this fixed promise problem.

Exercises

Count the promised oracle family

For $N=2^n$, count the constant and balanced Boolean truth tables. Explain why this count describes a promise on the selected oracle rather than a restriction on the states the algorithm may query.

Solution

There are two constant truth tables, all zero and all one. A balanced truth table is specified by choosing the $N/2$ positions assigned one, giving $\binom{N}{N/2}$ choices. Thus the promised family has

$$2+\binom{N}{N/2}$$

members. The supplier chooses one unitary $O_f$ from this family. Once chosen, the complete XOR map acts on every computational-basis state $|x,b\rangle$ and hence on every superposition by linearity; the promise does not confine the query state to a smaller subspace.

Verify Boolean phase kickback

Apply $O_f$ to $|x\rangle|{-}\rangle$. Prove target return and factorization for a general data superposition, then determine the effect of replacing $f$ by $f\mathbin\oplus1$.

Solution

For a basis state,

$$O_f|x\rangle|{-}\rangle = \frac{|x,f(x)\rangle-|x,1\mathbin\oplus f(x)\rangle}{\sqrt2} = (-1)^{f(x)}|x\rangle|{-}\rangle.$$

Therefore

$$O_f\left(\sum_x\alpha_x|x\rangle\right)|{-}\rangle = \left(\sum_x\alpha_x(-1)^{f(x)}|x\rangle\right)|{-}\rangle.$$

The common answer state factors exactly. Complementing $f$ multiplies every data amplitude by $-1$, which is one global phase and cannot affect any measurement probability.

Derive the Walsh–Hadamard law

Starting from the post-query data state, derive $A_f(y)$, prove Parseval normalization with character orthogonality, and obtain the zero-word probability for a truth table of arbitrary weight $w$.

Solution

Insert

$$H^{\otimes n}|x\rangle = \frac1{\sqrt N}\sum_y(-1)^{x\cdot y}|y\rangle$$

into $N^{-1/2}\sum_x(-1)^{f(x)}|x\rangle$. Collecting the coefficient of $|y\rangle$ gives

$$A_f(y)=\frac1N\sum_x(-1)^{f(x)+x\cdot y}.$$

Since $\sum_y(-1)^{(x\oplus x')\cdot y}=N\delta_{x,x'}$, expanding $\sum_y|A_f(y)|^2$ leaves $N$ diagonal terms divided by $N$, hence one. At $y=0^n$, there are $N-w$ positive and $w$ negative contributions, so

$$A_f(0^n)=1-\frac{2w}{N}, \qquad \Pr(0^n)=\left(1-\frac{2w}{N}\right)^2.$$

Enumerate the three-bit promise

Reproduce the exhaustive $n=3$ check and compute the spectrum of the nonlinear balanced truth table 00010111. Why does this example refute the claim that every balanced function produces one deterministic nonzero word?

Solution

There are $2+\binom84=72$ promised masks. For each mask, compute

$$W_f(y)=\sum_{x=0}^{7}(-1)^{f(x)+x\cdot y}.$$

The two constant masks have $W_f(000)=\pm8$; all seventy balanced masks have $W_f(000)=0$. For 00010111, direct summation gives

$$W_f=(0,4,4,0,4,0,0,-4).$$

Dividing by eight gives amplitudes $1/2$ on $001$, $010$, and $100$, amplitude $-1/2$ on $111$, and zero elsewhere. Four different outcomes therefore occur with probability $1/4$ each. Balance forbids only the zero word; it does not determine the rest of the spectrum.

Prove the deterministic exact bound

Give an executable classical schedule using $N/2+1$ queries and an indistinguishable-transcript argument showing that no exact deterministic schedule can use fewer in the worst case.

Solution

Query distinct addresses until a mismatch occurs or $N/2+1$ identical values have been seen. A mismatch proves balance; more than half the table having one value proves constancy under the promise.

For the lower bound, consider any transcript of at most $N/2$ identical answers. It can be completed to a constant table, but it can also be completed to a balanced table by placing the opposite bit in exactly $N/2$ unqueried positions. Both completions follow the same decision-tree path, so no leaf at that depth can be correct on both. Thus

$$D(\mathrm{DJ}_n)=\frac N2+1.$$

Randomization cannot reduce the worst-case fixed cap if every run must return the correct class: an all-equal transcript of at most $N/2$ answers remains compatible with both classes.

Solve the randomized minimax problem

Derive $p_{N,q}$, $a_{N,q}$, and $e^*_{N,q}$. Evaluate them for $N=8$ and $q=0,1,\ldots,5$, then prove $R_{1/3}=2$ for every $n\ge1$.

Solution

For $q\ge1$ distinct uniform addresses, a balanced table gives all zeros with probability $\binom{N/2}{q}/\binom Nq$ and all ones with the same probability. Hence

$$p_{N,q}=2\frac{\binom{N/2}{q}}{\binom Nq}.$$

If $a$ is the probability of returning constant after an all-equal transcript, the two worst-case errors are $1-a$ for a constant and $ap_{N,q}$ for a balanced function. Equalizing them gives

$$a_{N,q}=\frac1{1+p_{N,q}}, \qquad e^*_{N,q}=\frac{p_{N,q}}{1+p_{N,q}}.$$

For $N=8$ and $q=0$ through $5$, the balanced all-equal probabilities are

$$\text{N/A},\quad 1,\quad \frac37,\quad \frac17,\quad \frac1{35},\quad 0;$$

the constant-decision probabilities are

$$\frac12,\quad \frac12,\quad \frac7{10},\quad \frac78,\quad \frac{35}{36},\quad 1;$$

and the minimax errors are

$$\frac12,\quad \frac12,\quad \frac3{10},\quad \frac18,\quad \frac1{36},\quad 0.$$

Symmetrization over addresses and bit complementation reduces any algorithm to these transcript classes, proving optimality. One query has error $1/2$, while two have error $(N-2)/(3N-4)<1/3$ for every $N\ge2$. Therefore $R_{1/3}=2$.

Separate affine structure from balance

For $f_{a,b}(x)=a\cdot x\mathbin\oplus b$, compute the entire Walsh spectrum. Explain why its deterministic output cannot be generalized to every balanced function.

Solution

Substitution gives

$$\begin{aligned} A_{f_{a,b}}(y) &= \frac{(-1)^b}{N} \sum_x(-1)^{x\cdot(a\oplus y)}\\ &= (-1)^b\delta_{y,a}. \end{aligned}$$

Thus measurement returns $a$ with certainty. When $a=0$, the function is constant; when $a\ne0$, it is balanced. For $n\ge3$, only $2(N-1)$ of the $\binom{N}{N/2}$ balanced truth tables are affine, so most can have support on several Walsh labels, as the majority example shows. (For $n=1,2$, every balanced truth table happens to be affine.) The hidden-word inference belongs to Bernstein–Vazirani, not to the general Deutsch–Jozsa promise.

Diagnose a noisy zero-word test

Suppose the ideal data output is measured after an additional channel which, with probability $\eta$, replaces the entire data state by $I/N$. Compute the error for each promised class. Does one observation still certify balance?

Solution

The replacement contributes probability $1/N$ to every word. For a constant function the zero-word probability becomes $(1-\eta)+\eta/N$, so its classification error is $\eta(1-1/N)$. For a balanced function the ideal zero-word probability vanishes, but replacement contributes $\eta/N$; this is its error. For $\eta>0$, neither outcome provides the ideal certainty. Repeated independent trials can estimate the probabilities, but interpreting them requires a specified noise model. This example assumes replacement of the whole data register, not independent depolarization of each qubit.

References

• R. Cleve, A. Ekert, C. Macchiavello, and M. Mosca, “Quantum Algorithms Revisited,” Proceedings of the Royal Society A 454, 339–354 (1998), doi:10.1098/rspa.1998.0164.
• D. Deutsch, “Quantum Theory, the Church–Turing Principle and the Universal Quantum Computer,” Proceedings of the Royal Society A 400, 97–117 (1985), doi:10.1098/rspa.1985.0070.
• D. Deutsch and R. Jozsa, “Rapid Solution of Problems by Quantum Computation,” Proceedings of the Royal Society A 439, 553–558 (1992), doi:10.1098/rspa.1992.0167.
• M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information, 10th Anniversary Edition, Cambridge University Press (2010), doi:10.1017/CBO9780511976667.