Extended Quantum Computing Patterns

How can you find a specific element ( \tilde{x} ) within an unsorted database of ( N ) elements?

The goal is to find the correct bit string \(\tilde{x} \in \{0,1\}^N\) for which the function [ f: {0,1}^N \rightarrow {0,1} ] [ f(x) = \begin{cases} 0, & x \neq \tilde{x} \ 1, & x = \tilde{x} \end{cases} ] becomes 1 (indicator function). The assumption is that the function itself is provided in the form of an oracle, and any bit string with length \(N\) can be evaluated using it.

–

1. Create the superposition of all possible solutions: [ s = \frac{1}{\sqrt{N}} \sum_{x=0}^{N-1} |x\rangle ] This step involves preparing the quantum system in an equal superposition of all possible states, representing every possible solution.
2. Repeat the following steps until the amplitude of the desired solution \(\tilde{x}\) is "large enough": 2.1. Negate the amplitude of the target solution \(\tilde{x}\): Apply the oracle function that flips the sign of the amplitude corresponding to the target state ( |\(\tilde{x}\)\rangle ). 2.2. Reflect all amplitudes about the current average amplitude: Perform a diffusion operator (also known as the Grover diffusion or inversion about the mean), which reflects the quantum state across the average of all amplitudes. This step amplifies the amplitude of the target solution while reducing the amplitudes of other states.
3. Measure the final quantum state: After repeating the above steps a sufficient number of times, measure the quantum register. The result will likely be the desired solution \(\tilde{x}\).

The solution string \(\tilde{x}\)

–

Unstructured search, optimization problems, and satisfiability problems like 3-KNF-SAT where we want to find a solution to given clauses.