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

Costruire l'operatore Grover.

L'algoritmo di ricerca di Grover [1, 2] consiste in applicazioni ripetute del cosiddetto operatore di Grover, utilizzato per amplificare le ampiezze degli stati di uscita desiderati. Questo operatore, $\mathcal{Q}$, è costituito dall'oracolo di fase, $\mathcal{S}_f$, dallo sfasamento zero o dalla riflessione zero, $\mathcal{S}_0$, e da una preparazione dello stato di ingresso $\mathcal{A}$ :

Nella ricerca standard di Grover abbiamo $\mathcal{A} = H^{\otimes n}$ :

L'operazione $D = H^{\otimes n} \mathcal{S}_0 H^{\otimes n}$ viene anche chiamata operatore di diffusione. In questa formulazione possiamo vedere che l'operatore di Grover consiste in due passaggi: prima l'oracolo di fase moltiplica gli stati buoni per -1 (con $\mathcal{S}_f$ ) e poi l'intero stato viene riflesso intorno alla media (con $D$ ).

Questa classe consente di impostare una preparazione di stato diversa, come nell'amplificazione dell'ampiezza quantistica (una generalizzazione dell'algoritmo di Grover); $\mathcal{A}$ potrebbe non trattarsi di una sequenza di porte di Hadamard [3].

L'azione dell'oracolo di fase $\mathcal{S}_f$ è definita come

dove $f(x) = 1$ se $x$ è uno stato buono e 0 altrimenti. Per sottolineare il fatto che questo oracolo capovolge la fase degli stati buoni e non capovolge lo stato di un qubit risultato, chiamiamo $\mathcal{S}_f$ oracolo di fase.

Si noti che si può facilmente costruire un oracolo di fase a partire da un oracolo bitflip, inserendo il gate X controllato sul qubit risultato con un gate X e H. Per esempio

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

Esiste una certa flessibilità nel definire l'operatore oracolo e $\mathcal{A}$. Prima di applicare l'operatore di Grover nell'algoritmo di Grover, i qubit vengono preparati con un'applicazione dell'operatore $\mathcal{A}$ (o delle porte di Hadamard nella formulazione standard). Quindi, abbiamo sempre operazioni della forma $\mathcal{A} \mathcal{S}_f \mathcal{A}^\dagger$. È quindi possibile spostare la logica dei bitflip in $\mathcal{A}$ e lasciare all'oracolo solo il compito di effettuare i capovolgimenti di fase tramite porte Z basate sui bitflip. Un possibile caso d'uso sono gli oracoli che non decompongono i qubit di stato.

La riflessione zero $\mathcal{S}_0$ è solitamente definita come

dove $\mathbb{I}_n$ è l'identità su $n$ qubit. Per impostazione predefinita, questa classe implementa la versione negativa $2 |0\rangle^{\otimes n} \langle 0|^{\otimes n} - \mathbb{I}_n$, poiché questa può essere semplicemente implementata con una Z multicontrollata e con porte X sul qubit di destinazione e la fase globale introdotta non ha importanza per l'algoritmo di Grover.

Esempi:

Possiamo costruire un operatore di Grover solo dall'oracolo di 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")

Possiamo anche modificare la preparazione dello stato:

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

Inoltre, possiamo anche indicare su quali qubit deve agire la riflessione zero. Questo è utile nel caso in cui alcuni qubit siano usati solo come spazio per i graffi, ma non dovrebbe influenzare l'oracolo:

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'oracolo e la riflessione zero possono anche essere passati come qiskit.quantum_info oggetti:

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

Per un numero elevato di qubit, la porta X multicontrollata utilizzata per la riflessione zero può essere sintetizzata in modi diversi. A seconda del numero di qubit disponibili, il compilatore sceglierà un'implementazione diversa:

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

Parametri

• oracle (QuantumCircuit |Statevector) – L'oracolo di fase che mette in atto una riflessione sullo stato anomalo. Si noti che non si tratta di un oracolo di tipo “bitflip”; per ulteriori informazioni, consultare la stringa di documentazione.
• state_preparation (QuantumCircuit | None) – L'operatore che prepara lo stato "buono" e quello "cattivo". Per l'algoritmo di Grover, si tratta di una porta di Hadamard a n qubit, mentre per l'amplificazione o la stima dell'ampiezza l'operatore è $\mathcal{A}$.
• zero_reflection (QuantumCircuit |DensityMatrix |Operator | None) – La riflessione sullo stato zero, $\mathcal{S}_0$.
• reflection_qubits (list[int] | None) – Qubit su cui agisce la riflessione zero.
• insert_barriers (bool) – Se è necessario inserire delle barriere tra le riflessioni e A.
• name (str) – Il nome del circuito.

Riferimenti:

[1] L. K. Grover (1996), Un algoritmo quantomeccanico veloce per la ricerca nei database, arXiv:quant-ph/9605043.

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

[3] Brassard, G., Hoyer, P., Mosca, M., & Tapp, A. (2000). Amplificazione e stima dell'ampiezza quantistica. arXiv:quant-ph/0005055.