qiskit.algorithms.Grover¶

class
Grover
(iterations=None, growth_rate=None, sample_from_iterations=False, quantum_instance=None)[source]¶ Grover’s Search algorithm.
Grover’s Search [1, 2] is a well known quantum algorithm for that can be used 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 unstructuredsearch problem is to find an element \(x^* \in X\) such that \(f(x^*)=1\).
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)\) worstcase time. Instead, in an unstructuredsearch 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 unstructuredsearch problem on a quantum computer in \(\mathcal{O}(\sqrt{N})\) queries.
To carry out this search a socalled oracle is required, that flags a good element/state. The action of the oracle \(\mathcal{S}_f\) is
\[\mathcal{S}_f x\rangle = (1)^{f(x)} x\rangle,\]i.e. it flips the phase of the state \(x\rangle\) if \(x\) is a hit. The details of how \(S_f\) works are unimportant to the algorithm; Grover’s search algorithm treats the oracle as a black box.
This class supports oracles in form of
QuantumCircuit
With oracle at hand, Grover’s Search constructs the Grover operator to amplify the amplitudes of the good states:
\[\mathcal{Q} = H^{\otimes n} \mathcal{S}_0 H^{\otimes n} \mathcal{S}_f = D \mathcal{S}_f,\]where \(\mathcal{S}_0\) flips the phase of the allzero state and acts as identity on all other states. Sometimes the first three operands are summarized as diffusion operator, which implements a reflection over the equal superposition state.
If the number of solutions is known, we can calculate how often \(\mathcal{Q}\) should be applied to find a solution with very high probability, see the method optimal_num_iterations. If the number of solutions is unknown, the algorithm tries different powers of Grover’s operator, see the iterations argument, and after each iteration checks if a good state has been measured using good_state.
The generalization of Grover’s Search, Quantum Amplitude Amplification [3] uses a modified version of \(\mathcal{Q}\) where the diffusion operator does not reflect about the equal superposition state, but another state specified via an operator \(\mathcal{A}\):
\[\mathcal{Q} = \mathcal{A} \mathcal{S}_0 \mathcal{A}^\dagger \mathcal{S}_f.\]For more information, see the
GroverOperator
in the circuit library.References
 [1]: L. K. Grover (1996), A fast quantum mechanical algorithm for database search,
 [2]: I. Chuang & M. Nielsen, Quantum Computation and Quantum Information,
Cambridge: Cambridge University Press, 2000. Chapter 6.1.2.
 [3]: Brassard, G., Hoyer, P., Mosca, M., & Tapp, A. (2000).
Quantum Amplitude Amplification and Estimation. arXiv:quantph/0005055.
 Parameters
iterations (
Union
[List
[int
],Iterator
[int
],int
,None
]) – Specify the number of iterations/power of Grover’s operator to be checked. * If an int, only one circuit is run with that power of the Grover operator. If the number of solutions is known, this is option should be used with the optimal power. The optimal power can be computed withGrover.optimal_num_iterations
. * If a list, all the powers in the list are run in the specified order. * If an iterator, the powers yielded by the iterator are checked, until a maximum number of iterations or maximum power is reached.growth_rate (
Optional
[float
]) – If specified, the iterator is set to increasing powers ofgrowth_rate
, i.e. toint(growth_rate ** 1), int(growth_rate ** 2), ...
until a maximum number of iterations is reached.sample_from_iterations (
bool
) – If True, instead of taking the values initerations
as powers of the Grover operator, a random integer sample between 0 and smaller value than the iteration is used as a power, see [1], Section 4.quantum_instance (
Union
[Backend
,BaseBackend
,QuantumInstance
,None
]) – A Quantum Instance or Backend to run the circuits.
 Raises
ValueError – If
growth_rate
is a float but not larger than 1.ValueError – If both
iterations
andgrowth_rate
is set.
References
 [1]: Boyer et al., Tight bounds on quantum searching

__init__
(iterations=None, growth_rate=None, sample_from_iterations=False, quantum_instance=None)[source]¶  Parameters
iterations (
Union
[List
[int
],Iterator
[int
],int
,None
]) – Specify the number of iterations/power of Grover’s operator to be checked. * If an int, only one circuit is run with that power of the Grover operator. If the number of solutions is known, this is option should be used with the optimal power. The optimal power can be computed withGrover.optimal_num_iterations
. * If a list, all the powers in the list are run in the specified order. * If an iterator, the powers yielded by the iterator are checked, until a maximum number of iterations or maximum power is reached.growth_rate (
Optional
[float
]) – If specified, the iterator is set to increasing powers ofgrowth_rate
, i.e. toint(growth_rate ** 1), int(growth_rate ** 2), ...
until a maximum number of iterations is reached.sample_from_iterations (
bool
) – If True, instead of taking the values initerations
as powers of the Grover operator, a random integer sample between 0 and smaller value than the iteration is used as a power, see [1], Section 4.quantum_instance (
Union
[Backend
,BaseBackend
,QuantumInstance
,None
]) – A Quantum Instance or Backend to run the circuits.
 Raises
ValueError – If
growth_rate
is a float but not larger than 1.ValueError – If both
iterations
andgrowth_rate
is set.
References
 [1]: Boyer et al., Tight bounds on quantum searching
Methods
__init__
([iterations, growth_rate, …]) type iterations
Union
[List
[int
],Iterator
[int
],int
,None
]
amplify
(amplification_problem)Run the Grover algorithm.
construct_circuit
(problem[, power, measurement])Construct the circuit for Grover’s algorithm with
power
Grover operators.optimal_num_iterations
(num_solutions, num_qubits)Return the optimal number of iterations, if the number of solutions is known.
Attributes
Get the quantum instance.

amplify
(amplification_problem)[source]¶ Run the Grover algorithm.
 Parameters
amplification_problem (
AmplificationProblem
) – The amplification problem. Return type
GroverResult
 Returns
The result as a
GroverResult
, where e.g. the most likely state can be queried asresult.top_measurement
.

construct_circuit
(problem, power=None, measurement=False)[source]¶ Construct the circuit for Grover’s algorithm with
power
Grover operators. Parameters
problem (
AmplificationProblem
) – The amplification problem for the algorithm.power (
Optional
[int
]) – The number of times the Grover operator is repeated. If None, this argument is set to the first item initerations
.measurement (
bool
) – Boolean flag to indicate if measurement should be included in the circuit.
 Returns
the QuantumCircuit object for the constructed circuit
 Return type
 Raises
ValueError – If no power is passed and the iterations are not an integer.

static
optimal_num_iterations
(num_solutions, num_qubits)[source]¶ Return the optimal number of iterations, if the number of solutions is known.
 Parameters
num_solutions (
int
) – The number of solutions.num_qubits (
int
) – The number of qubits used to encode the states.
 Return type
int
 Returns
The optimal number of iterations for Grover’s algorithm to succeed.

property
quantum_instance
¶ Get the quantum instance. :rtype:
Optional
[QuantumInstance
] :returns: The quantum instance used to run this algorithm.