242 lines
13 KiB
Plaintext
242 lines
13 KiB
Plaintext
---
|
||
title: Grover
|
||
description: API reference for qiskit.aqua.algorithms.Grover
|
||
in_page_toc_min_heading_level: 1
|
||
python_api_type: class
|
||
python_api_name: qiskit.aqua.algorithms.Grover
|
||
---
|
||
|
||
# Grover
|
||
|
||
<Class id="qiskit.aqua.algorithms.Grover" isDedicatedPage={true} github="https://github.com/qiskit-community/qiskit-aqua/tree/stable/0.9/qiskit/aqua/algorithms/amplitude_amplifiers/grover.py" signature="Grover(oracle, good_state=None, state_preparation=None, iterations=1, sample_from_iterations=False, post_processing=None, grover_operator=None, quantum_instance=None, init_state=None, incremental=False, num_iterations=None, lam=None, rotation_counts=None, mct_mode=None)" modifiers="class">
|
||
Bases: `qiskit.aqua.algorithms.quantum_algorithm.QuantumAlgorithm`
|
||
|
||
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 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 `QuantumCircuit` or [`Oracle`](qiskit.aqua.components.oracles.Oracle "qiskit.aqua.components.oracles.Oracle"). For example the [`LogicalExpressionOracle`](qiskit.aqua.components.oracles.LogicalExpressionOracle "qiskit.aqua.components.oracles.LogicalExpressionOracle") can take as input a SAT problem in [DIMACS CNF format](http://www.satcompetition.org/2009/format-benchmarks2009.html) and be used with Grover algorithm to find a satisfiable assignment.
|
||
|
||
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 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).
|
||
|
||
**Parameters**
|
||
|
||
* **oracle** (`Union`\[`Oracle`, `QuantumCircuit`, `Statevector`]) – The oracle to flip the phase of good states, $\mathcal{S}_f$.
|
||
* **good\_state** (`Union`\[`Callable`\[\[`str`], `bool`], `List`\[`int`], `List`\[`str`], `Statevector`, `None`]) – A callable to check if a given measurement corresponds to a good state. For convenience, a list of bitstrings, a list of integer or statevector can be passed instead of a function. If the input is a list of bitstrings, each bitstrings in the list represents a good state. If the input is a list of integer, each integer represent the index of the good state to be $|1\rangle$. If it is a [`Statevector`](qiskit.quantum_info.Statevector "qiskit.quantum_info.Statevector"), it represents a superposition of all good states.
|
||
* **state\_preparation** (`Optional`\[`QuantumCircuit`]) – The state preparation $\mathcal{A}$. If None then Grover’s Search by default uses uniform superposition.
|
||
* **iterations** (`Union`\[`int`, `List`\[`int`]]) – Specify the number of iterations/power of Grover’s operator to be checked. It the number of solutions is known, this should be an integer specifying the optimal number of iterations (see `optimal_num_iterations`). Alternatively, this can be a list of powers to check.
|
||
* **sample\_from\_iterations** (`bool`) – 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.
|
||
* **post\_processing** (`Optional`\[`Callable`\[\[`List`\[`int`]], `List`\[`int`]]]) – An optional post processing applied to the top measurement. Can be used e.g. to convert from the bit-representation of the measurement \[1, 0, 1] to a DIMACS CNF format \[1, -2, 3].
|
||
* **grover\_operator** (`Optional`\[`QuantumCircuit`]) – A circuit implementing the Grover operator $\mathcal{Q}$. If None, the operator is constructed automatically using the [`GroverOperator`](qiskit.circuit.library.GroverOperator "qiskit.circuit.library.GroverOperator") from the circuit library.
|
||
* **quantum\_instance** (`Union`\[`QuantumInstance`, `Backend`, `BaseBackend`, `None`]) – A Quantum Instance or Backend to run the circuits.
|
||
* **init\_state** (`Optional`\[`InitialState`]) – DEPRECATED, use `state_preparation` instead. 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`) – DEPRECATED, use `iterations` instead. 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 \[2].
|
||
* **num\_iterations** (`Optional`\[`int`]) – DEPRECATED, use `iterations` instead. 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.
|
||
* **lam** (`Optional`\[`float`]) – DEPRECATED, use `iterations` instead. For incremental search mode, the maximum number of repetition of amplitude amplification increases by factor lam in every round, $R_{i+1} = lam \times R_{i}$. If this parameter is not set, the default value lam = 1.34 is used, which is proved to be optimal \[1].
|
||
* **rotation\_counts** (`Optional`\[`List`\[`int`]]) – DEPRECATED, use `iterations` instead. For incremental mode, if rotation\_counts is defined, parameter *lam* is ignored. rotation\_counts is the list of integers that defines the number of repetition of amplitude amplification for each round.
|
||
* **mct\_mode** (`Optional`\[`str`]) – DEPRECATED, pass a custom `grover_operator` instead. Multi-Control Toffoli mode (‘basic’ | ‘basic-dirty-ancilla’ | ‘advanced’ | ‘noancilla’)
|
||
|
||
**Raises**
|
||
|
||
* **TypeError** – If `init_state` is of unsupported type or is of type ```InitialState` but the oracle is not of type ``Oracle```.
|
||
* [**AquaError**](qiskit.aqua.AquaError "qiskit.aqua.AquaError") – evaluate\_classically() missing from the input oracle
|
||
* **TypeError** – If `oracle` is of unsupported type.
|
||
|
||
**References**
|
||
|
||
**\[1]: Boyer et al., Tight bounds on quantum searching**
|
||
|
||
[https://arxiv.org/abs/quant-ph/9605034](https://arxiv.org/abs/quant-ph/9605034)
|
||
|
||
## Methods
|
||
|
||
### construct\_circuit
|
||
|
||
<Function id="qiskit.aqua.algorithms.Grover.construct_circuit" signature="Grover.construct_circuit(power=None, measurement=False)">
|
||
Construct the circuit for Grover’s algorithm with `power` Grover operators.
|
||
|
||
**Parameters**
|
||
|
||
* **power** (`Optional`\[`int`]) – The number of times the Grover operator is repeated. If None, this argument is set to the first item in `iterations`.
|
||
* **measurement** (`bool`) – 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")
|
||
</Function>
|
||
|
||
### is\_good\_state
|
||
|
||
<Function id="qiskit.aqua.algorithms.Grover.is_good_state" signature="Grover.is_good_state(bitstr)">
|
||
Check whether a provided bitstring is a good state or not.
|
||
|
||
**Parameters**
|
||
|
||
**bitstr** (`str`) – The measurement as bitstring.
|
||
|
||
**Return type**
|
||
|
||
`bool`
|
||
|
||
**Returns**
|
||
|
||
True if the measurement is a good state, False otherwise.
|
||
</Function>
|
||
|
||
### optimal\_num\_iterations
|
||
|
||
<Function id="qiskit.aqua.algorithms.Grover.optimal_num_iterations" signature="Grover.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`) – 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.
|
||
</Function>
|
||
|
||
### post\_processing
|
||
|
||
<Function id="qiskit.aqua.algorithms.Grover.post_processing" signature="Grover.post_processing(measurement)">
|
||
Do the post-processing to the measurement result
|
||
|
||
**Parameters**
|
||
|
||
**measurement** (`List`\[`int`]) – The measurement as list of int.
|
||
|
||
**Return type**
|
||
|
||
`List`\[`int`]
|
||
|
||
**Returns**
|
||
|
||
Do the post-processing based on the post\_processing argument. If the post\_processing argument is None and the Oracle class is used as its oracle, oracle.evaluate\_classically is used as the post\_processing. Otherwise, just return the input bitstr
|
||
</Function>
|
||
|
||
### run
|
||
|
||
<Function id="qiskit.aqua.algorithms.Grover.run" signature="Grover.run(quantum_instance=None, **kwargs)">
|
||
Execute the algorithm with selected backend.
|
||
|
||
**Parameters**
|
||
|
||
* **quantum\_instance** (`Union`\[`QuantumInstance`, `Backend`, `BaseBackend`, `None`]) – the experimental setting.
|
||
* **kwargs** (*dict*) – kwargs
|
||
|
||
**Returns**
|
||
|
||
results of an algorithm.
|
||
|
||
**Return type**
|
||
|
||
dict
|
||
|
||
**Raises**
|
||
|
||
[**AquaError**](qiskit.aqua.AquaError "qiskit.aqua.AquaError") – If a quantum instance or backend has not been provided
|
||
</Function>
|
||
|
||
### set\_backend
|
||
|
||
<Function id="qiskit.aqua.algorithms.Grover.set_backend" signature="Grover.set_backend(backend, **kwargs)">
|
||
Sets backend with configuration.
|
||
|
||
**Return type**
|
||
|
||
`None`
|
||
</Function>
|
||
|
||
## Attributes
|
||
|
||
### backend
|
||
|
||
<Attribute id="qiskit.aqua.algorithms.Grover.backend">
|
||
Returns backend.
|
||
|
||
**Return type**
|
||
|
||
`Union`\[`Backend`, `BaseBackend`]
|
||
</Attribute>
|
||
|
||
### grover\_operator
|
||
|
||
<Attribute id="qiskit.aqua.algorithms.Grover.grover_operator">
|
||
Returns grover\_operator.
|
||
|
||
**Return type**
|
||
|
||
`QuantumCircuit`
|
||
</Attribute>
|
||
|
||
### quantum\_instance
|
||
|
||
<Attribute id="qiskit.aqua.algorithms.Grover.quantum_instance">
|
||
Returns quantum instance.
|
||
|
||
**Return type**
|
||
|
||
`Optional`\[`QuantumInstance`]
|
||
</Attribute>
|
||
|
||
### random
|
||
|
||
<Attribute id="qiskit.aqua.algorithms.Grover.random">
|
||
Return a numpy random.
|
||
</Attribute>
|
||
</Class>
|
||
|