Comparator-based Rz synthesis

Download Notebook - comparator_based_rz.ipynb

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\).

Based on “Single-qubit rotation algorithm with logarithmic Toffoli count and gate depth” by Hindlycke & Larsson (arXiv:2404.05618v4).

Algorithm

The algorithm uses repeat-until-success with a quantum comparator to approximate \(R_z(\theta)\) rotations.

Per attempt:

1. Prepare \(n = 1 + \lceil \log_2(1/\varepsilon) \rceil\) ancilla qubits in \(|+\rangle\) state

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\))

3. Apply S gate to target qubit

4. Uncompute the comparator

5. Measure ancillas:

   • All zeros: Success, \(R_z(\theta^*)\) applied where \(\theta^* \approx \theta\)

   • Otherwise: apply Z correction and retry

Properties:

• \(||R_z(\theta) - R_z(\theta^*)|| \leq |\theta - \theta^*| \leq \varepsilon\)

• Expected Toffoli count: \(< 4\lceil \log_2(1/\varepsilon) \rceil\)

• Expected attempts: \(< 2\) (success probability \(> 1/2\))

• Total ancilla qubits: \(2\lceil \log_2(1/\varepsilon) \rceil\)

• Depth can be reduced to \(O(\log \log(1/\varepsilon))\) while keeping \(O(\log(1/\varepsilon))\) Toffoli count

• Number of ancillae can be reduced to \(\lceil \log_2(1/\varepsilon) \rceil + 1\) while keeping \(O(\log(1/\varepsilon))\) Toffoli count

Example

We demonstrate the algorithm by approximating a \(T\) gate (\(R_z(\pi/4)\)) with error bound \(\varepsilon = 0.01\).

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.

The test works by:

1. Initializing the target qubit in \(|+\rangle\) state

2. Applying the approximate \(R_z(\theta)\) rotation using repeat-until-success

3. Extracting the quantum state to verify the rotation angle is within \(\varepsilon\) of the target

from math import ceil, log2, pi
from typing import no_type_check
from guppylang import guppy, comptime
from guppylang.std.quantum import qubit, h, discard
from guppylang.std.debug import state_result
from guppyalgos.primitives.gate_decompositions.and_op import (
    temp_and_compute,
    temp_and_uncompute,
)
from guppyalgos.primitives.rotations import (
    ComparatorBasedRz,
    ConstantComparatorCascade,
    n_comparator_based_rz_cascade_ancillas,
    n_constant_comparator_cascade_ancillas,
)
from selene_sim import Quest
from guppylang.std.angles import angle
import numpy as np

EPSILON = 0.01
THETA = 1 / 4 #units of pi

N = 1 + ceil(log2(1 / EPSILON))
N_COMPARATOR_ANCILLAS = n_constant_comparator_cascade_ancillas(N)
N_ANCILLAS = n_comparator_based_rz_cascade_ancillas(EPSILON)

@guppy
@no_type_check
def rz_fn(target: qubit, theta: angle) -> None:
    comparator = ConstantComparatorCascade[
        comptime(N), comptime(N_COMPARATOR_ANCILLAS)
    ](temp_and_compute, temp_and_uncompute, False)
    inverse_comparator = ConstantComparatorCascade[
        comptime(N), comptime(N_COMPARATOR_ANCILLAS)
    ](temp_and_compute, temp_and_uncompute, True)
    rz = ComparatorBasedRz(comparator, inverse_comparator)
    rz.compose(target, theta)

@guppy
def test_rotation() -> None:
    target = qubit()
    h(target)
    rz_fn(target, angle(comptime(THETA)))
    state_result("final", target)
    discard(target)

results = test_rotation.emulator(N_ANCILLAS + 1).run()

# Extract results
states = Quest.extract_states_dict(results.results[0].entries)
final_state = states["final"].get_single_state()
theta_star = np.angle(final_state[1] / final_state[0])  / np.pi
shots_data = results.collated_shots()
attempts = shots_data[0]["attempts"]

# Compute angle error
angle_error = abs(np.angle(np.exp(1j * (THETA - theta_star))))

print(f"\n=== Results ===")
print(f"Number of attempts:    {attempts[0]}")
print(f"Target angle:          {THETA}")
print(f"Achieved angle:        {theta_star}")
print(f"Angle error:           {angle_error}")
print(f"Epsilon:               {EPSILON}")

=== Results ===
Number of attempts:    3
Target angle:          0.25
Achieved angle:        0.24991790998954036
Angle error:           8.209001045964004e-05
Epsilon:               0.01