189 lines
11 KiB
Plaintext
189 lines
11 KiB
Plaintext
---
|
||
title: Grover
|
||
description: API reference for qiskit.algorithms.Grover
|
||
in_page_toc_min_heading_level: 1
|
||
python_api_type: class
|
||
python_api_name: qiskit.algorithms.Grover
|
||
---
|
||
|
||
# Grover
|
||
|
||
<Class id="qiskit.algorithms.Grover" isDedicatedPage={true} github="https://github.com/qiskit/qiskit/tree/stable/0.25/qiskit/algorithms/amplitude_amplifiers/grover.py" signature="qiskit.algorithms.Grover(iterations=None, growth_rate=None, sample_from_iterations=False, quantum_instance=None, sampler=None)" modifiers="class">
|
||
Bases: [`AmplitudeAmplifier`](qiskit.algorithms.AmplitudeAmplifier "qiskit.algorithms.amplitude_amplifiers.amplitude_amplifier.AmplitudeAmplifier")
|
||
|
||
Grover’s Search algorithm.
|
||
|
||
<Admonition title="Note" type="note">
|
||
If you want to learn more about the theory behind Grover’s Search algorithm, check out the [Qiskit Textbook](https://qiskit.org/textbook/ch-algorithms/grover.html). or the [Qiskit Tutorials](https://qiskit.org/documentation/tutorials/algorithms/07_grover_examples.html) for more concrete how-to examples.
|
||
</Admonition>
|
||
|
||
Grover’s Search \[1, 2] is a well known quantum algorithm 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 unstructured-search 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)$ 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.
|
||
|
||
To carry out this search a so-called 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 a [`QuantumCircuit`](qiskit.circuit.QuantumCircuit "qiskit.circuit.QuantumCircuit").
|
||
|
||
With the given oracle, 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 all-zero 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`](qiskit.circuit.library.GroverOperator "qiskit.circuit.library.GroverOperator") in the circuit library.
|
||
|
||
**References**
|
||
|
||
**\[1]: L. K. Grover (1996), A fast quantum mechanical algorithm for database search,**
|
||
|
||
[arXiv:quant-ph/9605043](https://arxiv.org/abs/quant-ph/9605043).
|
||
|
||
**\[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:quant-ph/0005055](http://arxiv.org/abs/quant-ph/0005055).
|
||
|
||
<Admonition title="Deprecated since version 0.24.0" type="danger">
|
||
`qiskit.algorithms.amplitude_amplifiers.grover.Grover.__init__()`’s argument `quantum_instance` is deprecated as of qiskit-terra 0.24.0. It will be removed no earlier than 3 months after the release date. Instead, use the `sampler` argument. See [https://qisk.it/algo\_migration](https://qisk.it/algo_migration) for a migration guide.
|
||
</Admonition>
|
||
|
||
**Parameters**
|
||
|
||
* **iterations** ([*list*](https://docs.python.org/3/library/stdtypes.html#list "(in Python v3.12)")*\[*[*int*](https://docs.python.org/3/library/functions.html#int "(in Python v3.12)")*] | Iterator\[*[*int*](https://docs.python.org/3/library/functions.html#int "(in Python v3.12)")*] |* [*int*](https://docs.python.org/3/library/functions.html#int "(in Python v3.12)") *| 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 option should be used with the optimal power. The optimal power can be computed with `Grover.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. \* If `None`, the [`AmplificationProblem`](qiskit.algorithms.AmplificationProblem "qiskit.algorithms.AmplificationProblem") provided must have an `is_good_state`, and circuits are run until that good state is reached.
|
||
* **growth\_rate** ([*float*](https://docs.python.org/3/library/functions.html#float "(in Python v3.12)") *| None*) – If specified, the iterator is set to increasing powers of `growth_rate`, i.e. to `int(growth_rate ** 1), int(growth_rate ** 2), ...` until a maximum number of iterations is reached.
|
||
* **sample\_from\_iterations** ([*bool*](https://docs.python.org/3/library/functions.html#bool "(in Python v3.12)")) – If True, instead of taking the values in `iterations` 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** ([*QuantumInstance*](qiskit.utils.QuantumInstance "qiskit.utils.QuantumInstance") *|*[*Backend*](qiskit.providers.Backend "qiskit.providers.Backend") *| None*) – Deprecated: A Quantum Instance or Backend to run the circuits.
|
||
* **sampler** ([*BaseSampler*](qiskit.primitives.BaseSampler "qiskit.primitives.BaseSampler") *| None*) – A Sampler to use for sampling the results of the circuits.
|
||
|
||
**Raises**
|
||
|
||
* [**ValueError**](https://docs.python.org/3/library/exceptions.html#ValueError "(in Python v3.12)") – If `growth_rate` is a float but not larger than 1.
|
||
* [**ValueError**](https://docs.python.org/3/library/exceptions.html#ValueError "(in Python v3.12)") – If both `iterations` and `growth_rate` is set.
|
||
|
||
**References**
|
||
|
||
**\[1]: Boyer et al., Tight bounds on quantum searching**
|
||
|
||
[https://arxiv.org/abs/quant-ph/9605034](https://arxiv.org/abs/quant-ph/9605034)
|
||
|
||
## Attributes
|
||
|
||
### quantum\_instance
|
||
|
||
<Attribute id="qiskit.algorithms.Grover.quantum_instance">
|
||
Deprecated. Get the quantum instance.
|
||
|
||
<Admonition title="Deprecated since version 0.24.0" type="danger">
|
||
The property `qiskit.algorithms.amplitude_amplifiers.grover.Grover.quantum_instance` is deprecated as of qiskit-terra 0.24.0. It will be removed no earlier than 3 months after the release date. See [https://qisk.it/algo\_migration](https://qisk.it/algo_migration) for a migration guide.
|
||
</Admonition>
|
||
|
||
**Returns**
|
||
|
||
The quantum instance used to run this algorithm.
|
||
</Attribute>
|
||
|
||
### sampler
|
||
|
||
<Attribute id="qiskit.algorithms.Grover.sampler">
|
||
Get the sampler.
|
||
|
||
**Returns**
|
||
|
||
The sampler used to run this algorithm.
|
||
</Attribute>
|
||
|
||
## Methods
|
||
|
||
### amplify
|
||
|
||
<Function id="qiskit.algorithms.Grover.amplify" signature="amplify(amplification_problem)">
|
||
Run the Grover algorithm.
|
||
|
||
**Parameters**
|
||
|
||
**amplification\_problem** ([*AmplificationProblem*](qiskit.algorithms.AmplificationProblem "qiskit.algorithms.amplitude_amplifiers.amplification_problem.AmplificationProblem")) – The amplification problem.
|
||
|
||
**Returns**
|
||
|
||
The result as a `GroverResult`, where e.g. the most likely state can be queried as `result.top_measurement`.
|
||
|
||
**Raises**
|
||
|
||
* [**ValueError**](https://docs.python.org/3/library/exceptions.html#ValueError "(in Python v3.12)") – If a quantum instance or sampler is not set.
|
||
* [**AlgorithmError**](algorithms#qiskit.algorithms.AlgorithmError "qiskit.algorithms.AlgorithmError") – If a sampler job fails.
|
||
* [**TypeError**](https://docs.python.org/3/library/exceptions.html#TypeError "(in Python v3.12)") – If `is_good_state` is not provided and is required (i.e. when iterations
|
||
* **is None**\*\* or ****a list****)\*\* –
|
||
|
||
**Return type**
|
||
|
||
[*GroverResult*](qiskit.algorithms.GroverResult "qiskit.algorithms.amplitude_amplifiers.grover.GroverResult")
|
||
</Function>
|
||
|
||
### construct\_circuit
|
||
|
||
<Function id="qiskit.algorithms.Grover.construct_circuit" signature="construct_circuit(problem, power=None, measurement=False)">
|
||
Construct the circuit for Grover’s algorithm with `power` Grover operators.
|
||
|
||
**Parameters**
|
||
|
||
* **problem** ([*AmplificationProblem*](qiskit.algorithms.AmplificationProblem "qiskit.algorithms.AmplificationProblem")) – The amplification problem for the algorithm.
|
||
* **power** ([*int*](https://docs.python.org/3/library/functions.html#int "(in Python v3.12)") *| None*) – The number of times the Grover operator is repeated. If None, this argument is set to the first item in `iterations`.
|
||
* **measurement** ([*bool*](https://docs.python.org/3/library/functions.html#bool "(in Python v3.12)")) – Boolean flag to indicate if measurement should be included in the circuit.
|
||
|
||
**Returns**
|
||
|
||
the QuantumCircuit object for the constructed circuit
|
||
|
||
**Return type**
|
||
|
||
[QuantumCircuit](qiskit.circuit.QuantumCircuit "qiskit.circuit.QuantumCircuit")
|
||
|
||
**Raises**
|
||
|
||
[**ValueError**](https://docs.python.org/3/library/exceptions.html#ValueError "(in Python v3.12)") – If no power is passed and the iterations are not an integer.
|
||
</Function>
|
||
|
||
### optimal\_num\_iterations
|
||
|
||
<Function id="qiskit.algorithms.Grover.optimal_num_iterations" signature="optimal_num_iterations(num_solutions, num_qubits)" modifiers="static">
|
||
Return the optimal number of iterations, if the number of solutions is known.
|
||
|
||
**Parameters**
|
||
|
||
* **num\_solutions** ([*int*](https://docs.python.org/3/library/functions.html#int "(in Python v3.12)")) – The number of solutions.
|
||
* **num\_qubits** ([*int*](https://docs.python.org/3/library/functions.html#int "(in Python v3.12)")) – The number of qubits used to encode the states.
|
||
|
||
**Returns**
|
||
|
||
The optimal number of iterations for Grover’s algorithm to succeed.
|
||
|
||
**Return type**
|
||
|
||
[int](https://docs.python.org/3/library/functions.html#int "(in Python v3.12)")
|
||
</Function>
|
||
</Class>
|
||
|