Grover

Grover(oracle, init_state=None, incremental=False, num_iterations=1, mct_mode='basic', quantum_instance=None)

The Grover’s Search algorithm.

Grover’s Search is a well known quantum algorithm for searching through unstructured collections of records for particular targets with quadratic speedup compared to classical algorithms.

Given a set $X$ of $N$ elements $X=\{x_1,x_2,\ldots,x_N\}$ and a boolean function $f : X \rightarrow \{0,1\}$, the goal of an unstructured-search problem is to find an element $x^* \in X$ such that $f(x^*)=1$.

Unstructured search is often alternatively formulated as a database search problem, in which, given a database, the goal is to find in it an item that meets some specification.

The search is called unstructured because there are no guarantees as to how the database is ordered. On a sorted database, for instance, one could perform binary search to find an element in $\mathbb{O}(\log N)$ worst-case time. Instead, in an unstructured-search problem, there is no prior knowledge about the contents of the database. With classical circuits, there is no alternative but to perform a linear number of queries to find the target element. Conversely, Grover’s Search algorithm allows to solve the unstructured-search problem on a quantum computer in $\mathcal{O}(\sqrt{N})$ queries.

All that is needed for carrying out a search is an oracle from Aqua’s oracles module for specifying the search criterion, which basically indicates a hit or miss for any given record. More formally, an oracle $O_f$ is an object implementing a boolean function $f$ as specified above. Given an input $x \in X$, $O_f$ implements $f(x)$. The details of how $O_f$ works are unimportant; Grover’s search algorithm treats the oracle as a black box.

For example the LogicalExpressionOracle can take as input a SAT problem in DIMACS CNF format(opens in a new tab) and be used with Grover algorithm to find a satisfiable assignment.

Parameters

• oracle (Oracle) – The oracle component
• init_state (Optional[InitialState]) – An optional initial quantum state. If None (default) then Grover’s Search by default uses uniform superposition to initialize its quantum state. However, an initial state may be supplied, if useful, for example, if the user has some prior knowledge regarding where the search target(s) might be located.
• incremental (bool) – Whether to use incremental search mode (True) or not (False). Supplied num_iterations is ignored when True and instead the search task will be carried out in successive rounds, using circuits built with incrementally higher number of iterations for the repetition of the amplitude amplification until a target is found or the maximal number $\log N$ ($N$ being the total number of elements in the set from the oracle used) of iterations is reached. The implementation follows Section 4 of Boyer et al. <https://arxiv.org/abs/quant-ph/9605034(opens in a new tab)>
• num_iterations (int) – How many times the marking and reflection phase sub-circuit is repeated to amplify the amplitude(s) of the target(s). Has a minimum value of 1.
• mct_mode (str) – Multi-Control Toffoli mode (‘basic’ | ‘basic-dirty-ancilla’ | ‘advanced’ | ‘noancilla’)
• quantum_instance (Union[QuantumInstance, BaseBackend, None]) – Quantum Instance or Backend

Raises

AquaError – evaluate_classically() missing from the input oracle

Attributes

backend

qc_amplitude_amplification_iteration

quantum_instance

random

Methods

construct_circuit

run

set_backend