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

Konstruieren Sie den Grover-Operator.

Der Grover-Suchalgorithmus [1, 2] besteht aus wiederholten Anwendungen des so genannten Grover-Operators, der zur Verstärkung der Amplituden der gewünschten Ausgangszustände verwendet wird. Dieser Operator, $\mathcal{Q}$, besteht aus dem Phasenorakel, $\mathcal{S}_f$, der Nullphasenverschiebung oder Nullreflexion, $\mathcal{S}_0$, und einer Eingangszustandsvorbereitung $\mathcal{A}$ :

In der Standard-Grover-Suche haben wir $\mathcal{A} = H^{\otimes n}$ :

Die Operation $D = H^{\otimes n} \mathcal{S}_0 H^{\otimes n}$ wird auch als Diffusionsoperator bezeichnet. In dieser Formulierung wird deutlich, dass der Grover-Operator aus zwei Schritten besteht: Zuerst multipliziert das Phasenorakel die guten Zustände mit -1 (mit $\mathcal{S}_f$ ) und dann wird der gesamte Zustand um den Mittelwert gespiegelt (mit $D$ ).

Diese Klasse ermöglicht die Festlegung einer anderen Zustandsvorbereitung, wie beispielsweise bei der Quantenamplitudenverstärkung (einer Verallgemeinerung des Grover-Algorithmus); $\mathcal{A}$ ist möglicherweise keine Schicht aus Hadamard-Gattern [3].

Die Aktion des Phasenorakels $\mathcal{S}_f$ ist definiert als

wobei $f(x) = 1$, wenn $x$ ein guter Zustand ist, und 0 andernfalls. Um die Tatsache hervorzuheben, dass dieses Orakel die Phase der guten Zustände umkehrt und nicht den Zustand eines Ergebnis-Qubits umkehrt, nennen wir $\mathcal{S}_f$ ein Phasenorakel.

Es ist zu beachten, dass man ein Phasenorakel leicht aus einem Bitflip-Orakel konstruieren kann, indem man das kontrollierte X-Gatter auf dem Ergebnis-Qubit durch ein X- und H-Gatter einklemmt. Zum Beispiel

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

Es besteht eine gewisse Flexibilität bei der Definition des Orakels und des Operators $\mathcal{A}$. Bevor der Grover-Operator in Grovers Algorithmus angewendet wird, werden die Qubits zunächst mit einer Anwendung des $\mathcal{A}$ -Operators (oder Hadamard-Gates in der Standardformulierung) vorbereitet. Wir haben also immer eine Operation der Form $\mathcal{A} \mathcal{S}_f \mathcal{A}^\dagger$. Daher ist es möglich, die Bitflip-Logik in $\mathcal{A}$ zu verlagern und das Orakel nur noch für Phasenumkehrungen über Z-Gatter auf der Grundlage der Bitflips einzusetzen. Ein möglicher Anwendungsfall hierfür sind Orakel, die die Zustands-Qubits nicht dekompilieren.

Die Null-Reflexion $\mathcal{S}_0$ ist normalerweise definiert als

wobei $\mathbb{I}_n$ die Identität auf $n$ qubits ist. Standardmäßig implementiert diese Klasse die negative Version $2 |0\rangle^{\otimes n} \langle 0|^{\otimes n} - \mathbb{I}_n$, da diese einfach mit einem mehrfach kontrollierten Z zwischen X-Gattern auf dem Ziel-Qubit implementiert werden kann und die eingeführte globale Phase für den Grover-Algorithmus keine Rolle spielt.

Beispiele:

Wir können einen Grover-Operator nur aus dem Phasenorakel konstruieren:

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

Wir können auch den Zustand der Vorbereitung ändern:

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

Darüber hinaus können wir auch markieren, auf welche Qubits die Nullreflexion wirken soll. Dies ist nützlich für den Fall, dass einige Qubits nur als Speicherplatz verwendet werden, sollte aber keine Auswirkungen auf das Orakel haben:

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

Das Orakel und die Nullreflexion können auch als qiskit.quantum_info Objekte übergeben werden:

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

Für eine große Anzahl von Qubits kann das mehrfach gesteuerte X-Gate, das für die Null-Reflexion verwendet wird, auf unterschiedliche Weise synthetisiert werden. Je nach Anzahl der verfügbaren Qubits wird der Compiler eine andere Implementierung wählen:

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

Parameter

• oracle (QuantumCircuit |Statevector) – Das Phasenorakel, das eine Reflexion über den fehlerhaften Zustand implementiert. Beachten Sie, dass es sich hierbei nicht um ein Bitflip-Orakel handelt; weitere Informationen finden Sie im Docstring.
• state_preparation (QuantumCircuit | None) – Der Bediener bereitet den guten und den schlechten Zustand vor. Beim Grover-Algorithmus handelt es sich um ein n-Qubit-Hadamard-Gatter, und zur Amplitudenverstärkung oder -schätzung wird der Operator $\mathcal{A}$ verwendet.
• zero_reflection (QuantumCircuit |DensityMatrix |Operator | None) – Die Überlegungen zum Nullzustand, $\mathcal{S}_0$.
• reflection_qubits (list[int] | None) – Qubits, auf die die Nullreflexion wirkt.
• insert_barriers (bool) – Ob Barrieren zwischen den Reflexionen und A eingefügt werden sollen.
• name (str) – Der Name des Stromkreises.

Quellenangaben:

[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. Kapitel 6.1.2.

[3] Brassard, G., Hoyer, P., Mosca, M., & Tapp, A. (2000). Quantenamplitudenverstärkung und -schätzung. arXiv:quant-ph/0005055.