{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "lcu-intro",
   "metadata": {},
   "source": [
    "# LCU and qubitization\n",
    "\n",
    "**Download Notebook** - {nb-download}`lcu_qubitization.ipynb`\n",
    "\n",
    "Build a block encoding from a Pauli Hamiltonian, then check that two quantum-walk steps encode its second Chebyshev polynomial. This example uses unary-iteration SELECT with temporary-AND uncomputation.\n",
    "\n",
    "Run this notebook from a source checkout with the development dependencies installed. The repository default is little endian."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "26d107e7",
   "metadata": {
    "tags": [
     "hide-input"
    ]
   },
   "outputs": [],
   "source": [
    "from typing import no_type_check\n",
    "\n",
    "import zixy.qubit.pauli as zqp\n",
    "from guppylang import guppy\n",
    "from guppylang.std.builtins import array\n",
    "from guppylang.std.quantum import qubit\n",
    "\n",
    "from guppyalgos.primitives.gate_decompositions.and_op import (\n",
    "    temp_and_compute,\n",
    "    temp_and_uncompute,\n",
    ")\n",
    "from guppyalgos.primitives.gate_decompositions.cnx.cnx import cnx\n",
    "from guppyalgos.algorithms.block_encoding.lcu import LCU, LCUData, build_unary_iteration_select\n",
    "from guppyalgos.algorithms.block_encoding.qubitization.qubitization import Qubitization\n",
    "from guppyalgos.primitives.subroutines.reflection import Reflection\n",
    "from guppyalgos.algorithms.state_preparation import multiplexor_prep\n",
    "from guppyalgos.tests.helpers import (\n",
    "    Endianness,\n",
    "    assert_allclose_ignorephase,\n",
    "    chebyshev_power_matrix,\n",
    "    get_unitary_projected,\n",
    ")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "lcu-prepare",
   "metadata": {},
   "source": [
    "## 1. Build PREPARE and SELECT\n",
    "\n",
    "For the Hamiltonian\n",
    "\n",
    "$$\n",
    "H=0.4Z_0-0.2X_1+0.3Y_0Y_1+0.1Z_0X_1,\\qquad\\lambda=\\sum_j|a_j|=1,\n",
    "$$\n",
    "\n",
    "`LCUData` extracts the weights and Pauli terms. `multiplexor_prep` prepares amplitudes $\\sqrt{|a_j|/\\lambda}$, while SELECT includes the coefficient signs. Together with inverse preparation, they give\n",
    "\n",
    "$$\n",
    "B=P^\\dagger SP,\\qquad\\langle00|B|00\\rangle=H/\\lambda.\n",
    "$$\n",
    "\n",
    "Two preparation qubits address the four terms. Unary iteration uses one additional work qubit internally."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "acc38feb",
   "metadata": {},
   "outputs": [],
   "source": [
    "hamiltonian = zqp.RealTermSum.from_str(\n",
    "    \"(0.4, Z0), (-0.2, X1), (0.3, Y0 Y1), (0.1, Z0 X1)\",\n",
    "    2,\n",
    ")\n",
    "lcu_data = LCUData.from_hamiltonian(hamiltonian)\n",
    "\n",
    "prepare = multiplexor_prep(lcu_data.amplitudes)\n",
    "\n",
    "select = build_unary_iteration_select(\n",
    "    lcu_data,\n",
    "    comp_and_op=temp_and_compute,\n",
    "    uncomp_and_op=temp_and_uncompute,\n",
    ")\n",
    "\n",
    "dagger = object()\n",
    "\n",
    "@guppy\n",
    "@no_type_check\n",
    "def unprepare(prep: array[qubit, 2]) -> None:\n",
    "    with dagger:\n",
    "        prepare(prep)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "lcu-walk",
   "metadata": {},
   "source": [
    "## 2. Apply two walk steps\n",
    "\n",
    "`Qubitization` combines the LCU with the all-zero reflection:\n",
    "\n",
    "$$\n",
    "W=RB,\\qquad R=I-2|00\\rangle\\langle00|.\n",
    "$$\n",
    "\n",
    "For this Hermitian Pauli encoding, the projected second power is\n",
    "\n",
    "$$\n",
    "\\langle00|W^2|00\\rangle=T_2(H/\\lambda)=2(H/\\lambda)^2-I.\n",
    "$$\n",
    "\n",
    "The check reserves the internal work qubit and compares the unnormalized block with the classical polynomial, allowing an overall global phase."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "7863fbb7",
   "metadata": {},
   "outputs": [],
   "source": [
    "power = 2\n",
    "\n",
    "@guppy\n",
    "@no_type_check\n",
    "def qubitize(\n",
    "    prep: array[qubit, 2],\n",
    "    state: array[qubit, 2],\n",
    ") -> None:\n",
    "    lcu = LCU(prepare, select, unprepare)\n",
    "    reflection = Reflection[2, 1](cnx)\n",
    "    Qubitization(lcu, reflection).power(prep, state, power)\n",
    "\n",
    "projected_qubitization = get_unitary_projected(\n",
    "    qubitize,\n",
    "    lcu_data.n_state_qubits,\n",
    "    {\"prep\": [False] * lcu_data.n_prep_qubits},\n",
    "    n_extra_qubits=lcu_data.n_prep_qubits - 1,\n",
    "    endianness=Endianness.LITTLE,\n",
    ")\n",
    "\n",
    "normalized_hamiltonian = (\n",
    "    hamiltonian.to_sparse_matrix().toarray() / lcu_data.l1_norm\n",
    ")\n",
    "expected_chebyshev = chebyshev_power_matrix(normalized_hamiltonian, power)\n",
    "assert_allclose_ignorephase(projected_qubitization, expected_chebyshev)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": ".venv (3.13.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.12.13"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}