{ "cells": [ { "cell_type": "markdown", "id": "7e5d320e", "metadata": {}, "source": [ "---\n", "title: \"Algoritmo de Deutsch\"\n", "description: \"Um curso gratuito sobre informação e computação quântica ministrado por IBM\"\n", "---\n", "\n", "\n", "\n", "# Algoritmo de Deutsch\n", "\n", "O algoritmo de Deutsch resolve o problema de paridade para o caso especial em que $n = 1.$ No contexto da computação quântica, esse problema às vezes é chamado de *problema de Deutsch*, e seguiremos essa nomenclatura nesta lição.\n", "\n", "Para ser mais preciso, a entrada é representada por uma função $f:\\Sigma \\rightarrow \\Sigma$ de um bit para um bit.\n", "Há quatro funções desse 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", "A primeira e a última dessas funções são *constantes* e as duas do meio são *equilibradas*, o que significa que os dois valores de saída possíveis para a função ocorrem o mesmo número de vezes à medida que percorremos as entradas.\n", "O problema de Deutsch é determinar a qual dessas duas categorias a função de entrada pertence: constante ou equilibrada.\n", "\n", "
\n", " Entrada: uma função $f:\\{0,1\\}\\rightarrow\\{0,1\\}$ \\ Saída: $0$ se $f$ for constante, $1$ se $f$ for equilibrado\n", "
\n", "\n", "Se considerarmos a função de entrada $f$ no problema de Deutsch como representando o acesso aleatório a uma cadeia de caracteres, estaremos pensando em uma cadeia de dois bits: $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", "Quando visto dessa forma, o problema de Deutsch é calcular a paridade (ou, de forma equivalente, o OU exclusivo) dos dois bits.\n", "\n", "Todo algoritmo de consulta clássico que resolve corretamente esse problema deve consultar ambos os bits: $f(0)$ e $f(1).$ Se soubermos que $f(1) = 1,$, por exemplo, a resposta ainda poderá ser $0$ ou $1,$, dependendo de $f(0) = 1$ ou $f(0) = 0,$, respectivamente.\n", "Todos os outros casos são semelhantes; conhecer apenas um dos dois bits não fornece nenhuma informação sobre sua paridade.\n", "Portanto, o circuito booleano descrito na seção anterior é o melhor que podemos fazer em termos do número de consultas necessárias para resolver esse problema.\n", "\n", "\n", "\n", "## Descrição do circuito quântico\n", "\n", "O algoritmo de Deutsch resolve o problema de Deutsch usando uma única consulta, proporcionando, portanto, uma vantagem quantificável da computação quântica em relação à clássica.\n", "Essa pode ser uma vantagem modesta - uma consulta em vez de duas - mas temos que começar por algum lugar.\n", "Os avanços científicos às vezes têm origens aparentemente humildes.\n", "\n", "Aqui está um circuito quântico que descreve o algoritmo de Deutsch:\n", "\n", "![Algoritmo de Deutsch](https://quantum.cloud.ibm.com/learning/images/courses/fundamentals-of-quantum-algorithms/quantum-query-algorithms/Deutsch-circuit.svg)\n", "\n", "\n", "\n", "## Análise\n", "\n", "Para analisar o algoritmo de Deutsch, vamos rastrear a ação do circuito acima e identificar os estados dos qubits nos momentos sugeridos por essa figura:\n", "\n", "![Estados durante o algoritmo de Deutsch](https://quantum.cloud.ibm.com/learning/images/courses/fundamentals-of-quantum-algorithms/quantum-query-algorithms/Deutsch-circuit-states.svg)\n", "\n", "O estado inicial é $\\vert 1\\rangle \\vert 0 \\rangle,$ e as duas operações Hadamard no lado esquerdo do circuito transformam esse estado em\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", "(Como sempre, estamos seguindo a convenção de ordenação de qubits do Qiskit, que coloca o qubit superior à direita e o qubit inferior à esquerda) Pode parecer pouco intuitivo escrever esse estado de produto parcialmente distribuído (deixando os estados do qubit 1 sem fatoração), mas isso tornará nossas expressões posteriores mais compactas.\n", "\n", "Em seguida, a porta $U_f$ é executada.\n", "De acordo com a definição da porta $U_f$, o valor da função $f$ para o estado clássico do qubit superior/direito é XORed no qubit inferior/esquerdo, o que transforma $\\vert \\pi_1\\rangle$ no estado\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", "Podemos simplificar essa expressão observando que a fórmula\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", "funciona para ambos os valores possíveis $a\\in\\Sigma.$ De forma mais explícita, os dois casos são os seguintes.\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", "Assim, podemos alternativamente expressar $\\vert\\pi_2\\rangle$ da seguinte forma:\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", "Algo interessante acabou de acontecer!\n", "Embora a ação da porta $U_f$ nos estados de base padrão deixe o qubit superior/direito sozinho e faça o XOR do valor da função no qubit inferior/mais à esquerda, aqui vemos que o estado do qubit superior/direito mudou (em geral) enquanto o estado do qubit inferior/mais à esquerda permanece o mesmo - especificamente no estado $\\vert - \\rangle$ antes e depois da execução da porta $U_f$.\n", "Esse fenômeno é conhecido como *retorno de fase*, e teremos mais informações sobre ele em breve.\n", "\n", "Com uma simplificação final, que é puxar o fator de $(-1)^{f(0)}$ para fora da soma, obtemos essa expressão do estado $\\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", "Observe que, nessa expressão, temos $f(0) \\oplus f(1)$ no expoente de $-1$ em vez de $f(1) - f(0),$, que é o que poderíamos esperar de um ponto de vista puramente algébrico, mas obtemos o mesmo resultado de qualquer maneira.\n", "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", "A aplicação da porta Hadamard final ao qubit superior nos deixa com o estado\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", "o que leva ao resultado correto com probabilidade $1$ quando o qubit direito/mais alto é medido.\n", "\n", "\n", "\n", "## Observações adicionais sobre o recuo de fase\n", "\n", "Antes de prosseguir, vamos examinar a análise acima de um ângulo ligeiramente diferente que pode esclarecer o fenômeno do recuo de fase.\n", "\n", "Primeiro, observe que a fórmula a seguir funciona para todas as opções de bits $b,c\\in\\Sigma.$\n", "\n", "$$\n", "\\vert b \\oplus c\\rangle = X^c \\vert b \\rangle\n", "$$\n", "\n", "Isso pode ser verificado verificando-o para os dois valores possíveis $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", "Usando essa fórmula, vemos que\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", "para cada escolha de bits $a,b\\in\\Sigma.$ Como essa fórmula é verdadeira para $b=0$ e $b=1,$, vemos por linearidade que\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", "para todos os vetores de estado do qubit $\\vert \\psi\\rangle,$ e, portanto\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", "O segredo para que isso funcione é que $X\\vert - \\rangle = - \\vert - \\rangle.$ Em termos matemáticos, o vetor $\\vert - \\rangle$ é um *vetor próprio* da matriz $X$ com *valor próprio* $-1.$\n", "\n", "Discutiremos os vetores próprios e os valores próprios com mais detalhes na próxima lição sobre *Estimativa de fase e fatoração,* em que o fenômeno de retrocesso de fase é generalizado para outras operações unitárias.\n", "\n", "Tendo em mente que os escalares flutuam livremente por meio de produtos tensoriais, encontramos uma maneira alternativa de raciocinar como a operação $U_f$ transforma $\\vert \\pi_1\\rangle$ em $\\vert \\pi_2\\rangle$ na análise acima:\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", "## Implementação no Qiskit\n", "\n", "Agora vamos ver como podemos implementar o algoritmo de Deutsch no Qiskit. Começaremos com uma verificação de versão e, em seguida, faremos as importações necessárias apenas para essa implementação.\n", "Para as implementações de outros algoritmos a seguir, realizaremos as importações necessárias separadamente para aumentar a modularidade.\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": [ "Primeiro, definiremos um circuito quântico que implementa uma porta de consulta para uma das quatro funções $f_1,$ $f_2,$ $f_3,$ ou $f_4$ de um bit para um bit descritas anteriormente. Como já mencionamos, a implementação de portas de consulta não é realmente uma parte do algoritmo de Deutsch em si; aqui, essencialmente, estamos apenas mostrando uma maneira de preparar a entrada, na forma de uma implementação de circuito de uma porta de consulta.\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": [ "Podemos ver a aparência de cada circuito usando o método `draw` . Aqui está o circuito para a função $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": [ "Em seguida, criaremos o circuito quântico real para o algoritmo de Deutsch, substituindo a porta de consulta por uma implementação de circuito quântico fornecida como argumento. Em breve, conectaremos um dos quatro circuitos definidos pela função `deutsch_function` que definimos anteriormente.\n", "As barreiras são incluídas para mostrar a separação visual entre a implementação da porta de consulta e o restante do 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": [ "Novamente, podemos ver a aparência do circuito usando o método `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": [ "Por fim, criaremos uma função que executa o circuito definido anteriormente uma vez e produz o resultado apropriado: \"constante\" ou \"balanceado\"\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": [ "Agora podemos executar o algoritmo de Deutsch em qualquer uma das quatro funções definidas acima.\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 }