算法库（顶层）

备注

SparQ_Algorithm/include/qcnn.h``（量子卷积网络）当前在源码中被 ``#if false 整体禁用，故不出现在本参考中。

Grover 搜索（SparQ_Algorithm/include/grover.h）

Grover quantum search algorithm (two interface sets: sparse state / dense state)

Provides register-level-programming-based Grover components: QRAM phase oracle (GroverOracle), HPH diffusion operator, full iteration (GroverOperator), repeated amplitude amplification (GroverAmplify), and quantum counting (GroverCount), which search for a marked item among N entries with O(√N) complexity. Also contains the legacy dense-state interface under the grover_dense namespace (operating directly on the std::vector<complex_t> state vector), as distinct from the new sparse-state interface in the grover namespace

namespace qram_simulator

QRAM sparse state simulator namespace.

Contains all classes, functions, and data structures related to quantum computing simulation

namespace grover

Sparse-state interface of Grover's algorithm (register-level programming)

struct GroverAmplify

#include <grover.h>

Multi-round amplitude amplification operator.

Executes the GroverOperator iteration n_repeats times in a row, amplifying the measurement probability of the marked item to close to 1

Public Functions

inline GroverAmplify(qram_qutrit::QRAMCircuit *qram_, size_t qram_address_id_, size_t search_data_id_, size_t data_size_, size_t n_repeats_)

Constructor.

参数:

• qram_ -- QRAM circuit pointer

• qram_address_id_ -- Address register ID

• search_data_id_ -- Search-target register ID

• data_size_ -- Search-target value bit width

• n_repeats_ -- Number of iterations

void operator()(std::vector<System> &state)

Apply multi-round amplitude amplification.

参数:

state -- System state vector

Public Members

size_t n_repeats

Number of iterations.

size_t qram_address_id

QRAM address register ID.

size_t qram_data_id

QRAM data register ID.

size_t search_data_id

Search-target register ID.

size_t data_size

Bit width of the search-target value.

qram_qutrit::QRAMCircuit *qram

QRAM circuit pointer.

struct GroverCount

#include <grover.h>

Quantum counting operator.

Circuit structure: Hadamard prepares the counting register in superposition → powers of the Grover iteration controlled by the counting register (c-U^{2^k}) → inverse QFT on the counting register, thereby estimating the number of marked items M (phase-estimation view: sin²θ = M/N)

Public Functions

inline GroverCount(qram_qutrit::QRAMCircuit *qram_, size_t count_reg_, size_t addr_reg_, size_t data_reg_, size_t search_data_reg_)

Constructor.

参数:

• qram_ -- QRAM circuit pointer

• count_reg_ -- Counting register ID

• addr_reg_ -- Address register ID

• data_reg_ -- Data register ID

• search_data_reg_ -- Search-target register ID

void operator()(std::vector<System> &state)

Perform quantum counting.

参数:

state -- System state vector

Public Members

size_t count_reg

Counting register ID.

size_t addr_reg

QRAM address register ID.

size_t data_reg

QRAM data register ID.

size_t search_data_reg

Search-target register ID.

qram_qutrit::QRAMCircuit *qram

QRAM circuit pointer.

struct GroverOperator

#include <grover.h>

Single full Grover iteration operator.

Combines GroverOracle (phase marking) with HPH (diffusion reflection) to form one standard Grover iteration G = HPH · Oracle. Supports conditional control (ClassControllable)

Public Functions

inline ClassControllable GroverOperator(qram_qutrit::QRAMCircuit *qram_, size_t qram_address_id_, size_t qram_data_id_, size_t search_data_id_)

Constructor.

参数:

• qram_ -- QRAM circuit pointer

• qram_address_id_ -- Address register ID

• qram_data_id_ -- Data register ID

• search_data_id_ -- Search-target register ID

void operator()(std::vector<System> &state) const

Apply a single Grover iteration.

参数:

state -- System state vector

Public Members

size_t qram_address_id

QRAM address register ID.

size_t qram_data_id

QRAM data register ID.

size_t search_data_id

Search-target register ID.

qram_qutrit::QRAMCircuit *qram

QRAM circuit pointer.

struct GroverOracle

#include <grover.h>

QRAM-based Grover phase oracle.

Loads the memory data into the data register via QRAM, applies a phase flip to the branches equal to the search target, then unloads (uncomputes) the data register, realizing phase-kickback-style marking: |x⟩|0⟩ → (-1)^{f(x)} |x⟩|0⟩. Supports conditional control (ClassControllable)

Public Functions

inline ClassControllable GroverOracle(qram_qutrit::QRAMCircuit *qram_, size_t qram_address_id_, size_t qram_data_id_, size_t search_data_id_)

Constructor (register-ID version)

参数:

• qram_ -- QRAM circuit pointer

• qram_address_id_ -- Address register ID

• qram_data_id_ -- Data register ID

• search_data_id_ -- Search-target register ID

inline GroverOracle(qram_qutrit::QRAMCircuit *qram_, std::string_view qram_address_, std::string_view qram_data_, std::string_view search_data_)

Constructor (register-name version)

参数:

• qram_ -- QRAM circuit pointer

• qram_address_ -- Address register name

• qram_data_ -- Data register name

• search_data_ -- Search-target register name

void operator()(std::vector<System> &state) const

Apply the oracle operation.

参数:

state -- System state vector

Public Members

size_t qram_address_id

QRAM address register ID.

size_t qram_data_id

QRAM data register ID.

size_t search_data_id

Search-target register ID (holds the value to match)

qram_qutrit::QRAMCircuit *qram

QRAM circuit (qutrit/qubit implementation) pointer.

struct HPH

#include <grover.h>

H-P-H diffusion operator.

The H⊗n · phase flip · H⊗n form of the Grover diffusion operator: applies Hadamard to the address register, then flips the phase of the |0...0⟩ branch, then applies Hadamard again, realizing reflection about the uniform superposition state. Supports conditional control (ClassControllable)

Public Functions

inline ClassControllable HPH(size_t qram_address_id_)

Constructor (register-ID version)

参数:

qram_address_id_ -- Address register ID

inline HPH(std::string qram_address_name, size_t size_)

Constructor (register-name version)

参数:

• qram_address_name -- Address register name

• size_ -- Register bit width

void operator()(std::vector<System> &state) const

Apply the diffusion operation.

参数:

state -- System state vector

Public Members

size_t qram_address_id

Address register ID.

size_t size

Register bit width (cached from the global register table at construction)

namespace grover_dense

Legacy dense-state interface of Grover's algorithm.

Operates directly on the full std::vector<complex_t> state vector, together with QRAM circuits and noise models, for interfacing with the dense-state simulator of the QRAM-Simulator base; new code is advised to use the sparse-state interface in the grover namespace

Functions

template<typename QRAM>
void oracle(std::vector<complex_t> &state, size_t n, QRAM *qram, std::string version)

Apply the QRAM oracle to a dense state.

Applies the QRAM with address bits [0, n) and data bit n, the remaining bits being otherqubit; after execution, verifies state normalization, printing the state and throwing an exception on failure

模板参数:

QRAM -- QRAM circuit type (qutrit/qubit implementation)

参数:

• state -- Dense state vector (input and output)

• n -- Address bit width

• qram -- QRAM circuit pointer

• version -- QRAM circuit version string

void diffusion(std::vector<complex_t> &state, size_t n)

Grover diffusion operator (reflection about the mean)

参数:

• state -- Dense state vector (input and output)

• n -- Address bit width

void grover(std::vector<complex_t> &state, size_t n, size_t pos, size_t repeat, std::function<void(decltype(state))> oracle)

Perform a full Grover iteration (oracle + diffusion)

参数:

• state -- Dense state vector (input and output)

• n -- Address bit width

• pos -- Position of the marked item in memory

• repeat -- Number of iterations

• oracle -- Oracle callback (takes a reference to the dense state)

template<typename QRAM>
std::vector<size_t> grover_shots(size_t n, size_t pos, size_t shots, size_t repeat, const std::map<OperationType, double> &noise, std::string version)

Run Grover search with multiple samples and tally the measurement results.

Each sample re-prepares the initial state, performs the specified number of Grover iterations, then measures, keeping only the lowest n bits (address bits) of the measurement result

模板参数:

QRAM -- QRAM circuit type

参数:

• n -- Address bit width

• pos -- Position of the marked item in memory

• shots -- Number of samples

• repeat -- Number of Grover iterations per sample

• noise -- Noise model parameters for each operation type

• version -- QRAM circuit version string

返回:

Vector of length 2^n whose i-th entry is the number of times address i was measured

Shor 因数分解（SparQ_Algorithm/include/shor.h）

Shor's quantum factoring algorithm (standard + semi-classical versions)

Implements the quantum part of Shor's algorithm via register-level programming: the modular exponentiation operator ExpMod (|x⟩|z⟩ → |x⟩|z·a^x mod N⟩), the full phase-estimation-style pipeline (Shor) and the semi-classical (measurement-feedback) variant SemiClassicalShor, plus classical postprocessing helpers such as the continued-fractions finisher. The corresponding Python implementation is in pysparq.algorithms.shor; the C++ experiment entry points are in Experiments/Shor

namespace qram_simulator

QRAM sparse state simulator namespace.

Contains all classes, functions, and data structures related to quantum computing simulation

namespace shor

Shor's factoring algorithm components.

Typedefs

using ExpModFunc = std::function<size_t(size_t)>

Modular exponentiation function type: x ↦ a^x mod N (wrapped from classical precomputation)

Functions

size_t general_expmod(size_t a, size_t x, size_t N)

Compute the large-exponent modular power a^x mod N.

参数:

• a -- Base

• x -- Exponent (arbitrarily large integer)

• N -- Modulus (the odd composite to be factored)

返回:

a^x mod N

inline void throw_bad_shor_result(const std::string &message)

Throw a Shor execution failure exception.

参数:

message -- Exception description

std::pair<size_t, size_t> find_best_fraction(size_t y, size_t Q, size_t N)

Find the numerator and denominator of the best continued-fractions approximation y/Q for a measured value.

参数:

• y -- Phase-estimation measured value

• Q -- Denominator upper bound (usually 2^size)

• N -- Number to be factored (the approximation's denominator must be less than N)

返回:

(numerator, denominator) pair of the best approximation

uint64_t compute_period(uint64_t meas_result, size_t size, size_t N)

Compute the period r from a measurement result.

参数:

• meas_result -- Phase-estimation measured value

• size -- Working register bit width

• N -- Number to be factored

返回:

Candidate period (0 means failure)

void check_period(uint64_t period, uint64_t a, uint64_t N)

Validate a period candidate: r must be even and a^{r/2} ≢ -1 (mod N)

参数:

• period -- Period candidate

• a -- Base

• N -- Number to be factored

抛出:

ShorExecutionFailed -- Thrown when validation fails

std::tuple<uint64_t, uint64_t> shor_postprocess(uint64_t meas, size_t size, uint64_t a, uint64_t N)

Shor classical postprocessing: recover the period from a measured value and compute factors.

参数:

• meas -- Phase-estimation measured value

• size -- Working register bit width

• a -- Base

• N -- Number to be factored

抛出:

ShorExecutionFailed -- Thrown when no valid period can be recovered

返回:

(p, q) factor pair (invalid values on failure)

inline int common_shor(size_t N, std::optional<size_t> ainput = std::nullopt)

Full standard Shor factorization pipeline (C++ experiment entry point)

Random (or specified) base a → precompute the modular exponentiation table → quantum phase estimation → partial-trace readout → continued-fractions postprocessing to output the factors

参数:

• N -- Odd composite to be factored

• ainput -- Optionally specified base (chosen at random by default)

返回:

0 means the pipeline completed; 1 means a and N are not coprime (in that case gcd(a,N) is already a factor)

inline auto semi_classical_shor(size_t N, std::optional<size_t> ainput = std::nullopt)

Full semi-classical Shor factorization pipeline (C++ experiment entry point)

Same classical preparation as common_shor, but the quantum part instead uses SemiClassicalShor's bit-by-bit measurement-feedback phase estimation

参数:

• N -- Odd composite to be factored

• ainput -- Optionally specified base (chosen at random by default)

返回:

0 means the pipeline completed; 1 means a and N are not coprime (in that case gcd(a,N) is already a factor)

struct ExpMod : public qram_simulator::SelfAdjointOperator

#include <shor.h>

Modular exponentiation quantum operator (self-adjoint)

Implements |x⟩|z⟩ → |x⟩|z · (a^x mod N)⟩; the modular exponentiation function is supplied by the classically precomputed ExpModFunc (a lookup table of a^x mod N over one period r), so the quantum side only performs a function-table-lookup-style transform

Public Functions

inline ExpMod(size_t reg_input_, size_t reg_output_, ExpModFunc func)

Constructor.

参数:

• reg_input_ -- Input register ID

• reg_output_ -- Output register ID

• func -- Modular exponentiation function

virtual void operator()(std::vector<System> &state) const

Apply the modular exponentiation operation.

参数:

state -- System state vector

Public Members

size_t reg_input

Input (exponent) register ID.

size_t reg_output

Output (power value) register ID.

ExpModFunc anc_func

Classically precomputed modular exponentiation function.

struct SemiClassicalShor

#include <shor.h>

Semi-classical Shor factorizer (measurement-feedback quantum phase estimation)

Replaces the full inverse QFT with bit-by-bit measurement + feedback rotation: after each measured bit, a conditional phase rotation is applied to the remaining superposition based on the bits measured so far, significantly reducing the number of qubits required. run() executes the quantum part and reads out via partial trace; postprocess() recovers the period via continued fractions and produces the factorization result

Public Functions

inline SemiClassicalShor(size_t a_, size_t N_, size_t n_)

Constructor.

参数:

• a_ -- Random base (coprime with N)

• N_ -- Odd composite to be factored

• n_ -- Number of binary digits of N

size_t run()

Execute the quantum part (semi-classical phase estimation + partial-trace readout)

返回:

Measured result as an integer value

void postprocess()

Classical postprocessing: recover the period via continued fractions and compute factors p, q.

Public Members

size_t a

Random base a (coprime with N)

size_t n

Number of binary digits of N.

size_t N

Odd composite N to be factored.

size_t size

Working register bit width (2n)

size_t meas_result = 0

Final measurement result (filled by run())

size_t period = 0

Recovered period r (filled by postprocess(), 0 means failure)

size_t p = 0

Factor p (filled by postprocess())

size_t q = 0

Factor q (filled by postprocess())

struct Shor

#include <shor.h>

Standard Shor factorization operator (phase-estimation style)

After the working register is prepared in superposition, ExpMod performs modular exponentiation, then a partial trace over the working register (equivalent to inverse-QFT sampling) reads out the phase information, from which the period is recovered by classical postprocessing

Public Functions

inline Shor(size_t work_register, size_t ancilla_register, size_t a_, size_t N_, ExpModFunc func)

Constructor.

参数:

• work_register -- Working register ID

• ancilla_register -- Ancillary register ID

• a_ -- Base a (kept for semantics only; actual computation goes through func)

• N_ -- Modulus N (kept for semantics only)

• func -- Modular exponentiation function

void operator()(std::vector<System> &state) const

Execute the quantum part of Shor's algorithm.

参数:

state -- System state vector

Public Members

size_t work_reg

Working register ID (holds the superposed exponent x)

size_t ancilla_reg

Ancillary register ID (holds a^x mod N)

ExpModFunc anc_func

Classically precomputed modular exponentiation function.

class ShorExecutionFailed : public std::runtime_error

#include <shor.h>

Shor execution failure exception.

Thrown in scenarios such as when the measurement results cannot yield a valid period (postprocessing failure)

Public Functions

inline ShorExecutionFailed(const std::string &message)

Constructor.

参数:

message -- Exception description

态制备（SparQ_Algorithm/include/state_preparation.h）

QRAM-based arbitrary sparse state preparation.

Prepares the target distribution via layer-by-layer amplitude splitting over a binary tree: each layer splits 1 rotation qubit off the working register, uses the QRAM to read the parent/child node amplitudes and compute the ratio angle, applies the conditional rotation (CondRot_Fixed_Bool) and then unloads the ancillary registers. Contains the operator version (State_Prep_via_QRAM) and a demo driver (the state_preparation_demo namespace). The corresponding Python implementation is in pysparq.algorithms.state_preparation; the C++ experiment entry point is in Experiments/StatePreparation

namespace qram_simulator

QRAM sparse state simulator namespace.

Contains all classes, functions, and data structures related to quantum computing simulation

namespace state_prep

State preparation operators.

struct State_Prep_via_QRAM : public qram_simulator::BaseOperator

#include <state_preparation.h>

QRAM-based state preparation operator (composite operator)

Prepares the target distribution stored in the QRAM into the working register bit by bit: layer k splits off the rotation qubit, builds the parent/child addresses (addr_parent/addr_child) and parent/child data (data_parent/data_child); after the QRAM load, the rotation angle is computed with Div_Sqrt_Arccos_UInt_UInt / GetRotateAngle_Int_Int, the conditional rotation writes in the amplitude ratio, and then a dagger sequence unloads all ancillary quantities. Supports conditional control (ClassControllable)

Public Functions

inline ClassControllable State_Prep_via_QRAM(qram_qutrit::QRAMCircuit *qram_, std::string_view work_qubit_, size_t dsz, size_t rsz)

Constructor.

参数:

• qram_ -- QRAM circuit pointer holding the target distribution

• work_qubit_ -- Working register name

• dsz -- Data register bit width

• rsz -- Rational register bit width

template<typename Ty>
inline void impl(Ty &state) const

Forward preparation implementation.

Executes layer by layer (k = 0 … addr_size-1): split the rotation qubit → build parent/child addresses and data → QRAM load → compute the rotation angle → conditional rotation → unload; the last layer handles the leaf-node angle with GetRotateAngle_Int_Int

模板参数:

Ty -- State type (std::vector<System> or SparseState)

参数:

state -- System state

template<typename Ty>
inline void impl_dag(Ty &state) const

Inverse (dagger) preparation implementation.

Strict reverse order of impl: the layer order is reversed (k = addr_size-1 … 0), and within each layer the operations run in the opposite order via .dag(), used to restore a prepared state back to the initial state

模板参数:

Ty -- State type

参数:

state -- System state

Public Members

std::string work_qubit

Working register name (holds the preparation result; also serves as the address prefix)

size_t addr_size

Address bit width (= working register bit width, the number of binary-tree layers)

size_t data_size

Data register bit width (holds amplitude numerators/denominators)

size_t rational_size

Rational register bit width (holds intermediate division and arccosine results)

qram_qutrit::QRAMCircuit *qram

QRAM circuit pointer holding the target distribution.

namespace state_preparation_demo

State preparation demo driver (for experiments)

struct SparseStateDemo

#include <state_preparation.h>

Sparse state demo carrier.

Registers the parent/child addresses, parent/child data, temporary bit, and rational registers at construction, holds the initial |0⟩ state; provides clear, sort, print, and run entry points

Public Functions

inline SparseStateDemo(size_t asz, size_t dsz, size_t rsz, std::string qram_version_)

Constructor: registers all registers and prepares the |0⟩ initial state.

参数:

• asz -- Address bit width

• dsz -- Data bit width

• rsz -- Rational bit width

• qram_version_ -- QRAM circuit version

void clear_state()

Clear the sparse state (back to the single-branch |0⟩)

void sort_state()

Sort the sparse state by basis-state key.

std::string to_string() const

Print the sparse state to a string.

void run()

Execute the state preparation pipeline.

Public Members

size_t addr_size

Address bit width.

size_t data_size

Data bit width.

size_t rational_size

Rational bit width.

std::vector<System> system_states

Sparse state (vector of basis states)

qram_qutrit::QRAMCircuit *qram

QRAM circuit pointer (filled by set_qram after make_qram)

std::string qram_version

QRAM circuit version string.

class StatePreparation

#include <state_preparation.h>

Full state preparation demo driver.

Combines the classical side (random distribution generation, binary tree construction, QRAM construction) with the quantum side (preparation execution on the SparseStateDemo carrier), and supports noise injection and fidelity statistics

Public Functions

inline StatePreparation(size_t qn, size_t data_sz, size_t data_range_, std::string qram_version_)

Constructor.

参数:

• qn -- Number of working-register qubits

• data_sz -- Data bit width

• data_range_ -- Data value range upper bound

• qram_version_ -- QRAM circuit version

void random_distribution()

Generate a random target distribution.

void show_distribution()

Print the target distribution.

std::vector<double> get_real_dist()

Get the normalized real-valued target distribution.

void make_tree()

Build the amplitude binary tree from the target distribution.

void show_tree()

Print the amplitude binary tree.

void make_qram()

Construct the QRAM memory from the binary tree.

void set_qram()

Inject the constructed QRAM circuit into the carrier.

void set_noise(const noise_t &noise)

Set the QRAM noise model.

参数:

noise -- Noise parameters (error rates per operation type)

double get_fidelity() const

Compute the fidelity between the prepared state and the target distribution.

double get_fidelity_show() const

Compute and print the fidelity.

inline void print_state()

Print the current sparse state (first 10 lines, with details)

void run()

Execute the full preparation pipeline.

inline void clear_state()

Clear the carrier's sparse state.

Public Members

SparseStateDemo sparse_state

Quantum-side sparse state carrier.

size_t qubit_number

Number of working-register qubits (= number of binary-tree layers)

size_t data_size

Data bit width.

size_t data_range

Data value range upper bound.

std::vector<size_t> dist

Target distribution (classical side, indexed by address)

std::vector<size_t> tree

Amplitude binary tree (classical side)

qram_qutrit::QRAMCircuit *qram

QRAM circuit pointer.

std::string qram_version

QRAM circuit version string.

块编码总览（SparQ_Algorithm/include/block_encoding.h）

Common utilities and compile-time switches for block encoding experiments.

Provides formatted printing of complex/real vectors and a helper that zero-pads result vectors, and centrally defines the implementation optimization switches for block encoding (OPTIMIZE_HADAM_INT, OPTIMIZE_ROT, etc.). The concrete block encoding operators live in the BlockEncoding/ subdirectory (block_encoding_tridiagonal.h, block_encoding_via_QRAM.h, make_qram.h)

Defines

OPTIMIZE_HADAM_INT

OPTIMIZE_ROT

namespace qram_simulator

QRAM sparse state simulator namespace.

Contains all classes, functions, and data structures related to quantum computing simulation

Functions

inline void print_complex_vec(const std::vector<complex_t> &zvec, int precision)

Print a complex vector with the given precision.

参数:

• zvec -- Complex vector

• precision -- Number of decimal places

inline std::vector<complex_t> get_output(const std::vector<complex_t> &vec, int size)

Zero-pad the complex result vector to 4 times the main register space dimension.

参数:

• vec -- Original result vector

• size -- Dimension of the main register space

返回:

New zero-padded vector

inline std::vector<double> get_output(const std::vector<double> &vec, int size)

Zero-pad the real result vector to 4 times the main register space dimension (real-valued version of get_output)

参数:

• vec -- Original result vector

• size -- Dimension of the main register space

返回:

New zero-padded vector

哈密顿量模拟（SparQ_Algorithm/include/hamiltonian_simulation.h）

Algorithm building blocks for the CKS quantum walk and Hamiltonian simulation / linear-system solving.

Targets Childs-Kothari-Somma (CKS) type algorithms: based on the compact QRAM storage of sparse matrices (a quantized-element data table + a fixed-length-per-row sparse column-index table), it provides sparse-matrix oracles (SparseMatrixOracle1 for element queries, SparseMatrixOracle2 — the quantum binary search converting between column indices and sparse slots), the state-preparation operator T, the single-step quantum walk QuantumWalk, and the multi-step walk manager QuantumWalkNSteps. Powers of the walk operator W = T† · P0 · T · Swap correspond to Chebyshev polynomials of the matrix; the LCU container combines Σ_j c_j · W^(2j+1) with Chebyshev coefficients to approximate the target function. Together with the BlockEncoding module it belongs to the block-encoding / Hamiltonian-simulation algorithm family, and its QRAM access semantics are consistent with SparQ/include/qram.h.

namespace qram_simulator

QRAM sparse state simulator namespace.

Contains all classes, functions, and data structures related to quantum computing simulation

namespace CKS

Typedefs

using walk_angle_function_t = std::function<u22_t(uint64_t, size_t row, size_t col)>

Quantum-walk rotation-angle function type: generates a 2x2 unitary rotation matrix from the quantized matrix element value v and its row/column position (row, col)

using QuantumBinarySearchFast = QuantumBinarySearch_Fast

Functions

inline HOST_DEVICE void _get_coef_positive_only (size_t mat_data_size, size_t v, size_t row, size_t col, double *mat)

Generates the 2x2 rotation matrix of the quantum walk (case where all matrix elements are non-negative)

Let Amax = 2^mat_data_size - 1 and a = v / Amax; generates the rotation matrix [[sqrt(a), -sqrt(1-a)], [sqrt(1-a), sqrt(a)]], whose rotation angle theta satisfies cos(theta) = sqrt(a). It is used in the quantum walk to encode matrix elements through the amplitude ratio sqrt(a).

参数:

• mat_data_size -- Quantization bit width of the matrix element

• v -- Quantized matrix element value

• row -- Row index of the element (unused in this overload)

• col -- Column index of the element (unused in this overload)

• mat -- Output buffer; the 2x2 complex matrix is written in the real/imaginary interleaved layout of u22_t

inline HOST_DEVICE u22_t _get_coef_positive_only (size_t mat_data_size, size_t v, size_t row, size_t col)

Generates the 2x2 rotation matrix of the quantum walk (positive-only elements case), returned as u22_t.

The parameters have the same meaning as in the double* buffer overload; directly returns the rotation matrix.

inline HOST_DEVICE void _get_coef_common (size_t mat_data_size, uint64_t v, size_t row, size_t col, double *mat)

Generates the 2x2 rotation matrix of the quantum walk (general case allowing negative elements)

Let Amax = 2^(mat_data_size-1) - 1. For non-negative elements it coincides with the positive-only case, generating [[sqrt(a), -sqrt(1-a)], [sqrt(1-a), sqrt(a)]] (a = v/Amax); for negative elements the diagonal entries become ±i·sqrt(|a|) and the anti-diagonal entries sqrt(1-|a|), with the sign of the diagonal entries chosen by comparing row and col (+i when row > col, -i when row < col), providing a consistent phase convention for the conjugate-symmetric elements of a Hermitian matrix.

参数:

• mat_data_size -- Quantization bit width of the matrix element

• v -- Quantized matrix element value (interpreted in two's complement)

• row -- Row index of the element (used to fix the sign convention for negative elements)

• col -- Column index of the element (used to fix the sign convention for negative elements)

• mat -- Output buffer; the 2x2 complex matrix is written in the real/imaginary interleaved layout of u22_t

inline HOST_DEVICE u22_t _get_coef_common (size_t mat_data_size, uint64_t v, size_t row, size_t col)

Generates the 2x2 rotation matrix of the quantum walk (general case allowing negative elements), returned as u22_t.

The parameters have the same meaning as in the double* buffer overload; directly returns the rotation matrix.

inline HOST_DEVICE void u22_dagger (double *mat)

Computes the conjugate transpose (dagger) of a 2x2 matrix in place.

参数:

mat -- 2x2 complex matrix (real/imaginary interleaved layout of u22_t, modified in place)

inline HOST_DEVICE void _get_coef_positive_only_inv (size_t mat_data_size, uint64_t v, size_t row, size_t col, double *mat)

Generates the inverse of the quantum-walk 2x2 rotation matrix (positive-only elements case)

First generates the forward rotation matrix, then takes its conjugate transpose (dagger). The parameters have the same meaning as in the forward version.

inline HOST_DEVICE void _get_coef_common_inv (size_t mat_data_size, uint64_t v, size_t row, size_t col, double *mat)

Generates the inverse of the quantum-walk 2x2 rotation matrix (general case allowing negative elements)

First generates the forward rotation matrix, then takes its conjugate transpose (dagger). The parameters have the same meaning as in the forward version.

inline HOST_DEVICE u22_t _get_coef_positive_only_inv (size_t mat_data_size, uint64_t v, size_t row, size_t col)

Generates the inverse of the quantum-walk 2x2 rotation matrix (positive-only elements case), returned as u22_t.

The parameters have the same meaning as in the double* buffer overload; directly returns the inverse rotation matrix.

inline HOST_DEVICE u22_t _get_coef_common_inv (size_t mat_data_size, uint64_t v, size_t row, size_t col)

Generates the inverse of the quantum-walk 2x2 rotation matrix (general case allowing negative elements), returned as u22_t.

The parameters have the same meaning as in the double* buffer overload; directly returns the inverse rotation matrix.

inline u22_t make_qw_rotation_matrix(const SparseMatrix &mat, uint64_t v, size_t row, size_t col)

Generates the quantum-walk rotation matrix according to the sparse matrix's sign convention.

If the matrix contains only non-negative elements, the _get_coef_positive_only path is taken; otherwise the _get_coef_common path, which allows negative elements, is taken.

参数:

• mat -- Sparse matrix (its positive_only and data_size metadata are used)

• v -- Quantized matrix element value

• row -- Row index of the element

• col -- Column index of the element

返回:

2x2 unitary rotation matrix (forward)

inline u22_t make_qw_rotation_matrix_inv(const SparseMatrix &mat, uint64_t v, size_t row, size_t col)

Generates the inverse (dagger) of the quantum-walk rotation matrix according to the sparse matrix's sign convention.

参数:

• mat -- Sparse matrix (its positive_only and data_size metadata are used)

• v -- Quantized matrix element value

• row -- Row index of the element

• col -- Column index of the element

返回:

Inverse of the 2x2 unitary rotation matrix

inline walk_angle_function_t make_func(const SparseMatrix &mat)

Constructs a lazily evaluated walk rotation-angle function (forward)

参数:

mat -- Sparse matrix (captures its positive_only and data_size)

返回:

A function object taking (v, row, col) as input and returning the 2x2 rotation matrix

inline walk_angle_function_t make_func_inv(const SparseMatrix &mat)

Constructs a lazily evaluated walk rotation-angle function (inverse / dagger)

参数:

mat -- Sparse matrix (captures its positive_only and data_size)

返回:

A function object taking (v, row, col) as input and returning the 2x2 inverse rotation matrix

std::vector<complex_t> my_linear_solver_reference(const SparseMatrix &mat)

Classical reference implementation of linear-system solving (all-ones right-hand side)

Calls the version with a right-hand side, using the all-ones vector as the right-hand side.

参数:

mat -- Sparse matrix

返回:

The normalized solution vector (complex)

std::vector<complex_t> my_linear_solver_reference(const SparseMatrix &mat, const DenseVector<double> &vec)

Classical reference implementation of linear-system solving (with a given right-hand side)

Solves A x = vec with the Eigen sparse linear solver and normalizes by the 2-norm, serving as the classical reference for the quantum algorithm's result.

参数:

• mat -- Sparse matrix

• vec -- Right-hand-side vector

返回:

The normalized solution vector (complex)

struct ChebyshevPolynomialCoefficient

#include <hamiltonian_simulation.h>

Chebyshev polynomial expansion coefficients for the CKS algorithm.

Provides the coefficients c_j and their signs for the LCU combination Σ_j c_j · W^(2j+1): expansion order b = kappa^2 · log(kappa/eps), truncation point j0 = sqrt(b·log(4b/eps)). For large b, c_j is computed with the erfc asymptotic formula; for small b, the binomial-distribution tail probability is summed exactly; odd-j terms take a negative sign.

Public Functions

inline ChebyshevPolynomialCoefficient(size_t b_)

Constructor.

参数:

b_ -- Chebyshev expansion-order parameter

double C(size_t Big, size_t Small)

Computes the binomial coefficient C(Big, Small) / 4^b, scaled by 4^b.

备注

During the recursion, as soon as the intermediate value exceeds 2^b it is divided by 2^b to avoid overflow.

参数:

• Big -- Upper parameter of the binomial coefficient

• Small -- Lower parameter of the binomial coefficient

返回:

C(Big, Small) / 4^b

double coef(size_t j)

Computes the j-th coefficient c_j of the Chebyshev expansion.

For b > 100, uses the erfc asymptotic formula c_j = 2·erfc((j+0.5)/sqrt(b)); otherwise sums the binomial-distribution tail exactly: c_j = 4 · Σ_{i=j+1}^{b} C(2b, b+i).

参数:

j -- Term index (0 to b-1)

返回:

Coefficient c_j

bool sign(size_t j)

Sign of the j-th term.

参数:

j -- Term index

返回:

Returns true for odd j (negative sign), false for even j (positive sign)

size_t step(size_t j)

Number of quantum-walk steps for the j-th term.

参数:

j -- Term index

返回:

Number of walk steps 2j + 1

Public Members

size_t b

Expansion-order parameter b = kappa^2 · log(kappa/eps)

struct CondRot_General_Bool_QW : public qram_simulator::BaseOperator

#include <hamiltonian_simulation.h>

General conditional-rotation operator for the quantum walk.

Generates a 2x2 unitary matrix from the quantized matrix element (v, j, k) via the walk rotation-angle function and applies it to the Boolean output register: state branches are first sorted and grouped by the output register, then dispatched to the matching implementation by matrix shape (diagonal / anti-diagonal / general); dag uses the inverse rotation-angle function. Kept for future specialized paths; the current main path replaces it with the two-step combination GetQWRotateAngle + CondRot_Fixed_Bool.

Public Functions

inline CondRot_General_Bool_QW(std::string_view j_, std::string_view k_, std::string_view reg_in, std::string_view reg_out, const SparseMatrix *mat)

Constructor.

参数:

• j_ -- Name of the row-index register

• k_ -- Name of the column-index (sparse slot) register

• reg_in -- Name of the input (matrix element) register

• reg_out -- Name of the output Boolean register

• mat -- Pointer to the sparse matrix

void operate(size_t l, size_t r, std::vector<System> &state, walk_angle_function_t func) const

Applies the rotation to the branches within the state interval [l, r)

参数:

• l -- Left boundary of the interval

• r -- Right boundary of the interval

• state -- System state vector

• func -- Walk rotation-angle function (generates the 2x2 matrix from the matrix element and its row/column position)

void _operate_diagonal(size_t l, size_t r, std::vector<System> &state, const u22_t &mat) const

Diagonal-matrix operation implementation (creates no new branches; scales amplitudes in place)

参数:

• l -- Left boundary of the interval

• r -- Right boundary of the interval

• state -- System state vector

• mat -- 2x2 diagonal matrix

void _operate_off_diagonal(size_t l, size_t r, std::vector<System> &state, const u22_t &mat) const

Anti-diagonal matrix operation implementation (creates no new branches; swaps and flips the Boolean value in place)

参数:

• l -- Left boundary of the interval

• r -- Right boundary of the interval

• state -- System state vector

• mat -- 2x2 anti-diagonal matrix

void _operate_general(size_t l, size_t r, std::vector<System> &state, const u22_t &mat) const

General 2x2 matrix operation implementation (may create new branches)

参数:

• l -- Left boundary of the interval

• r -- Right boundary of the interval

• state -- System state vector

• mat -- General 2x2 unitary matrix

virtual void operator()(std::vector<System> &state) const

Applies the general conditional rotation (forward)

参数:

state -- System state vector

virtual void dag(std::vector<System> &state) const

Applies the dagger of the general conditional rotation.

参数:

state -- System state vector

inline virtual void dag(std::vector<System> &state) const

Apply the conjugate transpose (dagger) operation.

参数:

state -- System state vector

抛出:

Throws -- a not-implemented exception by default

inline virtual void dag(SparseState &state) const

Apply dagger to a SparseState.

参数:

state -- Sparse state

Public Members

std::string j

Name of the row-index register.

std::string k

Name of the column-index (sparse slot) register.

std::string in_name

Name of the input (matrix element) register.

std::string out_name

Name of the output Boolean register.

size_t j_id

Register ID of the row index.

size_t k_id

Register ID of the column index (sparse slot)

size_t in_id

Register ID of the input (matrix element)

size_t out_id

Register ID of the output Boolean register.

const SparseMatrix *mat

Pointer to the sparse matrix (provides quantization and sign-convention metadata)

Public Static Functions

static bool _is_diagonal(const u22_t &data)

Checks whether the matrix is diagonal.

参数:

data -- 2x2 matrix

返回:

Whether the matrix is diagonal

static bool _is_off_diagonal(const u22_t &data)

Checks whether the matrix is anti-diagonal.

参数:

data -- 2x2 matrix

返回:

Whether the matrix is anti-diagonal

struct GetDataAddr : public qram_simulator::SelfAdjointOperator

#include <hamiltonian_simulation.h>

Matrix-element storage address computation operator (self-adjoint)

Performs data_offset ^= offset + row_sz * row + col_sparse, i.e. the address in the QRAM data table of the element (the col_sparse-th sparse slot of row row); two invocations cancel each other.

Public Functions

inline GetDataAddr(std::string_view reg_offset, std::string_view reg_row, std::string_view reg_col_sparse, size_t row_sz_, std::string_view reg_data_offset)

Constructor (register-name version)

参数:

• reg_offset -- Name of the data-table start offset register

• reg_row -- Name of the row-index register

• reg_col_sparse -- Name of the sparse-slot register

• row_sz_ -- Number of slots per row

• reg_data_offset -- Name of the element-address output register

inline GetDataAddr(size_t reg_offset, size_t reg_row, size_t reg_col_sparse, size_t row_sz_, size_t reg_data_offset)

Constructor (register-ID version)

参数:

• reg_offset -- Register ID of the data-table start offset

• reg_row -- Register ID of the row index

• reg_col_sparse -- Register ID of the sparse slot

• row_sz_ -- Number of slots per row

• reg_data_offset -- Register ID of the element-address output

virtual void operator()(std::vector<System> &state) const

Computes the storage address of a matrix element.

参数:

state -- System state vector

inline virtual void dag(std::vector<System> &state) const override

Apply the dagger operation (the dagger of a self-adjoint operator equals itself)

参数:

state -- System state vector

inline virtual void dag(SparseState &state) const override

Apply dagger to a SparseState.

参数:

state -- Sparse state

inline virtual void dag(std::vector<System> &state) const

Apply the conjugate transpose (dagger) operation.

参数:

state -- System state vector

抛出:

Throws -- a not-implemented exception by default

inline virtual void dag(SparseState &state) const

Apply dagger to a SparseState.

参数:

state -- Sparse state

Public Members

size_t offset_id

Register ID of the data-table start offset.

size_t row_id

Register ID of the row index.

size_t row_sz

Number of slots per row.

size_t col_sparse_id

Register ID of the sparse slot.

size_t row_data_id

Register ID of the element-address output (written by XOR)

struct GetQWRotateAngle_Int_Int_Int : public qram_simulator::SelfAdjointOperator

#include <hamiltonian_simulation.h>

Quantum-walk rotation-angle computation operator (self-adjoint)

Computes the ratio ratio = |a_jk| / Amax from the quantized matrix element v (for positive-only elements Amax = 2^data_size - 1; in the general case Amax = 2^(data_size-1) - 1, with v interpreted in two's complement and taken in absolute value), then quantizes the rotation angle theta = arccos(sqrt(ratio)) / (2*pi) into a Rational fixed-point value and XORs it into the output register. Usually combined with CondRot_Fixed_Bool to form a two-step equivalent implementation of the general conditional rotation CondRot_General_Bool_QW: first compute the angle, then apply a fixed-angle rotation, and finally uncompute the angle. Supports conditional control (ClassControllable).

Public Functions

inline ClassControllable GetQWRotateAngle_Int_Int_Int(std::string_view data_, std::string_view row_, std::string_view col_, std::string_view out_, const SparseMatrix *mat_)

Constructor (register-name version)

参数:

• data_ -- Name of the quantized matrix element register

• row_ -- Name of the row-index register

• col_ -- Name of the column-index (sparse slot) register

• out_ -- Name of the rotation-angle output register

• mat_ -- Pointer to the sparse matrix

inline GetQWRotateAngle_Int_Int_Int(size_t data_, size_t row_, size_t col_, size_t out_, const SparseMatrix *mat_)

Constructor (register-ID version)

参数:

• data_ -- Register ID of the quantized matrix element

• row_ -- Register ID of the row index

• col_ -- Register ID of the column index (sparse slot)

• out_ -- Register ID of the rotation-angle output

• mat_ -- Pointer to the sparse matrix

virtual void operator()(std::vector<System> &state) const

Computes the walk rotation angle and writes it to the output register.

备注

The operator is self-adjoint: two consecutive invocations cancel each other.

参数:

state -- System state vector

inline virtual void dag(std::vector<System> &state) const override

Apply the dagger operation (the dagger of a self-adjoint operator equals itself)

参数:

state -- System state vector

inline virtual void dag(SparseState &state) const override

Apply dagger to a SparseState.

参数:

state -- Sparse state

inline virtual void dag(std::vector<System> &state) const

Apply the conjugate transpose (dagger) operation.

参数:

state -- System state vector

抛出:

Throws -- a not-implemented exception by default

inline virtual void dag(SparseState &state) const

Apply dagger to a SparseState.

参数:

state -- Sparse state

Public Members

size_t data_id

Register ID of the quantized matrix element.

size_t row_id

Register ID of the row index.

size_t col_id

Register ID of the column index (sparse slot)

size_t out_id

Register ID of the rotation-angle output (Rational fixed-point)

const SparseMatrix *mat

Pointer to the sparse matrix (provides quantization and sign-convention metadata)

struct GetRowAddr : public qram_simulator::SelfAdjointOperator

#include <hamiltonian_simulation.h>

Row-start address computation operator (self-adjoint)

Performs row_offset ^= offset + row_sz * row, i.e. the start address of the segment corresponding to row row in the QRAM row-wise fixed-length storage (each row occupies a fixed row_sz slots); two invocations cancel each other.

Public Functions

inline GetRowAddr(std::string_view reg_offset, std::string_view reg_row, size_t row_sz_, std::string_view reg_row_offset)

Constructor (register-name version)

参数:

• reg_offset -- Name of the segment start offset register

• reg_row -- Name of the row-index register

• row_sz_ -- Number of slots per row

• reg_row_offset -- Name of the row-start address output register

inline GetRowAddr(int reg_offset, int reg_row, size_t row_sz_, int reg_row_offset)

Constructor (register-ID version)

参数:

• reg_offset -- Register ID of the segment start offset

• reg_row -- Register ID of the row index

• row_sz_ -- Number of slots per row

• reg_row_offset -- Register ID of the row-start address output

virtual void operator()(std::vector<System> &state) const

Computes the row-start address.

参数:

state -- System state vector

inline virtual void dag(std::vector<System> &state) const override

Apply the dagger operation (the dagger of a self-adjoint operator equals itself)

参数:

state -- System state vector

inline virtual void dag(SparseState &state) const override

Apply dagger to a SparseState.

参数:

state -- Sparse state

inline virtual void dag(std::vector<System> &state) const

Apply the conjugate transpose (dagger) operation.

参数:

state -- System state vector

抛出:

Throws -- a not-implemented exception by default

inline virtual void dag(SparseState &state) const

Apply dagger to a SparseState.

参数:

state -- Sparse state

Public Members

size_t offset_id

Register ID of the segment start offset.

size_t row_id

Register ID of the row index.

size_t row_sz

Number of slots per row.

size_t row_offset_id

Register ID of the row-start address output (written by XOR)

struct LCU_Container

#include <hamiltonian_simulation.h>

LCU container for CKS linear-system solving (general version)

Approximates the target operator corresponding to the matrix's Chebyshev series by the linear combination Σ_j c_j · W^(2j+1) (j = 0..j0): each term's walk state, with its corresponding number of steps, is prepared independently by QuantumWalkNSteps, then accumulated into the current state by coefficient and sign, and merged with deduplication. Expansion order b = kappa^2 · log(kappa/eps), truncation point j0 = sqrt(b · log(4b/eps)).

Public Functions

inline LCU_Container(const SparseMatrix &mat, double kappa_, double eps_)

Constructor.

Computes b and j0 and initializes the walk register environment.

参数:

• mat -- Sparse matrix

• kappa_ -- Condition number

• eps_ -- Target precision

inline auto GetInputVecReg()

Gets the name of the register holding the input vector.

返回:

The walk manager's input register name

std::vector<System> state_of_j(size_t j)

Prepares the walk state corresponding to the j-th term.

参数:

j -- Term index

返回:

The system state after 2j+1 walk steps

void add(std::vector<System> new_state, double coef, bool sign)

Accumulates a new state, scaled by its coefficient, into the LCU combined state.

参数:

• new_state -- The state to accumulate

• coef -- Chebyshev coefficient

• sign -- Whether to take the negative sign (odd-j terms)

void iterate()

Runs the full LCU iteration.

Iterates j = 0..j0: prepares the state after 2j+1 walk steps, accumulates it by coefficient and sign, and sort-merges each round to keep the state size under control.

Public Members

std::vector<System> current_state

The accumulated LCU combined state.

double kappa

Condition number kappa.

double eps

Target precision eps.

size_t b

Chebyshev expansion-order parameter b.

size_t j0

LCU summation truncation point.

QuantumWalkNSteps<std::vector<System>> quantum_walk_obj

Multi-step quantum walk manager.

ChebyshevPolynomialCoefficient chebyshev_obj

Chebyshev coefficient calculator.

template<typename StateTy = SparseState>
struct LCU_Container_NoiseFree

#include <hamiltonian_simulation.h>

LCU container for CKS linear-system solving (noise-free optimized version)

Iterates in place on a single walk state instead of copying the state for each LCU term, hence it only applies to noise-free simulation. ExternalInput injects the input and completes the first walk step; Step advances the LCU iteration term by term (j from 0 to j0, with the coefficient sum a as the LCU normalization factor); PartialTrace post-selects on the walk auxiliary registers and yields the success probability.

Public Functions

inline LCU_Container_NoiseFree(const SparseMatrix &mat, double kappa, double eps)

Constructor.

Computes b and j0, initializes the walk register environment, and creates the walk state.

参数:

• mat -- Sparse matrix

• kappa -- Condition number

• eps -- Target precision

inline auto GetInputVecReg() const

Gets the name of the register holding the input vector.

返回:

The walk manager's input register name

inline size_t get_addr_size() const

Gets the QRAM address width.

返回:

The walk manager's addr_size

template<typename Ty>
inline void ExternalInput()

Injects an external input (default-construction version)

Applies the input operator Ty on the input register, clears zero amplitudes, then runs the first walk step.

template<typename Ty, typename ...Args>
inline void ExternalInput(Args&&... args)

Injects an external input (version with extra arguments)

Applies the input operator Ty on the input register, clears zero amplitudes, then runs the first walk step.

参数:

args -- Extra arguments forwarded to the constructor of the input operator Ty

inline void ExternalInput_V2(const BaseOperator &op)

Injects an external input (operator-instance version)

Applies the input operator, clears zero amplitudes, then runs the first walk step.

参数:

op -- The input operator applied to the input register

inline bool Step()

Advances the LCU by one term.

When j is non-zero, first advances the walk state by two steps (step count 2j+1), then accumulates the coefficient into a and adds the current walk state, scaled by the coefficient and sign, into the combined state.

返回:

Returns true while the truncation point has not been reached, false when the iteration is over

inline void Add(const StateTy &new_state, double coef, bool sign)

Accumulates the state, scaled by its coefficient, into the LCU combined state.

参数:

• new_state -- The state to accumulate

• coef -- Chebyshev coefficient

• sign -- Whether to take the negative sign (odd-j terms)

inline double _impl_partial_trace(StateTy &state) const

Computes the post-selection success probability (internal implementation)

Applies the partial-trace selection to branches where the walk auxiliary registers (b1, k, b2, j_comp, k_comp, and the offset registers) are all zero and j lies in [0, n_row), and combines it with the LCU normalization factor a to obtain the success probability (PartialTraceSelect returns 1/sqrt(p)).

参数:

state -- System state vector (modified by the partial-trace selection)

返回:

The LCU post-selection success probability

inline double PartialTrace()

Computes the post-selection success probability (destructive version)

备注

Modifies current_state.

返回:

The success probability

inline std::tuple<StateTy, double> PartialTrace_Nondestructive() const

Computes the post-selection success probability (non-destructive version)

返回:

(A copy of the post-selected state, the success probability)

Public Members

StateTy current_state

The accumulated LCU combined state.

StateTy step_state

The current walk state (advanced in place across LCU terms)

QuantumWalkNSteps<StateTy> quantum_walk_obj

Multi-step quantum walk manager.

double kappa

Condition number kappa.

double eps

Target precision eps.

size_t b

Chebyshev expansion-order parameter b.

size_t j0

LCU summation truncation point.

size_t j = 0

double a = 0

The accumulated sum of Chebyshev coefficients (LCU normalization factor)

ChebyshevPolynomialCoefficient chebyshev_obj

Chebyshev coefficient calculator.

struct LCU_Container_Theory

#include <hamiltonian_simulation.h>

Classical theory-verification container for CKS linear-system solving.

Directly computes, with the dense matrix and the Chebyshev three-term recurrence T_{n+1} = 2·A'·T_n - T_{n-1}, the vector corresponding to each power of the walk (A' is the dense matrix normalized by the quantization scale and nnz_col), to be compared against the quantum implementation's LCU combination, verifying the algorithm's correctness at the classical level.

Public Functions

inline LCU_Container_Theory(const SparseMatrix &mat_, double kappa_, double eps_)

Constructor.

Builds the normalized dense matrix and initializes the first two terms of the Chebyshev recurrence (vec0, vec1) with a uniformly normalized vector.

参数:

• mat_ -- Sparse matrix

• kappa_ -- Condition number

• eps_ -- Target precision

inline void Add(const DenseVector<complex_t> &new_state, double coef, bool sign)

Accumulates the vector, scaled by its coefficient, into the LCU combined vector.

参数:

• new_state -- The vector to accumulate

• coef -- Chebyshev coefficient

• sign -- Whether to take the negative sign (odd-j terms)

DenseVector<complex_t> MakeStepState()

Builds the walk-power vector corresponding to the current LCU term.

For j = 0, returns the initial vec1; otherwise advances two steps via the three-term recurrence, matching the quantum walk advancing two steps per Step() call.

返回:

The T(2j+1) vector obtained from the Chebyshev recurrence

bool Step()

Advances the LCU by one term.

返回:

Returns true while the truncation point has not been reached, false when the iteration is over

std::pair<DenseVector<complex_t>, double> GetOutput() const

Gets the final solution vector and the success probability.

返回:

(Normalized solution vector, success probability = ||current||^2 / a^2)

Public Members

SparseMatrix mat

Sparse matrix.

DenseMatrix<complex_t> densemat

The normalized dense matrix.

double kappa

Condition number kappa.

double eps

Target precision eps.

size_t b

Chebyshev expansion-order parameter b.

size_t j0

LCU summation truncation point.

size_t j = 0

double a = 0

The accumulated sum of Chebyshev coefficients (LCU normalization factor)

ChebyshevPolynomialCoefficient chebyshev_obj

Chebyshev coefficient calculator.

DenseVector<complex_t> current_state

The accumulated LCU combined vector.

DenseVector<complex_t> step_state

The vector corresponding to the current walk power.

DenseVector<complex_t> vec0

DenseVector<complex_t> vec1

struct QuantumBinarySearch : public qram_simulator::SelfAdjointOperator

#include <hamiltonian_simulation.h>

QRAM-based quantum binary search operator (self-adjoint)

Searches the sorted QRAM memory region [offset, offset + total_length) for the address whose value equals the target register's value: in each round, flag controls whether subsequent rounds remain active; the interval's midpoint address is taken, its value loaded via QRAM and compared with the target — on a hit, the midpoint address is XORed into the result register and flag is updated to end the active search; otherwise the interval shrinks according to the comparison. Each round's temporary registers are saved with Push and uncomputed by Pop in reverse order, keeping the whole operation reversible and self-adjoint (impl_dag simply reuses impl).

Public Functions

QuantumBinarySearch(qram_qutrit::QRAMCircuit *qram, std::string_view address_offset_register, size_t total_length_, std::string_view target_register, std::string_view result_register)

Constructor (register-name version)

参数:

• qram -- Pointer to the QRAM circuit

• address_offset_register -- Name of the search start offset register

• total_length_ -- Length of the search interval

• target_register -- Name of the target value register

• result_register -- Name of the result register

QuantumBinarySearch(qram_qutrit::QRAMCircuit *qram, size_t address_offset_register, size_t total_length_, size_t target_register, size_t result_register)

Constructor (register-ID version)

参数:

• qram -- Pointer to the QRAM circuit

• address_offset_register -- Register ID of the search start offset

• total_length_ -- Length of the search interval

• target_register -- Register ID of the target value

• result_register -- Register ID of the result

template<typename Ty>
inline void impl(Ty &state) const

Forward implementation of the binary search (also serves as the dagger implementation)

After running max_step search rounds forward, all temporary registers are uncomputed in reverse order, so the whole is a self-adjoint operation.

参数:

state -- System state vector

template<typename Ty>
inline void impl_dag(Ty &state) const

Dagger implementation of the binary search.

The operator is self-adjoint and directly reuses the forward implementation.

参数:

state -- System state vector

inline virtual void dag(std::vector<System> &state) const override

Apply the dagger operation (the dagger of a self-adjoint operator equals itself)

参数:

state -- System state vector

inline virtual void dag(SparseState &state) const override

Apply dagger to a SparseState.

参数:

state -- Sparse state

inline virtual void dag(std::vector<System> &state) const

Apply the conjugate transpose (dagger) operation.

参数:

state -- System state vector

抛出:

Throws -- a not-implemented exception by default

inline virtual void dag(SparseState &state) const

Apply dagger to a SparseState.

参数:

state -- Sparse state

Public Members

qram_qutrit::QRAMCircuit *qram

Pointer to the QRAM circuit (provides the sorted memory being searched)

size_t total_length

Length of the search interval.

size_t max_step

Number of binary-search rounds (log2(total_length) + 1)

size_t address_offset_id

Register ID of the search start offset (its value is the interval's left-end address)

size_t target_id

Register ID of the target value.

size_t result_id

Register ID of the result (the hit address is written by XOR)

struct QuantumBinarySearch_Fast : public qram_simulator::SelfAdjointOperator

#include <hamiltonian_simulation.h>

Fast version of the quantum binary search.

Directly performs a classical binary search on each state branch at the simulator level (avoiding the per-round QRAM load and uncomputation overhead) and XORs the hit address into the result register; the search semantics match QuantumBinarySearch. Used by SparseMatrixOracle2 for sparse-slot localization.

Public Functions

QuantumBinarySearch_Fast(qram_qutrit::QRAMCircuit *qram, std::string_view address_offset_register, size_t total_length_, std::string_view target_register, std::string_view result_register)

Constructor (register-name version)

参数:

• qram -- Pointer to the QRAM circuit

• address_offset_register -- Name of the search start offset register

• total_length_ -- Length of the search interval

• target_register -- Name of the target value register

• result_register -- Name of the result register

QuantumBinarySearch_Fast(qram_qutrit::QRAMCircuit *qram, size_t address_offset_register, size_t total_length_, size_t target_register, size_t result_register)

Constructor (register-ID version)

参数:

• qram -- Pointer to the QRAM circuit

• address_offset_register -- Register ID of the search start offset

• total_length_ -- Length of the search interval

• target_register -- Register ID of the target value

• result_register -- Register ID of the result

size_t binary_search(size_t offset, size_t target) const

Performs a classical binary search on a single state branch.

参数:

• offset -- Start address of the search interval

• target -- Target value

返回:

The hit address; returns 0 on a miss

virtual void operator()(std::vector<System> &state) const

Applies the fast binary search (classical computation branch by branch)

参数:

state -- System state vector

inline virtual void dag(std::vector<System> &state) const override

Apply the dagger operation (the dagger of a self-adjoint operator equals itself)

参数:

state -- System state vector

inline virtual void dag(SparseState &state) const override

Apply dagger to a SparseState.

参数:

state -- Sparse state

inline virtual void dag(std::vector<System> &state) const

Apply the conjugate transpose (dagger) operation.

参数:

state -- System state vector

抛出:

Throws -- a not-implemented exception by default

inline virtual void dag(SparseState &state) const

Apply dagger to a SparseState.

参数:

state -- Sparse state

Public Members

qram_qutrit::QRAMCircuit *qram

Pointer to the QRAM circuit (provides the sorted memory being searched)

size_t total_length

Length of the search interval.

size_t max_step

Number of binary-search rounds (log2(total_length) + 1)

size_t address_offset_id

Register ID of the search start offset (its value is the interval's left-end address)

size_t target_id

Register ID of the target value.

size_t result_id

Register ID of the result (the hit address is written by XOR)

struct QuantumWalk : public qram_simulator::BaseOperator

#include <hamiltonian_simulation.h>

Single-step quantum walk operator (CKS walk)

Circuit implementation of the walk operator W = T† · P0 · T · Swap: P0 is the phase flip on the all-zero state of the walk auxiliary registers (b1, k, b2, k_comp), and Swap exchanges the row/column roles of (j, b1, j_comp) and (k, b2, k_comp). The walk's spectrum is determined by the matrix's eigenvalues; the matrix elements of its powers W^(2j+1) correspond to Chebyshev polynomials of the matrix, which the LCU container combines to approximate the target function.

Public Functions

inline QuantumWalk(qram_qutrit::QRAMCircuit *qram_, std::string_view j_, std::string_view b1_, std::string_view k_, std::string_view b2_, std::string_view j_comp_, std::string_view k_comp_, std::string_view data_offset_, std::string_view sparse_offset_, const SparseMatrix &mat_)

Constructor.

参数:

• qram_ -- Pointer to the QRAM circuit

• j_ -- Name of the row-index register

• b1_ -- Name of the Boolean flag b1 register

• k_ -- Name of the column-index register

• b2_ -- Name of the Boolean flag b2 register

• j_comp_ -- Name of the j-side auxiliary register

• k_comp_ -- Name of the k-side auxiliary register

• data_offset_ -- Name of the data-table offset register

• sparse_offset_ -- Name of the sparse-table offset register

• mat_ -- Sparse matrix

template<typename Ty>
inline void impl(Ty &system_states) const

Applies the single-step quantum walk.

Executes in order: T† -> phase flip P0 -> T -> row/column swap (Swap).

参数:

system_states -- System state vector

template<typename Ty>
inline void impl_dag(Ty &system_states) const

Dagger implementation of the single-step quantum walk.

备注

Not implemented; throws an exception when called.

参数:

system_states -- System state vector

Public Members

std::string j

Names of the walk-related registers (j/b1/k/b2/j_comp/k_comp plus data and sparse offsets)

std::string b1

std::string k

std::string b2

std::string j_comp

std::string k_comp

std::string data_offset

std::string sparse_offset

qram_qutrit::QRAMCircuit *qram

Pointer to the QRAM circuit.

SparseMatrix mat

Copy of the sparse matrix.

template<typename Ty = SparseState>
class QuantumWalkNSteps

#include <hamiltonian_simulation.h>

Multi-step quantum walk manager.

Creates the register environment needed by the walk and prepares the n-step walk state: at initialization it creates (or attaches to) the QRAM circuit according to the sparse-matrix layout and registers the walk registers (j/b1/k/b2/j_comp/k_comp plus the data and sparse offset registers); MakeNStepState first applies the uniform Hadamard input and the first walk step (T · Swap · T†), then iterates single walk steps (phase flip + T + Swap + T†), preparing the quantum state that corresponds to the walk's power, for the LCU container to combine with Chebyshev coefficients.

Public Functions

inline QuantumWalkNSteps(const SparseMatrix &mat_, qram_qutrit::QRAMCircuit *qram_)

Constructor (attaching to an external QRAM circuit)

参数:

• mat_ -- Sparse matrix

• qram_ -- Pointer to the external QRAM circuit (lifetime managed by the caller)

inline QuantumWalkNSteps(const SparseMatrix &mat_)

Constructor (internally creates the QRAM circuit)

备注

The QRAM circuit is owned by this object and released on destruction.

参数:

mat_ -- Sparse matrix (QRAM memory is built from its compact layout)

inline ~QuantumWalkNSteps()

Destructor.

备注

The QRAM circuit is deleted by this object; when attaching an external circuit, ownership conventions must be ensured by the caller.

inline std::string GetVecInputReg() const

Gets the name of the register holding the input vector.

返回:

The name of the row-index register j

inline size_t get_init_size() const

Gets the initialization width of the input register.

返回:

log2(n_row), i.e. the number of bits needed to represent the row index

inline void InitEnvironment()

Registers all registers needed by the walk.

Registers the data / sparse offset registers and the j/b1/k/b2/j_comp/k_comp walk registers in System.

inline Ty CreateSys()

Creates the initial system state.

返回:

A system state with the sparse offset register initialized (set to the matrix's sparse-table offset)

inline Ty MakeNStepState(size_t n_steps)

Prepares the system state of an n-step quantum walk.

Workflow: create the state -> apply the uniform Hadamard input on the j register -> first walk step (T · Swap · T†) -> iterate n_steps-1 single walk steps.

参数:

n_steps -- Number of walk steps (0 means only the uniform Hadamard superposition is applied)

返回:

The system state after n walk steps

inline void FirstStep(Ty &system_states)

First step of the walk (without the phase flip)

Executes T -> row/column swap (Swap) -> T† (without the phase flip).

参数:

system_states -- System state vector

inline void StepImplOneStep(Ty &system_states)

Implementation of a single walk step.

Executes phase flip P0 -> T -> row/column swap (Swap) -> T†, i.e. a single power of the walk operator.

参数:

system_states -- System state vector

inline void Step(Ty &system_states)

Advances the walk by two steps.

Executes two consecutive single walk steps, matching the LCU expansion where the number of steps increases by 2 each time (2j+1 -> 2(j+1)+1).

参数:

system_states -- System state vector

Public Members

std::string data_offset = "data_offset"

Name of the data-table offset register.

std::string sparse_offset = "sparse_offset"

Name of the sparse-table offset register.

std::string j = "row_id"

Name of the row-index (input vector) register.

std::string b1 = "reg_b1"

Name of the Boolean flag b1 register.

std::string k = "col_id"

Name of the column-index register.

std::string b2 = "reg_b2"

Name of the Boolean flag b2 register.

std::string j_comp = "j_comp"

Name of the j-side auxiliary register.

std::string k_comp = "k_comp"

Name of the k-side auxiliary register.

SparseMatrix mat

Copy of the sparse matrix.

size_t addr_size

QRAM address width, element quantization width, sparse-table offset, matrix order, and non-zeros per row.

size_t data_size

size_t offset

size_t n_row

size_t nnz_col

size_t default_register_size

Default register width (max of the address width and the element width)

qram_qutrit::QRAMCircuit *qram

Pointer to the QRAM circuit.

Public Static Attributes

static constexpr int suggest_reserve = 1024000

Suggested state-size reserve constant.

struct SparseMatrixOracle1 : public qram_simulator::SelfAdjointOperator

#include <hamiltonian_simulation.h>

Sparse-matrix oracle No. 1: matrix-element query (self-adjoint)

Queries the QRAM data table by (row i, in-row sparse slot s_j) and loads the corresponding quantized matrix element a_{ij}, i.e. |offset>|i>|s_j>|0> -> |offset>|i>|s_j>|a_{ij}>. The element address is computed by GetDataAddr (offset + row_size*i + s_j); after the load the address register is uncomputed again, keeping the whole self-adjoint.

Public Functions

SparseMatrixOracle1(qram_qutrit::QRAMCircuit *qram, std::string_view reg_offset, std::string_view reg_row, std::string_view reg_col_id, std::string_view reg_output, size_t row_size_)

Constructor.

参数:

• qram -- Pointer to the QRAM circuit

• reg_offset -- Name of the data-table offset register

• reg_row -- Name of the row-index register

• reg_col_id -- Name of the sparse-slot register

• reg_output -- Name of the query-result output register

• row_size_ -- Number of slots per row

template<typename Ty>
inline void impl(Ty &state) const

Forward implementation of the element query (also serves as the dagger implementation)

Computes data_addr = offset + row_size*i + s_j, loads the element into the output register via QRAM, then calls GetDataAddr again to uncompute the address register.

参数:

state -- System state vector

template<typename Ty>
inline void impl_dag(Ty &state) const

Dagger implementation of the element query.

The operator is self-adjoint and directly reuses the forward implementation.

参数:

state -- System state vector

inline virtual void dag(std::vector<System> &state) const override

Apply the dagger operation (the dagger of a self-adjoint operator equals itself)

参数:

state -- System state vector

inline virtual void dag(SparseState &state) const override

Apply dagger to a SparseState.

参数:

state -- Sparse state

inline virtual void dag(std::vector<System> &state) const

Apply the conjugate transpose (dagger) operation.

参数:

state -- System state vector

抛出:

Throws -- a not-implemented exception by default

inline virtual void dag(SparseState &state) const

Apply dagger to a SparseState.

参数:

state -- Sparse state

Public Members

qram_qutrit::QRAMCircuit *qram

Pointer to the QRAM circuit.

std::string reg_offset

Name of the data-table offset register.

std::string reg_row

Name of the row-index register.

std::string reg_col_id

Name of the sparse-slot register (the element's position in the row's compact storage)

std::string reg_output

Name of the query-result (quantized element) output register.

size_t row_size

Number of slots per row.

struct SparseMatrixOracle2 : public qram_simulator::BaseOperator

#include <hamiltonian_simulation.h>

Sparse-matrix oracle No. 2: conversion from column index to sparse slot.

Via quantum binary search, converts the matrix column index j into the sparse slot s_j of that element in the row's compact storage, i.e. |offset>|i>|j> -> |offset>|i>|s_j>. The start address of the row's sparse table is computed by GetRowAddr; the search yields the absolute address within the sparse table, so the column index is restored to a slot number by loading it via QRAM and subtracting the row-start address.

Public Functions

SparseMatrixOracle2(qram_qutrit::QRAMCircuit *qram, std::string_view reg_sparse_offset, std::string_view reg_row_, std::string_view reg_col_, std::string_view reg_search_result_, size_t row_size)

Constructor.

参数:

• qram -- Pointer to the QRAM circuit

• reg_sparse_offset -- Name of the sparse-table offset register

• reg_row_ -- Name of the row-index register

• reg_col_ -- Name of the column-index register

• reg_search_result_ -- Name of the binary-search result register

• row_size -- Number of slots per row

template<typename Ty>
inline void impl(Ty &state) const

Forward implementation of the column-index to sparse-slot conversion.

Steps in order: GetRowAddr computes the row's sparse-table start address -> quantum binary search locates the slot holding the column index -> QRAM load restores it -> swap and subtract the row-start address, so the column register finally holds the slot number s_j; the implementation carries detailed step-by-step comments.

参数:

state -- System state vector

template<typename Ty>
inline void impl_dag(Ty &state) const

Dagger implementation of the column-index to sparse-slot conversion.

Executes the forward implementation's steps in reverse, restoring the sparse slot s_j back into the column index j.

参数:

state -- System state vector

inline virtual void dag(std::vector<System> &state) const

Apply the conjugate transpose (dagger) operation.

参数:

state -- System state vector

抛出:

Throws -- a not-implemented exception by default

inline virtual void dag(SparseState &state) const

Apply dagger to a SparseState.

参数:

state -- Sparse state

Public Members

qram_qutrit::QRAMCircuit *qram

Pointer to the QRAM circuit.

std::string reg_sparse_offset

Name of the sparse-table offset register.

std::string reg_row

Name of the row-index register.

std::string reg_col

Name of the column-index register (the actual column index in the matrix)

std::string reg_search_result

Name of the binary-search result register.

size_t row_size

Number of slots per row.

struct SparseMatrixOracle2_ComputeCol : public qram_simulator::BaseOperator

#include <hamiltonian_simulation.h>

Computes the column index from the sparse slot (out-of-place, QRAM-query implementation)

|offset>|l>|z> -> |offset>|l>|z + k>: queries the QRAM at the address sparse-table offset plus slot l, obtains the corresponding column index k and accumulates (XORs) it into the target register; the address register is uncomputed after the query.

Public Functions

SparseMatrixOracle2_ComputeCol(qram_qutrit::QRAMCircuit *qram, std::string_view sparse_offset, std::string_view k, std::string_view l, std::string_view addr_offset, size_t row_size)

Constructor.

参数:

• qram -- Pointer to the QRAM circuit

• sparse_offset -- Name of the sparse-table offset register

• k -- Name of the column-index register

• l -- Name of the sparse-slot register

• addr_offset -- Name of the temporary address register

• row_size -- Number of slots per row

virtual void operator()(std::vector<System> &state) const

Applies the column-index computation.

参数:

state -- System state vector

Public Members

qram_qutrit::QRAMCircuit *qram

Pointer to the QRAM circuit.

std::string sparse_offset

Name of the sparse-table offset register.

std::string k

Name of the column-index register (query output)

std::string l

Name of the sparse-slot register.

std::string addr_offset

Name of the temporary address register.

size_t row_size

Number of slots per row.

struct SparseMatrixOracle2_ComputeSparsity : public qram_simulator::BaseOperator

#include <hamiltonian_simulation.h>

Computes the sparse slot from the column index (out-of-place, quantum-binary-search implementation)

|offset>|k>|z> -> |offset>|k>|z + l>: performs a quantum binary search over the row's sparse-table interval with the column index k as the target, accumulates the hit slot address (including the table offset) into l, and then subtracts the offset to restore the relative slot number.

Public Functions

SparseMatrixOracle2_ComputeSparsity(qram_qutrit::QRAMCircuit *qram, std::string_view sparse_offset, std::string_view k, std::string_view l, size_t row_size)

Constructor.

参数:

• qram -- Pointer to the QRAM circuit

• sparse_offset -- Name of the sparse-table offset register

• k -- Name of the column-index register

• l -- Name of the sparse-slot register

• row_size -- Number of slots per row

virtual void operator()(std::vector<System> &state) const

Applies the sparse-slot computation.

参数:

state -- System state vector

inline virtual void dag(std::vector<System> &state) const

Apply the conjugate transpose (dagger) operation.

参数:

state -- System state vector

抛出:

Throws -- a not-implemented exception by default

inline virtual void dag(SparseState &state) const

Apply dagger to a SparseState.

参数:

state -- Sparse state

Public Members

qram_qutrit::QRAMCircuit *qram

Pointer to the QRAM circuit.

std::string sparse_offset

Name of the sparse-table offset register.

std::string k

Name of the column-index register.

std::string l

Name of the sparse-slot register.

size_t row_size

Number of slots per row.

struct T : public qram_simulator::BaseOperator

#include <hamiltonian_simulation.h>

State-preparation operator T of the CKS quantum walk.

For the row index j, prepares the row's "square-root amplitude" superposition: |j>|0> -> Σ_k sqrt(A_{j,s_k}) |j>|k> (k is the in-row sparse slot). Workflow: apply Hadamard to the slot register k to form a uniform superposition -> Oracle1 loads the quantized element d[j,k] -> the dagger of Oracle2 maps k from the slot to the actual column index -> GetQWRotateAngle + CondRot_Fixed_Bool perform the conditional rotation with ratio sqrt(A_{j,k}) -> uncompute each oracle in turn to restore the registers.

Public Functions

inline T(qram_qutrit::QRAMCircuit *qram_, std::string_view reg_data_offset_, std::string_view reg_sparse_offset_, std::string_view reg_j_, std::string_view reg_b1_, std::string_view reg_k_, std::string_view reg_b2_, std::string_view reg_search_result_, size_t nnz_col_, size_t data_size_, const SparseMatrix *mat_)

Constructor.

参数:

• qram_ -- Pointer to the QRAM circuit

• reg_data_offset_ -- Name of the data-table offset register

• reg_sparse_offset_ -- Name of the sparse-table offset register

• reg_j_ -- Name of the row-index register

• reg_b1_ -- Name of the Boolean flag b1 register

• reg_k_ -- Name of the slot / column-index register

• reg_b2_ -- Name of the Boolean flag b2 register

• reg_search_result_ -- Name of the binary-search result register

• nnz_col_ -- Number of non-zero elements (slots) per row

• data_size_ -- Bit width of the temporary data register

• mat_ -- Pointer to the sparse matrix

template<typename Ty>
inline void impl(Ty &system_states) const

Forward implementation of the state preparation T.

Inside the function body, per-line state comments mark each step's register transformation (Hadamard superposition, oracle loading / mapping, conditional rotation, and uncomputation).

参数:

system_states -- System state vector

template<typename Ty>
inline void impl_dag(Ty &system_states) const

Dagger implementation of the state preparation T.

Uncomputes in the reverse order of the forward workflow (including the inverse conditional rotation), and inserts CheckNan / ClearZero / CheckNormalization checks.

参数:

system_states -- System state vector

inline virtual void dag(std::vector<System> &state) const

Apply the conjugate transpose (dagger) operation.

参数:

state -- System state vector

抛出:

Throws -- a not-implemented exception by default

inline virtual void dag(SparseState &state) const

Apply dagger to a SparseState.

参数:

state -- Sparse state

Public Members

qram_qutrit::QRAMCircuit *qram

Pointer to the QRAM circuit.

std::string reg_data_offset

Name of the data-table offset register.

std::string reg_sparse_offset

Name of the sparse-table offset register.

std::string reg_j

Name of the row-index register.

std::string reg_b1

Name of the Boolean flag b1 register.

std::string reg_k

Name of the slot / column-index register.

std::string reg_b2

Name of the Boolean flag b2 register (target of the conditional rotation)

std::string reg_search_result

Name of the binary-search result register.

size_t nnz_col

Number of non-zero elements (slots) per row.

size_t data_size

Bit width of the temporary data register (max of the address width and the element width)

const SparseMatrix *mat

Pointer to the sparse matrix.