FABLE_CODING.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Circuitos FABLE para codificaciones-por-bloque\n",
    "\n",
    "### Oráculos de consulta para matrices reales\n",
    "\n",
    "$O_A$ para una matriz real $A$ de orden 2:\n",
    "\n",
 "<img src=\"https://raw.githubusercontent.com/SebastianPaucar/Quantum-Computing-Notes/main/Images/FABLE_IMP_1.PNG\">",
    "\n",
    "Donde los ángulos $\\hat{\\theta}_{i}$ son calculados a partir de $A$, como se verá.\n",
    "\n",
    "Ahora bien, dada las propiedades de $R_y$:\n",
    "\n",
    "\\begin{equation}\n",
    "R_y(\\theta_{i})R_y(\\theta_{j})=R_y(\\theta_{i}+\\theta_{j})\n",
    "\\end{equation}\n",
    "\n",
    "\\begin{equation}\n",
    "XR_{y}(\\theta)X = R_{y}(-\\theta)\n",
    "\\end{equation}\n",
    "\n",
    "Por lo que, de la figura anterior, se encuentra:\n",
"\n",
 "<img src=\"https://raw.githubusercontent.com/SebastianPaucar/Quantum-Computing-Notes/main/Images/FABLE_IMP_2.PNG\">",
    "\n",
    "Así, el ángulo de rotación depende del estado de los dos últimos qubits de control.\n",
    "\n",
    "Para implementar $O_A$ con ángulos $\\theta_{ij}=\\arccos{a_{ij}}$, debemos vectorizar a $A$ tal que $\\text{vec}(A)_{i+j,N} = a_{ij}$ para obtener los $\\theta_{k}$.\n",
    "\n",
    "Del sistema de ecuaciones anterior, tenemos:\n",
    "\n",
 "<img src=\"https://raw.githubusercontent.com/SebastianPaucar/Quantum-Computing-Notes/main/Images/FABLE_IMP_3.PNG\">",
    "\n",
    "Esto es:\n",
"\n",
"<img src=\"https://raw.githubusercontent.com/SebastianPaucar/Quantum-Computing-Notes/main/Images/FABLE_IMP_4.PNG\">",
    "\n",
    "Donde $\\hat{H}= [1 \\ 1;-1 \\ 1]$ es un escalar múltiplo de la compuerta Hadamard y $P_G$ es una matriz de permutación que transforma *el orden binario* al *Orden de código gray*.\n",
    "\n",
    "Este algoritmo generaliza $O_A$ para matrices $A$ de orden general $N$. El circuito correspondiente consiste de una secuencia de compuertas de longitud $2^{2n}$ que alterna entre compuertas $R_{y}$ y $CNOT$.\n",
    "\n",
    "Los $R_y$ solo actúan en el primer qubit, que es *target* del $CNOT$ siguiente.\n",
    "\n",
    "**En general**, el qubit de control del $l$-ésimo $CNOT$ es determinado por el bit donde el $l$-ésimo y $l+1$-ésimo *código gray* difieren.\n",
    "\n",
    "Para un oráculo $O_{A}$ con ángulos $\\theta_{k}$, con $k$ de 0 a $2^n$ ($\\boldsymbol{\\theta}$). Los ángulos de las compuertas $R_y$ en el *circuito cuántico*, $\\boldsymbol{\\hat{\\theta}}$ es tal que:\n",
    "\n",
    "\\begin{equation}\n",
    "(\\hat{H}^{\\otimes 2n}P_{G}) \\boldsymbol{\\hat{\\theta}} = \\boldsymbol{\\theta}\n",
    "\\end{equation}\n",
    "\n",
    "Resoluble por un algoritmo clásico usando la transformada rápida de Walsh-Hadamard. También usado en la ***implementación de FABLE***.\n",
    "\n",
    "Esta estructura de circuito es conocida como una ***rotación $R_y$ uniformemente controlada***, porque rota el qubit *target* un ángulo diferente por cada cadena de bits en el registro de control.\n",
    "\n",
    "Se usa la siguiente notación para rotaciones uniformemente controladas en la implementación de $O_A$:\n",
    "\n",
"<img src=\"https://raw.githubusercontent.com/SebastianPaucar/Quantum-Computing-Notes/main/Images/FABLE_IMP_5.PNG\">",
    "\n",
    "Sujeta a una complejidad de $O(N^2)$ para $A$ de orden $N$, donde se usan $N^2$ CNOT y $N^2$ $R_y$ de un solo qubit.\n",
    "\n",
    "Esto alcanza la misma complejidad asintótica de compuertas que se requiere clásicamente para almacenar los datos y es óptimo para datos no estructurados.\n",
    "\n",
    "\n",
    "### Oráculos de consulta para matrices complejas\n",
    "\n",
    "Para $A$ compleja, codificamos los elementos de matriz como productos de $R_y$ y $R_z$:\n",
    "\n",
    "\\begin{equation}\n",
    "a_{ij} = \\lvert a_{ij} \\lvert e^{i \\alpha_{ij}}\n",
    "\\end{equation}\n",
    "\n",
    "$O_A$ actúa en el estado $| 0 \\rangle$ del primer qubit como un producto de $R_y$ y $R_z$, con:\n",
    "\n",
    "\\begin{equation}\n",
    "\\theta_{ij} =\\arccos{ \\lvert a_{ij} \\lvert }\n",
    "\\end{equation}\n",
    "\n",
    "\\begin{equation}\n",
    "\\phi_{ij}=-\\alpha_{ij} \n",
    "\\end{equation}\n",
    "\n",
    "Esto es:\n",
    "\n",
"<img src=\"https://raw.githubusercontent.com/SebastianPaucar/Quantum-Computing-Notes/main/Images/FABLE_IMP_6.PNG\">",
    "\n",
    "Extendiendo a definir $R_z$ uniformemente controlada. Así, para matrices complejas, se tiene la implementación de $O_A$:\n",
    "\n",
"<img src=\"https://raw.githubusercontent.com/SebastianPaucar/Quantum-Computing-Notes/main/Images/FABLE_IMP_7.PNG\">",
    "\n",
    "Donde $R_y$ y $R_z$ dotan la magnitud y fase de los elementos de matriz.\n",
    "\n",
    "Los ángulos de rotación pueden ser calculados mediante:\n",
    "\n",
    "\n",
    "Usando la magnitud y fase de los datos de la matriz.\n",
    "\n",
    "La complejidad de compuerta de $O_A$ para matrices complejas es el doble que para el caso real.\n",
    "\n",
    "Así, los **circuitos FABLE completos para el caso real y complejo**, con $O_A$ implementado como rotaciones uniformemente controladas son:\n",
    "\n",
"<img src=\"https://raw.githubusercontent.com/SebastianPaucar/Quantum-Computing-Notes/main/Images/FABLE_IMP_8.PNG\">",
    "\n",
    "### Codificación-en-bloque aproximada y compresión de circuitos\n",
    "\n",
    "Anteriormente solo consideramos implementaciones exactas de $O_A$, las cuales resultan en codificaciones-en-bloque exactas.\n",
    "\n",
    "Mostraremos cómo comprimir circuitos FABLE y cuál es el error de aproximación resultante de la codificación de bloques.\n",
    "\n",
    "#### Codificación-en-bloque aproximada\n",
    "\n",
    "Usaremos la siguiente definición extendida para codificaciones-en-bloque aproximadas para matrices objetivo hasta una precisión de $\\epsilon$.\n",
    "\n",
    "**Definición:** Sean $a,n,m $ naturales con $m=a+n$ y $\\epsilon$ real positivo. Un $m$-qubit unitario U es un $(\\alpha,a,\\epsilon)$-codificación en bloque de un operador $n$-qubit A si:\n",
    "\n",
    "\\begin{equation}\n",
    "\\bar{A} = (\\langle 0|^{\\otimes a} \\otimes I_{n})U(|0\\rangle^{\\otimes a} \\otimes I_{n})\n",
    "\\end{equation}\n",
    "\n",
    "Donde $\\lVert A- \\alpha \\bar{A} \\lVert _{2}$, $\\lVert \\hat{A} \\lVert _{2}$ y $\\lVert A \\lVert \\leq \\alpha + \\epsilon$, y $\\epsilon$ es el error absoluto de la codificación-en-bloque.\n",
    "\n",
    "#### Compresión y esparcificación de un circuito FABLE\n",
    "\n",
    "Considere el algoritmo de compresión de circuito.\n",
    "\n",
"<img src=\"https://raw.githubusercontent.com/SebastianPaucar/Quantum-Computing-Notes/main/Images/FABLE_IMP_9.PNG\">",
    "\n",
    "Que corresponde a una compuerta de rotación uniformemente controlada con 8 ángulos. Se ha omitido las etiquetas de las compuertas de rotación.\n",
    "\n",
    "Este algoritmo de compresión usa el umbral de corte $\\delta_{c}$ real positivo. $\\hat{\\theta}_{i}<\\delta_{c}$ se desprecian.\n",
    "\n",
    "Esto es, si $\\bar{\\theta}_{k\\in[2;6]} \\leq \\delta_{c}$, se remueven las rotaciones de un solo qubit son removidas, así:\n",
    "\n",
"<img src=\"https://raw.githubusercontent.com/SebastianPaucar/Quantum-Computing-Notes/main/Images/FABLE_IMP_9.PNG\">",
    "\n",
    "Y dado que todo par consecutivo $CNOT$ con mismo qubit de control se cancelan entre sí, se tiene:\n",
    "\n",
"<img src=\"https://raw.githubusercontent.com/SebastianPaucar/Quantum-Computing-Notes/main/Images/FABLE_IMP_10.PNG\">",
    "\n",
    "Que corresponde a un circuito comprimido.\n",
    "\n",
    "***El algoritmo de compresión de circuito*** consiste en dos etapas:\n",
    "\n",
    "<ul>\n",
    "<li> Eliminar las rotaciones para ángulos $\\hat{\\theta}_{i} < \\delta _{c}$ en $\\boldsymbol{\\hat{\\theta}}$ del circuito.</li>\n",
    "<li>Comprobar paridad de qubits de control de cada serie $CNOT$ consecutiva. Se mantiene $CNOT$ para el $i$-ésimo qubit de control si hay una cantidad impar de $CNOT$ para este qubit de control. De lo contrario, se eliminan todas las compuerta $CNOT$.</li>\n",
    "</ul>\n",
    "\n",
    "Este procedimiento se considera una *esparcificación* de datos, pues representa la matriz codificada en bloques con menos de $N^2$ parámetros. \n",
    "\n",
    "Generalmente, esta esparcificación en $\\boldsymbol{\\hat{\\theta}}$ se da después de la transformación de Walsh-Hadamard, no implicando que $\\boldsymbol{\\theta}$ y $A$ sean dispersos.\n",
    "\n",
    "Los circuitos FABLE son eficientes para la clase de matrices que son dispersas en el dominio de Walsh-Hadamard.\n",
    "\n",
    "Relacionamos $\\delta_{c}$ con $\\epsilon$ a partir del siguiente **Teorema:**\n",
    "\n",
    "Para una matriz $A$ (orden $N$) de $n$ qubits, con $\\lvert a_{ij} \\lvert \\leq 1$, el circuito FABLE sujeto a $\\delta_{c}$ proporciona un $(1/2^n,n+1,N^3\\delta_{c})$-codificación-en-bloque de $A$, hasta el tercer orden en $\\delta_{c}$\n",
    "\n",
    "Numericamente se verifica que este límite de error:\n",
    "\n",
"<img src=\"https://raw.githubusercontent.com/SebastianPaucar/Quantum-Computing-Notes/main/Images/FABLE_IMP_11.PNG\">",
    "\n",
    "Que corresponde a simulaciones de QCLAB sin ruido para circuitos FABLE comprimidos. Los circuitos FABLE aquí son generados para matrices generadas aleatoriamente, con entradas que respetan una distribución normal estándar. Las matrices, que son operadores de 2 a 7 qubits, requiere circuitos de 5 a 15 qubits. Se respeta el último teorema mostrado.\n",
    "\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {
  "language_info": {
   "name": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}