Algorithm Library (Top Level)¶

Note

SparQ_Algorithm/include/qcnn.h (quantum convolutional neural networks) is currently disabled as a whole by #if false in the source, so it does not appear in this reference.

Grover Search (`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.

Parameters:

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.

Parameters:: 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.

Parameters:

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.

Parameters:: 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.

Parameters:

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.

Parameters:: 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)

Parameters:

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)

Parameters:

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.

Parameters:: 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)

Parameters:: qram_address_id_ – Address register ID

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

Constructor (register-name version)

Parameters:

qram_address_name – Address register name
size_ – Register bit width

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

Apply the diffusion operation.

Parameters:: 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

Template Parameters:

QRAM – QRAM circuit type (qutrit/qubit implementation)

Parameters:

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)

Parameters:

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)

Parameters:

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

Template Parameters:

QRAM – QRAM circuit type

Parameters:

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

Returns:

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

Shor Factoring (`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.

Parameters:

a – Base
x – Exponent (arbitrarily large integer)
N – Modulus (the odd composite to be factored)

Returns:

a^x mod N

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

Throw a Shor execution failure exception.

Parameters:: 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.

Parameters:

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)

Returns:

(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.

Parameters:

meas_result – Phase-estimation measured value
size – Working register bit width
N – Number to be factored

Returns:

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)

Parameters:

period – Period candidate
a – Base
N – Number to be factored

Throws:

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.

Parameters:

meas – Phase-estimation measured value
size – Working register bit width
a – Base
N – Number to be factored

Throws:

ShorExecutionFailed – Thrown when no valid period can be recovered

Returns:

(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

Parameters:

N – Odd composite to be factored
ainput – Optionally specified base (chosen at random by default)

Returns:

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

Parameters:

N – Odd composite to be factored
ainput – Optionally specified base (chosen at random by default)

Returns:

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.

Parameters:

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.

Parameters:: 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.

Parameters:

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)

Returns:: 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.

Parameters:

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.

Parameters:: 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.

Parameters:: message – Exception description

State Preparation (`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.

Parameters:

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

Template Parameters:: Ty – State type (std::vector<System> or SparseState)
Parameters:: 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

Template Parameters:: Ty – State type
Parameters:: 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.

Parameters:

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.

Parameters:

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.

Parameters:: 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.

Block Encoding Overview (`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.

Parameters:

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.

Parameters:

vec – Original result vector
size – Dimension of the main register space

Returns:

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)

Parameters:

vec – Original result vector
size – Dimension of the main register space

Returns:

New zero-padded vector

Hamiltonian Simulation (`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).

Parameters:

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.

Parameters:

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.

Parameters:: 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.

Parameters:

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

Returns:

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.

Parameters:

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

Returns:

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)

Parameters:: mat – Sparse matrix (captures its positive_only and data_size)
Returns:: 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)

Parameters:: mat – Sparse matrix (captures its positive_only and data_size)
Returns:: 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.

Parameters:: mat – Sparse matrix
Returns:: 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.

Parameters:

mat – Sparse matrix
vec – Right-hand-side vector

Returns:

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.

Parameters:: 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.

Note

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

Parameters:

Big – Upper parameter of the binomial coefficient
Small – Lower parameter of the binomial coefficient

Returns:

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

Parameters:: j – Term index (0 to b-1)
Returns:: Coefficient c_j

bool sign(size_t j)¶

Sign of the j-th term.

Parameters:: j – Term index
Returns:: 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.

Parameters:: j – Term index
Returns:: 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.

Parameters:

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)

Parameters:

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)

Parameters:

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)

Parameters:

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)

Parameters:

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)

Parameters:: state – System state vector

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

Applies the dagger of the general conditional rotation.

Parameters:: state – System state vector

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

Apply the conjugate transpose (dagger) operation.

Parameters:: state – System state vector
Throws:: Throws – a not-implemented exception by default

inline virtual void dag(SparseState &state) const¶

Apply dagger to a SparseState.

Parameters:: 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.

Parameters:: data – 2x2 matrix
Returns:: Whether the matrix is diagonal

static bool _is_off_diagonal(const u22_t &data)¶

Checks whether the matrix is anti-diagonal.

Parameters:: data – 2x2 matrix
Returns:: 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)

Parameters:

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)

Parameters:

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.

Parameters:: 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)

Parameters:: state – System state vector

inline virtual void dag(SparseState &state) const override¶

Apply dagger to a SparseState.

Parameters:: state – Sparse state

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

Apply the conjugate transpose (dagger) operation.

Parameters:: state – System state vector
Throws:: Throws – a not-implemented exception by default

inline virtual void dag(SparseState &state) const

Apply dagger to a SparseState.

Parameters:: 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)

Parameters:

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)

Parameters:

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.

Note

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

Parameters:: 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)

Parameters:: state – System state vector

inline virtual void dag(SparseState &state) const override¶

Apply dagger to a SparseState.

Parameters:: state – Sparse state

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

Apply the conjugate transpose (dagger) operation.

Parameters:: state – System state vector
Throws:: Throws – a not-implemented exception by default

inline virtual void dag(SparseState &state) const

Apply dagger to a SparseState.

Parameters:: 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)

Parameters:

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)

Parameters:

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.

Parameters:: 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)

Parameters:: state – System state vector

inline virtual void dag(SparseState &state) const override¶

Apply dagger to a SparseState.

Parameters:: state – Sparse state

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

Apply the conjugate transpose (dagger) operation.

Parameters:: state – System state vector
Throws:: Throws – a not-implemented exception by default

inline virtual void dag(SparseState &state) const

Apply dagger to a SparseState.

Parameters:: 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.

Parameters:

mat – Sparse matrix
kappa_ – Condition number
eps_ – Target precision

inline auto GetInputVecReg()¶

Gets the name of the register holding the input vector.

Returns:: 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.

Parameters:: j – Term index
Returns:: 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.

Parameters:

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.

Parameters:

mat – Sparse matrix
kappa – Condition number
eps – Target precision

inline auto GetInputVecReg() const¶

Gets the name of the register holding the input vector.

Returns:: The walk manager’s input register name

inline size_t get_addr_size() const¶

Gets the QRAM address width.

Returns:: 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.

Parameters:: 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.

Parameters:: 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:: 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.

Parameters:

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

Parameters:: state – System state vector (modified by the partial-trace selection)
Returns:: The LCU post-selection success probability

inline double PartialTrace()¶

Computes the post-selection success probability (destructive version)

Note

Modifies current_state.

Returns:: The success probability

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

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

Returns:: (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.

Parameters:

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.

Parameters:

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.

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

bool Step()¶

Advances the LCU by one term.

Returns:: 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.

Returns:: (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)

Parameters:

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)

Parameters:

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.

Parameters:: 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.

Parameters:: 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)

Parameters:: state – System state vector

inline virtual void dag(SparseState &state) const override¶

Apply dagger to a SparseState.

Parameters:: state – Sparse state

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

Apply the conjugate transpose (dagger) operation.

Parameters:: state – System state vector
Throws:: Throws – a not-implemented exception by default

inline virtual void dag(SparseState &state) const

Apply dagger to a SparseState.

Parameters:: 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)

Parameters:

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)

Parameters:

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.

Parameters:

offset – Start address of the search interval
target – Target value

Returns:

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)

Parameters:: 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)

Parameters:: state – System state vector

inline virtual void dag(SparseState &state) const override¶

Apply dagger to a SparseState.

Parameters:: state – Sparse state

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

Apply the conjugate transpose (dagger) operation.

Parameters:: state – System state vector
Throws:: Throws – a not-implemented exception by default

inline virtual void dag(SparseState &state) const

Apply dagger to a SparseState.

Parameters:: 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.

Parameters:

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

Parameters:: system_states – System state vector

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

Dagger implementation of the single-step quantum walk.

Note

Not implemented; throws an exception when called.

Parameters:: 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)

Parameters:

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)

Note

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

Parameters:: mat_ – Sparse matrix (QRAM memory is built from its compact layout)

inline ~QuantumWalkNSteps()¶: Destructor.

Note

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.

Returns:: The name of the row-index register j

inline size_t get_init_size() const¶

Gets the initialization width of the input register.

Returns:: 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.

Returns:: 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.

Parameters:: n_steps – Number of walk steps (0 means only the uniform Hadamard superposition is applied)
Returns:: 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).

Parameters:: 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.

Parameters:: 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).

Parameters:: 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.

Parameters:

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.

Parameters:: 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.

Parameters:: 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)

Parameters:: state – System state vector

inline virtual void dag(SparseState &state) const override¶

Apply dagger to a SparseState.

Parameters:: state – Sparse state

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

Apply the conjugate transpose (dagger) operation.

Parameters:: state – System state vector
Throws:: Throws – a not-implemented exception by default

inline virtual void dag(SparseState &state) const

Apply dagger to a SparseState.

Parameters:: 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.

Parameters:

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.

Parameters:: 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.

Parameters:: state – System state vector

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

Apply the conjugate transpose (dagger) operation.

Parameters:: state – System state vector
Throws:: Throws – a not-implemented exception by default

inline virtual void dag(SparseState &state) const¶

Apply dagger to a SparseState.

Parameters:: 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.

Parameters:

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.

Parameters:: 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.

Parameters:

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.

Parameters:: state – System state vector

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

Apply the conjugate transpose (dagger) operation.

Parameters:: state – System state vector
Throws:: Throws – a not-implemented exception by default

inline virtual void dag(SparseState &state) const¶

Apply dagger to a SparseState.

Parameters:: 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.

Parameters:

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

Parameters:: 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.

Parameters:: system_states – System state vector

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

Apply the conjugate transpose (dagger) operation.

Parameters:: state – System state vector
Throws:: Throws – a not-implemented exception by default

inline virtual void dag(SparseState &state) const¶

Apply dagger to a SparseState.

Parameters:: 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.

中文版 ===

算法库（顶层）¶

Note

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

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

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

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.

Parameters:

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.

Parameters:: 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.

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.

Parameters:

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.

Parameters:: 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.

Parameters:

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.

Parameters:: 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.

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)

Parameters:

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)

Parameters:

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.

Parameters:: 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.

Public Functions

inline ClassControllable HPH(size_t qram_address_id_)

Constructor (register-ID version)

Parameters:: qram_address_id_ – Address register ID

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

Constructor (register-name version)

Parameters:

qram_address_name – Address register name
size_ – Register bit width

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

Apply the diffusion operation.

Parameters:: 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.

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

Template Parameters:

QRAM – QRAM circuit type (qutrit/qubit implementation)

Parameters:

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)

Parameters:

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)

Parameters:

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

Template Parameters:

QRAM – QRAM circuit type

Parameters:

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

Returns:

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)

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.

Parameters:

a – Base
x – Exponent (arbitrarily large integer)
N – Modulus (the odd composite to be factored)

Returns:

a^x mod N

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

Throw a Shor execution failure exception.

Parameters:: 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.

Parameters:

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)

Returns:

(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.

Parameters:

meas_result – Phase-estimation measured value
size – Working register bit width
N – Number to be factored

Returns:

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)

Parameters:

period – Period candidate
a – Base
N – Number to be factored

Throws:

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.

Parameters:

meas – Phase-estimation measured value
size – Working register bit width
a – Base
N – Number to be factored

Throws:

ShorExecutionFailed – Thrown when no valid period can be recovered

Returns:

(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

Parameters:

N – Odd composite to be factored
ainput – Optionally specified base (chosen at random by default)

Returns:

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

Parameters:

N – Odd composite to be factored
ainput – Optionally specified base (chosen at random by default)

Returns:

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)

Public Functions

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

Constructor.

Parameters:

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.

Parameters:: 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)

Public Functions

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

Constructor.

Parameters:

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)

Returns:: 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)

Public Functions

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

Constructor.

Parameters:

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.

Parameters:: 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.

Parameters:: message – Exception description

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

QRAM-based arbitrary sparse state preparation.

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)

Public Functions

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

Constructor.

Parameters:

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.

Template Parameters:: Ty – State type (std::vector<System> or SparseState)
Parameters:: state – System state

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

Inverse (dagger) preparation implementation.

Template Parameters:: Ty – State type
Parameters:: 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.

Parameters:

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.

Public Functions

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

Constructor.

Parameters:

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.

Parameters:: 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.

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.

Parameters:

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.

Parameters:

vec – Original result vector
size – Dimension of the main register space

Returns:

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)

Parameters:

vec – Original result vector
size – Dimension of the main register space

Returns:

New zero-padded vector

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

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

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)

Parameters:

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)

Parameters:

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.

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