Circuit primitive examples

These standalone examples use public APIs and fail if an independent numerical reference or workspace check disagrees with the circuit.

Coherent QROM lookup

A quantum algorithm may need different classical data for different branches of a quantum state. This example shows how a quantum address can look up a table entry while preserving the superposition and its relative phases. It then uses the loaded data to change the state and reverses the lookup, demonstrating how table data can influence a calculation while its temporary storage is returned to zero.

You should come away able to identify the address, output, and scratch registers and understand why their initial values and cleanup matter. The same lookup is built with SELECT and SELECT-SWAP strategies and with an external enable, making their qubit and gate tradeoffs visible. Full-state comparisons with an independently constructed reference check that the chosen entry, the phase change, and workspace restoration all agree.

Individual validation checks are shown with --verbose. All checks still run by default, and failures are always reported.

Read a table coherently, use a loaded bit, and unlookup. The example checks SELECT and SELECT-SWAP, native and wrapped control, and clean workspace.

See also

Coherent circuit primitives for register contracts and interpretation.

"""Coherent QROM: lookup, use, unlookup, and external control.

A quantum algorithm may need different classical data for different branches
of a quantum state. This example shows how a quantum address can look up a
table entry while preserving the superposition and its relative phases. It
then uses the loaded data to change the state and reverses the lookup,
demonstrating how table data can influence a calculation while its temporary
storage is returned to zero.

You should come away able to identify the address, output, and scratch
registers and understand why their initial values and cleanup matter. The same
lookup is built with SELECT and SELECT-SWAP strategies and with an external
enable, making their qubit and gate tradeoffs visible. Full-state comparisons
with an independently constructed reference check that the chosen entry, the
phase change, and workspace restoration all agree.

Run with: python3 qrom_lookup.py
QROM XORs classical words into a quantum output without measuring the address.
All checks compare complex amplitudes, including restored ladder workspace.
Add --verbose to show individual validation checks; failures are always reported.
"""

import argparse
import os
import time

import numpy as np

import cudaq
from cudaq_algorithms import state_from
from cudaq_algorithms.primitives import QROM

DATA = [3, 0, 5, 6, 1]
ADDRESS_BITS = 3
OUTPUT_BITS = 3
ATOL = 1e-10


def check(label, actual, expected, *, verbose=False):
    error = float(np.max(np.abs(actual - expected)))
    passed = np.isfinite(error) and error <= ATOL
    if verbose or not passed:
        print(f"CHECK {label}: {error:.3e} <= {ATOL:.1e} -> "
              f"{'PASS' if passed else 'FAIL'}")
    if not np.isfinite(error) or error > ATOL:
        raise AssertionError(label)


def complex_ket(size, rng):
    ket = rng.normal(size=size) + 1j * rng.normal(size=size)
    return ket / np.linalg.norm(ket)


def reference(initial, *, controlled=False, phase=False):
    """Logical registers are [control? | address | output], low bits first."""
    result = np.zeros_like(initial)
    offset = int(controlled)
    for index, amplitude in enumerate(initial):
        address = (index >> offset) & ((1 << ADDRESS_BITS) - 1)
        word = DATA[address] if address < len(DATA) else 0
        enabled = not controlled or bool(index & 1)
        if phase:
            # lookup, Z on output bit 0, lookup: the phase of a zero output
            # word is (-1)**(word & 1); a nonzero y would add (-1)**(y & 1).
            result[index] = amplitude * (-1 if word & 1 else 1)
        else:
            target = index ^ (word <<
                              (ADDRESS_BITS + offset)) if enabled else index
            result[target] += amplitude
    return result


def lookup_circuit(table, *, wrapped=False, phase=False):
    # QROM.kernel is a callable PROPERTY. It is not a zero-argument factory.
    lookup = table.kernel
    m, width, ladder_width = table.num_address, table.num_output, table.num_ladder

    if table.controlled:

        @cudaq.kernel
        def native(initial: cudaq.State):
            logical = cudaq.qvector(initial)
            ladder = cudaq.qvector(ladder_width)
            lookup(logical[0:1], logical[1:1 + m], ladder,
                   logical[1 + m:1 + m + width])

        return native

    if wrapped:

        @cudaq.kernel
        def controlled_parent(initial: cudaq.State):
            logical = cudaq.qvector(initial)
            ladder = cudaq.qvector(ladder_width)
            cudaq.control(lookup, logical[0:1], logical[1:1 + m], ladder,
                          logical[1 + m:1 + m + width])

        return controlled_parent

    @cudaq.kernel
    def plain(initial: cudaq.State):
        logical = cudaq.qvector(initial)
        ladder = cudaq.qvector(ladder_width)
        lookup(logical[0:m], ladder, logical[m:m + width])
        if phase:
            # Use a loaded bit, then erase the word with the same XOR lookup.
            z(logical[m])
            lookup(logical[0:m], ladder, logical[m:m + width])

    return plain


def run_check(label,
              table,
              initial,
              *,
              wrapped=False,
              phase=False,
              verbose=False):
    controlled = table.controlled or wrapped
    expected_logical = reference(initial, controlled=controlled, phase=phase)
    expected = np.zeros(len(initial) << table.num_ladder, dtype=complex)
    expected[:len(initial)] = expected_logical
    circuit = lookup_circuit(table, wrapped=wrapped, phase=phase)
    actual = np.asarray(cudaq.get_state(circuit, state_from(initial)))
    check(label, actual, expected, verbose=verbose)
    return actual[:len(initial)]


def resource_kernel(table, *, wrapped=False):
    """Allocate clean registers; count only lookup, with no state preparation."""
    lookup = table.kernel
    m, width, ladder_width = table.num_address, table.num_output, table.num_ladder
    if table.controlled:

        @cudaq.kernel
        def native():
            control = cudaq.qvector(1)
            address = cudaq.qvector(m)
            ladder = cudaq.qvector(ladder_width)
            output = cudaq.qvector(width)
            lookup(control, address, ladder, output)

        return native

    if wrapped:

        @cudaq.kernel
        def wrapped_lookup():
            control = cudaq.qvector(1)
            address = cudaq.qvector(m)
            ladder = cudaq.qvector(ladder_width)
            output = cudaq.qvector(width)
            cudaq.control(lookup, control, address, ladder, output)

        return wrapped_lookup

    @cudaq.kernel
    def plain():
        address = cudaq.qvector(m)
        ladder = cudaq.qvector(ladder_width)
        output = cudaq.qvector(width)
        lookup(address, ladder, output)

    return plain


def report_resources(label, table, *, wrapped=False):
    resources = cudaq.estimate_resources(
        resource_kernel(table, wrapped=wrapped))
    # "ccx" is a display name, not the count() lookup key.
    toffolis = resources.count_controls("x", 2)
    higher_x = sum(
        resources.count_controls("x", controls)
        for controls in range(3, table.num_address + 3))
    fredkins = resources.count_controls("swap", 1)
    total = (table.num_address + table.num_output + table.num_ladder +
             int(table.controlled or wrapped))
    print(f"{label:24s} qubits={total:2d} ladder={table.num_ladder:2d} "
          f"CCX={toffolis:3d} higher-controlled-X={higher_x:3d} "
          f"controlled-SWAP={fredkins:2d}")
    if not wrapped and toffolis != table.toffoli_count:
        raise AssertionError(f"{label}: compiler/QROM Toffoli counts differ")
    return total


def main():
    parser = argparse.ArgumentParser(description=__doc__.splitlines()[0])
    parser.add_argument(
        "--verbose",
        action="store_true",
        help="show each validation check (failures are always reported)")
    verbose = parser.parse_args().verbose
    start = time.perf_counter()
    cudaq.set_target(os.environ.get("CUDAQ_DEFAULT_SIMULATOR", "qpp-cpu"))
    rng = np.random.default_rng(7)
    print("Table:", DATA, "; addresses 5, 6, 7 read zero.")
    print("Address 1 is a valid zero-valued entry; padding is also zero.")
    print("All ladder registers start clean and must be restored.")

    # Nonzero output and complex amplitudes test XOR semantics and coherence.
    initial = complex_ket(1 << (ADDRESS_BITS + OUTPUT_BITS), rng)
    marked_input = np.zeros_like(initial)
    marked_input[:1 << ADDRESS_BITS] = complex_ket(1 << ADDRESS_BITS, rng)
    variants = (("select", None), ("select_swap", 2), ("auto", None))
    plain_results = []
    maximum_qubits = 0
    for variant, block_size in variants:
        table = QROM(DATA,
                     ADDRESS_BITS,
                     OUTPUT_BITS,
                     variant=variant,
                     block_size=block_size)
        print(f"\nRequested {variant}, selected {table.variant}, "
              f"block_size={table.block_size}")
        plain_results.append(
            run_check(f"{variant} XOR", table, initial, verbose=verbose))
        run_check(f"{variant} lookup/use/unlookup",
                  table,
                  marked_input,
                  phase=True,
                  verbose=verbose)
        maximum_qubits = max(maximum_qubits,
                             report_resources(f"{variant} plain", table))

        # Native control can change auto's construction and workspace geometry.
        native = QROM(DATA,
                      ADDRESS_BITS,
                      OUTPUT_BITS,
                      variant=variant,
                      block_size=block_size,
                      controlled=True)
        for control_value in (0, 1):
            controlled_input = np.zeros(2 * len(initial), dtype=complex)
            controlled_input[control_value::2] = initial
            run_check(f"{variant} enable={control_value}",
                      native,
                      controlled_input,
                      verbose=verbose)

        coherent_input = np.zeros(2 * len(initial), dtype=complex)
        coherent_input[0::2] = initial / np.sqrt(2)
        coherent_input[1::2] = 1j * initial / np.sqrt(2)
        run_check(f"{variant} coherent native control",
                  native,
                  coherent_input,
                  verbose=verbose)
        run_check(f"{variant} coherent wrapped control",
                  table,
                  coherent_input,
                  wrapped=True,
                  verbose=verbose)
        maximum_qubits = max(
            maximum_qubits,
            report_resources(f"{variant} native control", native),
            report_resources(f"{variant} wrapped control", table,
                             wrapped=True))

    for result in plain_results[1:]:
        # Complete states above check each geometry; these are logical slices.
        check("strategies agree on logical XOR",
              result,
              plain_results[0],
              verbose=verbose)

    print("\nResource-only pricing (no large statevector is allocated):")
    print(
        "entries width  select-CCX  swap-CCX  auto variant/block/ladder; native auto"
    )
    for entries, width in ((4, 8), (8, 1), (16, 1), (64, 1), (64, 8)):
        data = [(7 * k + 3) % (1 << width) for k in range(entries)]
        bits = (entries - 1).bit_length()
        select = QROM(data, bits, width, variant="select")
        swap_table = QROM(data, bits, width, variant="select_swap")
        auto = QROM(data, bits, width)
        native_auto = QROM(data, bits, width, controlled=True)
        if auto.toffoli_count != min(select.toffoli_count,
                                     swap_table.toffoli_count):
            raise AssertionError(
                "auto did not choose the cheapest coherent price")
        print(
            f"{entries:7d} {width:5d} {select.toffoli_count:11d} "
            f"{swap_table.toffoli_count:9d} "
            f"{auto.variant}/{auto.block_size}/{auto.num_ladder}; "
            f"{native_auto.variant}/{native_auto.block_size}/{native_auto.num_ladder}"
        )
    print(
        "auto minimizes the coherent Toffoli model, preferring SELECT on ties."
    )
    print(
        "It does not enforce a qubit budget. Logical counts are not T counts.")
    print(
        "QROM routing swaps are decomposed; their CCX gates are already included."
    )
    print(f"Maximum executed qubits: {maximum_qubits}; "
          f"elapsed: {time.perf_counter() - start:.2f}s")


if __name__ == "__main__":
    main()

Reversible modular arithmetic

Compare CDKM and QFT arithmetic, use unsigned comparison flags, and restore all work registers. The example checks full complex amplitudes and overflow.

It starts with an explicit threshold oracle: prepare (|2> + |5>)/sqrt(2), compute x >= 3, mark its flag with Z, and uncompute. The printed states show the relative minus sign on x=5 and the restored flag and workspace.

All checks run in the default mode, which prints the demonstrations and a short validation summary. Add --verbose to print each check’s numerical error. A failed check always reports its details and exits with an error.

See also

Coherent circuit primitives for register contracts and interpretation.

"""Reversible modular arithmetic, comparison flags, and clean workspace.

Many quantum algorithms make decisions from numbers stored in qubits: add an
offset, compare a value with a threshold, or mark the values that satisfy a
condition. This example builds those operations as reversible circuits. Its
threshold demonstration computes a yes/no flag, uses that flag to place a
relative minus sign on the matching input, and then undoes the comparison so
the flag and scratch qubits can be reused.

The lessons are to track what every register means, account for wraparound in
fixed-width arithmetic, and undo temporary calculations after using their
result. Addition and subtraction, two constant-arithmetic constructions, and
unsigned comparisons are checked against classical predictions on
superpositions. You should be able to distinguish a correct numerical output
from a complete reversible operation that also preserves phases and restores
its workspace, and read the resource counts as the cost of those requirements.

Run with: python3 reversible_arithmetic.py
Add --verbose to display the numerical error for every validation check.
Register bit zero is least significant. All views passed to an operation
are disjoint. Arithmetic wraps modulo 2**n; it does not report overflow.
"""

import argparse
import os

import numpy as np

import cudaq
from cudaq_algorithms import state_from
from cudaq_algorithms.primitives import (
    add_constant, add_constant_qft, add_register, cmp_ge_constant,
    cmp_ge_constant_qft_shift, cmp_ge_constant_qft_shift_adj, cmp_ge_register,
    subtract_constant, subtract_constant_qft, subtract_register)

ATOL = 1e-10


def complex_ket(size, rng):
    ket = rng.normal(size=size) + 1j * rng.normal(size=size)
    return ket / np.linalg.norm(ket)


def embed(ket, extra_bits):
    expected = np.zeros(len(ket) << extra_bits, dtype=complex)
    expected[:len(ket)] = ket
    return expected


def permute(ket, mapping):
    result = np.zeros_like(ket)
    for index, amplitude in enumerate(ket):
        result[mapping(index)] += amplitude
    return result


def simulate(kernel, ket, *args):
    return np.asarray(cudaq.get_state(kernel, state_from(ket), *args))


@cudaq.kernel
def register_arithmetic(initial: cudaq.State, n: int, inverse: bool,
                        roundtrip: bool):
    operands = cudaq.qvector(initial)  # [a(n) | b(n)]
    carry = cudaq.qvector(1)  # clean on entry and exit
    if inverse:
        subtract_register(operands[0:n], operands[n:2 * n], carry)
    else:
        add_register(operands[0:n], operands[n:2 * n], carry)
    if roundtrip:
        if inverse:
            add_register(operands[0:n], operands[n:2 * n], carry)
        else:
            subtract_register(operands[0:n], operands[n:2 * n], carry)


@cudaq.kernel
def constant_cdkm(initial: cudaq.State, bits: list[int], inverse: bool,
                  roundtrip: bool):
    target = cudaq.qvector(initial)
    work = cudaq.qvector(target.size())
    carry = cudaq.qvector(1)
    if inverse:
        subtract_constant(target, bits, work, carry)
    else:
        add_constant(target, bits, work, carry)
    if roundtrip:
        if inverse:
            add_constant(target, bits, work, carry)
        else:
            subtract_constant(target, bits, work, carry)


@cudaq.kernel
def constant_qft(initial: cudaq.State, constant: int, inverse: bool,
                 roundtrip: bool):
    target = cudaq.qvector(initial)
    if inverse:
        subtract_constant_qft(target, constant)
    else:
        add_constant_qft(target, constant)
    if roundtrip:
        if inverse:
            add_constant_qft(target, constant)
        else:
            subtract_constant_qft(target, constant)


@cudaq.kernel
def register_comparison(initial: cudaq.State, n: int):
    logical = cudaq.qvector(initial)  # [a(n) | b(n) | flag(1)]
    carry = cudaq.qvector(1)
    cmp_ge_register(logical[0:n], logical[n:2 * n], carry,
                    logical[2 * n:2 * n + 1])


@cudaq.kernel
def threshold_cdkm(initial: cudaq.State, bits: list[int], k_is_zero: int,
                   phase: bool):
    logical = cudaq.qvector(initial)  # [x(n) | flag(1)]
    n = logical.size() - 1
    work = cudaq.qvector(n)
    carry = cudaq.qvector(1)
    cmp_ge_constant(logical[0:n], bits, k_is_zero, work, carry,
                    logical[n:n + 1])
    if phase:
        z(logical[n])
        cmp_ge_constant(logical[0:n], bits, k_is_zero, work, carry,
                        logical[n:n + 1])


@cudaq.kernel
def threshold_qft(initial: cudaq.State, constant: int, phase: bool,
                  roundtrip: bool):
    logical = cudaq.qvector(initial)
    n = logical.size() - 1
    cmp_ge_constant_qft_shift(logical[0:n], constant, 0, logical[n:n + 1])
    if phase:
        z(logical[n])
    if roundtrip:
        cmp_ge_constant_qft_shift_adj(logical[0:n], constant, 0,
                                      logical[n:n + 1])


@cudaq.kernel
def threshold_oracle_stages(initial: cudaq.State, complement_bits: list[int],
                            stage: int):
    """Run a prefix of compare, phase mark, uncompute; no measurements."""
    logical = cudaq.qvector(initial)  # [x(n) | flag(1)]
    n = logical.size() - 1
    work = cudaq.qvector(n)
    carry = cudaq.qvector(1)
    if stage >= 1:
        cmp_ge_constant(logical[0:n], complement_bits, 0, work, carry,
                        logical[n:n + 1])
    if stage >= 2:
        z(logical[n])
    if stage >= 3:
        cmp_ge_constant(logical[0:n], complement_bits, 0, work, carry,
                        logical[n:n + 1])


def show_threshold_oracle(verbose=False):
    """Display actual simulated amplitudes for a two-value threshold oracle."""
    n = 3
    modulus = 1 << n
    initial = np.zeros(2 * modulus, dtype=complex)
    initial[[2, 5]] = 1 / np.sqrt(2)
    # cmp_ge_constant takes the n low bits of 2**n - K, least-significant bit
    # first; here 8 - 3 = 5.
    complement_bits = [1, 0, 1]
    snapshots = (
        ("Input", ((2, 0, 1), (5, 0, 1))),
        ("Compare x >= 3", ((2, 0, 1), (5, 1, 1))),
        ("Z on flag", ((2, 0, 1), (5, 1, -1))),
        ("Uncompute", ((2, 0, 1), (5, 0, -1))),
    )
    print("\nA useful comparison: a threshold phase oracle")
    print("Kets below are |x>|flag>; work/carry are shown separately.")
    print("Each row inspects a fresh simulator run of the circuit prefix.")
    for stage, (label, branches) in enumerate(snapshots):
        actual = simulate(threshold_oracle_stages, initial, complement_bits,
                          stage)
        expected = np.zeros_like(actual)
        for value, flag, sign in branches:
            expected[value + (flag << n)] = sign / np.sqrt(2)
        # Compare all eight qubits: every unlisted amplitude must be zero,
        # including any population in the work or carry registers.
        np.testing.assert_allclose(actual,
                                   expected,
                                   rtol=0,
                                   atol=ATOL,
                                   err_msg=f"threshold oracle: {label}")
        terms = []
        for index in np.flatnonzero(np.abs(actual) > ATOL):
            value, flag = index & (modulus - 1), (index >> n) & 1
            sign = "-" if actual[index].real < 0 else "+"
            terms.append(f"{sign} |{value}>|{flag}>")
        expression = " ".join(terms).removeprefix("+ ")
        print(f"  {label:15s}: ({expression}) / sqrt(2)   work/carry=|0000>")
    probabilities = np.abs(actual[:modulus])**2
    np.testing.assert_allclose(probabilities[[2, 5]], [.5, .5],
                               rtol=0,
                               atol=ATOL)
    overlap = abs(np.vdot(embed(initial, n + 1), actual))
    np.testing.assert_allclose(overlap, 0., rtol=0, atol=ATOL)
    print("The values still have probability 1/2 each; only their relative "
          "phase changed.")
    print("The final state is orthogonal to the input, so interference can "
          "distinguish them.")
    print("The flag and all work/carry qubits return to zero; the oracle "
          "can be reused.")
    if verbose:
        print(
            f"All four full-state references verified at tolerance {ATOL:.1e}."
        )


@cudaq.kernel
def resource_add(n: int):
    a = cudaq.qvector(n)
    b = cudaq.qvector(n)
    carry = cudaq.qvector(1)
    add_register(a, b, carry)


@cudaq.kernel
def resource_compare(n: int):
    a = cudaq.qvector(n)
    b = cudaq.qvector(n)
    carry = cudaq.qvector(1)
    flag = cudaq.qvector(1)
    cmp_ge_register(a, b, carry, flag)


@cudaq.kernel
def resource_qft(n: int):
    target = cudaq.qvector(n)
    add_constant_qft(target, 1)


def main():
    parser = argparse.ArgumentParser(description=__doc__.splitlines()[0])
    parser.add_argument(
        "--verbose",
        action="store_true",
        help="show the numerical error for every validation check")
    verbose = parser.parse_args().verbose

    def check(label, actual, expected):
        error = float(np.max(np.abs(actual - expected)))
        passed = np.isfinite(error) and error <= ATOL
        if verbose or not passed:
            print(f"CHECK {label}: {error:.3e} <= {ATOL:.1e} -> "
                  f"{'PASS' if passed else 'FAIL'}")
        if not passed:
            raise AssertionError(label)

    cudaq.set_target(os.environ.get("CUDAQ_DEFAULT_SIMULATOR", "qpp-cpu"))
    rng = np.random.default_rng(7)
    n = 3
    modulus = 1 << n
    mask = modulus - 1
    print("Three-bit unsigned operands; arithmetic is modulo 8.")
    print("All carry/work qubits start at zero and must return to zero.")
    show_threshold_oracle(verbose)
    print("\n a  b   (a+b) mod 8  (b-a) mod 8")
    for a, b in ((1, 2), (3, 7), (7, 7)):
        basis = np.zeros(modulus * modulus, dtype=complex)
        basis[a + (b << n)] = 1
        expected = np.zeros_like(basis)
        expected[a + (((a + b) & mask) << n)] = 1
        check(f"basis addition {a}+{b}",
              simulate(register_arithmetic, basis, n, False, False),
              embed(expected, 1))
        print(f"{a:2d} {b:2d} {((a+b) & mask):13d} {((b-a) & mask):12d}")

    # A nonuniform complex state detects swapped operations and phase errors.
    operands = complex_ket(modulus * modulus, rng)
    for inverse in (False, True):

        def mapping(index):
            a, b = index & mask, index >> n
            output = (b - a if inverse else b + a) & mask
            return a + (output << n)

        expected = embed(permute(operands, mapping), 1)
        name = "subtract" if inverse else "add"
        check(f"register {name}, a preserved, carry clean",
              simulate(register_arithmetic, operands, n, inverse, False),
              expected)
    check("register add/subtract round trip",
          simulate(register_arithmetic, operands, n, False, True),
          embed(operands, 1))

    constant = 3
    bits = [(constant >> bit) & 1 for bit in range(n)]
    target = complex_ket(modulus, rng)
    for inverse in (False, True):
        shift = -constant if inverse else constant
        expected = np.roll(target, shift)
        cdkm = simulate(constant_cdkm, target, bits, inverse, False)
        qft = simulate(constant_qft, target, constant, inverse, False)
        name = "subtract" if inverse else "add"
        check(f"CDKM constant {name}, workspace clean", cdkm,
              embed(expected, n + 1))
        check(f"QFT constant {name}", qft, expected)
        check(f"CDKM/QFT {name} agree", cdkm[:modulus], qft)
    check("CDKM constant round trip",
          simulate(constant_cdkm, target, bits, False, True),
          embed(target, n + 1))
    check("QFT constant round trip",
          simulate(constant_qft, target, constant, False, True), target)

    print("\nComparison flags are XOR-loaded, not assigned.")
    for flag_value in (0, 1):
        logical = np.zeros(2 * len(operands), dtype=complex)
        logical[flag_value * len(operands):(flag_value + 1) *
                len(operands)] = operands

        def comparison(index):
            a, b = index & mask, (index >> n) & mask
            return index ^ (int(a >= b) << (2 * n))

        check(f"register comparison, input flag={flag_value}",
              simulate(register_comparison, logical, n),
              embed(permute(logical, comparison), 1))

    # Both flag amplitudes are nonzero: the XOR contract holds coherently too.
    logical = complex_ket(2 * modulus, rng)
    phase_input = np.zeros_like(logical)
    phase_input[:modulus] = target
    # K=2 and K=5 have complements 6 = [0, 1, 1] and 3 = [1, 1, 0]: reversing
    # either list changes the threshold, so these two detect a wrong bit
    # order. The complements of 0, 3 and 8 read the same in both directions.
    for threshold in (0, 2, constant, 5, modulus):
        complement = (modulus - threshold) & mask
        complement_bits = [(complement >> bit) & 1 for bit in range(n)]
        expected = permute(logical, lambda i: i ^ (int(
            (i & mask) >= threshold) << n))
        check(
            f"CDKM threshold K={threshold}, coherent flag",
            simulate(threshold_cdkm, logical, complement_bits,
                     int(threshold == 0), False), embed(expected, n + 1))
        marked = phase_input.copy()
        for value in range(modulus):
            if value >= threshold:
                marked[value] *= -1
        check(
            f"CDKM compute/phase/uncompute K={threshold}",
            simulate(threshold_cdkm, phase_input, complement_bits,
                     int(threshold == 0), True), embed(marked, n + 1))

    print("\nThe QFT comparator temporarily shifts x; use only its flag.")
    shifted = permute(
        logical, lambda i: (((i & mask) - constant) & mask) + (((i >> n) ^ int(
            (i & mask) >= constant)) << n))
    check("QFT comparator intermediate shift and flag",
          simulate(threshold_qft, logical, constant, False, False), shifted)
    check("QFT comparator adjoint restores x and flag",
          simulate(threshold_qft, logical, constant, False, True), logical)
    marked = phase_input.copy()
    marked[constant:modulus] *= -1
    check("QFT compute/phase/uncompute restores workspace",
          simulate(threshold_qft, phase_input, constant, True, True), marked)
    unchanged_x = permute(logical, lambda i: i ^ modulus)
    check("QFT K=0 is unshifted and constant-true",
          simulate(threshold_qft, logical, 0, False, False), unchanged_x)

    print("\nResource-only width sweep (no input-state preparation):")
    print("width operation       qubits CCX controlled-R1 single-R1")
    for width in (2, 3, 5):
        for name, kernel, qubits, expected_ccx in (("register add",
                                                    resource_add,
                                                    2 * width + 1,
                                                    2 * width - 2),
                                                   ("register cmp",
                                                    resource_compare,
                                                    2 * width + 2,
                                                    2 * width - 1),
                                                   ("QFT add K=1",
                                                    resource_qft, width, 0)):
            resources = cudaq.estimate_resources(kernel, width)
            ccx = resources.count_controls("x", 2)
            if ccx != expected_ccx:
                raise AssertionError(f"{name}: resource contract changed")
            print(f"{width:5d} {name:15s} {qubits:6d} {ccx:3d} "
                  f"{resources.count_controls('r1', 1):13d} "
                  f"{resources.count_controls('r1', 0):9d}")
    print(
        "Zero Toffolis in QFT arithmetic does not imply zero synthesis cost.")
    print("All arithmetic, comparison, and workspace checks passed.")
    print(f"Maximum executed qubits: {2*n+2}")


if __name__ == "__main__":
    main()

Alias sampling and an LCU

Individual validation checks are shown with --verbose. All checks still run by default, and failures are always reported.

Prepare a weighted index marginal, inspect garbage and discretization, then compose a mixed-sign non-Pauli LCU and validate its Walk/QSVT consumers.

See also

Coherent circuit primitives for register contracts and interpretation.

"""Coherent alias sampling: weighted indices, garbage, and a generic LCU.

Quantum models are often written as weighted sums of simple operations, and
later algorithms need a circuit representation of that sum. This example
builds one from an X gate that flips a data qubit and a signed controlled-Z
operation that changes selected amplitudes' signs. An extra index register
acts as a coherent selector, with alias sampling supplying the relative
weights. Preparing the selector, applying its chosen operations, and reversing
the preparation places the weighted sum in the part of the larger circuit
where all its extra qubits are zero.

You should learn why the sampling weights stay positive while a negative
coefficient is supplied by a phase in the selected operation, and why the
sampler's temporary information can remain entangled with the index until
preparation is reversed. The example also distinguishes scratch that must
return to zero from amplitude that legitimately remains outside the encoded
block after selection. Independent NumPy checks compare the requested weights,
their finite-precision replacements, and the resulting matrix before the same
encoding is used by Walk and QSVT.

Run with: python3 alias_sampling_lcu.py
The index has a weighted marginal, while the other registers remain entangled.
Use PREPARE/SELECT/UNPREPARE to obtain the operator's all-zero-ancilla block.
Add --verbose to show individual validation checks; failures are always reported.
"""

from fractions import Fraction
import argparse
import os

import numpy as np

import cudaq
from cudaq_algorithms import LCUBlockEncoding, PhaseSequence, QSVT, Walk, state_from
from cudaq_algorithms import sim_utils as sim
from cudaq_algorithms.primitives import AliasSamplingPrepare

ATOL = 1e-10


def bound_check(label, error, tolerance, *, verbose=False):
    passed = np.isfinite(error) and error <= tolerance
    if verbose or not passed:
        print(f"CHECK {label}: {error:.3e} <= {tolerance:.3e} -> "
              f"{'PASS' if passed else 'FAIL'}")
    if not passed:
        raise AssertionError(label)


def check(label, actual, expected, *, verbose=False):
    bound_check(label,
                float(np.max(np.abs(actual - expected))),
                ATOL,
                verbose=verbose)


def enumerate_tables(sampler):
    """Count classical bin/reference branches, preserving their garbage."""
    m, mu, bins = sampler.num_index, sampler.mu, sampler.num_bins
    unit = 1 << mu
    counts = [0] * bins
    expected = np.zeros(1 << (m + sampler.num_garbage), dtype=complex)
    amplitude = 1 / np.sqrt(bins * unit)
    for original in range(bins):
        for reference in range(unit):
            flag = int(reference >= sampler.keep[original])
            selected = sampler.alias[original] if flag else original
            alias_after_swap = original if flag else sampler.alias[original]
            garbage = (alias_after_swap + (sampler.keep[original] << m) +
                       (reference << (m + mu)) + (flag << (m + 2 * mu)))
            expected[selected + (garbage << m)] += amplitude
            counts[selected] += 1
    fractions = [Fraction(count, bins * unit) for count in counts]
    return np.array([float(value) for value in fractions]), fractions, expected


def preparation_circuit(sampler, *, roundtrip=False, adjoint=False):
    operation = sampler.adjoint_kernel() if adjoint else sampler.kernel()
    unprepare = sampler.adjoint_kernel()
    m, garbage_width = sampler.num_index, sampler.num_garbage

    @cudaq.kernel
    def run():
        index = cudaq.qvector(m)
        garbage = cudaq.qvector(garbage_width)
        operation(index, garbage)
        if roundtrip:
            unprepare(index, garbage)

    return run


def scalar_response(phases, x):
    """Independent two-dimensional model for all-forward projector phases."""
    s = np.sqrt(max(0.0, 1 - x * x))
    step = np.array([[-x, -s], [s, -x]], dtype=complex)
    matrix = np.diag([np.exp(1j * phases[0]), 1.0])
    for phase in phases[1:]:
        matrix = np.diag([np.exp(1j * phase), 1.0]) @ step @ matrix
    return matrix[0, 0]


def main():
    parser = argparse.ArgumentParser(description=__doc__.splitlines()[0])
    parser.add_argument(
        "--verbose",
        action="store_true",
        help="show each validation check (failures are always reported)")
    verbose = parser.parse_args().verbose
    cudaq.set_target(os.environ.get("CUDAQ_DEFAULT_SIMULATOR", "qpp-cpu"))
    sampler = AliasSamplingPrepare([1.0, 0.0, np.sqrt(2)], mu=2)
    print(sampler)
    print("Garbage: [alias | keep | reference | flag | QROM ladder | carry].")
    state = np.asarray(cudaq.get_state(preparation_circuit(sampler)))
    table_probabilities, fractions, expected_state = enumerate_tables(sampler)
    check("complete coherent preparation, including clean ladder/carry",
          state,
          expected_state,
          verbose=verbose)
    # The index is the low register; sum over the high garbage register.
    matrix = state.reshape(1 << sampler.num_garbage, sampler.num_bins)
    marginal = np.sum(np.abs(matrix)**2, axis=0)
    check("index marginal versus integer branch counts",
          marginal,
          table_probabilities,
          verbose=verbose)
    check("public table probabilities",
          sampler.table_probabilities,
          table_probabilities,
          verbose=verbose)
    check("zero-weight and padded bins",
          marginal[[1, 3]],
          np.zeros(2),
          verbose=verbose)
    requested = np.array([1.0, 0.0, np.sqrt(2), 0.0]) / (1 + np.sqrt(2))
    check("ideal probabilities versus the requested weights",
          sampler.probabilities,
          requested,
          verbose=verbose)
    expected_bound = 1.5 / (sampler.num_bins * (1 << sampler.mu))
    check("public per-bin rounding bound",
          sampler.discretization_bound,
          expected_bound,
          verbose=verbose)
    bound_check("ideal-versus-table probability error",
                float(np.max(np.abs(table_probabilities - requested))),
                expected_bound + ATOL,
                verbose=verbose)
    print("\nbin  keep  alias  exact table fraction  marginal   ideal")
    for k, fraction in enumerate(fractions):
        print(f"{k:3d} {sampler.keep[k]:5d} {sampler.alias[k]:6d} "
              f"{str(fraction):>20s} {marginal[k]:9.6f} "
              f"{sampler.probabilities[k]:9.6f}")
    reduced = matrix.T @ matrix.conj()
    print(
        f"Index purity: {np.trace(reduced @ reduced).real:.6f}; "
        f"probability of all-zero garbage: {np.sum(np.abs(matrix[0])**2):.6f}")
    print("A correct marginal does not imply a clean amplitude state.")

    roundtrip = np.asarray(
        cudaq.get_state(preparation_circuit(sampler, roundtrip=True)))
    zero = np.zeros_like(roundtrip)
    zero[0] = 1
    check("PREPARE/adjoint restores every qubit",
          roundtrip,
          zero,
          verbose=verbose)
    for adjoint in (False, True):
        resources = cudaq.estimate_resources(
            preparation_circuit(sampler, adjoint=adjoint))
        expected_ccx = sampler.qrom.toffoli_count + 2 * sampler.mu - 1
        if resources.count_controls("x", 2) != expected_ccx:
            raise AssertionError("PREPARE Toffoli price differs from compiler")
        if resources.count_controls("swap", 1) != sampler.num_index:
            raise AssertionError("PREPARE controlled-swap count differs")
        print(f"{'UNPREPARE' if adjoint else 'PREPARE'}: "
              f"{expected_ccx} CCX + {sampler.num_index} Fredkins; "
              f"{sampler.num_index + sampler.num_garbage} qubits")

    print(
        "\nClassical precision sweep; these extra circuits are not executed:")
    for mu in (1, 2, 4, 6):
        candidate = AliasSamplingPrepare([1.0, 0.0, np.sqrt(2)], mu=mu)
        error = float(np.max(np.abs(candidate.table_probabilities -
                                    requested)))
        bound_check(f"mu={mu} probability bound",
                    error,
                    candidate.discretization_bound + ATOL,
                    verbose=verbose)
        print(f"  mu={mu}: probability error={error:.3e}, "
              f"bound={candidate.discretization_bound:.3e}; "
              f"index={candidate.num_index} garbage={candidate.num_garbage} "
              f"QROM={candidate.qrom.variant}; no monotonic-error assumption")

    print("\nLCU: H = 0.9 X_0 - 0.5 CZ_01, a non-Pauli SELECT body.")
    # Positive weights; the negative sign belongs to the second SELECT body.
    bodies = [[("x", 0)],
              [("and_tt", 0, 1, 0), ("z_w", 0), ("and_tt", 0, 1, 0),
               ("sign", )]]
    encoding = LCUBlockEncoding(num_system=2,
                                weights=[0.9, 0.5],
                                bodies=bodies,
                                mu=2)
    x0 = np.kron(np.eye(2), np.array([[0., 1.], [1., 0.]]))
    negative_cz = -np.diag([1., 1., 1., -1.])
    terms = (x0, negative_cz)
    for term in terms:
        check("SELECT term is Hermitian", term, term.conj().T, verbose=verbose)
        check("SELECT term is an involution",
              term @ term,
              np.eye(4),
              verbose=verbose)
    ideal = 0.9 * x0 + 0.5 * negative_cz
    check("represented weights at mu=2",
          encoding.discretized_weights,
          np.array([0.875, 0.525]),
          verbose=verbose)
    realized = sum(
        weight * term
        for weight, term in zip(encoding.discretized_weights, terms))
    columns = [
        sim.action(encoding, np.ascontiguousarray(column))
        for column in np.eye(4, dtype=complex).T
    ]
    check("complete LCU block versus represented operator",
          np.column_stack(columns),
          realized / encoding.alpha,
          verbose=verbose)
    check("exact one-norm is preserved", encoding.alpha, 1.4, verbose=verbose)
    weight_bound = float(
        np.sum(np.abs(encoding.discretized_weights - np.array([0.9, 0.5]))))
    bound_check("operator discretization versus weight error",
                float(np.linalg.norm(realized - ideal, 2)),
                weight_bound + ATOL,
                verbose=verbose)
    bound_check("weight error versus per-bin bound",
                weight_bound,
                encoding.alpha * encoding.preparation.num_bins *
                encoding.discretization_bound + ATOL,
                verbose=verbose)

    print(
        f"Represented LCU weights: {encoding.discretized_weights}; "
        f"operator rounding error={np.linalg.norm(realized - ideal, 2):.3e}, "
        f"weight-error bound={weight_bound:.3e}")

    rng = np.random.default_rng(7)
    ket = rng.normal(size=4) + 1j * rng.normal(size=4)
    ket /= np.linalg.norm(ket)
    state = np.asarray(
        cudaq.get_state(encoding.encode_kernel(), state_from(ket)))
    # SELECT work occupies the highest bits and is always restored.
    work_start = encoding.num_system + encoding.num_index + encoding.num_garbage
    check("SELECT work is clean",
          state[1 << work_start:],
          np.zeros_like(state[1 << work_start:]),
          verbose=verbose)
    print(f"Probability outside the good ancilla block: "
          f"{1 - np.sum(np.abs(state[:4])**2):.6f}")
    print(
        "UNPREPARE after SELECT generally leaves amplitude outside that block."
    )

    scaled = realized / encoding.alpha
    for power, polynomial in ((1, -scaled), (2,
                                             2 * scaled @ scaled - np.eye(4))):
        actual = sim.good_subspace(
            encoding,
            cudaq.get_state(
                Walk(encoding).kernel(power=power), state_from(ket)))
        check(f"Walk power={power}, T_k(-H_mu/alpha)",
              actual,
              polynomial @ ket,
              verbose=verbose)
    phases = [0.3, -0.4, 0.25, 0.7]
    values, vectors = np.linalg.eigh(scaled)
    response = np.array([scalar_response(phases, value) for value in values])
    expected = vectors @ (response * (vectors.conj().T @ ket))
    check("QSVT versus independent scalar model",
          sim.transform(QSVT(encoding), ket, PhaseSequence(phases)),
          expected,
          verbose=verbose)
    print("This non-Pauli body has no select_observable for odd Walk.moment.")
    print(
        "Use statevector walk blocks here; even reflection observables can grow."
    )
    print(
        f"LCU: {encoding.num_system} system + {encoding.num_index} index + "
        f"{encoding.num_garbage} garbage + {encoding.num_select_work} work qubits."
    )
    print(
        "The standalone sampler can select a QROM strategy; LCU pins SELECT.")
    print(
        "Logical gate counts exclude fault-tolerant synthesis; Fredkins are separate."
    )
    maximum = max(sampler.num_index + sampler.num_garbage,
                  encoding.num_system + encoding.num_ancilla)
    print(f"Maximum executed qubits: {maximum}")
    print("All preparation, LCU block, Walk, and QSVT checks passed.")


if __name__ == "__main__":
    main()