FABLE.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## FABLE: Fast Approximate Quantum Circuits for Block-Encodings\n",
    "\n",
    "### MOTIVACIÓN\n",
    "*La codificación por bloques de matrices* se ha convertido en un *elemento esencial* de los algoritmos cuánticos derivados de la transformación cuántica de valores singulares. \n",
    "\n",
    "Se estudiará FABLE, un *método para generar circuitos cuánticos aproximados para codificaciones de bloque de matrices de manera rápida*. Son de estructura simple, comprimibles y esparcibles y están formulados directamente en términos de compuertas de uno y dos qubits.\n",
    "\n",
    "Se proporcionará un *teorema de compresión* que relaciona el umbral de compresión con el error en la codificación por bloques.\n",
    "\n",
    "### Introducción\n",
    "\n",
    "La transformación cuántica de valores singurales (QVST) generaliza la qubitización y el procesamiento de señales cuánticas. Proporciona un marco unificador que abarca muchos algoritmos cuánticos que ofrecen una aceleración sobre el mejor algoritmo clásico conocido.\n",
    "\n",
    "Todos los algoritmos cuánticos derivados de la QVST se basan en la noción de una codificación de bloque de alguna matriz $A$ que representa el problema en cuestión.\n",
    "\n",
    "Estas matrices son operadores no unitarios y no pueden ejecutarse directamente en una computadora cuántica que solo realiza evolución unitaria. ***Esta restricción se supera mediante la ampliación del espacio de Hilbert e incorporando el operador no unitario en un estado específico de los qubits ancilla***.\n",
    "\n",
    "La incorporación más utilizada es una codificación de bloque, donde la matriz del sistema $A$ se incorpora en el *bloque principal líder* de una matriz unitaria más grande que actúa en todo el espacio de Hilbert.\n",
    "\n",
    "\\begin{equation}\n",
    "U=\n",
    "\\begin{bmatrix}\n",
    "A & * \\\\\n",
    "* & *\n",
    "\\end{bmatrix}\n",
    "\\end{equation}\n",
    "\n",
    "Y se dice que U codifica en bloque a A.\n",
    "\n",
    "Hasta ahora, los resultados de complejidad basados en QVST se han formulado en términos de *complejidad de consulta*, es decir, cuántas consultas a $U$ se requieren para resolver el problema. \n",
    "\n",
    " FABLE es un algoritmo eficiente para generar circuitos cuánticos que codifican en bloque matrices arbitrarias con la precisión prescrita. Constan de un oráculo de consulta, implementada con rotaciones $R_{y}$ y $R_{z}$ de un qubit, y compuertas $CNOT$ de dos qubits, adicional a algunas compuertas *Hadamard* y *SWAP*. \n",
    "\n",
    " La complejidad de compuertas de un circuito FABLE para martrices generales y no estructuradas de orden $N$ está acotado por $O(N^2)$ compuertas. Esta complejidad escala exponencialmente en el número de qubits para matrices densas, ya que codificar una matriz no estructurada de dimensión exponencial es una tarea difícil.\n",
    "\n",
    " Los problemas más importantes suelen ser muy estructurados y, dado que los circuitos FABLE pueden ser comprimidos, las complejidades de compuerta se ven reducidas. Este proceso ***puede*** interpretarse como un esparcimiento del circuito y de la matriz.\n",
    "\n",
    " El algoritmo FABLE aplica una *transformación de Walsh-Hadamard* a los datos de la matriz y realiza el *esparcimiento en el dominio de Walsh-Hadamard*. Las matrices FABLE dispersas corresponden a matrices que contienen muchos ceros en este dominio, lo que ***no necesariamente se corresponde con la dispersión en el dominio original***.\n",
    "\n",
    " Los circuitos FABLE son adecuados para implementar algoritmos cuánticos derivados del QSVT en la era NISQ y demás.\n",
    "\n",
    " ### CODIFICACIÓN POR BLOQUES\n",
    " Se procederá a definir formalmente la codificación por bloques.\n",
    "\n",
    " Una codificación por bloques de una matriz no unitaria es la **inserción de una versión adecuadamente escalada** de esa matriz en el **bloque líder de una matriz unitaria más grande**\n",
    "\n",
    "Sean $a,n,m \\in \\mathbb{N}$, con $m=a+n$, una matriz unitaria $U$ de $m$ qubits es una $(\\alpha,a)$-codificación-en-bloque de un operador A de $n$ qubits si:\n",
    "\n",
    "\\begin{equation}\n",
    "\\tilde{A} = (\\langle 0 | ^ {\\otimes a} \\otimes I_{n})U(|0\\rangle^ {\\otimes a}\\otimes I_{n})\n",
    "\\end{equation}\n",
    "\n",
    "y $A= \\alpha \\tilde{A}$. $\\alpha$ corresponde al *factor de subnormalización* necesario para codificar matrices, y  $a$ al *número de qubits ancilla* usado en la codificación por bloques. \n",
    "\n",
    "Toda matriz unitaria es ya un trivial $(1,0)$-codificación-en-bloque de ella misma.\n",
    "\n",
    "Toda matriz no unitaria puede ser integrada en una $(\\lVert {A} \\lVert_{2},1)$-codificación-en-bloque. Esto no garantiza la existencia de una implementación eficiente de circuitos cuánticos.\n",
    "\n",
    "$\\tilde{A}$ es la traza parcial de $U$ sobre el estado cero del espacio ancilla. Esto parte el espacio de Hilbert: \n",
    "\n",
    "\\begin{equation}\n",
    " \\mathcal{H}_ {m} = \\mathcal{H}_{a} \\otimes \\mathcal{H} _ {n} \n",
    "\\end{equation}\n",
    "\n",
    "Dado un estado de $n$ qubits $| \\psi \\rangle \\in \\mathcal{H}_{n}$, para un $| \\phi \\rangle = |0\\rangle^  {\\otimes a} \\otimes |\\psi\\rangle$:\n",
    "\n",
    "\\begin{equation}\n",
    "U|\\phi \\rangle = |0\\rangle ^  {\\otimes a}  \\otimes \\tilde{A}|\\psi\\rangle + \\sqrt{1-\\lVert \\tilde{A} |\\psi\\rangle \\lVert ^ 2} |\\sigma ^\\perp \\rangle\n",
    "\\end{equation}\n",
    "\n",
    "con:\n",
    "\n",
    "\\begin{equation}\n",
    "(\\langle 0| ^  {\\otimes a} \\otimes I_{n}) |\\sigma ^\\perp \\rangle = 0\n",
    "\\end{equation}\n",
    "\n",
    "\\begin{equation}\n",
    "\\lVert |\\sigma ^\\perp \\rangle \\lVert = 1\n",
    "\\end{equation}\n",
    "\n",
    "$ |\\sigma ^\\perp \\rangle$ es el estado normalizado para el cual en registro ancilla tiene un estado ortogonal a $ |0 \\rangle ^  {\\otimes a}$.\n",
    "\n",
    "Con probabilidad $\\lVert \\tilde{A} |\\psi\\rangle \\lVert ^ 2$, una medida parcial de los qubits ancilla resulta en $0^  {\\otimes a}$ y los qubits señal están en el estado objetivo $\\dfrac{\\tilde{A} |\\psi\\rangle}{\\lVert \\tilde{A} |\\psi\\rangle \\lVert}$.\n",
    "\n",
    "Usando la *amplificación de amplitud*, el proceso debe ser repetido $\\dfrac{1}{\\lVert \\tilde{A} |\\psi\\rangle \\lVert}$ veces.\n",
    "\n",
    "Circuito cuántico abstracto para una $( \\alpha ,a)$ codificación-en-bloque, U, de A. El cable cuántico más bajo lleva los qubits de señal, el cable superior son los qubits ancilla:\n",
    "\n",
   "<img src=\"https://raw.githubusercontent.com/SebastianPaucar/Quantum-Computing-Notes/main/Images/F1.PNG\">",
    "\n",
    "Si el registro de ancilla es medido en el estado cero, el registro de señal se encuentra en el estado deseado $\\dfrac{\\tilde{A} |\\psi\\rangle}{\\lVert \\tilde{A} |\\psi\\rangle \\lVert}$.\n",
    "\n",
    "## Circuitos cuánticos para la codificación-en-bloques de matrices dispersas\n",
    "\n",
    "Se presentan en términos de oráculos de consulta.\n",
    "\n",
    "Estos oráculos proporcionan información sobre la posición y la descripción binaria de las entradas de la matriz.\n",
    "\n",
    "Estos oráculos suelen acompañarse de otro oráculo que brinda acceso a los datos de la matriz.\n",
    "\n",
    "***Propondemos un nuevo enfoque***, por lo que definiremos *de inmediato* una operación de consulta de matriz $O_A$ para dada una matriz $A$. \n",
    "\n",
    "Veremos cómo este oráculo puede esquematizarse en un circuito cuántico.\n",
    "\n",
    "**Definición:** Sean $a_{ij}$ las entradas de una matriz $A$ de orden $N = 2^n$, con $\\lVert a_{ij} \\lVert \\leq 1$. La matriz de consulta $O_A$ unitaria se aplica tal que:\n",
    "\n",
    "\\begin{equation}\n",
    "O_{A}|0\\rangle |i\\rangle |j\\rangle = (a_{ij}|0\\rangle + \\sqrt{1- \\lvert a_{ij} \\lvert ^2}|1\\rangle)|i\\rangle |j\\rangle\n",
    "\\end{equation}\n",
    "\n",
    "Con $|i\\rangle$ y $|j\\rangle$ estados base computacional de n qubits.\n",
    "\n",
    "Un circuito cuántico de alto nivel para codificar en bloque una matriz $A$ puede ser:\n",
    "\n",
    "<img src=\"https://raw.githubusercontent.com/SebastianPaucar/Quantum-Computing-Notes/main/Images/F2.PNG\">",
    "\n",
    "Donde $H^{\\otimes n}$ es una transformación de Hadamard de n qubits, el cual crea una superposición igual sobre los qubits de la fila.\n",
    "\n",
    "***Se recalca que*** Si los $n+1$ ancilla qubits son medidos en el estado cero, el registro de señal estará en el estado deseado $\\dfrac{\\tilde{A} |\\psi\\rangle}{\\lVert \\tilde{A} |\\psi\\rangle \\lVert}$.\n",
    "\n",
    "Deberemos también tener en cuenta la compuerta SWAP de $2n$ qubits:\n",
    "\n",
    "\\begin{equation}\n",
    "SWAP |i\\rangle |j\\rangle = |j\\rangle |i\\rangle\n",
    "\\end{equation}\n",
    "\n",
    "Por otro lado, se recalca que ***codificaremos toda la información sobre la matriz en un solo oráculo de consulta***.\n",
    "\n",
    "El siguiente teorema asegura que el circuito anteriormente dibujado es una codificación por bloques de la matriz objetivo $A$:\n",
    "\n",
    "**Teorema:** El circuito $U_{A}$ de la figura anterior es un $(1/2^n,n+1)$-codificación-en-bloque de una matriz $A$ de $n$ qubits ***si*** $\\lVert a_{ij} \\lVert \\leq 1$.\n",
    "\n",
    "**Aclaración:** Es decir, la figura:\n",
"\n",
"<img src=\"https://raw.githubusercontent.com/SebastianPaucar/Quantum-Computing-Notes/main/Images/F2.PNG\">",
   "\n",
    "Representa a $U_{A}$, por lo que:\n",
    "\n",
    "\\begin{equation}\n",
    "U_{A} = (I_1 \\otimes H^{\\otimes n} \\otimes I_n )(I_{1} \\otimes SWAP)O_{A}(I_1 \\otimes H^{\\otimes n} \\otimes I_n)\n",
    "\\end{equation}\n",
    "\n",
    "Y si $U_{A}$ es una $(1/2^n,n+1)$-codificación-en-bloque de una matriz $A$, **debe cumplirse la siguiente definición**:\n",
    "\n",
  
    "\\begin{equation}\n",
    "(\\dfrac{1}{2^n})A = (\\langle 0 | ^ {\\otimes a} \\otimes I_{n})U_{A}(|0\\rangle^ {\\otimes a}\\otimes I_{n})\n",
    "\\end{equation}\n",
    "\n",
    "Y se demuestra que la ecuación equivalente a tomar $|j\\rangle$ por la derecha y $\\langle i |$ por la izquierda:\n",
    "\n",
    "\\begin{equation}\n",
    "(\\dfrac{1}{2^n})a_{ij} = \\langle 0 |\\langle 0 | ^ {\\otimes n} \\langle i |U_{A}|0\\rangle^ {\\otimes n}|0\\rangle |j\\rangle\n",
    "\\end{equation}\n",
    "\n",
    "Se verifica, por lo que el teorema es correcto.\n",
    "\n",
    "Todos los elementos del circuito, ***a excepción de $O_{A}$*** pueden ser expresados en compuertas simples. \n",
    "\n",
    "La complejidad de las compuertas Hadamard y SWAP es polinomial en $n$.\n",
    "\n",
    "Probaremos que ***el oráculo $O_{A}$ puede implementarse con compuertas simples***. Comenzaremos probando matrices con ***entradas reales***.\n",
    "\n",
    "Si $A$ es real, para dados indices fila y columna $i$ y $j$, $O_{A}$ actúa sobre el estado $|0\\rangle $ del primer qubit como una compuerta $R_{y}$ con ángulo:\n",
    "\n",
    "\\begin{equation}\n",
    "\\theta_{ij} = \\arccos(a_{ij})\n",
    "\\end{equation}\n",
    "\n",
    "Es decir:\n",
    "\n",
    "<img src=\"https://raw.githubusercontent.com/SebastianPaucar/Quantum-Computing-Notes/main/Images/RY.PNG\">",
    "\n",
    "Así, $O_{A}$ guarda la siguiente estructura para matrices reales:\n",
    "\n",
    "<img src=\"https://raw.githubusercontent.com/SebastianPaucar/Quantum-Computing-Notes/main/Images/OA_REAL.PNG\">",
    "\n",
    "Donde $c_{ij} = \\cos{\\theta_{ij}}$ y $s_{ij} = \\sin{\\theta_{ij}}$.\n",
    "\n",
    "***Una primera implementación*** de $O_{A}$ para $A$ real de orden $N$ usa $N^2$ compuertas $R_{y}$ multicontroladas.\n",
    "\n",
    "Usaremos $C^n(R_{y})$ para compuertas $R_{y}$ con $n$ qubits de control.\n",
    "\n",
    "Como se construyó $O_{A}$, se usa $C^n(R_{y})$ para cada entrada $a_{ij}$, donde los qubits de control codifican los índices fila y columna $|i\\rangle $ y $|j\\rangle $ de la entrada correspondiente.\n",
    "\n",
    "Para codificar una matriz de orden 2 usando 3 qubits y 4 compuertas $C^2(R_{y})$:\n",
    "\n",
  "<img src=\"https://raw.githubusercontent.com/SebastianPaucar/Quantum-Computing-Notes/main/Images/F3.PNG\">",
    "\n",
    "Donde los ángulos están dados según la definición de $\\theta_{ij}$. \n",
    "\n",
    "La mayor desventaja de este enfoque es que requiere $N^2$ compuertas  $C^{2n}(R_{y})$ para el óraculo $O_{A}$ para $A$ real de orden $N$. \n",
    "\n",
    "Adicionalmente, cada compuerta $C^{2n}(R_{y})$ requiere $O(N^2)$ compuertas de 1 y 2 qubits.\n",
    "\n",
    "Esto eleva la complejidad del circuito a $O(N^4)$. Resultado cuadráticamente peor que el costo de representación clásica.\n",
    "\n",
    "Se propondrá una ***reducción cuadrática de complejidad de puertas con la implementación FABLE*** de circuitos de codificación-en-bloques.\n",
    "\n"
   ]
  }
 ],
 "metadata": {
  "language_info": {
   "name": "python"
  },
  "orig_nbformat": 4
 },
 "nbformat": 4,
 "nbformat_minor": 2
}