Extended Quantum Computing Patterns

Achieve a computational speedup on computation when verification of a solution is simple.

There are many problems for which finding a solution is hard, but for an alleged solution it is easy to verify whether it is correct. For example, determining the factorization of a certain number is hard when the number is huge, but multiplying prime numbers to verify that their product equals the number is simple. Thus, to check if a list of prime numbers is the factorization of a specific number, multiplying the prime numbers is sufficient to verify the factorization.

–

For certain problems, finding a solution can be done faster by exploiting quantum parallelism: First, all possible solutions are created, then this list of solutions is searched for correct solutions by verifying the correctness of each solution. The Grover algorithm is used for searching through the possible solutions relying on an oracle to verify whether the possible solutions are correct. This means that \(O(\sqrt{N})\) applications of the oracle are needed to determine the solution.

This pattern requires that an oracle is given which can verify the solutions.

–

An Oracle is used to verify solutions. The Grover algorithm used for the scanning increases the probability to measure a correct solution via Amplitude Amplification.

This technique can be applied for e.g., cracking keys, finding Hamiltonian cycles, solving 3-SAT, or the traveling salesman problem.

Grover's Algorithm (PlanQK) Dürr-Høyer Quantum Minimization Algorithm (PlanQK)