{ "cells": [ { "cell_type": "markdown", "id": "bfa8f443", "metadata": {}, "source": [ "---\n", "title: \"L'algoritmo Deutsch-Jozsa\"\n", "description: \"Scopri come l'algoritmo Deutsch-Jozsa utilizza il parallelismo quantistico e l'interferenza per ottenere un aumento esponenziale della velocità rispetto agli algoritmi classici.\"\n", "---\n", "\n", "{/* cspell:ignore blackbox Hadamards */}\n", "\n" ] }, { "cell_type": "markdown", "id": "e761a401-3dd0-4c3c-9333-0d89da48fb34", "metadata": {}, "source": [ "\n", "\n", "# L'algoritmo Deutsch-Jozsa\n", "\n", "Per questo modulo Qiskit in Classrooms, gli studenti devono avere un ambiente Python funzionante con i seguenti pacchetti installati:\n", "\n", "* `qiskit` v2.1.0 o più recente\n", "* `qiskit-ibm-runtime` v0.40.1 o più recente\n", "* `qiskit-aer` v0.17.0 o più recente\n", "* `qiskit.visualization`\n", "* `numpy`\n", "* `pylatexenc`\n", "\n", "Per configurare e installare i pacchetti di cui sopra, consultare la guida [Installare Qiskit](/docs/guides/install-qiskit).\n", "Per poter eseguire lavori su veri computer quantistici, gli studenti dovranno creare un account con IBM Quantum® seguendo i passaggi della guida [Set up your IBM Cloud account](/docs/guides/cloud-setup).\n", "\n", "Questo modulo è stato testato e ha utilizzato quattro secondi di tempo della QPU. Si tratta solo di una stima. L'utilizzo effettivo può variare.\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "id": "24a83c6d", "metadata": {}, "outputs": [], "source": [ "# Uncomment and modify this line as needed to install dependencies\n", "#!pip install 'qiskit>=2.1.0' 'qiskit-ibm-runtime>=0.40.1' 'qiskit-aer>=0.17.0' 'numpy' 'pylatexenc'" ] }, { "cell_type": "markdown", "id": "026f7f82-ac54-413d-8158-e58461bc2afd", "metadata": {}, "source": [ "Guardate la presentazione del modulo da parte della dottoressa Katie McCormick qui sotto, oppure fate clic [qui](https://youtu.be/QcK0GK7DUh8?si=8e0Lmjgylxmgl2y7) per guardarla su YouTube.\n", "\n", "***\n", "\n", "\n", "\n" ] }, { "cell_type": "markdown", "id": "34b2aac3-848f-46b4-8c95-8236b6ad7f8e", "metadata": {}, "source": [ "\n", "\n", "## Introduzione\n", "\n", "All'inizio degli anni '80, i fisici quantistici e gli informatici avevano una vaga idea che la meccanica quantistica potesse essere sfruttata per effettuare calcoli molto più potenti di quelli che possono fare i computer classici. Il loro ragionamento era il seguente: è difficile per un computer classico simulare i sistemi quantistici, ma un computer *quantistico* dovrebbe essere in grado di farlo in modo più efficiente. E se un computer quantistico poteva simulare i sistemi quantistici in modo più efficiente, forse c'erano altri compiti che poteva svolgere in modo più efficiente di un computer classico.\n", "\n", "La logica era solida, ma i dettagli erano ancora da definire. Tutto è iniziato nel 1985, quando David Deutsch ha descritto il primo \"computer quantistico universale\" In questo stesso articolo, ha fornito il primo esempio di problema per il quale un computer quantistico potrebbe risolvere qualcosa in modo più efficiente di un computer classico. Questo primo esempio giocattolo è oggi noto come \"algoritmo di Deutsch\" Il miglioramento dell'algoritmo di Deutsch era modesto, ma Deutsch collaborò con Richard Jozsa qualche anno dopo per ampliare ulteriormente il divario tra computer classici e quantistici.\n", "\n", "Questi algoritmi - quello di Deutsch e l'estensione Deutsch-Jozsa - non sono particolarmente utili, ma sono comunque molto importanti per alcune ragioni:\n", "\n", "1. Storicamente, sono stati alcuni dei primi algoritmi quantistici che hanno dimostrato di battere le loro controparti classiche. La loro comprensione può aiutarci a capire come si è evoluto nel tempo il pensiero della comunità sull'informatica quantistica.\n", "2. Possono aiutarci a comprendere alcuni aspetti della risposta a una domanda sorprendentemente sottile: Cosa conferisce al calcolo quantistico la sua potenza? A volte i computer quantistici vengono paragonati a giganteschi processori paralleli a scala esponenziale. Ma questo non è del tutto corretto. Sebbene una parte della risposta a questa domanda risieda nel cosiddetto \"parallelismo quantistico\", l'estrazione della maggior quantità possibile di informazioni in una singola esecuzione è un'arte sottile. Gli algoritmi Deutsch e Deutsch-Jozsa mostrano come ciò possa essere fatto.\n", "\n", "In questo modulo impareremo a conoscere l'algoritmo di Deutsch e l'algoritmo di Deutsch-Jozsa e a capire cosa ci insegnano sulla potenza dell'informatica quantistica.\n", "\n" ] }, { "cell_type": "markdown", "id": "096da154-5663-4f46-8d9e-b6f163260706", "metadata": {}, "source": [ "\n", "\n", "## Il parallelismo quantistico e i suoi limiti\n", "\n", "Parte della potenza dell'informatica quantistica deriva dal \"parallelismo quantistico\" che è essenzialmente la capacità di eseguire operazioni su più ingressi allo stesso tempo, poiché gli stati dei qubit in ingresso potrebbero essere una sovrapposizione di più stati classicamente consentiti. Tuttavia, mentre un circuito quantistico potrebbe essere in grado di valutare più stati in ingresso contemporaneamente, estrarre tutte le informazioni in una sola volta è impossibile.\n", "\n", "Per capire cosa intendo, diciamo che abbiamo un bit, $x$ e una funzione applicata a quel bit, $f(x)$. Esistono quattro possibili funzioni binarie che portano un singolo bit a un altro singolo bit:\n", "\n", "| $x$ | $f_1(x)$ | $f_2(x)$ | $f_3(x)$ | $f_4(x)$ |\n", "| --- | -------- | -------- | -------- | -------- |\n", "| 0 | 0 | 0 | 1 | 1 |\n", "| 1 | 0 | 1 | 0 | 1 |\n", "\n", "Vorremmo scoprire quale di queste funzioni (1-4) è il nostro $f(x)$. Classicamente, dovremmo eseguire la funzione due volte, una per $x=0$ e una per $x=1$. Ma vediamo se possiamo fare di meglio con un circuito quantistico. Possiamo conoscere la funzione con la seguente porta:\n", "\n", "![quantum\\_parallelismo](https://quantum.cloud.ibm.com/learning/images/modules/computer-science/deutsch-jozsa/quantum-parallelism.avif)\n", "\n", "In questo caso, la porta $U_f$ calcola $f(x)$, dove $x$ è lo stato del qubit 0, e lo applica al qubit 1. Quindi, lo stato risultante, $|x\\rangle|y\\oplus f(x)\\rangle$, diventa semplicemente $|x\\rangle|f(x)\\rangle$ quando $|y\\rangle = |0\\rangle$. Questo contiene tutte le informazioni necessarie per conoscere la funzione $f(x)$ : il qubit 0 ci dice cos'è $x$ e il qubit 1 ci dice cos'è $f(x)$. Quindi, se inizializziamo $|x\\rangle = \\frac{1}{\\sqrt{2}}(|0\\rangle+|1\\rangle)$, lo stato finale di entrambi i qubit sarà: $|y\\rangle|x\\rangle = \\frac{1}{\\sqrt{2}}(|f(0)\\rangle|0\\rangle+|f(1)\\rangle|1\\rangle)$. Ma come possiamo accedere a queste informazioni?\n", "\n", "\n", "\n", "### 2.1. Provalo su Qiskit:\n", "\n", "Utilizzando Qiskit, selezioneremo a caso una delle quattro possibili funzioni di cui sopra e faremo funzionare il circuito. Il vostro compito è quello di utilizzare le misure del circuito quantistico per imparare la funzione nel minor numero possibile di esecuzioni.\n", "\n", "In questo primo esperimento e in tutto il modulo, utilizzeremo un framework per il calcolo quantistico noto come \"Qiskit patterns\", che suddivide i flussi di lavoro nelle seguenti fasi:\n", "\n", "* Fase 1: mappare gli input classici in un problema quantistico\n", "* Fase 2: Ottimizzazione del problema per l'esecuzione quantistica\n", "* Fase 3: Esecuzione tramite le primitive \" IBM Quantum \"\n", "* Fase 4: post-elaborazione e analisi classica\n", "\n", "Cominciamo con l'installare alcuni pacchetti necessari, tra cui le primitive di IBM Quantum. Sceglieremo inoltre il computer quantistico meno carico tra quelli a nostra disposizione.\n", "\n", "Di seguito è riportato un codice per salvare le credenziali al primo utilizzo. Assicurarsi di eliminare queste informazioni dal blocco note dopo averlo salvato nel proprio ambiente, in modo che le credenziali non vengano accidentalmente condivise quando si condivide il blocco note. Per ulteriori informazioni, vedere [Configurazione dell'account IBM Cloud](/docs/guides/initialize-account) e [Inizializzazione del servizio in un ambiente non attendibile](/docs/guides/cloud-setup-untrusted).\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "id": "6ccc7364-7b6b-45f5-94b8-b1274006ee2f", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "ibm_brisbane\n" ] } ], "source": [ "# Load IBM Quantum Compute Service\n", "from qiskit_ibm_runtime import QiskitRuntimeService\n", "\n", "# Load the Runtime primitive and session\n", "from qiskit_ibm_runtime import SamplerV2 as Sampler\n", "\n", "# Syntax for first saving your token. Delete these lines after saving your credentials.\n", "\n", "# QiskitRuntimeService.save_account(channel='ibm_quantum_platform',\n", "# instance = '', token='', overwrite=True, set_as_default=True)\n", "# service = QiskitRuntimeService(channel='ibm_quantum_platform')\n", "\n", "# Load saved credentials\n", "service = QiskitRuntimeService()\n", "\n", "# Use the least busy backend, or uncomment the loading of a specific backend like \"ibm_brisbane\".\n", "# backend = service.least_busy(operational=True, simulator=False, min_num_qubits = 127)\n", "backend = service.backend(\"ibm_brisbane\")\n", "print(backend.name)\n", "\n", "\n", "sampler = Sampler(mode=backend)" ] }, { "cell_type": "markdown", "id": "9912a7c5-ce2b-4eaa-abe7-82ebd4e494c8", "metadata": {}, "source": [ "La cella sottostante consente di passare dall'uso del simulatore a quello dell'hardware reale nel corso del notebook. Si consiglia di eseguirlo subito:\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "id": "29468e63-ce36-4eb7-95b4-176788a97e54", "metadata": {}, "outputs": [], "source": [ "# Load the backend sampler\n", "from qiskit.primitives import BackendSamplerV2\n", "\n", "# Load the Aer simulator and generate a noise model based on the currently-selected backend.\n", "from qiskit_aer import AerSimulator\n", "from qiskit_aer.noise import NoiseModel\n", "\n", "# Alternatively, load a fake backend with generic properties and define a simulator.\n", "\n", "\n", "noise_model = NoiseModel.from_backend(backend)\n", "\n", "# Define a simulator using Aer, and use it in Sampler.\n", "backend_sim = AerSimulator(noise_model=noise_model)\n", "sampler_sim = BackendSamplerV2(backend=backend_sim)\n", "\n", "# You could also define a simulator-based sampler using a generic backend:\n", "# backend_gen = GenericBackendV2(num_qubits=18)\n", "# sampler_gen = BackendSamplerV2(backend=backend_gen)" ] }, { "cell_type": "markdown", "id": "19e9b62f-6e1c-43a1-bdda-75766b1ff7d3", "metadata": {}, "source": [ "Ora che abbiamo caricato i pacchetti necessari, possiamo procedere con il flusso di lavoro dei modelli Qiskit. Nella fase di mappatura che segue, si crea prima una funzione che seleziona tra le quattro possibili funzioni che portano un singolo bit a un altro singolo bit.\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "id": "5e67183b-42b9-44c2-bd4b-b5e2d192a796", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\"Output" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Step 1: Map\n", "\n", "from qiskit import QuantumCircuit\n", "\n", "qc = QuantumCircuit(2)\n", "\n", "\n", "def twobit_function(case: int):\n", " \"\"\"\n", " Generate a valid two-bit function as a `QuantumCircuit`.\n", " \"\"\"\n", " if case not in [1, 2, 3, 4]:\n", " raise ValueError(\"`case` must be 1, 2, 3, or 4.\")\n", "\n", " f = QuantumCircuit(2)\n", " if case in [2, 3]:\n", " f.cx(0, 1)\n", " if case in [3, 4]:\n", " f.x(1)\n", " return f\n", "\n", "\n", "# first, convert oracle circuit (above) to a single gate for drawing purposes. otherwise, the\n", "# circuit is too large to display\n", "\n", "# you may edit the number inside \"twobit_function()\" to select among the four valid functions:\n", "# blackbox = twobit_function(2).to_gate()\n", "\n", "# blackbox.label = \"$U_f$\"\n", "\n", "qc.h(0)\n", "qc.barrier()\n", "qc.compose(twobit_function(2), inplace=True)\n", "qc.measure_all()\n", "\n", "\n", "qc.draw(\"mpl\")" ] }, { "cell_type": "markdown", "id": "5cf08592-f32e-4ae8-ad69-afb160e43ab4", "metadata": {}, "source": [ "Nel circuito sopra descritto, la porta di Hadamard \"H\" porta il qubit 0, che inizialmente si trova nello stato $|0\\rangle$, allo stato di sovrapposizione $\\frac{1}{\\sqrt{2}}(|0\\rangle+|1\\rangle)$. Quindi, $U_f$ valuta la funzione $f(x)$ e la applica al qubit 1.\n", "\n", "Successivamente dobbiamo ottimizzare e transpilare il circuito per farlo funzionare sul computer quantistico:\n", "\n" ] }, { "cell_type": "code", "execution_count": 4, "id": "d8d77417-0295-4f20-aff6-b2a007d5d02f", "metadata": {}, "outputs": [], "source": [ "# Step 2: Transpile\n", "from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager\n", "\n", "target = backend.target\n", "pm = generate_preset_pass_manager(target=target, optimization_level=3)\n", "\n", "qc_isa = pm.run(qc)" ] }, { "cell_type": "markdown", "id": "51e7b705-a4b8-460a-aa5a-6122c84f9b2f", "metadata": {}, "source": [ "Infine, eseguiamo il nostro circuito transpilato sul computer quantistico e visualizziamo i nostri risultati:\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "id": "0495256b-2a80-422e-9adf-2fef1c039a6d", "metadata": {}, "outputs": [], "source": [ "# Step 3: Run the job on a real quantum computer\n", "\n", "job = sampler.run([qc_isa], shots=1)\n", "# job = sampler_sim.run([qc_isa],shots=1) # uncomment this line to run on simulator instead\n", "res = job.result()\n", "counts = res[0].data.meas.get_counts()" ] }, { "cell_type": "code", "execution_count": 6, "id": "6d2904cc-c730-4dca-a167-438018230299", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\"Output" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Step 4: Visualize and analyze results\n", "\n", "## Analysis\n", "from qiskit.visualization import plot_histogram\n", "\n", "plot_histogram(counts)" ] }, { "cell_type": "markdown", "id": "47710bb8-372c-4949-9468-bd2480c4ae5b", "metadata": {}, "source": [ "L'istogramma sopra riportato rappresenta i nostri risultati. A seconda del numero di scatti scelti per eseguire il circuito al punto 3, si possono vedere una o due barre, che rappresentano gli stati misurati dei due qubit in ogni scatto. Come sempre in Qiskit e in questo quaderno, usiamo la notazione \"little endian\", cioè gli stati dei qubit da 0 a n sono scritti in ordine crescente da destra a sinistra, quindi il qubit 0 è sempre il più a destra.\n", "\n", "Quindi, poiché il qubit 0 era in uno stato di sovrapposizione, il circuito ha valutato la funzione *sia* per $x=0$ che per $x=1$ *allo stesso tempo* - cosa che i computer classici non possono fare! Ma l'inghippo arriva quando vogliamo conoscere la funzione $f(x)$ - quando misuriamo i qubit, facciamo collassare il loro stato. Se si seleziona \"scatti = 1\" per eseguire il circuito una sola volta, si vedrà solo una barra nell'istogramma qui sopra e le informazioni sulla funzione saranno incomplete.\n", "\n", "\n", "\n", "#### Verifica la tua comprensione\n", "\n", "Quante volte dobbiamo eseguire l'algoritmo di cui sopra per imparare la funzione $f(x)$? È migliore del caso classico? Preferireste un computer classico o quantistico per risolvere questo problema?\n", "\n", "\n", " \n", " Poiché la misura collassa la sovrapposizione e restituisce un solo valore, dobbiamo eseguire il circuito *almeno* due volte per restituire entrambe le uscite della funzione $f(0)$ e $f(1)$. Nel caso migliore, le prestazioni sono pari a quelle del caso classico, in cui si calcolano sia $f(0)$ che $f(1)$ nelle prime due interrogazioni. Ma è possibile che sia necessario eseguirlo più di due volte, poiché la misura finale è probabilistica e potrebbe restituire lo stesso valore $f(x)$ le prime due volte. In questo caso preferirei un computer classico.\n", " \n", "\n", "\n", "Quindi, anche se il parallelismo quantistico può essere potente se usato nel modo giusto, non è corretto dire che un computer quantistico funziona proprio come un processore parallelo classico e massiccio. L'atto della misurazione fa collassare gli stati quantistici, per cui possiamo sempre accedere a un solo risultato della computazione.\n", "\n" ] }, { "cell_type": "markdown", "id": "cda50fdf-c354-4021-9b5a-c8cde5cc5edd", "metadata": {}, "source": [ "\n", "\n", "## Algoritmo di Deutsch\n", "\n", "Sebbene il parallelismo quantistico da solo non ci dia un vantaggio rispetto ai computer classici, possiamo abbinarlo a un altro fenomeno quantistico, l'interferenza, per ottenere una maggiore velocità. L'algoritmo oggi noto come \"algoritmo di Deutsch\" è il primo esempio di algoritmo che realizza questo obiettivo.\n", "\n", "\n", "\n", "### Il problema\n", "\n", "Il problema era questo:\n", "\n", "Dato un bit di ingresso, $x = \\{0,1\\}$, e una funzione di ingresso $f(x) = \\{0,1\\}$, determinare se la funzione è *bilanciata* o *costante*. Cioè, se è bilanciata, l'uscita della funzione è 0 per metà del tempo e 1 per l'altra metà del tempo. Se è costante, allora l'uscita della funzione è sempre 0 o sempre 1. Ricordiamo la tabella delle quattro possibili funzioni che portano un singolo bit a un altro singolo bit:\n", "\n", "| $x$ | $f_1(x)$ | $f_2(x)$ | $f_3(x)$ | $f_4(x)$ |\n", "| --- | -------- | -------- | -------- | -------- |\n", "| 0 | 0 | 0 | 1 | 1 |\n", "| 1 | 0 | 1 | 0 | 1 |\n", "\n", "La prima e l'ultima funzione, $f_1(x)$ e $f_4(x)$, sono costanti, mentre le due funzioni centrali, $f_2(x)$ e $f_3(x)$, sono bilanciate.\n", "\n" ] }, { "cell_type": "markdown", "id": "a34f1c24-0ed5-4458-8d4e-5957c691cadb", "metadata": {}, "source": [ "\n", "\n", "### L'algoritmo\n", "\n", "Il modo in cui Deutsch ha affrontato questo problema è stato il \"modello della query\" Nel modello di interrogazione, la funzione di input ( $f_i(x)$ ) è contenuta in una \"scatola nera\": non abbiamo accesso diretto al suo contenuto, ma possiamo interrogare la scatola nera e questa ci darà l'output della funzione. A volte diciamo che un \"oracolo\" fornisce queste informazioni. Si veda la [Lezione 1: Algoritmi di interrogazione quantistica](/learning/courses/fundamentals-of-quantum-algorithms/quantum-query-algorithms/introduction) del corso Fondamenti di algoritmi quantistici per ulteriori informazioni sul modello di interrogazione.\n", "\n", "Per determinare se un algoritmo quantistico è più efficiente di un algoritmo classico nel modello di interrogazione, possiamo semplicemente confrontare il numero di interrogazioni che dobbiamo fare alla scatola nera in ciascun caso. Nel caso classico, per sapere se la funzione contenuta nella scatola nera è bilanciata o costante, dovremmo interrogare la scatola due volte per ottenere sia $f(0)$ che $f(1)$.\n", "\n", "Con l'algoritmo quantistico di Deutsch, però, ha trovato un modo per ottenere le informazioni con una sola interrogazione! Ha apportato un aggiustamento al circuito del \"parallelismo quantistico\" di cui sopra, in modo da preparare uno stato di sovrapposizione su *entrambi i* qubit, invece che solo sul qubit 0. Quindi le due uscite della funzione, $f(0)$ e $f(1)$, interferiscono per restituire 0 se sono entrambe 0 o entrambe 1 (la funzione è costante), e restituiscono 1 se sono diverse (la funzione è bilanciata). In questo modo, Deutsch poteva distinguere tra una funzione costante e una funzione bilanciata con un'unica interrogazione.\n", "\n", "Ecco lo schema del circuito dell'algoritmo di Deutsch:\n", "\n", "![Schema del circuito dell'algoritmo di Deutsch](https://quantum.cloud.ibm.com/learning/images/modules/computer-science/deutsch-jozsa/Deutsch_algo.avif)\n", "\n", "Per capire come funziona questo algoritmo, osserviamo gli stati quantici dei qubit nei tre punti indicati nel diagramma precedente. Provate a risolvere da soli gli stati prima di cliccare per visualizzare le risposte:\n", "\n", "\n", "\n", "#### Verifica la tua comprensione\n", "\n", "Qual è lo stato $|\\pi_1\\rangle$?\n", "\n", "\n", " \n", " Applicando una trasformata di Hadamard, lo stato $|0\\rangle$ diventa $\\frac{1}{\\sqrt{2}}(|0\\rangle+|1\\rangle)$ e lo stato $|1\\rangle$ diventa $\\frac{1}{\\sqrt{2}}(|0\\rangle-|1\\rangle)$. Quindi, lo stato completo diventa: $|\\pi_1\\rangle = [\\frac{|0\\rangle-|1\\rangle}{\\sqrt{2}}][\\frac{|0\\rangle+|1\\rangle}{\\sqrt{2}}]$\n", " \n", "\n", "\n", "Qual è lo stato $|\\pi_2\\rangle$?\n", "\n", "\n", " \n", " Prima di applicare $U_f$, ricordate cosa fa. Cambierà lo stato del qubit 1 in base allo stato del qubit 0. Quindi, è sensato fattorizzare lo stato del qubit 0: $|\\pi_1\\rangle = \\frac{1}{2} (|0\\rangle-|1\\rangle)|0\\rangle+\\frac{1}{2}(|0\\rangle-|1\\rangle)|1\\rangle$. Quindi, se $f(0)=f(1)$, i due termini si trasformano allo stesso modo e il segno relativo tra i due termini rimane positivo, ma se $f(0)\\neq f(1)$, allora significa che il secondo termine prende un segno meno rispetto al primo termine, cambiando lo stato del qubit 0 da $\\frac{1}{\\sqrt{2}}(|0\\rangle+|1\\rangle)$ a $\\frac{1}{\\sqrt{2}}(|0\\rangle-|1\\rangle)$. Quindi:\n", "\n", " $$\n", " |\\pi_2\\rangle = \\begin{cases}\n", " \\pm[\\frac{|0\\rangle-|1\\rangle}{\\sqrt{2}}][\\frac{|0\\rangle+|1\\rangle}{\\sqrt{2}}] & \\text{if} & f(0) = f(1) \\\\\n", " \\pm[\\frac{|0\\rangle-|1\\rangle}{\\sqrt{2}}][\\frac{|0\\rangle-|1\\rangle}{\\sqrt{2}}] &\\text{if} & f(0) \\neq f(1) \\\\\n", " \\end{cases}\n", " $$\n", " \n", "\n", "\n", "Qual è lo stato $|\\pi_3\\rangle$?\n", "\n", "\n", " \n", " Ora, lo stato del qubit 0 è $\\frac{1}{\\sqrt{2}}(|0\\rangle+|1\\rangle)$ o $\\frac{1}{\\sqrt{2}}(|0\\rangle-|1\\rangle)$, a seconda della funzione. Applicando l'Hadamard si ottiene rispettivamente $|0\\rangle$ o $|1\\rangle$.\n", "\n", " $$\n", " |\\pi_3\\rangle = \\begin{cases}\n", " \\pm[\\frac{|0\\rangle-|1\\rangle}{\\sqrt{2}}]|0\\rangle & \\text{if} & f(0) = f(1) \\\\\n", " \\pm[\\frac{|0\\rangle-|1\\rangle}{\\sqrt{2}}]|1\\rangle &\\text{if} & f(0) \\neq f(1) \\\\\n", " \\end{cases}\n", " $$\n", " \n", "\n", "\n", "Esaminando le vostre risposte alle domande precedenti, notate che accade qualcosa di un po' sorprendente. Sebbene $U_f$ non faccia nulla di esplicito allo stato del qubit 0, poiché modifica il qubit 1 in base allo stato del qubit 0, può accadere che ciò provochi uno spostamento di fase nel qubit 0. Questo fenomeno è noto come \"phase-kickback\" e viene discusso più dettagliatamente nella [Lezione 1: Algoritmi di query quantistica](/learning/courses/fundamentals-of-quantum-algorithms/quantum-query-algorithms/introduction) del corso Fondamenti di algoritmi quantistici.\n", "\n", "Ora che abbiamo capito come funziona questo algoritmo, implementiamolo con Qiskit.\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "id": "4d9129df-f2ef-4f94-9508-21ed986fd823", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\"Output" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ "## Deutsch's algorithm:\n", "\n", "## Step 1: Map the problem\n", "\n", "# first, convert oracle circuit (above) to a single gate for drawing purposes.\n", "# otherwise, the circuit is too large to display\n", "blackbox = twobit_function(\n", " 3\n", " # you may edit the number (1-4) inside \"twobit_function()\" to select among the four valid functions\n", ").to_gate()\n", "blackbox.label = \"$U_f$\"\n", "\n", "\n", "qc_deutsch = QuantumCircuit(2, 1)\n", "\n", "qc_deutsch.x(1)\n", "qc_deutsch.h(range(2))\n", "\n", "qc_deutsch.barrier()\n", "qc_deutsch.compose(twobit_function(2), inplace=True)\n", "qc_deutsch.barrier()\n", "\n", "qc_deutsch.h(0)\n", "qc_deutsch.measure(0, 0)\n", "\n", "qc_deutsch.draw(\"mpl\")" ] }, { "cell_type": "code", "execution_count": 8, "id": "ef0196b4-d4f0-4581-96f8-97893e652ee8", "metadata": {}, "outputs": [], "source": [ "# Step 2: Transpile\n", "from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager\n", "\n", "target = backend.target\n", "pm = generate_preset_pass_manager(target=target, optimization_level=3)\n", "\n", "qc_isa = pm.run(qc_deutsch)" ] }, { "cell_type": "code", "execution_count": null, "id": "51ad01d0-fa90-4e80-a55d-e55e146e2065", "metadata": {}, "outputs": [], "source": [ "# Step 3: Run the job on a real quantum computer\n", "\n", "job = sampler.run([qc_isa], shots=1)\n", "# job = sampler_sim.run([qc_isa],shots=1) # uncomment this line to run on simulator instead\n", "res = job.result()\n", "counts = res[0].data.c.get_counts()" ] }, { "cell_type": "code", "execution_count": 10, "id": "5465d833-49e0-4779-94a3-0adb18f6aa76", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "{'1': 1}\n", "balanced\n" ] } ], "source": [ "# Step 4: Visualize and analyze results\n", "\n", "## Analysis\n", "print(counts)\n", "if \"1\" in counts:\n", " print(\"balanced\")\n", "else:\n", " print(\"constant\")" ] }, { "cell_type": "markdown", "id": "82f6da25-0f9c-47b3-aa24-02482f008383", "metadata": {}, "source": [ "\n", "\n", "## L'algoritmo Deutsch-Jozsa\n", "\n", "L'algoritmo di Deutsch è stato un primo passo importante per dimostrare come un computer quantistico possa essere più efficiente di un computer classico, ma si è trattato solo di un miglioramento modesto: ha richiesto una sola interrogazione, rispetto alle due del caso classico. Nel 1992, Deutsch e il suo collega Richard Jozsa estesero l'algoritmo originale a due qubit a un numero maggiore di qubit. Il problema è rimasto lo stesso: determinare se una funzione è *bilanciata* o *costante*. Questa volta, però, la funzione passa da $n$ bit a un singolo bit. O la funzione restituisce 0 e 1 un numero uguale di volte (è *bilanciata* ) o la funzione restituisce sempre 1 o sempre 0 (è *costante* ).\n", "\n", "Ecco lo schema del circuito dell'algoritmo:\n", "\n", "![DJ\\_algo.png](https://quantum.cloud.ibm.com/learning/images/modules/computer-science/deutsch-jozsa/DJ_algo.avif)\n", "\n", "Questo algoritmo funziona come l'algoritmo di Deutsch: il phase-kickback permette di leggere lo stato del qubit 0 per determinare se la funzione è costante o bilanciata. È un po' più difficile da capire rispetto al caso dell'algoritmo di Deutsch a due qubit, poiché gli stati includeranno le somme dei qubit di $n$. Per questo motivo, l'elaborazione di questi stati sarà lasciata come esercizio opzionale alla fine del modulo. L'algoritmo restituirà una stringa di bit con tutti 0 se la funzione è costante e una stringa di bit contenente almeno un 1 se la funzione è bilanciata.\n", "\n", "Per vedere come funziona l'algoritmo in Qiskit, dobbiamo innanzitutto generare il nostro oracolo: la funzione casuale che è garantita essere costante o bilanciata. Il codice seguente genererà una funzione bilanciata il 50% delle volte e una funzione costante il 50% delle volte. Non preoccupatevi se non seguite completamente il codice: è complicato e non è necessario per la comprensione dell'algoritmo quantistico.\n", "\n" ] }, { "cell_type": "code", "execution_count": 11, "id": "ca2a51c0-3e62-4536-b891-0834e325a3d6", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\"Output" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "from qiskit import QuantumCircuit\n", "import numpy as np\n", "\n", "\n", "def dj_function(num_qubits):\n", " \"\"\"\n", " Create a random Deutsch-Jozsa function.\n", " \"\"\"\n", "\n", " qc_dj = QuantumCircuit(num_qubits + 1)\n", " if np.random.randint(0, 2):\n", " # Flip output qubits with 50% chance\n", " qc_dj.x(num_qubits)\n", " if np.random.randint(0, 2):\n", " # return constant circuit with 50% chance.\n", " return qc_dj\n", "\n", " # If the \"if\" statement above was \"TRUE\" then we've returned the constant\n", " # function and the function is complete. If not, we proceed in creating our\n", " # balanced function. Everything below is to produce the balanced function:\n", "\n", " # select half of all possible states at random:\n", " on_states = np.random.choice(\n", " range(2**num_qubits), # numbers to sample from\n", " 2**num_qubits // 2, # number of samples\n", " replace=False, # makes sure states are only sampled once\n", " )\n", "\n", " def add_cx(qc_dj, bit_string):\n", " for qubit, bit in enumerate(reversed(bit_string)):\n", " if bit == \"1\":\n", " qc_dj.x(qubit)\n", " return qc_dj\n", "\n", " for state in on_states:\n", " # qc_dj.barrier() # Barriers are added to help visualize how the functions are created.\n", " # They can safely be removed.\n", " qc_dj = add_cx(qc_dj, f\"{state:0b}\")\n", " qc_dj.mcx(list(range(num_qubits)), num_qubits)\n", " qc_dj = add_cx(qc_dj, f\"{state:0b}\")\n", "\n", " # qc_dj.barrier()\n", "\n", " return qc_dj\n", "\n", "\n", "n = 3 # number of input qubits\n", "\n", "oracle = dj_function(n)\n", "\n", "display(oracle.draw(\"mpl\"))" ] }, { "cell_type": "markdown", "id": "78096e00-a29b-418c-a620-726675c2a792", "metadata": {}, "source": [ "Si tratta della funzione oracolo, che può essere bilanciata o costante. Si può vedere se l'uscita dell'ultimo qubit dipende dai valori inseriti per i primi $n$ qubit? Se l'uscita dell'ultimo qubit dipende dai primi $n$ qubit, si può dire se tale uscita dipendente è bilanciata o meno?\n", "\n", "Possiamo dire se la funzione è bilanciata o costante osservando il circuito di cui sopra, ma ricordate che per questo problema pensiamo a questa funzione come a una \"scatola nera\" Non possiamo sbirciare nella scatola per vedere lo schema del circuito. Invece, è necessario interrogare la casella.\n", "\n", "Per interrogare la scatola, utilizziamo l'algoritmo di Deutsch-Jozsa e determiniamo se la funzione è costante o bilanciata:\n", "\n" ] }, { "cell_type": "code", "execution_count": 12, "id": "fe7ee688-f052-4a7e-bcc7-a14bea57e5c6", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\"Output" ] }, "execution_count": 12, "metadata": {}, "output_type": "execute_result" } ], "source": [ "blackbox = oracle.to_gate()\n", "blackbox.label = \"$U_f$\"\n", "\n", "\n", "qc_dj = QuantumCircuit(n + 1, n)\n", "qc_dj.x(n)\n", "qc_dj.h(range(n + 1))\n", "qc_dj.barrier()\n", "qc_dj.compose(blackbox, inplace=True)\n", "qc_dj.barrier()\n", "qc_dj.h(range(n))\n", "qc_dj.measure(range(n), range(n))\n", "\n", "qc_dj.decompose().decompose()\n", "\n", "\n", "qc_dj.draw(\"mpl\")" ] }, { "cell_type": "code", "execution_count": 13, "id": "bf3aedfa-7454-424e-85cb-c446a8918417", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\"Output" ] }, "execution_count": 13, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Step 1: Map the problem\n", "\n", "qc_dj = QuantumCircuit(n + 1, n)\n", "qc_dj.x(n)\n", "qc_dj.h(range(n + 1))\n", "qc_dj.barrier()\n", "qc_dj.compose(oracle, inplace=True)\n", "qc_dj.barrier()\n", "qc_dj.h(range(n))\n", "qc_dj.measure(range(n), range(n))\n", "\n", "qc_dj.decompose().decompose()\n", "\n", "\n", "qc_dj.draw(\"mpl\")" ] }, { "cell_type": "code", "execution_count": 14, "id": "5497c1aa-c427-419b-b22c-a0c2fa0c4028", "metadata": {}, "outputs": [], "source": [ "# Step 2: Transpile\n", "from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager\n", "\n", "target = backend.target\n", "pm = generate_preset_pass_manager(target=target, optimization_level=3)\n", "\n", "qc_isa = pm.run(qc_dj)" ] }, { "cell_type": "code", "execution_count": null, "id": "974f3db9-1b55-414c-9fe4-d891cf22f78f", "metadata": {}, "outputs": [], "source": [ "# Step 3: Run the job on a real quantum computer\n", "\n", "job = sampler.run([qc_isa], shots=1)\n", "# job = sampler_sim.run([qc_isa],shots=1) # uncomment this line to run on simulator instead\n", "res = job.result()\n", "counts = res[0].data.c.get_counts()" ] }, { "cell_type": "code", "execution_count": 16, "id": "39af76b4-f380-4a61-82a4-1e9203c20408", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "{'110': 1}\n", "balanced\n" ] } ], "source": [ "# Step 4: Visualize and analyze results\n", "\n", "## Analysis\n", "print(counts)\n", "\n", "if (\n", " \"0\" * n in counts\n", "): # The D-J algorithm returns all zeroes if the function was constant\n", " print(\"constant\")\n", "else:\n", " print(\"balanced\") # anything other than all zeroes means the function is balanced." ] }, { "cell_type": "markdown", "id": "c601a252-d1d4-4def-b9a4-d05494d34899", "metadata": {}, "source": [ "Sopra, la prima riga dell'output è la stringa di bit dei risultati della misurazione. La seconda riga indica se la stringa di bit implica che la funzione è bilanciata o costante. Se la stringa di bit contiene tutti zeri, è costante; altrimenti è bilanciata. Quindi, con una sola esecuzione del circuito quantistico di cui sopra, possiamo determinare se la funzione è costante o bilanciata!\n", "\n", "\n", "\n", "#### Verifica la tua comprensione\n", "\n", "Quante interrogazioni occorrerebbero a un computer classico per determinare con certezza al 100% se una funzione è costante o bilanciata? Ricordate che, classicamente, una singola query consente di applicare la funzione solo a una singola stringa di bit.\n", "\n", "\n", " \n", " Ci sono $2^n$ possibili bitstring da controllare e, nel peggiore dei casi, è necessario verificare $2^n/2+1$ di questi. Ad esempio, se la funzione fosse costante e si continuasse a misurare \"1\" come uscita della funzione, non si potrebbe essere certi che sia veramente costante finché non si controlla più della metà dei risultati. Prima di allora, si poteva essere solo molto sfortunati nel continuare a misurare \"1\" su una funzione bilanciata. È come lanciare una moneta in continuazione e ogni volta che cade a testa in giù. È improbabile, ma non impossibile.\n", " \n", "\n", "\n", "Come cambierebbe la risposta di cui sopra se si dovesse semplicemente misurare fino a quando un risultato (equilibrato o costante) è più probabile dell'altro? Quante query sarebbero necessarie in questo caso?\n", "\n", "\n", " \n", " In questo caso, è sufficiente misurare due volte. Se le due misure sono diverse, si sa che la funzione è bilanciata. Se le due misure sono uguali, allora potrebbe essere bilanciato, oppure costante. La probabilità che sia equilibrata con questa serie di misure è: $\\frac{1}{2}\\frac{2^n /2 - 1}{2^n-1}$. Questo valore è inferiore a 1/2, quindi è più probabile che la funzione sia costante in questo caso.\n", " \n", "\n", "\n", "Quindi, l'algoritmo di Deutsch-Jozsa ha dimostrato una velocità esponenziale rispetto a un algoritmo classico *deterministico* (che restituisce la risposta con una certezza del 100%), ma nessuna velocità significativa rispetto a un algoritmo *probabilistico* (che restituisce un risultato che *probabilmente* è la risposta corretta).\n", "\n" ] }, { "cell_type": "markdown", "id": "37d8d1b5-1593-480e-afb9-cdae1debb8ea", "metadata": {}, "source": [ "\n", "\n", "### Il problema di Bernstein-Vazirani\n", "\n", "Nel 1997, Ethan Bernstein e Umesh Vazirani hanno utilizzato l'algoritmo di Deutsch-Jozsa per risolvere un problema più specifico e ristretto rispetto al problema di Deutsch-Jozsa. Invece di cercare semplicemente di distinguere tra due diverse classi di funzioni, come nel caso D-J, Bernstein e Vazirani hanno utilizzato l'algoritmo di Deutsch-Jozsa per imparare effettivamente una stringa codificata in una funzione. Il problema è questo:\n", "\n", "La funzione $f:\\{0,1\\}^n \\rightarrow \\{0,1\\}$ prende ancora una stringa $n$ -bit e produce un singolo bit. Ma ora, invece di promettere che la funzione è bilanciata o costante, ci viene promesso che la funzione è il prodotto di punti tra la stringa in ingresso $x$ e una qualche stringa segreta $n$ -bit $s$, modulo 2. (Questo prodotto di punti modulo 2 è chiamato \"prodotto binario di punti\") Il problema è capire qual è la stringa segreta, $n$ -bit.\n", "\n", "In altre parole, ci viene data una funzione black-box $f: {0,1}^n \\rightarrow {0,1}$ che soddisfa $f(x) = s \\cdot x$ per qualche stringa $s$, e vogliamo imparare la stringa $s$.\n", "\n", "Vediamo come l'algoritmo D-J risolve questo problema:\n", "\n", "1. In primo luogo, un gate Hadamard viene applicato ai qubit di ingresso $n$ e un gate NOT più un Hadamard viene applicato al qubit di uscita, creando lo stato:\n", "\n", "$$\n", "|\\Psi\\rangle = |-\\rangle_{n} \\otimes |+\\rangle_{n-1} \\otimes |+\\rangle_{n-2} \\otimes ... \\otimes |+\\rangle_0\n", "$$\n", "\n", "Lo stato dei qubit da 1 a $n$ può essere scritto più semplicemente come una somma di tutti $2^n$ gli stati base $n$ dei qubit $|00...00\\rangle, |00...01\\rangle, |000...11\\rangle, ..., |111...11\\rangle$. Chiamiamo l'insieme di questi stati base $\\Sigma^n$. (Per maggiori dettagli si veda [Fondamenti degli algoritmi quantistici](/learning/courses/fundamentals-of-quantum-algorithms/quantum-query-algorithms/deutsch-jozsa-algorithm) )\n", "\n", "$$\n", "|\\Psi\\rangle = |-\\rangle \\otimes \\frac{1}{\\sqrt{2^n}}\\sum\\limits_{x \\in \\Sigma^n}{|x\\rangle}\n", "$$\n", "\n", "2. Successivamente, il gate $U_f$ viene applicato ai qubit. Questo gate prende in ingresso i primi n qubit (che ora sono in una sovrapposizione uguale di tutte le possibili stringhe di n bit) e applica la funzione $f(x)=s \\cdot x$ al qubit in uscita, in modo che questo qubit si trovi ora nello stato: $ |- \\oplus f(x)\\rangle$. Grazie al meccanismo del contraccolpo di fase, lo stato di questo qubit rimane invariato, ma alcuni termini dello stato del qubit di ingresso acquistano il segno meno:\n", "\n", "$$\n", "|\\Psi\\rangle = |-\\rangle \\otimes \\frac{1}{\\sqrt{2^n}}\\sum\\limits_{x \\in \\Sigma^n}{(-1)^{f(x)}|x\\rangle}\n", "$$\n", "\n", "3. Ora, la serie successiva di Hadamard viene applicata ai qubit da 0 a $n-1$. In questo caso, tenere traccia dei segni meno può essere complicato. È utile sapere che l'applicazione di uno strato di Hadamard a $n$ qubit in uno stato base standard $|x\\rangle$ può essere scritto come:\n", "\n", "$$\n", "H^{\\otimes n} |x\\rangle = \\frac{1}{\\sqrt{2^n}}\\sum\\limits_{y \\in \\Sigma^n}{(-1)^{x \\cdot y}|y\\rangle}\n", "$$\n", "\n", "Quindi lo stato diventa:\n", "\n", "$$\n", "|\\Psi\\rangle = |-\\rangle \\otimes \\frac{1}{2^n}\\sum\\limits_{x \\in \\Sigma^n}\\sum\\limits_{y \\in \\Sigma^n}{(-1)^{(s \\cdot x) + (x \\cdot y)}|y\\rangle}\n", "$$\n", "\n", "4. Il passo successivo consiste nel misurare i primi $n$ bit. Ma cosa misureremo? Si scopre che lo stato di cui sopra si semplifica in: $|\\Psi\\rangle = |-\\rangle \\otimes |s\\rangle$, ma non è affatto ovvio. Se volete seguire la matematica, consultate il corso [Fundamentals of Quantum Algorithms](/learning/courses/fundamentals-of-quantum-algorithms/quantum-query-algorithms/deutsch-jozsa-algorithm#the-bernstein-vazirani-problem) di John Watrous. Il punto, però, è che il meccanismo di contraccolpo di fase porta i qubit in ingresso nello stato $|s\\rangle$. Quindi, per scoprire quale fosse la stringa segreta $s$ è sufficiente misurare i qubit!\n", "\n", "\n", "\n", "#### Verifica la tua comprensione\n", "\n", "Verificare che lo stato del punto 3 sia effettivamente lo stato $|s\\rangle$ per il caso speciale di $n=1$.\n", "\n", "\n", " \n", " Quando si scrivono esplicitamente le due sommatorie, si dovrebbe ottenere uno stato con quattro termini (omettiamo lo stato di uscita $|-\\rangle$ per questo):\n", "\n", " $$\n", " |\\Psi\\rangle = \\frac{1}{2}[|0\\rangle + (-1)^s |0\\rangle + |1\\rangle + (-1)^{(s+1)} |1\\rangle]\n", " $$\n", "\n", " Se $s=0$, allora i primi due termini si sommano costruttivamente e gli ultimi due termini si annullano, ottenendo $|\\Psi\\rangle = |0\\rangle$. Se $s=1$, allora gli ultimi due termini si sommano costruttivamente e i primi due termini si annullano, ottenendo $|\\Psi\\rangle = |1\\rangle$. Quindi, in entrambi i casi, $|\\Psi\\rangle = |s\\rangle$. Si spera che questo caso più semplice dia un'idea di come funziona il caso generale con $n$ qubit: tutti i termini che non sono $|s\\rangle$ interferiscono, lasciando solo lo stato $|s\\rangle$.\n", " \n", "\n", "\n", "Come può lo stesso algoritmo risolvere i problemi di Bernstein-Vazirani e Deutsch-Jozsa? Per capirlo, si pensi alle funzioni di Bernstein-Vazirani, che hanno la forma $f(x) = s \\cdot x$. Queste funzioni sono anche funzioni di Deutsch-Jozsa? Cioè, determinare se le funzioni di questa forma soddisfano la promessa del problema di Deutsch-Jozsa: che siano *costanti* o *equilibrate*. In che modo questo ci aiuta a capire come lo stesso algoritmo risolva due problemi diversi?\n", "\n", "\n", " \n", " Ogni funzione di Bernstein-Vazirani della forma $f(x) = s \\cdot x$ soddisfa anche la promessa del problema di Deutsch-Jozsa: se s=00...00, allora la funzione è costante (restituisce sempre 0 per ogni stringa x). Se s è una qualsiasi altra stringa, la funzione è bilanciata. Quindi, applicando l'algoritmo di Deutsch-Jozsa a una di queste funzioni si risolvono contemporaneamente entrambi i problemi! Restituisce la stringa, e se questa stringa è 00...00 allora sappiamo che è costante; se c'è almeno un \"1\" nella stringa, sappiamo che è bilanciata.\n", " \n", "\n", "\n", "Possiamo anche verificare che questo algoritmo risolve con successo il problema di Bernstein-Vazirani testandolo sperimentalmente. Per prima cosa, creiamo la funzione B-V che vive all'interno della scatola nera:\n", "\n" ] }, { "cell_type": "code", "execution_count": 17, "id": "45449a26-0bd0-4244-87be-3309937955b9", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\"Output" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# Step 1: Map the problem\n", "\n", "\n", "def bv_function(s):\n", " \"\"\"\n", " Create a Bernstein-Vazirani function from a string of 1s and 0s.\n", " \"\"\"\n", " qc = QuantumCircuit(len(s) + 1)\n", " for index, bit in enumerate(reversed(s)):\n", " if bit == \"1\":\n", " qc.cx(index, len(s))\n", " return qc\n", "\n", "\n", "display(bv_function(\"1000\").draw(\"mpl\"))" ] }, { "cell_type": "code", "execution_count": 18, "id": "0cf6f2bc-3b5e-46d2-ab82-1a190e77c42b", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\"Output" ] }, "execution_count": 18, "metadata": {}, "output_type": "execute_result" } ], "source": [ "string = \"1000\" # secret string that we'll pretend we don't know or have access to\n", "n = len(string)\n", "\n", "qc = QuantumCircuit(n + 1, n)\n", "qc.x(n)\n", "qc.h(range(n + 1))\n", "qc.barrier()\n", "# qc.compose(oracle, inplace = True)\n", "qc.compose(bv_function(string), inplace=True)\n", "qc.barrier()\n", "qc.h(range(n))\n", "qc.measure(range(n), range(n))\n", "\n", "qc.draw(\"mpl\")" ] }, { "cell_type": "code", "execution_count": 19, "id": "5d225a6e-e3d0-4c08-8aeb-f03337bfffc4", "metadata": {}, "outputs": [], "source": [ "# Step 2: Transpile\n", "from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager\n", "\n", "target = backend.target\n", "pm = generate_preset_pass_manager(target=target, optimization_level=3)\n", "\n", "qc_isa = pm.run(qc)" ] }, { "cell_type": "code", "execution_count": null, "id": "8fef6a65-227a-4f27-af3e-348513e1cd33", "metadata": {}, "outputs": [], "source": [ "# Step 3: Run the job on a real quantum computer\n", "\n", "job = sampler.run([qc_isa], shots=1)\n", "# job = sampler_sim.run([qc_isa],shots=1) # uncomment this line to run on simulator instead\n", "res = job.result()\n", "counts = res[0].data.c.get_counts()" ] }, { "cell_type": "code", "execution_count": 21, "id": "ec576787-d9ba-4406-b799-9c0de21a8088", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "{'0000': 1}\n" ] } ], "source": [ "# Step 4: Visualize and analyze results\n", "\n", "## Analysis\n", "print(counts)" ] }, { "cell_type": "markdown", "id": "46ff0418-570d-4e78-be36-f403aeccc392", "metadata": {}, "source": [ "Quindi, con una sola interrogazione, l'algoritmo Deutsch-Jozsa restituirà la stringa $s$ utilizzata nella funzione: $f(x)=x \\cdot s$ quando lo applicheremo al problema di Bernstein-Vazirani. Con un algoritmo classico, sarebbero necessarie $n$ query per risolvere lo stesso problema.\n", "\n", "\n", "\n", "## Conclusione\n", "\n", "Ci auguriamo che, esaminando questi semplici esempi, si sia potuto intuire meglio come i computer quantistici siano in grado di sfruttare la superposizione, l'entanglement e l'interferenza per ottenere la loro potenza rispetto ai computer classici.\n", "\n", "L'algoritmo di Deutsch-Jozsa ha un'enorme importanza storica perché è stato il primo a dimostrare un aumento di velocità rispetto a un algoritmo classico, ma solo polinomiale. L'algoritmo Deutsch-Jozsa è solo l'inizio della storia.\n", "\n", "Dopo aver utilizzato l'algoritmo per risolvere il loro problema, Bernstein e Vazirani lo usarono come base per un problema più complicato e ricorsivo, chiamato *problema ricorsivo del campionamento di Fourier*. La loro soluzione offre una velocità super-polinomiale rispetto agli algoritmi classici. E ancora prima di Bernstein e Vazirani, Peter Shor aveva già ideato il suo famoso algoritmo che consentiva ai computer quantistici di fattorizzare grandi numeri in modo esponenzialmente più veloce di qualsiasi algoritmo classico. Questi risultati hanno mostrato l'eccitante promessa di un futuro computer quantistico e hanno spronato fisici e ingegneri a trasformare questo futuro in realtà.\n", "\n" ] }, { "cell_type": "markdown", "id": "c76273ac-ad3c-4c82-94e8-213e887dc7b7", "metadata": {}, "source": [ "\n", "\n", "## Domande\n", "\n", "Gli insegnanti possono richiedere le versioni di questi quaderni con le chiavi di risposta e le indicazioni per l'inserimento nei curricula comuni compilando questo [rapido sondaggio](https://ibm.biz/classrooms_instructor_key_request) sull'utilizzo dei quaderni.\n", "\n", "\n", "\n", "### Concetti fondamentali\n", "\n", "* gli algoritmi Deutsch e Deutsch-Jozsa utilizzano il parallelismo quantistico combinato con l'interferenza per trovare una risposta a un problema più velocemente di quanto possa fare un computer classico.\n", "* il meccanismo del contraccolpo di fase è un fenomeno quantistico controintuitivo che trasferisce le operazioni su un qubit alla fase di un altro qubit. Gli algoritmi Deutsch e Deutsch-Jozsa utilizzano questo meccanismo.\n", "* L'algoritmo di Deutsch-Jozsa offre una velocità polinomiale rispetto a qualsiasi algoritmo deterministico classico.\n", "* L'algoritmo di Deutsch-Jozsa può essere applicato a un problema diverso, chiamato problema di Bernstein-Vazirani, per trovare una stringa nascosta codificata in una funzione.\n", "\n", "\n", "\n", "### vero/falso\n", "\n", "1. T/F L'algoritmo di Deutsch è un caso speciale dell'algoritmo di Deutsch-Jozsa in cui l'ingresso è un singolo qubit.\n", "2. T/F Gli algoritmi di Deutsch e Deutsch-Jozsa utilizzano la sovrapposizione quantistica e l'interferenza per raggiungere la loro efficienza.\n", "3. T/F L'algoritmo di Deutsch-Jozsa richiede valutazioni multiple di funzioni per determinare se una funzione è costante o bilanciata.\n", "4. T/F L'\"algoritmo di Bernstein-Vazirani\" è in realtà lo stesso algoritmo di Deutsch-Jozsa, applicato a un problema diverso.\n", "5. T/F L'algoritmo di Bernstein-Vazirani può trovare più stringhe segrete contemporaneamente.\n", "\n", "\n", "\n", "### Risposta breve\n", "\n", "1. Quanto tempo impiegherebbe un algoritmo classico per risolvere il problema di Deutsch-Jozsa nel caso peggiore?\n", "\n", "2. Quanto tempo impiegherebbe un algoritmo classico per risolvere il problema di Bernstein-Vazirani? Quale accelerazione offre l'algoritmo DJ in questo caso?\n", "\n", "3. Descrivete il meccanismo di phase-kickback e come funziona per risolvere i problemi di Deutsch-Jozsa e Bernstein-Vazirani.\n", "\n", "\n", "\n", "### Problema di sfida\n", "\n", "1. L'algoritmo di Deutsch-Jozsa: Ricordiamo che la domanda precedente chiedeva di calcolare gli stati intermedi dei qubit $\\pi_1$ e $\\pi_2$ dell'algoritmo di Deutsch. Fare lo stesso per gli stati intermedi $n+1$ -qubit $\\pi_1$, e $\\pi_2$ dell'algoritmo di Deutsch-Jozsa, per il caso specifico che $n=2$. Quindi, verificare che $\\pi_3 = |-\\rangle \\otimes \\sum\\limits_{x_0...x_n}(-1)^{f(x_0...x_n)}|x_0 ... x_n\\rangle$, sempre per il caso specifico che $n=2$.\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "id": "a1b8767d", "source": "© IBM Corp., 2017-2026" } ], "metadata": { "in_page_toc_max_heading_level": 2, "in_page_toc_min_heading_level": 2, "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" }, "widgets": { "application/vnd.jupyter.widget-state+json": { "state": {}, "version_major": 2, "version_minor": 0 } } }, "nbformat": 4, "nbformat_minor": 5 }