离散绝热（DiscreteAdiabatic/）

QDA 基础组件（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|)

参数:

b -- Normalized right-hand side vector

模板参数:

Ty -- Eigen vector expression type

返回:

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.

参数:

  • A -- Original matrix

  • fs -- Interpolation parameter f(s)

模板参数:

Ty -- Eigen matrix expression type

返回:

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)

参数:

  • A -- Original matrix

  • fs -- Interpolation parameter f(s)

  • b -- Normalized right-hand side vector

模板参数:

  • Ty1 -- Eigen matrix expression type

  • Ty2 -- Eigen vector expression type

返回:

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.

参数:

coeffs -- List of nonnegative coefficients

抛出:

Throws -- an exception when a coefficient is negative

返回:

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)

参数:

  • n -- Polynomial order

  • x -- Input value

返回:

T_n(x)

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

Compute the Dolph-Chebyshev window function value.

参数:

  • epsilon_ -- Error tolerance ε

  • l_ -- Window length parameter l

  • phi_ -- Phase angle φ

返回:

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

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

Evaluate an even-function Fourier series.

参数:

  • weights -- Coefficient list (w_0 is the constant term)

  • x -- Evaluation point

返回:

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.

参数:

  • epsilon_ -- Error tolerance ε

  • l_ -- Filter length parameter l

返回:

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)

参数:

  • 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

模板参数:

  • Block_Encoding -- Block encoding type of A

  • State_Prep -- State preparation type of |b⟩

  • StateType -- State container type (default SparseState)

返回:

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)

参数:

  • 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

模板参数:

  • Block_Encoding -- Block encoding type of A

  • State_Prep -- State preparation type of |b⟩

返回:

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)

参数:

  • 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

模板参数:

  • Block_Encoding -- Block encoding type of A

  • State_Prep -- State preparation type of |b⟩

  • StateType -- State container type (default SparseState)

返回:

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)

参数:

  • 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

模板参数:

  • Block_Encoding -- Block encoding type of A

  • State_Prep -- State preparation type of |b⟩

返回:

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)

模板参数:

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

参数:

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

参数:

state -- System state vector

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

Block encoding circuit implementation (dagger, inverse)

备注

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

参数:

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)

模板参数:

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

参数:

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

参数:

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)

模板参数:

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.

参数:

  • 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

参数:

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

参数:

state -- System state vector

返回:

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

参数:

  • 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})

参数:

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

参数:

state -- System state vector

返回:

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

参数:

state -- Sparse state

返回:

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

备注

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

参数:

state -- System state vector

返回:

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.

参数:

state -- System state vector

返回:

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

模板参数:

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)

参数:

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

参数:

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

参数:

state -- System state vector

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

Execute the LCU combination (dagger, inverse)

参数:

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

参数:

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

返回:

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

DenseVector<double> get_vector_0b()

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

返回:

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)

返回:

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)

Returns the initial state |0⟩⊗|b⟩ when f(s) ≈ 0; returns the normalized solution of A x = b (placed in the |1⟩ branch) when f(s) ≈ 1; otherwise solves A_f y = (|0⟩⊗|b⟩) and returns its normalized solution as the intermediate eigenstate

参数:

is_PD -- Whether this is the positive-definite case (unused in the current implementation)

返回:

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)

备注

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)

模板参数:

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

参数:

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

参数:

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†

参数:

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)

三对角 QDA 求解器（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.

参数:

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

参数:

  • 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 的 QDA 求解器（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.

参数:

  • 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

模板参数:

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.

参数:

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

参数:

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

参数:

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

模板参数:

Ty -- State type

参数:

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)

模板参数:

Ty -- State type

参数:

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)