{ "cells": [ { "cell_type": "markdown", "id": "17463a96", "metadata": {}, "source": [ "---\n", "title: \"L'algoritmo Deutsch-Jozsa\"\n", "description: \"Corso gratuito \\\" IBM \\\" sull'informazione e il calcolo quantistico\"\n", "---\n", "\n", "\n", "\n", "# L'algoritmo Deutsch-Jozsa\n", "\n", "L'algoritmo di Deutsch supera tutti gli algoritmi classici per un problema di interrogazione, ma il vantaggio è piuttosto modesto: un'interrogazione contro due.\n", "L'algoritmo di Deutsch-Jozsa estende questo vantaggio e, di fatto, può essere utilizzato per risolvere un paio di problemi di interrogazione diversi.\n", "\n", "Ecco una descrizione del circuito quantistico dell'algoritmo di Deutsch-Jozsa.\n", "A seconda del problema specifico da risolvere, può essere necessaria un'ulteriore fase di post-elaborazione classica, non mostrata nella figura.\n", "\n", "![Algoritmo Deutsch-Jozsa](https://quantum.cloud.ibm.com/learning/images/courses/fundamentals-of-quantum-algorithms/quantum-query-algorithms/Deutsch-Jozsa.svg)\n", "\n", "Naturalmente, non abbiamo ancora discusso quali problemi risolve questo algoritmo; lo faremo nelle due sezioni successive.\n", "\n", "\n", "\n", "## Il problema Deutsch-Jozsa\n", "\n", "Inizieremo con il problema di interrogazione che l'algoritmo Deutsch-Jozsa era originariamente destinato a risolvere, noto come *problema Deutsch-Jozsa*.\n", "\n", "La funzione di input per questo problema ha la forma $f:\\Sigma^n \\rightarrow \\Sigma$ per un numero intero positivo arbitrario $n.$ Come nel problema di Deutsch, il compito consiste nell'emettere $0$ se $f$ è costante e $1$ se $f$ è bilanciato, il che significa ancora una volta che il numero di stringhe di input su cui la funzione assume il valore $0$ è uguale al numero di stringhe di input su cui la funzione assume il valore $1$.\n", "\n", "Si noti che, quando $n$ è più grande di $1,$, esistono funzioni della forma $f:\\Sigma^n \\rightarrow \\Sigma$ che non sono né costanti né bilanciate.\n", "Ad esempio, la funzione $f:\\Sigma^2\\rightarrow\\Sigma$ definita come\n", "\n", "$$\n", "\\begin{aligned}\n", "f(00) & = 0 \\\\\n", "f(01) & = 0 \\\\\n", "f(10) & = 0 \\\\\n", "f(11) & = 1\n", "\\end{aligned}\n", "$$\n", "\n", "non rientra in nessuna delle due categorie.\n", "Per il problema di Deutsch-Jozsa, semplicemente non ci preoccupiamo di funzioni come questa: sono considerate ingressi \"non importanti\".\n", "Cioè, per questo problema abbiamo la *promessa* che $f$ sia costante o equilibrato.\n", "\n", "
\n", " Ingresso: una funzione $f:\\{0,1\\}^n\\rightarrow\\{0,1\\}$ \\ Promessa: $f$ è costante o bilanciato \\ Output: $0$ se $f$ è costante, $1$ se $f$ è bilanciata\n", "
\n", "\n", "L'algoritmo di Deutsch-Jozsa, con la sua singola query, risolve questo problema nel senso seguente:\n", "se tutti i risultati delle misurazioni $n$ sono $0,$, allora la funzione $f$ è costante;\n", "altrimenti, se almeno uno dei risultati delle misurazioni è $1,$, allora la funzione $f$ è bilanciata.\n", "In altre parole, il circuito sopra descritto è seguito da una fase di post-elaborazione classica in cui viene calcolata la somma logica (OR) dei risultati delle misurazioni per ottenere il bit di uscita del problema di Deutsch-Jozsa.\n", "\n", "\n", "\n", "### Analisi dell'algoritmo\n", "\n", "Per analizzare le prestazioni dell'algoritmo di Deutsch-Jozsa per il problema di Deutsch-Jozsa, è utile iniziare pensando all'azione di un singolo strato di porte di Hadamard.\n", "Un'operazione di Hadamard può essere espressa come una matrice nel modo consueto,\n", "\n", "$$\n", "H = \\begin{pmatrix}\n", "\\frac{1}{\\sqrt{2}} & \\frac{1}{\\sqrt{2}} \\\\[2mm]\n", "\\frac{1}{\\sqrt{2}} & -\\frac{1}{\\sqrt{2}}\n", "\\end{pmatrix},\n", "$$\n", "\n", "ma possiamo anche esprimere questa operazione in termini di azione sugli stati base standard:\n", "\n", "$$\n", "\\begin{aligned}\n", "H \\vert 0\\rangle & = \\frac{1}{\\sqrt{2}} \\vert 0 \\rangle + \\frac{1}{\\sqrt{2}} \\vert 1 \\rangle\\\\[3mm]\n", "H \\vert 1\\rangle & = \\frac{1}{\\sqrt{2}} \\vert 0 \\rangle - \\frac{1}{\\sqrt{2}} \\vert 1 \\rangle.\n", "\\end{aligned}\n", "$$\n", "\n", "Queste due equazioni possono essere combinate in un'unica formula,\n", "\n", "$$\n", "H \\vert a \\rangle = \\frac{1}{\\sqrt{2}} \\vert 0 \\rangle + \\frac{1}{\\sqrt{2}} (-1)^a \\vert 1 \\rangle\n", "= \\frac{1}{\\sqrt{2}} \\sum_{b\\in\\{0,1\\}} (-1)^{ab} \\vert b\\rangle,\n", "$$\n", "\n", "che è vero per entrambe le scelte di $a\\in\\Sigma.$\n", "\n", "Supponiamo ora che invece di un solo qubit abbiamo $n$ qubit e che su ognuno di essi venga eseguita un'operazione di Hadamard.\n", "L'operazione combinata sui qubit $n$ è descritta dal prodotto tensoriale $H\\otimes \\cdots \\otimes H$ ( $n$ volte), che per concisione e chiarezza scriviamo come $H^{\\otimes n}$.\n", "Utilizzando la formula precedente, seguita da un'espansione e da una semplificazione, possiamo esprimere l'azione di questa operazione combinata sugli stati base standard dei qubit di $n$ in questo modo:\n", "\n", "$$\n", "\\begin{aligned}\n", " & H^{\\otimes n} \\vert x_{n-1} \\cdots x_1 x_0 \\rangle \\\\\n", " & \\qquad = \\bigl(H \\vert x_{n-1} \\rangle \\bigr) \\otimes \\cdots \\otimes \\bigl(H \\vert x_{0} \\rangle \\bigr) \\\\\n", " & \\qquad = \\Biggl( \\frac{1}{\\sqrt{2}} \\sum_{y_{n-1}\\in\\Sigma} (-1)^{x_{n-1} y_{n-1}} \\vert y_{n-1} \\rangle \\Biggr)\n", " \\otimes \\cdots \\otimes\n", " \\Biggl( \\frac{1}{\\sqrt{2}} \\sum_{y_{0}\\in\\Sigma} (-1)^{x_{0} y_{0}} \\vert y_{0} \\rangle \\Biggr) \\\\\n", " & \\qquad = \\frac{1}{\\sqrt{2^n}} \\sum_{y_{n-1}\\cdots y_0 \\in \\Sigma^n}\n", " (-1)^{x_{n-1}y_{n-1} + \\cdots + x_0 y_0} \\vert y_{n-1} \\cdots y_0 \\rangle.\n", "\\end{aligned}\n", "$$\n", "\n", "Qui, tra l'altro, stiamo scrivendo stringhe binarie di lunghezza $n$ come $x_{n-1}\\cdots x_0$ e $y_{n-1}\\cdots y_0,$ seguendo la convenzione di indicizzazione di Qiskit.\n", "\n", "Questa formula ci fornisce un utile strumento per analizzare il circuito quantistico di cui sopra.\n", "Dopo l'esecuzione del primo strato di porte di Hadamard, lo stato dei qubit di $n+1$ (compreso il qubit più a sinistra/inferiore, che viene trattato separatamente dal resto) è\n", "\n", "$$\n", "\\bigl( H \\vert 1 \\rangle \\bigr) \\bigl( H^{\\otimes n} \\vert 0 \\cdots 0 \\rangle \\bigr)\n", "= \\vert - \\rangle \\otimes \\frac{1}{\\sqrt{2^n}} \\sum_{x_{n-1}\\cdots x_0 \\in \\Sigma^n} \\vert x_{n-1} \\cdots x_0 \\rangle.\n", "$$\n", "\n", "Quando viene eseguita l'operazione $U_f$, questo stato viene trasformato in\n", "\n", "$$\n", "\\vert - \\rangle \\otimes \\frac{1}{\\sqrt{2^n}}\n", "\\sum_{x_{n-1}\\cdots x_0 \\in \\Sigma^n} (-1)^{f(x_{n-1}\\cdots x_0)} \\vert x_{n-1} \\cdots x_0 \\rangle\n", "$$\n", "\n", "attraverso lo stesso fenomeno di contraccolpo di fase che abbiamo visto nell'analisi dell'algoritmo di Deutsch.\n", "\n", "Quindi viene eseguito il secondo strato di porte di Hadamard, che (in base alla formula precedente) trasforma questo stato in\n", "\n", "$$\n", "\\vert - \\rangle \\otimes \\frac{1}{2^n}\n", "\\sum_{x_{n-1}\\cdots x_0 \\in \\Sigma^n}\n", "\\sum_{y_{n-1}\\cdots y_0 \\in \\Sigma^n}\n", "(-1)^{f(x_{n-1}\\cdots x_0) + x_{n-1}y_{n-1} + \\cdots + x_0 y_0}\n", "\\vert y_{n-1} \\cdots y_0 \\rangle.\n", "$$\n", "\n", "Questa espressione sembra un po' complicata e non si può concludere molto sulle probabilità di ottenere risultati di misura diversi senza conoscere meglio la funzione $f.$\n", "\n", "Fortunatamente, tutto ciò che dobbiamo sapere è la probabilità che ognuno dei risultati della misurazione sia $0$ - perché questa è la probabilità che l'algoritmo determini che $f$ è costante.\n", "Questa probabilità ha una formula semplice.\n", "\n", "$$\n", "\\Biggl\\vert\n", "\\frac{1}{2^n}\n", "\\sum_{x_{n-1}\\cdots x_0 \\in \\Sigma^n}\n", "(-1)^{f(x_{n-1}\\cdots x_0)}\n", "\\Biggr\\vert^2\n", "= \\begin{cases}\n", "1 & \\text{if $f$ is constant}\\\\[1mm]\n", "0 & \\text{if $f$ is balanced}\n", "\\end{cases}\n", "$$\n", "\n", "Si noti che questi valori corrispondono alla probabilità di misurare lo stato\n", "$\\vert 0^{\\otimes n} \\rangle$, piuttosto che direttamente al bit di output classico finale del\n", "problema di Deutsch-Jozsa. L'algoritmo restituisce \" $0$ \" quando tutti i risultati delle misurazioni\n", "sono \" $0$ \" (a indicare che \" $f$ \" è costante) e restituisce \" $1$ \" in caso contrario\n", "(a indicare che \" $f$ \" è bilanciato).\n", "\n", "Più in dettaglio, se $f$ è costante, allora o $f(x_{n-1}\\cdots x_0) = 0$ per ogni stringa $x_{n-1}\\cdots x_0,$ nel qual caso il valore della somma è $2^n,$ oppure $f(x_{n-1}\\cdots x_0) = 1$ per ogni stringa $x_{n-1}\\cdots x_0,$ nel qual caso il valore della somma è $-2^n.$ Dividendo per $2^n$ e prendendo il quadrato del valore assoluto si ottiene $1.$\n", "\n", "Se invece $f$ è bilanciato, allora $f$ assume il valore $0$ su metà delle stringhe $x_{n-1}\\cdots x_0$ e il valore $1$ sull'altra metà, quindi i termini $+1$ e $-1$ della somma si annullano e rimane il valore $0.$\n", "\n", "Concludiamo che l'algoritmo funziona correttamente a condizione che la promessa sia mantenuta.\n", "\n", "\n", "\n", "### Difficoltà classica\n", "\n", "L'algoritmo di Deutsch-Jozsa funziona sempre, ci dà sempre la risposta corretta quando la promessa è soddisfatta e richiede una sola interrogazione.\n", "Come si confronta con gli algoritmi di interrogazione classici per il problema di Deutsch-Jozsa?\n", "\n", "In primo luogo, qualsiasi algoritmo *deterministico* classico che risolva correttamente il problema di Deutsch-Jozsa deve effettuare un numero esponenziale di interrogazioni: $2^{n-1} + 1$ nel caso peggiore, sono necessarie molte interrogazioni.\n", "Il ragionamento è che, se un algoritmo deterministico interroga $f$ su $2^{n-1}$ o meno stringhe diverse, e ottiene ogni volta lo stesso valore di funzione, allora entrambe le risposte sono ancora possibili.\n", "La funzione potrebbe essere costante o bilanciata, ma per sfortuna le query restituiscono tutte lo stesso valore della funzione.\n", "\n", "La seconda possibilità potrebbe sembrare improbabile, ma per gli algoritmi deterministici non c'è casualità o incertezza, quindi falliranno sistematicamente su alcune funzioni.\n", "A questo proposito, abbiamo quindi un vantaggio significativo degli algoritmi quantistici rispetto a quelli classici.\n", "\n", "C'è però una fregatura: gli algoritmi classici *probabilistici* possono risolvere il problema di Deutsch-Jozsa con una probabilità molto alta, utilizzando solo poche query.\n", "In particolare, se scegliamo a caso alcune stringhe diverse di lunghezza $n$ e interroghiamo $f$ su queste stringhe, è improbabile che otterremo lo stesso valore di funzione per tutte quando $f$ è bilanciato.\n", "\n", "Per essere precisi, se scegliamo $k$ stringhe di input $x^1,\\ldots,x^k \\in \\Sigma^n$ in modo uniformemente casuale, valutiamo $f(x^1),\\ldots,f(x^k),$ e rispondiamo $0$ se i valori della funzione sono tutti uguali, e $1$ in caso contrario, allora saremo sempre corretti quando $f$ è costante, e sbagliati nel caso in cui $f$ sia bilanciato con probabilità appena superiore a % $2^{-k + 1}.$ Se prendiamo ad esempio $k = 11,$, questo algoritmo risponderà correttamente con una probabilità maggiore di $99.9$ %.\n", "\n", "Per questo motivo, abbiamo ancora un vantaggio piuttosto modesto degli algoritmi quantistici rispetto a quelli classici, ma si tratta comunque di un vantaggio quantificabile che rappresenta un miglioramento rispetto all'algoritmo di Deutsch.\n", "\n" ] }, { "cell_type": "markdown", "id": "83b0e8b5", "metadata": {}, "source": [ "\n", "\n", "## Deutsch-Jozsa con Qiskit\n", "\n" ] }, { "cell_type": "code", "execution_count": 12, "id": "c7839d8f", "metadata": {}, "outputs": [], "source": [ "from qiskit import QuantumCircuit\n", "from qiskit_aer import AerSimulator\n", "import numpy as np" ] }, { "cell_type": "markdown", "id": "59738a5c", "metadata": {}, "source": [ "Per implementare l'algoritmo di Deutsch-Jozsa in Qiskit, inizieremo definendo una funzione `dj_query` che genera un circuito quantistico che implementa un query gate, per una funzione scelta a caso che soddisfa la promessa per il problema di Deutsch-Jozsa.\n", "Con una probabilità del 50%, la funzione è costante, mentre con una variazione del 50% la funzione è bilanciata.\n", "Per ognuna di queste due possibilità, la funzione viene selezionata in modo uniforme tra le funzioni di quel tipo.\n", "L'argomento è il numero di bit di ingresso della funzione.\n", "\n" ] }, { "cell_type": "code", "execution_count": 13, "id": "b39e7af8", "metadata": {}, "outputs": [], "source": [ "def dj_query(num_qubits):\n", " # Create a circuit implementing for a query gate for a random function\n", " # satisfying the promise for the Deutsch-Jozsa problem.\n", "\n", " qc = QuantumCircuit(num_qubits + 1)\n", "\n", " if np.random.randint(0, 2):\n", " # Flip output qubit with 50% chance\n", " qc.x(num_qubits)\n", " if np.random.randint(0, 2):\n", " # return constant circuit with 50% chance\n", " return qc\n", "\n", " # Choose half the possible input strings\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, bit_string):\n", " for qubit, bit in enumerate(reversed(bit_string)):\n", " if bit == \"1\":\n", " qc.x(qubit)\n", " return qc\n", "\n", " for state in on_states:\n", " qc.barrier() # Barriers are added to help visualize how the functions are created.\n", " qc = add_cx(qc, f\"{state:0b}\")\n", " qc.mcx(list(range(num_qubits)), num_qubits)\n", " qc = add_cx(qc, f\"{state:0b}\")\n", "\n", " qc.barrier()\n", "\n", " return qc" ] }, { "cell_type": "markdown", "id": "60b36f11", "metadata": {}, "source": [ "Possiamo mostrare l'implementazione del circuito quantistico della porta di interrogazione utilizzando il metodo `draw` come di consueto.\n", "\n" ] }, { "cell_type": "code", "execution_count": 14, "id": "b4a6df3d", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\"Output" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "display(dj_query(3).draw(output=\"mpl\"))" ] }, { "cell_type": "markdown", "id": "6ed6dd43", "metadata": {}, "source": [ "Definiamo poi una funzione che crea il circuito di Deutsch-Jozsa, prendendo come argomento un'implementazione del circuito quantistico di un query gate.\n", "\n" ] }, { "cell_type": "code", "execution_count": 15, "id": "79ab8817", "metadata": {}, "outputs": [], "source": [ "def compile_circuit(function: QuantumCircuit):\n", " # Compiles a circuit for use in the Deutsch-Jozsa algorithm.\n", "\n", " n = function.num_qubits - 1\n", " qc = QuantumCircuit(n + 1, n)\n", " qc.x(n)\n", " qc.h(range(n + 1))\n", " qc.compose(function, inplace=True)\n", " qc.h(range(n))\n", " qc.measure(range(n), range(n))\n", " return qc" ] }, { "cell_type": "markdown", "id": "71c07df9", "metadata": {}, "source": [ "Infine, viene definita una funzione che esegue una volta il circuito Deutsch-Jozsa.\n", "\n" ] }, { "cell_type": "code", "execution_count": 16, "id": "8a6cf538", "metadata": {}, "outputs": [], "source": [ "def dj_algorithm(function: QuantumCircuit):\n", " # Determine if a 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 \"1\" in measurements[0]:\n", " return \"balanced\"\n", " return \"constant\"" ] }, { "cell_type": "markdown", "id": "49113ebf", "metadata": {}, "source": [ "Possiamo testare la nostra implementazione scegliendo una funzione a caso, visualizzando l'implementazione del circuito quantistico di una porta di interrogazione per questa funzione e poi eseguendo l'algoritmo di Deutsch-Jozsa su quella funzione.\n", "\n" ] }, { "cell_type": "code", "execution_count": 17, "id": "aca4745e", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\"Output" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": [ "'balanced'" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "f = dj_query(3)\n", "display(f.draw(\"mpl\"))\n", "display(dj_algorithm(f))" ] }, { "cell_type": "markdown", "id": "89e58116", "metadata": {}, "source": [ "\n", "\n", "## Il problema di Bernstein-Vazirani\n", "\n", "Successivamente, discuteremo un problema noto come *problema di Bernstein-Vazirani*.\n", "È anche chiamato *problema del campionamento di Fourier*, sebbene esistano formulazioni più generali di questo problema che vanno anche sotto questo nome.\n", "\n", "Per prima cosa, introduciamo alcune notazioni.\n", "Per due stringhe binarie qualsiasi $x = x_{n-1} \\cdots x_0$ e $y = y_{n-1}\\cdots y_0$ di lunghezza $n,$ definiamo\n", "\n", "$$\n", "x \\cdot y = x_{n-1} y_{n-1} \\oplus \\cdots \\oplus x_0 y_0.\n", "$$\n", "\n", "Questa operazione viene chiamata *prodotto binario dei punti*.\n", "Un modo alternativo per definirlo è il seguente.\n", "\n", "$$\n", "x \\cdot y =\n", "\\begin{cases}\n", "1 & x_{{n-1}} y_{n-1} + \\cdots + x_0 y_0 \\text{ is odd}\\\\[0.5mm]\n", "0 & x_{{n-1}} y_{n-1} + \\cdots + x_0 y_0 \\text{ is even}\n", "\\end{cases}\n", "$$\n", "\n", "Si noti che si tratta di un'operazione simmetrica, il che significa che il risultato non cambia se si scambiano $x$ e $y,$, quindi siamo liberi di farlo ogni volta che è conveniente.\n", "A volte è utile pensare al prodotto binario dei punti $x \\cdot y$ come alla parità dei bit di $x$ nelle posizioni in cui la stringa $y$ ha un $1,$ o, equivalentemente, alla parità dei bit di $y$ nelle posizioni in cui la stringa $x$ ha un $1.$\n", "\n", "Con questa notazione in mano possiamo ora definire il problema di Bernstein-Vazirani.\n", "\n", "
\n", " Input: una funzione $f:\\{0,1\\}^n\\rightarrow\\{0,1\\}$ \\ Promessa: esiste una stringa binaria $s = s_{n-1} \\cdots s_0$ per la quale $f(x) = s\\cdot x$ per tutte le $x\\in\\Sigma^n$ \\ Uscita: la stringa $s$\n", "
\n", "\n", "In realtà non abbiamo bisogno di un nuovo algoritmo quantistico per questo problema; l'algoritmo di Deutsch-Jozsa lo risolve.\n", "Per chiarezza, chiamiamo il circuito quantistico di cui sopra, che non include la fase classica di post-elaborazione del calcolo dell'OR, *circuito Deutsch-Jozsa*.\n", "\n", "\n", "\n", "### Analisi dell'algoritmo\n", "\n", "Per analizzare come funziona il circuito di Deutsch-Jozsa per una funzione che soddisfa la promessa del problema di Bernstein-Vazirani, inizieremo con una rapida osservazione.\n", "Utilizzando il prodotto binario dei punti, possiamo descrivere alternativamente l'azione delle porte di Hadamard di $n$ sugli stati base standard dei qubit di $n$ come segue.\n", "\n", "$$\n", "H^{\\otimes n} \\vert x \\rangle = \\frac{1}{\\sqrt{2^n}} \\sum_{y\\in\\Sigma^n} (-1)^{x\\cdot y} \\vert y\\rangle\n", "$$\n", "\n", "Analogamente a quanto abbiamo visto analizzando l'algoritmo di Deutsch, questo è dovuto al fatto che il valore $(-1)^k$ per qualsiasi intero $k$ dipende solo dal fatto che $k$ sia pari o dispari.\n", "\n", "Passando al circuito di Deutsch-Jozsa, dopo che è stato eseguito il primo strato di porte di Hadamard, lo stato dei qubit di $n+1$ è\n", "\n", "$$\n", "\\vert - \\rangle \\otimes \\frac{1}{\\sqrt{2^n}} \\sum_{x \\in \\Sigma^n} \\vert x \\rangle.\n", "$$\n", "\n", "Viene quindi eseguito il gate di interrogazione, che (attraverso il fenomeno del contraccolpo di fase) trasforma lo stato in\n", "\n", "$$\n", "\\vert - \\rangle \\otimes \\frac{1}{\\sqrt{2^n}} \\sum_{x \\in \\Sigma^n} (-1)^{f(x)} \\vert x \\rangle.\n", "$$\n", "\n", "Utilizzando la nostra formula per l'azione di uno strato di porte di Hadamard, vediamo che il secondo strato di porte di Hadamard trasforma poi questo stato in\n", "\n", "$$\n", "\\vert - \\rangle \\otimes \\frac{1}{2^n}\n", "\\sum_{x \\in \\Sigma^n} \\sum_{y \\in \\Sigma^n} (-1)^{f(x) + x \\cdot y} \\vert y \\rangle.\n", "$$\n", "\n", "Ora possiamo fare alcune semplificazioni, nell'esponente di $-1$ all'interno della somma.\n", "Ci è stato promesso che $f(x) = s\\cdot x$ per qualche stringa $s = s_{n-1} \\cdots s_0,$ in modo da poter esprimere lo stato come\n", "\n", "$$\n", "\\vert - \\rangle \\otimes \\frac{1}{2^n}\n", "\\sum_{x \\in \\Sigma^n} \\sum_{y \\in \\Sigma^n} (-1)^{s\\cdot x + x \\cdot y} \\vert y \\rangle.\n", "$$\n", "\n", "Poiché $s\\cdot x$ e $x\\cdot y$ sono valori binari, possiamo sostituire l'addizione con l'OR esclusivo - sempre perché l'unica cosa che conta per un intero nell'esponente di $-1$ è che sia pari o dispari.\n", "Sfruttando la simmetria del prodotto binario dei punti, si ottiene questa espressione per lo stato:\n", "\n", "$$\n", "\\vert - \\rangle \\otimes \\frac{1}{2^n}\n", "\\sum_{x \\in \\Sigma^n} \\sum_{y \\in \\Sigma^n} (-1)^{(s\\cdot x) \\oplus (y \\cdot x)} \\vert y \\rangle.\n", "$$\n", "\n", "(Le parentesi sono state aggiunte per chiarezza, anche se in realtà non sono necessarie perché è convenzionale trattare il prodotto binario dei punti come se avesse una precedenza maggiore rispetto all'OR esclusivo)\n", "\n", "A questo punto utilizzeremo la seguente formula.\n", "\n", "$$\n", "(s\\cdot x) \\oplus (y \\cdot x) = (s \\oplus y) \\cdot x\n", "$$\n", "\n", "Possiamo ottenere la formula attraverso una formula simile per i bit,\n", "\n", "$$\n", "(a c) \\oplus (b c) = (a \\oplus b) c,\n", "$$\n", "\n", "insieme a un'espansione del prodotto binario dei punti e del bitwise exclusive-OR:\n", "\n", "$$\n", "\\begin{aligned}\n", "(s\\cdot x) \\oplus (y \\cdot x)\n", "& = (s_{n-1} x_{n-1}) \\oplus \\cdots \\oplus (s_{0} x_{0}) \\oplus\n", "(y_{n-1} x_{n-1}) \\oplus \\cdots \\oplus (y_{0} x_{0}) \\\\\n", "& = (s_{n-1} \\oplus y_{n-1}) x_{n-1} \\oplus \\cdots \\oplus (s_{0} \\oplus y_{0}) x_{0} \\\\\n", "& = (s \\oplus y) \\cdot x\n", "\\end{aligned}\n", "$$\n", "\n", "Questo ci permette di esprimere lo stato del circuito immediatamente prima delle misure in questo modo:\n", "\n", "$$\n", "\\vert - \\rangle \\otimes \\frac{1}{2^n}\n", "\\sum_{x \\in \\Sigma^n} \\sum_{y \\in \\Sigma^n} (-1)^{(s\\oplus y)\\cdot x} \\vert y \\rangle.\n", "$$\n", "\n", "Il passo finale consiste nell'utilizzare un'altra formula, che funziona per ogni stringa binaria $z = z_{n-1}\\cdots z_0.$\n", "\n", "$$\n", "\\frac{1}{2^n}\n", "\\sum_{x \\in \\Sigma^n} (-1)^{z \\cdot x}\n", "= \\begin{cases}\n", "1 & \\text{if $z = 0^n$}\\\\\n", "0 & \\text{if $z\\neq 0^n$}\n", "\\end{cases}\n", "$$\n", "\n", "Qui usiamo una semplice notazione per le stringhe che useremo più volte nel corso della lezione: $0^n$ è la stringa di lunghezza pari a zero $n.$\n", "\n", "Un modo semplice per dimostrare che questa formula funziona è considerare i due casi separatamente.\n", "Se $z = 0^n,$ allora $z\\cdot x = 0$ per ogni stringa $x\\in\\Sigma^n,$ quindi il valore di ogni termine della somma è $1,$ e si ottiene $1$ sommando e dividendo per $2^n.$ D'altra parte, se uno qualsiasi dei bit di $z$ è uguale a $1,$ allora il prodotto binario dei punti $z\\cdot x$ è uguale a $0$ per esattamente la metà delle scelte possibili per $x\\in\\Sigma^n$ e $1$ per l'altra metà - perché il valore del prodotto binario dei punti $z\\cdot x$ si capovolge (da $0$ a $1$ o da $1$ a $0$ ) se capovolgiamo un qualsiasi bit di $x$ in una posizione in cui $z$ ha una $1.$\n", "\n", "Se ora applichiamo questa formula per semplificare lo stato del circuito prima delle misure, otteniamo\n", "\n", "$$\n", "\\vert - \\rangle \\otimes \\frac{1}{2^n}\n", "\\sum_{x \\in \\Sigma^n} \\sum_{y \\in \\Sigma^n} (-1)^{(s\\oplus y)\\cdot x} \\vert y \\rangle\n", "= \\vert - \\rangle \\otimes \\vert s \\rangle,\n", "$$\n", "\n", "perché $s\\oplus y = 0^n$ se e solo se $y = s.$ Pertanto, le misure rivelano proprio la stringa $s$ che stiamo cercando.\n", "\n", "\n", "\n", "### Difficoltà classica\n", "\n", "Mentre il circuito Deutsch-Jozsa risolve il problema di Bernstein-Vazirani con una sola interrogazione, qualsiasi algoritmo di interrogazione classico deve effettuare almeno $n$ interrogazioni per risolvere questo problema.\n", "\n", "Si può ragionare attraverso un cosiddetto argomento *di teoria dell'informazione*, che in questo caso è molto semplice.\n", "Ogni interrogazione classica rivela un singolo bit di informazione sulla soluzione, e ci sono $n$ bit di informazione che devono essere scoperti, quindi sono necessarie almeno $n$ interrogazioni.\n", "\n", "È infatti possibile risolvere il problema di Bernstein-Vazirani in modo classico, interrogando la funzione su ciascuna delle stringhe $n$ che hanno un singolo $1,$ in ogni possibile posizione, e $0$ per tutti gli altri bit, che rivela i bit di $s$ uno alla volta.\n", "Pertanto, il vantaggio degli algoritmi quantistici rispetto a quelli classici per questo problema è $1$ query rispetto a $n$ query.\n", "\n" ] }, { "cell_type": "markdown", "id": "28583734", "metadata": {}, "source": [ "\n", "\n", "## Bernstein-Vazirani con Qiskit\n", "\n", "Abbiamo già implementato il circuito di Deutsch-Jozsa sopra, e qui lo useremo per risolvere il problema di Bernstein-Vazirani.\n", "Per prima cosa definiremo una funzione che implementa una porta di interrogazione per il problema di Bernstein-Vazirani, data una qualsiasi stringa binaria $s.$\n", "\n" ] }, { "cell_type": "code", "execution_count": 18, "id": "11861a7e", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\"Output" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "def bv_query(s):\n", " # Create a quantum circuit implementing a query gate for the\n", " # Bernstein-Vazirani problem.\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_query(\"1011\").draw(output=\"mpl\"))" ] }, { "cell_type": "markdown", "id": "c24e91e8", "metadata": {}, "source": [ "Ora possiamo creare una funzione che esegua il circuito Deutsch-Jozsa sulla funzione, utilizzando la funzione `compile_circuit` definita in precedenza.\n", "\n" ] }, { "cell_type": "code", "execution_count": 19, "id": "7db2ea99", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "'1011'" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "def bv_algorithm(function: QuantumCircuit):\n", " qc = compile_circuit(function)\n", " result = AerSimulator().run(qc, shots=1, memory=True).result()\n", " return result.get_memory()[0]\n", "\n", "\n", "display(bv_algorithm(bv_query(\"1011\")))" ] }, { "cell_type": "markdown", "id": "86c52e37", "metadata": {}, "source": [ "\n", "\n", "### Osservazione sulla nomenclatura\n", "\n", "Nel contesto del problema di Bernstein-Vazirani, è comune che l'algoritmo di Deutsch-Jozsa sia indicato come \"algoritmo di Bernstein-Vazirani\"\n", "Questo è leggermente fuorviante, perché l'algoritmo *è* l'algoritmo di Deutsch-Jozsa, come Bernstein e Vazirani hanno detto chiaramente nel loro lavoro.\n", "\n", "Dopo aver dimostrato che l'algoritmo di Deutsch-Jozsa risolve il problema di Bernstein-Vazirani (come si è detto), Bernstein e Vazirani hanno definito un problema molto più complicato, noto come *problema di campionamento ricorsivo di Fourier*.\n", "Si tratta di un problema altamente congegnato in cui le soluzioni alle diverse istanze del problema sbloccano effettivamente nuovi livelli del problema disposti in una struttura ad albero.\n", "Il problema di Bernstein-Vazirani è essenzialmente solo il caso base di questo problema più complicato.\n", "\n", "Il problema del campionamento ricorsivo di Fourier è stato il primo esempio conosciuto di problema di interrogazione in cui gli algoritmi quantistici hanno un vantaggio cosiddetto *super-polinomiale* rispetto agli algoritmi probabilistici, superando così il vantaggio dei quanti rispetto ai classici offerto dall'algoritmo di Deutsch-Jozsa.\n", "Intuitivamente, la versione ricorsiva del problema amplifica il vantaggio di $1$ rispetto a $n$ degli algoritmi quantistici a qualcosa di molto più grande.\n", "\n", "L'aspetto più impegnativo dell'analisi matematica che stabilisce questo vantaggio è dimostrare che gli algoritmi di interrogazione classici non possono risolvere il problema senza effettuare molte interrogazioni.\n", "Questo è abbastanza tipico; per molti problemi può essere molto difficile escludere approcci classici creativi che li risolvano in modo efficiente.\n", "\n", "Il problema di Simon, e l'algoritmo per esso descritto nella prossima sezione, fornisce un esempio molto più semplice di un vantaggio super-polinomiale (e, di fatto, esponenziale) degli algoritmi quantistici rispetto a quelli classici, e per questo motivo il problema del campionamento ricorsivo di Fourier viene discusso meno spesso.\n", "Si tratta comunque di un interessante problema computazionale a sé stante.\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" } }, "nbformat": 4, "nbformat_minor": 5 }