{ "cells": [ { "cell_type": "markdown", "id": "17463a96", "metadata": {}, "source": [ "---\n", "title: \"O algoritmo de Deutsch-Jozsa\"\n", "description: \"Um curso gratuito sobre informação e computação quântica ministrado por IBM\"\n", "---\n", "\n", "\n", "\n", "# O algoritmo de Deutsch-Jozsa\n", "\n", "O algoritmo de Deutsch supera todos os algoritmos clássicos para um problema de consulta, mas a vantagem é bastante modesta: uma consulta contra duas.\n", "O algoritmo Deutsch-Jozsa amplia essa vantagem e, de fato, pode ser usado para resolver alguns problemas de consulta diferentes.\n", "\n", "Aqui está uma descrição do circuito quântico do algoritmo Deutsch-Jozsa.\n", "Uma etapa adicional clássica de pós-processamento, não mostrada na figura, também pode ser necessária, dependendo do problema específico que está sendo resolvido.\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", "É claro que ainda não discutimos quais problemas esse algoritmo resolve; isso será feito nas duas seções a seguir.\n", "\n", "\n", "\n", "## O problema de Deutsch-Jozsa\n", "\n", "Começaremos com o problema de consulta que o algoritmo Deutsch-Jozsa foi originalmente planejado para resolver, conhecido como o *problema Deutsch-Jozsa*.\n", "\n", "A função de entrada para esse problema tem o formato $f:\\Sigma^n \\rightarrow \\Sigma$ para um número inteiro positivo arbitrário $n.$ Como no problema de Deutsch, a tarefa é produzir $0$ se $f$ for constante e $1$ se $f$ for equilibrado, o que significa novamente que o número de cadeias de caracteres de entrada nas quais a função assume o valor $0$ é igual ao número de cadeias de caracteres de entrada nas quais a função assume o valor $1$.\n", "\n", "Observe que, quando $n$ é maior que $1,$, há funções do formato $f:\\Sigma^n \\rightarrow \\Sigma$ que não são constantes nem equilibradas.\n", "Por exemplo, a função $f:\\Sigma^2\\rightarrow\\Sigma$ definida como\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", "não se enquadra em nenhuma dessas duas categorias.\n", "No caso do problema Deutsch-Jozsa, simplesmente não nos preocupamos com funções como essa - elas são consideradas entradas \"indiferentes\".\n", "Ou seja, para esse problema, temos *a promessa de* que $f$ é constante ou equilibrado.\n", "\n", "
\n", " Entrada: uma função $f:\\{0,1\\}^n\\rightarrow\\{0,1\\}$ \\ Promessa: $f$ é constante ou equilibrada \\ Saída: $0$ se $f$ for constante, $1$ se $f$ for equilibrado\n", "
\n", "\n", "O algoritmo de Deutsch-Jozsa, com sua única consulta, resolve esse problema da seguinte maneira:\n", "se todos os resultados das medições $n$ forem $0,$, então a função $f$ é constante;\n", "caso contrário, se pelo menos um dos resultados das medições for $1,$, então a função $f$ é equilibrada.\n", "Outra forma de expressar isso é dizer que o circuito descrito acima é seguido por uma etapa clássica de pós-processamento, na qual se calcula a operação OR dos resultados das medições para produzir o bit de saída do problema de Deutsch-Jozsa.\n", "\n", "\n", "\n", "### Análise de algoritmos\n", "\n", "Para analisar o desempenho do algoritmo Deutsch-Jozsa para o problema Deutsch-Jozsa, é útil começar pensando na ação de uma única camada de portas Hadamard.\n", "Uma operação Hadamard pode ser expressa como uma matriz da maneira usual,\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", "mas também podemos expressar essa operação em termos de sua ação nos estados da base padrão:\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", "Essas duas equações podem ser combinadas em uma única fórmula,\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", "o que é verdadeiro para ambas as opções de $a\\in\\Sigma.$\n", "\n", "Agora, suponha que, em vez de apenas um único qubit, tenhamos $n$ qubits e que uma operação Hadamard seja realizada em cada um deles.\n", "A operação combinada nos $n$ qubits é descrita pelo produto tensorial $H\\otimes \\cdots \\otimes H$ ( $n$ vezes), que escrevemos como $H^{\\otimes n}$ para fins de concisão e clareza.\n", "Usando a fórmula acima, seguida de expansão e simplificação, podemos expressar a ação dessa operação combinada nos estados da base padrão dos $n$ qubits da seguinte forma:\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", "Aqui, a propósito, estamos escrevendo strings binárias de comprimento $n$ como $x_{n-1}\\cdots x_0$ e $y_{n-1}\\cdots y_0,$ seguindo a convenção de indexação do Qiskit.\n", "\n", "Essa fórmula nos fornece uma ferramenta útil para analisar o circuito quântico acima.\n", "Após a execução da primeira camada de portas Hadamard, o estado dos $n+1$ qubits (incluindo o qubit mais à esquerda/inferior, que é tratado separadamente do restante) é\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 a operação $U_f$ é realizada, esse estado é transformado em\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", "exatamente pelo mesmo fenômeno de retorno de fase que vimos na análise do algoritmo de Deutsch.\n", "\n", "Em seguida, a segunda camada de portas Hadamard é executada, o que (pela fórmula acima) transforma esse estado em\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", "Essa expressão parece um pouco complicada, e não se pode concluir muito sobre as probabilidades de obter diferentes resultados de medição sem saber mais sobre a função $f.$\n", "\n", "Felizmente, tudo o que precisamos saber é a probabilidade de que cada um dos resultados da medição seja $0$ - porque essa é a probabilidade de que o algoritmo determine que $f$ é constante.\n", "Essa probabilidade tem uma fórmula simples.\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", "Observe que esses valores correspondem à probabilidade de se medir o estado\n", "$\\vert 0^{\\otimes n} \\rangle$, e não diretamente ao bit de saída clássico final do\n", "problema de Deutsch-Jozsa. O algoritmo gera o resultado “ $0$ ” quando todos os resultados das medições\n", "são “ $0$ ” (indicando que “ $f$ ” é constante) e, caso contrário, gera “ $1$ ”\n", "(indicando que “ $f$ ” está em equilíbrio).\n", "\n", "Mais detalhadamente, se $f$ for constante, então $f(x_{n-1}\\cdots x_0) = 0$ para cada string $x_{n-1}\\cdots x_0,$ caso em que o valor da soma é $2^n,$ ou $f(x_{n-1}\\cdots x_0) = 1$ para cada string $x_{n-1}\\cdots x_0,$ e, nesse caso, o valor da soma é $-2^n.$ Dividindo por $2^n$ e tomando o quadrado do valor absoluto, obtém-se $1.$\n", "\n", "Se, por outro lado, $f$ estiver equilibrado, então $f$ assume o valor $0$ em metade das cadeias de caracteres $x_{n-1}\\cdots x_0$ e o valor $1$ na outra metade, de modo que os termos $+1$ e $-1$ na soma se cancelam e ficamos com o valor $0.$\n", "\n", "Concluímos que o algoritmo funciona corretamente desde que a promessa seja cumprida.\n", "\n", "\n", "\n", "### Dificuldade clássica\n", "\n", "O algoritmo Deutsch-Jozsa funciona todas as vezes, sempre nos dando a resposta correta quando a promessa é cumprida, e requer uma única consulta.\n", "Como isso se compara aos algoritmos de consulta clássicos para o problema Deutsch-Jozsa?\n", "\n", "Primeiro, qualquer algoritmo clássico *determinístico* que resolva corretamente o problema Deutsch-Jozsa deve fazer um número exponencial de consultas: $2^{n-1} + 1$ consultas são necessárias no pior dos casos.\n", "O raciocínio é que, se um algoritmo determinístico consultar $f$ em $2^{n-1}$ ou menos cadeias de caracteres diferentes e obtiver o mesmo valor de função todas as vezes, então ambas as respostas ainda serão possíveis.\n", "A função pode ser constante ou equilibrada, mas, por azar, todas as consultas retornam o mesmo valor de função.\n", "\n", "A segunda possibilidade pode parecer improvável, mas para algoritmos determinísticos não há aleatoriedade ou incerteza, portanto, eles falharão sistematicamente em determinadas funções.\n", "Portanto, temos uma vantagem significativa dos algoritmos quânticos em relação aos clássicos nesse aspecto.\n", "\n", "No entanto, há um problema: os algoritmos clássicos *probabilísticos* podem resolver o problema Deutsch-Jozsa com uma probabilidade muito alta usando apenas algumas consultas.\n", "Em particular, se simplesmente escolhermos algumas cadeias diferentes de comprimento $n$ aleatoriamente e consultarmos $f$ nessas cadeias, é improvável que obtenhamos o mesmo valor de função para todas elas quando $f$ estiver equilibrado.\n", "\n", "Para ser mais específico, se escolhermos as cadeias de entrada $k$ $x^1,\\ldots,x^k \\in \\Sigma^n$ uniformemente ao acaso, avaliarmos $f(x^1),\\ldots,f(x^k),$ e respondermos $0$ se os valores da função forem todos iguais e $1$ se não forem, então sempre estaremos corretos quando $f$ for constante e errados no caso de $f$ ser equilibrado com probabilidade igual a $2^{-k + 1}.$ Se considerarmos $k = 11,$, por exemplo, esse algoritmo responderá corretamente com probabilidade maior que $99.9$ %.\n", "\n", "Por esse motivo, ainda temos uma vantagem bastante modesta dos algoritmos quânticos em relação aos clássicos, mas, ainda assim, é uma vantagem quantificável que representa um aprimoramento em relação ao algoritmo de Deutsch.\n", "\n" ] }, { "cell_type": "markdown", "id": "83b0e8b5", "metadata": {}, "source": [ "\n", "\n", "## Deutsch-Jozsa com 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": [ "Para implementar o algoritmo Deutsch-Jozsa no Qiskit, começaremos definindo uma função `dj_query` que gera um circuito quântico implementando uma porta de consulta, para uma função selecionada aleatoriamente que satisfaça a promessa do problema Deutsch-Jozsa.\n", "Com 50% de chance, a função é constante, e com 50% de mudança, a função é equilibrada.\n", "Para cada uma dessas duas possibilidades, a função é selecionada uniformemente entre as funções desse tipo.\n", "O argumento é o número de bits de entrada da função.\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": [ "Podemos mostrar a implementação do circuito quântico da porta de consulta usando o método `draw` como de costume.\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": [ "Em seguida, definimos uma função que cria o circuito Deutsch-Jozsa, tendo como argumento uma implementação de circuito quântico de uma porta de consulta.\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": [ "Por fim, é definida uma função que executa o circuito Deutsch-Jozsa uma vez.\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": [ "Podemos testar nossa implementação escolhendo uma função aleatoriamente, exibindo a implementação do circuito quântico de uma porta de consulta para essa função e, em seguida, executando o algoritmo Deutsch-Jozsa nessa função.\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", "## O problema de Bernstein-Vazirani\n", "\n", "A seguir, discutiremos um problema conhecido como *problema de Bernstein-Vazirani*.\n", "Ele também é chamado de *problema de amostragem de Fourier*, embora existam formulações mais gerais desse problema que também têm esse nome.\n", "\n", "Primeiro, vamos introduzir algumas notações.\n", "Para quaisquer duas cadeias binárias $x = x_{n-1} \\cdots x_0$ e $y = y_{n-1}\\cdots y_0$ de comprimento $n,$, definimos\n", "\n", "$$\n", "x \\cdot y = x_{n-1} y_{n-1} \\oplus \\cdots \\oplus x_0 y_0.\n", "$$\n", "\n", "Vamos nos referir a essa operação como o *produto de ponto binário*.\n", "Uma maneira alternativa de defini-lo é assim.\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", "Observe que essa é uma operação simétrica, o que significa que o resultado não muda se trocarmos $x$ e $y,$, portanto, podemos fazer isso sempre que for conveniente.\n", "Às vezes, é útil pensar no produto de ponto binário $x \\cdot y$ como sendo a paridade dos bits de $x$ nas posições em que a cadeia de caracteres $y$ tem um $1,$ ou, de forma equivalente, a paridade dos bits de $y$ nas posições em que a cadeia de caracteres $x$ tem um $1.$\n", "\n", "Com essa notação em mãos, podemos agora definir o problema de Bernstein-Vazirani.\n", "\n", "
\n", " Entrada: uma função $f:\\{0,1\\}^n\\rightarrow\\{0,1\\}$ \\ Promessa: existe uma string binária $s = s_{n-1} \\cdots s_0$ para a qual $f(x) = s\\cdot x$ para todos os $x\\in\\Sigma^n$ \\ Saída: a string $s$\n", "
\n", "\n", "Na verdade, não precisamos de um novo algoritmo quântico para esse problema; o algoritmo Deutsch-Jozsa o resolve.\n", "Para fins de clareza, vamos nos referir ao circuito quântico acima, que não inclui a etapa clássica de pós-processamento de computação do OU, como o *circuito Deutsch-Jozsa*.\n", "\n", "\n", "\n", "### Análise de algoritmos\n", "\n", "Para analisar como o circuito Deutsch-Jozsa funciona para uma função que satisfaz a promessa do problema Bernstein-Vazirani, começaremos com uma observação rápida.\n", "Usando o produto de ponto binário, podemos, alternativamente, descrever a ação de $n$ Hadamard gates nos estados de base padrão de $n$ qubits da seguinte forma.\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", "Semelhante ao que vimos ao analisar o algoritmo de Deutsch, isso ocorre porque o valor $(-1)^k$ para qualquer número inteiro $k$ depende apenas do fato de $k$ ser par ou ímpar.\n", "\n", "Voltando ao circuito Deutsch-Jozsa, após a execução da primeira camada de portas Hadamard, o estado dos $n+1$ qubits é\n", "\n", "$$\n", "\\vert - \\rangle \\otimes \\frac{1}{\\sqrt{2^n}} \\sum_{x \\in \\Sigma^n} \\vert x \\rangle.\n", "$$\n", "\n", "A porta de consulta é então executada, o que (por meio do fenômeno de retrocesso de fase) transforma o estado em\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", "Usando nossa fórmula para a ação de uma camada de portas Hadamard, vemos que a segunda camada de portas Hadamard transforma esse estado em\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", "Agora podemos fazer algumas simplificações, no expoente de $-1$ dentro da soma.\n", "Prometemos que $f(x) = s\\cdot x$ para alguma string $s = s_{n-1} \\cdots s_0,$ para que possamos expressar o estado como\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", "Como $s\\cdot x$ e $x\\cdot y$ são valores binários, podemos substituir a adição pelo exclusivo-OR - novamente porque a única coisa que importa para um número inteiro no expoente de $-1$ é se ele é par ou ímpar.\n", "Usando a simetria do produto de ponto binário, obtemos essa expressão para o estado:\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", "(Os parênteses foram adicionados para fins de clareza, embora não sejam realmente necessários, pois é convencional tratar o produto de ponto binário como tendo precedência mais alta do que o exclusivo-OR)\n", "\n", "Neste ponto, usaremos a seguinte fórmula.\n", "\n", "$$\n", "(s\\cdot x) \\oplus (y \\cdot x) = (s \\oplus y) \\cdot x\n", "$$\n", "\n", "Podemos obter a fórmula por meio de uma fórmula semelhante para bits,\n", "\n", "$$\n", "(a c) \\oplus (b c) = (a \\oplus b) c,\n", "$$\n", "\n", "juntamente com uma expansão do produto de ponto binário e do 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", "Isso nos permite expressar o estado do circuito imediatamente antes das medições da seguinte forma:\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", "A etapa final é usar outra fórmula, que funciona para cada string binária $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", "Aqui estamos usando uma notação simples para cadeias de caracteres que usaremos várias outras vezes na lição: $0^n$ é a cadeia de caracteres totalmente zero de comprimento $n.$\n", "\n", "Uma maneira simples de argumentar que essa fórmula funciona é considerar os dois casos separadamente.\n", "Se $z = 0^n,$, então $z\\cdot x = 0$ para cada cadeia de caracteres $x\\in\\Sigma^n,$, então o valor de cada termo na soma é $1,$ e obtemos $1$ somando e dividindo por $2^n.$ Por outro lado, se qualquer um dos bits de $z$ for igual a $1,$, então o produto de ponto binário $z\\cdot x$ é igual a $0$ para exatamente metade das escolhas possíveis para $x\\in\\Sigma^n$ e $1$ para a outra metade - porque o valor do produto de ponto binário $z\\cdot x$ inverte (de $0$ para $1$ ou de $1$ para $0$ ) se invertermos qualquer bit de $x$ em uma posição em que $z$ tenha um $1.$\n", "\n", "Se agora aplicarmos essa fórmula para simplificar o estado do circuito antes das medições, obteremos\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", "devido ao fato de que $s\\oplus y = 0^n$ se e somente se $y = s.$ Portanto, as medições revelam precisamente a string $s$ que estamos procurando.\n", "\n", "\n", "\n", "### Dificuldade clássica\n", "\n", "Enquanto o circuito Deutsch-Jozsa resolve o problema Bernstein-Vazirani com uma única consulta, qualquer algoritmo de consulta clássico precisa fazer pelo menos $n$ consultas para resolver esse problema.\n", "\n", "Isso pode ser explicado por meio do chamado argumento *da teoria da informação*, que é muito simples nesse caso.\n", "Cada consulta clássica revela um único bit de informação sobre a solução, e há $n$ bits de informação que precisam ser descobertos - portanto, são necessárias pelo menos $n$ consultas.\n", "\n", "De fato, é possível resolver o problema de Bernstein-Vazirani de forma clássica, consultando a função em cada uma das cadeias de caracteres $n$ com um único $1,$ em cada posição possível e $0$ para todos os outros bits, o que revela os bits de $s$ um de cada vez.\n", "Portanto, a vantagem do quantum sobre os algoritmos clássicos para esse problema é $1$ query versus $n$ queries.\n", "\n" ] }, { "cell_type": "markdown", "id": "28583734", "metadata": {}, "source": [ "\n", "\n", "## Bernstein-Vazirani com Qiskit\n", "\n", "Já implementamos o circuito Deutsch-Jozsa acima e aqui o utilizaremos para resolver o problema Bernstein-Vazirani.\n", "Primeiro, definiremos uma função que implementa uma porta de consulta para o problema de Bernstein-Vazirani com qualquer string binária $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": [ "Agora podemos criar uma função que executa o circuito Deutsch-Jozsa na função, usando a função `compile_circuit` que foi definida anteriormente.\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", "### Observação sobre a nomenclatura\n", "\n", "No contexto do problema Bernstein-Vazirani, é comum que o algoritmo Deutsch-Jozsa seja chamado de \"algoritmo Bernstein-Vazirani\"\n", "Isso é um pouco enganoso, pois o algoritmo *é* o algoritmo Deutsch-Jozsa, como Bernstein e Vazirani deixaram bem claro em seu trabalho.\n", "\n", "O que Bernstein e Vazirani fizeram depois de mostrar que o algoritmo Deutsch-Jozsa resolve o problema de Bernstein-Vazirani (como foi dito acima) foi definir um problema muito mais complicado, conhecido como *problema de amostragem recursiva de Fourier*.\n", "Esse é um problema altamente planejado em que as soluções para diferentes instâncias do problema efetivamente desbloqueiam novos níveis do problema organizados em uma estrutura semelhante a uma árvore.\n", "O problema de Bernstein-Vazirani é essencialmente apenas o caso básico desse problema mais complicado.\n", "\n", "O problema de amostragem recursiva de Fourier foi o primeiro exemplo conhecido de um problema de consulta em que os algoritmos quânticos têm a chamada vantagem *superpolinomial* sobre os algoritmos probabilísticos, superando assim a vantagem do quântico sobre o clássico oferecida pelo algoritmo Deutsch-Jozsa.\n", "Intuitivamente falando, a versão recursiva do problema amplia a vantagem $1$ versus $n$ dos algoritmos quânticos para algo muito maior.\n", "\n", "O aspecto mais desafiador da análise matemática que estabelece essa vantagem é mostrar que os algoritmos de consulta clássicos não conseguem resolver o problema sem fazer muitas consultas.\n", "Isso é bastante comum; para muitos problemas, pode ser muito difícil descartar abordagens clássicas criativas que os resolvam de forma eficiente.\n", "\n", "O problema de Simon e o algoritmo para ele descrito na próxima seção fornecem um exemplo muito mais simples de uma vantagem superpolinomial (e, na verdade, exponencial) do quantum em relação aos algoritmos clássicos e, por esse motivo, o problema de amostragem recursiva de Fourier é discutido com menos frequência.\n", "No entanto, esse é um problema computacional interessante por si só.\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 }