A quantum oracle is a circuit that recognizes outcomes satisfying a chosen condition and tags them as good; all other outcomes are bad. It plays the role of a SQL WHERE clause: the condition specifies what to find, but designing an efficient quantum implementation is the difficult part. section 5.0
Two common tags encode the same good-versus-bad distinction differently. A phase oracle rotates each good outcome’s amplitude by 180°, equivalently multiplying it by −1. A bit oracle entangles outcomes with an ancilla qubit, so good outcomes are associated with measuring 1 and bad outcomes with measuring 0. The two forms can be converted into one another. section 5.1 section 5.5
Build an oracle around the condition that defines a desired outcome:
- Represent the outcomes to match as a list of good binary-state indices. section 5.2.3
- For each target index, apply X gates to qubits whose corresponding target bits are 0, so a multi-controlled operation can match that state. section 6.2.1
- Apply a multi-controlled phase operation for a phase oracle, or target an extra ancilla qubit for a bit oracle; then undo the X gates. section 5.2.3 section 6.2.1
- Use the tagged outcomes as input to amplitude amplification or Grover’s algorithm, which raises their measurement probability. section 6.3
Marking outcomes 1, 3, and 5
Prepare a three-qubit state with Hadamard gates, then apply a bit oracle whose good-outcome list is [1, 3, 5]. Afterward, states paired with ancilla value 1 have nonzero amplitude only when their three-qubit outcome is good. For a phase-oracle version, the matching outcomes instead receive a −1 amplitude factor. section 5.2.3 section 6.1.1
Oracles are reusable selectors rather than complete search procedures. In unstructured search, the oracle marks candidate items and the Grover inversion step amplifies marked amplitudes. For function-encoded states, simple digit-matching oracles can select outputs in a range, including positive or negative values represented with Two’s Complement. section 6.3 section 10.2
Listing 5.4 Function to create a bit oracle circuit
def bit_oracle_match(n, items):
q = QuantumRegister(n)
a = QuantumRegister(1)
qc = QuantumCircuit(q, a)
for m in items:
for i in range(n):
if is_bit_not_set(m, i):
qc.x(q[i])
qc.mcx([q[i] for i in range(len(q))], a[0]) #1
for i in range(n):
if is_bit_not_set(m, i):
qc.x(q[i])
return qc
This circuit constructs a bit oracle for listed state indices. It allocates an ancilla, maps each desired bit pattern to the all-ones control pattern, applies a multi-controlled X to the ancilla, and restores the data qubits. section 5.2.3
