Oracles and Arithmetic

7.1 Reversible Predicates

Our predicate takes three bits and returns one. To evaluate it with unitary gates, we cannot simply replace the inputs with the output, because that would discard information. Instead we keep the inputs and add the answer to a fourth qubit. We first choose the gates, then state and test the contract for every value of that fourth qubit.

7.1.1 Boolean evaluation

Which gates add \(ab\oplus c\) to a target qubit? We place \(a,b,c\) on qubits 0, 1 and 2 and the target on qubit 3. The function is an XOR of two terms, and flipping a bit twice is the same as flipping it by the XOR of the two reasons. So we can handle each term with its own gate.

The term \(ab\) is an AND, and a Toffoli controlled by qubits 0 and 1 flips the target exactly when \(ab=1\). The term \(c\) needs a CNOT from qubit 2. Together they send the target \(t\) to \(t\oplus ab\oplus c\) and leave the inputs untouched. This predicate needs no ancilla.

A larger predicate would. For \((a\wedge b)\wedge(c\vee d)\), say, the intermediate values need ancillas, and we use the pattern we met for the three-input AND. We compute the intermediate values into clean ancillas, copy the final value into the target with a CNOT, and then reverse the computing gates so the ancillas return to \(\ket0\). This pattern is called compute–copy–uncompute.

7.1.2 Answer registers and retained inputs

Suppose we test the circuit on the eight inputs with target 0, and the target always ends as \(f\). Is the oracle correct? Not necessarily. A circuit that first resets the target and then computes \(f\) passes every one of those tests. On target 1, though, it returns \(f\) instead of \(1\oplus f\), and since it contains a reset it is not even unitary. The answer operation of an oracle is XOR, not assignment, so the contract must hold for target 0 and target 1.

So we check all \(2^4=16\) basis inputs. Column \(k\) of the circuit’s matrix is its output for basis input \(k\), and the expected output is the same basis state with the target bit flipped when \(f=1\). How does a program compute that? An integer from 0 to 15 holds the four qubit values as its binary digits, with qubit 0 as the least significant digit, exactly as in our bit-order convention. Python’s bitwise operators act on those digits. To read qubit \(k\), we shift the digits right by \(k\) places with index >> k, which drops the lowest \(k\) digits. Then & 1 keeps only the lowest remaining digit, so (index >> k) & 1 is the value of qubit \(k\). To write the target, we need the opposite shift: f << 3 moves \(f\) to digit 3, giving 8 when \(f=1\) and 0 otherwise. Finally ^ is XOR applied digit by digit.

So index ^ (f << 3) flips the target’s digit exactly when \(f=1\). In the companion, for index in range(16): repeats its indented body for each index from 0 to 15. The line a, b, c = … assigns three names at once from three values. matrix[:, index] selects column index, where the colon means “all rows,” and np.eye(16)[:, expected] is the basis vector we expect.

Why compare whole columns rather than probabilities? A linear operator is fixed by what it does to the basis states, including the phases of the outputs. An extra Z on one qubit changes no basis probability, yet it changes the column’s sign, and the column test catches it.

7.2 Arithmetic Circuits

Our predicate used only AND and XOR. Algorithms often need oracles that do arithmetic, adding or comparing integers stored in qubits. An integer on qubits has a fixed number of digits, and arithmetic usually needs intermediate values. So we must decide what happens when a result does not fit, and where the intermediate values live. We start with addition and comparison, then turn to width and workspace.

7.2.1 Addition and comparison

How do we add 1 to a two-bit number \(x=x_0+2x_1\) with reversible gates? In ordinary binary addition the low digit always flips, and the high digit flips exactly when the low digit was 1, because that produces a carry. The order of gates matters: the carry depends on the low digit’s old value. So we first apply a CNOT from qubit 0 to qubit 1, and only then an X on qubit 0. Checking the four inputs: \(0\to1\), \(1\to2\), \(2\to3\), and \(3\to0\).

The last case shows that the circuit computes addition modulo 4. It has to: it is a permutation of four basis states, so it cannot produce a fifth. If we want to keep the overflow, we must add a qubit for it. Either choice is legitimate, but the program must make it explicitly. The bit width is part of the function.

Comparison follows the compute–copy–uncompute pattern. To decide whether \(a<b\), we compute \(a-b\) and look at whether the subtraction needs a borrow from beyond the top digit. We copy that borrow flag into the target, then reverse the subtraction to restore the workspace.

7.2.2 Precision and workspace requirements

What if the numbers are not integers? A common choice is fixed point: store an integer \(m\) and read it as \(m/2^k\). With 4 bits and \(k=2\), the representable values are \(0,0.25,0.5,\dots,3.75\). Adding a bit can extend the range or refine the spacing, so changing the width changes both range and precision.

Arithmetic also needs space. Carries, comparison flags and partial products each need wires, and each must be uncomputed. If we report only the final gate that writes the answer, we hide most of the oracle’s cost. The same holds when an oracle looks up values in a finite table. Loading the table, or reading from it, needs a circuit of its own, with its own cost.

7.3 Phase Oracles

Search and many other algorithms do not want \(f(x)\) written in a target. They want each input’s amplitude multiplied by \((-1)^{f(x)}\). Can our bit oracle provide that sign without a new circuit? If it can, we must test the signs, and a histogram cannot see a sign. We derive the phase form first, then test it and count its cost.

7.3.1 Compute, phase, and uncompute

Suppose the target starts in \(\ket-=(\ket0-\ket1)/\sqrt2\) instead of a basis state. The bit oracle sends \(\ket x\ket0\) to \(\ket x\ket{f(x)}\) and \(\ket x\ket1\) to \(\ket x\ket{1\oplus f(x)}\), so \[U_f\ket x\ket-=\ket x\,\frac{\ket{f(x)}-\ket{1\oplus f(x)}}{\sqrt2}=(-1)^{f(x)}\ket x\ket-.\] When \(f(x)=0\) nothing changes, and when \(f(x)=1\) the two terms swap, which flips the sign. The target is unchanged, and the sign has moved onto the input. This is called phase kickback, and \(U_f\) used this way is a phase oracle.

In a larger predicate, the ancillas must be uncomputed before this works. A retained ancilla would carry \(f\)-dependent values, and the input state would not factor away from the workspace.

To test it, the companion prepares all eight inputs with equal amplitude, using H on qubits 0, 1 and 2. It prepares \(\ket-\) on the target with X and then H. Each input amplitude is \(1/\sqrt8\) and each target amplitude is \(\pm1/\sqrt2\), so after the oracle the amplitude of basis index \(k\) should be \[\frac{(-1)^{f(a,b,c)\oplus t}}{4},\] where \(t\) is the target bit of \(k\). The code builds this list of 16 numbers. The expression [(index >> k) & 1 for k in range(4)] is a list comprehension: it makes a list from the expression before for, evaluated at each \(k\). Here it gives the four bits of index. Starting from the empty list [], the method append adds one expected amplitude per index.

7.3.2 Superposition tests and resource counts

Why insist on comparing amplitudes? In this state every one of the 16 amplitudes has magnitude \(1/4\). So every basis probability is \(1/16\), whatever \(f\) is. A histogram of measured counts would look the same for the correct oracle, for a wrong one, and for no oracle at all. Only the signs carry \(f\), and the companion compares all 16 complex amplitudes at once. That one test checks every sign and also checks that the target ends in \(\ket-\), unentangled from the inputs.

What does the oracle cost? Logically, one Toffoli and one CNOT, plus the preparation and any readout. A Toffoli is not native on most devices. Compiled to CNOTs and one-qubit gates, it takes 6 CNOTs. So a resource report should give both the logical count and the compiled count. Because its contract is simple, inputs kept and target XORed, the oracle can serve as a component in search, in phase encoding, or in a larger arithmetic circuit.

"""Runnable companion for Quantum Programming, Chapter 7."""
import numpy as np
from qiskit import QuantumCircuit
from qiskit.quantum_info import Operator, Statevector

# f(a,b,c) = ab XOR c; q0=a, q1=b, q2=c, q3=target.
qc = QuantumCircuit(4)
qc.ccx(0, 1, 3)
qc.cx(2, 3)
matrix = Operator(qc).data
for index in range(16):
    a, b, c = index & 1, (index >> 1) & 1, (index >> 2) & 1
    expected = index ^ (((a & b) ^ c) << 3)
    assert np.allclose(matrix[:, index], np.eye(16)[:, expected])
# Target minus makes the same oracle a phase oracle.
prep = QuantumCircuit(4)
prep.h([0, 1, 2])
prep.x(3)
prep.h(3)
state = Statevector.from_instruction(prep.compose(qc))
expected = []
for index in range(16):
    a, b, c, target = [(index >> k) & 1 for k in range(4)]
    expected.append((-1)**((a & b) ^ c ^ target) / 4)
assert np.allclose(state.data, expected)
print("All basis columns and coherent signs verified")

Companion script: chapter_07.py.

With an oracle we can build and verify, the algorithms we studied abstractly become possible to program. What does each of them add to the code beyond its oracle?

Sources and further study: IBM, circuit API.