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')

Construye el operador Grover.

El algoritmo de búsqueda de Grover [1, 2] consiste en aplicaciones repetidas del llamado operador de Grover utilizado para amplificar las amplitudes de los estados de salida deseados. Este operador, $\mathcal{Q}$, consta del oráculo de fase, $\mathcal{S}_f$, el desplazamiento de fase cero o reflexión cero, $\mathcal{S}_0$, y una preparación de estado de entrada $\mathcal{A}$ :

En la búsqueda estándar de Grover tenemos $\mathcal{A} = H^{\otimes n}$ :

La operación $D = H^{\otimes n} \mathcal{S}_0 H^{\otimes n}$ también se denomina operador de difusión. En esta formulación podemos ver que el operador de Grover consta de dos pasos: primero, el oráculo de fase multiplica los estados buenos por -1 (con $\mathcal{S}_f$ ) y luego se refleja todo el estado alrededor de la media (con $D$ ).

Esta clase permite establecer una preparación de estado diferente, como en la amplificación de amplitudes cuánticas (una generalización del algoritmo de Grover); $\mathcal{A}$ podría no ser una capa de puertas de Hadamard [3].

La acción del oráculo de fase $\mathcal{S}_f$ se define como

donde $f(x) = 1$ si $x$ es un buen estado y 0 en caso contrario. Para resaltar el hecho de que este oráculo invierte la fase de los estados buenos y no invierte el estado de un qubit resultante, llamamos a $\mathcal{S}_f$ oráculo de fase.

Nótese que se puede construir fácilmente un oráculo de fase a partir de un oráculo de cambio de bit intercalando la puerta X controlada en el qubit resultado por una puerta X y H. Por ejemplo

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

Existe cierta flexibilidad a la hora de definir el oráculo y el operador $\mathcal{A}$. Antes de aplicar el operador Grover en el algoritmo de Grover, los qubits se preparan primero con una aplicación del operador $\mathcal{A}$ (o puertas Hadamard en la formulación estándar). Así, siempre tenemos una operación de la forma $\mathcal{A} \mathcal{S}_f \mathcal{A}^\dagger$. Por lo tanto, es posible trasladar la lógica de cambio de bits a $\mathcal{A}$ y dejar el oráculo sólo para hacer cambios de fase a través de puertas Z basadas en los cambios de bits. Un posible caso de uso para esto son los oráculos que no descomputan los qubits de estado.

La reflexión cero $\mathcal{S}_0$ suele definirse como

donde $\mathbb{I}_n$ es la identidad en $n$ qubits. Por defecto, esta clase implementa la versión negativa $2 |0\rangle^{\otimes n} \langle 0|^{\otimes n} - \mathbb{I}_n$, ya que ésta puede implementarse simplemente con una Z multicontrolada intercalada por puertas X en el qubit objetivo y la fase global introducida no importa para el algoritmo de Grover.

Ejemplos:

Podemos construir un operador Grover a partir del oráculo de fase:

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")

También podemos modificar la preparación del estado:

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")

Además, también podemos marcar sobre qué qubits debe actuar la reflexión cero. Esto es útil en caso de que algunos qubits sólo se utilicen como espacio de memoria virtual, pero no debería afectar al oráculo:

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")

El oráculo y el reflejo cero también se pueden pasar como qiskit.quantum_info objetos:

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")

Para un gran número de qubits, la puerta X multicontrolada utilizada para la reflexión cero puede sintetizarse de diferentes maneras. Dependiendo del número de qubits disponibles, el compilador elegirá una implementación diferente:

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

Parámetros

• oracle (QuantumCircuit |Statevector) – El oráculo de fase implementando una reflexión sobre el mal estado. Tenga en cuenta que esto no es un oráculo bitflip, consulte el docstring para obtener más información.
• state_preparation (QuantumCircuit | None) – El operador prepara el buen y el mal estado. Para el algoritmo de Grover, se trata de una puerta Hadamard de n-qubit y para la amplificación o estimación de amplitud el operador $\mathcal{A}$.
• zero_reflection (QuantumCircuit |DensityMatrix |Operator | None) – La reflexión sobre el estado cero, $\mathcal{S}_0$.
• reflection_qubits (list[int] | None) – Qubits sobre los que actúa la reflexión cero.
• insert_barriers (bool) – Si deben intercalarse barreras entre los reflejos y A.
• name (str) – El nombre del circuito.

Referencias:

[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. Capítulo 6.1.2.

[3] Brassard, G., Hoyer, P., Mosca, M., y Tapp, A. (2000). Amplificación y estimación de la amplitud cuántica. arXiv:quant-ph/0005055.