{ "cells": [ { "cell_type": "markdown", "id": "7e5d320e", "metadata": {}, "source": [ "---\n", "title: \"Algoritmo di Deutsch\"\n", "description: \"Corso gratuito \\\" IBM \\\" sull'informazione e il calcolo quantistico\"\n", "---\n", "\n", "\n", "\n", "# Algoritmo di Deutsch\n", "\n", "L'algoritmo di Deutsch risolve il problema della parità nel caso particolare in cui $n = 1$.\n", "Nel contesto dell'informatica quantistica, questo problema viene talvolta definito \" *problema di Deutsch* \" e in questa lezione seguiremo tale nomenclatura.\n", "\n", "Per essere precisi, l'ingresso è rappresentato da una funzione $f:\\Sigma \\rightarrow \\Sigma$ da un bit a un bit.\n", "Esistono quattro funzioni di questo tipo:\n", "\n", "$$\n", "\\rule[-10mm]{0mm}{10mm}\n", "\\begin{array}{c|c}\n", " a & f_1(a)\\\\\n", " \\hline\n", " 0 & 0\\\\\n", " 1 & 0\n", "\\end{array}\n", "\\qquad\n", "\\begin{array}{c|c}\n", " a & f_2(a)\\\\\n", " \\hline\n", " 0 & 0\\\\\n", " 1 & 1\n", "\\end{array}\n", "\\qquad\n", "\\begin{array}{c|c}\n", " a & f_3(a)\\\\\n", " \\hline\n", " 0 & 1\\\\\n", " 1 & 0\n", "\\end{array}\n", "\\qquad\n", "\\begin{array}{c|c}\n", " a & f_4(a)\\\\\n", " \\hline\n", " 0 & 1\\\\\n", " 1 & 1\n", "\\end{array}\n", "$$\n", "\n", "La prima e l'ultima di queste funzioni sono *costanti*, mentre le due centrali sono *bilanciate*, il che significa che i due possibili valori di uscita della funzione si verificano lo stesso numero di volte quando si passa da un ingresso all'altro.\n", "Il problema di Deutsch consiste nel determinare a quale delle due categorie appartiene la funzione di ingresso: costante o bilanciata.\n", "\n", "
\n", " Ingresso: una funzione $f:\\{0,1\\}\\rightarrow\\{0,1\\}$ \\ Output: $0$ se $f$ è costante, $1$ se $f$ è bilanciata\n", "
\n", "\n", "Se consideriamo la funzione di input $f$ nel problema di Deutsch come rappresentazione di un accesso casuale a una stringa, stiamo considerando una stringa di due bit: $f(0)f(1)$.\n", "\n", "$$\n", "\\begin{array}{cc}\n", "\\mathsf{function} & \\mathsf{string}\\\\\n", "\\hline\n", "f_1 & 00 \\\\\n", "f_2 & 01 \\\\\n", "f_3 & 10 \\\\\n", "f_4 & 11\n", "\\end{array}\n", "$$\n", "\n", "Visto in questo modo, il problema di Deutsch consiste nel calcolare la parità (o, equivalentemente, l'OR esclusivo) dei due bit.\n", "\n", "Ogni algoritmo di interrogazione classico che risolva correttamente questo problema deve interrogare entrambi i bit: $f(0)$ e $f(1)$.\n", "Se venissimo a sapere che $f(1) = 1$, ad esempio, la risposta potrebbe comunque essere $0$ o $1$, a seconda che $f(0) = 1$ o $f(0) = 0$, rispettivamente.\n", "In tutti gli altri casi la situazione è simile: conoscere solo uno dei due bit non fornisce alcuna informazione sulla loro parità.\n", "Pertanto, il circuito booleano descritto nella sezione precedente rappresenta la soluzione ottimale in termini di numero di query necessarie per risolvere questo problema.\n", "\n", "\n", "\n", "## Descrizione del circuito quantistico\n", "\n", "L'algoritmo di Deutsch risolve il problema di Deutsch utilizzando una singola interrogazione, fornendo quindi un vantaggio quantificabile della computazione quantistica rispetto a quella classica.\n", "Si tratta forse di un vantaggio modesto - una sola interrogazione invece di due - ma da qualche parte bisogna pur cominciare.\n", "I progressi scientifici hanno talvolta origini apparentemente umili.\n", "\n", "Ecco un circuito quantistico che descrive l'algoritmo di Deutsch:\n", "\n", "![Algoritmo di Deutsch](https://quantum.cloud.ibm.com/learning/images/courses/fundamentals-of-quantum-algorithms/quantum-query-algorithms/Deutsch-circuit.svg)\n", "\n", "\n", "\n", "## Analisi\n", "\n", "Per analizzare l'algoritmo di Deutsch, ripercorriamo l'azione del circuito di cui sopra e identifichiamo gli stati dei qubit nei momenti suggeriti dalla figura:\n", "\n", "![Stati durante l'algoritmo di Deutsch](https://quantum.cloud.ibm.com/learning/images/courses/fundamentals-of-quantum-algorithms/quantum-query-algorithms/Deutsch-circuit-states.svg)\n", "\n", "Lo stato iniziale è $\\vert 1\\rangle \\vert 0 \\rangle$, e le due operazioni di Hadamard sul lato sinistro del circuito trasformano questo stato in\n", "\n", "$$\n", "\\vert \\pi_1 \\rangle = \\vert - \\rangle \\vert + \\rangle\n", "= \\frac{1}{2} \\bigl( \\vert 0\\rangle - \\vert 1\\rangle \\bigr) \\vert 0\\rangle\n", "+ \\frac{1}{2} \\bigl( \\vert 0\\rangle - \\vert 1\\rangle \\bigr) \\vert 1\\rangle.\n", "$$\n", "\n", "(Come sempre, seguiamo la convenzione di ordinamento dei qubit di Qiskit, che pone il qubit superiore a destra e quello inferiore a sinistra) Può sembrare poco intuitivo scrivere questo prodotto di stato parzialmente distribuito (lasciando gli stati del qubit 1 sfalsati), ma questo renderà le nostre espressioni successive più compatte.\n", "\n", "Successivamente, viene eseguito il gate $U_f$.\n", "Secondo la definizione del gate $U_f$, il valore della funzione $f$ per lo stato classico del qubit in alto/più a destra è sottoposto a XOR sul qubit in basso/più a sinistra, che trasforma $\\vert \\pi_1\\rangle$ nello stato\n", "\n", "$$\n", "\\vert \\pi_2 \\rangle\n", "= \\frac{1}{2} \\bigl( \\vert 0 \\oplus f(0) \\rangle - \\vert 1 \\oplus f(0) \\rangle \\bigr) \\vert 0 \\rangle\n", "+ \\frac{1}{2} \\bigl( \\vert 0 \\oplus f(1) \\rangle - \\vert 1 \\oplus f(1) \\rangle \\bigr) \\vert 1 \\rangle.\n", "$$\n", "\n", "Possiamo semplificare questa espressione osservando che la formula\n", "\n", "$$\n", "\\vert 0 \\oplus a\\rangle - \\vert 1 \\oplus a\\rangle = (-1)^a \\bigl( \\vert 0\\rangle - \\vert 1\\rangle \\bigr)\n", "$$\n", "\n", "funziona per entrambi i valori possibili $a\\in\\Sigma$\n", "Più precisamente, i due casi sono i seguenti.\n", "\n", "$$\n", "\\begin{aligned}\n", "\\vert 0 \\oplus 0\\rangle - \\vert 1 \\oplus 0\\rangle\n", "& = \\vert 0 \\rangle - \\vert 1 \\rangle\n", "= (-1)^0 \\bigl( \\vert 0\\rangle - \\vert 1\\rangle \\bigr)\\\\\n", "\\vert 0 \\oplus 1\\rangle - \\vert 1 \\oplus 1\\rangle & = \\vert 1 \\rangle - \\vert 0\\rangle\n", "= (-1)^1 \\bigl( \\vert 0\\rangle - \\vert 1\\rangle \\bigr)\n", "\\end{aligned}\n", "$$\n", "\n", "In alternativa, possiamo esprimere $\\vert\\pi_2\\rangle$ in questo modo:\n", "\n", "$$\n", "\\begin{aligned}\n", " \\vert\\pi_2\\rangle\n", " & = \\frac{1}{2} (-1)^{f(0)} \\bigl( \\vert 0 \\rangle - \\vert 1 \\rangle \\bigr) \\vert 0 \\rangle\n", " + \\frac{1}{2} (-1)^{f(1)} \\bigl( \\vert 0 \\rangle - \\vert 1 \\rangle \\bigr) \\vert 1 \\rangle \\\\\n", " & = \\vert - \\rangle \\biggl( \\frac{(-1)^{f(0)} \\vert 0\\rangle + (-1)^{f(1)} \\vert 1\\rangle}{\\sqrt{2}}\\biggr).\n", "\\end{aligned}\n", "$$\n", "\n", "È appena successo qualcosa di interessante!\n", "Sebbene l'azione del gate $U_f$ sugli stati base standard lasci il qubit in alto a destra da solo e faccia lo XOR del valore della funzione sul qubit in basso a sinistra, in questo caso vediamo che lo stato del qubit in alto a destra è cambiato (in generale), mentre lo stato del qubit in basso a sinistra rimane lo stesso - in particolare si trova nello stato $\\vert - \\rangle$ prima e dopo l'esecuzione del gate $U_f$.\n", "Questo fenomeno è noto come *contraccolpo di fase* e ne parleremo più avanti.\n", "\n", "Con un'ultima semplificazione, che consiste nell'estrarre il fattore di $(-1)^{f(0)}$ al di fuori della somma, otteniamo questa espressione dello stato $\\vert\\pi_2\\rangle$ :\n", "\n", "$$\n", "\\begin{aligned}\n", " \\vert\\pi_2\\rangle\n", " & = (-1)^{f(0)} \\vert - \\rangle\n", " \\biggl( \\frac{\\vert 0\\rangle + (-1)^{f(0) \\oplus f(1)} \\vert 1\\rangle}{\\sqrt{2}}\\biggr) \\\\\n", " & = \\begin{cases}\n", " (-1)^{f(0)} \\vert - \\rangle \\vert + \\rangle & \\text{if $f(0) \\oplus f(1) = 0$}\\\\[1mm]\n", " (-1)^{f(0)} \\vert - \\rangle \\vert - \\rangle & \\text{if $f(0) \\oplus f(1) = 1$}.\n", " \\end{cases}\n", "\\end{aligned}\n", "$$\n", "\n", "Si noti che in questa espressione, nell’esponente di $-1$ abbiamo $f(0) \\oplus f(1)$, anziché $f(1) - f(0)$, che è ciò che ci si potrebbe aspettare da un punto di vista puramente algebrico; tuttavia, in entrambi i casi si ottiene lo stesso risultato.\n", "Questo perché il valore $(-1)^k$ per qualsiasi numero intero $k$ dipende solo dal fatto che $k$ sia pari o dispari.\n", "\n", "Applicando il gate di Hadamard finale al qubit superiore si ottiene lo stato\n", "\n", "$$\n", "\\vert \\pi_3 \\rangle =\n", "\\begin{cases}\n", " (-1)^{f(0)} \\vert - \\rangle \\vert 0 \\rangle & \\text{if $f(0) \\oplus f(1) = 0$}\\\\[1mm]\n", " (-1)^{f(0)} \\vert - \\rangle \\vert 1 \\rangle & \\text{if $f(0) \\oplus f(1) = 1$},\n", "\\end{cases}\n", "$$\n", "\n", "che porta al risultato corretto con probabilità $1$ quando viene misurato il qubit destro/superiore.\n", "\n", "\n", "\n", "## Ulteriori osservazioni sul contraccolpo di fase\n", "\n", "Prima di proseguire, analizziamo l'analisi di cui sopra da un'angolazione leggermente diversa che può far luce sul fenomeno del contraccolpo di fase.\n", "\n", "Innanzitutto, si noti che la seguente formula vale per tutte le combinazioni di bit $b,c\\in\\Sigma$.\n", "\n", "$$\n", "\\vert b \\oplus c\\rangle = X^c \\vert b \\rangle\n", "$$\n", "\n", "Questo può essere verificato controllando i due possibili valori $c = 0$ e $c = 1$ :\n", "\n", "$$\n", "\\begin{aligned}\n", "\\vert b \\oplus 0 \\rangle & = \\vert b\\rangle = \\mathbb{I} \\vert b \\rangle = X^0 \\vert b \\rangle\\\\\n", "\\vert b \\oplus 1 \\rangle & = \\vert \\neg b\\rangle = X \\vert b \\rangle = X^1 \\vert b \\rangle.\n", "\\end{aligned}\n", "$$\n", "\n", "Utilizzando questa formula, vediamo che\n", "\n", "$$\n", "U_f \\bigl(\\vert b\\rangle \\vert a \\rangle\\bigr)\n", "= \\vert b \\oplus f(a) \\rangle \\vert a \\rangle\n", "= \\bigl(X^{f(a)}\\vert b \\rangle\\bigr) \\vert a \\rangle\n", "$$\n", "\n", "per ogni scelta di bit $a,b\\in\\Sigma$.\n", "Poiché questa formula è vera per $b=0$ e $b=1$, dalla linearità si deduce che\n", "\n", "$$\n", "U_f \\bigl( \\vert \\psi \\rangle \\vert a \\rangle \\bigr) = \\bigl(X^{f(a)}\\vert \\psi \\rangle\\bigr) \\vert a \\rangle\n", "$$\n", "\n", "per tutti i vettori di stato dei qubit $\\vert \\psi\\rangle$, e quindi\n", "\n", "$$\n", "U_f \\bigl( \\vert - \\rangle \\vert a \\rangle \\bigr) = \\bigl(X^{f(a)} \\vert - \\rangle \\bigr) \\vert a \\rangle\n", "= (-1)^{f(a)} \\vert - \\rangle \\vert a \\rangle.\n", "$$\n", "\n", "La chiave che rende possibile tutto ciò è che $X\\vert - \\rangle = - \\vert - \\rangle$.\n", "In termini matematici, il vettore $\\vert - \\rangle$ è un *vettore* proprio della matrice $X$ avente *autovalore* $-1$.\n", "\n", "Parleremo di autovettori e autovalori in modo più dettagliato nella prossima lezione sulla *stima di fase e sulla fattorizzazione,* dove il fenomeno del contraccolpo di fase viene generalizzato ad altre operazioni unitarie.\n", "\n", "Tenendo presente che gli scalari fluttuano liberamente attraverso i prodotti tensoriali, troviamo un modo alternativo di ragionare su come l'operazione $U_f$ trasforma $\\vert \\pi_1\\rangle$ in $\\vert \\pi_2\\rangle$ nell'analisi precedente:\n", "\n", "$$\n", "\\begin{aligned}\n", " \\vert \\pi_2 \\rangle\n", " & = U_f \\bigl( \\vert - \\rangle \\vert + \\rangle \\bigr)\\\\\n", " & = \\frac{1}{\\sqrt{2}} U_f \\bigl(\\vert - \\rangle \\vert 0\\rangle \\bigr)\n", " + \\frac{1}{\\sqrt{2}} U_f \\bigl(\\vert - \\rangle \\vert 1\\rangle \\bigr)\\\\\n", " & = \\vert - \\rangle \\biggl( \\frac{(-1)^{f(0)} \\vert 0\\rangle + (-1)^{f(1)} \\vert 1\\rangle}{\\sqrt{2}}\\biggr).\n", "\\end{aligned}\n", "$$\n", "\n" ] }, { "cell_type": "markdown", "id": "d0cff57e", "metadata": {}, "source": [ "\n", "\n", "## Implementazione in Qiskit\n", "\n", "Vediamo ora come implementare l'algoritmo di Deutsch in Qiskit. Inizieremo con un controllo della versione e poi eseguiremo le importazioni necessarie solo per questa implementazione.\n", "Per le implementazioni di altri algoritmi che seguiranno, eseguiremo le importazioni necessarie separatamente, per una maggiore modularità.\n", "\n" ] }, { "cell_type": "code", "execution_count": 1, "id": "baa9bc2c", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "2.1.1\n" ] } ], "source": [ "from qiskit import __version__\n", "\n", "print(__version__)" ] }, { "cell_type": "code", "execution_count": 2, "id": "0a706449", "metadata": {}, "outputs": [], "source": [ "from qiskit import QuantumCircuit\n", "from qiskit_aer import AerSimulator" ] }, { "cell_type": "markdown", "id": "0af39df9", "metadata": {}, "source": [ "Per prima cosa definiremo un circuito quantistico che implementi un gate di query per una delle quattro funzioni $f_1$, $f_2$, $f_3$ o $f_4$ da un bit a un bit, descritte in precedenza. Come abbiamo già accennato, l’implementazione dei “query gate” non fa propriamente parte dell’algoritmo di Deutsch in sé;\n", "qui ci limitiamo essenzialmente a mostrare un modo per preparare l’input, sotto forma di implementazione circuitale di un “query gate”.\n", "\n" ] }, { "cell_type": "code", "execution_count": 3, "id": "ba5a708f", "metadata": {}, "outputs": [], "source": [ "def deutsch_function(case: int):\n", " # This function generates a quantum circuit for one of the 4 functions\n", " # from one bit to one bit\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" ] }, { "cell_type": "markdown", "id": "46eccf09", "metadata": {}, "source": [ "Possiamo vedere come è fatto ogni circuito utilizzando il metodo `draw` . Ecco lo schema del circuito per la funzione “ $f_3$ ”.\n", "\n" ] }, { "cell_type": "code", "execution_count": 4, "id": "787e3c81", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\"Output" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "display(deutsch_function(3).draw(output=\"mpl\"))" ] }, { "cell_type": "markdown", "id": "b6fa5b7b", "metadata": {}, "source": [ "Successivamente creeremo il circuito quantistico vero e proprio per l'algoritmo di Deutsch, sostituendo la porta di interrogazione con un'implementazione del circuito quantistico fornita come argomento. A breve inseriremo uno dei quattro circuiti definiti dalla funzione `deutsch_function` che abbiamo definito in precedenza.\n", "Le barriere sono incluse per mostrare la separazione visiva tra l'implementazione della porta di interrogazione e il resto del circuito.\n", "\n" ] }, { "cell_type": "code", "execution_count": 5, "id": "379aac92", "metadata": {}, "outputs": [], "source": [ "def compile_circuit(function: QuantumCircuit):\n", " # Compiles a circuit for use in Deutsch's algorithm.\n", "\n", " n = function.num_qubits - 1\n", " qc = QuantumCircuit(n + 1, n)\n", "\n", " qc.x(n)\n", " qc.h(range(n + 1))\n", "\n", " qc.barrier()\n", " qc.compose(function, inplace=True)\n", " qc.barrier()\n", "\n", " qc.h(range(n))\n", " qc.measure(range(n), range(n))\n", "\n", " return qc" ] }, { "cell_type": "markdown", "id": "e5112614", "metadata": {}, "source": [ "Anche in questo caso possiamo vedere come si presenta il circuito utilizzando il metodo `draw` .\n", "\n" ] }, { "cell_type": "code", "execution_count": 6, "id": "27b41067", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\"Output" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "display(compile_circuit(deutsch_function(3)).draw(output=\"mpl\"))" ] }, { "cell_type": "markdown", "id": "d24d14eb", "metadata": {}, "source": [ "Infine, creeremo una funzione che esegua una volta il circuito precedentemente definito e fornisca il risultato appropriato: \"costante\" o \"bilanciato\"\n", "\n" ] }, { "cell_type": "code", "execution_count": 7, "id": "5b31e311", "metadata": {}, "outputs": [], "source": [ "def deutsch_algorithm(function: QuantumCircuit):\n", " # Determine if a one-bit function is constant or balanced.\n", "\n", " qc = compile_circuit(function)\n", "\n", " result = AerSimulator().run(qc, shots=1, memory=True).result()\n", " measurements = result.get_memory()\n", " if measurements[0] == \"0\":\n", " return \"constant\"\n", " return \"balanced\"" ] }, { "cell_type": "markdown", "id": "3d0868ed", "metadata": {}, "source": [ "Ora possiamo eseguire l'algoritmo di Deutsch su una qualsiasi delle quattro funzioni definite sopra.\n", "\n" ] }, { "cell_type": "code", "execution_count": 8, "id": "33b8355d", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "'balanced'" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "f = deutsch_function(3)\n", "display(deutsch_algorithm(f))" ] }, { "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" } }, "nbformat": 4, "nbformat_minor": 5 }