Hackathon_V_Workshop_de_Computação_Quântica_UFSC.ipynb

{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "view-in-github"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/marcotulio956/quantum.compWS/blob/master/Hackathon_V_Workshop_de_Computa%C3%A7%C3%A3o_Qu%C3%A2ntica_UFSC.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "2sZxD-WzHVw7"
      },
      "source": [
        "# [Hackathon - V Workshop de Computação Quântica - UFSC](https://workshop-cq.ufsc.br/2022/#hackathon)\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "59P0dM44H9Br"
      },
      "source": [
        "----------------\n",
        "Exemplo de implementação da sub-rotina quântica do algoritmo de fatoração de Shor."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 1,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "dTm2HP2TrSGs",
        "outputId": "dc82b4a1-9046-4eca-b5f2-75fcc70e857a"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "Ket 0.4.1.post1\n"
          ]
        }
      ],
      "source": [
        "#!pip install git+https://gitlab.com/evandro-crr/shor-ket.git -q\n",
        "!ket --version\n",
        "from ket import *"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 2,
      "metadata": {
        "id": "hof54zYztyOY"
      },
      "outputs": [],
      "source": [
        "def quantum_subroutine_example(N, x):\n",
        "    from ket.lib import qft\n",
        "    from ket.plugins import pown\n",
        "    from functools import reduce\n",
        "    from math import gcd\n",
        "\n",
        "    n = N.bit_length()\n",
        "\n",
        "    def subroutine():\n",
        "        reg1 = H(quant(n))\n",
        "        reg2 = pown(x, reg1, N) # Lembre que não é premitido usar o plugin pown\n",
        "        adj(qft, reg1)\n",
        "        return measure(reg1).value\n",
        "\n",
        "    r = reduce(gcd, [subroutine() for _ in range(n)])\n",
        "    return 2**n//r"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "V8hT-N1iIMDV"
      },
      "source": [
        "-------------"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "### Solução Desenvolvida "
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 3,
      "metadata": {},
      "outputs": [],
      "source": [
        "from QSet import *\n",
        "\n",
        "# examples\n",
        "# QSet.gcd(8,4)\n",
        "# QSet.shors_quantum_subroutine(4,3)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 4,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "K-_t4KWiIRoK",
        "outputId": "8215618f-885f-4c72-e898-c815ebdd8536"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "Shor's algorithm: 205193=449x457\t(1min 23.13s; 08/10/2022 13:53:55)\n"
          ]
        }
      ],
      "source": [
        "# Esta célula será usada para avaliar sua solução\n",
        "from shor import shor\n",
        "\n",
        "N = 449 * 457\n",
        "\n",
        "#p = shor(N, quantum_subroutine_example, quantum=True, verbose=True)\n",
        "p = shor(N, QSet.shors_quantum_subroutine, quantum=True, verbose=True)\n",
        "q = N//p\n",
        "assert(N == p * q)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 5,
      "metadata": {
        "id": "x0Db6LyhIzoG"
      },
      "outputs": [],
      "source": [
        "from shor import is_prime\n",
        "assert(is_prime(p) and is_prime(q))"
      ]
    }
  ],
  "metadata": {
    "colab": {
      "collapsed_sections": [],
      "include_colab_link": true,
      "provenance": [],
      "toc_visible": true
    },
    "kernelspec": {
      "display_name": "Python 3.10.5 64-bit",
      "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.10.5"
    },
    "vscode": {
      "interpreter": {
        "hash": "bebf9730dc43cfbc35fb329a82a69476f49cde6de038a2bbfc26f12404ad85fb"
      }
    }
  },
  "nbformat": 4,
  "nbformat_minor": 0
}