{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "0c675c9b",
   "metadata": {},
   "source": [
    "# About Block-Encoding"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "12c21319",
   "metadata": {},
   "source": [
    "## Outline"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a173a560",
   "metadata": {},
   "source": [
    "Quantum computers are based on qubits, which differ fundamentally from classical bits used in conventional computing systems. By harnessing quantum phenomena such as superposition and entanglement, quantum algorithms have the potential to perform certain computations and data processing tasks that are infeasible for classical computers.\n",
    "\n",
    "However, quantum circuits are subject to several physical and mathematical constraints. One major limitation is that only unitary operations are allowed within quantum circuits. As a result, directly applying non-unitary matrices—which often arise in chemistry and physics simulations (e.g., dissipative dynamics, measurement processes)—is not straightforward. This makes tasks such as computing expectation values or simulating non-unitary transformations challenging.\n",
    "\n",
    "This module implements a solution to that problem using a technique called Block-Encoding (BE) [1]. The BE framework allows a non-unitary matrix to be embedded within a larger unitary operator, provided the matrix can be decomposed into a linear combination of production of Pauli matrices.\n",
    "\n",
    "In practice, the algorithm constructs a unitary circuit that applies each Pauli term conditionally via ancillary (control) qubits. This allows the effective application of the non-unitary matrix to a quantum state within the constraints of unitary-only quantum hardware.\n",
    "\n",
    "By using BE, this module enables simulation and computation involving non-unitary operators on quantum hardware, which opens up new possibilities for quantum algorithms in computational chemistry and related domains."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8e013e4b",
   "metadata": {},
   "source": [
    "This page provides a theoretical overview of BE, along with the key challenges associated with its implementation.\n",
    "\n",
    "For step-by-step instructions on how to use this module, `PItBE`, please refer to [Demo Play](../eng/demo_use_en.ipynb)."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e769e0a9",
   "metadata": {},
   "source": [
    "## Theoretical Background "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1d088cac",
   "metadata": {},
   "source": [
    "### Quantum State Representation and Gate Structure in the BE Method\n",
    "\n",
    "Let $\\hat{A}$ be a non-unitary square matrix of size $2^n \\times 2^n$ (i.e., $\\hat{A} \\in \\mathbb{C}^{2^n\\times{}2^n}$), which we aim to encode and apply using quantum operations. Assume that $\\hat{A}$ can be expressed as a linear combination of unitary Pauli operator, $\\hat{P}_i$, products, as follows:\n",
    "\n",
    "$$\n",
    "\\hat{A} = \\sum_i^m\\alpha_i\\hat{P}_i\n",
    "$$\n",
    "\n",
    "Here:\n",
    "- Each $\\alpha_j$ is a complex coefficient ($\\alpha_j \\in \\mathbb{C}$)\n",
    "- Each $\\hat{P}_j$ is a product of Pauli operators (i.e., elements from $\\{I, X, Y, Z\\}^{\\otimes{}n}$)\n",
    "\n",
    "The number of terms in the decomposition is denoted by $m$. For the purposes of this explanation, we assume that $m = 2^k$ for some integer $k \\in \\mathbb{N}$.  \n",
    "Additionally, the coefficients $\\alpha_j$ are assumed to be normalized, as required for constructing the block-encoding.\n",
    "\n",
    "Let $|\\psi\\rangle$ denote the quantum state to which we wish to apply the non-unitary matrix $\\hat{A}$.\n",
    "\n",
    "In BE, the quantum state consists of two parts:\n",
    "\n",
    "1. **Main qubits**, which store the input quantum state to which the non-unitary operator is to be applied.\n",
    "2. **Ancilla qubits**, which are used to control the application of quantum gates $ \\hat{P}_i $ acting on the main qubits.\n",
    "\n",
    "This combined quantum state can be expressed as the Kronecker (tensor) product:\n",
    "$$\n",
    "    |00\\dots0\\rangle_{\\text{anci}}\\otimes |\\psi\\rangle_\\text{main}\n",
    "$$\n",
    "The number of ancillary qubits is $\\log_2(m)$, which is equal to $k$ in this context.\n",
    "Within the quantum circuit, two types of quantum gates are used:\n",
    "\n",
    "- **Controlled Pauli gates**\n",
    "  \n",
    "  $\\hat{P}_i$, which act on the main qubits depending on the state of the ancilla.\n",
    "- **Ancilla-only unitary gates**\n",
    "  \n",
    "  $\\hat{B}$ and $\\hat{C}$, which act solely on the ancilla qubits.\n",
    "\n",
    "Both $\\hat{B}$ and $\\hat{C}$ are unitary matrices of dimension $2^k \\times 2^k$, and their elements are complex numbers. They are defined as:\n",
    "$$\n",
    "\\begin{aligned}\n",
    "    \\hat{B}: \\beta_{s,t}\\\\\n",
    "    \\hat{C}: \\gamma_{s,t}\n",
    "\\end{aligned}\n",
    "$$\n",
    "where $s$ and $t$ are indices over the $2^k$ basis states of the ancillary qubits."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a23f720b",
   "metadata": {},
   "source": [
    "### Applying Gate $\\hat{B}$ on ancilla qubits\n",
    "\n",
    "First, we introduce the quantum circuit that implements BE.\n",
    "\n",
    "![BE Circuit](../../picture/be_circ_en.png)\n",
    "\n",
    "In the following, we explain the theoretical background by tracing the evolution of the quantum state as the quantum circuit like above executes step by step.\n",
    "\n",
    "We begin by applying the unitary gate $\\hat{B}$ to the ancillary qubits. As a result, the ancillary register is transformed into a superposition state, while the main register remains unchanged.\n",
    "The transformation can be written as:\n",
    "$$\n",
    "|0\\dots{}0\\rangle_{\\text{anci}}\\otimes|\\psi\\rangle_{\\text{main}}\n",
    "\\to\n",
    "\\left(\\sum_i^m{\\beta_{i,0}}|i\\rangle_{\\text{anci}}\\right)\\otimes|\\psi\\rangle_{\\text{main}}\n",
    "$$\n",
    "Here, $|i\\rangle$ denotes the computational basis state corresponding to the integer $i$, represented in $k$**-bit binary form**.\n",
    "For example, when $k = 5$ and $i = 8$, the basis state $|i\\rangle$ is:\n",
    "$$\n",
    "|i\\rangle = |00100\\rangle\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4c314370",
   "metadata": {},
   "source": [
    "### Applying Controlled Gates $\\hat{P}_i$ on Main Qubits Based on States of Ancilla Qubits\n",
    "\n",
    "Next, we apply controlled quantum gates $\\hat{P}_i$ to the main qubits. Each controlled gate is activated based on the value of the ancillary register. Specifically, when the ancillary qubits are in the state $|i\\rangle$, the corresponding unitary operator $\\hat{P}_i$ is applied to the main qubits.\n",
    "\n",
    "This process transforms the quantum state as follows:\n",
    "$$\n",
    "\\left(\\sum_i^m\\beta_{i,0}|i\\rangle_{\\text{anci}}\\right)\\otimes|\\psi\\rangle_{\\text{main}}\n",
    "\\to\n",
    "\\sum_i^m\\beta_{i,0}|i\\rangle_{\\text{anci}}\\otimes\\hat{P}_i|\\psi\\rangle_{\\text{main}}\n",
    "$$\n",
    "As a result, we obtain a superposition where each term encodes the state obtained by applying a different unitary operator $\\hat{P}_i$ to the original state $|\\psi\\rangle$, distinguished by the value of the ancillary register.\n",
    "\n",
    "This allows the quantum circuit to simultaneously represent the outcomes of applying multiple different operators, while keeping them distinguishable through the ancilla."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4e9f663f",
   "metadata": {},
   "source": [
    "### Applying Gate $\\hat{C}$ on ancilla qubits and Extracting the Final State\n",
    "After the controlled gates $\\hat{P}_i$ have been applied, we next apply the unitary gate $\\hat{C}$ to the ancillary qubits. This transforms the quantum state as follows:\n",
    "$$\n",
    "\\sum_i^m\\beta_{i,0}|i\\rangle_{\\text{anci}}\\otimes\\hat{P}_i|\\psi\\rangle_{\\text{main}}\n",
    "\\to\n",
    "\\sum_{i,j}^m\\gamma_{j,i}\\beta_{i,0}|j\\rangle_{\\text{anci}}\\otimes\\hat{P}_i|\\psi\\rangle_{\\text{main}}\n",
    "$$\n",
    "If the coefficients $\\gamma_{j,i}$ and $\\beta_{i,0}$ are chosen such that for a specific value of $j$, the following condition is satisfied:\n",
    "$$\n",
    "\\gamma_{j,i}\\beta_{i,0} = t\\alpha_i\\quad(t>0)\n",
    "$$\n",
    "then projecting the ancillary register onto the state $|j\\rangle$ gives access to the state $\\hat{A}|\\psi\\rangle$ up to a scaling factor:\n",
    "$$\n",
    "\\begin{aligned}\n",
    "    &\\quad\\sum_{i}^m\\gamma_{j,i}\\beta_{i,0}|j\\rangle_{\\text{anci}}\\otimes\\hat{P}_i|\\psi\\rangle_{\\text{main}}\\\\\n",
    "    &=\\sum_{i}^mt\\alpha_i|j\\rangle_{\\text{anci}}\\otimes\\hat{P}_i|\\psi\\rangle_{\\text{main}}\\\\\n",
    "    &=|j\\rangle_{\\text{anci}}\\otimes\\left(\\sum_{i}^mt\\alpha_i\\hat{P}_i|\\psi\\rangle_{\\text{main}}\\right)\\\\\n",
    "    &=|j\\rangle_{\\text{anci}}\\otimes{}t\\hat{A}|\\psi\\rangle_{\\text{main}}\\\\\n",
    "\\end{aligned}\n",
    "$$\n",
    "In practice, it is recommended to choose $j = 0$. If the parameters are set as:\n",
    "$$\n",
    "\\beta_{i,0} = \\sqrt{t\\alpha_i}\n",
    "$$\n",
    "then this implies:\n",
    "$$\n",
    "\\gamma_{0,i} = \\sqrt{t\\alpha_i}\n",
    "$$\n",
    "so that the matrix $\\hat{C}$ becomes the Hermitian transpose of $\\hat{B}$:\n",
    "$$\n",
    "\\hat{C} = \\hat{B}^T\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e0ba3039",
   "metadata": {},
   "source": [
    "### Measurement Probability in the BE Method\n",
    "During the projective measurement step, the probability $p_j$ of obtaining the BE-encoded result from the ancillary register is given by:\n",
    "$$\n",
    "\\begin{aligned}\n",
    "    p_j \n",
    "    &= ||j\\rangle_{\\text{anci}}\\otimes{}t\\hat{A}|\\psi\\rangle_{\\text{main}}|^2\\\\\n",
    "    &= \\langle{}j|j\\rangle_{\\text{anci}}\\times{}t^2\\langle{}\\psi|\\hat{A}^{\\dagger}\\hat{A}|\\psi\\rangle_{\\text{main}}\\\\\n",
    "    &= t^2\\langle{}\\psi|\\hat{A}^{\\dagger}\\hat{A}|\\psi\\rangle_{\\text{main}}\\\\\n",
    "\\end{aligned}\n",
    "$$\n",
    "Now, suppose the quantum state $|\\psi\\rangle$ can be written as a linear combination of the eigenvectors $|\\phi_l\\rangle$ of $\\hat{A}$ with coefficients $\\epsilon_l$:\n",
    "$$\n",
    "|\\psi\\rangle=\\sum_l\\epsilon_l|\\phi_l\\rangle\n",
    "$$\n",
    "Then, using the eigenvalues $\\lambda_l$ of $\\hat{A}$, the measurement probability becomes:\n",
    "$$\n",
    "\\begin{aligned}\n",
    "    p_j \n",
    "    &= t^2\\langle{}\\psi|\\hat{A}^{\\dagger}\\hat{A}|\\psi\\rangle_{\\text{main}}\\\\\n",
    "    &= t^2\\sum_i|\\epsilon_i\\lambda_i|\\phi_i\\rangle|^2\\\\\n",
    "    &= t^2\\sum_i|\\epsilon_i\\lambda_i|^2\n",
    "\\end{aligned}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e2baeade",
   "metadata": {},
   "source": [
    "## Limitations and Challenges of the BE Method\n",
    "\n",
    "While the BE method enables the application of non-unitary matrices on quantum states using unitary circuits, it comes with several theoretical and practical challenges:\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e448a97b",
   "metadata": {},
   "source": [
    "### Ancilla Overhead  \n",
    "   The method requires $[\\log_2(m)]$ ancillary qubits, where $m$ is the number of Pauli terms in the decomposition of $\\hat{A}$. For large $m$, this can lead to significant qubit overhead, which is critical on NISQ (Noisy Intermediate-Scale Quantum) hardware."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0c8399c3",
   "metadata": {},
   "source": [
    "### Gate Complexity  \n",
    "   Implementing the required unitaries $\\hat{B}$, $\\hat{C}$, and $\\hat{P}_i$ for large-scale systems can be circuit-depth intensive, especially for general dense matrices where the Pauli decomposition has many terms."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "79108928",
   "metadata": {},
   "source": [
    "### Implementation of Quantum Gates $\\hat{B}$ and $\\hat{C}$\n",
    "\n",
    "In the execution of the BE method, it is necessary to implement the controlled quantum gates $\\hat{P}_i$, which apply the Pauli product terms that constitute $\\hat{A}$. However, implementing these gates typically requires multiple control qubits, which in turn demand a large number of CNOT gates.\n",
    "\n",
    "When combined with the gate cost for implementing the ancillary-only unitaries $\\hat{B}$ and $\\hat{C}$, the total number of quantum gates required for BE becomes significant. As a result, the BE method is currently impractical on NISQ devices.\n",
    "\n",
    "The author believes that the full-scale implementation of the BE method will require either:\n",
    "- the advent of fault-tolerant quantum computers with quantum error correction, or  \n",
    "- the development of optimized methods to reduce the overall gate count.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b4ffe0f3",
   "metadata": {},
   "source": [
    "### Success Probability \n",
    "   The success probability of measuring the desired ancilla state (typically $|0\\rangle$) is proportional to:  \n",
    "   $$\n",
    "   p_j = t^2\\sum_i|\\epsilon_i\\lambda_i|^2\n",
    "   $$\n",
    "   which may be small depending on $\\hat{A}$ and $|\\psi\\rangle$, requiring repeated executions and amplitude amplification strategies."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "648004f4",
   "metadata": {},
   "source": [
    "## Referrence\n",
    "\n",
    "[1] Andrew M Childs and Nathan Wiebe. “Hamiltonian simulation using linear combinations of unitary operations”. In: \n",
    "[arXiv preprint arXiv:1202.5822](https://arxiv.org/abs/1202.5822) (2012). \n",
    "\n",
    "\n",
    "The paper which proposed the BE method"
   ]
  }
 ],
 "metadata": {
  "language_info": {
   "name": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}