Quellcode fΓΌr qiskit.circuit.library.grover_operator

# 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

[Doku]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 .. parsed-literal:: 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