Groverův algoritmus

Odhadovaná spotřeba: méně než jedna minuta na procesoru Eagle r3 (POZNÁMKA: Jedná se pouze o odhad. Tvůj skutečný čas běhu se může lišit.)

Pozadí

Amplifikace amplitudy je obecný kvantový algoritmus neboli podprogram, který lze použít k dosažení kvadratického zrychlení oproti hrstce klasických algoritmů. Groverův algoritmus byl prvním, kdo demonstroval toto zrychlení na nestrukturovaných problémech vyhledávání. Formulace Groverova vyhledávacího problému vyžaduje orákulovou funkci, která označí jeden nebo více stavů výpočetní báze jako stavy, které chceme najít, a zesilovací Circuit, který zvyšuje amplitudu označených stavů a potlačuje zbývající stavy.

Zde ukážeme, jak sestavit Groverova orákula a použít grover_operator() z knihovny Qiskit circuit library k snadnému nastavení instance Groverova vyhledávání. Primitiv Sampler za běhu umožňuje bezproblémové spuštění Groverových Circuit.

Požadavky

Před zahájením tohoto tutoriálu se ujisti, že máš nainstalováno následující:

• Qiskit SDK v1.4 nebo novější, s podporou vizualizace
• Qiskit Runtime (pip install qiskit-ibm-runtime) v0.36 nebo novější

Nastavení

# Added by doQumentation — required packages for this notebook
!pip install -q qiskit qiskit-ibm-runtime

# Built-in modules
import math

# Imports from Qiskit
from qiskit import QuantumCircuit
from qiskit.circuit.library import grover_operator, MCMTGate, ZGate
from qiskit.visualization import plot_distribution
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager

# Imports from Qiskit Runtime
from qiskit_ibm_runtime import QiskitRuntimeService
from qiskit_ibm_runtime import SamplerV2 as Sampler

def grover_oracle(marked_states):
    """Build a Grover oracle for multiple marked states

    Here we assume all input marked states have the same number of bits

    Parameters:
        marked_states (str or list): Marked states of oracle

    Returns:
        QuantumCircuit: Quantum circuit representing Grover oracle
    """
    if not isinstance(marked_states, list):
        marked_states = [marked_states]
    # Compute the number of qubits in circuit
    num_qubits = len(marked_states[0])

    qc = QuantumCircuit(num_qubits)
    # Mark each target state in the input list
    for target in marked_states:
        # Flip target bit-string to match Qiskit bit-ordering
        rev_target = target[::-1]
        # Find the indices of all the '0' elements in bit-string
        zero_inds = [
            ind
            for ind in range(num_qubits)
            if rev_target.startswith("0", ind)
        ]
        # Add a multi-controlled Z-gate with pre- and post-applied X-gates (open-controls)
        # where the target bit-string has a '0' entry
        if zero_inds:
            qc.x(zero_inds)
        qc.compose(MCMTGate(ZGate(), num_qubits - 1, 1), inplace=True)
        if zero_inds:
            qc.x(zero_inds)
    return qc

Krok 1: Mapování klasických vstupů na kvantový problém

Groverův algoritmus vyžaduje orákulum, které specifikuje jeden nebo více označených stavů výpočetní báze, přičemž „označený" znamená stav s fází -1. Gate řízené-Z, nebo jeho víceřízená zobecnění přes $N$ Qubitů, označuje stav $2^{N}-1$ ('1'*$N$ bitový řetězec). Označení stavů báze s jednou nebo více hodnotami '0' v binární reprezentaci vyžaduje aplikaci Gate X na odpovídající Qubitů před a po Gate řízené-Z; ekvivalentní otevřenému řízení na daném Qubit. V následujícím kódu definujeme orákulum, které přesně to dělá — označuje jeden nebo více vstupních stavů báze definovaných prostřednictvím jejich bitové řetězcové reprezentace. Gate MCMT slouží k implementaci víceřízeného Gate Z.

# To run on hardware, select the backend with the fewest number of jobs in the queue
service = QiskitRuntimeService()
backend = service.least_busy(
    operational=True, simulator=False, min_num_qubits=127
)
backend.name

'ibm_brisbane'

Konkrétní instance Groverova algoritmu

Nyní, když máme funkci orákula, můžeme definovat konkrétní instanci Groverova vyhledávání. V tomto příkladu označíme dva výpočetní stavy z osmi dostupných v tříqubitovém výpočetním prostoru:

marked_states = ["011", "100"]

oracle = grover_oracle(marked_states)
oracle.draw(output="mpl", style="iqp")

marked_states = ["011", "100"]

oracle = grover_oracle(marked_states)
oracle.draw(output="mpl", style="iqp")

marked_states = ["011", "100"]

oracle = grover_oracle(marked_states)
oracle.draw(output="mpl", style="iqp")

Groverův operátor

Vestavěná funkce Qiskit grover_operator() přijme Circuit orákula a vrátí Circuit, který se skládá ze samotného Circuit orákula a Circuit, který amplifikuje stavy označené orákulem. Zde použijeme metodu decompose() na Circuit, abychom viděli Gate uvnitř operátoru:

grover_op = grover_operator(oracle)
grover_op.decompose().draw(output="mpl", style="iqp")

Opakované aplikace tohoto Circuit grover_op amplifikují označené stavy, čímž se stanou nejpravděpodobnějšími bitovými řetězci ve výstupním rozdělení z Circuit. Existuje optimální počet takových aplikací, který je určen poměrem označených stavů k celkovému počtu možných výpočetních stavů:

optimal_num_iterations = math.floor(
    math.pi
    / (4 * math.asin(math.sqrt(len(marked_states) / 2**grover_op.num_qubits)))
)

Kompletní Groverův Circuit

Kompletní Groverův experiment začíná Gate Hadamard na každém Qubit; vytváří rovnoměrnou superpozici všech stavů výpočetní báze, následovanou Groverovým operátorem (grover_op) opakovaným optimální počet krát. Zde využíváme metody QuantumCircuit.power(INT) k opakované aplikaci Groverova operátoru.

qc = QuantumCircuit(grover_op.num_qubits)
# Create even superposition of all basis states
qc.h(range(grover_op.num_qubits))
# Apply Grover operator the optimal number of times
qc.compose(grover_op.power(optimal_num_iterations), inplace=True)
# Measure all qubits
qc.measure_all()
qc.draw(output="mpl", style="iqp")

Krok 2: Optimalizace problému pro spuštění na kvantovém hardwaru

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)

circuit_isa = pm.run(qc)
circuit_isa.draw(output="mpl", idle_wires=False, style="iqp")

Krok 3: Spuštění pomocí primitiv Qiskit

Amplifikace amplitudy je vzorkovací problém vhodný pro spuštění s primitivem Sampler za běhu.

Poznámka: Metoda run() Qiskit Runtime SamplerV2 přijímá iterovatelný objekt primitive unified blocks (PUBs). Pro Sampler je každý PUB iterovatelný objekt ve formátu (circuit, parameter_values). Nicméně jako minimum přijímá seznam kvantových Circuit.

# To run on local simulator:
#   1. Use the StatevectorSampler from qiskit.primitives instead
sampler = Sampler(mode=backend)
sampler.options.default_shots = 10_000
result = sampler.run([circuit_isa]).result()
dist = result[0].data.meas.get_counts()

Krok 4: Zpracování výsledků a vrácení v požadovaném klasickém formátu

plot_distribution(dist)

Průzkum k tutoriálu

Vyplň prosím tento krátký průzkum a poskytni zpětnou vazbu k tomuto tutoriálu. Tvé poznatky nám pomohou zlepšit naši nabídku obsahu a uživatelský zážitek.

Odkaz na průzkum

Note: This survey is provided by IBM Quantum and relates to the original English content. To give feedback on doQumentation's website, translations, or code execution, please open a GitHub issue.