A search problem asks for an input x satisfying a specified condition, commonly represented by a Boolean function f(x) that returns 1 for solutions and 0 otherwise. The formulation separates the problem instance from the generic search procedure: a quantum oracle implements f(x), while Grover’s algorithm supplies the search logic. section 7.1 section 8.0
A quantum implementation follows a concrete representation-and-testing workflow:
- Choose how to encode candidate inputs x and calculate f(x) classically. section 8.0
- Convert the classical calculation into reversible computation and implement a marking oracle. section 8.0
- Prepare the search space, apply Grover’s search, then test the complete program and inspect its results. section 8.0 section 6.0
- Reduce the search space or improve input encoding when constraints permit, balancing qubit count, program length, and simulator cost. section 8.5
Constraint search
Boolean satisfiability searches for an assignment that makes a Boolean expression true. The N queens puzzle similarly searches candidate board placements, marking those with queens in distinct rows, columns, and diagonals. A simpler oracle marks the three-bit strings 001 and 110. section 6.0 section 8.0 section 7.1
Figure 8.1 Solving a search problem using Grover’s algorithm starts with deciding on the representation of the function input \(x\) and the way to calculate the function \(f(x)\) based on it. Then, we implement the marking oracle for this function and the operation that prepares the state \(\ket{\textrm{mean}}\) based on that decision. Finally, these building blocks are used in Grover’s search to get the end-to-end solution.
Use the workflow diagram to connect input encoding, classical evaluation, oracle construction, search-space preparation, and Grover’s algorithm. section 8.0
