grover

grover#

Functionality#

Grover’s search [15] [16] algorithm aims to find a solution for unstructured search.

grover_operator.py#

Callee: GroverOperator

The Grover operator is the core transformation that amplifies the amplitudes of “good” states (solutions). This operator \(\mathcal{Q}\) consists of the phase oracle \(\mathcal{S}_f\), zero phase-shift or zero reflection \(\mathcal{S}_0\), and an input state preparation \(\mathcal{A}\):

\[ \mathcal{Q} = \mathcal{A} \mathcal{S}_0 \mathcal{A}^\dagger \mathcal{S}_f. \]

In the standard Grover search we have

\[ \mathcal{A} = H^{\otimes n}, \]

and then

\[ \mathcal{Q} = H^{\otimes n} \mathcal{S}_0 H^{\otimes n} \mathcal{S}_f = D \mathcal{S}_f. \]

The operation \(D = H^{\otimes n} \mathcal{S}_0 H^{\otimes n}\) is also referred to as diffusion operator. In this formulation we can see that Grover’s operator consists of two steps: first, the phase oracle multiplies the good states by -1 (with \(\mathcal{S}_f\)) and then the whole state is reflected around the mean (with \(D\)).

The action of the phase oracle \(\mathcal{S}_f\) is defined as

\[ \mathcal{S}_f: \ket{x} \mapsto (-1)^{f(x)} \ket{x} \]

​ where \(f(x) = 1\) if \(x\) is a good state and 0 otherwise, which is determined by the input oracle. To highlight the fact that this oracle flips the phase of the good states and does not flip the state of a result qubit, we call \(\mathcal{S}_f\) a phase oracle.

The zero reflection \(\mathcal{S}_0\) flips the sign of the \(\ket{0}^{\otimes n}\) state, which is usually defined as

\[ \mathcal{S}_0 = 2\ket{0}^{\otimes n}\bra{0}^{\otimes n} -\mathbb{I}_n \]

where \(\mathbb{I}_n\) is the identity on \(n\) qubits. By default, this class implements the negative version \(2\ket{0}^{\otimes n}\bra{0}^{\otimes n} -\mathbb{I}_n\), since this can simply be implemented with a multi-controlled Z sandwiched by X gates on the target qubit and the introduced global phase does not matter for Grover’s algorithm.

Test expectations:

Program specification can be constructed according to each subroutine of Grover operator, such that the unitary operation can be verified through testing.

Doc references: [17] [18]

grover_search.py#

Callee: GroverSearch

This program implements the complete Grover’s search algorithm through multiple applications of the above grover operator.

The quantum circuit is constructed as follows:

Grover's search circuit

Grover search circuit (Source: https://en.wikipedia.org/wiki/Grover%27s_algorithm)

  1. Initialization: Uniform Superposition Apply Hadamard gates to all \(n\) qubits:

    \[ |0\rangle^{\otimes n} \xrightarrow{H^{\otimes n}} \ket{s}_n = \frac{1}{\sqrt{N}}\sum_{x=0}^{N-1}\ket{x}_{n}, \]

    where \(N = 2^n\) and the state is an equal superposition of all computational basis states.

  2. Phase Oracle \(S_f\): The phase oracle flips the sign of the target states \(x \in T\), where \(T\) is the set of solutions:

    \[\begin{split} S_f\ket{x}_n = \begin{cases} -\ket{x}_n, & x \in T \\ \ket{x}_n, & x \notin T \end{cases} \end{split}\]

    Applied to the uniform superposition:

    \[ \ket{s}_n \xrightarrow{S_f} S_f\ket{s}_n = \frac{1}{\sqrt{N}}\Big(\sum_{x \notin T} \ket{x}_n - \sum_{x \in T} \ket{x}_n\Big) \]

    By this means, good states have their amplitudes negated and bad states remain unchanged.

  3. Diffuser (Inversion About the Mean): The diffuser is defined as:

    \[ D = 2\ket{s}_n\langle s|_n - \mathbb{I}_n \]

  4. Grover Iteration: The Grover operator is:

    \[ \mathcal{Q} = D \cdot S_f \]

    After \(t\) iterations, the state evolves to:

    \[ |\psi_t\rangle = \mathcal{Q}^t \ket{s}_n = \cos((2t+1)\theta) \ket{\beta}_n + \sin((2t+1)\theta) \ket{\alpha}_n \]

    Where:

    • \(\ket{\alpha}_n = \frac{1}{\sqrt{|T|}} \sum_{x \in T} \ket{x}_n\) (good subspace)

    • \(\ket{\beta}_n = \frac{1}{\sqrt{N-|T|}} \sum_{x \notin T} \ket{x}_n\) (bad subspace)

    • \(\theta = \arcsin(\sqrt{|T|/N})\)

    • Each iteration rotates the state vector in the 2-dimensional subspace spanned by \(\ket{\alpha}_n\) and \(\ket{\beta}_n\).

    • Choosing \(t \approx \frac{\pi}{4} \sqrt{N/|T|}\) maximizes the probability of measuring a target state.

  5. Measurement (not included in our implementation) After the Grover iterations, measure all qubits:

    \[ |\psi_t\rangle \approx \ket{\alpha}_n = \frac{1}{\sqrt{|T|}}\sum_{x \in T} \ket{x}_n \]

    Measurement collapses the state to one of the target states \(x \in T\) with high probability.

Test expectations:

  • When searching only one item among \(N\) items, the probability of measuring a target state will be maximized, close to 1 by choosing \(t \approx \frac{\pi}{4} \sqrt{N/|T|}\) iterations.

  • When there are multiple target states, we can check the exact state \(|\psi_t\rangle \) after \(t\) iterations.

Notes:

  • For steps, we accept steps = None only when oracle is of type Statevector, since in that case we can determine the number of target states directly from the statevector. If oracle is a QuantumCircuit, the user must provide steps explicitly.

  • As we can see the formula, Grover’s algorithm can ensure the target solution with high probability. This means that the solution is not deterministic and exact.

Code Example#

The following code gives an example to prepare the argument oracle for testing the grover module:

Example 1: Quantum circuit from [17]:

>>> from qiskit.circuit import QuantumCircuit
>>> from qiskit.circuit.library import GroverOperator
>>> oracle = QuantumCircuit(2)
>>> oracle.z(0)  # good state = first qubit is |1>. Remember this is a phase oracle.
>>> grover_op = GroverOperator(oracle, insert_barriers=True)
>>> grover_op.decompose().draw()
         ┌───┐ ░ ┌───┐ ░ ┌───┐          ┌───┐      ░ ┌───┐
state_0: ┤ Z ├─░─┤ H ├─░─┤ X ├───────■──┤ X ├──────░─┤ H ├
         └───┘ ░ ├───┤ ░ ├───┤┌───┐┌─┴─┐├───┤┌───┐ ░ ├───┤
state_1: ──────░─┤ H ├─░─┤ X ├┤ H ├┤ X ├┤ H ├┤ X ├─░─┤ H ├
               ░ └───┘ ░ └───┘└───┘└───┘└───┘└───┘ ░ └───┘

Example 2: Statevector

>>> from qiskit.quantum_info import Statevector
>>> from qiskit.circuit.library import GroverOperator
>>> oracle_sv = Statevector([0, 0, 0, 1, 0, 0, 0, 0])   # good state = |3>
>>> grover_op = GroverOperator(oracle_sv, insert_barriers=True)
>>> grover_op.decompose().draw()
global phase: π
         ┌─────────────────────────────┐ ░ ┌───┐ ░ ┌───┐          ┌───┐      ░ ┌───┐
state_0: ┤0                            ├─░─┤ H ├─░─┤ X ├───────■──┤ X ├──────░─┤ H ├
         │                             │ ░ ├───┤ ░ ├───┤       │  ├───┤      ░ ├───┤
state_1: ┤1 Diagonal(1,1,1,-1,1,1,1,1) ├─░─┤ H ├─░─┤ X ├───────■──┤ X ├──────░─┤ H ├
         │                             │ ░ ├───┤ ░ ├───┤┌───┐┌─┴─┐├───┤┌───┐ ░ ├───┤
state_2: ┤2                            ├─░─┤ H ├─░─┤ X ├┤ H ├┤ X ├┤ H ├┤ X ├─░─┤ H ├
         └─────────────────────────────┘ ░ └───┘ ░ └───┘└───┘└───┘└───┘└───┘ ░ └───┘

API#

qolumbina.programs.grover.grover_operator#

The Grover operator.

class GroverOperator(oracle, state_preparation=None, zero_reflection=None, reflection_qubits=None, insert_barriers=False, name='Q')[source]#

Bases: QuantumCircuit

Grover operator circuit.

Parameters:

  • oracle (QuantumCircuit | Statevector) – The phase oracle implementing a reflection about the bad state. Note that this is not a bitflip oracle, see the docstring for more information.

  • state_preparation (QuantumCircuit | None) – The operator preparing the good and bad state. For Grover’s algorithm, this is a n-qubit Hadamard gate and for amplitude amplification or estimation the operator \(\mathcal{A}\). If None, a layer of Hadamard gates is used on reflection_qubits.

  • zero_reflection (QuantumCircuit | DensityMatrix | Operator | None) – The reflection about the zero state, \(\mathcal{S}_0\). If None, a default implementation is used.

  • reflection_qubits (list[int] | None) – Qubits on which the zero reflection acts on. If None, all qubits of the oracle are used.

  • insert_barriers (bool) – Whether barriers should be inserted between the reflections and A.

  • name (str) – The name of the circuit.

Contents