{ "cells": [ { "cell_type": "markdown", "id": "76d7b924", "metadata": {}, "source": [ "---\n", "title: \"Algoritmo di Grover\"\n", "description: \"Utilizza l'algoritmo di Grover per effettuare ricerche in un database non strutturato con un miglioramento quadratico della velocità.\"\n", "---\n", "\n", "{/* cspell:ignore fontsize */}\n", "\n", "\n", "\n", "# Algoritmo di Grover\n", "\n", "*Stima dei tempi di esecuzione: meno di un minuto su un processore Eagle r3 (NOTA: si tratta solo di una stima). (La durata potrebbe variare.)*\n", "\n" ] }, { "cell_type": "markdown", "id": "88aa4204", "metadata": {}, "source": [ "\n", "\n", "## Risultati di apprendimento\n", "\n", "Una volta completato questo tutorial, avrai acquisito le seguenti conoscenze:\n", "\n", "* Come costruire oracoli di Grover che contrassegnano uno o più stati della base computazionale\n", "* Come utilizzare la `grover_operator()` funzione della libreria di circuiti Qiskit\n", "* Come determinare il numero ottimale di iterazioni di Grover per un dato problema\n", "* Come eseguire l'algoritmo di Grover utilizzando la primitiva \" IBM Quantum \" del Sampler\n", "\n", "\n", "\n", "## Prerequisiti\n", "\n", "Si consiglia di approfondire i seguenti argomenti:\n", "\n", "* [Nozioni fondamentali sugli algoritmi quantistici: l'algoritmo di Grover](/learning/courses/fundamentals-of-quantum-algorithms/grover-algorithm/introduction)\n", "* [Fondamenti dell'informazione quantistica](/learning/courses/basics-of-quantum-information)\n", "\n", "\n", "\n", "## Sfondo\n", "\n", "L'amplificazione dell'ampiezza è un algoritmo quantistico generico, o subroutine, che può essere utilizzato per ottenere un aumento quadratico della velocità rispetto a una serie di algoritmi classici. [L'algoritmo di Grover](https://arxiv.org/abs/quant-ph/9605043) è stato il primo a dimostrare questo aumento di velocità nei problemi di ricerca non strutturati. Per formulare un problema di ricerca di Grover occorre una funzione oracolo che identifichi uno o più stati della base computazionale come gli stati che ci interessa individuare, nonché un circuito di amplificazione che aumenti l'ampiezza degli stati identificati, sopprimendo di conseguenza gli stati rimanenti.\n", "\n", "Qui dimostriamo come costruire gli oracoli di Grover e come utilizzare le librerie di circuiti di Qiskit per creare facilmente un'istanza di ricerca di Grover [`grover_operator()`](/docs/api/qiskit/qiskit.circuit.library.grover_operator) della libreria di circuiti Qiskit per creare facilmente un'istanza di ricerca di Grover. La primitiva runtime `Sampler` consente l'esecuzione senza soluzione di continuità dei circuiti Grover.\n", "\n" ] }, { "cell_type": "markdown", "id": "5bbba268", "metadata": {}, "source": [ "\n", "\n", "## Requisiti\n", "\n", "Prima di iniziare questo tutorial, assicurati di avere installato quanto segue:\n", "\n", "* Qiskit SDK v2.0 o versioni successive, con supporto [alla visualizzazione](/docs/api/qiskit/visualization)\n", "* Qiskit Runtime v0.22 o versioni successive (`pip install qiskit-ibm-runtime`)\n", "\n" ] }, { "cell_type": "markdown", "id": "bfccad15", "metadata": {}, "source": [ "\n", "\n", "## Configura\n", "\n" ] }, { "cell_type": "code", "execution_count": 1, "id": "e2cb0472", "metadata": {}, "outputs": [], "source": [ "# Built-in modules\n", "import math\n", "\n", "# Imports from Qiskit\n", "from qiskit import QuantumCircuit\n", "from qiskit.circuit.library import grover_operator, MCMTGate, ZGate\n", "from qiskit.visualization import plot_distribution\n", "from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager\n", "\n", "# Imports from qiskit-ibm-runtime\n", "from qiskit_ibm_runtime import QiskitRuntimeService\n", "from qiskit_ibm_runtime import SamplerV2 as Sampler\n", "\n", "\n", "def grover_oracle(marked_states):\n", " \"\"\"Build a Grover oracle for multiple marked states\n", "\n", " Here we assume all input marked states have the same number of bits\n", "\n", " Parameters:\n", " marked_states (str or list): Marked states of oracle\n", "\n", " Returns:\n", " QuantumCircuit: Quantum circuit representing Grover oracle\n", " \"\"\"\n", " if not isinstance(marked_states, list):\n", " marked_states = [marked_states]\n", " # Compute the number of qubits in circuit\n", " num_qubits = len(marked_states[0])\n", "\n", " qc = QuantumCircuit(num_qubits)\n", " # Mark each target state in the input list\n", " for target in marked_states:\n", " # Flip target bit-string to match Qiskit bit-ordering\n", " rev_target = target[::-1]\n", " # Find the indices of all the '0' elements in bit-string\n", " zero_inds = [\n", " ind\n", " for ind in range(num_qubits)\n", " if rev_target.startswith(\"0\", ind)\n", " ]\n", " # Add a multi-controlled Z-gate with pre- and post-applied X-gates (open-controls)\n", " # where the target bit-string has a '0' entry\n", " if zero_inds:\n", " qc.x(zero_inds)\n", " qc.compose(MCMTGate(ZGate(), num_qubits - 1, 1), inplace=True)\n", " if zero_inds:\n", " qc.x(zero_inds)\n", " return qc" ] }, { "cell_type": "markdown", "id": "77e41aba", "metadata": {}, "source": [ "\n", "\n", "## Esempio di simulatore su piccola scala\n", "\n", "In questa sezione, analizzeremo passo dopo passo l'algoritmo di Grover su scala ridotta utilizzando un simulatore locale, prima di eseguire lo stesso problema su un hardware quantistico reale.\n", "\n" ] }, { "cell_type": "markdown", "id": "0c0fb667", "metadata": {}, "source": [ "\n", "\n", "### Fase 1: mappare gli input classici su un problema quantistico\n", "\n", "L'algoritmo di Grover richiede un [oracolo](/learning/modules/computer-science/grovers#introduction) che specifichi uno o più stati della base computazionale contrassegnati, dove per \"contrassegnati\" si intendono stati con una fase pari a -1. Un gate a Z controllato, o la sua generalizzazione multi-controllata su qubit di tipo \" $N$ \", definisce lo stato \" $2^{N}-1$ \" (`'1'`\\*stringa di bit $N$ ). Per contrassegnare gli stati di base con uno o più 1 `'0'` nella rappresentazione binaria è necessario applicare porte X ai qubit corrispondenti prima e dopo la porta Z controllata, il che equivale ad applicare un comando di controllo aperto a quel qubit. Nel codice seguente, definiamo un oracolo che identifica uno o più stati di base in ingresso definiti tramite la loro rappresentazione in stringa di bit. Il `MCMT` gate viene utilizzato per realizzare il gate Z a controllo multiplo.\n", "\n" ] }, { "attachments": {}, "cell_type": "markdown", "id": "bca14740", "metadata": {}, "source": [ "\n", "\n", "### Caso specifico di Grover\n", "\n", "Ora che abbiamo la funzione oracolo, possiamo definire un'istanza specifica della ricerca di Grover. In questo esempio segneremo due stati computazionali degli otto disponibili in uno spazio computazionale a tre qubit:\n", "\n" ] }, { "cell_type": "code", "execution_count": 2, "id": "c150298f", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\"Output" ] }, "execution_count": 2, "metadata": {}, "output_type": "execute_result" } ], "source": [ "marked_states = [\"011\", \"100\"]\n", "\n", "oracle = grover_oracle(marked_states)\n", "oracle.draw(output=\"mpl\", style=\"iqp\")" ] }, { "attachments": {}, "cell_type": "markdown", "id": "25487b93", "metadata": {}, "source": [ "\n", "\n", "### Operatore Grover\n", "\n", "Il built-in Qiskit `grover_operator()` prende un circuito oracolo e restituisce un circuito composto dal circuito oracolo stesso e da un circuito che amplifica gli stati contrassegnati dall'oracolo. In questo caso, utilizziamo il metodo `decompose()` per vedere le porte all'interno dell'operatore:\n", "\n" ] }, { "cell_type": "code", "execution_count": 3, "id": "283d5265", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\"Output" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "grover_op = grover_operator(oracle)\n", "grover_op.decompose().draw(output=\"mpl\", style=\"iqp\")" ] }, { "attachments": {}, "cell_type": "markdown", "id": "83c34dc9", "metadata": {}, "source": [ "Applicazioni ripetute di questo circuito `grover_op` amplificano gli stati contrassegnati, rendendoli le stringhe di bit più probabili nella distribuzione in uscita dal circuito. Esiste un numero ottimale di tali applicazioni, determinato dal rapporto tra gli stati contrassegnati e il numero totale di stati computazionali possibili:\n", "\n" ] }, { "cell_type": "code", "execution_count": 4, "id": "f4c3d4b5", "metadata": {}, "outputs": [], "source": [ "optimal_num_iterations = math.floor(\n", " math.pi\n", " / (4 * math.asin(math.sqrt(len(marked_states) / 2**grover_op.num_qubits)))\n", ")" ] }, { "attachments": {}, "cell_type": "markdown", "id": "e06c8238", "metadata": {}, "source": [ "\n", "\n", "### Circuito Grover completo\n", "\n", "Un esperimento di Grover completo inizia con un gate Hadamard su ogni qubit; si crea una sovrapposizione uniforme di tutti gli stati della base computazionale, seguita dall'operatore di Grover (`grover_op`) ripetuto il numero ottimale di volte. Qui utilizziamo il metodo `QuantumCircuit.power(INT)` per applicare ripetutamente l'operatore di Grover.\n", "\n" ] }, { "cell_type": "code", "execution_count": 5, "id": "4933ae44", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\"Output" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "qc = QuantumCircuit(grover_op.num_qubits)\n", "# Create even superposition of all basis states\n", "qc.h(range(grover_op.num_qubits))\n", "# Apply Grover operator the optimal number of times\n", "qc.compose(grover_op.power(optimal_num_iterations), inplace=True)\n", "# Measure all qubits\n", "qc.measure_all()\n", "qc.draw(output=\"mpl\", style=\"iqp\")" ] }, { "cell_type": "markdown", "id": "0649c854", "metadata": {}, "source": [ "\n", "\n", "### Fase 2: Ottimizzazione del problema per l'esecuzione su hardware quantistico\n", "\n", "Per la simulazione su piccola scala, compiliamo il circuito senza specificare un hardware particolare.\n", "\n" ] }, { "cell_type": "code", "execution_count": 6, "id": "c4f67f35", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\"Output" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "pm = generate_preset_pass_manager(optimization_level=3)\n", "circuit_isa = pm.run(qc)\n", "circuit_isa.draw(output=\"mpl\", idle_wires=False, style=\"iqp\")" ] }, { "cell_type": "markdown", "id": "4e0d4d90", "metadata": {}, "source": [ "\n", "\n", "### Passaggio 3: eseguire utilizzando Qiskit primitives\n", "\n", "L'amplificazione dell'ampiezza è un problema di campionamento che si presta all'esecuzione con la [`SamplerV2`](/docs/api/qiskit-ibm-runtime/sampler-v2) primitiva. Qui utilizziamo il `StatevectorSampler` da `qiskit.primitives` per la simulazione locale.\n", "\n" ] }, { "cell_type": "code", "execution_count": 7, "id": "7666ad7c", "metadata": {}, "outputs": [], "source": [ "from qiskit.primitives import StatevectorSampler\n", "\n", "sampler = StatevectorSampler()\n", "result = sampler.run([circuit_isa], shots=10_000).result()\n", "dist = result[0].data.meas.get_counts()" ] }, { "cell_type": "markdown", "id": "5c8263c7", "metadata": {}, "source": [ "\n", "\n", "### Fase 4: Post-elaborazione e restituzione del risultato nel formato classico desiderato\n", "\n" ] }, { "cell_type": "code", "execution_count": 8, "id": "a5ef9913", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\"Output" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "plot_distribution(dist)" ] }, { "cell_type": "markdown", "id": "2b45b2ee", "metadata": {}, "source": [ "\n", "\n", "## Esempio di hardware\n", "\n" ] }, { "cell_type": "markdown", "id": "5fb22680", "metadata": {}, "source": [ "\n", "\n", "### Passaggi da 1 a 4\n", "\n", "L'algoritmo di Grover è fondamentalmente un algoritmo tollerante ai guasti: i gate Z a controllo multiplo che costituiscono il cuore dell'oracolo e dell'operatore di diffusione comportano una profondità dei gate a due qubit che cresce molto rapidamente con il numero di qubit (come mostreremo nella prossima sezione). Ciò significa che l'algoritmo non si adatta bene all'hardware odierno, soggetto a interferenze. Per questo motivo, illustriamo l'esecuzione hardware su una scala ridotta, analoga a quella dell'esempio del simulatore riportato sopra, anziché tentare di affrontare un problema di dimensioni maggiori.\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "id": "be3c3d9e", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\"Output" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# -------------------------Step 1-------------------------\n", "marked_states = [\"011\", \"100\"]\n", "\n", "oracle = grover_oracle(marked_states)\n", "grover_op = grover_operator(oracle)\n", "\n", "optimal_num_iterations = math.floor(\n", " math.pi\n", " / (4 * math.asin(math.sqrt(len(marked_states) / 2**grover_op.num_qubits)))\n", ")\n", "\n", "qc = QuantumCircuit(grover_op.num_qubits)\n", "qc.h(range(grover_op.num_qubits))\n", "qc.compose(grover_op.power(optimal_num_iterations), inplace=True)\n", "qc.measure_all()\n", "\n", "# -------------------------Step 2-------------------------\n", "service = QiskitRuntimeService()\n", "backend = service.least_busy(\n", " operational=True, simulator=False, min_num_qubits=127\n", ")\n", "\n", "target = backend.target\n", "pm = generate_preset_pass_manager(target=target, optimization_level=3)\n", "circuit_isa = pm.run(qc)\n", "\n", "# -------------------------Step 3-------------------------\n", "sampler = Sampler(mode=backend)\n", "sampler.options.default_shots = 10_000\n", "sampler.options.environment.job_tags = [\"TUT-GA\"]\n", "result = sampler.run([circuit_isa]).result()\n", "dist = result[0].data.meas.get_counts()\n", "\n", "# -------------------------Step 4-------------------------\n", "plot_distribution(dist)" ] }, { "cell_type": "markdown", "id": "12e72eab", "metadata": {}, "source": [ "\n", "\n", "## Discussione: Scalabilità della profondità dei gate a due qubit\n", "\n", "Uno dei motivi principali per cui l'algoritmo di Grover è considerato un algoritmo tollerante ai guasti è la rapida crescita della profondità delle porte a due qubit del circuito all'aumentare del numero di qubit. Il gate Z a controllo multiplo, che costituisce il nucleo sia dell'oracolo che dell'operatore di diffusione, si scompone in un numero di gate a due qubit che cresce in modo esponenziale con il numero di qubit di controllo. Se a ciò si aggiunge il fatto che il numero ottimale di iterazioni di Grover cresce esso stesso come un $O(\\sqrt{2^n})$ e, la profondità complessiva a due qubit diventa ben presto impraticabile per un hardware soggetto a rumore.\n", "\n", "Di seguito, costruiamo circuiti di Grover per un numero crescente di qubit, li trasponiamo e tracciamo la profondità delle porte a due qubit risultante per illustrare tale scalabilità.\n", "\n" ] }, { "cell_type": "code", "execution_count": 10, "id": "abc6b43c", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "n=3: optimal_iters=2, 2Q depth=39\n", "n=4: optimal_iters=3, 2Q depth=111\n", "n=5: optimal_iters=4, 2Q depth=466\n", "n=6: optimal_iters=6, 2Q depth=1646\n", "n=7: optimal_iters=8, 2Q depth=3550\n", "n=8: optimal_iters=12, 2Q depth=7989\n", "n=9: optimal_iters=17, 2Q depth=14824\n" ] }, { "data": { "text/plain": [ "\"Output" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "import matplotlib.pyplot as plt\n", "\n", "num_qubits_list = list(range(3, 10))\n", "two_q_depths = []\n", "backend = service.least_busy(\n", " operational=True, simulator=False, min_num_qubits=127\n", ")\n", "for n in num_qubits_list:\n", " # Mark a single state for simplicity\n", " marked = [\"1\" * n]\n", " oracle_n = grover_oracle(marked)\n", " grover_op_n = grover_operator(oracle_n)\n", "\n", " # Optimal number of iterations\n", " num_iters = math.floor(\n", " math.pi / (4 * math.asin(math.sqrt(len(marked) / 2**n)))\n", " )\n", "\n", " # Build the full Grover circuit\n", " qc_n = QuantumCircuit(n)\n", " qc_n.h(range(n))\n", " qc_n.compose(grover_op_n.power(num_iters), inplace=True)\n", " qc_n.measure_all()\n", "\n", " # Transpile to a basis gate set and count 2Q depth\n", " pm_n = generate_preset_pass_manager(backend=backend, optimization_level=3)\n", " qc_transpiled = pm_n.run(qc_n)\n", "\n", " # Compute depth restricted to 2-qubit operations\n", " depth_2q = qc_transpiled.depth(lambda x: x.operation.num_qubits == 2)\n", "\n", " two_q_depths.append(depth_2q)\n", " print(f\"n={n}: optimal_iters={num_iters}, 2Q depth={depth_2q}\")\n", "\n", "# Plot\n", "fig, ax = plt.subplots(figsize=(8, 5))\n", "ax.plot(\n", " num_qubits_list,\n", " two_q_depths,\n", " \"o-\",\n", " linewidth=2,\n", " markersize=8,\n", " color=\"#6929C4\",\n", ")\n", "ax.set_xlabel(\"Number of qubits\", fontsize=13)\n", "ax.set_ylabel(\"Two-qubit gate depth\", fontsize=13)\n", "ax.set_title(\"Grover's algorithm: 2Q depth scaling\", fontsize=14)\n", "ax.set_yscale(\"log\")\n", "ax.grid(True, alpha=0.3)\n", "ax.set_xticks(num_qubits_list)\n", "plt.tight_layout()\n", "plt.show()" ] }, { "cell_type": "markdown", "id": "f3ddda55", "metadata": {}, "source": [ "Come mostra il grafico, la profondità del gate a due qubit cresce in modo estremamente rapido con l'aumentare del numero di qubit — all'incirca in modo esponenziale. Ciò rende l'algoritmo di Grover poco pratico sull'attuale hardware quantistico soggetto a rumore, a meno che i problemi non siano di dimensioni molto ridotte. L'algoritmo rimane un obiettivo importante per i futuri computer quantistici a tolleranza di errore, nei quali la correzione degli errori consentirà l'esecuzione affidabile di circuiti complessi.\n", "\n" ] }, { "cell_type": "markdown", "id": "cf6e8fe6", "metadata": {}, "source": [ "\n", "\n", "## Passi successivi\n", "\n", "\n", " Se questo lavoro ti è sembrato interessante, potrebbero interessarti anche i seguenti contenuti:\n", "\n", " * [Libreria di circuiti Qiskit: `grover_operator()` Riferimento API](/docs/api/qiskit/qiskit.circuit.library.grover_operator)\n", " * [Il tutorial sul](/docs/tutorials/quantum-approximate-optimization-algorithm) QAOA e [la lezione sul QAOA su scala industriale](/learning/courses/quantum-computing-in-practice/utility-scale-qaoa) forniscono esempi a breve termine di ottimizzazione con i computer quantistici\n", " * Per un approfondimento sugli algoritmi a breve termine, consulta il corso [\"Il calcolo quantistico nella pratica\"](/learning/courses/quantum-computing-in-practice)\n", "\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "id": "a1b8767d", "source": "© IBM Corp., 2017-2026" } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3" }, "hours": 1, "qpuSeconds": 60 }, "nbformat": 4, "nbformat_minor": 5 }