{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Comparator-based Rz synthesis\n", "\n", "**Download Notebook** - {nb-download}`comparator_based_rz.ipynb`\n", "\n", "The $R_z(\\theta)$ gate applies a phase rotation around the Z-axis. Since fault-tolerant quantum computers typically support only a limited gate set, arbitrary rotations must be approximated. This algorithm uses a repeat-until-success approach with Clifford+Toffoli gates to approximate any $R_z(\\theta)$ rotation within error $\\varepsilon$.\n", "\n", "Based on \"Single-qubit rotation algorithm with logarithmic Toffoli count and gate depth\" by Hindlycke & Larsson ([arXiv:2404.05618v4](https://arxiv.org/abs/2404.05618v4))." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Algorithm\n", "\n", "The algorithm uses repeat-until-success with a quantum comparator to approximate $R_z(\\theta)$ rotations.\n", "\n", "**Per attempt:**\n", "1. Prepare $n = 1 + \\lceil \\log_2(1/\\varepsilon) \\rceil$ ancilla qubits in $|+\\rangle$ state\n", "2. Apply comparator circuit (tests if ancilla register $\\geq k$, where $k = 2^{n-1} + \\lfloor 2^{n-1} \\tan(\\theta/2) + 1/2 \\rfloor$)\n", "3. Apply S gate to target qubit\n", "4. Uncompute the comparator\n", "5. Measure ancillas:\n", " - All zeros: Success, $R_z(\\theta^*)$ applied where $\\theta^* \\approx \\theta$\n", " - Otherwise: apply Z correction and retry\n", "\n", "**Properties:**\n", "- $||R_z(\\theta) - R_z(\\theta^*)|| \\leq |\\theta - \\theta^*| \\leq \\varepsilon$\n", "- Expected Toffoli count: $< 4\\lceil \\log_2(1/\\varepsilon) \\rceil$\n", "- Expected attempts: $< 2$ (success probability $> 1/2$)\n", "- Total ancilla qubits: $2\\lceil \\log_2(1/\\varepsilon) \\rceil$\n", "- Depth can be reduced to $O(\\log \\log(1/\\varepsilon))$ while keeping $O(\\log(1/\\varepsilon))$ Toffoli count\n", "- Number of ancillae can be reduced to $\\lceil \\log_2(1/\\varepsilon) \\rceil + 1$ while keeping $O(\\log(1/\\varepsilon))$ Toffoli count" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Example\n", "\n", "We demonstrate the algorithm by approximating a $T$ gate ($R_z(\\pi/4)$) with error bound $\\varepsilon = 0.01$.\n", "\n", "This example shows the full composition. It constructs the forward and inverse `ConstantComparatorCascade` values, then supplies them to the generic `ComparatorBasedRz` struct. Another constant-comparator implementation can be used in the same way if it satisfies the `ConstantComparator` protocol.\n", "\n", "The test works by:\n", "1. Initializing the target qubit in $|+\\rangle$ state\n", "2. Applying the approximate $R_z(\\theta)$ rotation using repeat-until-success\n", "3. Extracting the quantum state to verify the rotation angle is within $\\varepsilon$ of the target" ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "from math import ceil, log2, pi\n", "from typing import no_type_check\n", "from guppylang import guppy, comptime\n", "from guppylang.std.quantum import qubit, h, discard\n", "from guppylang.std.debug import state_result\n", "from guppyalgos.primitives.gate_decompositions.and_op import (\n", " temp_and_compute,\n", " temp_and_uncompute,\n", ")\n", "from guppyalgos.primitives.rotations import (\n", " ComparatorBasedRz,\n", " ConstantComparatorCascade,\n", " n_comparator_based_rz_cascade_ancillas,\n", " n_constant_comparator_cascade_ancillas,\n", ")\n", "from selene_sim import Quest\n", "from guppylang.std.angles import angle\n", "import numpy as np" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "\n", "=== Results ===\n", "Number of attempts: 3\n", "Target angle: 0.25\n", "Achieved angle: 0.24991790998954036\n", "Angle error: 8.209001045964004e-05\n", "Epsilon: 0.01\n" ] } ], "source": [ "EPSILON = 0.01\n", "THETA = 1 / 4 #units of pi\n", "\n", "N = 1 + ceil(log2(1 / EPSILON))\n", "N_COMPARATOR_ANCILLAS = n_constant_comparator_cascade_ancillas(N)\n", "N_ANCILLAS = n_comparator_based_rz_cascade_ancillas(EPSILON)\n", "\n", "@guppy\n", "@no_type_check\n", "def rz_fn(target: qubit, theta: angle) -> None:\n", " comparator = ConstantComparatorCascade[\n", " comptime(N), comptime(N_COMPARATOR_ANCILLAS)\n", " ](temp_and_compute, temp_and_uncompute, False)\n", " inverse_comparator = ConstantComparatorCascade[\n", " comptime(N), comptime(N_COMPARATOR_ANCILLAS)\n", " ](temp_and_compute, temp_and_uncompute, True)\n", " rz = ComparatorBasedRz(comparator, inverse_comparator)\n", " rz.compose(target, theta)\n", "\n", "@guppy\n", "def test_rotation() -> None:\n", " target = qubit()\n", " h(target)\n", " rz_fn(target, angle(comptime(THETA)))\n", " state_result(\"final\", target)\n", " discard(target)\n", "\n", "results = test_rotation.emulator(N_ANCILLAS + 1).run()\n", "\n", "# Extract results\n", "states = Quest.extract_states_dict(results.results[0].entries)\n", "final_state = states[\"final\"].get_single_state()\n", "theta_star = np.angle(final_state[1] / final_state[0]) / np.pi\n", "shots_data = results.collated_shots()\n", "attempts = shots_data[0][\"attempts\"]\n", "\n", "# Compute angle error\n", "angle_error = abs(np.angle(np.exp(1j * (THETA - theta_star))))\n", "\n", "print(f\"\\n=== Results ===\")\n", "print(f\"Number of attempts: {attempts[0]}\")\n", "print(f\"Target angle: {THETA}\")\n", "print(f\"Achieved angle: {theta_star}\")\n", "print(f\"Angle error: {angle_error}\")\n", "print(f\"Epsilon: {EPSILON}\")" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": "guppyalgos (3.14.x)", "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": 4 }