grover_operator.py

# This code is part of Qiskit.
#
# (C) Copyright IBM 2017, 2020.
#
# This code is licensed under the Apache License, Version 2.0. You may
# obtain a copy of this license in the LICENSE.txt file in the root directory
# of this source tree or at http://www.apache.org/licenses/LICENSE-2.0.
#
# Any modifications or derivative works of this code must retain this
# copyright notice, and modified files need to carry a notice indicating
# that they have been altered from the originals.

"""The Grover operator."""

from __future__ import annotations
from typing import List, Optional, Union
import numpy

from qiskit.circuit import QuantumCircuit, QuantumRegister, AncillaRegister
from qiskit.exceptions import QiskitError
from qiskit.quantum_info import Statevector, Operator, DensityMatrix
from .standard_gates import MCXGate


class GroverOperator(QuantumCircuit):
    r"""The Grover operator.

    Grover's search algorithm [1, 2] consists of repeated applications of the so-called
    Grover operator used to amplify the amplitudes of the desired output states.
    This operator, :math:`\mathcal{Q}`, consists of the phase oracle, :math:`\mathcal{S}_f`,
    zero phase-shift or zero reflection, :math:`\mathcal{S}_0`, and an
    input state preparation :math:`\mathcal{A}`:

    .. math::
        \mathcal{Q} = \mathcal{A} \mathcal{S}_0 \mathcal{A}^\dagger \mathcal{S}_f

    In the standard Grover search we have :math:`\mathcal{A} = H^{\otimes n}`:

    .. math::
        \mathcal{Q} = H^{\otimes n} \mathcal{S}_0 H^{\otimes n} \mathcal{S}_f
                    = D \mathcal{S_f}

    The operation :math:`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 :math:`\mathcal{S}_f`)
    and then the whole state is reflected around the mean (with :math:`D`).

    This class allows setting a different state preparation, as in quantum amplitude
    amplification (a generalization of Grover's algorithm), :math:`\mathcal{A}` might not be
    a layer of Hardamard gates [3].

    The action of the phase oracle :math:`\mathcal{S}_f` is defined as

    .. math::
        \mathcal{S}_f: |x\rangle \mapsto (-1)^{f(x)}|x\rangle

    where :math:`f(x) = 1` if :math:`x` is a good state and 0 otherwise. 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 :math:`\mathcal{S}_f` a phase oracle.

    Note that you can easily construct a phase oracle from a bitflip oracle by sandwiching the
    controlled X gate on the result qubit by a X and H gate. For instance

    .. code-block:: text

        Bitflip oracle     Phaseflip oracle
        q_0: ──■──         q_0: ────────────■────────────
             ┌─┴─┐              ┌───┐┌───┐┌─┴─┐┌───┐┌───┐
        out: ┤ X ├         out: ┤ X ├┤ H ├┤ X ├┤ H ├┤ X ├
             └───┘              └───┘└───┘└───┘└───┘└───┘

    There is some flexibility in defining the oracle and :math:`\mathcal{A}` operator. Before the
    Grover operator is applied in Grover's algorithm, the qubits are first prepared with one
    application of the :math:`\mathcal{A}` operator (or Hadamard gates in the standard formulation).
    Thus, we always have operation of the form
    :math:`\mathcal{A} \mathcal{S}_f \mathcal{A}^\dagger`. Therefore it is possible to move
    bitflip logic into :math:`\mathcal{A}` and leaving the oracle only to do phaseflips via Z gates
    based on the bitflips. One possible use-case for this are oracles that do not uncompute the
    state qubits.

    The zero reflection :math:`\mathcal{S}_0` is usually defined as

    .. math::
        \mathcal{S}_0 = 2 |0\rangle^{\otimes n} \langle 0|^{\otimes n} - \mathbb{I}_n

    where :math:`\mathbb{I}_n` is the identity on :math:`n` qubits.
    By default, this class implements the negative version
    :math:`2 |0\rangle^{\otimes n} \langle 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.

    Examples:
        >>> from qiskit.circuit import QuantumCircuit
        >>> from qiskit.circuit.library import GroverOperator
        >>> oracle = QuantumCircuit(2)
        >>> oracle.z(0)  # good state = first qubit is |1>
        >>> 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 ├
                       ░ └───┘ ░ └───┘└───┘└───┘└───┘└───┘ ░ └───┘

        >>> oracle = QuantumCircuit(1)
        >>> oracle.z(0)  # the qubit state |1> is the good state
        >>> state_preparation = QuantumCircuit(1)
        >>> state_preparation.ry(0.2, 0)  # non-uniform state preparation
        >>> grover_op = GroverOperator(oracle, state_preparation)
        >>> grover_op.decompose().draw()
                 ┌───┐┌──────────┐┌───┐┌───┐┌───┐┌─────────┐
        state_0: ┤ Z ├┤ RY(-0.2) ├┤ X ├┤ Z ├┤ X ├┤ RY(0.2) ├
                 └───┘└──────────┘└───┘└───┘└───┘└─────────┘

        >>> oracle = QuantumCircuit(4)
        >>> oracle.z(3)
        >>> reflection_qubits = [0, 3]
        >>> state_preparation = QuantumCircuit(4)
        >>> state_preparation.cry(0.1, 0, 3)
        >>> state_preparation.ry(0.5, 3)
        >>> grover_op = GroverOperator(oracle, state_preparation,
        ... reflection_qubits=reflection_qubits)
        >>> grover_op.decompose().draw()
                                              ┌───┐          ┌───┐
        state_0: ──────────────────────■──────┤ X ├───────■──┤ X ├──────────■────────────────
                                       │      └───┘       │  └───┘          │
        state_1: ──────────────────────┼──────────────────┼─────────────────┼────────────────
                                       │                  │                 │
        state_2: ──────────────────────┼──────────────────┼─────────────────┼────────────────
                 ┌───┐┌──────────┐┌────┴─────┐┌───┐┌───┐┌─┴─┐┌───┐┌───┐┌────┴────┐┌─────────┐
        state_3: ┤ Z ├┤ RY(-0.5) ├┤ RY(-0.1) ├┤ X ├┤ H ├┤ X ├┤ H ├┤ X ├┤ RY(0.1) ├┤ RY(0.5) ├
                 └───┘└──────────┘└──────────┘└───┘└───┘└───┘└───┘└───┘└─────────┘└─────────┘

        >>> mark_state = Statevector.from_label('011')
        >>> diffuse_operator = 2 * DensityMatrix.from_label('000') - Operator.from_label('III')
        >>> grover_op = GroverOperator(oracle=mark_state, zero_reflection=diffuse_operator)
        >>> grover_op.decompose().draw(fold=70)
                 ┌─────────────────┐      ┌───┐                          »
        state_0: ┤0                ├──────┤ H ├──────────────────────────»
                 │                 │┌─────┴───┴─────┐     ┌───┐          »
        state_1: ┤1 UCRZ(0,pi,0,0) ├┤0              ├─────┤ H ├──────────»
                 │                 ││  UCRZ(pi/2,0) │┌────┴───┴────┐┌───┐»
        state_2: ┤2                ├┤1              ├┤ UCRZ(-pi/4) ├┤ H ├»
                 └─────────────────┘└───────────────┘└─────────────┘└───┘»
        «         ┌─────────────────┐      ┌───┐
        «state_0: ┤0                ├──────┤ H ├─────────────────────────
        «         │                 │┌─────┴───┴─────┐    ┌───┐
        «state_1: ┤1 UCRZ(pi,0,0,0) ├┤0              ├────┤ H ├──────────
        «         │                 ││  UCRZ(pi/2,0) │┌───┴───┴────┐┌───┐
        «state_2: ┤2                ├┤1              ├┤ UCRZ(pi/4) ├┤ H ├
        «         └─────────────────┘└───────────────┘└────────────┘└───┘

    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>`_.
    """

    def __init__(
        self,
        oracle: Union[QuantumCircuit, Statevector],
        state_preparation: Optional[QuantumCircuit] = None,
        zero_reflection: Optional[Union[QuantumCircuit, DensityMatrix, Operator]] = None,
        reflection_qubits: Optional[List[int]] = None,
        insert_barriers: bool = False,
        mcx_mode: str = "noancilla",
        name: str = "Q",
    ) -> None:
        r"""
        Args:
            oracle: 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: 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 :math:`\mathcal{A}`.
            zero_reflection: The reflection about the zero state, :math:`\mathcal{S}_0`.
            reflection_qubits: Qubits on which the zero reflection acts on.
            insert_barriers: Whether barriers should be inserted between the reflections and A.
            mcx_mode: The mode to use for building the default zero reflection.
            name: The name of the circuit.
        """
        super().__init__(name=name)

        # store inputs
        if isinstance(oracle, Statevector):
            from qiskit.circuit.library import Diagonal  # pylint: disable=cyclic-import

            oracle = Diagonal((-1) ** oracle.data)
        self._oracle = oracle

        if isinstance(zero_reflection, (Operator, DensityMatrix)):
            from qiskit.circuit.library import Diagonal  # pylint: disable=cyclic-import

            zero_reflection = Diagonal(zero_reflection.data.diagonal())
        self._zero_reflection = zero_reflection

        self._reflection_qubits = reflection_qubits
        self._state_preparation = state_preparation
        self._insert_barriers = insert_barriers
        self._mcx_mode = mcx_mode

        # build circuit
        self._build()

    @property
    def reflection_qubits(self):
        """Reflection qubits, on which S0 is applied (if S0 is not user-specified)."""
        if self._reflection_qubits is not None:
            return self._reflection_qubits

        num_state_qubits = self.oracle.num_qubits - self.oracle.num_ancillas
        return list(range(num_state_qubits))

    @property
    def zero_reflection(self) -> QuantumCircuit:
        """The subcircuit implementing the reflection about 0."""
        if self._zero_reflection is not None:
            return self._zero_reflection

        num_state_qubits = self.oracle.num_qubits - self.oracle.num_ancillas
        return _zero_reflection(num_state_qubits, self.reflection_qubits, self._mcx_mode)

    @property
    def state_preparation(self) -> QuantumCircuit:
        """The subcircuit implementing the A operator or Hadamards."""
        if self._state_preparation is not None:
            return self._state_preparation

        num_state_qubits = self.oracle.num_qubits - self.oracle.num_ancillas
        hadamards = QuantumCircuit(num_state_qubits, name="H")
        # apply Hadamards only on reflection qubits, rest will cancel out
        hadamards.h(self.reflection_qubits)
        return hadamards

    @property
    def oracle(self):
        """The oracle implementing a reflection about the bad state."""
        return self._oracle

    def _build(self):
        num_state_qubits = self.oracle.num_qubits - self.oracle.num_ancillas
        circuit = QuantumCircuit(QuantumRegister(num_state_qubits, name="state"), name="Q")
        num_ancillas = numpy.max(
            [
                self.oracle.num_ancillas,
                self.zero_reflection.num_ancillas,
                self.state_preparation.num_ancillas,
            ]
        )
        if num_ancillas > 0:
            circuit.add_register(AncillaRegister(num_ancillas, name="ancilla"))

        circuit.compose(self.oracle, list(range(self.oracle.num_qubits)), inplace=True)
        if self._insert_barriers:
            circuit.barrier()
        circuit.compose(
            self.state_preparation.inverse(),
            list(range(self.state_preparation.num_qubits)),
            inplace=True,
        )
        if self._insert_barriers:
            circuit.barrier()
        circuit.compose(
            self.zero_reflection, list(range(self.zero_reflection.num_qubits)), inplace=True
        )
        if self._insert_barriers:
            circuit.barrier()
        circuit.compose(
            self.state_preparation, list(range(self.state_preparation.num_qubits)), inplace=True
        )

        # minus sign
        circuit.global_phase = numpy.pi

        self.add_register(*circuit.qregs)
        try:
            circuit_wrapped = circuit.to_gate()
        except QiskitError:
            circuit_wrapped = circuit.to_instruction()

        self.compose(circuit_wrapped, qubits=self.qubits, inplace=True)


# TODO use the oracle compiler or the bit string oracle
def _zero_reflection(
    num_state_qubits: int, qubits: List[int], mcx_mode: Optional[str] = None
) -> QuantumCircuit:
    qr_state = QuantumRegister(num_state_qubits, "state")
    reflection = QuantumCircuit(qr_state, name="S_0")

    num_ancillas = MCXGate.get_num_ancilla_qubits(len(qubits) - 1, mcx_mode)
    if num_ancillas > 0:
        qr_ancilla = AncillaRegister(num_ancillas, "ancilla")
        reflection.add_register(qr_ancilla)
    else:
        qr_ancilla = AncillaRegister(0)

    reflection.x(qubits)
    if len(qubits) == 1:
        reflection.z(0)  # MCX does not allow 0 control qubits, therefore this is separate
    else:
        reflection.h(qubits[-1])
        reflection.mcx(qubits[:-1], qubits[-1], qr_ancilla[:], mode=mcx_mode)
        reflection.h(qubits[-1])
    reflection.x(qubits)

    return reflection