{ "cells": [ { "cell_type": "markdown", "id": "76d7b924", "metadata": {}, "source": [ "---\n", "title: \"algoritmo de Grover\"\n", "description: \"Use o algoritmo de Grover para pesquisar um banco de dados não estruturado com um aumento de velocidade quadrático.\"\n", "---\n", "\n", "{/* cspell:ignore fontsize */}\n", "\n", "\n", "\n", "# algoritmo de Grover\n", "\n", "*Estimativa de tempo de execução: menos de um minuto em um processador Eagle r3 (NOTA: Trata-se apenas de uma estimativa. (O tempo de execução pode variar.)*\n", "\n" ] }, { "cell_type": "markdown", "id": "88aa4204", "metadata": {}, "source": [ "\n", "\n", "## Resultados do aprendizado\n", "\n", "Ao concluir este tutorial, você deverá compreender as seguintes informações:\n", "\n", "* Como construir oráculos de Grover que marquem um ou mais estados da base computacional\n", "* Como usar a `grover_operator()` função da biblioteca de circuitos do Qiskit\n", "* Como determinar o número ideal de iterações de Grover para um determinado problema\n", "* Como executar o algoritmo de Grover usando a primitiva Sampler do `Qiskit Runtime`\n", "\n", "\n", "\n", "## Pré-requisitos\n", "\n", "Recomenda-se que você se familiarize com estes tópicos:\n", "\n", "* [Fundamentos dos algoritmos quânticos: o algoritmo de Grover](/learning/courses/fundamentals-of-quantum-algorithms/grover-algorithm/introduction)\n", "* [Noções básicas de informação quântica](/learning/courses/basics-of-quantum-information)\n", "\n", "\n", "\n", "## Segundo plano\n", "\n", "A amplificação de amplitude é um algoritmo quântico de uso geral, ou sub-rotina, que pode ser utilizado para obter um aumento de velocidade quadrático em relação a alguns algoritmos clássicos. [O algoritmo de Grover](https://arxiv.org/abs/quant-ph/9605043) foi o primeiro a demonstrar essa aceleração em problemas de busca não estruturados. A formulação de um problema de busca de Grover requer uma função oráculo que identifique um ou mais estados da base computacional como aqueles que nos interessam encontrar, e um circuito de amplificação que aumente a amplitude dos estados identificados, suprimindo, consequentemente, os demais estados.\n", "\n", "Aqui, demonstramos como construir oráculos de Grover e usar o [`grover_operator()`](/docs/api/qiskit/qiskit.circuit.library.grover_operator) da biblioteca de circuitos Qiskit para configurar facilmente uma instância de pesquisa de Grover. A primitiva de tempo de execução `Sampler` permite a execução contínua dos circuitos Grover.\n", "\n" ] }, { "cell_type": "markdown", "id": "5bbba268", "metadata": {}, "source": [ "\n", "\n", "## Requisitos\n", "\n", "Antes de iniciar este tutorial, certifique-se de que os seguintes itens estejam instalados:\n", "\n", "* Qiskit SDK v2.0 ou posterior, com suporte [à visualização](/docs/api/qiskit/visualization)\n", "* Qiskit Runtime v0.22 ou posterior (`pip install qiskit-ibm-runtime`)\n", "\n" ] }, { "cell_type": "markdown", "id": "bfccad15", "metadata": {}, "source": [ "\n", "\n", "## Instalação\n", "\n" ] }, { "cell_type": "code", "execution_count": 1, "id": "e2cb0472", "metadata": {}, "outputs": [], "source": [ "# Built-in modules\n", "import math\n", "\n", "# Imports from Qiskit\n", "from qiskit import QuantumCircuit\n", "from qiskit.circuit.library import grover_operator, MCMTGate, ZGate\n", "from qiskit.visualization import plot_distribution\n", "from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager\n", "\n", "# Imports from Qiskit Runtime\n", "from qiskit_ibm_runtime import QiskitRuntimeService\n", "from qiskit_ibm_runtime import SamplerV2 as Sampler\n", "\n", "\n", "def grover_oracle(marked_states):\n", " \"\"\"Build a Grover oracle for multiple marked states\n", "\n", " Here we assume all input marked states have the same number of bits\n", "\n", " Parameters:\n", " marked_states (str or list): Marked states of oracle\n", "\n", " Returns:\n", " QuantumCircuit: Quantum circuit representing Grover oracle\n", " \"\"\"\n", " if not isinstance(marked_states, list):\n", " marked_states = [marked_states]\n", " # Compute the number of qubits in circuit\n", " num_qubits = len(marked_states[0])\n", "\n", " qc = QuantumCircuit(num_qubits)\n", " # Mark each target state in the input list\n", " for target in marked_states:\n", " # Flip target bit-string to match Qiskit bit-ordering\n", " rev_target = target[::-1]\n", " # Find the indices of all the '0' elements in bit-string\n", " zero_inds = [\n", " ind\n", " for ind in range(num_qubits)\n", " if rev_target.startswith(\"0\", ind)\n", " ]\n", " # Add a multi-controlled Z-gate with pre- and post-applied X-gates (open-controls)\n", " # where the target bit-string has a '0' entry\n", " if zero_inds:\n", " qc.x(zero_inds)\n", " qc.compose(MCMTGate(ZGate(), num_qubits - 1, 1), inplace=True)\n", " if zero_inds:\n", " qc.x(zero_inds)\n", " return qc" ] }, { "cell_type": "markdown", "id": "77e41aba", "metadata": {}, "source": [ "\n", "\n", "## Exemplo de simulador em pequena escala\n", "\n", "Nesta seção, vamos acompanhar cada etapa do algoritmo de Grover em pequena escala, utilizando um simulador local, antes de executar o mesmo problema em hardware quântico real.\n", "\n" ] }, { "cell_type": "markdown", "id": "0c0fb667", "metadata": {}, "source": [ "\n", "\n", "### Passo 1: Mapear entradas clássicas para um problema quântico\n", "\n", "O algoritmo de Grover requer um [oráculo](/learning/modules/computer-science/grovers#introduction) que especifique um ou mais estados da base computacional marcados, sendo que “marcado” significa um estado com uma fase de -1. Uma porta de Z controlado, ou sua generalização multicontrolada sobre qubits d $N$, marca o estado de $2^{N}-1$ (`'1'`\\*sequência de bits $N$ ). Para marcar estados de base com um ou mais `'0'` na representação binária, é necessário aplicar portas X nos qubits correspondentes antes e depois da porta Z controlada, o que equivale a aplicar um comando de controle aberto nesse qubit. No código a seguir, definimos um oráculo que identifica um ou mais estados de base de entrada definidos por meio de sua representação em cadeia de bits. A `MCMT` porta é utilizada para implementar a porta Z multicontrolada.\n", "\n" ] }, { "attachments": {}, "cell_type": "markdown", "id": "bca14740", "metadata": {}, "source": [ "\n", "\n", "### Instanciação específica de Grover\n", "\n", "Agora que temos a função de oráculo, podemos definir uma instância específica da pesquisa de Grover. Neste exemplo, marcaremos dois estados computacionais dentre os oito disponíveis em um espaço computacional de três qubits:\n", "\n" ] }, { "cell_type": "code", "execution_count": 2, "id": "c150298f", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\"Output" ] }, "execution_count": 2, "metadata": {}, "output_type": "execute_result" } ], "source": [ "marked_states = [\"011\", \"100\"]\n", "\n", "oracle = grover_oracle(marked_states)\n", "oracle.draw(output=\"mpl\", style=\"iqp\")" ] }, { "attachments": {}, "cell_type": "markdown", "id": "25487b93", "metadata": {}, "source": [ "\n", "\n", "### Operador Grover\n", "\n", "O Qiskit `grover_operator()` incorporado pega um circuito de oráculo e retorna um circuito composto pelo próprio circuito do oráculo e um circuito que amplifica os estados marcados pelo oráculo. Aqui, usamos o método `decompose()` o circuito para ver as portas dentro do operador:\n", "\n" ] }, { "cell_type": "code", "execution_count": 3, "id": "283d5265", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\"Output" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "grover_op = grover_operator(oracle)\n", "grover_op.decompose().draw(output=\"mpl\", style=\"iqp\")" ] }, { "attachments": {}, "cell_type": "markdown", "id": "83c34dc9", "metadata": {}, "source": [ "As aplicações repetidas desse circuito `grover_op` amplificam os estados marcados, tornando-os as cadeias de bits mais prováveis na distribuição de saída do circuito. Há um número ideal desses aplicativos que é determinado pela proporção de estados marcados em relação ao número total de estados computacionais possíveis:\n", "\n" ] }, { "cell_type": "code", "execution_count": 4, "id": "f4c3d4b5", "metadata": {}, "outputs": [], "source": [ "optimal_num_iterations = math.floor(\n", " math.pi\n", " / (4 * math.asin(math.sqrt(len(marked_states) / 2**grover_op.num_qubits)))\n", ")" ] }, { "attachments": {}, "cell_type": "markdown", "id": "e06c8238", "metadata": {}, "source": [ "\n", "\n", "### Circuito Grover completo\n", "\n", "Um experimento completo de Grover começa com uma porta Hadamard em cada qubit, criando uma superposição uniforme de todos os estados da base computacional, seguida do operador de Grover (`grover_op`) repetido o número ideal de vezes. Aqui, usamos o método `QuantumCircuit.power(INT)` para aplicar repetidamente o operador de Grover.\n", "\n" ] }, { "cell_type": "code", "execution_count": 5, "id": "4933ae44", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\"Output" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "qc = QuantumCircuit(grover_op.num_qubits)\n", "# Create even superposition of all basis states\n", "qc.h(range(grover_op.num_qubits))\n", "# Apply Grover operator the optimal number of times\n", "qc.compose(grover_op.power(optimal_num_iterations), inplace=True)\n", "# Measure all qubits\n", "qc.measure_all()\n", "qc.draw(output=\"mpl\", style=\"iqp\")" ] }, { "cell_type": "markdown", "id": "0649c854", "metadata": {}, "source": [ "\n", "\n", "### Etapa 2: Otimizar o problema para execução em hardware quântico\n", "\n", "Para a simulação em pequena escala, compilamos o circuito sem direcioná-lo a um hardware específico.\n", "\n" ] }, { "cell_type": "code", "execution_count": 6, "id": "c4f67f35", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\"Output" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "pm = generate_preset_pass_manager(optimization_level=3)\n", "circuit_isa = pm.run(qc)\n", "circuit_isa.draw(output=\"mpl\", idle_wires=False, style=\"iqp\")" ] }, { "cell_type": "markdown", "id": "4e0d4d90", "metadata": {}, "source": [ "\n", "\n", "### Passo 3: Execute usando Qiskit primitives\n", "\n", "A amplificação de amplitude é um problema de amostragem adequado para ser executado com a [`SamplerV2`](/docs/api/qiskit-ibm-runtime/sampler-v2) primitiva. Aqui, utilizamos o `StatevectorSampler` de `qiskit.primitives` para simulação local.\n", "\n" ] }, { "cell_type": "code", "execution_count": 7, "id": "7666ad7c", "metadata": {}, "outputs": [], "source": [ "from qiskit.primitives import StatevectorSampler\n", "\n", "sampler = StatevectorSampler()\n", "result = sampler.run([circuit_isa], shots=10_000).result()\n", "dist = result[0].data.meas.get_counts()" ] }, { "cell_type": "markdown", "id": "5c8263c7", "metadata": {}, "source": [ "\n", "\n", "### Etapa 4: Pós-processamento e retorno do resultado no formato clássico desejado\n", "\n" ] }, { "cell_type": "code", "execution_count": 8, "id": "a5ef9913", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\"Output" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "plot_distribution(dist)" ] }, { "cell_type": "markdown", "id": "2b45b2ee", "metadata": {}, "source": [ "\n", "\n", "## Exemplo de hardware\n", "\n" ] }, { "cell_type": "markdown", "id": "5fb22680", "metadata": {}, "source": [ "\n", "\n", "### Etapas 1 a 4\n", "\n", "O algoritmo de Grover é, em essência, um algoritmo tolerante a falhas — as portas Z multicontroladas, que constituem o núcleo do oráculo e do operador de difusão, resultam em profundidades de porta de dois qubits que aumentam muito rapidamente com o número de qubits (como mostraremos na próxima seção). Isso significa que o algoritmo não se adapta bem ao hardware atual, que apresenta ruídos. Por esse motivo, demonstramos a execução em hardware na mesma escala reduzida do exemplo do simulador acima, em vez de tentarmos resolver um problema de maior dimensão.\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "id": "be3c3d9e", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\"Output" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# -------------------------Step 1-------------------------\n", "marked_states = [\"011\", \"100\"]\n", "\n", "oracle = grover_oracle(marked_states)\n", "grover_op = grover_operator(oracle)\n", "\n", "optimal_num_iterations = math.floor(\n", " math.pi\n", " / (4 * math.asin(math.sqrt(len(marked_states) / 2**grover_op.num_qubits)))\n", ")\n", "\n", "qc = QuantumCircuit(grover_op.num_qubits)\n", "qc.h(range(grover_op.num_qubits))\n", "qc.compose(grover_op.power(optimal_num_iterations), inplace=True)\n", "qc.measure_all()\n", "\n", "# -------------------------Step 2-------------------------\n", "service = QiskitRuntimeService()\n", "backend = service.least_busy(\n", " operational=True, simulator=False, min_num_qubits=127\n", ")\n", "\n", "target = backend.target\n", "pm = generate_preset_pass_manager(target=target, optimization_level=3)\n", "circuit_isa = pm.run(qc)\n", "\n", "# -------------------------Step 3-------------------------\n", "sampler = Sampler(mode=backend)\n", "sampler.options.default_shots = 10_000\n", "sampler.options.environment.job_tags = [\"TUT-GA\"]\n", "result = sampler.run([circuit_isa]).result()\n", "dist = result[0].data.meas.get_counts()\n", "\n", "# -------------------------Step 4-------------------------\n", "plot_distribution(dist)" ] }, { "cell_type": "markdown", "id": "12e72eab", "metadata": {}, "source": [ "\n", "\n", "## Discussão: Escalonamento da profundidade de portas de dois qubits\n", "\n", "Uma das principais razões pelas quais o algoritmo de Grover é considerado um algoritmo tolerante a falhas é o rápido aumento da profundidade da porta de dois qubits do circuito à medida que o número de qubits aumenta. A porta Z multicontrolada, que está no centro tanto do oráculo quanto do operador de difusão, decompõe-se em um número de portas de dois qubits que cresce exponencialmente com o número de qubits de controle. Somado ao fato de que o número ideal de iterações de Grover cresce na proporção de $O(\\sqrt{2^n})$, a profundidade total de dois qubits rapidamente se torna impraticável para hardware sujeito a ruídos.\n", "\n", "A seguir, construímos circuitos de Grover para um número crescente de qubits, os transpilamos e representamos graficamente a profundidade da porta de dois qubits resultante para ilustrar essa escalabilidade.\n", "\n" ] }, { "cell_type": "code", "execution_count": 10, "id": "abc6b43c", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "n=3: optimal_iters=2, 2Q depth=39\n", "n=4: optimal_iters=3, 2Q depth=111\n", "n=5: optimal_iters=4, 2Q depth=466\n", "n=6: optimal_iters=6, 2Q depth=1646\n", "n=7: optimal_iters=8, 2Q depth=3550\n", "n=8: optimal_iters=12, 2Q depth=7989\n", "n=9: optimal_iters=17, 2Q depth=14824\n" ] }, { "data": { "text/plain": [ "\"Output" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "import matplotlib.pyplot as plt\n", "\n", "num_qubits_list = list(range(3, 10))\n", "two_q_depths = []\n", "backend = service.least_busy(\n", " operational=True, simulator=False, min_num_qubits=127\n", ")\n", "for n in num_qubits_list:\n", " # Mark a single state for simplicity\n", " marked = [\"1\" * n]\n", " oracle_n = grover_oracle(marked)\n", " grover_op_n = grover_operator(oracle_n)\n", "\n", " # Optimal number of iterations\n", " num_iters = math.floor(\n", " math.pi / (4 * math.asin(math.sqrt(len(marked) / 2**n)))\n", " )\n", "\n", " # Build the full Grover circuit\n", " qc_n = QuantumCircuit(n)\n", " qc_n.h(range(n))\n", " qc_n.compose(grover_op_n.power(num_iters), inplace=True)\n", " qc_n.measure_all()\n", "\n", " # Transpile to a basis gate set and count 2Q depth\n", " pm_n = generate_preset_pass_manager(backend=backend, optimization_level=3)\n", " qc_transpiled = pm_n.run(qc_n)\n", "\n", " # Compute depth restricted to 2-qubit operations\n", " depth_2q = qc_transpiled.depth(lambda x: x.operation.num_qubits == 2)\n", "\n", " two_q_depths.append(depth_2q)\n", " print(f\"n={n}: optimal_iters={num_iters}, 2Q depth={depth_2q}\")\n", "\n", "# Plot\n", "fig, ax = plt.subplots(figsize=(8, 5))\n", "ax.plot(\n", " num_qubits_list,\n", " two_q_depths,\n", " \"o-\",\n", " linewidth=2,\n", " markersize=8,\n", " color=\"#6929C4\",\n", ")\n", "ax.set_xlabel(\"Number of qubits\", fontsize=13)\n", "ax.set_ylabel(\"Two-qubit gate depth\", fontsize=13)\n", "ax.set_title(\"Grover's algorithm: 2Q depth scaling\", fontsize=14)\n", "ax.set_yscale(\"log\")\n", "ax.grid(True, alpha=0.3)\n", "ax.set_xticks(num_qubits_list)\n", "plt.tight_layout()\n", "plt.show()" ] }, { "cell_type": "markdown", "id": "f3ddda55", "metadata": {}, "source": [ "Como mostra o gráfico, a profundidade da porta de dois qubits cresce extremamente rápido com o número de qubits — aproximadamente de forma exponencial. Isso torna o algoritmo de Grover impraticável no hardware quântico atual, sujeito a ruídos, exceto para problemas de dimensões muito pequenas. O algoritmo continua sendo um alvo importante para futuros computadores quânticos tolerantes a falhas, nos quais a correção de erros permitirá que circuitos complexos sejam executados de forma confiável.\n", "\n" ] }, { "cell_type": "markdown", "id": "cf6e8fe6", "metadata": {}, "source": [ "\n", "\n", "## Próximas etapas\n", "\n", "\n", " Se você achou este trabalho interessante, talvez se interesse pelo seguinte material:\n", "\n", " * [Biblioteca de circuitos do Qiskit: `grover_operator()` Referência da API](/docs/api/qiskit/qiskit.circuit.library.grover_operator)\n", " * [O tutorial](/docs/tutorials/quantum-approximate-optimization-algorithm) sobre QAOA e [a aula sobre QAOA em escala de utilidade](/learning/courses/quantum-computing-in-practice/utility-scale-qaoa) apresentam exemplos de otimização com computadores quânticos no curto prazo\n", " * Para uma análise mais aprofundada dos algoritmos de curto prazo, consulte o curso [“Computação quântica na prática”](/learning/courses/quantum-computing-in-practice)\n", "\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" }, "hours": 1, "qpuSeconds": 60 }, "nbformat": 4, "nbformat_minor": 5 }