A bit oracle is a quantum circuit that marks selected, or “good,” outcomes by entangling them with an extra tag qubit. After the oracle runs, good outcomes are associated with a tag measurement of 1; bad outcomes are associated with 0. It plays the role of a predicate or SQL WHERE clause: define which candidates satisfy a condition, then let a larger quantum procedure use that marking. section 5.1 section 5.0 section 5.5
Figure 5.4 The effect of a bit oracle on the amplitudes of a state with good outcomes g and bad outcomes b
The state view makes the tag-bit effect visible: amplitudes for marked outcomes appear in the tag-1 half, while unmarked outcomes remain associated with tag 0. section 5.1.2
For an n-qubit item register representing N = 2ⁿ items, adding the tag qubit creates 2N possible outcomes. With the tag qubit added last, its digit is the leftmost binary digit: an item’s tag-1 amplitude is found at index N + item. A simple classical model extends the state with N zero amplitudes, tests each item with a predicate, and moves the amplitude of each matching item into its tag-1 position. section 5.1.2
Marking item 3 in a three-qubit state
Prepare three item qubits in equal superposition, use a predicate that accepts only 3, then apply the bit oracle. The marked outcome 3 has nonzero amplitude with tag bit 1. The same pattern works for several good items, such as 1, 3, and 5: tag-1 outcomes have nonzero amplitudes only when their item is good. section 5.1.2 section 5.2.3
A circuit implementation allocates an n-qubit item register and one ancilla qubit. For each good item, X gates temporarily map its zero-valued bits into the control pattern required by a multi-controlled X gate; that gate flips the ancilla only for the matching item, and the X gates are undone. This constructs the tag without changing the intended item encoding. section 5.2.3
Bit and phase oracles are interchangeable circuit forms. A phase oracle can be converted to a bit oracle by placing Hadamards around the ancilla and applying the phase-oracle circuit with that ancilla as an added control. Conversely, applying a bit oracle, a π phase to its tag qubit, and the bit oracle again produces phase-oracle behavior, rotating good amplitudes by 180°. section 5.3.1 section 5.3.2
This marking is useful when searching for specified outcomes or estimating their probabilities. In unstructured search, oracle construction is the difficult part: once outcomes are tagged, Grover’s algorithm can increase the probability of measuring them. section 5.0 section 6.1.1
