Deutsch–Jozsa Algorithm

The Deutsch–Jozsa problem asks whether a promised Boolean function is constant or balanced. Given a complete coherent XOR-oracle interface, the modern circuit answers exactly with one quantum query by converting the function values into signs and testing the zero-frequency Walsh coefficient. The result is a particularly clean demonstration of phase kickback and interference.

Its complexity lesson requires care. One exact quantum query replaces $2^{n-1}+1$ exact deterministic classical queries, but a bounded-error randomized classical algorithm needs only two queries. The exponential separation is therefore an exact-query result for a deliberately structured black-box promise—not a practical speedup, a runtime theorem, or a separation between BQP and BPP.

Historically, Deutsch and Jozsa’s 1992 formulation used two calls to the function-controlled-NOT operation. The exact one-query network developed here is the 1998 refinement by Cleve, Ekert, Macchiavello, and Mosca.

Required background. Quantum Oracles supplies the complete oracle action, promise and capability distinctions, and construction boundary. Phase Kickback supplies the general XOR-to-phase identity, target-return condition, and phase-sensitive interpretation instantiated here.

Helpful background. Algorithmic Primitives supplies the access–phase–interference–readout pattern. Query Complexity fixes the deterministic, randomized, exact, zero-error, and bounded-error query conventions used below.

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.

The Ten-Field Deutsch–Jozsa Claim Record

Use the chapter’s common algorithm record before interpreting the one-query result. Every field receives a value or a justified N/A; a cost hidden by the oracle model is unspecified, not zero.

1. Problem family and size. The family is $\mathrm{DJ}_n$ for $n\ge1$, with address length $n$ and truth-table size $N=2^n$.
2. Promise and instance. The supplied Boolean function is constant or has exactly $N/2$ zero values and $N/2$ one values; a finite audit must also state its truth-table order.
3. Access and encoding. One query is the complete unitary $O_f|x,b\rangle=|x,b\mathbin\oplus f(x)\rangle$ on an $n$-qubit data register and a one-qubit answer register. Oracle construction and hidden workspace are outside this unit.
4. Output and use. Measuring $0^n$ means constant; every nonzero data word means balanced. The output is one promise-class bit, not the truth table or a balanced function’s hidden description.
5. Success and error. The ideal quantum procedure is exact on every promised instance. Off-promise behavior and noisy finite-shot inference are different contracts.
6. Algorithmic idea. Prepare a uniform query state, imprint $(-1)^{f(x)}$ through a minus-state answer qubit, and use Walsh–Hadamard interference to test whether the mean sign vanishes.
7. Executable procedure. Prepare $|0^n\rangle|1\rangle$, apply $H^{\otimes(n+1)}$, call $O_f$ once, apply $H^{\otimes n}$ to the data register, measure those $n$ qubits, and apply the zero-word decision rule.
8. Resource ledger. Count one abstract XOR query, $n+1$ visible logical qubits plus oracle workspace, $2n+1$ Hadamards when $|1\rangle$ is supplied, and one $n$-bit measurement. Add one $X$ when starting from $|0^{n+1}\rangle$.
9. Classical comparator. Under matched truth-table queries, $D=R_0=N/2+1$ for exact computation, whereas the fixed-cap two-sided value is $R_{1/3}=2$.
10. Evidence and limits. The circuit and query counts are exact black-box theorems. They do not price oracle construction, gates inside the oracle, memory, noise, fault tolerance, or wall-clock time and do not prove a useful application or BQP $\ne$ BPP.

The remaining sections derive every entry and expose the qualifications that the compact record suppresses.

The Modern One-Query Circuit

Let $X$ denote the $n$-qubit data register and $B$ the one-qubit answer register, in tensor order $X\otimes B$. The complete Boolean XOR oracle is

$$O_f|x,b\rangle = |x,b\mathbin\oplus f(x)\rangle, \qquad x\in\{0,1\}^n, \quad b\in\{0,1\}.$$

It is a permutation unitary and satisfies $O_f^\dagger=O_f$. That involution is a mathematical property of this interface; it does not imply that an arbitrary physical implementation is free, elementary, or supplied with additional controlled capabilities.

Starting from $|0^n\rangle|1\rangle$, the modern schedule is

$$|0^n\rangle|1\rangle \xrightarrow{H^{\otimes(n+1)}} \frac1{\sqrt N}\sum_x|x\rangle|{-}\rangle \xrightarrow{O_f} \frac1{\sqrt N}\sum_x(-1)^{f(x)}|x\rangle|{-}\rangle \xrightarrow{H^{\otimes n}\otimes I} \sum_y A_f(y)|y\rangle|{-}\rangle.$$

Only the data register is measured. The complete schedule contains one call to $O_f$, irrespective of the number of coherent basis labels in the superposition.

The modern Deutsch–Jozsa network uses one complete XOR-oracle call. The answer qubit returns in $|{-}\rangle$ while the data register acquires the relative signs $(-1)^{f(x)}$; the final Hadamards test whether their zero-frequency Walsh coefficient vanishes.

A direct phase oracle $P_f|x\rangle=(-1)^{f(x)}|x\rangle$ would give a shorter-looking circuit, but it is a different declared interface. Here the phase action is derived from one call to the complete bit oracle and an explicitly prepared answer state.

Phase Kickback and the Oracle State

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 Correctness

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 under the fixed-cap conventions of the query-complexity owner,

$$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.

The Deterministic Classical Query 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) =R_0(\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 Classical Comparator

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.

Resources and Implementation Boundaries

The one-query statement occupies one coordinate in a larger resource ledger:

Resource	Ideal modern circuit
Boolean XOR-oracle calls	$1$
visible logical qubits	$n+1$
hidden oracle workspace	unspecified
Hadamard gates	$2n+1$ if $
additional preparation from $	0^{n+1}\rangle$
data measurements	one $n$-bit computational-basis measurement
ideal repetitions	$1$
oracle gates, width, depth, and cleanup	unspecified
routing, fault tolerance, and physical spacetime	unspecified
calibration, noise, and wall-clock cost	unspecified

The two Hadamard layers are parallel across their registers, but total circuit depth includes the oracle depth and the preparation, interference, and readout layers. If an implementation of $O_f$ has gate count $G_f$, depth $d_f$, and workspace $w_f$, calling it one query does not replace those values by one. An arbitrary $N$-entry truth table may itself require resources exponential in $n$ to store or synthesize.

Likewise, a query on a superposition is not $N$ readable classical evaluations. The circuit returns one class bit under a promise; it neither prints the truth table nor identifies an arbitrary balanced function. A device experiment with a small, transparently compiled instance can test preparation, phase control, interference, and readout while remaining silent about asymptotic total cost.

Classical Information Review owns the comparison once representation, memory construction, output utility, accuracy, and total cost beyond queries are included. Claims, Hype, and Evidence Standards owns the language needed to distinguish an ideal theorem, a finite simulation, a device demonstration, and an end-to-end advantage claim.

Two Worked Claim Audits

Exhaustive three-bit promise and spectrum audit

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$.

1. Problem family and size. This is the $n=3$ member with $N=8$ truth-table entries and $72$ legal functions.
2. Promise and instance. The exhaustive set contains two constants and seventy weight-four functions; the displayed instance is 00010111 in lexicographic address order.
3. Access and encoding. The register order is three data qubits followed by one answer qubit, and one complete XOR-oracle call implements the displayed truth table abstractly.
4. Output and use. The audit checks only the constant-versus-balanced bit. It also records the entire ideal data distribution to test the stronger state calculation.
5. Success and error. Every constant has zero-word probability one and every balanced function has zero-word probability zero; the analytic decision error is zero.
6. Algorithmic idea. The integer Walsh transform checks cancellation at zero frequency while retaining the nonzero spectrum needed to diagnose the common fixed-output misconception.
7. Executable procedure. Enumerate masks $0$ through $255$, retain weights $0$, $4$, and $8$, compute all eight signed character sums, divide by eight, and verify norm and zero-word probability.
8. Resource ledger. The ideal circuit uses four visible qubits, one query, seven Hadamards, and one three-bit register readout measuring three qubits; an all-zero initialization adds one $X$. Oracle synthesis remains unspecified.
9. Classical comparator. At $N=8$, exact deterministic classification needs five worst-case truth-table queries; this exhaustive software check is verification evidence, not that comparator algorithm.
10. Evidence and limits. Node.js v26.4.0 integer enumeration reports $72$ promised functions, zero failed norm or decision assertions, and the exact vector above. There is no floating-point or sampling uncertainty.

A compact reproduction of the integer check is:

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 });

Eight-input matched-query comparator audit

For the same $N=8$ family, the exact quantum and classical values are

$$Q_E=1, \qquad D=R_0=5, \qquad R_{1/3}=2.$$

The exact fixed-cap minimax sequence is:

cap $q$	balanced all-equal probability $p_{8,q}$	constant decision probability $a_{8,q}$	worst-case error $e^*_{8,q}$
$0$	N/A	$1/2$	$1/2$
$1$	$1$	$1/2$	$1/2$
$2$	$3/7$	$7/10$	$3/10$
$3$	$1/7$	$7/8$	$1/8$
$4$	$1/35$	$35/36$	$1/36$
$5$	$0$	$1$	$0$

1. Problem family and size. The comparison concerns $\mathrm{DJ}_3$ with address length three and truth-table size eight.
2. Promise and instance. Worst-case success is required over both constant functions and all seventy balanced functions; no input distribution defines the final guarantee.
3. Access and encoding. Both models receive matched unit-cost value queries to the same Boolean truth table. The quantum interface is coherent XOR access; the classical interface returns the queried bit.
4. Output and use. Each model returns only constant or balanced, not a witness, table, or nonzero Walsh label.
5. Success and error. The quantum result is exact. The randomized comparator has a fixed worst-case cap and two-sided error at most $1/3$ on every promised function.
6. Algorithmic idea. Quantum interference tests the signed mean in one call; the randomized algorithm samples distinct positions and randomizes its decision on the ambiguous all-equal transcript.
7. Executable procedure. For $q=2$, choose two distinct addresses uniformly. Return balanced after unequal answers; after equal answers, return constant with probability $7/10$.
8. Resource ledger. The comparison counts only oracle calls: one coherent quantum query versus two classical value queries. It excludes both implementations, nonquery work, memory, noise, and time.
9. Classical comparator. A constant instance succeeds with probability $7/10$. A balanced instance is all equal with probability $3/7$, so its error is $(3/7)(7/10)=3/10$ and its success is also $7/10$.
10. Evidence and limits. A single queried bit has the same uniform marginal under an equal mixture of the two constants and the uniform balanced family, so one query has average success at most $1/2$ and cannot meet the worst-case target. The factor-two bounded-error query gap is not exponential.

The $N=8$ audit deliberately reports both error regimes. Quoting only $1$ versus $5$ would hide the efficient randomized comparator; quoting only $1$ versus $2$ would hide the exact-query theorem the algorithm was designed to illustrate.

Historical Formulations and Canonical Ownership

The familiar circuit is the result of a sequence of refinements. Deutsch’s 1985 one-bit problem introduced a quantum interference procedure whose outcome could be inconclusive with probability $1/2$. Deutsch and Jozsa generalized the task in 1992 to the constant-versus-balanced promise and obtained an exact quantum advantage, but their network used two calls to the function-controlled-NOT operation. Cleve, Ekert, Macchiavello, and Mosca gave the now-standard exact one-query reconstruction in 1998. The one-call schedule on this page should therefore not be attributed verbatim to the 1992 circuit.

The algorithm also sits at several precise ownership seams. Quantum Oracles owns the interface, extensions, and hidden construction assumptions; Phase Kickback owns the general phase-transduction theorem; Algorithmic Primitives owns the reusable composition pattern; and Query Complexity owns the general measures and lower-bound methods. This page owns their particular composition for the Deutsch–Jozsa promise.

For the affine subfamily

$$f_{a,b}(x)=a\cdot x\mathbin\oplus b,$$

the same Walsh calculation gives

$$A_{f_{a,b}}(y)=(-1)^b\delta_{y,a}.$$

The network then returns the hidden word $a$ exactly. Deutsch–Jozsa asks only whether $a=0$ on this restricted family; a general balanced function need not be affine. Bernstein–Vazirani Algorithm owns the hidden-word problem, specialized character proof, and matched one-versus-$n$ query comparison.

Simon’s Algorithm instead owns a many-bit value-oracle hidden XOR-period promise, repeated orthogonal-subspace samples, binary-rank recovery and verification, and the matched exponential query separation; it is not a one-shot corollary of Deutsch–Jozsa. Formal class claims, relativization, and the distinction between black-box evidence and BQP versus BPP belong to Quantum Complexity Classes.

Common Deutsch–Jozsa Failures

Omitting the promise. The zero-word decision is exact only for constant and exactly balanced functions. Off-promise inputs follow the weight-dependent probability law and are not classified by the theorem.

Confusing $n$ with $N$. The address has $n$ bits, while the truth table has $N=2^n$ entries. The deterministic exact bound is exponential in $n$ but linear in $N$.

Using the wrong normalization. The final amplitude has a factor $1/N$, and $x\cdot y$ is a mod-two inner product. A factor $1/\sqrt N$ or an ordinary integer dot product gives the wrong state.

Assigning one balanced output. Only $0^n$ is forbidden for every balanced instance. The remaining probability distribution depends on the full Walsh spectrum.

Treating the two constants as distinguishable. Constant zero and constant one produce states that differ by one global sign. The measurement correctly assigns both to the same class.

Calling superposition bulk readout. One oracle call changes a joint amplitude pattern; one measurement does not expose $N$ function values.

Suppressing the randomized comparator. The exponential query separation is exact/deterministic. With error $1/3$, the matched randomized classical complexity is two.

Calling one query one unit of runtime. Oracle construction, nonquery gates, workspace, memory, compilation, noise, readout, and physical time remain separate resources.

Overstating the history or consequence. The modern one-query network is a 1998 refinement. It proves neither universal necessity of entanglement, practical advantage, nor BQP $\ne$ BPP.

Exercises

1. 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.

2. 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.

3. 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.$$

4. 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.

5. 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 this count when zero error is required, so $R_0=D$.

6. 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$.

7. 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.

8. Complete a ten-field implementation audit

Audit the $N=8$ modern circuit and repair the sentence “one quantum query means the algorithm runs in constant time.” Use every field in the chapter’s claim record.

Solution

1. Problem family and size. The task is $\mathrm{DJ}_3$, with three address bits and eight truth-table entries.
2. Promise and instance. The oracle is promised constant or balanced; choose 00010111 as the finite balanced instance and state lexicographic address order.
3. Access and encoding. One licensed query is the complete four-qubit XOR action $O_f|x,b\rangle=|x,b\oplus f(x)\rangle$. Its internal implementation and workspace are not supplied.
4. Output and use. The three measured data bits are reduced to constant when they equal 000 and balanced otherwise. They are not a dump of eight function values.
5. Success and error. The ideal promise algorithm succeeds with probability one. Noise, finite-shot inference, and off-promise classification are outside that statement.
6. Algorithmic idea. A minus-state target converts one coherent evaluation into the sign pattern $(-1)^{f(x)}$, and a Walsh transform tests the signed mean.
7. Executable procedure. From $|000\rangle|1\rangle$, apply four initial Hadamards, one $O_f$, three final Hadamards on the data, measure the data once, and use the zero-word rule.
8. Resource ledger. Count one abstract query, four visible qubits plus hidden workspace, seven Hadamards, three measured bits, and no ideal retry. From $|0000\rangle$, add one $X$. Oracle gates and depth, memory, routing, correction, and time are unspecified.
9. Classical comparator. The matched exact deterministic cost is five queries; the matched fixed-cap error-$1/3$ randomized cost is two. The exponential phrasing applies only to the exact family as $n$ grows.
10. Evidence and limits. The state and counts are exact ideal calculations, with the finite spectrum independently enumerated. They establish neither a constant-time implementation, a gate/runtime advantage, a practical application, nor BQP $\ne$ BPP.

A defensible repair is: “Given unit-cost coherent XOR-oracle access to a promised constant-or-balanced Boolean function on $n$-bit addresses, the modern Deutsch–Jozsa circuit returns the correct class with one exact quantum query; exact deterministic classical decision trees require $2^{n-1}+1$ matched value queries, while bounded-error randomized trees require two. Oracle construction and all nonquery implementation costs are excluded.”

References

• E. Bernstein and U. Vazirani, “Quantum Complexity Theory,” SIAM Journal on Computing 26, 1411–1473 (1997), doi:10.1137/S0097539796300921.
• 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. Collins, K. W. Kim, and W. C. Holton, “Deutsch–Jozsa Algorithm as a Test of Quantum Computation,” Physical Review A 58, R1633–R1636 (1998), doi:10.1103/PhysRevA.58.R1633.
• 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.
• S. Gulde, M. Riebe, G. P. T. Lancaster, C. Becher, J. Eschner, H. Häffner, F. Schmidt-Kaler, I. L. Chuang, and R. Blatt, “Implementation of the Deutsch–Jozsa Algorithm on an Ion-Trap Quantum Computer,” Nature 421, 48–50 (2003), doi:10.1038/nature01336.
• N. Johansson and J.-Å. Larsson, “Efficient Classical Simulation of the Deutsch–Jozsa and Simon’s Algorithms,” Quantum Information Processing 16, Article 233 (2017), doi:10.1007/s11128-017-1679-7.
• A. Montanaro, “Quantum Algorithms: An Overview,” npj Quantum Information 2, 15023 (2016), doi:10.1038/npjqi.2015.23.
• M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information, 10th Anniversary Edition, Cambridge University Press (2010), doi:10.1017/CBO9780511976667.
• D. R. Simon, “On the Power of Quantum Computation,” SIAM Journal on Computing 26, 1474–1483 (1997), doi:10.1137/S0097539796298637.