qiskit.circuit.library.grover_operator

qiskit.circuit.library.grover_operator(oracle, state_preparation=None, zero_reflection=None, reflection_qubits=None, insert_barriers=False, name='Q')

Construire l'opérateur Grover.

L'algorithme de recherche de Grover [1, 2] consiste en des applications répétées de l'opérateur dit de Grover utilisé pour amplifier les amplitudes des états de sortie souhaités. Cet opérateur, $\mathcal{Q}$, se compose de l'oracle de phase, $\mathcal{S}_f$, du déphasage nul ou de la réflexion nulle, $\mathcal{S}_0$, et d'une préparation de l'état d'entrée $\mathcal{A}$ :

Dans la recherche standard de Grover, nous avons $\mathcal{A} = H^{\otimes n}$ :

L'opération $D = H^{\otimes n} \mathcal{S}_0 H^{\otimes n}$ est également appelée opérateur de diffusion. Dans cette formulation, nous pouvons voir que l'opérateur de Grover consiste en deux étapes : tout d'abord, l'oracle de phase multiplie les bons états par -1 (avec $\mathcal{S}_f$ ) et ensuite l'état entier est réfléchi autour de la moyenne (avec $D$ ).

Cette classe permet de définir une préparation d'état différente, comme dans l'amplification d'amplitude quantique (une généralisation de l'algorithme de Grover); l' $\mathcal{A}$ e pourrait ne pas être une superposition de portes de Hadamard [3].

L'action de l'oracle de phase $\mathcal{S}_f$ est définie comme suit

où $f(x) = 1$ si $x$ est un bon état et 0 sinon. Pour souligner le fait que cet oracle renverse la phase des bons états et ne renverse pas l'état d'un qubit de résultat, nous appelons $\mathcal{S}_f$ un oracle de phase.

Notez que vous pouvez facilement construire un oracle de phase à partir d'un oracle de bitflip en prenant en sandwich la porte X contrôlée sur le qubit de résultat par une porte X et une porte H. Par exemple

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

La définition de l'oracle et de l'opérateur $\mathcal{A}$ offre une certaine souplesse. Avant d'appliquer l'opérateur de Grover dans l'algorithme de Grover, les qubits sont d'abord préparés avec une application de l'opérateur $\mathcal{A}$ (ou des portes de Hadamard dans la formulation standard). Ainsi, nous avons toujours une opération de la forme $\mathcal{A} \mathcal{S}_f \mathcal{A}^\dagger$. Il est donc possible de déplacer la logique bitflip dans $\mathcal{A}$ et de ne laisser l'oracle que pour effectuer des phasesflips via des portes Z basées sur les bitflips. Les oracles qui ne calculent pas les qubits d'état constituent un cas d'utilisation possible.

La réflexion zéro $\mathcal{S}_0$ est généralement définie comme suit

où $\mathbb{I}_n$ est l'identité sur $n$ qubits. Par défaut, cette classe implémente la version négative $2 |0\rangle^{\otimes n} \langle 0|^{\otimes n} - \mathbb{I}_n$, puisqu'elle peut simplement être implémentée avec un Z multi-contrôlé pris en sandwich par des portes X sur le qubit cible et que la phase globale introduite n'a pas d'importance pour l'algorithme de Grover.

Exemples :

Nous pouvons construire un opérateur de Grover à partir de l'oracle de phase :

from qiskit.circuit import QuantumCircuit
from qiskit.circuit.library import grover_operator

oracle = QuantumCircuit(2)
oracle.z(0)  # good state = first qubit is |1>
grover_op = grover_operator(oracle, insert_barriers=True)
grover_op.draw("mpl")

Nous pouvons également modifier la préparation de l'état :

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 = grover_operator(oracle, state_preparation)
grover_op.draw("mpl")

En outre, nous pouvons également indiquer sur quels qubits la réflexion sur le zéro doit agir. Ceci est utile dans le cas où certains qubits sont simplement utilisés comme espace de stockage, mais ne devrait pas affecter l'oracle :

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 = grover_operator(oracle, state_preparation, reflection_qubits=reflection_qubits)
grover_op.draw("mpl")

L'oracle et la réflexion zéro peuvent également être transmis sous forme qiskit.quantum_info d'objets :

from qiskit.quantum_info import Statevector, DensityMatrix, Operator

mark_state = Statevector.from_label("011")
reflection = 2 * DensityMatrix.from_label("000") - Operator.from_label("III")
grover_op = grover_operator(oracle=mark_state, zero_reflection=reflection)
grover_op.draw("mpl")

Pour un grand nombre de qubits, la porte X multi-contrôlée utilisée pour la réflexion zéro peut être synthétisée de différentes manières. En fonction du nombre de qubits disponibles, le compilateur choisira une implémentation différente :

from qiskit import transpile, Qubit
from qiskit.circuit import QuantumCircuit
from qiskit.circuit.library import grover_operator

oracle = QuantumCircuit(10)
oracle.z(oracle.qubits)
grover_op = grover_operator(oracle)

# without extra qubit space, the MCX synthesis is expensive
basis_gates = ["u", "cx"]
tqc = transpile(grover_op, basis_gates=basis_gates)
is_2q = lambda inst: len(inst.qubits) == 2
print("2q depth w/o scratch qubits:", tqc.depth(filter_function=is_2q))  # > 350

# add extra bits that can be used as scratch space
grover_op.add_bits([Qubit() for _ in range(num_qubits)])
tqc = transpile(grover_op, basis_gates=basis_gates)
print("2q depth w/ scratch qubits:", tqc.depth(filter_function=is_2q)) # < 100

Paramètres

• oracle (QuantumCircuit |Statevector) – L'oracle de phase mettant en œuvre une réflexion sur l'état incorrect. Notez qu'il ne s'agit pas d'un oracle de type « bitflip »; consultez la chaîne de documentation pour plus d'informations.
• state_preparation (QuantumCircuit | None) – L'opérateur chargé de préparer les états « bon » et « mauvais ». Pour l'algorithme de Grover, il s'agit d'une porte de Hadamard à n qubits, et pour l'amplification ou l'estimation d'amplitude, l'opérateur $\mathcal{A}$.
• zero_reflection (QuantumCircuit |DensityMatrix |Operator | None) – Réflexion sur l'état zéro, $\mathcal{S}_0$.
• reflection_qubits (list[int] | None) – Qubits sur lesquels la réflexion zéro agit.
• insert_barriers (bool) – Si des barrières doivent être insérées entre les réflexions et A.
• name (str) – Le nom du circuit.

Références :

[1] L. K. Grover (1996), A fast quantum mechanical algorithm for database search, arXiv:quant-ph/9605043.

[2] I. Chuang & M. Nielsen, Quantum Computation and Quantum Information, Cambridge : Cambridge University Press, 2000. Chapitre 6.1.2.

[3] Brassard, G., Hoyer, P., Mosca, M., & Tapp, A. (2000). Amplification et estimation de l'amplitude quantique. arXiv:quant-ph/0005055.