Getting-started walkthrough

An ordered learning path through the library. Each example builds on the one before it, from the single core idea – block-encode a Hamiltonian and walk it – up to bringing your own encoding. Every example verifies its own claims against an independent dense reference, so each script runs to completion or fails loudly.

See also

The user guide pages cover each primitive in depth; Getting Started sets up the installation these scripts assume.

Quickstart: block-encode a Hamiltonian and walk it

The five-minute tour of the core idea. A Hamiltonian is not a circuit, so you block-encode it: PauliLCU hides H / alpha inside a larger unitary on a few ancilla qubits, and the qubitization Walk turns powers of that unitary into Chebyshev moments checked against a dense matrix.

"""Example 1 — Quickstart: block-encode a Hamiltonian and walk it.

The five-minute tour of the core idea. A Hamiltonian H is not a circuit
(it is not unitary), so you *block-encode* it: PauliLCU hides H / alpha
inside a bigger unitary on a few ancilla qubits. The qubitization Walk
then turns powers of that unitary into Chebyshev polynomials of H --
measured as expectation values, the raw data spectral algorithms consume.

Everything downstream (examples 2-8) is built on these three objects:
PauliLCU (the block encoding), Walk (qubitization), and the observable
`moment` path. Here we build them and check the moments against a dense
matrix, in the house style: every claim verified against an independent
reference.

Run: python3 01_quickstart_block_encoding.py
"""

from __future__ import annotations

import os

import cudaq
import numpy as np

from cudaq_algorithms import PauliLCU, Walk

# The convention: read docs/sphinx/conventions.rst. The walk returns +<T_k(H/alpha)>.
_PAULIS = {
    "I": np.eye(2, dtype=complex),
    "X": np.array([[0, 1], [1, 0]], dtype=complex),
    "Y": np.array([[0, -1j], [1j, 0]]),
    "Z": np.diag([1.0, -1.0]).astype(complex),
}


def dense_hamiltonian(terms: dict) -> np.ndarray:
    """Dense matrix of a Pauli sum (little-endian: qubit 0 is the low bit,
    so word[0] is the rightmost tensor factor -- matching CUDA-Q)."""
    matrix = 0
    for word, coefficient in terms.items():
        factor = np.array([[1]], dtype=complex)
        for label in word:
            factor = np.kron(_PAULIS[label], factor)
        matrix = matrix + coefficient * factor
    return matrix


def chebyshev(x: np.ndarray, k: int) -> np.ndarray:
    """T_k(x) for a matrix argument, by the Chebyshev recurrence."""
    if k == 0:
        return np.eye(x.shape[0], dtype=complex)
    previous, current = np.eye(x.shape[0], dtype=complex), x
    for _ in range(2, k + 1):
        previous, current = current, 2 * x @ current - previous
    return current


def main() -> int:
    cudaq.set_target(os.environ.get("CUDAQ_DEFAULT_SIMULATOR", "qpp-cpu"))

    # 1. Block-encode a Hamiltonian given as {pauli_word: coefficient}.
    terms = {"ZZ": 0.5, "XI": 0.3, "IX": 0.3}
    encoding = PauliLCU(terms)
    print(f"system qubits : {encoding.num_system}")
    print(f"ancillas      : {encoding.num_ancilla}")
    print(f"alpha (1-norm): {encoding.alpha:.6f}   # W encodes H / alpha")

    # 2. Build the qubitization walk over that encoding.
    walk = Walk(encoding)

    # 3. Measure Chebyshev moments <T_k(H/alpha)> from a chosen state.
    rng = np.random.default_rng(0)
    state = rng.normal(size=1 << encoding.num_system).astype(np.complex128)
    state /= np.linalg.norm(state)
    moments = walk.moments(state, 4)

    # 4. Verify against the dense matrix -- the numbers must agree.
    x = dense_hamiltonian(terms) / encoding.alpha
    print("\n k   walk.moment    dense <T_k(H/alpha)>")
    for k, measured in enumerate(moments):
        reference = float(np.real(state.conj() @ chebyshev(x, k) @ state))
        print(f" {k}   {measured:+.8f}    {reference:+.8f}")
        assert abs(measured - reference) < 1e-10

    print("\nOK — the walk reproduces Chebyshev polynomials of H to machine "
          "precision.")
    return 0


if __name__ == "__main__":
    raise SystemExit(main())

Hamiltonian simulation, two independent ways

Compute the time evolution exp(-iHt)|psi> with two different primitives and check both against dense linear algebra: QSVT with Jacobi-Anger phase factors, and Trotter product formulas with an error-vs-steps trade-off. Because the two constructions are completely different, their agreement is a strong test.

"""Example 2 — Hamiltonian simulation, two independent ways.

Compute exp(-i H t)|psi> with two different primitives and check both
against dense linear algebra:

  * QSVT  -- block-encode H, apply a polynomial approximation of exp(-ixt)
             built from Jacobi-Anger phase factors (generated by QSPPACK).
  * Trotter -- a product formula, no block encoding or ancillas, with the
               error-vs-steps trade-off and a resource estimate.

Because the two constructions are completely different, agreeing with the
same dense reference means they cross-validate each other. This is the
"primitives compose into applications" story made concrete.

Prerequisite: qsppack (installed with the wheel). Run: python3 02_hamiltonian_simulation.py
"""

from __future__ import annotations

import os

import cudaq
import numpy as np
from scipy.linalg import expm

from cudaq_algorithms import (PauliLCU, PhaseSequence, QSVT, Trotter,
                              recover_real_time_evolution)
from cudaq_algorithms import sim_utils as sim

_PAULIS = {
    "I": np.eye(2, dtype=complex),
    "X": np.array([[0, 1], [1, 0]], dtype=complex),
    "Z": np.diag([1.0, -1.0]).astype(complex),
}


def dense(terms, num_qubits):
    # Little-endian, matching CUDA-Q: word[i] acts on qubit i, and qubit 0
    # is the least-significant bit, so build P[word[0]] as the rightmost
    # tensor factor by kron-ing each successive Pauli on the left.
    matrix = np.zeros((1 << num_qubits, 1 << num_qubits), dtype=complex)
    for word, coefficient in terms.items():
        factor = np.array([[1]], dtype=complex)
        for label in word:
            factor = np.kron(_PAULIS[label], factor)
        matrix = matrix + coefficient * factor
    return matrix


def jacobi_anger_phases(tau, degree):
    """cos/sin QSP phases for exp(-i tau x) via Jacobi-Anger + QSPPACK."""
    import contextlib
    import io

    import qsppack
    from scipy import special

    cos_coeffs = np.array([0.5 * special.jv(0, tau)] +
                          [((-1)**k) * special.jv(2 * k, tau)
                           for k in range(1, degree // 2 + 1)])
    sin_coeffs = np.array([((-1)**k) * special.jv(2 * k + 1, tau)
                           for k in range(degree // 2)])
    options = {
        "criteria": 1e-12,
        "method": "Newton",
        "typePhi": "full",
        "useReal": True
    }
    with contextlib.redirect_stdout(io.StringIO()):  # hush the QSP solver
        cos_phases, _ = qsppack.solve(cos_coeffs, 0, {
            **options, "targetPre": True
        })
        sin_phases, _ = qsppack.solve(sin_coeffs, 1, {
            **options, "targetPre": False
        })
    return [float(p) for p in cos_phases], [float(p) for p in sin_phases]


def main() -> int:
    cudaq.set_target(os.environ.get("CUDAQ_DEFAULT_SIMULATOR", "qpp-cpu"))

    terms = {"ZZ": 0.7, "XI": 0.4, "IX": 0.4, "ZI": 0.31}
    num_qubits = 2
    time = 0.8
    matrix = dense(terms, num_qubits)

    rng = np.random.default_rng(1)
    psi = rng.normal(size=1 << num_qubits).astype(np.complex128)
    psi /= np.linalg.norm(psi)
    exact = expm(-1j * matrix * time) @ psi

    # -- QSVT --------------------------------------------------------------
    encoding = PauliLCU(terms)
    transformer = QSVT(encoding)
    tau = encoding.alpha * time
    cos_phases, sin_phases = jacobi_anger_phases(tau, degree=16)
    cos_state = sim.transform(transformer, psi,
                              PhaseSequence(cos_phases, convention="qsp"))
    sin_state = sim.transform(transformer, psi,
                              PhaseSequence(sin_phases, convention="qsp"))
    qsvt_state = recover_real_time_evolution(cos_state, sin_state, cos_phases,
                                             sin_phases)
    qsvt_error = float(np.max(np.abs(qsvt_state - exact)))
    print(f"QSVT   (degree 16) : max amplitude error {qsvt_error:.2e}")

    # -- Trotter -----------------------------------------------------------
    evolution = Trotter(terms)
    print("Trotter (order 2)  : error shrinks as steps^-2")
    for steps in (1, 2, 4, 8, 16):
        trotter_state = sim.evolve(evolution, psi, time, steps=steps, order=2)
        error = float(np.max(np.abs(trotter_state - exact)))
        print(f"     steps={steps:2d}   max amplitude error {error:.2e}")
    resources = evolution.resources(steps=16, order=2)
    print(f"   resource estimate at 16 steps: "
          f"{resources.pauli_rotations} Pauli rotations")

    assert qsvt_error < 1e-6
    print("\nOK — two different circuits, one physics: both reproduce "
          "exp(-iHt)|psi>.")
    return 0


if __name__ == "__main__":
    raise SystemExit(main())

From a molecule to its ground-state energy

The full classical to quantum to classical loop, end to end: PySCF mean field, Jordan-Wigner qubit Hamiltonian, PauliLCU block encoding, Walk moments, and a classical Krylov solve for the ground-state energy checked against FCI.

"""Example 3 — From a molecule to its ground-state energy.

The full classical -> quantum -> classical loop, end to end:

    PySCF mean field
      -> chemistry.from_pyscf         (chemist (pq|rs) MO integrals)
      -> chemistry.qubit_hamiltonian  (Jordan-Wigner -> SpinOperator)
      -> PauliLCU                     (block-encode H / alpha)
      -> Walk.moments                 (Chebyshev moments <T_k(H/alpha)>)
      -> classical Krylov solve       (quantum exact Lanczos)
      -> ground-state energy, checked against FCI.

This is the example to read first if you care about chemistry: it shows
how integrals become a qubit Hamiltonian, how the qubitization walk turns
into measured moments, and how those moments feed a real ground-state
algorithm. Every number is checked against an independent reference (FCI).

Reference: Kirby, Motta, Mezzacapo, "Exact and efficient Lanczos method
on a quantum computer", Quantum 7, 1018 (2023), arXiv:2208.00567.

Prerequisite: PySCF (`pip install pyscf`). Run: python3 03_chemistry_to_ground_state.py
"""

from __future__ import annotations

import os

import cudaq
import numpy as np

from cudaq_algorithms import PauliLCU, Walk, chemistry


def krylov_matrices(moments: np.ndarray, dimension: int):
    """Overlap S and scaled-Hamiltonian H~ from Chebyshev moments.

    The Krylov basis is |phi_i> = T_i(H/alpha)|ref>. With
    mu_k = <ref|T_k(H/alpha)|ref> and the Chebyshev product identities
    T_i T_j = (T_{i+j} + T_{|i-j|}) / 2 and x T_j = (T_{j+1} + T_{|j-1|}) / 2,
    both matrices are just combinations of the measured moments.
    """
    mu = moments
    overlap = np.empty((dimension, dimension))
    scaled = np.empty((dimension, dimension))
    for i in range(dimension):
        for j in range(dimension):
            overlap[i, j] = 0.5 * (mu[i + j] + mu[abs(i - j)])
            scaled[i,
                   j] = 0.25 * (mu[i + j + 1] + mu[abs(i - j - 1)] +
                                mu[i + abs(j - 1)] + mu[abs(i - abs(j - 1))])
    return overlap, scaled


def ground_eigenvalue(scaled, overlap, cutoff=1e-8):
    """Solve the projected generalized eigenproblem, dropping null directions."""
    values, vectors = np.linalg.eigh(overlap)
    keep = values > cutoff
    transform = vectors[:, keep] / np.sqrt(values[keep])
    projected = transform.T @ scaled @ transform
    return float(np.linalg.eigvalsh(projected).min())


def main() -> int:
    cudaq.set_target(os.environ.get("CUDAQ_DEFAULT_SIMULATOR", "qpp-cpu"))

    try:
        from pyscf import fci, gto, scf
    except ImportError:
        print("This example needs PySCF:  pip install pyscf")
        return 0

    # 1. Converged restricted mean field for H2 / STO-3G.
    geometry = [("H", (0.0, 0.0, 0.0)), ("H", (0.0, 0.0, 0.7474))]
    mol = gto.M(atom=geometry, basis="sto-3g", symmetry=False)
    mean_field = scf.RHF(mol).run(verbose=0)

    # 2. Extract chemist-notation MO integrals + nuclear repulsion.
    one_body, eri, nuclear_repulsion = chemistry.from_pyscf(mean_field)
    print(f"molecule            : H2 / STO-3G  ({one_body.shape[0]} spatial "
          f"orbitals, {2 * one_body.shape[0]} qubits)")

    # 3. Jordan-Wigner qubit Hamiltonian (nuclear repulsion kept classical).
    hamiltonian = chemistry.qubit_hamiltonian(one_body, eri, scalar_offset=0.0)

    # 4. Block-encode it and build the qubitization walk.
    encoding = PauliLCU(hamiltonian)
    walk = Walk(encoding)
    print(f"block encoding      : {hamiltonian.term_count} Pauli terms, "
          f"alpha = {encoding.alpha:.6f}, {encoding.num_ancilla} ancillas")

    # 5. Measure Chebyshev moments from the Hartree-Fock reference.
    #    (HF determinant: the lowest `num_electrons` qubits occupied.)
    reference = np.zeros(1 << encoding.num_system, dtype=np.complex128)
    reference[(1 << mol.nelectron) - 1] = 1.0
    krylov_dimension = 4
    moments = np.asarray(walk.moments(reference, 2 * krylov_dimension))
    print(f"Chebyshev moments   : {np.array2string(moments, precision=4)}")

    # 6. Classical Krylov solve -> QEL energy (add nuclear repulsion back).
    overlap, scaled = krylov_matrices(moments, krylov_dimension)
    qel_energy = ground_eigenvalue(scaled, overlap) * encoding.alpha \
        + nuclear_repulsion

    # 7. Check against FCI.
    fci_energy = float(fci.FCI(mean_field).kernel()[0])
    print(f"\nQEL ground energy   : {qel_energy:.10f} Ha")
    print(f"FCI reference       : {fci_energy:.10f} Ha")
    print(f"|error|             : {abs(qel_energy - fci_energy):.2e} Ha")
    assert abs(qel_energy - fci_energy) < 1e-8
    print("\nOK — the qubitization moments reproduce the exact ground state.")
    return 0


if __name__ == "__main__":
    raise SystemExit(main())

Double factorization and the BlockEncoding protocol

Double factorization rewrites the two-electron tensor as a sum of low-rank leaves, giving a compression dial you can watch trade accuracy for a cheaper block encoding. The same pipeline scales to larger molecules and plugs into the structural BlockEncoding protocol shared by every consumer.

"""Example 4 — Double factorization and the BlockEncoding protocol.

Three ideas, built on real molecules from PySCF:

  A. The compression dial (H2). Double factorization rewrites the
     two-electron tensor as a sum of low-rank "leaves". Keep fewer leaves
     and you trade accuracy for a cheaper block encoding -- a knob you can
     watch, checked against the exact FCI energy at every setting.

  B. It scales, and DF is compact (N2, 20 qubits). The same pipeline runs
     at 20 qubits. There, a flat Pauli LCU block-encodes the Hamiltonian
     as a SELECT over ~3000 Pauli strings; double factorization encodes
     the *same* operator with a few dozen structured leaves. Far fewer
     building blocks, comparable normalization.

  C. Polymorphism through the protocol. `PauliLCU` and
     `DoubleFactorizedEncoding` are unrelated classes, but both satisfy
     `BlockEncoding` -- so `Walk` and `QSVT` consume either with identical
     code.

Prerequisite: PySCF (`pip install pyscf`). Takes a few seconds (the N2
FCI reference is the slow part). Run: python3 04_double_factorization_and_the_protocol.py
"""

from __future__ import annotations

import os
import pathlib
import sys

import cudaq

from cudaq_algorithms import (BlockEncoding, PauliLCU, QSVT, Walk, chemistry)
from cudaq_algorithms import double_factorization as df

# The double-factorized encoding is the worked BlockEncoding example that
# lives beside this script (CUDA-Q kernels need real .py files, so a plain
# path-based import works).
sys.path.insert(0, str(pathlib.Path(__file__).resolve().parent))
from df_encoding import DoubleFactorizedEncoding


def mean_field(atom: str, basis: str = "sto-3g"):
    from pyscf import gto, scf

    mol = gto.M(atom=atom, basis=basis, symmetry=False)
    return mol, scf.RHF(mol).run(verbose=0)


def fci_energy(one_body, eri, num_electrons, nuclear_repulsion) -> float:
    """Exact (FCI) total energy of the given MO integrals, via PySCF."""
    from pyscf import fci

    electronic, _ = fci.direct_spin1.kernel(one_body, eri, one_body.shape[0],
                                            num_electrons)
    return float(electronic) + nuclear_repulsion


def main() -> int:
    cudaq.set_target(os.environ.get("CUDAQ_DEFAULT_SIMULATOR", "qpp-cpu"))

    try:
        import pyscf  # noqa: F401
    except ImportError:
        print("This example needs PySCF:  pip install pyscf")
        return 0

    # -- A. The compression dial (H2) ------------------------------------
    mol, mf = mean_field("H 0 0 0; H 0 0 0.7414")
    one_body, eri, e_nuc = chemistry.from_pyscf(mf)
    exact = fci_energy(one_body, eri, mol.nelectron, e_nuc)
    full = df.explicit_double_factorization(eri, threshold=0.0)
    print(f"A. H2/STO-3G compression dial (exact FCI = {exact:.6f} Ha)")
    print(f"   {'leaves':>6} {'tensor error':>13} {'alpha':>8} "
          f"{'E error (Ha)':>13}")
    for num_leaves in range(1, full.num_leaves + 1):
        truncated = df.explicit_double_factorization(eri,
                                                     max_num_leaves=num_leaves)
        reconstructed_eri = df.reconstruct_eri(truncated)
        alpha = PauliLCU(
            chemistry.qubit_hamiltonian(one_body,
                                        reconstructed_eri,
                                        scalar_offset=e_nuc)).alpha
        energy = fci_energy(one_body, reconstructed_eri, mol.nelectron, e_nuc)
        print(
            f"   {num_leaves:>6} {df.factorization_error(eri, truncated):>13.2e}"
            f" {alpha:>8.4f} {energy - exact:>+13.2e}")

    # -- B. It scales, and DF is compact (N2, 20 qubits) -----------------
    mol, mf = mean_field("N 0 0 0; N 0 0 1.09")
    one_body, eri, e_nuc = chemistry.from_pyscf(mf)
    hamiltonian = chemistry.qubit_hamiltonian(one_body,
                                              eri,
                                              scalar_offset=e_nuc)
    flat = PauliLCU(hamiltonian)
    factorization = df.explicit_double_factorization(eri, threshold=0.0)
    dfe = DoubleFactorizedEncoding(one_body,
                                   factorization,
                                   scalar_offset=e_nuc)
    print(f"\nB. N2/STO-3G on {hamiltonian.qubit_count} qubits: "
          f"same Hamiltonian, two block encodings")
    print(f"   flat PauliLCU : alpha = {flat.alpha:6.2f}  over "
          f"{hamiltonian.term_count} Pauli terms")
    print(f"   double factn  : alpha = {dfe.alpha:6.2f}  over "
          f"{factorization.num_leaves} leaves")
    print("   -> DF encodes the same operator with ~50x fewer SELECT building "
          "blocks,\n      at a comparable one-norm (in a minimal basis the DF "
          "rank is near\n      full, so alpha barely drops; larger bases "
          "compress far more).")

    # -- C. One protocol, two encodings ----------------------------------
    print(
        "\nC. both are BlockEncodings, so Walk/QSVT consume either unchanged")
    for name, encoding in [("PauliLCU", flat),
                           ("DoubleFactorizedEncoding", dfe)]:
        assert isinstance(encoding, BlockEncoding)
        Walk(encoding)
        QSVT(encoding)  # the exact same construction works on both
        print(f"   {name:26s} system={encoding.num_system} "
              f"ancilla={encoding.num_ancilla} -> Walk + QSVT built")

    print("\nOK — pyscf integrals in, block encodings out; DF is the compact, "
          "scalable one, and both plug into the same primitives (example 6 "
          "shows how to add your own).")
    return 0


if __name__ == "__main__":
    raise SystemExit(main())

State preparation and injection

Every primitive factory (Walk, QSVT, Trotter) accepts a state_prep kernel argument. Pass one and the factory returns a zero-argument, hardware-shaped circuit with no statevector crossing the API boundary – the seam that makes the primitives hardware-ready and the seam a tensor-network state-prep compiler would plug into.

"""Example 5 — State preparation and injection.

Every primitive factory (Walk, QSVT, Trotter) takes a `state_prep`
argument: a `(qubits: qview)` CUDA-Q kernel that prepares the register.
Pass one and the factory returns a *zero-argument* circuit -- no
`cudaq.State` argument, no statevector crossing the API boundary -- that
you can sample directly
and hand to synthesis. This is the seam that makes the primitives
hardware-ready, and the seam an MPS/tensor-network state-prep compiler
would plug into.

Two things this shows:
  A. The injection contract: an injected walk is a zero-argument kernel,
     and its measured moment matches the data-path (cudaq.State) form.
  B. Any `(qubits: qview)` kernel qualifies -- including a Givens
     Slater-determinant prep produced from an orbital-coefficient matrix.

Run: python3 05_state_prep_and_injection.py
"""

from __future__ import annotations

import os

import cudaq
import numpy as np

from cudaq_algorithms import PauliLCU, Walk, stateprep


# A state-prep kernel is just a `(qubits: qview)` device kernel. This one
# prepares |...01> -- one electron in the lowest orbital (a 2-qubit
# Hartree-Fock reference).
@cudaq.kernel
def hartree_fock_prep(qubits: cudaq.qview):
    x(qubits[0])


def main() -> int:
    cudaq.set_target(os.environ.get("CUDAQ_DEFAULT_SIMULATOR", "qpp-cpu"))

    encoding = PauliLCU({"ZZ": 0.5, "XI": 0.3, "IX": 0.3, "ZI": 0.2})
    walk = Walk(encoding)

    # -- A. Injection contract -------------------------------------------
    # With state_prep, walk.kernel returns a ZERO-ARGUMENT circuit: prepare
    # the reference, then apply W^3. Sample it like any kernel.
    injected = walk.kernel(power=3, state_prep=hartree_fock_prep)
    counts = cudaq.sample(injected, shots_count=2000)
    print("A. injected walk is a zero-argument, directly sampleable circuit")
    print(f"   sampled {len(counts)} bitstrings, e.g. "
          f"{dict(list(counts.items())[:3])}")

    # The observable path also accepts state_prep. It must agree with the
    # data path, where we hand in the same reference as a statevector.
    reference = np.zeros(1 << encoding.num_system, dtype=np.complex128)
    reference[1] = 1.0  # |01>, matching x(qubits[0])
    moment_injected = walk.moment(None, 3, state_prep=hartree_fock_prep)
    moment_data = walk.moment(reference, 3)
    print(f"   moment via injection : {moment_injected:+.10f}")
    print(f"   moment via data path : {moment_data:+.10f}")
    assert abs(moment_injected - moment_data) < 1e-10
    print("   -> identical: injection changes how the state enters, not the "
          "physics")

    # -- B. Any (qubits: qview) kernel qualifies -------------------------
    # A Givens Slater determinant of an orbital-coefficient matrix Q is
    # also just a (qubits: qview) kernel -- built from Q, injectable the
    # same way. Its computational-basis amplitudes are the minors of Q.
    orbital_coefficients = np.array([[0.6, 0.0], [0.8, 0.0], [0.0, 0.6],
                                     [0.0, 0.8]])
    schedule = stateprep.make_givens_rotation_schedule(orbital_coefficients)
    slater_prep = stateprep.slater_determinant_kernel(schedule)

    @cudaq.kernel
    def prepare_slater():
        qubits = cudaq.qvector(4)
        slater_prep(qubits)

    slater_counts = cudaq.sample(prepare_slater, shots_count=4000)
    print("\nB. a Givens Slater-determinant prep is the same kind of kernel")
    print(f"   4 spin-orbitals, 2 electrons -> occupied-pair bitstrings:")
    for bits, n in sorted(slater_counts.items(), key=lambda kv: -kv[1])[:4]:
        print(f"     |{bits}>  {n/4000:.3f}")
    print("   (these frequencies are |det Q[S,:]|^2 -- an entangled "
          "reference, injectable exactly like the HF one)")
    return 0


if __name__ == "__main__":
    raise SystemExit(main())

Bring your own block encoding

Walk and QSVT are generic over the BlockEncoding protocol: any object exposing the right members works, with no inheritance. This example implements the protocol from scratch for a two-term single-qubit LCU and watches the walk measure correct Chebyshev moments on it.

"""Example 6 — Bring your own block encoding.

`Walk` and `QSVT` are generic over the `BlockEncoding` protocol: any
object exposing the right members works, with no inheritance and no
changes to the primitives. This example implements the protocol from
scratch for the simplest nontrivial case -- a two-term LCU of a single
qubit, H = a*X + b*Z -- and shows the qubitization `Walk` measuring
correct Chebyshev moments on it.

The protocol (see docs and `block_encoding.py`): three sizes
(`num_system`, `num_ancilla`, `alpha`) plus kernel factories. The walk
step convention, mirrored below, is: SELECT, then reflect about the
PREPARE state. Get that right and everything else is inherited.

Run: python3 06_bring_your_own_encoding.py
"""

from __future__ import annotations

import math
import os

import cudaq
import numpy as np

from cudaq_algorithms import BlockEncoding, Walk
from cudaq_algorithms.common_kernels import reflect_about_zero


class TwoTermLCU:
    """Block encoding of H = a*X + b*Z (a, b > 0) on one system qubit.

    PREPARE puts the single ancilla into (sqrt(a), sqrt(b)) / sqrt(alpha);
    SELECT applies X when the ancilla is |0> and Z when it is |1>. Then
    <0|B^dag SELECT B|0> = (a*X + b*Z) / alpha = H / alpha.
    """

    def __init__(self, a: float, b: float):
        self.a, self.b = float(a), float(b)
        self.num_system = 1
        self.num_ancilla = 1
        self.alpha = self.a + self.b
        # PREPARE angle: ry(theta)|0> = (cos, sin) = (sqrt(a), sqrt(b))/sqrt(alpha)
        self._theta = 2.0 * math.atan2(math.sqrt(self.b), math.sqrt(self.a))

    # -- sizes -----------------------------------------------------------
    # num_system, num_ancilla, alpha are plain attributes (set above).

    # -- kernel factories (data captured at factory time) ----------------
    def prepare_kernel(self):
        theta = self._theta

        @cudaq.kernel
        def prepare(ancilla: cudaq.qview):
            ry(theta, ancilla[0])

        return prepare

    def unprepare_kernel(self):
        theta = self._theta

        @cudaq.kernel
        def unprepare(ancilla: cudaq.qview):
            ry(-theta, ancilla[0])

        return unprepare

    def _select_kernel(self):

        @cudaq.kernel
        def select(ancilla: cudaq.qview, system: cudaq.qview):
            # |0><0| (x) X : X on system, controlled on ancilla == 0
            x(ancilla[0])
            x.ctrl(ancilla[0], system[0])
            x(ancilla[0])
            # |1><1| (x) Z : Z on system, controlled on ancilla == 1
            z.ctrl(ancilla[0], system[0])

        return select

    def walk_step_kernel(self):
        theta = self._theta
        select = self._select_kernel()

        @cudaq.kernel
        def walk_step(ancilla: cudaq.qview, system: cudaq.qview):
            select(ancilla, system)  # SELECT
            ry(-theta, ancilla[0])  # reflect about PREPARE state:
            reflect_about_zero(ancilla)  #   B (I - 2|0><0|) B^dag
            ry(theta, ancilla[0])

        return walk_step

    def adjoint_walk_step_kernel(self):
        theta = self._theta
        select = self._select_kernel()

        @cudaq.kernel
        def adjoint_walk_step(ancilla: cudaq.qview, system: cudaq.qview):
            ry(-theta, ancilla[0])  # reflection first (self-adjoint),
            reflect_about_zero(ancilla)
            ry(theta, ancilla[0])
            select(ancilla, system)  # then SELECT (self-adjoint)

        return adjoint_walk_step

    def apply_kernel(self):
        theta = self._theta
        select = self._select_kernel()

        @cudaq.kernel
        def apply(ancilla: cudaq.qview, system: cudaq.qview):
            ry(theta, ancilla[0])
            select(ancilla, system)
            ry(-theta, ancilla[0])

        return apply

    # -- hooks left to the reader ---------------------------------------
    # The controlled variants (for QPE) follow the same pattern with the
    # control on qubit 0 of a combined register; select_observable enables
    # odd moments. Omitted here -- even moments below need none of them.
    def controlled_apply_kernel(self):
        raise NotImplementedError("exercise: controlled U_A for QPE")

    def controlled_walk_step_kernel(self):
        raise NotImplementedError("exercise: controlled W for QPE")

    def controlled_adjoint_walk_step_kernel(self):
        raise NotImplementedError("exercise: controlled W-dagger")

    def select_observable(self):
        raise NotImplementedError("exercise: enables odd Chebyshev moments")


def dense_moment(a, b, k, state):
    """Reference <T_k(H/alpha)> for H = a*X + b*Z."""
    X = np.array([[0, 1], [1, 0]], dtype=complex)
    Z = np.diag([1.0, -1.0]).astype(complex)
    x = (a * X + b * Z) / (a + b)
    previous, current = np.eye(2, dtype=complex), x
    if k == 0:
        current = np.eye(2, dtype=complex)
    for _ in range(2, k + 1):
        previous, current = current, 2 * x @ current - previous
    return float(np.real(state.conj() @ current @ state))


def main() -> int:
    cudaq.set_target(os.environ.get("CUDAQ_DEFAULT_SIMULATOR", "qpp-cpu"))

    encoding = TwoTermLCU(a=0.6, b=0.9)

    # It satisfies the protocol -- structurally, no base class involved.
    print(f"isinstance(encoding, BlockEncoding) : "
          f"{isinstance(encoding, BlockEncoding)}")
    print(f"num_system / num_ancilla / alpha    : "
          f"{encoding.num_system} / {encoding.num_ancilla} / {encoding.alpha}")

    # Walk consumes it with no changes. Measure even Chebyshev moments
    # (even orders use the geometry-derived reflection observable, so they
    # need no encoding-specific observable hook).
    walk = Walk(encoding)
    state = np.array([0.8, 0.6], dtype=np.complex128)  # a chosen |psi>

    print("\n k   Walk.moment    dense <T_k(H/alpha)>")
    ok = True
    for k in (0, 2, 4, 6):
        measured = walk.moment(state, k)
        reference = dense_moment(encoding.a, encoding.b, k, state)
        flag = "ok" if abs(measured - reference) < 1e-10 else "MISMATCH"
        ok = ok and flag == "ok"
        print(f" {k}   {measured:+.8f}    {reference:+.8f}   {flag}")

    assert ok
    print("\nOK — a from-scratch encoding drops into Walk unchanged. That is "
          "the extension point: bring an encoding, inherit the primitives.")
    return 0


if __name__ == "__main__":
    raise SystemExit(main())

Solve a linear system with QSVT

The task is to solve a linear system: given a matrix A and an input vector b, find the vector x satisfying A x = b. QSVT approaches this by applying a polynomial that approximates the reciprocal of each eigenvalue of the encoded matrix. This example carries that idea through a small dense solve and a sparse solve, with independent NumPy solutions providing concrete targets for the circuit output.

You should learn why eigenvalues near zero make inversion harder, why the quantum circuit implements a scaled approximation to the inverse, and how known input and encoding scales recover the solution’s magnitude. The comparisons separate matrix rounding, polynomial approximation, and circuit error, and check both the output vector and its residual in A x = b. Reading all coordinates from a simulator is part of this demonstration; the example explains what would still be needed to extract useful information from a quantum state on hardware.

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

The payoff of QSVT’s “pick a polynomial” design: example 2 approximated exp(-ixt) for time evolution; swap the phase sequence for one approximating 1/x and the same PauliLCU + QSVT machinery becomes a quantum linear solver – the QSVT reading of HHL. A 5x5 symmetric positive-definite system is padded to three qubits, block-encoded, and inverted with a Childs-Kothari-Somma polynomial. Degree depends on the normalized minimum eigenvalue, including the encoding’s alpha. The known input, polynomial, and encoding scales restore physical units without fitting to the NumPy solution.

A second 2x2 SPD case uses the matrix-data sparse constructor at three value-angle bits, generates fresh phases for its represented spectrum, and executes a full-vector inverse and residual check. Quantization, polynomial, phase-synthesis, and circuit errors have separate budgets. Both cases use simulator full-state real-response extraction; the raw complex good-block norm is not an isolated inverse-filter success probability. See Block-encoding examples for the sparse-access introduction. Verified against independent numpy.linalg.solve references. Requires qsppack for the phase factors, like example 2. The application in Sparse matrix inversion for heat diffusion below derives a banded sparse inverse from a physical model and compares every temperature coordinate with NumPy.

"""Example 7 — Invert a 5x5 matrix with QSVT (the quantum linear solver).

The task is to solve a linear system: given a matrix A and an input vector b,
find the vector x satisfying A x = b. QSVT approaches this by applying a
polynomial that approximates the reciprocal of each eigenvalue of the encoded
matrix. This example carries that idea through a small dense solve and a
sparse solve, with independent NumPy solutions providing concrete targets for
the circuit output.

You should learn why eigenvalues near zero make inversion harder, why the
quantum circuit implements a scaled approximation to the inverse, and how
known input and encoding scales recover the solution's magnitude. The
comparisons separate matrix rounding, polynomial approximation, and circuit
error, and check both the output vector and its residual in A x = b. Reading
all coordinates from a simulator is part of this demonstration; the example
explains what would still be needed to extract useful information from a
quantum state on hardware.

Time evolution (example 2) applied a QSVT polynomial approximating
exp(-ixt). Swap the polynomial and the same machinery solves A x = b:
apply a polynomial approximating 1/x to the block-encoded matrix and the
good-subspace state is proportional to A^-1 b. This is the QSVT reading of
HHL, and it reuses PauliLCU + QSVT unchanged -- only the phase sequence is
new.

Three ideas carry the example:

  * Embedding. A is 5x5; a register holds 2^k amplitudes. Pad A to the
    next power of two (8x8, three qubits) with an identity block. The pad
    is block-diagonal, so with b supported on the first five coordinates
    the solution never leaks into the padding.
  * The polynomial. 1/x is singular at 0, so it can only be approximated
    away from zero, on the spectrum's domain [x_min, x_max]. We use the
    Childs-Kothari-Somma closed form: (1 - (1-x^2)^b)/x is an odd
    polynomial (degree 2b-1) with an exact Chebyshev expansion, and it
    tracks 1/x wherever |x| is bounded away from 0. Degree grows like
    (alpha/lambda_min)^2 log(1/eps): encoding normalization matters as well
    as the physical condition number.
  * Normalization. A QSVT polynomial must satisfy |p| <= 1 on [-1, 1],
    but 1/x is unbounded. So we implement a *scaled* inverse p(x) ~ c/x;
    the circuit returns c*alpha*A^-1 b, and the classical constant is
    recovered from the known input, polynomial, and encoding scales.

A second, 2x2 sparse case uses table-backed encode_sparse at three angle
bits, independently reconstructs the quantized operator, and generates its
own inverse phases. It separates circuit, quantization, and polynomial
errors. Real-response extraction uses full-state simulator postprocessing;
it is not a coherent procedure for reading out every solution coordinate.

Verified against numpy.linalg.solve: direction fidelity ~1 and a small
residual ||A x_hat - b||. Run: python3 07_matrix_inversion_qsvt.py
Add --verbose to show individual validation checks; failures are always reported.
"""
from __future__ import annotations

import argparse
import contextlib
import io
import os
import time

import cudaq
import numpy as np
from numpy.polynomial import chebyshev
from scipy.stats import binom

from cudaq_algorithms import PauliLCU, PhaseSequence, QSVT
from cudaq_algorithms import sim_utils as sim
from cudaq_algorithms.sparse import encode_sparse

_PAULIS = {
    "I": np.eye(2, dtype=complex),
    "X": np.array([[0, 1], [1, 0]], dtype=complex),
    "Y": np.array([[0, -1j], [1j, 0]]),
    "Z": np.diag([1.0, -1.0]).astype(complex),
}


def pauli_terms(matrix: np.ndarray, num_qubits: int) -> dict:
    """Decompose a Hermitian matrix into a {pauli_word: coefficient} sum.

    Little-endian, matching CUDA-Q and example 1: word[0] is the rightmost
    tensor factor. Coefficients are c_P = tr(P^dagger M) / 2^n; for a
    Hermitian M they come out real.
    """
    terms: dict = {}
    for index in range(4**num_qubits):
        labels, digits = [], index
        for _ in range(num_qubits):
            labels.append("IXYZ"[digits % 4])
            digits //= 4
        word = "".join(labels)
        factor = np.array([[1]], dtype=complex)
        for label in word:
            factor = np.kron(_PAULIS[label], factor)
        coefficient = np.trace(factor.conj().T @ matrix) / (2**num_qubits)
        if abs(coefficient) > 1e-10:
            terms[word] = coefficient.real
    return terms


def inverse_chebyshev_coeffs(b: int) -> np.ndarray:
    """Chebyshev coefficients of (1 - (1-x^2)^b)/x, the CKS 1/x proxy.

    Returns the coefficients of T_1, T_3, ..., T_{2b-1} (odd parity) --
    exactly the form qsppack.solve consumes. The identity is

    (1-(1-x^2)^b)/x = 4 sum_j (-1)^j [2^-2b sum_{i=j+1}^b C(2b, b+i)] T_{2j+1}.
    """
    # Stable binomial survival probabilities avoid overflowing 2.0**(2*b).
    j = np.arange(b)
    return 4 * (-1.)**j * binom.sf(b + j, 2 * b, .5)


def evaluate_odd(coeffs: np.ndarray, x: np.ndarray) -> np.ndarray:
    """Evaluate sum_j coeffs[j] T_{2j+1}(x)."""
    full = np.zeros(2 * len(coeffs))
    full[1::2] = coeffs
    return chebyshev.chebval(x, full)


def inverse_phase_sequence(x_min: float, epsilon: float):
    """Phase factors for a scaled 1/x on [x_min, 1], and the scale c.

    Picks the CKS degree from the error bound |(1-x^2)^b| <= exp(-b x_min^2),
    scales the polynomial to sit safely inside |p| <= 1 (so the QSP solve
    stays well-conditioned), and returns qsp-convention phases.
    """
    import qsppack

    b = max(int(np.ceil(np.log(1 / epsilon) / x_min**2)), 3)
    print(f"Planning CKS degree {2*b-1} from x_min={x_min:.6f}", flush=True)
    if 2 * b - 1 > 511:
        raise ValueError(
            "requested inverse exceeds this example's degree-511 guard")
    coeffs = inverse_chebyshev_coeffs(b)
    # |f_B(x)| <= min(B|x|, 1/|x|) <= sqrt(B) gives global headroom.
    scale = 0.9 / np.sqrt(b)
    coeffs = coeffs * scale

    options = {
        "criteria": 1e-10,
        "method": "Newton",
        "typePhi": "full",
        "useReal": True,
        "targetPre": True,
    }
    with contextlib.redirect_stdout(io.StringIO()):  # hush the QSP solver
        phases, _ = qsppack.solve(coeffs.copy(), 1, options)
    return [float(p) for p in phases], scale, b


def check(label, error, tolerance=1e-10, *, 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 qsp_response(phases, values):
    """Independent raw device response; the walk signal is minus H/alpha."""
    responses = []
    for value in values:
        root = np.sqrt(max(0., 1 - value * value))
        step = np.array([[-value, -root], [root, -value]], dtype=complex)
        result = np.diag([np.exp(1j * phases[0]), np.exp(-1j * phases[0])])
        for phase in phases[1:]:
            result = np.diag([np.exp(1j * phase),
                              np.exp(-1j * phase)]) @ step @ result
        responses.append(np.exp(1j * np.sum(phases)) * result[0, 0])
    return np.array(responses)


def sparse_inverse(*, verbose=False):
    """Fresh phases for a power-of-two sparse SPD system, with no fitted scale."""
    started = time.perf_counter()
    ideal = np.array([[1.5, -.25], [-.25, 1.5]])
    rhs = np.array([1., 0.])  # Not an eigenvector.
    beta = float(np.linalg.norm(rhs))
    encoding = encode_sparse(ideal, value_bits=3)
    print("\nSparse inverse: QROM-backed 2x2 SPD matrix; report:",
          encoding.report)
    print(
        f"system={encoding.num_system}, block ancillas={encoding.num_block_ancilla}, "
        f"scratch={encoding.num_scratch}, all ancillas={encoding.num_ancilla}, "
        f"total={encoding.num_system+encoding.num_ancilla}")
    # The same independent angle rule as the public storage contract. Do not
    # obtain the reference by multiplying a measured block by alpha.
    realized = np.zeros_like(ideal)
    for row, column in zip(*np.nonzero(ideal)):
        value = ideal[row, column]
        theta = np.arcsin(np.sqrt(abs(value) / encoding.h))
        code = min((1 << encoding.value_bits) - 1,
                   round((1 << encoding.value_bits) * theta / (np.pi / 2)))
        realized[row, column] = np.sign(value) * encoding.h * np.sin(
            np.pi * code / (2 * (1 << encoding.value_bits)))**2
    columns = []
    for index in range(2):
        basis = np.zeros(2, dtype=complex)
        basis[index] = 1.
        columns.append(sim.action(encoding, basis))
    check("sparse encoding versus quantized matrix",
          np.max(np.abs(encoding.alpha * np.column_stack(columns) - realized)),
          verbose=verbose)
    exact = np.linalg.solve(ideal, rhs)
    rounded = np.linalg.solve(realized, rhs)
    values, vectors = np.linalg.eigh(realized)
    normalized = values / encoding.alpha
    epsilon = 1e-3
    phases, scale, half_degree = inverse_phase_sequence(
        float(normalized.min()), epsilon)
    polynomial = scale * evaluate_odd(inverse_chebyshev_coeffs(half_degree),
                                      normalized)
    check("sparse relative inverse polynomial",
          np.max(np.abs(1 - normalized * polynomial / scale)),
          epsilon + 1e-12,
          verbose=verbose)
    response = qsp_response(phases, normalized)
    # Odd parity under x -> -x supplies minus; doubled projector phases
    # supply exp(i*sum(phi)). Verify these corrections before any solve.
    corrected = -(response * np.exp(-1j * np.sum(phases))).real
    phase_error = float(np.max(np.abs(corrected - polynomial)))
    check("sparse phase synthesis versus inverse polynomial",
          phase_error,
          2e-8,
          verbose=verbose)
    ket = np.asarray(rhs / beta, dtype=complex)
    raw = sim.run_on_large_stack(sim.transform, QSVT(encoding), ket,
                                 PhaseSequence(phases, convention="qsp"))
    expected = vectors @ (response * (vectors.conj().T @ ket))
    circuit_atol = 1e-8
    check("sparse raw complex QSVT versus scalar model",
          np.max(np.abs(raw - expected)),
          circuit_atol,
          verbose=verbose)
    solution = -(raw * np.exp(-1j * np.sum(phases))).real * beta / (
        scale * encoding.alpha)
    matrix_error = float(np.linalg.norm(realized - ideal, 2))
    quantization_bound = matrix_error * np.linalg.norm(exact) / values.min()
    polynomial_bound = epsilon * np.linalg.norm(rounded)
    phase_bound = beta * phase_error / (scale * encoding.alpha)
    roundoff_bound = beta * np.sqrt(2) * circuit_atol / (scale *
                                                         encoding.alpha)
    inverse_bound = polynomial_bound + phase_bound + roundoff_bound
    overall_bound = quantization_bound + inverse_bound
    check("sparse quantized versus ideal NumPy solve",
          np.linalg.norm(rounded - exact),
          quantization_bound + 1e-12,
          verbose=verbose)
    check("sparse reconstructed versus quantized solve",
          np.linalg.norm(solution - rounded),
          inverse_bound,
          verbose=verbose)
    check("sparse reconstructed versus ideal solve",
          np.linalg.norm(solution - exact),
          overall_bound,
          verbose=verbose)
    residual = np.linalg.norm(ideal @ solution - rhs) / beta
    check("sparse physical residual",
          residual,
          np.linalg.norm(ideal, 2) * overall_bound / beta,
          verbose=verbose)
    print("  coordinate   ideal NumPy    quantized NumPy    QSVT")
    for index in range(2):
        print(f"  {index:10d} {exact[index]:13.9f} {rounded[index]:17.9f} "
              f"{solution[index]:13.9f}")
    print(
        f"matrix quantization error={matrix_error:.3e}; "
        f"relative solution error={np.linalg.norm(solution-exact)/np.linalg.norm(exact):.3e}"
    )
    print(f"degree={2*half_degree-1}; c={scale:.9f}; beta={beta}; "
          f"known physical recovery={beta/(scale*encoding.alpha):.9f}")
    print(f"error bounds: quantization={quantization_bound:.3e}, "
          f"polynomial={polynomial_bound:.3e}, phase={phase_bound:.3e}, "
          f"roundoff={roundoff_bound:.3e}")
    print(
        "Real-response extraction is simulator postprocessing; the raw good-block "
        "norm is not isolated inverse-filter success probability.")
    print(
        "No zero padding is introduced; zero-padded reciprocal problems need "
        "explicit treatment of zero eigenvalues and RHS support.")
    print(
        f"Sparse case elapsed: {time.perf_counter()-started:.2f}s; "
        f"maximum executed qubits: {encoding.num_system+encoding.num_ancilla}")


def main() -> int:
    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
    started = time.perf_counter()
    cudaq.set_target(os.environ.get("CUDAQ_DEFAULT_SIMULATOR", "qpp-cpu"))

    # 1. A 5x5 symmetric positive-definite matrix with a controlled spectrum
    #    in [1, 2] (condition number 2). The smallest eigenvalue is 1, so
    #    padding to 8x8 with an identity block adds no new small eigenvalue.
    rng = np.random.default_rng(3)
    basis, _ = np.linalg.qr(rng.normal(size=(5, 5)))
    spectrum = np.array([1.0, 1.25, 1.5, 1.75, 2.0])
    a5 = (basis * spectrum) @ basis.T
    a5 = 0.5 * (a5 + a5.T)
    a8 = np.eye(8, dtype=complex)
    a8[:5, :5] = a5

    # 2. Block-encode A (Hermitian) as a Pauli LCU. QSVT applies polynomials
    #    to x = eigenvalue / alpha, so the working domain is [x_min, x_max].
    terms = pauli_terms(a8, num_qubits=3)
    encoding = PauliLCU(terms)
    transformer = QSVT(encoding)

    eigenvalues = np.linalg.eigvalsh(a8)
    x = eigenvalues / encoding.alpha
    x_min, x_max = float(x.min()), float(x.max())
    print(f"matrix                : 5x5 SPD, padded to 8x8 (3 system qubits)")
    print(f"Pauli LCU terms       : {len(terms)}  "
          f"(system {encoding.num_system} + ancilla {encoding.num_ancilla})")
    print(f"alpha (1-norm)        : {encoding.alpha:.6f}")
    print(
        f"condition number      : {eigenvalues.max() / eigenvalues.min():.2f}")
    print(f"spectral domain x     : [{x_min:.4f}, {x_max:.4f}]")

    # 3. Build phases for a scaled 1/x over the spectral domain, and check
    #    the polynomial tracks scale/x there before trusting the circuit.
    phases, scale, degree_half = inverse_phase_sequence(x_min, epsilon=1e-2)
    domain = np.linspace(x_min, x_max, 200)
    polynomial = scale * evaluate_odd(inverse_chebyshev_coeffs(degree_half),
                                      domain)
    poly_error = float(np.max(np.abs(polynomial - scale / domain)))
    print(f"CKS polynomial degree : {2 * degree_half - 1}  "
          f"(scaled by c = {scale:.5f})")
    print(f"|p(x) - c/x| on domain: {poly_error:.2e}")
    print(f"phase factors         : {len(phases)}")

    # 4. Solve A x = b. Prepare b on the system register, run the QSVT
    #    sequence, keep the all-zero-ancilla block. The qsp convention makes
    #    the good-subspace amplitude complex (p(x) + i * complementary(x));
    #    with a real b and real eigenvectors, the real part -- after removing
    #    the qsp global phase exp(i * sum phi) and odd-parity minus sign --
    #    is p(A/alpha) b. Full-state real extraction is simulator postprocessing.
    b = np.zeros(8, dtype=complex)
    b[:5] = rng.normal(size=5)
    b /= np.linalg.norm(b)

    raw = sim.transform(transformer, b, PhaseSequence(phases,
                                                      convention="qsp"))
    response = qsp_response(phases, x)
    corrected_response = -(response * np.exp(-1j * np.sum(phases))).real
    intended = scale * evaluate_odd(inverse_chebyshev_coeffs(degree_half), x)
    check("dense phase convention versus polynomial",
          np.max(np.abs(corrected_response - intended)),
          2e-8,
          verbose=verbose)
    values, vectors = np.linalg.eigh(a8)
    response = qsp_response(phases, values / encoding.alpha)
    expected_raw = vectors @ (response * (vectors.conj().T @ b))
    check("dense raw QSVT versus scalar model",
          np.max(np.abs(raw - expected_raw)),
          1e-8,
          verbose=verbose)
    good = -(raw * np.exp(-1j * np.sum(phases))).real

    # 5. b has unit norm. The known polynomial and encoding scales recover
    #    A^-1 b directly; no scalar is fitted to NumPy or to the residual.
    constant = scale * encoding.alpha
    x_hat = good / constant

    exact = np.linalg.solve(a8, b).real
    fidelity = float(
        abs(np.vdot(good / np.linalg.norm(good),
                    exact / np.linalg.norm(exact))))
    residual = float(np.linalg.norm(a8 @ x_hat - b))
    solution_error = float(
        np.linalg.norm(x_hat - exact) / np.linalg.norm(exact))

    print(f"\nknown response scale  : c*alpha = {constant:+.5f}")
    print(f"direction fidelity    : {fidelity:.6f}")
    print(f"residual ||A x - b||  : {residual:.3e}")
    print(f"solution rel. error   : {solution_error:.3e}")

    assert fidelity > 0.999
    assert residual < 1e-2
    print("\nOK — QSVT applied 1/x to the block-encoded matrix; the "
          "good-subspace state solves A x = b.")
    sparse_inverse(verbose=verbose)
    print(f"Total example elapsed: {time.perf_counter()-started:.2f}s")
    return 0


if __name__ == "__main__":
    raise SystemExit(main())

Quantum phase estimation with three energy oracles

The physical question is how to estimate a molecule’s energy using a quantum circuit. Phase estimation extracts an energy-dependent phase into a counting register whose measurement produces a distribution of estimates. This example uses the same small hydrogen molecule and initial state throughout, so readers can follow how exact time evolution, approximate time evolution, and a qubitization walk each connect their phases to the same energy problem.

You should learn how the initial state’s overlap with energy eigenstates determines which energies are observed, and how counting-register resolution limits their precision. The explicit circuits and the packaged PhaseEstimation API show the roles of controlled operations, measured bits, and energy decoding. Comparing their distributions with exact references also explains why walk phases require a cosine-based decoder and mirror folding, and how to judge sampling variation separately from a systematic error.

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

Quantum phase estimation reads the eigenphases of a unitary into a counting register: for \(U|E_j\rangle = e^{2\pi i \phi_j}|E_j\rangle\), an \(m\)-qubit register and the controlled powers \(U^{2^k}\) build a phase gradient that the inverse QFT converts into a peak near the integer \(y = 2^m \phi_j\). On a superposed input QPE samples eigenvalues with the input state’s spectral weights – it does not choose the ground state. H2 works well because Hartree-Fock has dominant ground-state overlap.

This example wraps one QPE shell – the same Hartree-Fock preparation, the same six-qubit counting register, the same hand-written inverse QFT – around three different constructions of the unitary whose phase reveals energy:

Method

Unitary measured by QPE

Energy decoder

Exact matrix

\(U_t = e^{-iHt}\) (dense, simulator-only reference)

\(E = -\operatorname{wrap}(2\pi y/M)/t\)

Product formula

\(U_{\mathrm{Trot}}(t) \approx e^{-iHt}\) via trotter.apply_trotter

same linear decoder

Qubitization walk

\(W\) from the PauliLCU block encoding

\(E = -\alpha\cos\theta\)

The walk case is what cudaq_algorithms.PhaseEstimation packages (see Qubitization and QSVT). After the three-oracle comparison, the example executes that packaged interface with the same Hamiltonian and Hartree-Fock preparation: build a measured kernel, call cudaq.sample, and decode with energies_from_counts. It is another implementation of the walk approach, rather than a fourth physical oracle.

The packaged section checks that the textbook and centered exact phase marginals agree bin by bin, compares seeded sampled distributions with their exact marginals under a declared statistical bound, and verifies the nonlinear cosine phase-cell edges. Only phase bits are measured; public decoders handle register interpretation and mirror folding. The encoded identity/core energy is included once.

The product-formula oracle shows a subtlety of composing library evolution under control: Trotter evolves the nonidentity part of the Hamiltonian, so its omitted identity coefficient – a global phase for free evolution – must be restored as a controlled relative phase inside the QPE loop.

The walk oracle decodes through the qubitization convention \(\cos\theta_j = -E_j/\alpha\), so each energy appears at mirror phases \(\pm\theta_j\); the decoder folds conjugate bins before taking the mode. Its controlled-power schedule is the centered form of Berry et al., PRX Quantum 6, 020327 (2025), which replaces \(W^n\) by \(W^{n - M/2}\): one unconditional \(W^\dagger\), a controlled \(W\) for bit zero, and a coherent choice of \(W^{\pm 2^{k-1}}\) for every upper bit.

A four-qubit problem does not need qubitization – the dense reference is cheaper classically. The walk is here because fault-tolerant algorithms commonly assume structured PREPARE/SELECT access, and this shell is exactly how such an oracle drops into QPE. Six counting qubits keep the script fast on the CPU simulator; every modal estimate is asserted to land within one phase cell of the exact ground energy. The time-oracle half-cell is about 34 mHa here; walk cells use their own asymmetric cosine edges. Resolution scales with the register: at 12 counting qubits the same circuits reach roughly 0.1–0.5 mHa.

"""Example 8 — Quantum phase estimation with three energy oracles.

The physical question is how to estimate a molecule's energy using a quantum
circuit. Phase estimation extracts an energy-dependent phase into a counting
register whose measurement produces a distribution of estimates. This example
uses the same small hydrogen molecule and initial state throughout, so readers
can follow how exact time evolution, approximate time evolution, and a
qubitization walk each connect their phases to the same energy problem.

You should learn how the initial state's overlap with energy eigenstates
determines which energies are observed, and how counting-register resolution
limits their precision. The explicit circuits and the packaged PhaseEstimation
API show the roles of controlled operations, measured bits, and energy
decoding. Comparing their distributions with exact references also explains
why walk phases require a cosine-based decoder and mirror folding, and how to
judge sampling variation separately from a systematic error.

QPE turns the eigenphases of a unitary into measured bit strings. This
example estimates ground-state energies of the H2/STO-3G Hamiltonian with
one QPE shell around three different oracle constructions:

    1. exact dense-matrix time evolution  exp(-iHt)   (simulator reference)
    2. first-order product-formula evolution          (trotter.apply_trotter)
    3. an FTQC-oriented qubitization WALK              (PauliLCU)

All three use the same Hartree-Fock input, the same six-qubit counting
register, and the same hand-written inverse QFT. What changes is how the
nonunitary Hamiltonian H becomes a unitary whose phase reveals energy:
the time-evolution oracles decode linearly, E = -wrap(2*pi*y/M)/t, while
the walk decodes through the qubitization convention E = -alpha*cos(theta)
after folding the walk's conjugate mirror phases.

QPE does not choose the ground state: on a superposed input it samples
eigenvalues with the input state's spectral weights. H2 works well because
Hartree-Fock has dominant ground-state overlap. Each modal estimate is
checked to land within one phase cell of the exact ground energy.

The final section executes PhaseEstimation's packaged textbook walk ladder
on the same input. Its public decoders, exact phase marginal, sampled
statistical check, and cosine phase cells are compared with the
centered walk above. This is another implementation of method 3, not another
physical oracle.

The walk QPE core follows the centered exponent schedule of Berry et al.,
"Rapid initial-state preparation for the quantum simulation of strongly
correlated molecules", PRX Quantum 6, 020327 (2025).

Prerequisite: PySCF (`pip install pyscf`). Run: python3 08_quantum_phase_estimation.py
Add --verbose to show individual validation checks; failures are always reported.
"""

from __future__ import annotations

import argparse
import math
import os
import time

import cudaq
import numpy as np
import scipy

from cudaq_algorithms import PauliLCU, PhaseEstimation, chemistry, stateprep, trotter
from cudaq_algorithms import sim_utils as sim

# ----------------------------------------------------------------------
# Classical decoding helpers: counts -> probabilities -> modal bin -> energy
# ----------------------------------------------------------------------


def logical_integer(cudaq_bitstring: str) -> int:
    """Convert CUDA-Q's q0-first display string to logical integer ``y``."""
    return int(str(cudaq_bitstring)[::-1], 2)


def wrap_to_pi(angle: float) -> float:
    """Map an angle to the half-open interval ``[-pi, pi)``."""
    return (float(angle) + math.pi) % (2.0 * math.pi) - math.pi


def sampled_probabilities(counts, counting_qubits: int,
                          shots: int) -> np.ndarray:
    """Return logical-QPE-bin probabilities from CUDA-Q sample counts."""
    if counting_qubits < 1:
        raise ValueError("counting_qubits must be positive")
    if shots < 1:
        raise ValueError("shots must be positive")

    probabilities = np.zeros(1 << counting_qubits, dtype=np.float64)
    for bits, count in counts.items():
        probabilities[logical_integer(str(bits))] += int(count) / shots
    return probabilities


def decode_time_qpe(probabilities: np.ndarray,
                    evolution_time: float) -> tuple[int, float]:
    """Decode the modal bin for ``U = exp(-i H t)`` into an energy."""
    if evolution_time <= 0.0:
        raise ValueError("evolution_time must be positive")
    num_bins = len(probabilities)
    mode = int(np.argmax(probabilities))
    phase = wrap_to_pi(2.0 * math.pi * mode / num_bins)
    return mode, -phase / evolution_time


def decode_walk_qpe(probabilities: np.ndarray,
                    alpha: float) -> tuple[int, float]:
    """Fold conjugate WALK phases and decode ``E = -alpha*cos(theta)``."""
    if alpha <= 0.0:
        raise ValueError("alpha must be positive")
    num_bins = len(probabilities)
    if num_bins % 2:
        raise ValueError("the phase-register dimension must be even")

    # Each energy appears at mirror phases +theta and -theta; add bin y
    # to bin M - y before selecting the mode.
    folded = probabilities[:num_bins // 2 + 1].copy()
    folded[1:-1] += probabilities[-1:num_bins // 2:-1]
    mode = int(np.argmax(folded))
    phase = 2.0 * math.pi * mode / num_bins
    return mode, -alpha * math.cos(phase)


def check(label, error, tolerance=1e-10, *, 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 packaged_walk_comparison(encoding,
                             prepare_hartree_fock,
                             centered_kernel,
                             centered_sampled,
                             counting_qubits,
                             shots,
                             exact_ground_energy,
                             *,
                             verbose=False):
    print("\nPackaged PhaseEstimation: the same walk, a textbook power ladder")
    qpe = PhaseEstimation(encoding)
    measured = qpe.kernel(counting_qubits,
                          state_prep=prepare_hartree_fock,
                          measure=True)
    cudaq.set_random_seed(109)
    counts = cudaq.sample(measured, shots_count=shots)
    ranked = qpe.energies_from_counts(counts, counting_qubits, top=3)
    sampled = qpe.phase_probabilities_from_counts(counts, counting_qubits)
    # The public decoder also accepts full-register counts, whose layout is
    # system | phase | ancilla. No manual string slicing is needed here.
    check("only phase bits measured",
          max(abs(len(str(bits)) - counting_qubits) for bits in counts),
          0,
          verbose=verbose)
    exact = sim.qpe.phase_probabilities(qpe,
                                        counting_qubits,
                                        state_prep=prepare_hartree_fock)
    bins = 1 << counting_qubits
    check("exact phase marginal normalized",
          abs(float(exact.sum()) - 1),
          verbose=verbose)
    # A priori union/Hoeffding bound over phase-bin subsets, delta=1e-6.
    # Compare unfolded distributions before identifying conjugate energies.
    delta = 1e-6
    tv_bound = min(
        1., np.sqrt((bins * np.log(2) + np.log(2 / delta)) / (2 * shots)))
    tv = lambda a, b: 0.5 * float(np.sum(np.abs(a - b)))
    check("sampled versus exact unfolded phase TV",
          tv(sampled, exact),
          tv_bound,
          verbose=verbose)

    # Same physical oracle, different schedule and allocation order. The
    # centered schedule applies W^(n - M/2) instead of W^n; the extra
    # W^(-M/2) is a phase on each walk eigencomponent, so the phase-register
    # marginal agrees bin by bin before any folding. Disable measurement in
    # the centered shell to obtain its exact phase marginal.
    centered_state = np.asarray(
        cudaq.get_state(centered_kernel, counting_qubits, encoding.num_system,
                        encoding.num_ancilla, False))
    centered_exact = np.sum(np.abs(
        centered_state.reshape(1 << encoding.num_system,
                               1 << encoding.num_ancilla, bins))**2,
                            axis=(0, 1))
    check("centered versus textbook exact phase marginals",
          tv(centered_exact, exact),
          verbose=verbose)
    check("centered sampled versus its exact unfolded phase TV",
          tv(centered_sampled, centered_exact),
          tv_bound,
          verbose=verbose)
    check("centered versus textbook sampled phase TV",
          tv(centered_sampled, sampled),
          2 * tv_bound,
          verbose=verbose)
    decoded = np.array(
        [qpe.phase_to_energy(j, counting_qubits) for j in range(bins)])
    expected = -encoding.alpha * np.cos(2 * np.pi * np.arange(bins) / bins)
    check("public cosine decoder on every phase bin",
          float(np.max(np.abs(decoded - expected))),
          verbose=verbose)

    mode, _ = decode_walk_qpe(exact, encoding.alpha)
    sampled_mode, sampled_energy = decode_walk_qpe(sampled, encoding.alpha)
    centered_mode, _ = decode_walk_qpe(centered_sampled, encoding.alpha)
    check("sampled dominant energy matches public ranking",
          abs(sampled_energy - ranked[0][0]),
          verbose=verbose)
    check("centered and textbook dominant energy cell",
          abs(centered_mode - mode),
          0,
          verbose=verbose)
    check("sampled and exact dominant energy cell",
          abs(sampled_mode - mode),
          0,
          verbose=verbose)
    lower = -encoding.alpha * math.cos(
        2 * math.pi * max(0., mode - 0.5) / bins)
    upper = -encoding.alpha * math.cos(
        2 * math.pi * min(bins / 2, mode + 0.5) / bins)
    check("exact ground energy lies in cosine phase cell",
          max(lower - exact_ground_energy, exact_ground_energy - upper, 0.),
          1e-9,
          verbose=verbose)
    print(
        f"m={counting_qubits}, shots={shots}, alpha={encoding.alpha:.9f}, "
        f"total qubits={encoding.num_system+counting_qubits+encoding.num_ancilla}, "
        f"textbook controlled-walk steps={bins-1}")
    print(f"sampling seed=109; unfolded TV={tv(sampled, exact):.6f}, "
          f"a priori bound={tv_bound:.6f}, delta={delta}")
    for value, probability in ranked:
        print(f"  folded E={value:+.12f} Ha, probability={probability:.6f}")
    print(f"ground-energy cell: [{lower:+.9f}, {upper:+.9f}] Ha")
    print("The encoded Hamiltonian already includes core/nuclear energy once.")
    print("PhaseEstimation builds circuits and decodes; the caller executes.")
    print(
        "QPE weights reflect input overlaps; it does not select the ground state."
    )
    print(
        "Long simulated ladders (from m=13) need sim.run_on_large_stack, "
        "including when cudaq.sample is the executor; they are not run here.")


def main() -> int:
    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
    started = time.perf_counter()
    cudaq.set_target(os.environ.get("CUDAQ_DEFAULT_SIMULATOR", "qpp-cpu"))

    try:
        import pyscf
        from pyscf import fci as pyscf_fci
    except ImportError:
        print("This example needs PySCF:  pip install pyscf")
        return 0

    # 1. H2 at 0.7474 Angstrom in STO-3G: two electrons in a singlet.
    #    With two spatial orbitals the spin-orbital Hamiltonian acts on
    #    four qubits -- deliberately small, so QPE can be compared with
    #    exact NumPy diagonalization.
    geometry = [("H", (0.0, 0.0, 0.0)), ("H", (0.0, 0.0, 0.7474))]
    mol = pyscf.gto.M(atom=geometry, basis="sto-3g", spin=0, charge=0)
    mean_field = pyscf.scf.RHF(mol).run(verbose=0)
    hf_energy = float(mean_field.e_tot)
    fci_energy = float(pyscf_fci.FCI(mean_field).kernel()[0])

    one_body, eri, core = chemistry.from_pyscf(mean_field)
    spin_hamiltonian = chemistry.qubit_hamiltonian(one_body,
                                                   eri,
                                                   scalar_offset=core)
    electron_count = int(mol.nelectron)
    system_qubit_count = 2 * one_body.shape[0]
    print(f"electrons: {electron_count}")
    print(f"system qubits: {system_qubit_count}")
    print(f"RHF reference: {hf_energy:+.12f} Ha")
    print(f"FCI reference: {fci_energy:+.12f} Ha")

    # 2. Let the library organize the Pauli sum. PauliLCU retains the
    #    term pairs and computes the LCU normalization alpha = sum |a_l|
    #    (a spectral bound: ||H|| <= alpha). Trotter reuses the same
    #    pairs, orders the nonidentity terms, and reports the identity
    #    coefficient separately -- an identity contribution is a global
    #    phase for free evolution but a measurable relative phase under
    #    QPE control.
    encoding = PauliLCU(spin_hamiltonian)
    product_formula = trotter.Trotter(list(encoding.terms))

    trotter_coefficients = product_formula.coefficients
    trotter_words = [cudaq.pauli_word(word) for word in product_formula.words]
    identity_coefficient = product_formula.identity_coefficient

    hamiltonian_matrix = np.asarray(spin_hamiltonian.to_matrix(),
                                    dtype=np.complex128)
    exact_energies = np.linalg.eigvalsh(hamiltonian_matrix)
    exact_ground_energy = float(exact_energies[0])

    print(f"Pauli terms (including identity): {encoding.num_terms}")
    print(f"LCU alpha: {encoding.alpha:.12f} Ha")
    print(f"signal qubits: {encoding.num_ancilla}")
    print(f"NumPy ground energy: {exact_ground_energy:+.12f} Ha")

    # The classical references must agree before any circuit runs: the
    # variational RHF energy sits above FCI, and FCI equals the exact
    # ground energy of the qubit Hamiltonian we are about to encode.
    assert hf_energy > fci_energy
    assert abs(fci_energy - exact_ground_energy) < 1e-9

    # 3. Phase register and evolution time. M = 2^6 = 64 phase bins.
    #    t = 0.9*pi/alpha keeps |E_j t| < pi for the whole spectrum, so
    #    the linear phase-to-energy decoder cannot alias across the
    #    [-pi, pi) boundary. Eight first-order Trotter steps suffice:
    #    counting-register resolution, not Trotter error, dominates the
    #    six-bit modal estimate.
    counting_qubits = 6
    dimension = 1 << counting_qubits
    shots = 20_000

    evolution_time = 0.9 * math.pi / encoding.alpha
    n_trotter_steps = 8
    trotter_order = 1
    time_half_cell = math.pi / (evolution_time * dimension)

    print(f"phase bins: {dimension}")
    print(f"shots per method: {shots}")
    print(f"evolution time: {evolution_time:.12f} Ha^-1")
    print(f"Trotter steps/order: {n_trotter_steps}/{trotter_order}")
    print(f"time-QPE half-cell: {1000 * time_half_cell:.3f} mHa")

    # 4. Shared state preparation and inverse QFT. Every method uses the
    #    same Hartree-Fock preparation and the same hand-written IQFT
    #    (reverse the register, then Hadamards with negative controlled
    #    phases).

    @cudaq.kernel
    def prepare_hartree_fock(system: cudaq.qview):
        # H2/STO-3G has two electrons.
        stateprep.hartree_fock(system, 2)

    @cudaq.kernel
    def iqft(qubits: cudaq.qview):
        size = qubits.size()

        for index in range(size // 2):
            swap(qubits[index], qubits[size - index - 1])

        for index in range(size - 1):
            h(qubits[index])
            next_index = index + 1
            for target in range(index, -1, -1):
                r1.ctrl(-np.pi / 2**(next_index - target), qubits[next_index],
                        qubits[target])

        h(qubits[size - 1])

    # 5a. Method 1 -- exact-matrix QPE. SciPy builds the dense evolution
    #     operator U_t = expm(-iHt) directly: QPE with no Hamiltonian-
    #     simulation approximation. A useful regression reference, not a
    #     scalable algorithm (the dense 2^n x 2^n unitary is exponential).
    #     The reversed target order reconciles CUDA-Q's registered-
    #     operation target significance with the matrix ordering returned
    #     by SpinOperator.to_matrix() for this four-qubit example.
    exact_evolution_matrix = scipy.linalg.expm(-1j * hamiltonian_matrix *
                                               evolution_time)
    cudaq.register_operation("exact_matrix", exact_evolution_matrix)

    @cudaq.kernel
    def exact_time_step(system: cudaq.qview):
        exact_matrix(system[3], system[2], system[1], system[0])

    @cudaq.kernel
    def qpe_exact(n_counting_q: int, n_system_q: int):
        counting = cudaq.qvector(n_counting_q)
        system = cudaq.qvector(n_system_q)

        prepare_hartree_fock(system)
        h(counting)

        for bit in range(n_counting_q):
            for _ in range(1 << bit):
                cudaq.control(exact_time_step, [counting[bit]], system)

        iqft(counting)
        mz(counting)

    # 5b. Method 2 -- product-formula QPE. trotter.apply_trotter applies
    #     the ordered first-order Pauli product for the nonidentity part
    #     H' under coherent control. The library intentionally omits the
    #     identity term c_I (a global phase for free evolution); under
    #     QPE control it becomes observable, so each controlled base
    #     oracle also applies r1(-t*c_I) on the control's |1> branch.
    @cudaq.kernel
    def qpe_trotter(n_counting_q: int, n_system_q: int,
                    coefficients: list[float], words: list[cudaq.pauli_word],
                    t: float, steps: int, order: int, identity: float):
        counting = cudaq.qvector(n_counting_q)
        system = cudaq.qvector(n_system_q)

        prepare_hartree_fock(system)
        h(counting)

        for bit in range(n_counting_q):
            # Repetition realizes U(t)**(2**bit) using one fixed base oracle.
            for _ in range(1 << bit):
                cudaq.control(trotter.apply_trotter, counting[bit],
                              coefficients, words, t, steps, order, system)
                # Restore the identity term's controlled relative phase --
                # subtle but required: apply_trotter evolves H' only.
                r1(-t * identity, counting[bit])

        iqft(counting)
        mz(counting)

    # 5c. Method 3 -- PauliLCU / qubitization WALK QPE. The walk W maps
    #     energies to phases through cos(theta_j) = -E_j / alpha, so each
    #     energy appears at mirror phases +/- theta_j (folded in the
    #     decoder). The centered exponent schedule
    #         n - M/2 = -1 + b_0 + sum_k 2^(k-1) (2 b_k - 1)
    #     replaces powers W^n by W^(n - M/2) [PRX Quantum 6, 020327
    #     (2025)]: an unconditional W-dagger supplies the -1, bit zero
    #     supplies controlled W, and every upper bit coherently chooses
    #     W^(-2^(k-1)) for 0 or W^(+2^(k-1)) for 1.
    #
    #     The controlled-walk kernels expect one contiguous view ordered
    #     [external control, signal...]. The combined counting-and-signal
    #     allocation therefore makes the final counting qubit the fixed
    #     control port; SWAPs move each active counting-bit state into
    #     that port and back without copying or measuring it.
    prepare_signal = encoding.prepare_kernel()
    walk_dagger = encoding.adjoint_walk_step_kernel()
    controlled_walk = encoding.controlled_walk_step_kernel()
    controlled_walk_dagger = encoding.controlled_adjoint_walk_step_kernel()

    @cudaq.kernel
    def qpe_walk(n_counting_q: int, n_system_q: int, n_signal_q: int,
                 measure_phase: bool):
        counting_and_signal = cudaq.qvector(n_counting_q + n_signal_q)
        counting = counting_and_signal.front(n_counting_q)
        signal = counting_and_signal.back(n_signal_q)
        control_and_signal = counting_and_signal.back(n_signal_q + 1)
        system = cudaq.qvector(n_system_q)

        prepare_hartree_fock(system)
        h(counting)
        prepare_signal(signal)

        # Constant -1 contribution to n - M/2.
        walk_dagger(signal, system)

        # Least-significant bit contributes +b0.
        swap(counting[0], counting[n_counting_q - 1])
        controlled_walk(control_and_signal, system)
        swap(counting[0], counting[n_counting_q - 1])

        for bit in range(1, n_counting_q):
            # Move b_k into the fixed external-control port.
            if bit != n_counting_q - 1:
                swap(counting[bit], counting[n_counting_q - 1])

            for _ in range(1 << (bit - 1)):
                # b_k=0 applies W dagger; b_k=1 applies W.
                x(control_and_signal[0])
                controlled_walk_dagger(control_and_signal, system)
                x(control_and_signal[0])
                controlled_walk(control_and_signal, system)

            if bit != n_counting_q - 1:
                swap(counting[bit], counting[n_counting_q - 1])

        iqft(counting)
        if measure_phase:
            mz(counting)

    # 6. Execute all three circuits: the same phase register, the same
    #    Hamiltonian, the same Hartree-Fock state, and 20,000 shots each.
    #    Fixed seeds make the outputs reproducible. Only the counting
    #    register is measured; the system (and the signal register in
    #    walk QPE) stays coherent until that measurement.
    cudaq.set_random_seed(103)
    exact_counts = cudaq.sample(qpe_exact,
                                counting_qubits,
                                system_qubit_count,
                                shots_count=shots)
    exact_sampled = sampled_probabilities(exact_counts, counting_qubits, shots)

    cudaq.set_random_seed(102)
    trotter_counts = cudaq.sample(qpe_trotter,
                                  counting_qubits,
                                  system_qubit_count,
                                  trotter_coefficients,
                                  trotter_words,
                                  evolution_time,
                                  n_trotter_steps,
                                  trotter_order,
                                  identity_coefficient,
                                  shots_count=shots)
    trotter_sampled = sampled_probabilities(trotter_counts, counting_qubits,
                                            shots)

    cudaq.set_random_seed(107)
    walk_counts = cudaq.sample(qpe_walk,
                               counting_qubits,
                               system_qubit_count,
                               encoding.num_ancilla,
                               True,
                               shots_count=shots)
    walk_sampled = sampled_probabilities(walk_counts, counting_qubits, shots)

    # 7. Decode modal phase bins into energies. No continuous fit: each
    #    result is the center of one discrete phase cell.
    exact_mode, exact_modal_energy = decode_time_qpe(exact_sampled,
                                                     evolution_time)
    trotter_mode, trotter_modal_energy = decode_time_qpe(
        trotter_sampled, evolution_time)
    walk_mode, walk_modal_energy = decode_walk_qpe(walk_sampled,
                                                   encoding.alpha)

    print(f"\nexact-matrix modal bin: {exact_mode}  ->"
          f" {exact_modal_energy:+.12f} Ha")
    print(f"Trotter modal bin: {trotter_mode}  ->"
          f" {trotter_modal_energy:+.12f} Ha")
    print(f"folded WALK modal bin: {walk_mode}  ->"
          f" {walk_modal_energy:+.12f} Ha")

    # 8. Self-verification: every modal estimate must land within one
    #    phase cell of the exact ground energy. For the time oracles the
    #    cell half-width is pi/(t*M); for the walk the cell around the
    #    modal bin is asymmetric because E = -alpha*cos(theta) is
    #    nonlinear, so both edges come from the neighboring half-bins.
    for name, energy in (("exact-matrix", exact_modal_energy),
                         ("Trotter", trotter_modal_energy)):
        error = abs(energy - exact_ground_energy)
        print(f"{name} |E - E0| = {1000 * error:.3f} mHa "
              f"(half-cell {1000 * time_half_cell:.3f} mHa)")
        assert error <= time_half_cell + 1e-9

    walk_lower = -encoding.alpha * math.cos(
        2.0 * math.pi * max(0.0, walk_mode - 0.5) / dimension)
    walk_upper = -encoding.alpha * math.cos(
        2.0 * math.pi * min(dimension / 2, walk_mode + 0.5) / dimension)
    print(
        f"WALK modal cell: [{walk_lower:+.9f}, {walk_upper:+.9f}] Ha, "
        f"|E - E0| = {1000 * abs(walk_modal_energy - exact_ground_energy):.3f} mHa"
    )
    assert walk_lower - 1e-9 <= exact_ground_energy <= walk_upper + 1e-9

    packaged_walk_comparison(encoding,
                             prepare_hartree_fock,
                             qpe_walk,
                             walk_sampled,
                             counting_qubits,
                             shots,
                             exact_ground_energy,
                             verbose=verbose)
    print(f"Total example elapsed: {time.perf_counter()-started:.2f}s")
    print("\nOK — all three QPE oracles land within one phase cell of the "
          "exact ground energy.")
    return 0


if __name__ == "__main__":
    raise SystemExit(main())

Combine block encodings: Fermi-Hubbard with T in momentum space

The Fermi-Hubbard Hamiltonian H = T + U has two pieces that are each diagonal in a different basis: the hopping T in momentum space, where its analytic dispersion eps(k) makes it a sum of single-qubit Z words, and the interaction U in real space. Encode each where it is cheap and combine: RotatedEncoding.from_orbital_rotation conjugates the momentum-diagonal PauliLCU of T by the Givens network of the standing-wave basis, and SumEncoding adds it to the real-space U with one slot qubit and one flag qubit, at alpha = alpha_T + alpha_U – below the flat PauliLCU of the same Hamiltonian (20 vs 24 on the 2x2 ring). The T/U split is the structure of Campbell’s Hubbard resource analysis (arXiv:2012.09238), realized here at the block-encoding level. The combined object is a BlockEncoding like any other: every block, the controlled variants, the even walk moments, a negative-coefficient shift H - E_ref I, and a QSVT sequence are verified against an independent sparse Jordan-Wigner reference.

"""Example 9 — Combine block encodings: Fermi-Hubbard with T in momentum space.

The 2D Fermi-Hubbard Hamiltonian splits into two pieces that are each
diagonal in a different basis::

    H = T + U,   T = -t sum_<ij>,s (a+_is a_js + h.c.),   U = u sum_i n_iu n_id

* ``T`` is diagonal in momentum space. On a periodic lattice its
  one-particle eigenmodes are known in closed form: plane waves with
  momentum ``k = (2 pi kx / lx, 2 pi ky / ly)`` and dispersion
  ``eps(k) = -2 t (cos kx + cos ky)``. Since ``eps(k) = eps(-k)``, the real
  standing waves ``cos(k . r)`` and ``sin(k . r)`` diagonalize ``T`` just
  as well, giving a real orthogonal basis in which ``T = sum_k eps(k) n_k``
  is a sum of single-qubit Z words with ``alpha_T = sum_k |eps(k)|``.
* ``U`` is diagonal in real space already: ``n_iu n_id`` is Z words in the
  computational basis.

Encode each piece where it is cheap, then combine. `RotatedEncoding`
conjugates the momentum-diagonal `PauliLCU` of ``T`` by the orbital
rotation into the momentum basis (`from_orbital_rotation` compiles the
real orthogonal mode matrix to a Givens-rotation network on both spin
sectors), and `SumEncoding` adds the two encodings with one slot qubit and
one flag qubit: ``alpha = alpha_T + alpha_U``. The result satisfies the
`BlockEncoding` protocol, so `Walk` and `QSVT` consume it unchanged, and
it beats a flat `PauliLCU` of the same Hamiltonian on ``alpha`` because the
hopping is encoded with ``sum_k |eps(k)|`` instead of the Jordan-Wigner
``XX + YY`` strings' one-norm.

Splitting ``T`` from ``U`` and treating ``T`` in the Fourier basis is the
structure exploited in Campbell's Hubbard resource analysis (Early
fault-tolerant simulations of the Hubbard model, arXiv:2012.09238), there
in split-operator Trotter form; this example realizes the same
decomposition at the block-encoding level.

Every encoded block is checked against an independent sparse Jordan-Wigner
reference, including a negative-coefficient sum (``H - E_ref I``) and a
short QSVT sequence against the dense 2x2 signal model. The default 2x2
ring (8 system + 6 ancilla qubits) runs on the CPU simulator; a larger
lattice (``--lx``, ``--ly``) above ``--max-qubits`` prints the alpha table
only.

Run: python3 09_hubbard_combined_encoding.py [--lx 2 --ly 2 --t 1 --u 4]
"""

from __future__ import annotations

import argparse
import math
import os
import sys

import cudaq
import numpy as np
import scipy.sparse as sp

from cudaq_algorithms import (BlockEncoding, PauliLCU, PhaseSequence, QSVT,
                              RotatedEncoding, SumEncoding, Walk, state_from)
from cudaq_algorithms import sim_utils as sim

# ----------------------------------------------------------------------
# The lattice. Sites are indexed site(ix, iy) = ix + lx * iy; spin
# orbitals are interleaved (2p up, 2p + 1 down), the library's
# Jordan-Wigner convention.
# ----------------------------------------------------------------------


def hopping_bonds(lx: int, ly: int) -> list[tuple[int, int]]:
    """Unique nearest-neighbor bonds of the lx x ly periodic lattice.

    Wrap-around bonds that coincide with an existing bond (length-2
    directions) are deduplicated, so the 2x2 lattice is the 4-site ring.
    """

    def site(ix, iy):
        return ix % lx + lx * (iy % ly)

    bonds = set()
    for iy in range(ly):
        for ix in range(lx):
            if lx > 1:
                bonds.add(tuple(sorted((site(ix, iy), site(ix + 1, iy)))))
            if ly > 1:
                bonds.add(tuple(sorted((site(ix, iy), site(ix, iy + 1)))))
    return sorted(bonds)


def hopping_matrix(lx: int, ly: int, t: float) -> np.ndarray:
    n = lx * ly
    matrix = np.zeros((n, n))
    for p, q in hopping_bonds(lx, ly):
        matrix[p, q] = matrix[q, p] = -t
    return matrix


def dispersion(lx: int, ly: int, t: float, kx: int, ky: int) -> float:
    """eps(k) with hopping_bonds' bond convention: a direction of length 1
    contributes nothing and a direction of length 2 has a single bond."""

    def direction(length: int, index: int) -> float:
        if length == 1:
            return 0.0
        factor = 1.0 if length == 2 else 2.0
        return -factor * t * math.cos(2.0 * math.pi * index / length)

    return direction(lx, kx) + direction(ly, ky)


def momentum_modes(lx: int, ly: int, t: float):
    """Real orthonormal momentum eigenbasis of the hopping matrix.

    Returns ``(modes, energies, labels)``: ``modes`` is ``n x n`` with the
    modes as columns, ``energies[m] = eps(k_m)``, and ``labels[m]`` names
    the momentum. Self-conjugate momenta (components 0 or pi) are already
    real plane waves; every other pair ``{k, -k}`` becomes the standing
    waves ``sqrt(2/N) cos(k . r)`` and ``sqrt(2/N) sin(k . r)``. Modes are
    ordered by increasing energy.
    """
    n = lx * ly
    ix = np.arange(n) % lx
    iy = np.arange(n) // lx
    columns, energies, labels = [], [], []
    seen = set()
    for ky in range(ly):
        for kx in range(lx):
            if (kx, ky) in seen:
                continue
            partner = ((lx - kx) % lx, (ly - ky) % ly)
            seen.add((kx, ky))
            seen.add(partner)
            phase = 2.0 * math.pi * (kx * ix / lx + ky * iy / ly)
            eps = dispersion(lx, ly, t, kx, ky)
            if partner == (kx, ky):
                columns.append(np.cos(phase) / math.sqrt(n))
                energies.append(eps)
                labels.append(f"k=({kx},{ky})")
            else:
                scale = math.sqrt(2.0 / n)
                columns.append(scale * np.cos(phase))
                energies.append(eps)
                labels.append(f"k=+-({kx},{ky}) cos")
                columns.append(scale * np.sin(phase))
                energies.append(eps)
                labels.append(f"k=+-({kx},{ky}) sin")
    order = np.argsort(energies, kind="stable")
    modes = np.column_stack([columns[i] for i in order])
    return (modes, np.array([energies[i]
                             for i in order]), [labels[i] for i in order])


def _z_word(num_qubits: int, *qubits: int) -> str:
    word = ["I"] * num_qubits
    for q in qubits:
        word[q] = "Z"
    return "".join(word)


def momentum_diagonal_words(energies: np.ndarray,
                            num_qubits: int) -> dict[str, float]:
    """T in its eigenbasis: sum_m eps_m n_m per spin, with n = (I - Z)/2."""
    words: dict[str, float] = {}
    constant = float(np.sum(energies))  # eps_m / 2 over both spins
    if abs(constant) > 1e-12:
        words["I" * num_qubits] = constant
    for m, eps in enumerate(energies):
        if abs(eps) > 1e-12:
            for spin in range(2):
                words[_z_word(num_qubits, 2 * m + spin)] = -0.5 * float(eps)
    return words


def interaction_words(num_sites: int, u: float,
                      num_qubits: int) -> dict[str, float]:
    """U = u sum_i n_iu n_id = u/4 sum_i (I - Z_2i - Z_2i+1 + Z_2i Z_2i+1)."""
    words: dict[str, float] = {"I" * num_qubits: 0.25 * u * num_sites}
    for i in range(num_sites):
        up, down = 2 * i, 2 * i + 1
        words[_z_word(num_qubits, up)] = -0.25 * u
        words[_z_word(num_qubits, down)] = -0.25 * u
        words[_z_word(num_qubits, up, down)] = 0.25 * u
    return words


def flat_hubbard_words(lx: int, ly: int, t: float,
                       u: float) -> dict[str, float]:
    """The full Hamiltonian as computational-frame Pauli words (baseline).

    A hopping bond (p < q) per spin is (X Z..Z X + Y Z..Z Y)/2 on the
    Jordan-Wigner string between the two modes, coefficient -t/2 each.
    """
    n = lx * ly
    num_qubits = 2 * n
    words = dict(interaction_words(n, u, num_qubits))
    for p, q in hopping_bonds(lx, ly):
        for spin in range(2):
            m1, m2 = 2 * p + spin, 2 * q + spin
            for pauli in ("X", "Y"):
                word = ["I"] * num_qubits
                word[m1] = pauli
                word[m2] = pauli
                for z in range(m1 + 1, m2):
                    word[z] = "Z"
                key = "".join(word)
                words[key] = words.get(key, 0.0) - 0.5 * t
    return {w: c for w, c in words.items() if abs(c) > 1e-12}


# ----------------------------------------------------------------------
# Independent sparse Jordan-Wigner reference (interleaved spins, qubit 0
# least significant, matching CUDA-Q's statevector order).
# ----------------------------------------------------------------------


def _sparse_annihilators(num_qubits: int) -> list[sp.csr_matrix]:
    z2 = sp.csr_matrix(np.diag([1.0, -1.0]))
    identity = sp.identity(2, format="csr")
    lowering = sp.csr_matrix(np.array([[0.0, 1.0], [0.0, 0.0]]))
    out = []
    for mode in range(num_qubits):
        ops = ([z2] * mode + [lowering] + [identity] *
               (num_qubits - mode - 1))[::-1]
        matrix = sp.identity(1, format="csr")
        for op in ops:
            matrix = sp.kron(matrix, op, format="csr")
        out.append(matrix)
    return out


def reference_hamiltonians(lx: int, ly: int, t: float, u: float):
    """Sparse (T, U) built directly from bonds and number operators."""
    n = lx * ly
    num_qubits = 2 * n
    lower = _sparse_annihilators(num_qubits)
    raise_ = [op.conj().T.tocsr() for op in lower]
    dim = 1 << num_qubits
    hopping = sp.csr_matrix((dim, dim), dtype=complex)
    for p, q in hopping_bonds(lx, ly):
        for spin in range(2):
            m1, m2 = 2 * p + spin, 2 * q + spin
            hopping = hopping - t * (raise_[m1] @ lower[m2] +
                                     raise_[m2] @ lower[m1])
    interaction = sp.csr_matrix((dim, dim), dtype=complex)
    for i in range(n):
        n_up = raise_[2 * i] @ lower[2 * i]
        n_down = raise_[2 * i + 1] @ lower[2 * i + 1]
        interaction = interaction + u * (n_up @ n_down)
    return hopping.tocsr(), interaction.tocsr()


def chebyshev_moment(h_scaled, ket: np.ndarray, order: int) -> float:
    """<ket| T_order(h_scaled) |ket> by the Chebyshev recurrence."""
    t_prev, t_cur = ket, h_scaled @ ket
    if order == 0:
        return float(np.real(ket.conj() @ t_prev))
    for _ in range(order - 1):
        t_prev, t_cur = t_cur, 2.0 * (h_scaled @ t_cur) - t_prev
    return float(np.real(ket.conj() @ t_cur))


def qsvt_response(sequence: PhaseSequence, x: float) -> complex:
    """Upper-left element of the 2x2 signal model of ``QSVT.kernel``.

    On an eigenstate with scaled eigenvalue ``x = lambda / alpha`` the
    good-subspace block of the circuit multiplies the state by this
    number. One forward walk step on the invariant 2D subspace is
    ``reflect_about_zero * block_encoding = diag(-1, 1) @ [[x, s], [s, -x]]``
    with ``s = sqrt(1 - x^2)`` (the walk's ``-H/alpha`` sign is folded in),
    and each qsvt-convention phase is ``diag(exp(i phi), 1)``.
    """
    s = math.sqrt(max(0.0, 1.0 - x * x))
    step = np.array([[-x, -s], [s, -x]], dtype=np.complex128)
    matrix = np.diag([np.exp(1.0j * sequence.phases[0]), 1.0])
    for phi in sequence.phases[1:]:
        matrix = np.diag([np.exp(1.0j * phi), 1.0]) @ step @ matrix
    return complex(matrix[0, 0])


# ----------------------------------------------------------------------
# Simulation helpers: the good-subspace block of each protocol kernel.
# ----------------------------------------------------------------------


def check(label: str, condition: bool):
    print(f"  [check] {label} ... {'OK' if condition else 'FAILED'}")
    if not condition:
        sys.exit(1)


def encoded_block(encoding, ket: np.ndarray) -> np.ndarray:
    state = cudaq.get_state(encoding.encode_kernel(), state_from(ket))
    return sim.good_subspace(encoding, state)


def controlled_blocks(encoding, ket: np.ndarray):
    """Good-subspace output of controlled_apply at control |0> and |1>."""
    controlled = encoding.controlled_apply_kernel()
    n_anc = encoding.num_ancilla
    dim = 1 << encoding.num_system

    @cudaq.kernel
    def circuit(state: cudaq.State, flip: bool):
        system = cudaq.qvector(state)
        control_and_ancilla = cudaq.qvector(1 + n_anc)
        if flip:
            x(control_and_ancilla[0])
        controlled(control_and_ancilla, system)
        if flip:
            x(control_and_ancilla[0])

    return [
        np.array(cudaq.get_state(circuit, state_from(ket), flip))[:dim]
        for flip in (False, True)
    ]


def controlled_roundtrips(encoding, ket: np.ndarray):
    """Controlled walk step followed by its controlled adjoint, at |0>, |1>."""
    step = encoding.controlled_walk_step_kernel()
    adjoint = encoding.controlled_adjoint_walk_step_kernel()
    n_anc = encoding.num_ancilla
    dim = 1 << encoding.num_system

    @cudaq.kernel
    def circuit(state: cudaq.State, flip: bool):
        system = cudaq.qvector(state)
        control_and_ancilla = cudaq.qvector(1 + n_anc)
        if flip:
            x(control_and_ancilla[0])
        step(control_and_ancilla, system)
        adjoint(control_and_ancilla, system)
        if flip:
            x(control_and_ancilla[0])

    return [
        np.array(cudaq.get_state(circuit, state_from(ket), flip))[:dim]
        for flip in (False, True)
    ]


def max_diff(a, b) -> float:
    return float(np.max(np.abs(np.asarray(a) - np.asarray(b))))


# ----------------------------------------------------------------------
# The story
# ----------------------------------------------------------------------


def main() -> int:
    cudaq.set_target(os.environ.get("CUDAQ_DEFAULT_SIMULATOR", "qpp-cpu"))

    parser = argparse.ArgumentParser(description=__doc__.splitlines()[0])
    parser.add_argument("--lx", type=int, default=2)
    parser.add_argument("--ly", type=int, default=2)
    parser.add_argument("--t", type=float, default=1.0)
    parser.add_argument("--u", type=float, default=4.0)
    parser.add_argument("--max-qubits",
                        type=int,
                        default=18,
                        help="skip the statevector checks above this many "
                        "qubits and report alphas only")
    args = parser.parse_args()
    lx, ly, t, u = args.lx, args.ly, args.t, args.u

    n = lx * ly
    num_qubits = 2 * n
    print(f"=== {lx}x{ly} Fermi-Hubbard (t = {t}, u = {u}): "
          f"{n} sites -> {num_qubits} system qubits ===")

    # 1. The analytic momentum basis: orthonormal, and it diagonalizes the
    #    hopping matrix with the closed-form dispersion.
    one_particle = hopping_matrix(lx, ly, t)
    modes, energies, labels = momentum_modes(lx, ly, t)
    check("momentum modes are orthonormal",
          max_diff(modes.T @ modes, np.eye(n)) < 1e-12)
    check("momentum modes diagonalize the hopping matrix with eps(k)",
          max_diff(modes.T @ one_particle @ modes, np.diag(energies)) < 1e-12)
    print("  dispersion, one line per mode (both spins share it):")
    for label, eps in zip(labels, energies):
        print(f"    {label:20s} eps = {eps:+.6f}")

    # 2. T diagonal in momentum space, rotated into the lattice frame; U
    #    diagonal in real space; the two summed.
    diagonal_t = PauliLCU(momentum_diagonal_words(energies, num_qubits))
    hopping = RotatedEncoding.from_orbital_rotation(diagonal_t, modes)
    interaction = PauliLCU(interaction_words(n, u, num_qubits))
    combined = SumEncoding([(1.0, hopping), (1.0, interaction)])
    check("the combined encoding satisfies the BlockEncoding protocol",
          isinstance(combined, BlockEncoding))

    # 3. The alpha table against a flat Pauli LCU of the same Hamiltonian.
    flat = PauliLCU(flat_hubbard_words(lx, ly, t, u))
    print(f"\n  alpha_T (momentum space) = {hopping.alpha:8.4f}  "
          f"({hopping.num_ancilla} ancillas)")
    print(f"  alpha_U (real space)     = {interaction.alpha:8.4f}  "
          f"({interaction.num_ancilla} ancillas)")
    print(f"  alpha (combined)         = {combined.alpha:8.4f}  "
          f"(= alpha_T + alpha_U; {combined.num_ancilla} ancillas: "
          f"{combined.num_slots} slot + flag + shared pool)")
    print(f"  alpha (flat PauliLCU)    = {flat.alpha:8.4f}  "
          f"({flat.num_terms} Pauli words, {flat.num_ancilla} ancillas)")
    check("combined alpha is below the flat PauliLCU alpha", combined.alpha
          < flat.alpha - 1e-12)

    total_qubits = num_qubits + combined.num_ancilla
    if total_qubits > args.max_qubits:
        print(f"\n  Statevector checks skipped: {total_qubits} qubits "
              f"> --max-qubits {args.max_qubits}.")
        return 0
    print(f"\n  Circuits: {num_qubits} system + {combined.num_ancilla} "
          f"ancilla = {total_qubits} qubits")

    # 4. Every block against the sparse Jordan-Wigner reference.
    hopping_ref, interaction_ref = reference_hamiltonians(lx, ly, t, u)
    hubbard = (hopping_ref + interaction_ref).tocsr()
    rng = np.random.default_rng(7)
    ket = rng.normal(
        size=1 << num_qubits) + 1.0j * rng.normal(size=1 << num_qubits)
    ket = (ket / np.linalg.norm(ket)).astype(np.complex128)

    error = max_diff(encoded_block(hopping, ket),
                     hopping_ref @ ket / hopping.alpha)
    check(f"T block == T/alpha_T (max |diff| = {error:.2e})", error < 1e-10)
    error = max_diff(encoded_block(interaction, ket),
                     interaction_ref @ ket / interaction.alpha)
    check(f"U block == U/alpha_U (max |diff| = {error:.2e})", error < 1e-10)
    error = max_diff(encoded_block(combined, ket),
                     hubbard @ ket / combined.alpha)
    check(f"combined block == (T + U)/alpha (max |diff| = {error:.2e})", error
          < 1e-10)

    # Control conventions: identity at |0>, the block at |1>; a controlled
    # walk step and its controlled adjoint round-trip at either value.
    at_zero, at_one = controlled_blocks(combined, ket)
    check("controlled apply is the identity at control |0>",
          max_diff(at_zero, ket) < 1e-10)
    check("controlled apply reproduces the block at control |1>",
          max_diff(at_one, hubbard @ ket / combined.alpha) < 1e-10)
    for value, state in enumerate(controlled_roundtrips(combined, ket)):
        check(
            f"controlled walk roundtrip is the identity at control |{value}>",
            max_diff(state, ket) < 1e-10)

    # 5. The combined object drops into Walk unchanged: even Chebyshev
    #    moments (the odd-moment observable hook is not available for a
    #    sum, see SumEncoding.select_observable).
    print("\n  Even Chebyshev moments <T_k(H/alpha)> through Walk:")
    scaled = hubbard / combined.alpha
    walk = Walk(combined)
    for order in (0, 2, 4):
        measured = walk.moment(ket, order)
        exact = chebyshev_moment(scaled, ket, order)
        print(
            f"    T_{order}: measured {measured:+.10f}   exact {exact:+.10f}")
        check(f"T_{order} moment matches the reference",
              abs(measured - exact) < 1e-8)

    # 6. A negative coefficient: shift the spectrum by the ground energy.
    #    SumEncoding([(1, H), (-E_ref, I)]) encodes (H - E_ref I) with
    #    alpha = alpha_H + |E_ref|; the identity is a one-term PauliLCU.
    dense = hubbard.toarray()
    e_ref = float(np.linalg.eigvalsh(dense)[0])
    identity = PauliLCU({"I" * num_qubits: 1.0})
    shifted = SumEncoding([(1.0, combined), (-e_ref, identity)])
    print(f"\n  Shifted H - E_ref I with E_ref = {e_ref:+.6f}: "
          f"alpha = {shifted.alpha:.4f} (= {combined.alpha:.4f} + "
          f"{abs(e_ref):.4f}), {shifted.num_ancilla} ancillas")
    error = max_diff(encoded_block(shifted, ket),
                     (hubbard @ ket - e_ref * ket) / shifted.alpha)
    check(f"shifted block == (H - E_ref I)/alpha (max |diff| = {error:.2e})",
          error < 1e-10)

    # 7. QSVT on the combined encoding: a degree-2 phase sequence against
    #    the dense signal model, eigenvalue by eigenvalue.
    sequence = PhaseSequence([0.3, -0.4, 0.25])
    device = sim.transform(QSVT(combined), ket, sequence)
    eigenvalues, eigenvectors = np.linalg.eigh(dense / combined.alpha)
    response = np.array(
        [qsvt_response(sequence, float(x)) for x in eigenvalues])
    host = eigenvectors @ (response * (eigenvectors.conj().T @ ket))
    error = max_diff(device, host)
    check(
        f"QSVT degree-{sequence.degree} sequence matches the signal model "
        f"(max |diff| = {error:.2e})", error < 1e-10)

    print("\nOK — T encoded in momentum space and U in real space, summed "
          "into one BlockEncoding that Walk and QSVT consume unchanged.")
    return 0


if __name__ == "__main__":
    raise SystemExit(main())

Sparse matrix inversion for heat diffusion

Start with a temperature pattern along a rod and ask what it becomes after one step of heat diffusion with fixed endpoint temperatures. A finite-difference model turns this physical question into a banded linear system. This example builds that system, solves it with NumPy, and uses a sparse quantum block encoding and an inverse polynomial to compute the same discrete update, connecting the earlier matrix tools to a recognizable application.

You should learn how the physical assumptions determine the matrix and its boundary entries, how a sparse inverse produces the updated temperature vector, and how to restore the output’s physical scale. The per-position table compares the ideal NumPy solution, a NumPy solution with the circuit’s rounded matrix coefficients, and the quantum result. Those comparisons show how matrix precision and inverse approximation contribute separately to error; they validate the chosen discrete problem, while accuracy relative to the continuous heat equation requires further space and time refinement.

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

One backward-Euler step in a rod produces a tridiagonal SPD matrix after fixed zero boundary values are eliminated. Arithmetic banded oracles feed the QSVT machinery; NumPy independently solves both the ideal matrix and the finite-angle matrix actually represented by the circuit. The example checks their encoded block, the long complex QSVT response, physical scale restoration, full-vector errors, and the residual separately.

The default two interior points and four angle bits require 14 total qubits. The full CKS inverse has degree 207 at the default 1e-2 target; a rigorously bounded Chebyshev tail below 1e-10 reduces the executed degree to 89. --full-cks retains the complete polynomial. At this default the four-bit matrix quantization, not the inverse polynomial, dominates the error budget. --points 4 is the four-position rod: 16 qubits, executing degree 99 of a degree-259 CKS polynomial, in seconds on an fp64 GPU and in minutes on the CPU simulator. The precision configuration --points 4 --value-bits 6 --inverse-epsilon 1e-3 uses 18 qubits and executes degree 125 of a degree-411 CKS polynomial; it runs in seconds on an fp64 GPU and in about twenty minutes on the CPU simulator. Degree depends on sparse normalization as well as physical conditioning. The per-node table compares initial, ideal NumPy, quantized NumPy, and QSVT temperatures. Full-state real-response extraction is simulator postprocessing; its raw good-block norm is not an isolated inverse-filter success probability.

The discretization follows the backward-Euler derivation. See Block encodings for sparse access and error budgets. The NumPy comparison validates the discrete system; a PDE convergence study would additionally test space/time accuracy.

For an optional saved figure, install Matplotlib and run python3 10_sparse_heat_equation.py --plot heat_step.png. Plotting is headless and includes both fixed endpoints. The default run requires QSPPACK but does not import Matplotlib.

"""One backward-Euler heat step in a rod, using a sparse QSVT inverse.

Start with a temperature pattern along a rod and ask what it becomes after one
step of heat diffusion with fixed endpoint temperatures. A finite-difference
model turns this physical question into a banded linear system. This example
builds that system, solves it with NumPy, and uses a sparse quantum block
encoding and an inverse polynomial to compute the same discrete update,
connecting the earlier matrix tools to a recognizable application.

You should learn how the physical assumptions determine the matrix and its
boundary entries, how a sparse inverse produces the updated temperature
vector, and how to restore the output's physical scale. The per-position table
compares the ideal NumPy solution, a NumPy solution with the circuit's rounded
matrix coefficients, and the quantum result. Those comparisons show how matrix
precision and inverse approximation contribute separately to error; they
validate the chosen discrete problem, while accuracy relative to the
continuous heat equation requires further space and time refinement.

Eliminating fixed zero endpoints gives A=tridiag(-r,1+2r,-r), where
r=D*dt/dx**2. N interior positions have dx=1/(N+1). Temperatures are above
ambient; D and dt are not assigned physical units here. NumPy solves the
same discrete system independently of the sparse quantum circuit.

The QSP real-response extraction uses full-state simulator postprocessing;
the raw good-block norm is not the success probability of an isolated
inverse filter. It does not demonstrate a coherent readout of every node.
Run: python3 10_sparse_heat_equation.py
The default (two interior positions, four angle bits, 1e-2 inverse target,
14 qubits) is sized for the CPU simulator. --points 4 is the four-position
rod on 16 qubits, and --points 4 --value-bits 6 --inverse-epsilon 1e-3 is
the 18-qubit precision configuration; both are practical on a GPU.
Optional: --plot heat_step.png
Add --verbose to show individual validation checks; failures are always reported.
"""

import argparse
import contextlib
import io
import os
from pathlib import Path
import time

import cudaq
import numpy as np
from numpy.polynomial import chebyshev
from scipy.stats import binom

from cudaq_algorithms import PhaseSequence, QSVT
from cudaq_algorithms import sim_utils as sim
from cudaq_algorithms.sparse import SparseOracleEncoding, banded_oracles

BLOCK_ATOL = 1e-10
CIRCUIT_ATOL = 1e-8
PHASE_ATOL = 2e-8
MAX_QUBITS = 20
MAX_DEGREE = 511


def 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'}",
            flush=True)
    if not passed:
        raise AssertionError(label)


def quantized_matrix(matrix, h, bits):
    """Independent public angle-format reference, including the top clamp."""
    result = np.zeros_like(matrix)
    for row, column in zip(*np.nonzero(matrix)):
        value = matrix[row, column]
        theta = np.arcsin(np.sqrt(abs(value) / h))
        code = min((1 << bits) - 1, round((1 << bits) * theta / (np.pi / 2)))
        result[row, column] = np.sign(value) * h * np.sin(np.pi * code /
                                                          (2 * (1 << bits)))**2
    return result


def inverse_polynomial(x_min, epsilon, full_cks=False, *, verbose=False):
    """CKS coefficients, adapted from example 07, with stable binomial tails.

    P[Binomial(2B,1/2)>B+j] replaces integer sums divided by 2**(2B),
    avoiding overflow. c=0.9/sqrt(B) gives analytical global headroom since
    |[1-(1-x*x)**B]/x| <= min(B*|x|,1/|x|) <= sqrt(B).
    """
    half_degree = max(3, int(np.ceil(np.log(1 / epsilon) / x_min**2)))
    degree = 2 * half_degree - 1
    print(
        f"CKS B={half_degree}, degree={degree}, requested relative "
        f"inverse target={epsilon:.3e}",
        flush=True)
    if degree > MAX_DEGREE:
        raise ValueError(
            f"degree {degree} exceeds example guard {MAX_DEGREE}; "
            "choose a less expensive explicit configuration")
    scale = .9 / np.sqrt(half_degree)
    indices = np.arange(half_degree)
    odd = scale * 4 * (-1.)**indices * binom.sf(half_degree + indices,
                                                2 * half_degree, .5)
    # CKS's degree bound is conservative. Its high-order Chebyshev
    # coefficients are tiny binomial tails. Since |T_k(x)| <= 1, the sum
    # of discarded absolute coefficients rigorously bounds the change
    # everywhere on [-1,1]. Keep this below 1e-10 and account for it
    # separately; the requested matrix precision and inverse target stay
    # unchanged. --full-cks executes every degree of the original recipe.
    tails = np.r_[np.cumsum(np.abs(odd[::-1]))[::-1], 0.]
    retained = half_degree
    if not full_cks:
        tail_target = min(1e-10, .01 * epsilon * scale)
        retained = next(k for k in range(1, half_degree + 1)
                        if tails[k] <= tail_target)
        if np.exp(-half_degree * x_min *
                  x_min) + tails[retained] / scale > epsilon:
            retained = half_degree
    tail_bound = float(tails[retained])
    odd = odd[:retained]
    degree = 2 * retained - 1
    print(
        f"Executed degree={degree}; discarded Chebyshev tail bound="
        f"{tail_bound:.3e} on all [-1,1]",
        flush=True)
    check("combined CKS and tail relative bound",
          np.exp(-half_degree * x_min * x_min) + tail_bound / scale,
          epsilon,
          verbose=verbose)
    coefficients = np.zeros(degree + 1)
    coefficients[1::2] = odd
    if not np.all(np.isfinite(coefficients)):
        raise ValueError(
            "inverse coefficient construction produced nonfinite values")
    return half_degree, scale, odd, coefficients, tail_bound


def qsp_response(phases, values):
    """Complex raw device response from an independent 2x2 signal model."""
    responses = []
    for x in values:
        s = np.sqrt(max(0., 1 - x * x))
        step = np.array([[-x, -s], [s, -x]], dtype=complex)
        result = np.diag([np.exp(1j * phases[0]), np.exp(-1j * phases[0])])
        for phase in phases[1:]:
            result = np.diag([np.exp(1j * phase),
                              np.exp(-1j * phase)]) @ step @ result
        responses.append(np.exp(1j * np.sum(phases)) * result[0, 0])
    return np.array(responses)


def save_plot(path, positions, initial, numpy_solution, qsvt_solution):
    import matplotlib
    matplotlib.use("Agg")
    import matplotlib.pyplot as plt

    figure, axis = plt.subplots(figsize=(7, 4))
    x = np.r_[0., positions, 1.]
    for values, label, marker in ((initial, "Initial", "o"),
                                  (numpy_solution, "NumPy next step", "s"),
                                  (qsvt_solution, "QSVT reconstruction", "x")):
        axis.plot(x, np.r_[0., values, 0.], marker=marker, label=label)
    axis.set(xlabel="Position x/L",
             ylabel="Temperature above ambient",
             title="One implicit heat-diffusion step")
    axis.legend()
    axis.grid(alpha=.25)
    figure.tight_layout()
    path = path.expanduser().resolve()
    path.parent.mkdir(parents=True, exist_ok=True)
    figure.savefig(path, dpi=160)
    plt.close(figure)
    print(f"Plot saved: {path}")


def arguments():
    parser = argparse.ArgumentParser(description=__doc__)
    parser.add_argument(
        "--points",
        type=int,
        default=2,
        help="interior positions, a power of two (4 is the 16-qubit rod)")
    parser.add_argument("--r", type=float, default=.25)
    parser.add_argument("--value-bits", type=int, default=4)
    parser.add_argument("--inverse-epsilon", type=float, default=1e-2)
    parser.add_argument("--plot", type=Path)
    parser.add_argument(
        "--full-cks",
        action="store_true",
        help="execute the uncompressed CKS polynomial (much slower on CPU)")
    parser.add_argument(
        "--verbose",
        action="store_true",
        help="show each validation check (failures are always reported)")
    args = parser.parse_args()
    if args.points < 2 or args.points & (args.points - 1):
        parser.error("--points must be a power of two, at least 2")
    if not np.isfinite(args.r) or args.r <= 0:
        parser.error("--r must be finite and positive")
    if not 1 <= args.value_bits <= 12:
        parser.error("--value-bits must lie in [1,12]")
    if not np.isfinite(
            args.inverse_epsilon) or not 0 < args.inverse_epsilon < .1:
        parser.error("--inverse-epsilon must lie strictly between 0 and 0.1")
    system_bits = args.points.bit_length() - 1
    # Three bands pad to four slots. Guard before constructing matrices,
    # kernels, coefficient arrays, or statevectors.
    if 2 * system_bits + args.value_bits + 8 > MAX_QUBITS:
        parser.error(
            f"requested geometry exceeds the {MAX_QUBITS}-qubit example guard")
    return args


def main():
    args = arguments()
    verbose = args.verbose
    started = time.perf_counter()
    target = os.environ.get("CUDAQ_DEFAULT_SIMULATOR", "qpp-cpu")
    if target == "nvidia":
        cudaq.set_target(target, option="fp64")
    else:
        cudaq.set_target(target)
    n, r = args.points, args.r
    dx = 1 / (n + 1)
    positions = np.arange(1, n + 1) * dx
    initial = np.zeros(n)
    initial[1] = 1.
    beta = float(np.linalg.norm(initial))
    if not np.isfinite(beta) or beta <= 0:
        raise ValueError(
            "the initial temperature must have finite nonzero norm")
    ideal = (np.diag(np.full(n, 1 + 2 * r)) + np.diag(np.full(n - 1, -r), 1) +
             np.diag(np.full(n - 1, -r), -1))
    numpy_solution = np.linalg.solve(ideal, initial)
    spectrum = 1 + 2 * r - 2 * r * np.cos(
        np.arange(1, n + 1) * np.pi / (n + 1))
    check("analytic SPD spectrum",
          np.max(np.abs(np.linalg.eigvalsh(ideal) - spectrum)),
          BLOCK_ATOL,
          verbose=verbose)
    check("ideal NumPy residual",
          np.linalg.norm(ideal @ numpy_solution - initial),
          BLOCK_ATOL,
          verbose=verbose)
    rational = {
        2: np.array([4., 24.]) / 35.,
        4: np.array([140., 840., 144., 24.]) / 1189.
    }
    if r == .25 and n in rational:
        check("closed-form rational NumPy solution",
              np.max(np.abs(numpy_solution - rational[n])),
              BLOCK_ATOL,
              verbose=verbose)
    print(
        f"N={n}, L=1, dx={dx:.6f}, r=D*dt/dx**2={r}; "
        "fixed zero endpoints are eliminated",
        flush=True)

    system_bits = n.bit_length() - 1
    oracles = banded_oracles([-1, 0, 1], [-r, 1 + 2 * r, -r],
                             num_system=system_bits,
                             value_bits=args.value_bits)
    encoding = SparseOracleEncoding(oracles, num_system=system_bits)
    check("three bands pad to four slots",
          abs(encoding.d_padded - 4),
          0.,
          verbose=verbose)
    check("sparse normalization",
          abs(encoding.alpha - 4 * (1 + 2 * r)),
          BLOCK_ATOL,
          verbose=verbose)
    print(
        f"system={encoding.num_system}, block ancillas={encoding.num_block_ancilla}, "
        f"scratch={encoding.num_scratch}, all ancillas={encoding.num_ancilla}, "
        f"total={encoding.num_system+encoding.num_ancilla}, "
        f"angle bits={encoding.value_bits}, slots={encoding.d}/{encoding.d_padded}, "
        f"h={encoding.h}, alpha={encoding.alpha}",
        flush=True)
    realized = quantized_matrix(ideal, encoding.h, args.value_bits)
    values, vectors = np.linalg.eigh(realized)
    normalized = values / encoding.alpha
    if not np.all((normalized > 0) & (normalized <= 1)):
        raise ValueError(
            "the quantized matrix must have spectrum in (0,alpha]")
    quantized_solution = np.linalg.solve(realized, initial)
    half_degree, scale, odd, coefficients, tail_bound = inverse_polynomial(
        float(normalized.min()),
        args.inverse_epsilon,
        args.full_cks,
        verbose=verbose)
    domain = np.linspace(normalized.min(), normalized.max(), 257)
    polynomial = chebyshev.chebval(domain, coefficients)
    check("CKS relative inverse approximation on interval",
          np.max(np.abs(1 - domain * polynomial / scale)),
          args.inverse_epsilon + 1e-12,
          verbose=verbose)
    grid = np.linspace(-1., 1., 4097)
    check("global polynomial headroom",
          np.max(np.abs(chebyshev.chebval(grid, coefficients))),
          .9 + 1e-12,
          verbose=verbose)

    try:
        import qsppack
    except ImportError as error:
        raise SystemExit(
            "This example needs QSPPACK: pip install qsppack") from error
    options = {
        "criteria": 1e-10,
        "method": "Newton",
        "typePhi": "full",
        "useReal": True,
        "targetPre": True
    }
    with contextlib.redirect_stdout(io.StringIO()):
        phases, _ = qsppack.solve(odd.copy(), 1, options)
    phases = [float(phase) for phase in phases]
    if len(phases) != len(coefficients):
        raise AssertionError("QSPPACK returned the wrong phase count")
    response = qsp_response(phases, normalized)
    # The walk signal is -A/alpha. Odd CKS parity therefore contributes a
    # minus sign, and doubled projector phases add exp(i*sum(raw phases)).
    # Both corrections are analytical; the scalar model verifies them.
    corrected = -(response * np.exp(-1j * np.sum(phases))).real
    intended = chebyshev.chebval(normalized, coefficients)
    phase_error = float(np.max(np.abs(corrected - intended)))
    check("phase synthesis on actual spectrum",
          phase_error,
          PHASE_ATOL,
          verbose=verbose)
    probes = qsp_response(phases, domain)
    check("phase synthesis on interval probes",
          np.max(
              np.abs(-(probes * np.exp(-1j * np.sum(phases))).real -
                     polynomial)),
          PHASE_ATOL,
          verbose=verbose)
    print(
        f"phases={len(phases)}, analytical c={scale:.9f}, beta={beta}; "
        f"physical recovery beta/(c*alpha)={beta/(scale*encoding.alpha):.9f}",
        flush=True)

    columns = []
    for index in range(n):
        basis = np.zeros(n, dtype=complex)
        basis[index] = 1.
        columns.append(sim.action(encoding, basis))
    block = np.column_stack(columns)
    check("circuit block versus independently quantized matrix",
          np.max(np.abs(encoding.alpha * block - realized)),
          BLOCK_ATOL,
          verbose=verbose)
    if n > 2:
        check("no end-to-end corner coupling",
              np.max(np.abs(block[[0, n - 1], [n - 1, 0]])),
              BLOCK_ATOL,
              verbose=verbose)
    print("Executing the sparse QSVT circuit...", flush=True)
    ket = np.asarray(initial / beta, dtype=complex)
    raw = sim.run_on_large_stack(sim.transform, QSVT(encoding), ket,
                                 PhaseSequence(phases, convention="qsp"))
    expected_raw = vectors @ (response * (vectors.conj().T @ ket))
    check("raw complex QSVT block versus scalar model",
          np.max(np.abs(raw - expected_raw)),
          CIRCUIT_ATOL,
          verbose=verbose)
    reconstructed = -(raw * np.exp(-1j * np.sum(phases))).real * beta / (
        scale * encoding.alpha)
    quantization_error = float(np.linalg.norm(realized - ideal, 2))
    inverse_norm = 1 / values.min()
    coefficient_bound = inverse_norm * quantization_error * np.linalg.norm(
        numpy_solution)
    polynomial_bound = args.inverse_epsilon * np.linalg.norm(
        quantized_solution)
    truncation_bound = beta * tail_bound / (scale * encoding.alpha)
    phase_bound = beta * phase_error / (scale * encoding.alpha)
    roundoff_bound = beta * np.sqrt(n) * CIRCUIT_ATOL / (scale *
                                                         encoding.alpha)
    solve_bound = polynomial_bound + truncation_bound + phase_bound + roundoff_bound
    total_bound = coefficient_bound + solve_bound
    check("quantized versus ideal solve",
          np.linalg.norm(quantized_solution - numpy_solution),
          coefficient_bound + 1e-12,
          verbose=verbose)
    check("QSVT versus quantized NumPy solve",
          np.linalg.norm(reconstructed - quantized_solution),
          solve_bound,
          verbose=verbose)
    check("QSVT versus ideal NumPy solve",
          np.linalg.norm(reconstructed - numpy_solution),
          total_bound,
          verbose=verbose)

    relative_error = np.linalg.norm(
        reconstructed - numpy_solution) / np.linalg.norm(numpy_solution)
    fidelity = abs(np.vdot(reconstructed, numpy_solution))**2 / (
        np.linalg.norm(reconstructed)**2 * np.linalg.norm(numpy_solution)**2)
    residual = np.linalg.norm(ideal @ reconstructed - initial) / beta
    residual_bound = np.linalg.norm(ideal, 2) * total_bound / beta
    check("relative physical residual",
          residual,
          residual_bound,
          verbose=verbose)
    print(
        f"matrix quantization norm={quantization_error:.6e}; "
        f"quantized-solve relative error="
        f"{np.linalg.norm(quantized_solution-numpy_solution)/np.linalg.norm(numpy_solution):.6e}"
    )
    print(f"error bounds: coefficients={coefficient_bound:.3e}, "
          f"polynomial={polynomial_bound:.3e}, tail={truncation_bound:.3e}, "
          f"phases={phase_bound:.3e}, "
          f"roundoff={roundoff_bound:.3e}, total={total_bound:.3e}")
    print(
        "\nPosition   Initial      NumPy       Quantized NumPy    QSVT        Abs error"
    )
    for x, before, exact, rounded, output in zip(positions, initial,
                                                 numpy_solution,
                                                 quantized_solution,
                                                 reconstructed):
        print(f"{x:8.4f} {before:9.5f} {exact:13.9f} {rounded:15.9f} "
              f"{output:13.9f} {abs(output-exact):11.3e}")
    print(f"full-vector relative error={relative_error:.6e}; "
          f"direction fidelity={fidelity:.9f}; residual={residual:.6e}")
    print(
        "Raw good-block norm is not isolated inverse-filter success probability."
    )
    print(
        "Full-state and real-response extraction are simulator postprocessing."
    )
    print("These checks validate the discrete solve; PDE space/time accuracy "
          "needs a separate convergence study.")
    if args.plot:
        save_plot(args.plot, positions, initial, numpy_solution, reconstructed)
    print(
        f"Maximum executed qubits: {encoding.num_system+encoding.num_ancilla}; "
        f"degree={len(phases)-1} (full CKS {2*half_degree-1}); "
        f"elapsed: {time.perf_counter()-started:.2f}s")


if __name__ == "__main__":
    main()