{ "cells": [ { "cell_type": "markdown", "id": "30e21277", "metadata": {}, "source": [ "# QROM Phase-Gradient Rotations\n", "\n", "**Download Notebook** - {nb-download}`qrom_phase_gradient_rotation.ipynb`\n", "\n", "This notebook demonstrates how to use `QROMRotations` together with the `RotationPhaseGradient` Guppy struct to implement a table of rotations whose angles are selected by a QROM index register.\n" ] }, { "cell_type": "markdown", "id": "2792f4c8", "metadata": {}, "source": [ "## Motivation\n", "\n", "Phase-gradient rotations are useful when a circuit needs to apply many different rotations selected by an index register, for example in QROM-based state preparation and basis rotations.\n", "\n", "The key idea is that we do **not** synthesize a separate arbitrary-angle rotation for every table entry. Instead, we:\n", "\n", "1. prepare a phase-gradient register once,\n", "2. use QROM to write the selected fixed-point bit string into a binary target register,\n", "3. use controlled addition into the phase-gradient register to kick the phase back onto an ancilla, and\n", "4. uncompute the QROM target again.\n", "\n", "This keeps the rotation synthesis cost as a one-time cost in the reusable phase-gradient preparation, while each indexed rotation query only uses QROM compute/uncompute plus the phase-gradient kickback primitive.\n", "\n", "The same overall QROM workflow also works with register-incremented rotations: the QROM still loads a little-endian fixed-point word into a data register, but the rotation box interprets that word directly as a sequence of controlled per-bit rotations instead of adding it into a phase-gradient register.\n", "\n", "In this notebook we use a concrete 16-bit example: the QROM has 16 entries, and entry `j` stores the 16-bit little-endian encoding of the increment `j`. So the table acts like a compact library of indexed fixed-point rotations.\n" ] }, { "cell_type": "code", "execution_count": 2, "id": "c289ebbb", "metadata": {}, "outputs": [], "source": [ "from math import atan2, ceil, log2\n", "from typing import Any, no_type_check\n", "\n", "import numpy as np\n", "import pandas as pd\n", "from guppylang import comptime, guppy\n", "from guppylang.std.builtins import array\n", "from guppylang.std.debug import state_output\n", "from guppylang.std.quantum import discard, discard_array, h, qubit\n", "from selene_sim import Quest\n", "\n", "from guppyalgos.algorithms.select.qrom import qrom_unary_iteration\n", "from guppyalgos.primitives.rotations import (\n", " RotationAxisZ,\n", " RotationPhaseGradient,\n", ")\n", "from guppyalgos.primitives.state_preparation.phase_gradient import Convention, phase_gradient\n", "from guppyalgos.utils import (\n", " int_to_bits,\n", " bits_to_int,\n", " phase_distance_mod_2,\n", " qarray,\n", ")\n", "from guppyalgos.tests.helpers import (\n", " assert_allclose_ignorephase,\n", " extract_state_branches_in_superposition,\n", ")\n" ] }, { "cell_type": "markdown", "id": "4e99cbc3", "metadata": {}, "source": [ "## What the QROM phase-gradient rotation does\n", "\n", "Let the QROM store little-endian fixed-point integers\n", "\n", "$$\n", " x^{(j)} = \\sum_{k=0}^{d-1} 2^k x_k^{(j)}, \\qquad x_k^{(j)} \\in \\{0,1\\},\n", "$$\n", "\n", "where $j$ is the QROM index and $d$ is the number of phase bits. If the QROM target is initialized to $|0^d\\rangle$, then the QROM compute step prepares\n", "\n", "$$\n", "\\operatorname{QROM}\\, |j\\rangle |0^d\\rangle = |j\\rangle |x^{(j)}\\rangle.\n", "$$\n", "\n", "Now let $|F_d\\rangle$ be the standard little-endian phase-gradient state\n", "\n", "$$\n", "|F_d\\rangle = \\frac{1}{\\sqrt{2^d}} \\sum_{y=0}^{2^d-1} e^{-2\\pi i y / 2^d} |y\\rangle.\n", "$$\n", "\n", "Controlled addition of $x^{(j)}$ into $|F_d\\rangle$ kicks back a positive phase onto the ancilla because `RotationPhaseGradient` flips the controlled addition with `X` gates on the target:\n", "\n", "$$\n", "|x^{(j)}\\rangle |F_d\\rangle |\\psi\\rangle\n", "\\mapsto\n", "|x^{(j)}\\rangle |F_d\\rangle R_z\\!\\left(\\theta_j\\right)|\\psi\\rangle,\n", "$$\n", "\n", "with half-turn rotation parameter\n", "\n", "$$\n", "\\theta_j^{\\mathrm{kick}} = \\frac{2 x^{(j)}}{2^d}.\n", "$$\n", "\n", "After the final QROM uncompute, the net indexed operation is\n", "\n", "$$\n", "|j\\rangle |0^d\\rangle |F_d\\rangle |\\psi\\rangle\n", "\\mapsto\n", "|j\\rangle |0^d\\rangle |F_d\\rangle R_z\\!\\left(\\theta_j\\right)|\\psi\\rangle.\n", "$$\n", "\n", "So on each QROM index $j$, the circuit applies the positive kickback rotation determined by the fixed-point word stored at that index, while restoring the QROM target register back to zero.\n" ] }, { "cell_type": "code", "execution_count": 5, "id": "d6872665", "metadata": {}, "outputs": [ { "data": { "text/html": [ "
\n", "\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
index jstored bits x^(j)encoded integer x^(j)kickback angle 2 x^(j) / 2^d
00[False, False, False, False]00.000
11[True, False, False, False]10.125
22[False, True, False, False]20.250
33[True, True, False, False]30.375
44[False, False, True, False]40.500
55[True, False, True, False]50.625
66[False, True, True, False]60.750
77[True, True, True, False]70.875
88[False, False, False, True]81.000
99[True, False, False, True]91.125
1010[False, True, False, True]101.250
1111[True, True, False, True]111.375
1212[False, False, True, True]121.500
1313[True, False, True, True]131.625
1414[False, True, True, True]141.750
1515[True, True, True, True]151.875
\n", "
" ], "text/plain": [ " index j stored bits x^(j) encoded integer x^(j) \\\n", "0 0 [False, False, False, False] 0 \n", "1 1 [True, False, False, False] 1 \n", "2 2 [False, True, False, False] 2 \n", "3 3 [True, True, False, False] 3 \n", "4 4 [False, False, True, False] 4 \n", "5 5 [True, False, True, False] 5 \n", "6 6 [False, True, True, False] 6 \n", "7 7 [True, True, True, False] 7 \n", "8 8 [False, False, False, True] 8 \n", "9 9 [True, False, False, True] 9 \n", "10 10 [False, True, False, True] 10 \n", "11 11 [True, True, False, True] 11 \n", "12 12 [False, False, True, True] 12 \n", "13 13 [True, False, True, True] 13 \n", "14 14 [False, True, True, True] 14 \n", "15 15 [True, True, True, True] 15 \n", "\n", " kickback angle 2 x^(j) / 2^d \n", "0 0.000 \n", "1 0.125 \n", "2 0.250 \n", "3 0.375 \n", "4 0.500 \n", "5 0.625 \n", "6 0.750 \n", "7 0.875 \n", "8 1.000 \n", "9 1.125 \n", "10 1.250 \n", "11 1.375 \n", "12 1.500 \n", "13 1.625 \n", "14 1.750 \n", "15 1.875 " ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "n_phase_qubits = 4\n", "n_index_elements = 2 ** n_phase_qubits\n", "\n", "data_input = [\n", " int_to_bits(index, n_phase_qubits)\n", " for index in range(n_index_elements)\n", "]\n", "n_index_qubits = ceil(log2(len(data_input)))\n", "\n", "def kickback_theta(bits: list[bool]) -> float:\n", " encoded_integer = bits_to_int(bits)\n", " return float(2.0 * encoded_integer / (2 ** len(bits)))\n", "\n", "\n", "pd.DataFrame(\n", " {\n", " \"index j\": list(range(len(data_input))),\n", " \"stored bits x^(j)\": data_input,\n", " \"encoded integer x^(j)\": [bits_to_int(bits) for bits in data_input],\n", " \"kickback angle 2 x^(j) / 2^d\": [kickback_theta(bits) for bits in data_input],\n", " }\n", ")\n" ] }, { "cell_type": "markdown", "id": "b19efff4", "metadata": {}, "source": [ "## Testing the QROM phase-gradient rotation" ] }, { "cell_type": "code", "execution_count": 17, "id": "c716f2a3", "metadata": {}, "outputs": [], "source": [ "def expected_ry_state(theta: float) -> np.ndarray:\n", " \"\"\"Returns the expected state vector for a rotation around the Y axis by angle theta.\"\"\"\n", " phase = np.pi * theta / 2.0\n", " return np.array([np.cos(phase), np.sin(phase)], dtype=np.complex128)\n", "\n", "def extract_rz_theta(state: np.ndarray) -> float:\n", " \"\"\"Extract theta from Rz(theta)|+>, up to global phase.\"\"\"\n", " relative_phase = np.angle(state[1] / state[0])\n", " return float((relative_phase / np.pi) % 2.0)" ] }, { "cell_type": "markdown", "id": "a1b5b727", "metadata": {}, "source": [ "## Run the QROM phase-gradient rotation in superposition" ] }, { "cell_type": "code", "execution_count": 39, "id": "fa56fd4a", "metadata": {}, "outputs": [], "source": [ "from guppyalgos.primitives.rotations import QROMRotations\n", "from guppyalgos.utils.guppy.gates import transversal\n", "\n", "def run_phase_gradient_qrom_rotation_superposition(\n", " data_input: list[list[bool]],\n", ") -> dict[str, Any]:\n", " n_data_qubits = len(data_input[0])\n", " n_index_qubits = ceil(log2(len(data_input)))\n", " qrom_compute = qrom_unary_iteration(data_input)\n", " qrom_uncompute = qrom_unary_iteration(data_input)\n", " fourier_state = phase_gradient(n_data_qubits, convention=Convention.Standard)\n", "\n", "\n", " @guppy\n", " @no_type_check\n", " def main() -> None:\n", " index_qreg = qarray(comptime(n_index_qubits))\n", " data_qreg = qarray(comptime(n_data_qubits))\n", " rotation_target = qubit()\n", " phase_state = qarray(comptime(n_data_qubits))\n", " fourier_state(phase_state)\n", " rotation = RotationPhaseGradient(\n", " phase_state, RotationAxisZ()\n", " )\n", "\n", " transversal(h, index_qreg)\n", " h(rotation_target)\n", "\n", " qrom_rot = QROMRotations(\n", " qrom_compute[array[qubit, comptime(n_data_qubits)]],\n", " rotation,\n", " qrom_uncompute[array[qubit, comptime(n_data_qubits)]],\n", " )\n", "\n", " qrom_rot.compose(index_qreg, data_qreg, rotation_target)\n", "\n", " state_output(\"index\", index_qreg)\n", " state_output(\"ancilla\", rotation_target)\n", " state_output(\"qrom_target\", data_qreg)\n", " discard_array(index_qreg)\n", " discard_array(data_qreg)\n", " discard_array(qrom_rot.rotation_box.phase_gradient)\n", " discard(rotation_target)\n", "\n", " res = main.emulator(n_qubits=n_index_qubits + (3 * n_data_qubits) + 1).run()\n", " return Quest.extract_states_dict(res.results[0].entries)" ] }, { "cell_type": "markdown", "id": "1c1d8d65", "metadata": {}, "source": [ "## Check that every extracted branch angle matches the stored input\n", "\n", "For each index `j`, the table shows the positive kickback angle $2x^{(j)}/2^d$ from the derivation and the extracted branch angle reported back in the same positive convention as the derivation.\n" ] }, { "cell_type": "code", "execution_count": 40, "id": "8d272493", "metadata": {}, "outputs": [], "source": [ "expected_zero = np.zeros(2**n_phase_qubits, dtype=np.complex128)\n", "expected_zero[0] = 1.0\n", "\n", "states = run_phase_gradient_qrom_rotation_superposition(data_input)\n", "qrom_target_state = states[\"qrom_target\"].get_single_state()\n", "assert_allclose_ignorephase(qrom_target_state, expected_zero)\n", "\n", "# The branch helper accepts little-endian bitstrings, matching the QROM data.\n", "index_bitstrings_le = [\n", " int_to_bits(index, n_index_qubits)\n", " for index in range(len(data_input))\n", "]\n", "projected_ancilla_states = extract_state_branches_in_superposition(\n", " states,\n", " \"index\",\n", " [\"ancilla\"],\n", " index_bitstrings_le,\n", ")\n", "\n", "rows = []\n", "for index, bits in enumerate(data_input):\n", " projected_ancilla = projected_ancilla_states[tuple(index_bitstrings_le[index])]\n", " input_positive_kickback_angle = kickback_theta(bits)\n", " ancilla_state = projected_ancilla.state.state\n", " extracted_theta = extract_rz_theta(ancilla_state)\n", "\n", " rows.append(\n", " {\n", " \"index j\": index,\n", " \"stored bits x^(j)\": bits,\n", " \"encoded integer x^(j)\": bits_to_int(bits),\n", " \"input positive kickback angle\": input_positive_kickback_angle,\n", " \"extracted branch angle\": extracted_theta,\n", " \"angle error mod 2\": phase_distance_mod_2(extracted_theta, input_positive_kickback_angle),\n", " }\n", " )\n", "\n", "branch_table = pd.DataFrame(rows)\n" ] }, { "cell_type": "code", "execution_count": 41, "id": "1a4493eb", "metadata": {}, "outputs": [ { "data": { "text/html": [ "
\n", "\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
index jstored bits x^(j)encoded integer x^(j)input positive kickback angleextracted branch angleangle error mod 2
00[False, False, False, False]00.0000.0000.000000e+00
11[True, False, False, False]10.1250.1252.775558e-16
22[False, True, False, False]20.2500.2501.665335e-16
33[True, True, False, False]30.3750.3751.665335e-16
44[False, False, True, False]40.5000.5000.000000e+00
55[True, False, True, False]50.6250.6251.110223e-16
66[False, True, True, False]60.7500.7506.661338e-16
77[True, True, True, False]70.8750.8750.000000e+00
88[False, False, False, True]81.0001.0000.000000e+00
99[True, False, False, True]91.1251.1254.440892e-16
1010[False, True, False, True]101.2501.2508.881784e-16
1111[True, True, False, True]111.3751.3754.440892e-16
1212[False, False, True, True]121.5001.5000.000000e+00
1313[True, False, True, True]131.6251.6254.440892e-16
1414[False, True, True, True]141.7501.7508.881784e-16
1515[True, True, True, True]151.8751.8752.220446e-16
\n", "
" ], "text/plain": [ " index j stored bits x^(j) encoded integer x^(j) \\\n", "0 0 [False, False, False, False] 0 \n", "1 1 [True, False, False, False] 1 \n", "2 2 [False, True, False, False] 2 \n", "3 3 [True, True, False, False] 3 \n", "4 4 [False, False, True, False] 4 \n", "5 5 [True, False, True, False] 5 \n", "6 6 [False, True, True, False] 6 \n", "7 7 [True, True, True, False] 7 \n", "8 8 [False, False, False, True] 8 \n", "9 9 [True, False, False, True] 9 \n", "10 10 [False, True, False, True] 10 \n", "11 11 [True, True, False, True] 11 \n", "12 12 [False, False, True, True] 12 \n", "13 13 [True, False, True, True] 13 \n", "14 14 [False, True, True, True] 14 \n", "15 15 [True, True, True, True] 15 \n", "\n", " input positive kickback angle extracted branch angle angle error mod 2 \n", "0 0.000 0.000 0.000000e+00 \n", "1 0.125 0.125 2.775558e-16 \n", "2 0.250 0.250 1.665335e-16 \n", "3 0.375 0.375 1.665335e-16 \n", "4 0.500 0.500 0.000000e+00 \n", "5 0.625 0.625 1.110223e-16 \n", "6 0.750 0.750 6.661338e-16 \n", "7 0.875 0.875 0.000000e+00 \n", "8 1.000 1.000 0.000000e+00 \n", "9 1.125 1.125 4.440892e-16 \n", "10 1.250 1.250 8.881784e-16 \n", "11 1.375 1.375 4.440892e-16 \n", "12 1.500 1.500 0.000000e+00 \n", "13 1.625 1.625 4.440892e-16 \n", "14 1.750 1.750 8.881784e-16 \n", "15 1.875 1.875 2.220446e-16 " ] }, "execution_count": 41, "metadata": {}, "output_type": "execute_result" } ], "source": [ "branch_table" ] }, { "cell_type": "code", "execution_count": null, "id": "d2b5e486", "metadata": {}, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": "Python 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.14.7" } }, "nbformat": 4, "nbformat_minor": 5 }