Unstructured search finds an input producing a desired output when the search space offers no exploitable organization. Given a black-box function with N possible inputs, Grover’s algorithm uses O(√N) queries instead of O(N) classically. section 1.3.1
Treat the problem as a hybrid quantum-classical workflow:
- Prepare and convert the classical problem data for the quantum subroutine. section 7.0
- Represent the target function with an oracle; phase oracles encode function values in amplitude signs, while marking oracles use an additional qubit. section 7.4
- Run Grover’s algorithm, interpret its probabilistic result, and classically verify that the returned input satisfies f(x₀) = 1. section 7.4
- Compare query and implementation costs with the best classical approach rather than assuming a practical quantum advantage. section 1.3.1
Black-box function inversion
A deterministic function maps each input bit string to one bit. The task is to find x₀ such that f(x₀) = 1, without using information about the function’s internal implementation. Hash inversion illustrates a search setting where exploitable classical structure may be unavailable. section 7.4 section 1.3.1
Figure 7.1 Solving a classical problem on a quantum computer involves converting the problem to its “quantum” formulation, implementing the quantum algorithm as code, and evaluating the performance of the quantum solution to compare it to that of the classical algorithms for solving the same problem.
Follow the workflow from classical problem formulation to quantum implementation and performance evaluation. section 7.0
