Parallelism, Deutsch and Deutsch–Jozsa

1 / 15 · Learn

Before you start

A measurement returns one bit per qubit (Lesson 1), and a relative phase becomes visible only after a gate such as $H$ makes the branches interfere (Lessons 4 and 5). This lesson puts both facts to work in the first quantum algorithms, with the phase kickback of Lessons 6 and 7 as the key step.

Part A: the oracle, quantum parallelism and Deutsch’s algorithm. Part B: $n$ input bits, the Deutsch–Jozsa algorithm, and how many queries each method needs.

By the end of this lesson you can:

apply $U_f\ket{x,y} = \ket{x, y\oplus f(x)}$ to basis states and to superpositions;
say what one measurement after a query on a superposition reveals, and what it doesn’t;
derive phase kickback and trace Deutsch’s algorithm for all four one-bit functions;
compute $H^{\otimes n}\ket x$ and the $\ket{0\ldots0}$ amplitude in Deutsch–Jozsa;
compare query counts: quantum, deterministic classical and randomized classical.

Check yourself

A warm-up: make a guess before reading on. The lesson comes back to it.

A quantum computer applies $U_f$ once to a superposition of all eight 3-bit inputs, producing $\tfrac{1}{\sqrt{8}}\sum_x\ket{x}\ket{f(x)}$ . Then every qubit is measured in the 0/1 basis. What does this one run tell you about $f$ ?

AAll eight values $f(x)$ : the whole table of $f$
BNothing: measuring a superposition gives meaningless random bits
COnly $f(000)$ , because the inputs started in $\ket{000}$
DThe value $f(x)$ at one input $x$ , chosen at random

Show the answer

Answer: D. The value $f(x)$ at one input $x$ , chosen at random

Each branch $\ket{x}\ket{f(x)}$ has amplitude $\tfrac{1}{\sqrt{8}}$ . The measurement picks one branch at random, with probability $1/8$ each, and returns its input and its value: one $f(x)$ per run, which is no more than one classical query gives.

Why not the others

A. The state involves all eight values, but a 0/1 measurement of 4 qubits returns 4 bits: one input $x$ and its value $f(x)$ . The other branches are gone once you have measured.
B. The bits are not meaningless. Every branch is $\ket{x}\ket{f(x)}$ , so in every result the last bit equals $f$ of the first ones: you learn one genuine value.
C. Every input has the same amplitude, $\tfrac{1}{\sqrt{8}}$ , so the measured $x$ is random: $000$ turns up only one time in 8.

Check yourself

A warm-up: make a guess before reading on. The lesson comes back to it.

A black box computes $f$ on 3-bit strings (eight inputs). You are promised that $f$ is either constant or balanced (0 on exactly 4 inputs and 1 on the other 4). Querying one input at a time, and needing to be certain, how many queries might you need in the worst case?

A $2$
B $3$
C $5$
D $8$

Show the answer

Answer: C. $5$

In the worst case the first 4 answers agree, which a balanced $f$ allows. Query number 5 decides: $2^{n-1} + 1 = 5$ for $n = 3$ .

Why not the others

A. Two queries settle it only if they disagree. If they agree, a balanced $f$ is still possible: 4 inputs share each value.
B. The count depends on the number of inputs, not on the number of bits in $x$ . A balanced $f$ can give the same value on any 4 inputs, so 4 agreeing answers prove nothing.
D. You never need all 8. A balanced $f$ has only 4 inputs of each value, so once 5 answers agree, $f$ must be constant.

2 / 15 · Learn

Part A · The oracle and quantum parallelism

Part A: the oracle, what a query on a superposition gives you, and Deutsch’s algorithm.

A function $f$ from one bit to one bit is either constant ( $f(0) = f(1)$ ) or balanced ( $f(0) \ne f(1)$ ). To use $f$ in a circuit you need a gate, and a gate that simply replaced $x$ by $f(x)$ fails for a constant $f$ : both inputs would land on one output, which no reversible gate allows. The fix is the Toffoli trick from Lesson 6: keep the input, and XOR the value into a second qubit,

U_f\ket{x, y} = \ket{x,\ y\oplus f(x)}.

Here $x$ is called the data register and $y$ the target. Applying $U_f$ twice gives back $y\oplus f(x)\oplus f(x) = y$ , so $U_f$ undoes itself: it only permutes the basis states.

Check yourself

For $f(x) = \bar x$ , so $f(0) = 1$ and $f(1) = 0$ , what is $U_f\ket{0, 1}$ ?

A $\ket{0, 0}$
B $\ket{1, 1}$
C $\ket{0, 1}$
D $\ket{1, 0}$

Show the answer

Answer: A. $\ket{0, 0}$

$f(0) = 1$ , so the target becomes $y\oplus f(x) = 1\oplus1 = 0$ , and the data qubit is untouched: $\ket{0, 0}$ . The truth table above shows the same row.

Why not the others

B. That replaces $x$ by $f(x)$ . On basis inputs $U_f$ never changes the data qubit; the value goes into the target, by XOR.
C. That writes $f(0) = 1$ into the target, replacing $y$ . $U_f$ adds it mod 2 instead: $y\oplus f(x) = 1\oplus1 = 0$ . Overwriting would erase $y$ , and $U_f$ could not be undone.
D. Only the target can change on a basis input. The data qubit stays $\ket0$ , and the target becomes $1\oplus f(0) = 0$ .

Now give $U_f$ a superposition. With the data qubit in $\ket+$ and the target in $\ket0$ , $U_f$ acts on each branch separately (linearity):

\begin{aligned}&U_f\Big(\tfrac{\ket0 + \ket1}{\sqrt2}\,\ket0\Big) \\ &\qquad = \tfrac{1}{\sqrt2}\big(\ket{0, f(0)} + \ket{1, f(1)}\big)\end{aligned}

One use of $U_f$ , and the state involves both $f(0)$ and $f(1)$ . With $n$ data qubits, each in $\ket+$ , there are $2^n$ branches, and one use of $U_f$ gives $\tfrac{1}{\sqrt{2^n}}\sum_x\ket{x, f(x)}$ . This is called quantum parallelism. Whether you can get the values out is the next question.

Check yourself

Let $f(x) = \bar x$ . Enter $U_f\big(\ket+\ket0\big)$ as four amplitudes, $\ket{00}$ to $\ket{11}$ (data qubit first).

Hints

Apply $U_f$ to each branch, $\ket{0,0}$ and $\ket{1,0}$ , separately.
$U_f\ket{x, 0} = \ket{x, f(x)}$ , with $f(0) = 1$ and $f(1) = 0$ .

Show the answer

Answer: $\frac{1}{\sqrt{2}}|01\rangle + \frac{1}{\sqrt{2}}|10\rangle$

Branch by branch: $U_f\ket{0,0} = \ket{0,1}$ and $U_f\ket{1,0} = \ket{1,0}$ . So the result is $(\ket{01} + \ket{10})/\sqrt2$ , which is the Bell state $\ket{\beta_{01}}$ : the data and the target are now entangled.

3 / 15 · Explore

Part A · What one run reveals

Predict, then see

Two data qubits, each in $\ket+$ , a target in $\ket0$ , and one use of $U_f$ give

\begin{aligned}\tfrac12\big(&\ket{00, f(00)} + \ket{01, f(01)} \\ + &\ket{10, f(10)} + \ket{11, f(11)}\big).\end{aligned}

You measure all three qubits in the 0/1 basis. Then you measure the same three qubits again, without preparing anything new. What do the two results show?

AAll four pairs at once; the second measurement adds nothing new
BTwo different pairs $(x, f(x))$ : each measurement reads out another branch
CTwo random 3-bit strings with no link to $f$
DThe same pair $(x, f(x))$ both times, with $x$ random

Why did the second measurement repeat the first, and what does it cost to see another pair $(x, f(x))$ ? A sentence or two is enough.

Show what happens

What happens: D. The same pair $(x, f(x))$ both times, with $x$ random

Each measurement returns one branch $\ket{x, f(x)}$ : a random $x$ (probability $\tfrac14$ each) with its correct value. Measuring again repeats it, because the measurement left the register in that basis state. Learning more needs fresh copies, each costing another use of $U_f$ : one value per query, as on a classical computer, except that you don’t get to choose $x$ .

Why not the others

A. Three qubits measured in the 0/1 basis give three bits: two for $x$ and one for $f(x)$ . The state involves all four values, but a measurement returns a single branch, picked at random.
B. With all four branches in the state, it seems a second look should find another one. But in the widget the second result repeated the first: one measurement keeps one branch and discards the rest.
C. The bits are not noise. In every result the last bit equals $f$ of the first two, because every branch is $\ket{x, f(x)}$ . Check any result in the widget against the values listed above it.

Why not just read off the amplitudes?

The circles show the amplitudes because this is a simulation. A real register offers no such readout. The only access is measurement, and a 0/1-basis measurement of three qubits returns three bits (Lesson 6). Estimating amplitudes from statistics takes many fresh copies, and so many uses of $U_f$ .

Check yourself

Three data qubits, each in $\ket+$ , and a target in $\ket0$ ; one use of $U_f$ ; then all four qubits are measured in the 0/1 basis. What is the probability that this run tells you $f(101)$ ?

$P = \;?$

Hints

What decides which value of $f$ the run shows?
The data register gives each of its eight strings with the same probability.

Show the answer

Answer: $P = \frac{1}{8}$

The data register gives each of the eight inputs with probability $\abs{1/\sqrt8}^2 = \tfrac18$ , and the target then shows $f(x)$ for that input. So $f(101)$ appears with probability $\tfrac18$ .

Common slips

$1$ : That assumes the run reveals every value. The measurement returns one branch $\ket{x}\ket{f(x)}$ , and $x = 101$ is one of eight equally likely inputs.
$\frac{1}{16}$ : That treats all four measured bits as random. Only the three data bits are: once $x$ is found, the target bit is $f(x)$ for certain. So the chance is that of finding $x = 101$ , which is $\tfrac18$ .
$\frac{1}{2}$ : Either you learn $f(101)$ or you don’t, but the two cases are not equally likely. You learn it only when the data register gives $101$ , one of eight equally likely results.

4 / 15 · Learn

Part A · Phase kickback

Change one thing: put the target in $\ket- = (\ket0 - \ket1)/\sqrt2$ . If $f(x) = 0$ , $U_f$ leaves $\ket x\ket-$ alone. If $f(x) = 1$ , it flips the target, and flipping swaps the two terms of $\ket-$ : $(\ket1 - \ket0)/\sqrt2 = -\ket-$ . Both cases in one line:

U_f\ket x\ket- = (-1)^{f(x)}\ket x\ket-

The target comes out unchanged, and the value $f(x)$ has become a sign on the data branch. On a basis state that sign is a global phase. On a superposition each branch gets its own sign, a relative phase. This is the phase kickback you met with CNOT in Lessons 6 and 7: CNOT is $U_f$ for $f(x) = x$ .

Check yourself

Let $f(x) = \bar x$ , so $f(0) = 1$ and $f(1) = 0$ . What is $U_f\ket+\ket-$ ?

A $-\ket-\ket-$
B $\ket+\ket-$ : the data qubit acts like a control, and controls don’t change
C $\ket+\ket+$ : the target flips
D $-\ket+\ket-$

Hints

Write $\ket+$ as two branches and apply $U_f$ to each.
A branch gains $-1$ exactly when $f(x) = 1$ .

Show the answer

Answer: A. $-\ket-\ket-$

Branch by branch: $f(0) = 1$ gives $-\ket0\ket-$ and $f(1) = 0$ gives $+\ket1\ket-$ . Together $\tfrac{1}{\sqrt2}(-\ket0 + \ket1)\ket- = -\ket-\ket-$ . The overall minus is a global phase; the relative sign between the branches is what turned $\ket+$ into $\ket-$ .

Why not the others

B. “The control never changes” holds only for basis inputs. Split $\ket+$ into its branches: the $\ket0$ branch has $f(0) = 1$ and picks up $-1$ , the $\ket1$ branch doesn’t. A minus sign on just one branch turns $\ket+$ into $\ket-$ (up to an overall sign).
C. Flipping $\ket-$ doesn’t give $\ket+$ : $X$ swaps the two terms of $(\ket0 - \ket1)/\sqrt2$ and so gives $-\ket-$ . The target keeps its state; the sign lands on the data branch.
D. That would need both branches to pick up $-1$ , which happens for $f(x) = 1$ . Here only the $x = 0$ branch has $f(x) = 1$ , so the two branches end with opposite signs.

5 / 15 · Learn

Part A · Deutsch’s algorithm

Deutsch’s problem: is a one-bit $f$ constant or balanced? A classical computer has to evaluate $f$ twice. Deutsch’s circuit uses $U_f$ once. Follow the state:

$\ket{\psi_0} = \ket0\ket1$ , the input;
$H$ on both qubits gives $\ket{\psi_1} = \ket+\ket-$ ;
$U_f$ then acts with kickback on each branch:

\ket{\psi_2} = \tfrac{1}{\sqrt2}\big((-1)^{f(0)}\ket0 + (-1)^{f(1)}\ket1\big)\ket-

Think of each input as carrying a chip, $+1$ or $-1$ . If $f$ is constant the two chips match, and the data qubit is $\pm\ket+$ . If $f$ is balanced they differ, and it is $\pm\ket-$ .

Check yourself

For which functions is the data qubit in $\ket-$ (up to an overall sign) right after $U_f$ ?

Select all that apply.

A $f(x) = \bar x$
B $f(x) = 0$
C $f(x) = 1$
D $f(x) = x$

Hints

Find the two chips $(-1)^{f(0)}$ and $(-1)^{f(1)}$ for each function.
Matching chips leave $\pm\ket+$ ; different chips give $\pm\ket-$ .

Show the answer

Answers: A. $f(x) = \bar x$ ; D. $f(x) = x$

The data qubit is $\pm\ket-$ exactly when the chips differ, that is when $f(0) \ne f(1)$ : the two balanced functions $f(x) = x$ (giving $\ket-$ ) and $f(x) = \bar x$ (giving $-\ket-$ ).

Why not the others

B. With $f(x) = 0$ both chips are $+1$ , so the data qubit stays $\ket+$ .
C. With $f(x) = 1$ both chips are $-1$ : the data qubit is $-\ket+$ . An overall sign is a global phase, so this is still $\ket+$ , not $\ket-$ .

6 / 15 · Learn

Part A · The last Hadamard

The last $H$ acts on the data qubit only. It turns $\ket+$ into $\ket0$ and $\ket-$ into $\ket1$ :

\ket{\psi_3} = \pm\ket{f(0)\oplus f(1)}\ket-

In chip terms, the data qubit’s $\ket0$ amplitude is the average of the two chips, and its $\ket1$ amplitude is half their difference. Matching chips add on $\ket0$ and cancel on $\ket1$ ; opposite chips do the reverse. So a 0/1-basis measurement of the top qubit gives $f(0)\oplus f(1)$ with certainty: 0 for constant, 1 for balanced. One query settles a question that no single classical evaluation can, and yet you learn neither $f(0)$ nor $f(1)$ .

Check yourself

Deutsch’s algorithm runs with $f(x) = \bar x$ . What does the 0/1-basis measurement of the top qubit give?

A1, with certainty
B0, with certainty
C $f(0)$ first; a second measurement then gives $f(1)$
D0 or 1, each with probability $\tfrac12$ : Hadamards randomize

Show the answer

Answer: A. 1, with certainty

The chips are $(-1)^1 = -1$ and $(-1)^0 = +1$ . They differ, so after $U_f$ the data qubit is $-\ket-$ , and the last $H$ makes it $-\ket1$ . The measurement gives $1 = f(0)\oplus f(1)$ : balanced.

Why not the others

B. 0 is the constant answer. Here $f(0) = 1$ and $f(1) = 0$ , so the chips are $-1$ and $+1$ : they cancel on $\ket0$ and add on $\ket1$ .
C. The circuit never makes $f(0)$ or $f(1)$ readable on its own. Kickback turns them into two signs, and the last $H$ combines the signs into the single bit $f(0)\oplus f(1)$ . Measuring again just repeats that bit.
D. A Hadamard can also undo randomness: $H\ket- = \ket1$ exactly. After the query the data qubit is $-\ket-$ , a definite state, and the last $H$ turns it into $-\ket1$ . Nothing is left to chance.

Check yourself

After Deutsch’s circuit someone measures the bottom (target) qubit in the 0/1 basis. What do they get?

A $f(0)\oplus f(1)$ , because $U_f$ writes into the target
B0 or 1 with probability $\tfrac12$ each, whatever $f$ is
C $f(0)$ , the value at the first input
D1, because the target started in $\ket1$

Show the answer

Answer: B. 0 or 1 with probability $\tfrac12$ each, whatever $f$ is

The target is $\ket-$ at the end for every $f$ , so its 0/1 measurement gives 0 or 1 with probability $\tfrac12$ each. The answer is in the top qubit.

Why not the others

A. With the target in $\ket-$ , $U_f$ only multiplies the target by $\pm1$ , so it stays $\ket-$ for every $f$ . A 0/1 measurement of $\ket-$ is a fair coin, with no information about $f$ .
C. No value of $f$ is stored in the target. It is $\ket-$ for every $f$ ; the effect of $f$ is a sign on the data branches.
D. The first $H$ turned the target’s $\ket1$ into $\ket-$ , and it stays $\ket-$ to the end. Measured in the 0/1 basis, $\ket-$ gives 0 or 1 with probability $\tfrac12$ each.

7 / 15 · Worked example

Part A · Worked example: all four functions

Enter states as four amplitudes, $\ket{00}$ to $\ket{11}$ , top qubit first. These steps want the exact vector, signs included, even where an overall sign would be a harmless global phase.

Worked example

The two balanced functions

Every run starts from the same $\ket{\psi_1} = \ket+\ket- = \tfrac12(\ket{00} - \ket{01} + \ket{10} - \ket{11})$ . First $f(x) = x$ , worked for you; then $f(x) = \bar x$ , which you do.

Query
Take $f(x) = x$ . $f(0) = 0$ , so the $x = 0$ terms are untouched. $f(1) = 1$ , so in the $x = 1$ terms the target flips: $\ket{10}$ and $\ket{11}$ swap amplitudes, $\tfrac12\ket{10} - \tfrac12\ket{11}\to -\tfrac12\ket{10} + \tfrac12\ket{11}$ . So
$\begin{aligned}\ket{\psi_2} &= \tfrac12\big(\ket{00} - \ket{01} \\ &\qquad - \ket{10} + \ket{11}\big) \\ &= \ket-\ket-\end{aligned}$
Chips: $+1$ for $x = 0$ , $-1$ for $x = 1$ .
Last H
$H\ket- = \ket1$ , so $\ket{\psi_3} = \ket1\ket- = \tfrac{1}{\sqrt2}(\ket{10} - \ket{11})$ . With chips: the top $\ket0$ amplitude is $\tfrac12(1 + (-1)) = 0$ and the top $\ket1$ amplitude is $\tfrac12(1 - (-1)) = 1$ . The measurement gives $1 = f(0)\oplus f(1) = 0\oplus1$ .
Your turn: query
Now $f(x) = \bar x$ : $f(0) = 1$ and $f(1) = 0$ . Start again from $\ket{\psi_1}$ .
Your turn
Run Deutsch’s algorithm with $f(x) = \bar x$ . Enter $\ket{\psi_2}$ , the state right after $U_f$ , as four amplitudes. Give the exact vector, signs included.
Hints
1. Which branches have $f(x) = 1$ ?
2. In those branches the target flips, and $X\ket- = -\ket-$ : the branch changes sign, the target doesn’t.
3. Here $(-1)^{f(0)} = -1$ and $(-1)^{f(1)} = +1$ . Multiply each branch of $\ket+\ket-$ by its chip.
Show the answer
Answer: $-\frac{1}{2}|00\rangle + \frac{1}{2}|01\rangle + \frac{1}{2}|10\rangle - \frac{1}{2}|11\rangle$
Chips: $(-1)^{f(0)} = -1$ and $(-1)^{f(1)} = +1$ . So $\ket{\psi_2} = -\ket-\ket- = -\frac{1}{2}|00\rangle + \frac{1}{2}|01\rangle + \frac{1}{2}|10\rangle - \frac{1}{2}|11\rangle$ .
Your turn: last H
Your turn
Run Deutsch’s algorithm with $f(x) = \bar x$ . Enter $\ket{\psi_3}$ , the state after the final $H$ , as four amplitudes. Give the exact vector, signs included.
Hints
1. Find $\ket{\psi_2}$ first: which sign does each branch carry?
2. Then apply $H$ to the top qubit only: $H\ket+ = \ket0$ , $H\ket- = \ket1$ .
3. Here $\ket{\psi_2} = -\ket-\ket-$ .
Show the answer
Answer: $-\frac{1}{\sqrt{2}}|10\rangle + \frac{1}{\sqrt{2}}|11\rangle$
Chips: $(-1)^{f(0)} = -1$ and $(-1)^{f(1)} = +1$ , so $\ket{\psi_2} = -\ket-\ket-$ . $H$ on the top qubit gives $\ket{\psi_3} = -\ket1\ket- = -\frac{1}{\sqrt{2}}|10\rangle + \frac{1}{\sqrt{2}}|11\rangle$ . The top qubit reads $1 = f(0)\oplus f(1)$ : balanced.

One more, fully worked, with a constant function.

Another worked example

Another example: a constant function

Query
Take $f(x) = 0$ . No branch has $f(x) = 1$ , so $U_f$ does nothing: $\ket{\psi_2} = \ket{\psi_1} = \ket+\ket- = \tfrac12(\ket{00} - \ket{01} + \ket{10} - \ket{11})$ . Both chips are $+1$ .
Last H
$H\ket+ = \ket0$ , so $\ket{\psi_3} = \ket0\ket- = \tfrac{1}{\sqrt2}(\ket{00} - \ket{01})$ . With chips: $\tfrac12(1 + 1) = 1$ on the top $\ket0$ and $\tfrac12(1 - 1) = 0$ on the top $\ket1$ .
Read out
The measurement gives 0: constant. For $f(x) = 1$ both chips are $-1$ , which gives $-\ket0\ket-$ : the same physical state with a global sign, and the same reading.

Check yourself

Run Deutsch’s algorithm with $f(x) = x$ . Enter $\ket{\psi_3}$ , the state after the final $H$ , as four amplitudes. Give the exact vector, signs included.

Hints

Find $\ket{\psi_2}$ first: which sign does each branch carry?
Then apply $H$ to the top qubit only: $H\ket+ = \ket0$ , $H\ket- = \ket1$ .
Here $\ket{\psi_2} = \ket-\ket-$ .

Show the answer

Answer: $\frac{1}{\sqrt{2}}|10\rangle - \frac{1}{\sqrt{2}}|11\rangle$

Chips: $(-1)^{f(0)} = +1$ and $(-1)^{f(1)} = -1$ , so $\ket{\psi_2} = \ket-\ket-$ . $H$ on the top qubit gives $\ket{\psi_3} = \ket1\ket- = \frac{1}{\sqrt{2}}|10\rangle - \frac{1}{\sqrt{2}}|11\rangle$ . The top qubit reads $1 = f(0)\oplus f(1)$ : balanced.

8 / 15 · Learn

Part B · Hadamards on n qubits

Part B: $n$ input bits, the Deutsch–Jozsa algorithm, and how many queries each method needs.

$H^{\otimes n}$ means a Hadamard on each of $n$ qubits. On $\ket{0\ldots0}$ every qubit becomes $\ket+$ , and multiplying out the product gives each $n$ ⁠-bit string exactly once:

H^{\otimes n}\ket{0}^{\otimes n} = \frac{1}{\sqrt{2^n}}\sum_{x\in\{0,1\}^n}\ket x

For $n = 2$ that is $\tfrac12(\ket{00} + \ket{01} + \ket{10} + \ket{11})$ . So $n$ gates prepare an equal superposition of $2^n$ strings, each with amplitude $1/\sqrt{2^n}$ , so that the $2^n$ probabilities add up to 1. $H^{\otimes n}$ is also called the Walsh–Hadamard transform.

Check yourself

What is the amplitude of $\ket{101}$ in $H^{\otimes3}\ket{000}$ ?

Hints

How many strings appear, and do they all have the same amplitude?
Each qubit contributes a factor $1/\sqrt2$ .

Show the answer

Answer: $\frac{\sqrt{2}}{4}$

$H^{\otimes3}\ket{000} = \ket+\ket+\ket+$ has 8 terms, each with amplitude $(1/\sqrt2)^3 = 1/(2\sqrt2) = \sqrt2/4$ . That includes $\ket{101}$ .

Common slips

$\frac{1}{8}$ : $\tfrac18$ is the probability of each string. The amplitude is its square root, $1/\sqrt8 = \sqrt2/4$ , so that eight probabilities of $\tfrac18$ add up to 1.
$\frac{1}{3}$ : Three qubits don’t give three terms: the product of three factors $(\ket0 + \ket1)/\sqrt2$ has $2^3 = 8$ terms, each with amplitude $(1/\sqrt2)^3$ .
$\frac{1}{\sqrt{3}}$ : That shares the probability among three strings. There are $2^3 = 8$ strings, so each amplitude is $1/\sqrt8$ .
$\frac{1}{2}$ : $\tfrac12$ is the amplitude for two qubits. Each extra qubit multiplies by another $1/\sqrt2$ : $(1/\sqrt2)^3 = 1/\sqrt8$ .

Other inputs give signs. For one qubit, ${H\ket0 = (\ket0 + \ket1)/\sqrt2}$ and ${H\ket1 = (\ket0 - \ket1)/\sqrt2}$ : the term $\ket z$ gets a minus sign exactly when the input and $z$ are both 1. Multiply the $n$ factors and the signs multiply:

H^{\otimes n}\ket x = \frac{1}{\sqrt{2^n}}\sum_z(-1)^{x\cdot z}\ket z

Here $x\cdot z = x_1z_1\oplus\cdots\oplus x_nz_n$ is the dot product mod 2. So $\ket z$ is negative when $x$ and $z$ share an odd number of 1s. Check with ${n = 2}$ : $H^{\otimes2}\ket{01} = \ket+\ket- = \tfrac12(\ket{00} - \ket{01} + \ket{10} - \ket{11})$ , negative where $z$ ends in 1.

Refresher: Bits, XOR and bit strings The dot product $x\cdot z$ mod 2, sums over bit strings and signs $(-1)^{f(x)}$ , with practice.

Check yourself

Enter $H^{\otimes2}\ket{10}$ as four amplitudes.

Hints

Which bit of $x = 10$ is 1?
With $x = 10$ , $x\cdot z = z_1$ : minus exactly where the first bit of $z$ is 1.

Show the answer

Answer: $\frac{1}{2}|00\rangle + \frac{1}{2}|01\rangle - \frac{1}{2}|10\rangle - \frac{1}{2}|11\rangle$

$x = 10$ , so $x\cdot z = z_1$ , and the sign is minus exactly where $z$ starts with 1: $\tfrac12(\ket{00} + \ket{01} - \ket{10} - \ket{11})$ . That is $\ket-\ket+$ , as $H\ket1\otimes H\ket0$ should be.

9 / 15 · Learn

Part B · The Deutsch–Jozsa algorithm

Now $f$ takes $n$ bits to one bit, and you are promised that it is constant (the same value on all $2^n$ inputs) or balanced (0 on exactly half of them, 1 on the other half). Which is it? The circuit is Deutsch’s with a wider data register: $n$ qubits in $\ket0$ and a target in $\ket1$ ; $H$ on every qubit; one $U_f$ ; then $H^{\otimes n}$ on the data and a 0/1-basis measurement of the data. After the query, kickback has put a chip on every input:

\ket{\psi_2} = \frac{1}{\sqrt{2^n}}\sum_x(-1)^{f(x)}\ket x\,\ket-

Check yourself

Let $n = 2$ and $f(00) = 0$ , $f(01) = 1$ , $f(10) = 1$ , $f(11) = 0$ , a balanced function. Enter the data register’s part of $\ket{\psi_2}$ , that is $\tfrac12\sum_x(-1)^{f(x)}\ket x$ , as four amplitudes.

Hints

What is the chip $(-1)^{f(x)}$ for each of the four inputs?
Each amplitude is $\tfrac12$ times its chip.

Show the answer

Answer: $\frac{1}{2}|00\rangle - \frac{1}{2}|01\rangle - \frac{1}{2}|10\rangle + \frac{1}{2}|11\rangle$

Chips $(-1)^{f(x)}$ : $+1, -1, -1, +1$ . So the data register is $\tfrac12(\ket{00} - \ket{01} - \ket{10} + \ket{11})$ , which happens to be $\ket-\ket-$ .

The last $H^{\otimes n}$ sends each $\ket x$ to $\tfrac{1}{\sqrt{2^n}}\sum_z(-1)^{x\cdot z}\ket z$ . Collect the terms for one output $z$ ; its amplitude is

\frac{1}{2^n}\sum_x(-1)^{x\cdot z + f(x)}.

For $z = 0\ldots0$ every $x\cdot z$ is 0, so the amplitude of $\ket{0\ldots0}$ is simply the average of the chips. If $f$ is constant, all chips are equal, the average is $\pm1$ , and the measurement gives all zeros with certainty. If $f$ is balanced, half the chips are $+1$ and half $-1$ , the average is 0, and all zeros never appears. The rule: all zeros means constant; anything else means balanced.

Check yourself

Deutsch–Jozsa with $n = 3$ and some balanced $f$ . What is the probability that the 0/1-basis measurement of the data register gives $000$ ?

$P(000) = \;?$

Hints

What is the $\ket{000}$ amplitude in terms of the chips?
It is the average of the eight chips $(-1)^{f(x)}$ . How many are $+1$ for a balanced $f$ ?

Show the answer

Answer: $P(000) = 0$

The $\ket{000}$ amplitude is $\tfrac18\sum_x(-1)^{f(x)} = \tfrac18(4 - 4) = 0$ for every balanced $f$ , so $P(000) = 0$ . That is why the read-out rule never fails.

Common slips

$\frac{1}{8}$ : That treats the last Hadamards as spreading the probability evenly over the eight strings. They add the eight chips into the $\ket{000}$ amplitude, and four $+1$ ⁠s cancel four $-1$ ⁠s exactly.
$\frac{1}{2}$ : Half the inputs have $f(x) = 0$ , but probabilities don’t follow that count. The $\ket{000}$ amplitude is the average of the chips, $\tfrac18(4 - 4) = 0$ .
$\frac{1}{64}$ : Square the average of the chips, not one chip over 8. For a balanced $f$ the average is $\tfrac18(4 - 4) = 0$ .
$1$ : All zeros with certainty is what a constant $f$ gives, when all eight chips are equal. For a balanced $f$ , four $+1$ chips and four $-1$ chips cancel on $\ket{000}$ : its amplitude is $\tfrac18(4 - 4) = 0$ .

10 / 15 · Learn

Part B · Where a balanced f sends the amplitude

For a balanced $f$ , the probability that leaves $\ket{0\ldots0}$ has to land on other strings, and which ones depends on $f$ . A tidy family is $f(x) = s\cdot x$ for a fixed string $s \ne 0\ldots0$ (such an $f$ is balanced). Its chips $(-1)^{s\cdot x}$ are exactly the signs $H^{\otimes n}$ gives when it acts on $\ket s$ . Since $H^{\otimes n}$ undoes itself, the last Hadamards turn the data register back into $\ket s$ , with certainty. For $n = 2$ and $f(x) = x_2$ , the last bit of $x$ , that string is $s = 01$ .

Check yourself

Deutsch–Jozsa with $n = 2$ and $f(x) = x_1\oplus x_2$ . What does the 0/1-basis measurement of the two data qubits give?

A $00$ , with certainty
B $11$ , with certainty
CEach of the four strings with probability $\tfrac14$
D $01$ or $10$ , the inputs where $f(x) = 1$

Hint

$x_1\oplus x_2 = x\cdot s$ for which string $s$ ?

Show the answer

Answer: B. $11$ , with certainty

$x_1\oplus x_2 = 11\cdot x$ , so $s = 11$ and the output is $\ket{11}$ with certainty. Check: for $z = 11$ , $x\cdot z = f(x)$ for every $x$ , so all four signs $(-1)^{x\cdot z + f(x)}$ are $+1$ and the amplitude is 1.

Why not the others

A. All zeros means constant, and $x_1\oplus x_2$ is balanced: $f(01) = f(10) = 1$ , $f(00) = f(11) = 0$ . Its chips $+, -, -, +$ cancel on $\ket{00}$ .
C. The last Hadamards don’t spread the amplitude out evenly. For each $z$ they add four signed terms; here the terms add up fully for one string and cancel for the other three.
D. The output is not a list of inputs. It is the string $z$ where the signs $(-1)^{x\cdot z + f(x)}$ all agree. For $z = 01$ they are $+, +, -, -$ , which cancel.

A preview beyond this course

Finding the hidden string $s$ in $f(x) = s\cdot x$ with one query is called the Bernstein–Vazirani problem. A classical computer needs $n$ queries for it, one per bit of $s$ . This course doesn’t cover it, but it uses exactly the circuit you just ran.

11 / 15 · Learn

Part B · Counting queries

A classical method that must be certain can be unlucky. A balanced $f$ gives the same value on half its inputs, so the first $2^{n-1}$ answers can all agree. One more query settles it: $2^{n-1} + 1$ queries in the worst case. Deutsch–Jozsa uses $U_f$ once, whatever $n$ is. For $n = 1$ , Deutsch’s problem, that is 2 against 1; for $n = 10$ it is 513 against 1.

Check yourself

For $n = 6$ , how many queries does a deterministic classical method need in the worst case to be certain?

Hints

How many inputs can share the same value when $f$ is balanced?
There are $2^6 = 64$ inputs, half of them with each value.

Show the answer

Answer: $33$

A balanced $f$ has $2^5 = 32$ inputs of each value, so 32 answers can agree; the 33rd settles it: $2^{n-1} + 1 = 33$ .

Common slips

$64$ : You never need all $2^6 = 64$ inputs. Half of them, 32, can share a value under a balanced $f$ , so 33 agreeing answers already prove that $f$ is constant.
$32$ : Thirty-two agreeing answers are still possible for a balanced $f$ : it has 32 inputs of each value. The 33rd query is the one that decides.
$6$ : The count depends on the number of inputs, $2^6 = 64$ , not on the number of bits. Up to 32 answers can agree under a balanced $f$ .

What changes if a small chance of error is allowed? Query $k$ inputs chosen at random and answer “constant” if all $k$ values agree, “balanced” otherwise. A constant $f$ is never misjudged. A balanced $f$ fools you only if all $k$ values agree. For independent random inputs each value is 0 or 1 with probability $\tfrac12$ , so all $k$ agree with probability

2\cdot\big(\tfrac12\big)^k = 2^{1-k}

(picking distinct inputs only lowers it). This does not depend on $n$ : eleven queries keep the error below 1 in 1000 for any $n$ . Deutsch–Jozsa’s exponential advantage holds only against classical methods that must never err.

Check yourself

You use the random method with $k = 4$ queries on a balanced $f$ . What is the probability that it wrongly answers “constant”?

$P(\text{error}) = \;?$

Hints

Which outcomes of the four queries lead to the answer “constant”?
All 0s, or all 1s. Each has probability $(\tfrac12)^4$ .

Show the answer

Answer: $P(\text{error}) = \frac{1}{8}$

The method says “constant” when all four values agree: all 0s or all 1s, each with probability $(\tfrac12)^4 = \tfrac{1}{16}$ . So the error is $2^{1-4} = \tfrac18$ .

Common slips

$\frac{1}{16}$ : That is the chance that all four values are 0. They could also all be 1, which fools you just as well, so double it: $2\cdot\tfrac{1}{16} = \tfrac18$ .
$\frac{7}{8}$ : That is the chance of the right answer, balanced. The error happens when all four values agree: $2\cdot(\tfrac12)^4 = \tfrac18$ .
$\frac{1}{2}$ : One query gives 0 or 1 with probability $\tfrac12$ , but the error needs all four to agree, and each extra query halves that chance: $2\cdot(\tfrac12)^4 = \tfrac18$ .

Check yourself

A headline reads: “Deutsch–Jozsa shows that a quantum computer beats every classical computer exponentially.” Take $n = 50$ . Which verdict is accurate?

AExaggerated: the gain is exponential only against classical methods that must never err
BFalse: Deutsch–Jozsa needs many runs too, so it has no advantage
CFalse: a careful classical method needs only 50 queries, one per bit
DAccurate: every classical method needs $2^{49} + 1$ queries

Hint

How many queries does the random method need to push its error below $10^{-6}$ , and does that number depend on $n$ ?

Show the answer

Answer: A. Exaggerated: the gain is exponential only against classical methods that must never err

A classical method that must be certain needs $2^{49} + 1$ queries in the worst case, and against it one query is an exponential gain. The random method errs with probability $2^{1-k}$ , independent of $n$ : 21 queries make that less than $10^{-6}$ . So “exponentially faster” holds only against error-free classical methods.

Why not the others

B. One run settles it with certainty: $\ket{0\dots0}$ has probability 1 for a constant $f$ and 0 for a balanced one. The advantage is real; it is exponential only against methods that must never err.
C. A query reveals one value $f(x)$ , not one bit of anything, and a balanced $f$ can agree on $2^{49}$ inputs. So a method that must be certain can need $2^{49} + 1$ queries. The headline fails for another reason: it forgets methods allowed a tiny error.
D. That count is for a method that must be certain. The random method errs with probability $2^{1-k}$ whatever $n$ is, so 21 queries bring the error below one in a million even for $n = 50$ . Against that, one quantum query is a modest gain. The headline is tempting because the certain count really does grow exponentially.

12 / 15 · Practice

Practice

Three items, each with new numbers when it comes back. Hints are there if you need them.

Check yourself

What is the amplitude of $\ket{0001}$ in $H^{\otimes 4}\ket{0110}$ ?

Hints

What sign does $(-1)^{x\cdot z}$ give for $x = 0110$ and $z = 0001$ ?
Every amplitude of $H^{\otimes n}\ket x$ has size $1/\sqrt{2^n}$ ; its sign is minus when $x$ and $z$ share an odd number of 1s.
They have no 1 in the same place, so $x\cdot z = 0$ . The size is $1/\sqrt{16}$ .

Show the answer

Answer: $\frac{1}{4}$

$x$ and $z$ have no 1 in the same place, so $x\cdot z = 0$ and the sign is $+$ . The size is $1/\sqrt{2^{4}} = \frac{1}{4}$ , so the amplitude is $\frac{1}{4}$ .

Line up $x = 0110$ and $z = 0001$ and multiply bit by bit: $0\cdot0 = 0$ , $1\cdot0 = 0$ , $1\cdot0 = 0$ , $0\cdot1 = 0$ . The products add to 0, so $x\cdot z = 0 \bmod 2 = 0$ and the sign $(-1)^{x\cdot z}$ is $+1$ . Every amplitude of $H^{\otimes 4}\ket{0110}$ has size $1/\sqrt{2^{4}} = \frac{1}{4}$ , so the amplitude of $\ket{0001}$ is $\frac{1}{4}$ .

Common slips

$-\frac{1}{4}$ : Right size, wrong sign. The sign is $(-1)^{x\cdot z}$ : $x = 0110$ and $z = 0001$ have no 1 in the same place, so $x\cdot z = 0$ and the sign is plus.
$\frac{1}{16}$ : $1/16$ is the size of a probability here. Each amplitude has size $1/\sqrt{2^{4}}$ , so that the 16 squared magnitudes add up to 1.

Check yourself

Deutsch–Jozsa with $n = 3$ . The balanced function $f$ is 1 on the inputs $010$ , $100$ , $110$ , $111$ and 0 on the other four. What is the amplitude of $\ket{111}$ in the data register just before the measurement?

Hints

Which two signs does each input $x$ contribute to the amplitude of $\ket{111}$ ?
The amplitude is the average of the eight signs $(-1)^{x\cdot z + f(x)}$ : one from the last Hadamards, one from the chip.
List $x\cdot 111$ for $x = 000, \ldots, 111$ : 0, 1, 1, 0, 1, 0, 0, 1. A term is $-1$ where this differs from $f(x)$ .

Show the answer

Answer: $\frac{1}{2}$

The eight signs $(-1)^{x\cdot z + f(x)}$ are +, -, +, +, +, +, -, +; they add up to $4$ , so the amplitude is $4/8 = \frac{1}{2}$ .

Go through $x = 000, 001, \ldots, 111$ . The values $x\cdot 111$ are 0, 1, 1, 0, 1, 0, 0, 1; the values $f(x)$ are 0, 0, 1, 0, 1, 0, 1, 1. Each term $(-1)^{x\cdot z + f(x)}$ is $+1$ where they agree and $-1$ where they differ: +, -, +, +, +, +, -, +. The sum is $4$ , so the amplitude is $4/8 = \frac{1}{2}$ , and $\ket{111}$ has probability $\frac{1}{4}$ .

Common slips

$0$ : The chips alone, $(-1)^{f(x)}$ , average to 0 for a balanced $f$ : that is the $\ket{000}$ amplitude. For $\ket{111}$ every term also carries the sign $(-1)^{x\cdot z}$ from the last Hadamards.
$\frac{1}{4}$ : That is the probability, the squared amplitude. The amplitude itself is $\frac{1}{2}$ .
$-\frac{1}{2}$ : Right size, wrong sign. Recount the signs $(-1)^{x\cdot z + f(x)}$ : a term is $-1$ exactly when $x\cdot z$ and $f(x)$ differ.

Check yourself

A balanced $f$ on 2-bit inputs (four of them). You query two different inputs, chosen at random. What is the probability that the two values agree, so that the random method wrongly says “constant”?

Hints

After the first answer, how many of the remaining inputs give the same value?
Each value belongs to 2 inputs, and one of them has been used. 3 inputs remain.
So the chance is 1 out of 3.

Show the answer

Answer: $\frac{1}{3}$

Whatever the first value, 1 of the 3 remaining inputs shares it, so the probability is $\tfrac{1}{3}$ . In general it is $\tfrac{2^{n-1}-1}{2^n-1} < \tfrac12$ : already better than independent queries, which give $\tfrac12$ .

A balanced $f$ on 4 inputs has 2 inputs with each value. The first query gives some value; 1 other input has that value, and the second query picks one of the 3 remaining inputs at random. So the chance that the two agree is $\tfrac{1}{3}$ . With independent queries (repeats allowed) it would be $\tfrac12$ .

Common slips

$\frac{1}{2}$ : That is the answer when the second query may repeat the first input: $2\cdot(\tfrac12)^2 = \tfrac12$ . Here the inputs are different, and one input of the first value is already used up.
$\frac{1}{4}$ : The numerator is right: 1 unused input shares the first value. But the second query chooses among the 3 inputs that are left, not all 4.

13 / 15 · Explain

Explain it

One measurement can’t read both $f(0)$ and $f(1)$ . How, then, does a single use of $U_f$ in Deutsch’s algorithm decide whether $f$ is constant or balanced?

Show a model answer

With the target in $\ket-$ , $U_f$ leaves the target alone and multiplies each branch $\ket x$ of the data qubit by $(-1)^{f(x)}$ : phase kickback. So after the query the data qubit is $\pm\ket+$ if $f(0) = f(1)$ and $\pm\ket-$ if not. The last $H$ makes the two branches interfere: matching signs add up on $\ket0$ , opposite signs on $\ket1$ . A 0/1-basis measurement then gives $f(0)\oplus f(1)$ with certainty. You learn only that one global bit, never $f(0)$ or $f(1)$ themselves.

A good answer covers

Kickback: with the target in $\ket-$ , $U_f$ puts the sign $(-1)^{f(x)}$ on each branch of the data qubit
The last $H$ makes the branches interfere: equal signs give $\ket0$ , opposite signs give $\ket1$ , with certainty
Only the global bit $f(0)\oplus f(1)$ is learned, not $f(0)$ or $f(1)$
The target stays $\ket-$ ; the answer ends up in the data qubit

14 / 15 · Mastery check

Mastery check

Check yourself

A quantum computer applies $U_f$ once to a superposition of all four 2-bit inputs, producing $\tfrac12\sum_x\ket{x}\ket{f(x)}$ . Then every qubit is measured in the 0/1 basis. What does this one run tell you about $f$ ?

AThe value $f(x)$ at one input $x$ , chosen at random
BNothing: measuring a superposition gives meaningless random bits
COnly $f(00)$ , because the inputs started in $\ket{00}$
DAll four values $f(x)$ : the whole table of $f$

Show the answer

Answer: A. The value $f(x)$ at one input $x$ , chosen at random

Each branch $\ket{x}\ket{f(x)}$ has amplitude $\tfrac12$ . The measurement picks one branch at random, with probability $1/4$ each, and returns its input and its value: one $f(x)$ per run, which is no more than one classical query gives.

Why not the others

B. The bits are not meaningless. Every branch is $\ket{x}\ket{f(x)}$ , so in every result the last bit equals $f$ of the first ones: you learn one genuine value.
C. Every input has the same amplitude, $\tfrac12$ , so the measured $x$ is random: $00$ turns up only one time in 4.
D. The state involves all four values, but a 0/1 measurement of 3 qubits returns 3 bits: one input $x$ and its value $f(x)$ . The other branches are gone once you have measured.

Check yourself

A student builds Deutsch’s circuit but prepares the bottom qubit in $\ket0$ instead of $\ket1$ , so it enters $U_f$ as $\ket+$ . Everything else is the same. What does the 0/1-basis measurement of the top qubit give?

A0 or 1 at random, with probability $\tfrac12$ each
B0 for every $f$ , so the circuit no longer tells constant from balanced
C $f(0)\oplus f(1)$ , as before: the target doesn’t matter
DNothing on top; the answer now appears on the bottom qubit

Show the answer

Answer: B. 0 for every $f$ , so the circuit no longer tells constant from balanced

$U_f\ket x\ket+ = \ket x\,\tfrac{1}{\sqrt2}\big(\ket{f(x)} + \ket{1\oplus f(x)}\big) = \ket x\ket+$ : no sign, for any $f$ . The state stays $\ket+\ket+$ , the last $H$ gives $\ket0\ket+$ , and the top qubit reads 0 whatever $f$ is. The $\ket-$ target is what turns $f(x)$ into a sign.

Why not the others

A. With no signs kicked back, the data qubit is still $\ket+$ after $U_f$ , and $H\ket+ = \ket0$ exactly. Two Hadamards in a row undo each other; nothing here randomizes the top qubit.
C. The target matters. Kickback needs the flip to change the target’s sign, and $X\ket+ = +\ket+$ . With $\ket+$ no branch picks up a sign, so the top qubit returns to $\ket0$ for every $f$ .
D. The bottom qubit is $\ket+$ before and after $U_f$ , since $U_f\ket x\ket+ = \ket x\ket+$ for every $f$ . Measured in the 0/1 basis it gives a random bit that says nothing about $f$ .

Check yourself

What is the amplitude of $\ket{111}$ in $H^{\otimes 3}\ket{110}$ ?

Hints

What sign does $(-1)^{x\cdot z}$ give for $x = 110$ and $z = 111$ ?
Every amplitude of $H^{\otimes n}\ket x$ has size $1/\sqrt{2^n}$ ; its sign is minus when $x$ and $z$ share an odd number of 1s.
They share a 1 in 2 places, so $x\cdot z = 0$ . The size is $1/\sqrt{8}$ .

Show the answer

Answer: $\frac{\sqrt{2}}{4}$

$x$ and $z$ share a 1 in 2 places, so $x\cdot z = 0$ and the sign is $+$ . The size is $1/\sqrt{2^{3}} = \frac{\sqrt{2}}{4}$ , so the amplitude is $\frac{\sqrt{2}}{4}$ .

Line up $x = 110$ and $z = 111$ and multiply bit by bit: $1\cdot1 = 1$ , $1\cdot1 = 1$ , $0\cdot1 = 0$ . The products add to 2, so $x\cdot z = 2 \bmod 2 = 0$ and the sign $(-1)^{x\cdot z}$ is $+1$ . Every amplitude of $H^{\otimes 3}\ket{110}$ has size $1/\sqrt{2^{3}} = \frac{\sqrt{2}}{4}$ , so the amplitude of $\ket{111}$ is $\frac{\sqrt{2}}{4}$ .

Common slips

$-\frac{\sqrt{2}}{4}$ : Right size, wrong sign. The sign is $(-1)^{x\cdot z}$ : $x = 110$ and $z = 111$ share a 1 in 2 places, so $x\cdot z = 0$ and the sign is plus.
$\frac{1}{8}$ : $1/8$ is the size of a probability here. Each amplitude has size $1/\sqrt{2^{3}}$ , so that the 8 squared magnitudes add up to 1.

Check yourself

Deutsch–Jozsa with $n = 2$ and $f(00) = 0$ , $f(01) = 0$ , $f(10) = 1$ , $f(11) = 1$ . What does the 0/1-basis measurement of the two data qubits give?

A $\ket{00}$ with certainty
B $\ket{01}$ with certainty
C $\ket{10}$ with certainty
D $\ket{11}$ with certainty
EEach of the four strings with probability $\tfrac14$

Show the answer

Answer: C. $\ket{10}$ with certainty

For $z = 10$ the four signs $(-1)^{x\cdot z + f(x)}$ are +, +, +, +: they all agree, so $\ket{10}$ has amplitude $1$ and every other string has amplitude 0. (Here $f(x) = 10\cdot x$ .)

Why not the others

A. All zeros would mean constant, but this $f$ is balanced: two 0s and two 1s, so the four chips +, +, -, - cancel on $\ket{00}$ .
B. For $\ket{01}$ the four signs $(-1)^{x\cdot z + f(x)}$ are +, -, -, +: they cancel, so this outcome never occurs.
D. For $\ket{11}$ the four signs $(-1)^{x\cdot z + f(x)}$ are +, -, +, -: they cancel, so this outcome never occurs.
E. The Hadamards don’t just spread amplitude around. For each outcome the last $H^{\otimes 2}$ adds four signed contributions, and here they add up fully on one string and cancel on the other three.

Check yourself

A black box computes $f$ on 4-bit strings (sixteen inputs). You are promised that $f$ is either constant or balanced (0 on exactly 8 inputs and 1 on the other 8). Querying one input at a time, and needing to be certain, how many queries might you need in the worst case?

A $2$
B $4$
C $9$
D $16$

Show the answer

Answer: C. $9$

In the worst case the first 8 answers agree, which a balanced $f$ allows. Query number 9 decides: $2^{n-1} + 1 = 9$ for $n = 4$ .

Why not the others

A. Two queries settle it only if they disagree. If they agree, a balanced $f$ is still possible: 8 inputs share each value.
B. The count depends on the number of inputs, not on the number of bits in $x$ . A balanced $f$ can give the same value on any 8 inputs, so 8 agreeing answers prove nothing.
D. You never need all 16. A balanced $f$ has only 8 inputs of each value, so once 9 answers agree, $f$ must be constant.

15 / 15 · Recap

Recap

From memory

Before reading the summary, write down what you remember. Pulling it back from memory is what makes it last.

What does one run of $U_f$ on a superposition, followed by a 0/1 measurement, tell you? Why is that no speedup?
Show the key points
- One pair $(x, f(x))$ , with $x$ random
- Measuring the same register again repeats it; a new pair needs a fresh copy and another use of $U_f$
- An advantage needs interference that answers a global question about $f$
Write the four states of Deutsch’s algorithm, $\ket{\psi_0}$ to $\ket{\psi_3}$ .
Show the key points
- $\ket{\psi_0} = \ket0\ket1$ , then $\ket{\psi_1} = \ket+\ket-$
- Kickback: $\ket{\psi_2} = \tfrac{1}{\sqrt2}\big((-1)^{f(0)}\ket0 + (-1)^{f(1)}\ket1\big)\ket-$ ; the target stays $\ket-$
- $\ket{\psi_3} = \pm\ket{f(0)\oplus f(1)}\ket-$ ; measure the top qubit
Why does all zeros mean constant in Deutsch–Jozsa, and how well can a randomized classical method do?
Show the key points
- The $\ket{0\ldots0}$ amplitude is the average of the chips, $\tfrac{1}{2^n}\sum_x(-1)^{f(x)}$ : $\pm1$ if constant, 0 if balanced
- A deterministic method can need $2^{n-1} + 1$ queries
- $k$ random queries err with probability at most $2^{1-k}$ , whatever $n$ is

Key ideas

$U_f\ket{x,y} = \ket{x, y\oplus f(x)}$ is reversible. On $\tfrac{1}{\sqrt{2^n}}\sum_x\ket x\ket0$ it gives $\tfrac{1}{\sqrt{2^n}}\sum_x\ket{x, f(x)}$ , but a measurement returns one random pair.
Phase kickback: $U_f\ket x\ket- = (-1)^{f(x)}\ket x\ket-$ . The target is unchanged; $f(x)$ becomes a sign on the data branch.
Deutsch: $\ket{\psi_3} = \pm\ket{f(0)\oplus f(1)}\ket-$ , so one query reveals whether $f(0) = f(1)$ , and nothing more.
$H^{\otimes n}\ket x = \tfrac{1}{\sqrt{2^n}}\sum_z(-1)^{x\cdot z}\ket z$ . In Deutsch–Jozsa the $\ket{0\ldots0}$ amplitude is the average of the chips: $\pm1$ if $f$ is constant, 0 if balanced.
One quantum query against $2^{n-1} + 1$ for a certain classical answer, but only a few for a nearly certain one: $k$ random queries err with probability at most $2^{1-k}$ .

Go further

Free resources for when you want more than this lesson covers.

Fundamentals of quantum algorithms: Quantum query algorithmsJohn Watrous, IBM Quantum · Course
Goes past Deutsch–Jozsa to the Bernstein–Vazirani problem and Simon’s algorithm, a stepping stone to Shor’s.
Quantum computing for computer scientistsMicrosoft Research · Video
A recorded talk that rebuilds bits, qubits and gates as matrices and ends by running the Deutsch problem in Q# code.
Deutsch–Jozsa algorithmWikipedia · Article
The history: Deutsch’s 1985 version worked only half the time, and the one-query version that is always right came in 1998.

Math refreshers

The toolkit topics this lesson leans on.

Bits, XOR and bit stringsx ⊕ y, x · z mod 2, sums over {0,1}ⁿ, and signs that depend on f(x)