Extended Quantum Computing Patterns

Re-use a computation of a quantum algorithm without necessarily knowing the implementation.

A Divide-and-Conquer approach is a commonly used method that simplifies solving a complex problem.
In such an approach, an oracle can be used as an reusable part of a quantum algorithm - a black blox with hidden internals. Multiple oracles can be used as building blocks to compose larger algorithms.

–

The concrete implementation of an oracle is highly problem-specific. As a consequence, there are many different types of oracles, of which several are discussed in (Gilyen et al. 2019).

Concrete implementations of oracles add to the overall depth to the overall quantum algorithm but are often neglected in the runtime of an oracle-based algorithm.

–

An oracle requires correct Initialization of the problem-specific input. Typically, an Uncompute is used after an oracle was applied.

Oracles are used in the algorithms of Deutsch, Deutsch-Jozsa, Bernstein-Vazirani, Simon, Grover, and many others. In (Mosca 2008), further usages are given.

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