Algorithm ni Grover

Tinatayang paggamit: wala pang isang minuto sa Eagle r3 processor (TANDAAN: Ito ay isang tantiya lamang. Maaaring mag-iba ang inyong runtime.)

Background

Ang amplitude amplification ay isang pangkalahatang layuning quantum algorithm, o subroutine, na maaaring gamitin upang makakuha ng quadratic speedup sa ilang classical algorithms. Ang algorithm ni Grover ang unang nagpakita ng speedup na ito sa mga unstructured search problems. Ang pagbuo ng Grover's search problem ay nangangailangan ng oracle function na nagmamarka ng isa o higit pang computational basis states bilang mga states na interesado tayong hanapin, at ng amplification circuit na nagpapataas ng amplitude ng mga markadong states, at dahil dito ay pinipigilan ang natitirang mga states.

Dito, ipapakita natin kung paano bumuo ng mga Grover oracle at gamitin ang grover_operator() mula sa Qiskit circuit library upang madaling mag-set up ng Grover's search instance. Ang runtime Sampler primitive ay nagbibigay-daan sa walang-sagabal na pagpapatupad ng mga Grover circuit.

Requirements

Bago magsimula sa tutorial na ito, siguraduhing mayroon kayong mga sumusunod na naka-install:

• Qiskit SDK v1.4 o mas bago, kasama ang suporta sa visualization
• Qiskit Runtime (pip install qiskit-ibm-runtime) v0.36 o mas bago

Setup

# 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

Step 1: Map classical inputs to a quantum problem

Ang algorithm ni Grover ay nangangailangan ng oracle na tumutukoy ng isa o higit pang markadong computational basis states, kung saan ang "markado" ay nangangahulugang isang state na may phase na -1. Ang controlled-Z gate, o ang multi-controlled generalization nito sa $N$ qubits, ay nagmamarka ng $2^{N}-1$ state ('1'*$N$ bit-string). Ang pagmamarka ng mga basis state na may isa o higit pang '0' sa binary representation ay nangangailangan ng paglalapat ng mga X-gate sa mga kaukulang qubit bago at pagkatapos ng controlled-Z gate; katumbas ng pagkakaroon ng open-control sa qubit na iyon. Sa sumusunod na code, tinutukoy natin ang isang oracle na gumagawa ng ganito, na nagmamarka ng isa o higit pang input basis states na tinukoy sa pamamagitan ng kanilang bit-string representation. Ang MCMT gate ay ginagamit upang ipatupad ang multi-controlled Z-gate.

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

Specific Grover's instance

Ngayong mayroon na tayong oracle function, maaari na tayong tumukoy ng isang partikular na instance ng Grover search. Sa halimbawang ito, markahan natin ang dalawang computational states sa walong magagamit sa three-qubit computational space:

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 operator

Ang built-in Qiskit grover_operator() ay tumatanggap ng oracle circuit at nagbabalik ng circuit na binubuo ng oracle circuit mismo at ng circuit na nagpapalakas ng mga states na minarkahan ng oracle. Dito, ginagamit natin ang decompose() method ng circuit upang makita ang mga gate sa loob ng operator:

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

Ang paulit-ulit na paggamit ng grover_op circuit na ito ay nagpapalakas sa mga markadong states, na ginagawa silang pinakamalamang na mga bit-string sa output distribution mula sa circuit. Mayroong optimal na bilang ng mga application na ito na tinutukoy ng ratio ng mga markadong states sa kabuuang bilang ng posibleng computational states:

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

Full Grover circuit

Ang isang kumpletong Grover experiment ay nagsisimula sa Hadamard gate sa bawat qubit; lumilikha ng pantay na superposition ng lahat ng computational basis states, na sinusundan ng Grover operator (grover_op) na inuulit ng optimal na bilang ng beses. Dito ay ginagamit natin ang QuantumCircuit.power(INT) method upang paulit-ulit na ilapat ang Grover operator.

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

Step 2: Optimize problem for quantum hardware execution

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

Step 3: Execute using Qiskit primitives

Ang amplitude amplification ay isang sampling problem na angkop para sa pagpapatupad gamit ang Sampler runtime primitive.

Tandaan na ang run() method ng Qiskit Runtime SamplerV2 ay tumatanggap ng iterable ng primitive unified blocks (PUBs). Para sa sampler, ang bawat PUB ay isang iterable sa format na (circuit, parameter_values). Gayunpaman, sa minimum, tumatanggap ito ng listahan ng quantum circuit(s).

# 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()

Step 4: Post-process and return result in desired classical format

plot_distribution(dist)

Tutorial survey

Mangyaring sagutin ang maikling survey na ito upang magbigay ng feedback sa tutorial na ito. Ang inyong mga pananaw ay makakatulong sa amin na mapabuti ang aming mga alok sa nilalaman at karanasan ng user.

Link to survey