A good outcome is a computational-basis outcome selected by an oracle’s condition. The condition separates outcomes of interest from bad outcomes; it does not require the oracle’s implementation to reveal how that condition is used later. A classical predicate can specify the selected items by returning true for matches and false otherwise. section 5.1 section 5.1.1
A phase oracle marks each good outcome by rotating its amplitude 180 degrees, equivalently multiplying it by −1. A bit oracle instead adds a tag bit: good outcomes have nonzero amplitude with tag value 1, while bad outcomes have zero amplitude in that tagged half. A bit oracle can support a phase-oracle implementation because it already identifies the good outcomes. section 5.1 section 5.1.2
To implement a match against listed good outcomes, an oracle circuit can:
- Use a phase oracle that applies a multi-controlled phase transformation after X gates align the target bit pattern, then reverses those X gates. section 5.2.2
- Use a bit oracle with an ancillary qubit and a multi-controlled X transformation to mark matching outcomes in the tag bit. section 5.2.3
One marked outcome in an eight-item state
With three qubits in equal superposition, outcome 3 can be the sole good outcome. A phase oracle changes only its amplitude’s phase. A bit oracle instead moves its corresponding amplitude to the state indexed by outcome 3 with tag bit 1. The same predicate-based setup supports a search example where repeated Grover iterations increase the probability of measuring the marked outcome. section 5.1.1 section 5.1.2 section 6.1.4
Figure 6.17 The combined measurement probabilities of good and bad outcomes before and after j applications of the Grover iterate
This probability table distinguishes the combined probability of all good outcomes from that of bad outcomes as Grover iterations proceed. section 6.1.4
Good outcomes may form a set rather than a single item. For example, binary strings with no two consecutive 1s are good outcomes; splitting the set by its first digit gives a recurrence whose counts follow the Fibonacci sequence. Such selection criteria can also prepare states where bad outcomes have probability zero. section 5.4
In unstructured search, the oracle’s tags identify the outcomes whose measurement probability should be amplified. Starting from a state prepared by A, each Grover iterate applies the oracle followed by an inversion operator. The combined good-outcome probability changes with the number of iterations, so repeated application can amplify and eventually overshoot the desired outcomes. section 6.1.1 section 6.1.4
