Building quantum oracles for real problems

1 / 15 · Learn

Before you start

Lessons 16 and 17 treated the oracle as a box that marks the solutions. This lesson opens the box for a real problem. You turn a logic puzzle into a circuit, check that it marks exactly the right inputs, run Grover search on it in code, and count what the whole search costs. The compute, copy, uncompute pattern of Lesson 13 does much of the work, and the gate costs of Lesson 11 come back at the end.

By the end of this lesson you can:

write a logic puzzle as a CNF formula and check an assignment against it;
say why an honest oracle checks the clauses instead of listing the answers;
build an OR clause from a Toffoli gate, and a phase oracle from compute, phase and uncompute steps;
run Grover search on such an oracle in code, choose the number of iterations, and read the solutions from the counts;
count the Toffoli and T gates in one oracle call, and compare the whole search with brute force.

Check yourself

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

A formula has 40 variables, so there are $2^{40}$ (about 1.1 trillion) possible assignments, and exactly one of them satisfies it. Grover search runs with an oracle that checks the formula. About how many oracle calls does it need?

A1: one call checks every assignment at once
BAbout 40, roughly one per variable
CAbout 820,000
DAbout 550 billion: half the assignments, as when checking them one by one

Show the answer

Answer: C. About 820,000

With $N = 2^{40}$ assignments and one solution, Grover needs about $\tfrac{\pi}{4}\sqrt N = \tfrac{\pi}{4}\,2^{20} \approx 823{,}550$ calls. That is far fewer than the $2^{39}$ checks brute force needs on average, but it is still exponential in the number of variables: two more variables double it.

Why not the others

A. One call does act on every assignment at once, but all it does is put a minus sign on the solution. A measurement right after it gives a random assignment. Turning that sign into a likely outcome takes about $\tfrac{\pi}{4}\sqrt N$ calls.
B. That would make SAT easy, and no quantum algorithm is known to do that. Grover’s count grows with the square root of the number of assignments, $\sqrt{2^{40}} = 2^{20}$ , not with the number of variables.
D. That is the classical average, $2^{39}$ checks. Grover gives a real gain: about $\tfrac{\pi}{4}\sqrt{2^{40}}$ calls, the square root of the classical count.

Check yourself

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

You want Grover search to solve a logic puzzle. What do you need in order to build its oracle?

AA circuit that checks the rules on any proposed solution
BOnly the number of solutions
CThe list of solutions, so that the oracle knows which inputs to mark
DA quantum memory loaded with every candidate in advance

Show the answer

Answer: A. A circuit that checks the rules on any proposed solution

A search oracle is a circuit that checks the rules on whatever input it gets and flips the sign when they all hold. Building it takes the rules, not the answers.

Why not the others

B. The number of solutions helps you choose how many Grover iterations to run, but it can’t mark anything. Marking is done by a circuit that checks the rules on its input.
C. With the list in hand there would be nothing left to search for. The oracle only has to recognise a solution when it sees one: a circuit that checks the rules on its input marks exactly the solutions, and nobody needs to know in advance which they are.
D. Loading every candidate would take as many steps as checking them all classically. The superposition of all candidates comes from Hadamards on the input qubits; the oracle then computes the rules on it.

2 / 15 · Learn

Logic puzzles as formulas

Three friends, Ana, Ben and Cy, are deciding whether to come to a party. Write $x_0 = 1$ if Ana comes and $x_0 = 0$ if not, and likewise $x_1$ for Ben and $x_2$ for Cy. They agree on two rules:

if Ben comes, Ana comes. This fails only when Ben comes without Ana, so it reads $x_0 \lor \lnot x_1$ ;
Ben or Cy comes, or both: $x_1 \lor x_2$ .

Each rule is a clause: an OR of literals, where a literal is a variable ( $x_1$ ) or its negation ( $\lnot x_1$ ). The puzzle wants all its clauses at once, so it is their AND:

\varphi = (x_0 \lor \lnot x_1) \land (x_1 \lor x_2)

An AND of clauses is a formula in conjunctive normal form (CNF). An assignment gives every variable a value; write it as a bit string $x_0x_1x_2$ . It satisfies $\varphi$ when every clause holds, and then $\varphi(x) = 1$ .

Check yourself

Ben and Cy come, Ana doesn’t: $x_0x_1x_2 = 011$ . Does this assignment satisfy $\varphi = (x_0 \lor \lnot x_1) \land (x_1 \lor x_2)$ ?

ANo: the second clause fails
BYes: two of the three variables are 1
CYes: the second clause holds
DNo: the first clause fails

Show the answer

Answer: D. No: the first clause fails

Clause 1: $x_0 \lor \lnot x_1 = 0 \lor 0 = 0$ , so $\varphi(011) = 0$ whatever clause 2 says. Ben came without Ana.

Why not the others

A. The second clause holds: $x_1 = 1$ , so $x_1 \lor x_2 = 1$ . It is the first that fails: $x_0 = 0$ and $\lnot x_1 = 0$ .
B. Counting 1s says nothing about the rules. Check each clause: the first, $x_0 \lor \lnot x_1$ , is $0 \lor 0 = 0$ , so the formula is 0.
C. A CNF formula needs every clause to hold, not just one. Here $x_1 \lor x_2 = 1$ , but $x_0 \lor \lnot x_1 = 0 \lor 0 = 0$ : Ben comes without Ana.

Checking one assignment is quick: evaluate each clause and take the AND, a few steps per clause. Finding a satisfying assignment is the hard direction. With $n$ variables there are $2^n$ assignments, and brute force tries them one by one: up to $2^n$ checks. Practical solvers prune cleverly and handle many large formulas, but no known method avoids exponential time in the worst case.

The satisfiability problem, SAT, is NP-complete. NP is the class of problems whose solutions can be checked quickly, and a fast algorithm for SAT would give a fast algorithm for every one of them, from timetabling to packing boxes. Most researchers believe that no such algorithm exists. The table below checks all eight assignments of the party formula.

The party formula on all eight assignments. Shaded rows satisfy both clauses. The last column is the sign $(-1)^{\varphi(x)}$ that a phase oracle will put on $\ket x$ , drawn as a needle as in circle notation: right for $+1$ , left for $-1$ .

Check yourself

How many of the eight assignments $x_0x_1x_2$ satisfy $(x_0 \lor x_2) \land (\lnot x_0 \lor \lnot x_1) \land (x_1 \lor \lnot x_2)$ ?

Hints

Which assignments make each clause false?
A clause of two literals is false only when both literals are false: that fixes two variables and leaves the third free, so it rules out two assignments. Strike them out for each clause and count what is left.

Show the answer

Answer: $2$

The satisfying assignments are 011 and 100: 2 of the eight.

Each clause rules out the assignments where all its literals are false. Clause 1, $x_0 \lor x_2$ , rules out 000 and 010. Clause 2, $\lnot x_0 \lor \lnot x_1$ , rules out 110 and 111. Clause 3, $x_1 \lor \lnot x_2$ , rules out 001 and 101. What is left: 011 and 100, so 2 assignments.

Common slips

$6$ : That counts the assignments that fail. 6 of the eight make some clause false, so 2 satisfy every clause.
$8$ : That counts the assignments where at least one clause holds. A CNF formula is an AND: every clause has to hold.
$4$ : That leaves out the last clause. Check it on the assignments that pass the others.

3 / 15 · Learn

An honest oracle

Grover search needs a phase oracle (Lesson 16): $O\ket x = (-1)^{\varphi(x)}\ket x$ , a minus sign on exactly the satisfying assignments. For the party, those are the four shaded rows of the table.

One way to build $O$ is to read it off the table: one multi-controlled Z for each solution, firing on that bit string alone. But writing that circuit takes the list of solutions, and with the list in hand there is nothing left to search for. Such an oracle presupposes the answer.

An honest oracle is built from the formula alone. It evaluates the clauses on whatever assignment it is given, as a classical checker would, and flips the sign when they all hold. Its size grows with the number of clauses, not with $2^n$ , and nobody needs to know in advance which inputs it will mark. Finding them is the search’s job.

Check yourself

Two students build a phase oracle for a 50-variable formula. Alice writes a gadget for each clause, then an AND and an uncompute. Bob lets a classical computer run until it has found every satisfying assignment, then writes one multi-controlled Z for each. Both circuits put the same signs on the same inputs. Whose construction is useful for search?

ABob’s: it marks the solutions directly, so it is sure to be right
BAlice’s
CNeither: any oracle that marks the solutions must already contain them
DBoth: they are the same operation, so they are equally useful

Hint

What did each student need to know before writing the circuit?

Show the answer

Answer: B. Alice’s

Alice’s oracle is built from the formula alone, at a size that grows with the number of clauses. Bob’s needs the solutions first, and finding them is the search itself.

Why not the others

A. It is right, but by the time Bob can write it the search is over: finding every solution took up to $2^{50}$ checks. An oracle that needs the answers before it can be built saves nothing.
C. Alice’s oracle contains the rules, not the solutions. It computes each clause on its input, the quick checking direction, and the signs follow; nobody knows in advance which inputs will get them.
D. They are the same operation, but not the same cost. Alice builds hers from the formula in a number of steps that grows with the number of clauses; Bob needs the answers first, which is the whole search.

4 / 15 · Learn

One clause from a Toffoli

Start with one clause, $x_0 \lor x_1$ . A Toffoli computes an AND, not an OR, so use De Morgan’s law:

a \lor b = \lnot(\lnot a \land \lnot b)

An OR is false only when every literal is false. So:

Flip a work qubit $w$ , which starts at $\ket0$ , when $x_0 = 0$ and $x_1 = 0$ . A Toffoli with two anti-controls does this: an anti-control, drawn ○, fires when its qubit is 0 instead of 1. (With ordinary controls only, put an X on each input before and after the Toffoli.)
Flip $w$ with an X. Now $w = 1$ unless both literals are false: $w = x_0 \lor x_1$ .

A negated literal such as $\lnot x_1$ is false when $x_1 = 1$ , so it gets an ordinary control instead. The inputs pass through unchanged, so the gadget is reversible.

Check yourself

Build the clause $x_0 \lor \lnot x_1$ : for every input $\ket{x_0x_1}\ket0$ , the work qubit $w$ (bottom wire) should end as $x_0 \lor \lnot x_1$ , and the inputs should be unchanged.

Build it in the circuit builder (gates: X, control, anti-control).

Hints

On which single input is $x_0 \lor \lnot x_1$ false?
It is false only for $x_0 = 0$ , $x_1 = 1$ . Fire a Toffoli there: an anti-control on $x_0$ , an ordinary control on $x_1$ , target $w$ .
Then flip $w$ with an X.

Show the answer

One circuit that works: controlled-X q1,q0=0→q2, then X on q2.

The clause is false only for $x_0 = 0$ , $x_1 = 1$ . A Toffoli with an anti-control on $x_0$ and a control on $x_1$ flips $w$ there, and the X on $w$ turns that into 1 everywhere else: $w = x_0 \lor \lnot x_1$ .

Clauses with three literals, and why they matter

A clause with three literals, such as $x_0 \lor \lnot x_1 \lor x_2$ , works the same way with one more control: a 3-controlled X fires on the one setting of its three variables that makes the clause false, then an X flips $w$ .

This matters for honesty about hardness. Formulas whose clauses all have two literals (2-SAT) can be solved quickly by a clever classical algorithm. With three literals per clause the problem, 3-SAT, is NP-complete. This lesson’s examples use two literals only to keep the circuits small; the construction is the same.

5 / 15 · Learn

From clauses to a phase oracle

Give each of the $m$ clauses its own work qubit, holding $c_1(x), \ldots, c_m(x)$ . The formula is the AND of those qubits, and a multi-controlled gate computes an AND. Aim an $m$ ⁠-controlled X at an output qubit prepared in $\ket-$ . It flips the output exactly when every clause holds, and flipping $\ket-$ gives $-\ket-$ . That is phase kickback (Lesson 9): the output stays $\ket-$ , and the branch $\ket x$ picks up the sign $(-1)^{\varphi(x)}$ . (A multi-controlled Z across the clause qubits does the same job without the output qubit.)

One step is left. The work qubits now hold the clause values $c(x)$ , a record that differs from branch to branch. Lesson 13 showed what such leftovers do: they stop the branches from interfering. So run the clause gadgets again in reverse order, which returns every work qubit to $\ket0$ . The whole oracle is compute, phase, uncompute.

The honest phase oracle. $C$ computes the clause values into the work qubits; the AND flips the output, whose $\ket-$ turns the flip into the sign $(-1)^{\varphi(x)}$ ; $C^{-1}$ clears the work qubits. Read the four states below the circuit: only at step 4 is the sign all that is left.

Check yourself

Grover search measures only the variable qubits, never the work qubits. Why must the oracle still uncompute the clause values?

AIt shouldn’t: running the clause gadgets backwards would also undo the minus signs
BThe clause values differ from branch to branch; left in place, they stop the branches from interfering
COnly so that the next oracle call can reuse the work qubits
DIt needn’t: qubits that are never measured can’t affect the result

Show the answer

Answer: B. The clause values differ from branch to branch; left in place, they stop the branches from interfering

After the AND, each branch is $(-1)^{\varphi(x)}\ket x\ket{c(x)}$ . The records $c(x)$ differ between branches, so the variables are entangled with the work qubits and the diffusion step can’t make the branches interfere. Uncomputing returns the work qubits to $\ket{0\ldots0}$ on every branch and leaves only the sign.

Why not the others

A. The signs come from the AND step, which the uncompute doesn’t repeat. The clause gadgets act on each branch the same way whatever its sign, so they clear the work qubits and leave the signs alone.
C. Reuse is a bonus, not the reason. Even with fresh work qubits for every call, the leftover records would tell the branches apart and block the interference Grover depends on.
D. Unmeasured qubits still matter when they are entangled with the ones you measure. Left in place, each branch $\ket x$ carries its own record $\ket{c(x)}$ , and branches with different records can’t interfere. Lesson 13 showed the same effect.

6 / 15 · Worked example

Worked example: the party oracle on four qubits

The party formula $\varphi = (x_0 \lor \lnot x_1) \land (x_1 \lor x_2)$ on four qubits: the variables $x_0, x_1, x_2$ and one work qubit $w$ . Clause 1 goes into $w$ . Clause 2 is folded into the phase step, so it needs no work qubit of its own.

Worked example

Building $O$ for the party formula

Compute clause 1
Clause 1, $x_0 \lor \lnot x_1$ , is false only when $x_0 = 0$ and $x_1 = 1$ . So the Toffoli gets an anti-control on $x_0$ and an ordinary control on $x_1$ , and an X on $w$ follows. Check the input $\ket{010}\ket0$ , Ben without Ana: the Toffoli fires, $w$ becomes 1, and the X makes it 0. Clause 1 fails, and $w$ says so.
Phase
The sign belongs on the branches where $w = 1$ and clause 2, $x_1 \lor x_2$ , holds. Use De Morgan on the sign. A Z on $w$ puts $-1$ on every branch with $w = 1$ . A second Z on $w$ , with anti-controls on $x_1$ and $x_2$ , multiplies by $-1$ again where $x_1 = x_2 = 0$ , the one case in which clause 2 fails. In one line, with $\bar x$ for NOT $x$ :
$(-1)^{w\,(x_1 \lor x_2)} = (-1)^{w}\,(-1)^{w\,\bar x_1 \bar x_2}$
Uncompute
Repeat the clause-1 gates in reverse order: the X on $w$ , then the same Toffoli. They return $w$ to 0 on every branch, and neither touches the sign. So $\ket x\ket0 \to (-1)^{\varphi(x)}\ket x\ket0$ : a phase oracle on three variables with one work qubit.
Your turn: the signs
Use the clauses rather than the simulator.
Your turn
Which inputs $\ket{x_0x_1x_2}\ket0$ come out of the party oracle with a minus sign? Select all.
Select all that apply.
1. A $\ket{000}$
2. B $\ket{001}$
3. C $\ket{010}$
4. D $\ket{011}$
5. E $\ket{100}$
6. F $\ket{101}$
7. G $\ket{110}$
8. H $\ket{111}$
Hints
1. Only the satisfying assignments get a sign. Test each clause.
2. A two-literal clause is false only when both of its literals are false.
Show the answer
Answers: B. $\ket{001}$ ; F. $\ket{101}$ ; G. $\ket{110}$ ; H. $\ket{111}$
The sign is $-1$ exactly where every clause holds: on $\ket{001}$ , $\ket{101}$ , $\ket{110}$ and $\ket{111}$ .
Why not the others
- A. Clause 2, $x_1 \lor x_2$ , is false here: $x_1 = 0$ and $x_2 = 0$ . No minus sign.
- C. Clause 1, $x_0 \lor \lnot x_1$ , is false here: $x_0 = 0$ and $x_1 = 1$ . No minus sign.
- D. Clause 1, $x_0 \lor \lnot x_1$ , is false here: $x_0 = 0$ and $x_1 = 1$ . No minus sign.
- E. Clause 2, $x_1 \lor x_2$ , is false here: $x_1 = 0$ and $x_2 = 0$ . No minus sign.
Your turn: a new rule
Cy changes rule 2 to “Ben comes, or Cy stays home”: $x_1 \lor \lnot x_2$ . Clause 1 is unchanged, so the compute and uncompute columns stay as they are.
Your turn
Fill in the phase step, columns 3 and 4, so that the circuit is the phase oracle for $(x_0 \lor \lnot x_1) \land (x_1 \lor \lnot x_2)$ .
Build it in the circuit builder (gates: Z, control, anti-control, X).
Hints
1. On which setting of $x_1$ and $x_2$ is the new clause 2 false?
2. It fails only for $x_1 = 0$ , $x_2 = 1$ . Keep the Z on $w$ ; the second Z on $w$ needs an anti-control on $x_1$ and an ordinary control on $x_2$ .
Show the answer
One circuit that works: controlled-X q1,q0=0→q3, then X on q3, then Z on q3, then controlled-Z q2,q1=0→q3, then X on q3, then controlled-X q1,q0=0→q3.
A Z on $w$ marks every branch with $w = 1$ . The second Z on $w$ , with an anti-control on $x_1$ and a control on $x_2$ , removes the mark where $x_1 = 0$ and $x_2 = 1$ , the one case in which $x_1 \lor \lnot x_2$ fails. The signs land on $000$ , $100$ , $110$ and $111$ .

One more, fully worked: $\psi = (\lnot x_0 \lor x_2) \land (x_0 \lor x_1)$ , with the same four qubits.

Another worked example

Another example: $(\lnot x_0 \lor x_2) \land (x_0 \lor x_1)$

Compute clause 1
$\lnot x_0 \lor x_2$ is false only when $x_0 = 1$ and $x_2 = 0$ : a Toffoli with an ordinary control on $x_0$ and an anti-control on $x_2$ , then an X on $w$ . Now $w = c_1(x)$ .
Phase
Clause 2, $x_0 \lor x_1$ , fails only when $x_0 = x_1 = 0$ : a Z on $w$ , then a Z on $w$ with anti-controls on $x_0$ and $x_1$ . The sign is $-1$ exactly where $w = 1$ and clause 2 holds.
Uncompute
The X on $w$ , then the same Toffoli, return $w$ to 0 on every branch.
Signs
If $x_0 = 1$ , clause 1 needs $x_2 = 1$ : that gives $101$ and $111$ . If $x_0 = 0$ , clause 2 needs $x_1 = 1$ : that gives $010$ and $011$ . Those four inputs pick up $-1$ ; the other four keep $+1$ .

7 / 15 · Learn

The oracle in code

In code, write each clause as a list of literals. A literal is a pair (q, v): it holds when qubit $q$ has the value $v$ . So (1, 0) is $\lnot x_1$ and (2, 1) is $x_2$ .

The function clause below is the De Morgan gadget, written with X gates around ordinary controls instead of anti-controls. It flips each qubit whose literal needs a 1, so that the qubit reads 1 exactly when its literal is false; fires an mcx onto the work qubit; flips the qubits back; and ends with an X on the work qubit. The same function handles clauses of any length.

This program is the bit-flip form of the party oracle, $\ket x\ket{00}\ket y \to \ket x\ket{00}\ket{y\oplus\varphi(x)}$ . With the output in $\ket-$ instead of $\ket y$ , the flip becomes the sign. But the program is missing a step.

Check yourself

The program computes both clauses into work qubits 3 and 4, then ANDs them into the output, qubit 5. It forgets to clean up. Add the uncompute step, so that every input $\ket{x_0x_1x_2}\ket{00}\ket0$ ends as $\ket{x_0x_1x_2}\ket{00}\ket{\varphi(x)}$ . The checker tries all eight inputs.

from qiskit import QuantumCircuit

n = 3                          # variables x0, x1, x2: qubits 0-2
clauses = [[(0, 1), (1, 0)],   # x0 or (not x1)
           [(1, 1), (2, 1)]]   # x1 or x2
m = len(clauses)               # work qubits 3-4, one per clause
out = n + m                    # output qubit 5

def clause(qc, lits, w):
    """Put the OR of the literals into work qubit w, which starts at 0."""
    for q, v in lits:
        if v == 1:
            qc.x(q)            # now q reads 1 exactly when its literal is false
    qc.mcx([q for q, v in lits], w)    # w = 1 when every literal is false
    for q, v in lits:
        if v == 1:
            qc.x(q)            # undo the flips
    qc.x(w)                    # De Morgan: OR = NOT (all false)

qc = QuantumCircuit(n + m + 1)
for k in range(m):
    clause(qc, clauses[k], n + k)        # compute the clauses
qc.mcx(list(range(n, n + m)), out)       # AND of the clauses into the output
# uncompute the clause qubits here

Write the program in the app’s code editor (Python with Qiskit’s circuit methods), run it, and check it.

Hints

Run it first: from $\ket{000000}$ the state ends as $\ket{000100}$ , because clause 1 holds and its work qubit still says so.
Each clause gadget undoes itself: running it a second time returns its work qubit to 0.
Repeat the compute loop after the mcx line.

Show the answer

One program that works:

from qiskit import QuantumCircuit

n = 3                          # variables x0, x1, x2: qubits 0-2
clauses = [[(0, 1), (1, 0)],   # x0 or (not x1)
           [(1, 1), (2, 1)]]   # x1 or x2
m = len(clauses)               # work qubits 3-4, one per clause
out = n + m                    # output qubit 5

def clause(qc, lits, w):
    """Put the OR of the literals into work qubit w, which starts at 0."""
    for q, v in lits:
        if v == 1:
            qc.x(q)            # now q reads 1 exactly when its literal is false
    qc.mcx([q for q, v in lits], w)    # w = 1 when every literal is false
    for q, v in lits:
        if v == 1:
            qc.x(q)            # undo the flips
    qc.x(w)                    # De Morgan: OR = NOT (all false)

qc = QuantumCircuit(n + m + 1)
for k in range(m):
    clause(qc, clauses[k], n + k)        # compute the clauses
qc.mcx(list(range(n, n + m)), out)       # AND of the clauses into the output
for k in range(m):
    clause(qc, clauses[k], n + k)        # uncompute: each gadget undoes itself

Each clause gadget is its own inverse, and the gadgets act on different work qubits, so running the loop again clears qubits 3 and 4 on every input. The output keeps $\varphi(x)$ , because the uncompute never touches qubit 5.

8 / 15 · Learn

Grover search on the puzzle

Now a bigger party. Dee joins ( $x_3$ ), and there are four rules:

Ana or Ben comes: $x_0 \lor x_1$ ;
if Ana comes, Cy comes: $\lnot x_0 \lor x_2$ ;
Ben and Dee don’t both come: $\lnot x_1 \lor \lnot x_3$ ;
if Cy comes, Dee comes: $\lnot x_2 \lor x_3$ .

The program below builds the honest oracle with one work qubit per clause (qubits 4 to 7) and an output qubit (8) in $\ket-$ , then runs Grover search with the diffusion step of Lesson 16 (the function diffuser below). How many iterations? With $N$ assignments, of which $M$ are solutions, about $\tfrac{\pi}{4}\sqrt{N/M}$ , rounded to a whole number. Here a quick classical count gives $M = 2$ of $N = 16$ , and $\tfrac{\pi}{4}\sqrt8 \approx 2.22$ : two iterations. (In a real search you wouldn’t know $M$ ; Lesson 17 showed how to manage without it.)

Interactive

A code editor for Python with Qiskit’s circuit methods, run in the page: edit the program below and run it to see the circuit it builds, the state it leaves and, when it measures, the counts from 1,000 shots.

from qiskit import QuantumCircuit
import math

n = 4                          # variables x0..x3: qubits 0-3
clauses = [[(0, 1), (1, 1)],   # x0 or x1
           [(0, 0), (2, 1)],   # (not x0) or x2
           [(1, 0), (3, 0)],   # (not x1) or (not x3)
           [(2, 0), (3, 1)]]   # (not x2) or x3
m = len(clauses)               # work qubits 4-7, one per clause
out = n + m                    # output qubit 8
UNCOMPUTE = True

def clause(qc, lits, w):
    """Put the OR of the literals into work qubit w, which starts at 0."""
    for q, v in lits:
        if v == 1:
            qc.x(q)            # now q reads 1 exactly when its literal is false
    qc.mcx([q for q, v in lits], w)    # w = 1 when every literal is false
    for q, v in lits:
        if v == 1:
            qc.x(q)            # undo the flips
    qc.x(w)                    # De Morgan: OR = NOT (all false)

def oracle(qc):
    for k in range(m):
        clause(qc, clauses[k], n + k)    # compute the clauses
    qc.mcx(list(range(n, n + m)), out)   # AND into the output: a sign, by kickback
    if UNCOMPUTE:
        for k in range(m):
            clause(qc, clauses[k], n + k)    # uncompute: clear the work qubits

def diffuser(qc):
    qc.h(range(n))
    qc.x(range(n))
    qc.h(n - 1)
    qc.mcx(list(range(n - 1)), n - 1)
    qc.h(n - 1)
    qc.x(range(n))
    qc.h(range(n))

M = 2                          # solutions, from a quick classical count
k = math.floor(math.pi / 4 * math.sqrt(2 ** n / M))

qc = QuantumCircuit(n + m + 1, n)
qc.x(out)
qc.h(out)                      # output in |->, so its flip becomes a sign
qc.h(range(n))
for i in range(k):
    oracle(qc)
    diffuser(qc)
qc.measure(range(n), range(n))

Grover search on the four-friend party: nine qubits, two iterations. Run it: two strings each come up about 47% of the time. Qiskit prints classical bit 0, which holds $x_0$ , on the right.

Open it in the app

Check yourself

Grover search on four variables $x_0, \ldots, x_3$ (qubits 0 to 3) ends with qc.measure(range(4), range(4)). The counts begin {'0010': 474, '1101': 468, '0111': 6, '1000': 5, …}. Which assignments, written $x_0x_1x_2x_3$ , did it find?

AOnly 0100: the most frequent string, read backwards
B0100 and 1011
CEvery string that appears in the counts
D0010 and 1101, as printed

Show the answer

Answer: B. 0100 and 1011

Qiskit puts $x_0$ on the right, so read the strings backwards: '0010' is 0100 and '1101' is 1011. Two counts of nearly equal size mean two solutions, and checking each against the formula takes a moment.

Why not the others

A. The two big counts differ by a few shots in a thousand, which is sampling noise: both strings came up nearly half the time, so 1011 is a solution too.
C. Grover leaves a small chance of a wrong answer, and those few shots land on the other strings. Each candidate is quick to check against the formula; the two big counts are the solutions.
D. Qiskit prints classical bit 0, which holds qubit 0 and so $x_0$ , as the rightmost character. Read each string backwards: '0010' is $x_0x_1x_2x_3 = 0100$ .

Check yourself

Grover search over the $2^{4}$ assignments of a 4-variable formula with exactly one satisfying assignment. How many iterations should it run?

Hints

How does the best number of iterations depend on $N$ and $M$ ?
About $\tfrac{\pi}{4}\sqrt{N/M}$ , rounded to a whole number.

Show the answer

Answer: $3$

$\tfrac{\pi}{4}\sqrt{2^{4}/1} = \tfrac{\pi}{4}\sqrt{16} \approx 3.14$ , so 3 iterations.

Common slips

$4$ : That leaves out the factor $\tfrac{\pi}{4}$ . Each iteration turns the state by a fixed angle, and about $\tfrac{\pi}{4}\sqrt{N/M}$ turns reach the solutions.
$8$ : That is about how many checks a classical search needs on average. Grover needs about the square root of that: $\tfrac{\pi}{4}\sqrt{N/M}$ .

9 / 15 · Explore

Skip the uncompute?

Predict, then see

The program below is the four-friend search with one change: UNCOMPUTE = False, so every oracle call computes the clauses and leaves them in the work qubits. It also runs a single iteration, to keep the comparison simple. With the uncompute switched on, that one iteration finds a solution 78% of the time. Without it, how often does a run give one of the two solutions?

AMore than 78%: fewer gates leave fewer chances for error
B0%: the solutions never come up
CAbout 78%, as before: the work qubits are never measured, so they can’t matter
DAbout 14%, hardly better than the 2 in 16 (12.5%) of a blind guess

Interactive

A code editor for Python with Qiskit’s circuit methods, run in the page: edit the program below and run it to see the circuit it builds, the state it leaves and, when it measures, the counts from 1,000 shots.

from qiskit import QuantumCircuit
import math

n = 4                          # variables x0..x3: qubits 0-3
clauses = [[(0, 1), (1, 1)],   # x0 or x1
           [(0, 0), (2, 1)],   # (not x0) or x2
           [(1, 0), (3, 0)],   # (not x1) or (not x3)
           [(2, 0), (3, 1)]]   # (not x2) or x3
m = len(clauses)               # work qubits 4-7, one per clause
out = n + m                    # output qubit 8
UNCOMPUTE = False

def clause(qc, lits, w):
    """Put the OR of the literals into work qubit w, which starts at 0."""
    for q, v in lits:
        if v == 1:
            qc.x(q)            # now q reads 1 exactly when its literal is false
    qc.mcx([q for q, v in lits], w)    # w = 1 when every literal is false
    for q, v in lits:
        if v == 1:
            qc.x(q)            # undo the flips
    qc.x(w)                    # De Morgan: OR = NOT (all false)

def oracle(qc):
    for k in range(m):
        clause(qc, clauses[k], n + k)    # compute the clauses
    qc.mcx(list(range(n, n + m)), out)   # AND into the output: a sign, by kickback
    if UNCOMPUTE:
        for k in range(m):
            clause(qc, clauses[k], n + k)    # uncompute: clear the work qubits

def diffuser(qc):
    qc.h(range(n))
    qc.x(range(n))
    qc.h(n - 1)
    qc.mcx(list(range(n - 1)), n - 1)
    qc.h(n - 1)
    qc.x(range(n))
    qc.h(range(n))

M = 2                          # solutions, from a quick classical count
k = 1                          # one iteration, to keep the comparison simple

qc = QuantumCircuit(n + m + 1, n)
qc.x(out)
qc.h(out)                      # output in |->, so its flip becomes a sign
qc.h(range(n))
for i in range(k):
    oracle(qc)
    diffuser(qc)
qc.measure(range(n), range(n))

Run the program as it is and add up the counts of 0010 and 1101, out of 1000 shots. Then change UNCOMPUTE = False to UNCOMPUTE = True, run it again and compare.

Open it in the app

Why did skipping the uncompute spoil the search, even though the work qubits are never measured? A sentence or two is enough.

Show what happens

What happens: D. About 14%, hardly better than the 2 in 16 (12.5%) of a blind guess

Without the uncompute, each branch $\ket x$ carries its own record $\ket{c(x)}$ in the work qubits. The diffusion step acts on the variable qubits only, and two branches can interfere only if everything else about them is the same. Branches with different records don’t, so the reflection that should pile amplitude onto the solutions has little to work with: the solutions come up $\tfrac{37}{256} \approx 14\%$ of the time, close to a blind guess. With the uncompute, every branch ends with $\ket{0000}$ in the work qubits, and the interference works: $\tfrac{25}{32} \approx 78\%$ after one iteration, and about 95% after two.

Why not the others

A. This simulator makes no errors, so fewer gates can’t help; the circuit is simply a different one. Without the uncompute, the two solutions came up only about 14% of the time.
B. Nothing cancels the solutions completely. Without working interference they come up about as often as any other strings: about 14% of runs for the two together.
C. That is the tempting view: what you don’t measure can’t hurt. The run shows otherwise: the two solutions together came up only about 14% of the time. The leftover clause values are entangled with the variables, and that blocks the interference.

10 / 15 · Learn

What one oracle call costs

Count Toffoli gates: on an error-corrected machine each one takes 7 T gates (Lesson 11), and T gates are the expensive part there. X gates are cheap, so leave them out. For a formula with $m$ clauses of two literals each:

computing the clauses takes $m$ Toffolis, one per clause;
the AND of the $m$ clause qubits is an $m$ ⁠-controlled X, which can be built from $2m - 3$ Toffolis and $m - 2$ extra work qubits (below);
uncomputing the clauses takes $m$ Toffolis again.

That makes $4m - 3$ Toffolis per call, and $7(4m - 3)$ T gates. The four-friend oracle, with $m = 4$ , uses 13 Toffolis and 91 T gates per call. The simulator runs mcx as one gate; real hardware can’t.

A 4-controlled X from Toffolis. The first two compute $c_1c_2$ , then $c_1c_2c_3$ , into work qubits; the middle one writes $c_1c_2c_3c_4$ onto the target; the last two uncompute, so the work qubits end at $\ket0$ . Compute, copy, uncompute once more. With $m$ controls it takes $2m - 3$ Toffolis.

Check yourself

An honest oracle for a formula with 10 clauses of 2 literals each computes every clause into its own work qubit, ANDs the 10 clause qubits into the output, and uncomputes the clauses. Build each $j$ ⁠-controlled X from $2j - 3$ Toffolis. How many Toffolis does one oracle call use?

Hints

Count three parts: compute the clauses, the AND, uncompute the clauses.
A 2-literal clause is a 2-controlled X: $2\cdot2 - 3 = 1$ Toffoli. The AND is a 10-controlled X: $2\cdot10 - 3 = 17$ .

Show the answer

Answer: $37$

Clauses: $10 \times 1 = 10$ Toffolis to compute and as many to uncompute. The AND: $17$ . Total $20 + 17 = 37$ Toffolis per call.

Common slips

$27$ : That leaves out the uncompute. The clause gadgets run a second time, in reverse, to clear the work qubits, and that costs as many Toffolis again.
$21$ : The AND of 10 clause qubits is a 10-controlled X, which takes $2\cdot10 - 3 = 17$ Toffolis, not one.
$17$ : That counts only the AND. Every clause gadget is a multi-controlled X too, run once to compute and once to uncompute.

Now multiply by the number of calls. With one solution among $N = 2^n$ assignments, Grover needs about $\tfrac{\pi}{4}\sqrt{2^n} = \tfrac{\pi}{4}\,2^{n/2}$ calls, against up to $2^n$ checks for brute force. Grover halves the exponent, from $n$ to $n/2$ , but doesn’t remove it: two more variables still double the work. And as Lesson 10 noted, no quantum algorithm can search an unstructured space with far fewer than $\sqrt N$ calls.

So the honest summary is a quadratic speed-up over brute force, not an efficient algorithm. No quantum algorithm is known to solve SAT, or any NP-complete problem, in polynomial time, and most researchers believe none exists. Grover-style search can also speed up cleverer classical methods, such as backtracking solvers, by a square root of their own cost, but that doesn’t make the problems easy either.

Check yourself

A headline reads: “Quantum computers will crack SAT and other NP-complete problems in a flash.” Which verdict is accurate?

AAccurate: one oracle call tests all $2^n$ assignments at once
BAccurate: the oracle checks a formula quickly, so the whole search is quick
CExaggerated: Grover gives a square-root speed-up over brute force, which is still exponential
DWrong the other way: quantum computers give no speed-up at all on SAT

Show the answer

Answer: C. Exaggerated: Grover gives a square-root speed-up over brute force, which is still exponential

Grover needs about $\tfrac{\pi}{4}\sqrt{2^n}$ oracle calls where brute force needs up to $2^n$ checks: a square root, but still exponential in $n$ . No quantum algorithm is known to solve NP-complete problems in polynomial time, and most researchers believe none exists.

Why not the others

A. One call marks every solution with a sign, but a measurement then returns one random assignment. Turning the signs into a likely solution takes about $\tfrac{\pi}{4}\sqrt{2^n}$ calls.
B. Each check is quick, but the search still needs about $\tfrac{\pi}{4}\sqrt{2^n}$ calls, which doubles with every two extra variables. No quantum algorithm is known to solve NP-complete problems in polynomial time.
D. Grover does give a real speed-up: about $2^{n/2}$ calls instead of up to $2^n$ checks. It is quadratic, not exponential, and it pays off only for large $n$ , but it exists.

11 / 15 · Worked example

Worked example: when does the square root pay off?

Worked example

Brute force against Grover, in seconds

The speeds below are made up, chosen so the arithmetic is exact. They are not measurements or forecasts of any real machine.

Assumptions
A classical computer checks $2^{30}$ assignments a second, about 1.07 billion. A quantum computer runs $2^{10} = 1024$ Grover iterations a second: each iteration is an oracle call with its many T gates, plus the diffusion step, on a slow error-corrected machine. The formula has $n$ variables and one solution. Count $2^n$ checks for brute force (its worst case) and $2^{n/2}$ iterations for Grover (leaving out the constant factor $\tfrac{\pi}{4}$ ).
Times
Classical: $2^n / 2^{30} = 2^{n-30}$ seconds. Quantum: $2^{n/2} / 2^{10} = 2^{n/2-10}$ seconds. At $n = 30$ the classical computer needs $2^0 = 1$ second and the quantum one $2^{5} = 32$ seconds. For small $n$ the slow quantum steps lose.
Break-even
The times are equal when the exponents are: $n - 30 = n/2 - 10$ , so $n/2 = 20$ and $n = 40$ . Both then take $2^{10} = 1024$ seconds, about 17 minutes. Past that point the quantum computer pulls ahead: two more variables multiply its time by 2 and the classical time by 4.
Your turn: n = 60
Your turn
With the same speeds, how many seconds does the quantum computer take at $n = 60$ ? A power of 2 is fine.
Hints
1. How many iterations does Grover need at $n = 60$ ?
2. $2^{60/2} = 2^{30}$ iterations at $2^{10}$ a second.
Show the answer
Answer: $1048576$
$2^{60/2} = 2^{30}$ iterations at $2^{10}$ a second take $2^{20} = 1{,}048{,}576$ seconds, about 12 days.
Common slips
- $1073741824$ : $2^{30}$ is the number of Grover iterations (and also the classical time in seconds). Divide the iterations by the speed of $2^{10}$ a second.
- $1125899906842624$ : That uses $2^{n-10}$ . Grover needs $2^{n/2}$ iterations, not $2^n$ : the time is $2^{30}/2^{10}$ seconds.
- $1099511627776$ : That multiplies by the speed. Iterations divided by iterations per second gives seconds: $2^{30}/2^{10}$ .
Your turn: the ratio
Your turn
At $n = 60$ , how many times longer than the quantum computer does the classical one take?
Hints
1. Write both times at $n = 60$ as powers of 2.
2. Classical $2^{30}$ seconds, quantum $2^{20}$ seconds.
Show the answer
Answer: $1024$
Classical $2^{60-30} = 2^{30}$ seconds (about 34 years), quantum $2^{20}$ seconds (about 12 days): a factor of $2^{10} = 1024$ .
Common slips
- $10$ : That is the difference of the exponents, $30 - 20$ . The ratio of the times is 2 to that power: $2^{30}/2^{20} = 2^{10}$ .
- $1073741824$ : That is the classical time in seconds. Divide it by the quantum time, $2^{20}$ seconds.
- $1048576$ : That is the quantum time in seconds. The ratio is $2^{30}/2^{20}$ .

One more, fully worked, with other made-up speeds.

Another worked example

Another example: different speeds

Assumptions
Classical: $2^{33}$ checks a second, eight of the machines above. Quantum: $2^{14}$ iterations a second, sixteen times faster than before. Still $2^n$ checks against $2^{n/2}$ iterations.
Times
Classical $2^{n-33}$ seconds; quantum $2^{n/2-14}$ seconds.
Break-even
$n - 33 = n/2 - 14$ gives $n/2 = 19$ , so $n = 38$ . Both take $2^{38-33} = 2^5 = 32$ seconds.
At n = 60
Quantum: $2^{30-14} = 2^{16}$ seconds, about 18 hours. Classical: $2^{60-33} = 2^{27}$ seconds, about 4.3 years. The ratio is $2^{27-16} = 2^{11} = 2048$ .

The two running times under the first set of made-up speeds, on a log scale. Brute force (amber) climbs twice as steeply as Grover (blue). They cross at $n = 40$ ; at $n = 60$ brute force needs about 34 years and Grover about 12 days. But Grover’s line still climbs: at $n = 100$ it would need $2^{40}$ seconds, about 35,000 years.

Check yourself

Made-up speeds: a classical computer checks $2^{30}$ assignments a second, and a quantum computer runs $2^{12}$ Grover iterations a second. For a formula with $n$ variables and one solution, count $2^n$ checks and $2^{n/2}$ iterations. For which $n$ do the two take the same time?

Hints

Write each time as a power of 2 in seconds: the number of steps divided by the steps per second.
The times are $2^{n-30}$ and $2^{n/2-12}$ seconds. Set the exponents equal.

Show the answer

Answer: $36$

$n - 30 = n/2 - 12$ gives $n/2 = 18$ , so $n = 36$ . Both then take $2^{6}$ seconds; for larger $n$ the quantum computer wins.

Common slips

$18$ : That solves $n/2 = 30 - 12$ and stops. Doubling gives $n$ : the times are $2^{n-30}$ and $2^{n/2-12}$ seconds, equal when $n - 30 = n/2 - 12$ .
$84$ : Check the signs: dividing by the speeds subtracts the exponents, so the times are $2^{n-30}$ and $2^{n/2-12}$ seconds.
$30$ : At $n = 30$ the classical computer needs only 1 second, while the quantum one needs $2^{3}$ seconds.

12 / 15 · Practice

Practice

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

Check yourself

How many of the eight assignments $x_0x_1x_2$ satisfy $(\lnot x_0 \lor x_1) \land (\lnot x_1 \lor x_2)$ ?

Hints

Which assignments make each clause false?
A clause of two literals is false only when both literals are false: that fixes two variables and leaves the third free, so it rules out two assignments. Strike them out for each clause and count what is left.

Show the answer

Answer: $4$

The satisfying assignments are 000, 001, 011 and 111: 4 of the eight.

Each clause rules out the assignments where all its literals are false. Clause 1, $\lnot x_0 \lor x_1$ , rules out 100 and 101. Clause 2, $\lnot x_1 \lor x_2$ , rules out 010 and 110. What is left: 000, 001, 011 and 111, so 4 assignments.

Common slips

$8$ : That counts the assignments where at least one clause holds. A CNF formula is an AND: every clause has to hold.
$6$ : That leaves out the last clause. Check it on the assignments that pass the others.

Check yourself

A Toffoli onto a work qubit $w$ that starts at 0, followed by an X on $w$ , should leave $w = \lnot x_0 \lor x_2$ . Which controls does the Toffoli need?

Aanti-control ○ on $x_0$ , anti-control ○ on $x_2$
Banti-control ○ on $x_0$ , control • on $x_2$
Ccontrol • on $x_0$ , anti-control ○ on $x_2$
Dcontrol • on $x_0$ , control • on $x_2$

Hints

On which single input of the two variables is the clause false?
A control fires on 1, an anti-control on 0. Fire the Toffoli exactly where every literal is false.

Show the answer

Answer: C. control • on $x_0$ , anti-control ○ on $x_2$

The clause is false only when $x_0 = 1$ and $x_2 = 0$ , so the Toffoli fires there: control • on $x_0$ , anti-control ○ on $x_2$ . The X on $w$ then gives 1 everywhere else, which is the OR.

Why not the others

A. The literal $\lnot x_0$ is false when $x_0 = 1$ , so $x_0$ needs an ordinary control, which fires on 1.
B. This Toffoli fires when both literals are true, so after the X, $w$ is 0 exactly there: that is NOT (both true), not the OR. Fire the Toffoli on the one input that makes the clause false.
D. The literal $x_2$ is false when $x_2 = 0$ , so $x_2$ needs an anti-control, which fires on 0.

Check yourself

Made-up speeds: a classical computer checks $2^{32}$ assignments a second, and a quantum computer runs $2^{14}$ Grover iterations a second. For a formula with $n$ variables and one solution, count $2^n$ checks and $2^{n/2}$ iterations. For which $n$ do the two take the same time?

Hints

Write each time as a power of 2 in seconds: the number of steps divided by the steps per second.
The times are $2^{n-32}$ and $2^{n/2-14}$ seconds. Set the exponents equal.

Show the answer

Answer: $36$

$n - 32 = n/2 - 14$ gives $n/2 = 18$ , so $n = 36$ . Both then take $2^{4}$ seconds; for larger $n$ the quantum computer wins.

Common slips

$18$ : That solves $n/2 = 32 - 14$ and stops. Doubling gives $n$ : the times are $2^{n-32}$ and $2^{n/2-14}$ seconds, equal when $n - 32 = n/2 - 14$ .
$92$ : Check the signs: dividing by the speeds subtracts the exponents, so the times are $2^{n-32}$ and $2^{n/2-14}$ seconds.
$32$ : At $n = 32$ the classical computer needs only 1 second, while the quantum one needs $2^{2}$ seconds.

13 / 15 · Explain

Explain it

A friend says: “Grover search with a SAT oracle tries all $2^n$ assignments at once, so SAT is easy on a quantum computer.” Explain what one oracle call really does, how many calls the search needs, and what that means for SAT.

Show a model answer

One call evaluates the clauses on every branch of the superposition, but all it leaves behind is a minus sign on the satisfying assignments; a measurement right after it would return one random assignment. Grover needs about $\tfrac{\pi}{4}\sqrt{2^n/M}$ calls to turn those signs into a high chance of measuring a solution. That is the square root of the $2^n$ checks of brute force, but $2^{n/2}$ still grows exponentially: two more variables double the work. So Grover gives SAT a quadratic speed-up, not an efficient algorithm, and no quantum algorithm is known to solve NP-complete problems in polynomial time.

A good answer covers

One call only marks the satisfying assignments with a sign; it doesn’t read them out (a measurement would give one random assignment)
The search needs about $\tfrac{\pi}{4}\sqrt{2^n/M}$ calls, the square root of the brute-force count
$2^{n/2}$ is still exponential in $n$ , so SAT doesn’t become easy
No known quantum algorithm solves NP-complete problems in polynomial time

14 / 15 · Mastery check

Mastery check

Check yourself

A formula has 30 variables, so there are $2^{30}$ (about 1.1 billion) possible assignments, and exactly one of them satisfies it. Grover search runs with an oracle that checks the formula. About how many oracle calls does it need?

A1: one call checks every assignment at once
BAbout 30, roughly one per variable
CAbout 26,000
DAbout 540 million: half the assignments, as when checking them one by one

Show the answer

Answer: C. About 26,000

With $N = 2^{30}$ assignments and one solution, Grover needs about $\tfrac{\pi}{4}\sqrt N = \tfrac{\pi}{4}\,2^{15} \approx 25{,}736$ calls. That is far fewer than the $2^{29}$ checks brute force needs on average, but it is still exponential in the number of variables: two more variables double it.

Why not the others

A. One call does act on every assignment at once, but all it does is put a minus sign on the solution. A measurement right after it gives a random assignment. Turning that sign into a likely outcome takes about $\tfrac{\pi}{4}\sqrt N$ calls.
B. That would make SAT easy, and no quantum algorithm is known to do that. Grover’s count grows with the square root of the number of assignments, $\sqrt{2^{30}} = 2^{15}$ , not with the number of variables.
D. That is the classical average, $2^{29}$ checks. Grover gives a real gain: about $\tfrac{\pi}{4}\sqrt{2^{30}}$ calls, the square root of the classical count.

Check yourself

You want Grover search to solve a map-colouring puzzle (neighbouring countries get different colours). What do you need in order to build its oracle?

AA quantum memory loaded with every candidate in advance
BA circuit that checks the rules on any proposed solution
CThe list of solutions, so that the oracle knows which inputs to mark
DOnly the number of solutions

Show the answer

Answer: B. A circuit that checks the rules on any proposed solution

A search oracle is a circuit that checks the rules on whatever input it gets and flips the sign when they all hold. Building it takes the rules, not the answers.

Why not the others

A. Loading every candidate would take as many steps as checking them all classically. The superposition of all candidates comes from Hadamards on the input qubits; the oracle then computes the rules on it.
C. With the list in hand there would be nothing left to search for. The oracle only has to recognise a solution when it sees one: a circuit that checks the rules on its input marks exactly the solutions, and nobody needs to know in advance which they are.
D. The number of solutions helps you choose how many Grover iterations to run, but it can’t mark anything. Marking is done by a circuit that checks the rules on its input.

Check yourself

A Toffoli onto a work qubit $w$ that starts at 0, followed by an X on $w$ , should leave $w = \lnot x_0 \lor \lnot x_1$ . Which controls does the Toffoli need?

Aanti-control ○ on $x_0$ , control • on $x_1$
Banti-control ○ on $x_0$ , anti-control ○ on $x_1$
Ccontrol • on $x_0$ , control • on $x_1$
Dcontrol • on $x_0$ , anti-control ○ on $x_1$

Hints

On which single input of the two variables is the clause false?
A control fires on 1, an anti-control on 0. Fire the Toffoli exactly where every literal is false.

Show the answer

Answer: C. control • on $x_0$ , control • on $x_1$

The clause is false only when $x_0 = 1$ and $x_1 = 1$ , so the Toffoli fires there: control • on $x_0$ , control • on $x_1$ . The X on $w$ then gives 1 everywhere else, which is the OR.

Why not the others

A. The literal $\lnot x_0$ is false when $x_0 = 1$ , so $x_0$ needs an ordinary control, which fires on 1.
B. This Toffoli fires when both literals are true, so after the X, $w$ is 0 exactly there: that is NOT (both true), not the OR. Fire the Toffoli on the one input that makes the clause false.
D. The literal $\lnot x_1$ is false when $x_1 = 1$ , so $x_1$ needs an ordinary control, which fires on 1.

Check yourself

To avoid uncomputing, a student gives every oracle call its own fresh work qubits: call 1 uses one set, call 2 another, and none is ever cleared. Does Grover search still find a solution with high probability?

ANo: the leftover clause values still differ from branch to branch and block the interference
BYes, but it needs twice as many iterations
CNo, because the extra qubits make the search space bigger
DYes: fresh work qubits start at 0, so nothing is left over to clean

Show the answer

Answer: A. No: the leftover clause values still differ from branch to branch and block the interference

Each call leaves $\ket{c(x)}$ in its work qubits, a record that differs between branches. Branches carrying different records can’t interfere, so the diffusion step can’t build up amplitude on the solutions. Only uncomputing, which returns the work qubits to $\ket{0\ldots0}$ on every branch, removes the records.

Why not the others

B. More iterations don’t help: each call adds another record that tells the branches apart, and branches that can be told apart don’t interfere. The fix is to uncompute, not to iterate more.
C. The search space is still the $2^n$ assignments of the variables; nothing searches over the work qubits. The trouble is the records they keep, which differ between branches and block the interference.
D. They start at 0, but after the call they hold the clause values $c(x)$ , which differ between branches. Those records are entangled with the variables, so the diffusion step can no longer make the branches interfere. Uncomputing is what removes them.

Check yourself

Grover search over the $2^{12}$ assignments of a 12-variable formula with exactly one satisfying assignment. How many iterations should it run?

Hints

How does the best number of iterations depend on $N$ and $M$ ?
About $\tfrac{\pi}{4}\sqrt{N/M}$ , rounded to a whole number.

Show the answer

Answer: $50$

$\tfrac{\pi}{4}\sqrt{2^{12}/1} = \tfrac{\pi}{4}\sqrt{4096} \approx 50.27$ , so 50 iterations.

Common slips

$64$ : That leaves out the factor $\tfrac{\pi}{4}$ . Each iteration turns the state by a fixed angle, and about $\tfrac{\pi}{4}\sqrt{N/M}$ turns reach the solutions.
$2048$ : That is about how many checks a classical search needs on average. Grover needs about the square root of that: $\tfrac{\pi}{4}\sqrt{N/M}$ .
$51$ : One more iteration overshoots: the state turns past the solutions and the success chance drops. Stop at the whole number nearest $\tfrac{\pi}{4}\sqrt{N/M}$ .

Check yourself

Grover search on four variables $x_0, \ldots, x_3$ (qubits 0 to 3) ends with qc.measure(range(4), range(4)). The counts begin {'0101': 461, '0100': 458, '1010': 7, '1011': 4, …}. Which assignments, written $x_0x_1x_2x_3$ , did it find?

AOnly 1010: the most frequent string, read backwards
BEvery string that appears in the counts
C0100 and 0101, as printed
D0010 and 1010

Show the answer

Answer: D. 0010 and 1010

Qiskit puts $x_0$ on the right, so read the strings backwards: '0100' is 0010 and '0101' is 1010. Two counts of nearly equal size mean two solutions, and checking each against the formula takes a moment.

Why not the others

A. The two big counts differ by a few shots in a thousand, which is sampling noise: both strings came up nearly half the time, so 0010 is a solution too.
B. Grover leaves a small chance of a wrong answer, and those few shots land on the other strings. Each candidate is quick to check against the formula; the two big counts are the solutions.
C. Qiskit prints classical bit 0, which holds qubit 0 and so $x_0$ , as the rightmost character. Read each string backwards: '0100' is $x_0x_1x_2x_3 = 0010$ .

Check yourself

An honest oracle for a formula with 8 clauses of 2 literals each computes every clause into its own work qubit, ANDs the 8 clause qubits into the output, and uncomputes the clauses. Build each $j$ ⁠-controlled X from $2j - 3$ Toffolis and count 7 T gates per Toffoli. How many T gates does one oracle call use?

Hints

Count three parts: compute the clauses, the AND, uncompute the clauses.
A 2-literal clause is a 2-controlled X: $2\cdot2 - 3 = 1$ Toffoli. The AND is a 8-controlled X: $2\cdot8 - 3 = 13$ .

Show the answer

Answer: $203$

Clauses: $8 \times 1 = 8$ Toffolis to compute and as many to uncompute. The AND: $13$ . Total $16 + 13 = 29$ Toffolis, so $7 \times 29 = 203$ T gates per call.

Common slips

$147$ : That leaves out the uncompute. The clause gadgets run a second time, in reverse, to clear the work qubits, and that costs as many Toffolis again.
$119$ : The AND of 8 clause qubits is a 8-controlled X, which takes $2\cdot8 - 3 = 13$ Toffolis, not one.
$91$ : That counts only the AND. Every clause gadget is a multi-controlled X too, run once to compute and once to uncompute.
$29$ : That is the number of Toffolis. Each one needs 7 T gates: $7 \times 29 = 203$ .

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.

How do you build an honest phase oracle for a CNF formula?
Show the key points
- One work qubit per clause. Each OR clause by De Morgan: a Toffoli fires where every literal is false (anti-control for $x$ , control for $\lnot x$ ), then an X on the work qubit
- The AND of the clause qubits flips an output qubit in $\ket-$ , which kicks back $(-1)^{\varphi(x)}$ (or a multi-controlled Z does it directly)
- Uncompute the clauses, so the work qubits return to $\ket{0\ldots0}$ and only the sign is left
How many iterations does Grover run on it, and how do you read the answer?
Show the key points
- About $\tfrac{\pi}{4}\sqrt{N/M}$ for $N = 2^n$ assignments and $M$ solutions
- Measure the variable qubits; Qiskit prints qubit 0 on the right, so read the strings backwards
- Check each candidate against the formula, which is quick
What does the whole search cost, compared with brute force?
Show the key points
- Per call: $4m - 3$ Toffolis for $m$ two-literal clauses, 7 T gates each
- About $2^{n/2}$ calls against up to $2^n$ checks: a square root, still exponential
- Slow quantum steps mean it wins only past a break-even size, such as $n = 40$ in the worked example

Part 2 in review

This lesson closes Part 2. Across its eight lessons you have learned to:

approximate any operation with a small universal gate set, and count what a circuit costs;
write and run circuits as Qiskit code, read its bit order, and see where simulation runs out;
compute, copy and uncompute, so that work qubits never spoil interference;
count oracle queries, and find a hidden string with a single query;
uncover a hidden XOR pattern with exponentially fewer queries than any classical method, by solving equations over bits;
find a marked item among $N$ in about $\sqrt N$ steps, seen as a rotation;
boost any algorithm’s chance of success, even when you don’t know the odds;
turn a logic puzzle into an honest oracle, and work out what a quantum search really costs.

Until the next lessons arrive, your spaced reviews will keep Parts 1 and 2 fresh.

Key ideas

SAT asks for an assignment that satisfies every clause of a CNF formula. Checking one is quick; brute force tries up to $2^n$ . SAT is NP-complete.
An honest oracle checks the clauses on its input. An oracle written from the list of solutions presupposes the answer.
An OR clause is one Toffoli by De Morgan: fire where every literal is false, then flip the work qubit.
Compute, phase, uncompute: $\ket x\ket{0\ldots0} \to (-1)^{\varphi(x)}\ket x\ket{0\ldots0}$ . Leftover clause values would block the interference.
Cost: Toffolis and T gates per call, times about $\tfrac{\pi}{4}\sqrt{N/M}$ calls. A square-root speed-up, still exponential, and ahead of brute force only for large $n$ .

Go further

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

PhaseOracleGateQiskit documentation · Article
Qiskit’s ready-made version of this lesson’s circuits: a phase oracle built from a logical expression or a CNF file.
Focus beyond quadratic speedups for error-corrected quantum advantageRyan Babbush and others · Article
Careful runtime estimates for error-corrected machines, concluding that a quadratic speed-up alone is unlikely to pay off on early ones.
NP-complete problems and physical realityScott Aaronson · Article
A readable survey of proposals, quantum computers among them, for solving NP-complete problems fast, and why none is believed to work.
Boolean satisfiability problemWikipedia · Article
SAT in depth: CNF, why 2-SAT is easy and 3-SAT is NP-complete, and how practical solvers cope.

Before you start

Logic puzzles as formulas

An honest oracle

One clause from a Toffoli

From clauses to a phase oracle

Worked example: the party oracle on four qubits

Building OOO for the party formula

Another example: (¬x0∨x2)∧(x0∨x1)(\lnot x_0 \lor x_2) \land (x_0 \lor x_1)(¬x0​∨x2​)∧(x0​∨x1​)

The oracle in code

Grover search on the puzzle

Skip the uncompute?

What one oracle call costs

Worked example: when does the square root pay off?

Brute force against Grover, in seconds

Another example: different speeds

Practice

Explain it

Mastery check

Recap

Part 2 in review

Key ideas

Go further

Building $O$ for the party formula

Another example: $(\lnot x_0 \lor x_2) \land (x_0 \lor x_1)$