Discrete Adiabatic (DiscreteAdiabatic/)¶

QDA Fundamental Components (`SparQ_Algorithm/include/DiscreteAdiabatic/qda_fundamental.h`)¶

Fundamental components of the quantum discrete adiabatic (QDA) linear-system solver.

Implements the core components of the optimal-scaling quantum linear-systems solver based on the discrete adiabatic theorem (Optimal scaling quantum linear-systems solver via discrete adiabatic theorem, PRX Quantum, 2022, 3(4): 040303; construction details in Appendix F of the paper): the block encoding of the interpolated Hamiltonian H(s) = (1-f(s))H₀ + f(s)H₁ (Block_Encoding_Hs / Block_Encoding_Hs_PD), the single-step quantum walk operator (Walk_s), the LCU combination of walk powers together with Dolph-Chebyshev filtering (Filtering), and fidelity debugging tools (QDADebugger / GetOutput). The interpolation parameter f(s) is taken from Eq. (69) of the paper, and the algorithm complexity is O(κ log(κ/ε)); the concrete solving procedure is assembled in qda_tridiagonal.h / qda_via_QRAM.h

namespace qram_simulator

QRAM sparse state simulator namespace.

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

namespace QDA¶

Discrete adiabatic (QDA) linear-system solver.

Functions

template<typename Ty> auto GetQb(const Eigen::MatrixBase<Ty> &b) -> EigenMat<complex_t>¶

Build the projector-complement operator matrix Q_b = I - (|0⟩⟨0|)⊗(|b⟩⟨b|)

Parameters:: b – Normalized right-hand side vector
Template Parameters:: Ty – Eigen vector expression type
Returns:: Complex matrix corresponding to Q_b (extended space)

template<typename Ty> EigenMat<complex_t> GetAf(const Eigen::MatrixBase<Ty> &A, double fs)¶

Build the Hermitian extended interpolation operator A_f.

Parameters:

A – Original matrix
fs – Interpolation parameter f(s)

Template Parameters:

Ty – Eigen matrix expression type

Returns:

Complex matrix corresponding to A_f = (1-f)·σz⊗I + f·[[0, A], [A†, 0]]

template<typename Ty1, typename Ty2> EigenMat<complex_t> GetHs(const Eigen::MatrixBase<Ty1> &A, double fs, const Eigen::MatrixBase<Ty2> &b)¶

Build the interpolated Hamiltonian matrix H(s) (off-diagonal block form)

Parameters:

A – Original matrix
fs – Interpolation parameter f(s)
b – Normalized right-hand side vector

Template Parameters:

Ty1 – Eigen matrix expression type
Ty2 – Eigen vector expression type

Returns:

H(s) = c·[[0, A_f·Q_b], [Q_b·A_f, 0]], where c = 1/√(2f² + 2(1-f)²)

inline std::vector<double> CalculateAngles(std::vector<double> &coeffs)¶

Compute the rotation-angle sequence for sequential state preparation from a list of nonnegative coefficients.

Parameters:: coeffs – List of nonnegative coefficients
Throws:: Throws – an exception when a coefficient is negative
Returns:: List of rotation angles θ_i = 2·arccos(√(c_i / Σ_{j≥i} c_j))

inline double chebyshevT(size_t n, double x)¶

Compute the Chebyshev polynomial of the first kind T_n(x) (iterative implementation)

Parameters:

n – Polynomial order
x – Input value

Returns:

T_n(x)

inline double DolphChebyshev(double epsilon_, int l_, double phi_)¶

Compute the Dolph-Chebyshev window function value.

Parameters:

epsilon_ – Error tolerance ε
l_ – Window length parameter l
phi_ – Phase angle φ

Returns:

ε·T_l(cosh(acosh(1/ε)/l)·cos φ)

inline double FourierSeries(std::vector<double> weights, double x)¶

Evaluate an even-function Fourier series.

Parameters:

weights – Coefficient list (w_0 is the constant term)
x – Evaluation point

Returns:

w_0 + Σ_{i≥1} 2·w_i·cos(i·x)

inline std::vector<double> ComputeFourierCoeffs(double epsilon_, int l_)¶

Numerically compute the Fourier coefficients of the Dolph-Chebyshev filter.

Parameters:

epsilon_ – Error tolerance ε
l_ – Filter length parameter l

Returns:

List of even-order coefficients (numerical integration of the window function, keeping only terms with even j)

template<typename Block_Encoding, typename State_Prep, typename StateType = SparseState> DenseMatrix<complex_t> _extract_full_unitary(Block_Encoding_Hs<Block_Encoding, State_Prep> encHs, std::string main_reg, std::string anc_UA, std::string anc_1, std::string anc_2, std::string anc_3, std::string anc_4)¶

Extract the full unitary matrix of Block_Encoding_Hs (for debugging)

Parameters:

encHs – H(s) block encoding operator
main_reg – Main data register name
anc_UA – Ancilla register name of the block encoding of A
anc_1 – Ancilla register anc_1 name
anc_2 – Ancilla register anc_2 name
anc_3 – Ancilla register anc_3 name
anc_4 – Ancilla register anc_4 name

Template Parameters:

Block_Encoding – Block encoding type of A
State_Prep – State preparation type of |b⟩
StateType – State container type (default SparseState)

Returns:

Full unitary matrix of dimension 2^(main register bits + anc_UA bits + 4)

template<typename Block_Encoding, typename State_Prep> DenseMatrix<complex_t> extract_full_unitary(Block_Encoding_Hs<Block_Encoding, State_Prep> encHs, std::string main_reg, std::string anc_UA, std::string anc_1, std::string anc_2, std::string anc_3, std::string anc_4)¶

Extract the full unitary matrix of Block_Encoding_Hs (convenient SparseState wrapper)

Parameters:

encHs – H(s) block encoding operator
main_reg – Main data register name
anc_UA – Ancilla register name of the block encoding of A
anc_1 – Ancilla register anc_1 name
anc_2 – Ancilla register anc_2 name
anc_3 – Ancilla register anc_3 name
anc_4 – Ancilla register anc_4 name

Template Parameters:

Block_Encoding – Block encoding type of A
State_Prep – State preparation type of |b⟩

Returns:

Full unitary matrix

template<typename Block_Encoding, typename State_Prep, typename StateType = SparseState> DenseMatrix<complex_t> _extract_block_encoding_Hs(Block_Encoding_Hs<Block_Encoding, State_Prep> encHs, std::string main_reg, std::string anc_UA, std::string anc_1, std::string anc_2, std::string anc_3, std::string anc_4, size_t qubit_num)¶

Extract the effective encoded block of the H(s) block encoding (for debugging)

Parameters:

encHs – H(s) block encoding operator
main_reg – Main data register name
anc_UA – Ancilla register name of the block encoding of A
anc_1 – Ancilla register anc_1 name
anc_2 – Ancilla register anc_2 name
anc_3 – Ancilla register anc_3 name
anc_4 – Ancilla register anc_4 name
qubit_num – Number of qubits n of the main register

Template Parameters:

Block_Encoding – Block encoding type of A
State_Prep – State preparation type of |b⟩
StateType – State container type (default SparseState)

Returns:

2^(n+2)-dimensional matrix, post-selected (anc_UA / anc_2 / anc_3 all 0) and normalized by the success probability, whose row and column indices include the two outer block indicators anc_1 and anc_4

template<typename Block_Encoding, typename State_Prep> DenseMatrix<complex_t> extract_block_encoding_Hs(Block_Encoding_Hs<Block_Encoding, State_Prep> encHs, std::string main_reg, std::string anc_UA, std::string anc_1, std::string anc_2, std::string anc_3, std::string anc_4, size_t qubit_num)¶

Extract the effective encoded block of the H(s) block encoding (convenient SparseState wrapper)

Parameters:

encHs – H(s) block encoding operator
main_reg – Main data register name
anc_UA – Ancilla register name of the block encoding of A
anc_1 – Ancilla register anc_1 name
anc_2 – Ancilla register anc_2 name
anc_3 – Ancilla register anc_3 name
anc_4 – Ancilla register anc_4 name
qubit_num – Number of qubits of the main register

Template Parameters:

Block_Encoding – Block encoding type of A
State_Prep – State preparation type of |b⟩

Returns:

Encoded block matrix after post-selection normalization

template<typename Block_Encoding, typename State_Prep> struct Block_Encoding_Hs¶

#include <qda_fundamental.h>

Block encoding of the interpolated Hamiltonian H(s) (general version)

H(s) = (1-f(s))H₀ + f(s)H₁: H₀ is built from the |b⟩ state preparation (enc_b) and a reflection on the main register, while H₁ is built from the block encoding of A (enc_A) (circuit details in Appendix F of the paper above). The interpolation is realized by applying the rotation matrix R_s = [[√N(1-f), √N f], [√N f, √N(f-1)]] (√N = 1/√((1-f)²+f²)) on anc_2; combined with controlled enc_A/enc_b and the reflections at each level, the whole forms a (⟨0|⊗I) U (|0|⊗I)-type block encoding of H(s). Supports conditional control (ClassControllable)

Template Parameters:

Block_Encoding – Block encoding type of A
State_Prep – State preparation type of |b⟩

Public Functions

inline ClassControllable Block_Encoding_Hs(Block_Encoding enc_A_, State_Prep enc_b_, std::string_view main_reg_, std::string_view anc_UA_, std::string_view anc_1_, std::string_view anc_2_, std::string_view anc_3_, std::string_view anc_4_, double fs_)¶

Constructor (computes the interpolation rotation matrix R_s)

Parameters:

enc_A_ – Block encoding operator of A
enc_b_ – State preparation operator of |b⟩
main_reg_ – Main data register name
anc_UA_ – Ancilla register name of the block encoding of A
anc_1_ – Ancilla register anc_1 name
anc_2_ – Ancilla register anc_2 name (target of the interpolation rotation)
anc_3_ – Ancilla register anc_3 name
anc_4_ – Ancilla register anc_4 name
fs_ – Interpolation parameter f(s)

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

Block encoding circuit implementation (forward)

Circuit sequence: H(anc_3) → enc_b† → main-register reflection (controlled) → enc_b → R_s interpolation rotation (controlled on anc_4) → H(anc_2) → controlled enc_A and reflection → inverse interpolation rotation → second round of the enc_b reflection sequence → H(anc_3)

Parameters:: state – System state vector

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

Block encoding circuit implementation (dagger, inverse)

Note

The current implementation throws a runtime error right at the entry (not yet completed); calling it fails immediately

Parameters:: state – System state vector

Public Members

double fs¶: Interpolation parameter f(s) ∈ [0,1].

u22_t R_s¶: Interpolation rotation matrix R_s (applied on anc_2)

std::string main_reg¶: Main data register name.

std::string anc_UA¶: Ancilla register name used by the block encoding of A.

std::string anc_1¶: Ancilla register anc_1 name.

std::string anc_2¶: Ancilla register anc_2 name (target of the interpolation rotation)

std::string anc_3¶: Ancilla register anc_3 name.

std::string anc_4¶: Ancilla register anc_4 name.

Block_Encoding enc_A¶: Block encoding operator of matrix A.

State_Prep enc_b¶: State preparation operator of the right-hand side |b⟩

template<typename Block_Encoding, typename State_Prep> struct Block_Encoding_Hs_PD¶

#include <qda_fundamental.h>

Block encoding of the interpolated Hamiltonian H(s) (positive-definite version)

Applicable when A is a positive-definite matrix; the circuit is leaner than the general version (some controlled layers are omitted, the interpolation rotation R_s acts on anc_1 instead, and enc_A is controlled by {anc_1, anc_3}); the construction of H(s) = (1-f(s))H₀ + f(s)H₁ follows the same idea as the general version. Supports conditional control (ClassControllable)

Template Parameters:

Block_Encoding – Block encoding type of A
State_Prep – State preparation type of |b⟩

Public Functions

inline ClassControllable Block_Encoding_Hs_PD(Block_Encoding enc_A_, State_Prep enc_b_, std::string_view main_reg_, std::string_view anc_UA_, std::string_view anc_1_, std::string_view anc_2_, std::string_view anc_3_, std::string_view anc_4_, double fs_)¶

Constructor (computes the interpolation rotation matrix R_s)

Parameters:

enc_A_ – Block encoding operator of A
enc_b_ – State preparation operator of |b⟩
main_reg_ – Main data register name
anc_UA_ – Ancilla register name of the block encoding of A
anc_1_ – Ancilla register anc_1 name (target of the interpolation rotation)
anc_2_ – Ancilla register anc_2 name
anc_3_ – Ancilla register anc_3 name
anc_4_ – Ancilla register anc_4 name (unused in the positive-definite version)
fs_ – Interpolation parameter f(s)

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

Positive-definite block encoding circuit implementation (forward)

Circuit sequence: H(anc_2) → enc_b† → main-register reflection (controlled on {anc_2, anc_3}) → enc_b → R_s interpolation rotation (controlled on anc_3) → H(anc_1) → controlled enc_A and enc_A† → inverse interpolation rotation → second round of the enc_b reflection sequence → H(anc_2)

Parameters:: state – System state vector

Public Members

double fs¶: Interpolation parameter f(s) ∈ [0,1].

u22_t R_s¶: Interpolation rotation matrix R_s (applied on anc_1)

std::string main_reg¶: Main data register name.

std::string anc_UA¶: Ancilla register name used by the block encoding of A.

std::string anc_1¶: Ancilla register anc_1 name (target of the interpolation rotation)

std::string anc_2¶: Ancilla register anc_2 name.

std::string anc_3¶: Ancilla register anc_3 name.

std::string anc_4¶: Ancilla register anc_4 name.

Block_Encoding enc_A¶: Block encoding operator of matrix A.

State_Prep enc_b¶: State preparation operator of the right-hand side |b⟩

template<typename Walk_type> struct Filtering¶

#include <qda_fundamental.h>

Dolph-Chebyshev filtering operator (QDA accuracy enhancement)

Applies filtering to the walk sequence to amplify the amplitude of the successful branch: first prepares the filter-coefficient state on the index register using a QRAM (qram_w), applies a Hadamard on anc_h followed by the controlled LCU walk-power expansion, then realizes reflection-style filtering through the alternating combination of X(anc_h) and LCU†, and finally undoes the preparation and reads the success probability. The filter coefficients are given by ComputeFourierCoeffs (Dolph-Chebyshev window). Supports conditional control (ClassControllable)

Template Parameters:: Walk_type – Walk operator type

Public Functions

inline Filtering(qram_qutrit::QRAMCircuit *qram_w, Walk_type Walk, std::string main_reg, std::string anc_UA, std::string anc_4, std::string anc_3, std::string anc_2, std::string anc_1, std::string index, std::string anc_h, size_t ds, size_t rs, std::string stdout_filename_)¶

Constructor.

Parameters:

qram_w – Pointer to the QRAM circuit storing the filter coefficients
Walk – Walk operator instance
main_reg – Main data register name
anc_UA – Ancilla register name of the block encoding of A
anc_4 – Ancilla register anc_4 name
anc_3 – Ancilla register anc_3 name
anc_2 – Ancilla register anc_2 name
anc_1 – Ancilla register anc_1 name
index – LCU index register name
anc_h – Filtering ancilla register name
ds – Data register bit width
rs – Rational register bit width
stdout_filename_ – Run log file path

template<typename Ty> inline void random_state_generate(Ty &state)¶

Generate a random initial state (for debugging)

Applies Hadamards on anc_1 and the main register, then injects a random real amplitude into each branch and normalizes

Parameters:: state – System state vector

template<typename Ty> inline double operator()(Ty &state)¶

Execute the filtering procedure and return the success probability.

Procedure: coefficient state preparation → H(anc_h) → LCU (controlled) → X(anc_h) → LCU† (controlled) → X(anc_h) → H(anc_h) → inverse preparation; afterwards writes the peak resource statistics to the log file

Parameters:: state – System state vector
Returns:: Post-selection probability (branches where both anc_h and index are 0), obtained by squaring the partial-trace amplitude

Public Members

qram_qutrit::QRAMCircuit *qram_w¶: Pointer to the QRAM circuit storing the filter coefficients.

std::string main_reg¶: Main data register name.

std::string anc_UA¶: Ancilla register name used by the block encoding of A.

std::string anc_4¶: Ancilla register anc_4 name.

std::string anc_3¶: Ancilla register anc_3 name.

std::string anc_2¶: Ancilla register anc_2 name.

std::string anc_1¶: Ancilla register anc_1 name.

std::string index¶: LCU index register name.

std::string anc_h¶: Filtering ancilla register name.

size_t data_size¶: Data register bit width (fixed-point quantization bits)

size_t rational_size¶: Rational (rotation-angle) register bit width.

Walk_type Walk¶: Walk operator instance.

int index_size¶: Index register bit width.

std::string stdout_filename¶: Run log file path.

struct GetOutput¶

#include <qda_fundamental.h>

Post-selection readout operator.

Filters out, from the final evolved state, the branches in which every specified ancilla register (anc_registers) takes value 0, and returns the normalized amplitude vector (main register + anc_1 + anc_4 layout) together with the success probability (sum of the weights of the matching branches); used to read out the solution of the discrete adiabatic evolution and verify its fidelity

Public Functions

inline GetOutput(std::string main_reg, std::string anc_UA, std::string anc_4, std::string anc_3, std::string anc_2, std::string anc_1, bool is_PD = false)¶

Constructor (basic version, post-selects {anc_UA, anc_3, anc_2})

Parameters:

main_reg – Main register name
anc_UA – Ancilla register name of the block encoding of A
anc_4 – Ancilla register anc_4 name
anc_3 – Ancilla register anc_3 name
anc_2 – Ancilla register anc_2 name
anc_1 – Ancilla register anc_1 name
is_PD – Positive-definite mode flag (unused in the current implementation; both modes post-select the same set of registers)

inline GetOutput(std::string main_reg, std::string anc_UA, std::string anc_4, std::string anc_3, std::string anc_2, std::string anc_1, std::string index, std::string anc_h)¶

Constructor (filtering version, post-selects {anc_UA, anc_3, anc_2, index, anc_h})

Parameters:

main_reg – Main register name
anc_UA – Ancilla register name of the block encoding of A
anc_4 – Ancilla register anc_4 name
anc_3 – Ancilla register anc_3 name
anc_2 – Ancilla register anc_2 name
anc_1 – Ancilla register anc_1 name
index – LCU index register name
anc_h – Filtering ancilla register name

std::pair<std::vector<complex_t>, double> operator()(const std::vector<System> &state) const¶

Extract the post-selected subspace from a system state vector (concrete implementation in qda_fundamental.cpp)

Parameters:: state – System state vector
Returns:: {Normalized amplitude vector (index = main_reg value + anc_1·2^n + anc_4·2^(n+1)), success probability}

inline std::pair<std::vector<complex_t>, double> operator()(const SparseState &state) const¶

Extract the post-selected subspace from a sparse state (delegates to the basis-state-list version)

Parameters:: state – Sparse state
Returns:: {Normalized amplitude vector, success probability}

template<typename Ty> inline bool check_removable(Ty &state)¶

Check whether the specified ancilla registers are zero in all branches.

Note

Uses the index/anc_h members; it is only meaningful when constructed via the constructor that includes them

Parameters:: state – System state vector
Returns:: Returns true when {anc_UA, anc_3, anc_2, index, anc_h} are all 0

template<typename Ty> inline std::pair<Ty, double> get_subspace(Ty &state)¶

Extract the subspace where all ancilla registers (anc_registers) are zero and normalize it.

Parameters:: state – System state vector
Returns:: {Subspace state list (normalized when the weight sum is nonzero), subspace probability sum}

Public Members

size_t main_reg¶: Main register ID.

size_t anc_UA¶: Ancilla register ID of the block encoding of A.

size_t anc_4¶: Ancilla register anc_4 ID.

size_t anc_3¶: Ancilla register anc_3 ID.

size_t anc_2¶: Ancilla register anc_2 ID.

size_t anc_1¶: Ancilla register anc_1 ID.

size_t index¶: LCU index register ID (used by the filtering procedure)

size_t anc_h¶: Filtering ancilla register anc_h ID.

std::vector<size_t> anc_registers¶: List of ancilla register IDs participating in the post-selection.

template<typename Walk_s> struct LCU¶

#include <qda_fundamental.h>

LCU (linear combination of unitaries) container of powers of the walk operator.

For the i-th bit of the index register, builds a walk operator controlled by that bit and applies it 2^(i+1) times; combined with the coefficient state preparation on the index register (State_Prep_via_QRAM), realizes the Σ_k c_k W^k-type expansion in walk powers (LCU). The progress of each step is both printed and written to the log file. Supports conditional control (ClassControllable)

Template Parameters:: Walk_s – Walk operator type

Public Functions

inline ClassControllable LCU(Walk_s Walk, size_t index, std::string filename_)¶

Constructor (index given as a register ID)

Parameters:

Walk – Walk operator instance
index – Index register ID
filename_ – Log file path

inline LCU(Walk_s Walk, std::string index, std::string filename_)¶

Constructor (index given as a register name)

Parameters:

Walk – Walk operator instance
index – Index register name
filename_ – Log file path

template<typename Ty> inline void operator()(Ty &state)¶

Execute the LCU combination (forward)

Parameters:: state – System state vector

template<typename Ty> inline void dag(Ty &state)¶

Execute the LCU combination (dagger, inverse)

Parameters:: state – System state vector

Public Members

size_t index¶: LCU index register ID.

Walk_s Walk¶: Walk operator instance.

size_t index_size¶: Index register bit width.

std::string filename¶: Log file path.

struct QDADebugger¶

#include <qda_fundamental.h>

QDA classical reference-solution debugger.

Stores the original matrix A and the right-hand side b, and computes the ideal results of each stage of the discrete adiabatic evolution on the classical side: the Hermitian extended interpolation matrix A_f, the ideal initial states |0⟩⊗|b⟩ and |1⟩⊗|b⟩, and the ideal eigenstate at intermediate times (obtained via a classical linear solver); used for fidelity comparison against the quantum simulation results

Subclassed by qram_simulator::QDA::QDA_tridiagonal::Walk_s_Tridiagonal_Debug, qram_simulator::QDA::QDA_via_QRAM::Walk_s_via_QRAM_Debug

Public Functions

inline QDADebugger(const DenseMatrix<double> &matrix_A_, const DenseVector<double> &vector_b_, double s_, double kappa_, double p_)¶

Constructor (computes f(s) from s, κ, p via Eq. (69))

Parameters:

matrix_A_ – Original matrix A
vector_b_ – Original right-hand side vector b
s_ – Adiabatic evolution discretization parameter s
kappa_ – Condition number κ
p_ – Adiabatic schedule parameter p

DenseMatrix<double> get_matrix_Af()¶

Compute the Hermitian extended interpolation matrix A_f.

Returns:: 2n×2n matrix [[(1-f)I, fA], [fA†, -(1-f)I]]

DenseVector<double> get_vector_0b()¶

Ideal initial state vector |0⟩⊗|b⟩ (extended space)

Returns:: 2n-dimensional vector whose first n components are b and last n are 0

DenseVector<double> get_vector_1b()¶

Ideal vector |1⟩⊗|b⟩ (extended space)

Returns:: 2n-dimensional vector whose first n components are 0 and last n are b

std::vector<double> get_mid_eigenstate(bool is_PD = false)¶

Compute the ideal eigenstate at intermediate time s (fidelity reference state)

Parameters:: is_PD – Whether this is the positive-definite case (unused in the current implementation)
Returns:: Real vector of length 4n (zero-padded according to the main register + ancilla layout, for direct comparison with the quantum state)

Public Members

DenseMatrix<double> matrix_A¶: Original matrix A.

DenseVector<double> vector_b¶: Original right-hand side vector b.

double fs¶: Interpolation parameter f(s)

size_t row_size¶: Dimension of b.

template<typename Block_Encoding, typename State_Prep, bool PD = false> struct Walk_s¶

#include <qda_fundamental.h>

Single-step quantum walk operator W(s) at parameter s.

Single-step implementation of the discrete adiabatic evolution: W(s) = i · R · U_H(s), where U_H(s) is the block encoding of the interpolated Hamiltonian H(s) = (1-f(s))H₀ + f(s)H₁ and R is the reflection over the block-encoding ancilla registers (acting on {anc_UA, anc_1, anc_2} when PD = true, otherwise on {anc_UA, anc_2, anc_3}); the whole is then multiplied by the global phase i. The interpolation parameter is computed according to Eq. (69) of the paper: fs = κ/(κ-1) · (1 - (1 + s(κ^(p-1) - 1))^(1/(1-p))). Supports conditional control (ClassControllable)

Note

PD only switches the registers used by the reflection; enc_Hs always uses the general block encoding Block_Encoding_Hs (see the commented-out conditional type alias EncHs for switching to the positive-definite block encoding)

Template Parameters:

Block_Encoding – Block encoding type of A
State_Prep – State preparation type of |b⟩
PD – Whether to use the reflection register set of the positive-definite variant

Public Types

using EncHs = Block_Encoding_Hs<Block_Encoding, State_Prep>¶: Type alias of the H(s) block encoding.

Public Functions

inline ClassControllable Walk_s(Block_Encoding enc_A_, State_Prep enc_b_, std::string_view main_reg_, std::string_view anc_UA_, std::string_view anc_1_, std::string_view anc_2_, std::string_view anc_3_, std::string_view anc_4_, double s_, double kappa_, double p_)¶

Constructor (internally derives f(s) and assembles the H(s) block encoding)

Parameters:

enc_A_ – Block encoding operator of A
enc_b_ – State preparation operator of |b⟩
main_reg_ – Main data register name
anc_UA_ – Ancilla register name of the block encoding of A
anc_1_ – Ancilla register anc_1 name
anc_2_ – Ancilla register anc_2 name
anc_3_ – Ancilla register anc_3 name
anc_4_ – Ancilla register anc_4 name
s_ – Adiabatic evolution discretization parameter s ∈ [0,1]
kappa_ – Condition number κ
p_ – Adiabatic schedule parameter p

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

Single-step walk circuit implementation (forward): H(s) block encoding → reflection → global phase.

Parameters:: state – System state vector

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

Single-step walk circuit implementation (dagger, inverse): global phase⁻¹ → reflection → H(s) block encoding†

Parameters:: state – System state vector

Public Members

double s¶: Adiabatic evolution discretization parameter s ∈ [0,1].

double kappa¶: Condition number κ of the linear system.

double p¶: Adiabatic schedule parameter p.

double fs¶: Interpolation parameter f(s) (computed from s, κ, p via Eq. (69) of the paper)

complex_t phase = complex_t(0, 1.0)¶: Global phase factor (default i)

std::string main_reg¶: Main data register name.

std::string anc_UA¶: Ancilla register name used by the block encoding of A.

std::string anc_1¶: Ancilla register anc_1 name.

std::string anc_2¶: Ancilla register anc_2 name.

std::string anc_3¶: Ancilla register anc_3 name.

std::string anc_4¶: Ancilla register anc_4 name.

Block_Encoding enc_A¶: Block encoding operator of matrix A.

State_Prep enc_b¶: State preparation operator of the right-hand side |b⟩

EncHs enc_Hs¶: Block encoding operator instance of H(s)

Public Static Attributes

static constexpr bool is_positive_definite = PD ¶: Positive-definite variant flag (compile-time constant from template parameter PD)

Tridiagonal QDA Solver (`SparQ_Algorithm/include/DiscreteAdiabatic/qda_tridiagonal.h`)¶

Tridiagonal-matrix version of the QDA linear-system solver.

Instantiates the generic single-step discrete adiabatic walk Walk_s from qda_fundamental.h for the tridiagonal setting: the block encoding of the matrix A = αI + βT uses Block_Encoding_Tridiagonal, and the encoding of the right-hand side b uses Hadamard_Int_Full (uniform distribution). Provides Walk_s_Tridiagonal (standard version) and Walk_s_Tridiagonal_Debug (debug version with fidelity comparison). The corresponding Python implementation is pysparq.algorithms.qda_solver; the C++ experiment entry point is Experiments/QDA

namespace qram_simulator

QRAM sparse state simulator namespace.

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

namespace QDA

Discrete adiabatic (QDA) linear-system solver.

namespace QDA_tridiagonal¶

Tridiagonal-matrix version of the QDA solver.

struct Walk_s_Tridiagonal : public qram_simulator::QDA::Walk_s<Block_Encoding_Tridiagonal, Hadamard_Int_Full>¶

#include <qda_tridiagonal.h>

Single-step discrete adiabatic walk for the tridiagonal setting.

Combines Block_Encoding_Tridiagonal (block encoding of A = αI + βT) with Hadamard_Int_Full (uniform-superposition encoding of b), and implements the single-step walk of the interpolated Hamiltonian H(s) following the Walk_s template of qda_fundamental.h

Subclassed by qram_simulator::QDA::QDA_tridiagonal::Walk_s_Tridiagonal_Debug

Public Types

using EncA = Block_Encoding_Tridiagonal¶: Matrix block encoding type.

using Encb = Hadamard_Int_Full ¶: Right-hand side encoding type.

Public Functions

inline Walk_s_Tridiagonal(std::string_view main_reg_, std::string_view anc_UA_, std::string_view anc_1_, std::string_view anc_2_, std::string_view anc_3_, std::string_view anc_4_, double s_, double kappa_, double p_, double alpha_, double beta_)¶

Constructor.

Parameters:

main_reg_ – Main register name
anc_UA_ – Block encoding ancilla register name
anc_1_ – Ancilla register 1 name
anc_2_ – Ancilla register 2 name
anc_3_ – Ancilla register 3 name
anc_4_ – Ancilla register 4 name
s_ – Interpolation parameter s ∈ [0, 1]
kappa_ – Condition number κ
p_ – Success probability parameter
alpha_ – Tridiagonal diagonal coefficient α
beta_ – Tridiagonal subdiagonal coefficient β

struct Walk_s_Tridiagonal_Debug : public qram_simulator::QDA::QDA_tridiagonal::Walk_s_Tridiagonal, public qram_simulator::QDA::QDADebugger ¶

#include <qda_tridiagonal.h>

Debug version of the tridiagonal QDA walk.

Extends Walk_s_Tridiagonal with a QDADebugger: holds classical copies of the matrix/vector for fidelity comparison against the ideal intermediate eigenstate

Public Functions

inline Walk_s_Tridiagonal_Debug(const DenseMatrix<double> &matrix, const DenseVector<double> &vec, std::string_view main_reg_, std::string_view anc_UA_, std::string_view anc_1_, std::string_view anc_2_, std::string_view anc_3_, std::string_view anc_4_, double s_, double kappa_, double p_, double alpha_, double beta_)¶

Constructor.

Parameters:

matrix – Classical copy of the tridiagonal matrix (for fidelity comparison)
vec – Classical copy of the right-hand side (for fidelity comparison)
main_reg_ – Main register name
anc_UA_ – Block encoding ancilla register name
anc_1_ – Ancilla register 1 name
anc_2_ – Ancilla register 2 name
anc_3_ – Ancilla register 3 name
anc_4_ – Ancilla register 4 name
s_ – Interpolation parameter s ∈ [0, 1]
kappa_ – Condition number κ
p_ – Success probability parameter
alpha_ – Tridiagonal diagonal coefficient α
beta_ – Tridiagonal subdiagonal coefficient β

QRAM-Based QDA Solver (`SparQ_Algorithm/include/DiscreteAdiabatic/qda_via_QRAM.h`)¶

QRAM-based general-matrix QDA linear-system solver.

Instantiates the generic single-step discrete adiabatic walk Walk_s from qda_fundamental.h for the QRAM setting: the block encoding of the matrix A uses Block_Encoding_via_QRAM (data from the qram_A hierarchy tree), and the encoding of the right-hand side b uses State_Prep_via_QRAM (data from the qram_b hierarchy tree). Includes the template version with customizable b encoding (Walk_s_via_QRAM_A), the standard version (Walk_s_via_QRAM), the debug version (Walk_s_via_QRAM_Debug), and the complete multi-step solving sequence (WalkSequence_via_QRAM_Debug, with per-step fidelity statistics). The corresponding Python implementation is pysparq.algorithms.qda_solver; the C++ experiment entry point is Experiments/QDA

namespace qram_simulator

QRAM sparse state simulator namespace.

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

namespace QDA

Discrete adiabatic (QDA) linear-system solver.

namespace QDA_via_QRAM¶

QRAM-based QDA solver.

struct Walk_s_via_QRAM : public qram_simulator::QDA::Walk_s<Block_Encoding_via_QRAM, State_Prep_via_QRAM>¶

#include <qda_via_QRAM.h>

Standard single-step walk for the QRAM setting.

The matrix block encoding uses Block_Encoding_via_QRAM (qram_A), and the right-hand side encoding uses State_Prep_via_QRAM (qram_b, QRAM state preparation of a classical distribution)

Subclassed by qram_simulator::QDA::QDA_via_QRAM::Walk_s_via_QRAM_Debug

Public Types

using EncA = Block_Encoding_via_QRAM¶: Matrix block encoding type.

using Encb = State_Prep_via_QRAM¶: Right-hand side encoding type.

Public Functions

inline Walk_s_via_QRAM(qram_qutrit::QRAMCircuit *qram_A_, qram_qutrit::QRAMCircuit *qram_b_, std::string_view main_reg_, std::string_view anc_UA_, std::string_view anc_1_, std::string_view anc_2_, std::string_view anc_3_, std::string_view anc_4_, double s_, double kappa_, double p_, size_t dsz, size_t rsz)¶

Constructor.

Parameters:

qram_A_ – Pointer to the QRAM circuit of matrix A
qram_b_ – Pointer to the QRAM circuit of the right-hand side b
main_reg_ – Main register name
anc_UA_ – Block encoding ancilla register name
anc_1_ – Ancilla register 1 name
anc_2_ – Ancilla register 2 name
anc_3_ – Ancilla register 3 name
anc_4_ – Ancilla register 4 name
s_ – Interpolation parameter s ∈ [0, 1]
kappa_ – Condition number κ
p_ – Success probability parameter
dsz – Data register bit width
rsz – Rational register bit width

Public Members

qram_qutrit::QRAMCircuit *qram_A¶: Pointer to the QRAM circuit of matrix A.

qram_qutrit::QRAMCircuit *qram_b¶: Pointer to the QRAM circuit of the right-hand side b.

size_t data_size¶: Data register bit width.

size_t rational_size¶: Rational register bit width.

template<typename Encb_type> struct Walk_s_via_QRAM_A : public qram_simulator::QDA::Walk_s<Block_Encoding_via_QRAM, Encb_type>¶

#include <qda_via_QRAM.h>

Single-step walk for the QRAM setting (template version with customizable b encoding)

The matrix block encoding is fixed to Block_Encoding_via_QRAM (data from qram_A); the right-hand side encoding type is specified by the template parameter Encb_type

Template Parameters:: Encb_type – Encoding operator type of the right-hand side b

Public Types

using EncA = Block_Encoding_via_QRAM¶: Matrix block encoding type.

using Encb = Encb_type ¶: Right-hand side encoding type.

Public Functions

inline Walk_s_via_QRAM_A(qram_qutrit::QRAMCircuit *qram_A_, Encb_type encb_, std::string_view main_reg_, std::string_view anc_UA_, std::string_view anc_1_, std::string_view anc_2_, std::string_view anc_3_, std::string_view anc_4_, double s_, double kappa_, double p_, size_t dsz, size_t rsz)¶

Constructor.

Parameters:

qram_A_ – Pointer to the QRAM circuit of matrix A
encb_ – Right-hand side encoding operator instance
main_reg_ – Main register name
anc_UA_ – Block encoding ancilla register name
anc_1_ – Ancilla register 1 name
anc_2_ – Ancilla register 2 name
anc_3_ – Ancilla register 3 name
anc_4_ – Ancilla register 4 name
s_ – Interpolation parameter s ∈ [0, 1]
kappa_ – Condition number κ
p_ – Success probability parameter
dsz – Data register bit width
rsz – Rational register bit width

Public Members

qram_qutrit::QRAMCircuit *qram_A¶: Pointer to the QRAM circuit of matrix A (hierarchy tree data)

size_t data_size¶: Data register bit width.

size_t rational_size¶: Rational register bit width.

struct Walk_s_via_QRAM_Debug : public qram_simulator::QDA::QDA_via_QRAM::Walk_s_via_QRAM, public qram_simulator::QDA::QDADebugger ¶

#include <qda_via_QRAM.h>

Debug version of the QDA walk for the QRAM setting.

Extends Walk_s_via_QRAM with a QDADebugger: holds classical copies of the matrix/vector for fidelity comparison against the ideal intermediate eigenstate

Public Functions

inline Walk_s_via_QRAM_Debug(qram_qutrit::QRAMCircuit *qram_A_, qram_qutrit::QRAMCircuit *qram_b_, const DenseMatrix<double> &matrix_A_, const DenseVector<double> &vector_b_, std::string main_reg_, std::string anc_UA_, std::string anc_1_, std::string anc_2_, std::string anc_3_, std::string anc_4_, double s_, double kappa_, double p_, bool is_PD, size_t dsz, size_t rsz)¶

Constructor.

Parameters:

qram_A_ – Pointer to the QRAM circuit of matrix A
qram_b_ – Pointer to the QRAM circuit of the right-hand side b
matrix_A_ – Classical matrix copy (for fidelity comparison)
vector_b_ – Classical right-hand side copy (for fidelity comparison)
main_reg_ – Main register name
anc_UA_ – Block encoding ancilla register name
anc_1_ – Ancilla register 1 name
anc_2_ – Ancilla register 2 name
anc_3_ – Ancilla register 3 name
anc_4_ – Ancilla register 4 name
s_ – Interpolation parameter s ∈ [0, 1]
kappa_ – Condition number κ
p_ – Success probability parameter
is_PD – Whether the matrix is positive definite (selects the H(s) construction path)
dsz – Data register bit width
rsz – Rational register bit width

struct WalkSequence_via_QRAM_Debug¶

#include <qda_via_QRAM.h>

Complete solving sequence of QDA for the QRAM setting (debug driver)

Executes the single-step walk with s = n/steps step by step and clears zero-amplitude branches; every few steps, reads out the intermediate state with GetOutput and compares it against the ideal eigenstate (QDADebugger::get_mid_eigenstate) for fidelity, appending statistics such as progress/fidelity/maximum register size to the two files stdout_filename and fidelity_filename (the latter generated from the stdout filename by replacing “stdout” with “fidelity”)

Public Functions

inline WalkSequence_via_QRAM_Debug(qram_qutrit::QRAMCircuit *qram_A_, qram_qutrit::QRAMCircuit *qram_b_, const DenseMatrix<double> &matrix_A, const DenseVector<double> &vector_b, std::string main_reg_, std::string anc_UA_, std::string anc_1_, std::string anc_2_, std::string anc_3_, std::string anc_4_, size_t steps_, double kappa_, double p_, size_t dsz, size_t rsz, std::string stdout_filename_)¶

Constructor.

Parameters:

qram_A_ – Pointer to the QRAM circuit of matrix A
qram_b_ – Pointer to the QRAM circuit of the right-hand side b
matrix_A – Classical matrix copy
vector_b – Classical right-hand side copy
main_reg_ – Main register name
anc_UA_ – Block encoding ancilla register name
anc_1_ – Ancilla register 1 name
anc_2_ – Ancilla register 2 name
anc_3_ – Ancilla register 3 name
anc_4_ – Ancilla register 4 name
steps_ – Total number of discrete adiabatic steps
kappa_ – Condition number κ
p_ – Success probability parameter
dsz – Data register bit width
rsz – Rational register bit width
stdout_filename_ – Run-statistics output filename

template<typename Ty> inline void operator()(Ty &state)¶

Execute the complete discrete adiabatic sequence (forward)

Template Parameters:: Ty – State type
Parameters:: state – System state

template<typename Ty> inline void dag(Ty &state)¶

Execute the inverse (dagger) of the discrete adiabatic sequence.

Applies the dagger of each step’s walk in reverse order (s goes from 1 back to 0)

Template Parameters:: Ty – State type
Parameters:: state – System state

Public Members

size_t steps¶: Total number of discrete adiabatic steps.

double kappa¶: Condition number κ

double p¶: Success probability parameter.

std::string main_reg¶: Main register name.

std::string anc_UA¶: Block encoding ancilla register name.

std::string anc_1¶: Names of ancilla registers 1-4.

std::string anc_2¶

std::string anc_3¶

std::string anc_4¶

qram_qutrit::QRAMCircuit *qram_A¶: Pointer to the QRAM circuit of matrix A.

qram_qutrit::QRAMCircuit *qram_b¶: Pointer to the QRAM circuit of the right-hand side b.

DenseMatrix<double> matrix_A¶: Classical matrix copy (for fidelity comparison)

DenseVector<double> vector_b¶: Classical right-hand side copy (for fidelity comparison)

size_t data_size¶: Data register bit width.

size_t rational_size¶: Rational register bit width.

std::string stdout_filename¶: Run-statistics output filename (the fidelity filename is derived from it)

Discrete Adiabatic (DiscreteAdiabatic/)¶

QDA Fundamental Components (SparQ_Algorithm/include/DiscreteAdiabatic/qda_fundamental.h)¶

Tridiagonal QDA Solver (SparQ_Algorithm/include/DiscreteAdiabatic/qda_tridiagonal.h)¶

QRAM-Based QDA Solver (SparQ_Algorithm/include/DiscreteAdiabatic/qda_via_QRAM.h)¶

QDA Fundamental Components (`SparQ_Algorithm/include/DiscreteAdiabatic/qda_fundamental.h`)¶

Tridiagonal QDA Solver (`SparQ_Algorithm/include/DiscreteAdiabatic/qda_tridiagonal.h`)¶

QRAM-Based QDA Solver (`SparQ_Algorithm/include/DiscreteAdiabatic/qda_via_QRAM.h`)¶