Algorytm Grovera

Szacowany czas obliczeń: poniżej jednej minuty na procesorze Eagle r3 (UWAGA: Jest to tylko szacunek. Rzeczywisty czas może się różnić.)

Tło

Wzmocnienie amplitudy to ogólny algorytm kwantowy (lub podprogram), który można wykorzystać do uzyskania kwadratowego przyspieszenia względem wielu klasycznych algorytmów. Algorytm Grovera był pierwszym, który zademonstrował to przyspieszenie w przypadku przeszukiwania nieuporządkowanych danych. Sformułowanie problemu wyszukiwania Grovera wymaga funkcji wyroczni, która oznacza jeden lub więcej stanów bazy obliczeniowej jako stany, które chcemy znaleźć, oraz obwodu wzmacniającego, który zwiększa amplitudę oznaczonych stanów, a tym samym tłumi pozostałe.

Tutaj pokazujemy, jak konstruować wyrocznie Grovera i używać funkcji grover_operator() z biblioteki obwodów Qiskit, aby w prosty sposób skonfigurować instancję wyszukiwania Grovera. Primityw Sampler środowiska uruchomieniowego umożliwia bezproblemowe wykonywanie obwodów Grovera.

Wymagania

Przed rozpoczęciem tego samouczka upewnij się, że masz zainstalowane następujące elementy:

• Qiskit SDK v1.4 lub nowszy, z obsługą wizualizacji
• Qiskit Runtime (pip install qiskit-ibm-runtime) v0.36 lub nowszy

Konfiguracja

# 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: Odwzorowanie klasycznych danych wejściowych na problem kwantowy

Algorytm Grovera wymaga wyroczni, która określa jeden lub więcej oznaczonych stanów bazy obliczeniowej, gdzie „oznaczony" oznacza stan z fazą -1. Gate kontrolowana-Z lub jej wielokrotnie kontrolowane uogólnienie na $N$ Qubitach oznacza stan $2^{N}-1$ ('1'*$N$ bitów). Oznaczenie stanów bazy z co najmniej jednym '0' w reprezentacji binarnej wymaga zastosowania bramek X na odpowiednich Qubitach przed i po bramce controlled-Z — co jest równoważne posiadaniu otwartego sterowania na tym Qubicie. W poniższym kodzie definiujemy wyrocznię, która robi dokładnie to: oznacza jeden lub więcej wejściowych stanów bazy, zdefiniowanych przez reprezentację bitową. Gate MCMT służy do implementacji wielokrotnie kontrolowanej bramki 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'

Konkretna instancja wyszukiwania Grovera

Teraz, gdy mamy funkcję wyroczni, możemy zdefiniować konkretną instancję wyszukiwania Grovera. W tym przykładzie oznaczymy dwa stany obliczeniowe spośród ośmiu dostępnych w trójQubitowej przestrzeni obliczeniowej:

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

Operator Grovera

Wbudowana funkcja Qiskit grover_operator() przyjmuje obwód wyroczni i zwraca obwód złożony z samego obwodu wyroczni oraz obwodu wzmacniającego stany oznaczone przez wyrocznię. Tutaj używamy metody decompose() na obwodzie, aby zobaczyć bramki wewnątrz operatora:

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

Wielokrotne zastosowania obwodu grover_op wzmacniają oznaczone stany, czyniąc je najbardziej prawdopodobnymi ciągami bitów w wynikowym rozkładzie z obwodu. Istnieje optymalna liczba takich zastosowań, wyznaczana przez stosunek liczby oznaczonych stanów do całkowitej liczby możliwych stanów obliczeniowych:

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

Pełny Circuit Grovera

Pełny eksperyment Grovera rozpoczyna się od bramki Hadamarda na każdym Qubicie, tworząc równą superpozycję wszystkich stanów bazy obliczeniowej, a następnie operator Grovera (grover_op) jest stosowany optymalną liczbę razy. Tutaj korzystamy z metody QuantumCircuit.power(INT), aby wielokrotnie zastosować operator Grovera.

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: Optymalizacja problemu pod kątem wykonania na sprzęcie kwantowym

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: Wykonanie przy użyciu prymitywów Qiskit

Wzmocnienie amplitudy to problem próbkowania, który nadaje się do wykonania przy użyciu prymitywu środowiska uruchomieniowego Sampler.

Należy zwrócić uwagę, że metoda run() obiektu Qiskit Runtime SamplerV2 przyjmuje iterowalną kolekcję primitive unified blocks (PUBs). W przypadku Samplera każdy PUB jest iterowalną kolekcją w formacie (circuit, parameter_values). Jednak wymagana jest co najmniej lista obwodów kwantowych.

# 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: Przetwarzanie końcowe i zwrócenie wyniku w pożądanym formacie klasycznym

plot_distribution(dist)

Ankieta dotycząca samouczka

Prosimy o wypełnienie krótkiej ankiety, aby podzielić się opinią na temat tego samouczka. Twoje spostrzeżenia pomogą nam udoskonalić nasze materiały i doświadczenie użytkownika.

Link do ankiety

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.