VTAA-CKS 变时线性系统求解器

oracq.algorithms.qlss.vtaa_cks

CKS section 5 VTAA linear-system solver: GPE clock, banded inverse LCU, and variable-time amplitude amplification.

Based on Childs–Kothari–Somma (arXiv:1511.02306 §5, SIAM J. Comput. 2017). Variable-time layer structure: the clock bits C_j are written by gapped phase estimation (Lemma 22), which controlled-triggers the banded Chebyshev inverse LCU (Lemma 23, including the alpha_max uniformization rotation of eq. (98)); the outer layer applies the clock-aware nested amplification of Ambainis (arXiv:1010.4458) (operator form taken from Low–Su arXiv:2410.18178 eq. (47)–(53)); finally the GPE garbage is erased with the inverse of A' (eq. (99)–(112)).

The GPE decision follows the deterministic route of Low–Su Prop 23: a Yoder–Low–Chuang fixed-point decision polynomial (reusing the verified synthesis of qsvt.fixed_point_search_phases) is applied to the qubitization walk, and the decision bit is flipped on the signal==0 branch: when the magnitude of lambda is at least theta_j the decision is 1 (fire, hard bound epsilon) with amplitude near 1, while at x=0 the decision is 0; the transition band response is deterministic and exactly computable. The query count O((alpha/theta_j) log(1/eps)) is of the same order as the PEA plus majority vote of CKS Lemma 22; the P_j garbage is kept as in the paper and erased by the inverse of A'. No public implementation of VTAA or CKS §5 was available before this one.

oracq.algorithms.qlss.vtaa_cks.gpe_fire_phases(threshold, x_edge, epsilon, degree_cap=40, *, synthesizer=None)

GPE fire decision phases: YLC fixed-point polynomial with |P| >= 1-epsilon when |x| >= threshold.

The threshold decreases monotonically with degree; odd degrees from 3 upward are searched until the [threshold, x_edge] grid validation passes; at x=0, P=0, and the response over the transition band (0, threshold) is deterministic and exactly computable (a band CKS makes no promise about).

参数:

• threshold -- Fire decision threshold (encoded spectral units), in (0, x_edge].

• x_edge -- Right end of the validation grid, in [threshold, 1].

• epsilon -- Hard bound on the decision response, in (0,1).

• degree_cap -- Search cap for the decision polynomial degree; odd degrees from 3 upward are searched.

• synthesizer -- Optional replacement for the bundled YLC phase synthesis route (pinned-completion mode; the exact P_S identity still applies).

返回:

The grid-validated QSP phase sequence and the actual degree.

返回类型:

tuple[tuple[float, ...], int]

oracq.algorithms.qlss.vtaa_cks.clock_or_operation(width)

Clock-prefix OR predicate: the coherent criterion for stopped<=j, used by the VTAA reflections.

参数:

width -- Number of bits in the clock prefix; a positive integer.

返回:

A Boolean-circuit operation writing the OR of the prefix bits into the 1-bit stopped register.

返回类型:

Operation

oracq.algorithms.qlss.vtaa_cks.gapped_phase_estimation(a, threshold, x_edge, *, epsilon=0.02, degree_cap=40, synthesizer=None)

GPE of CKS Lemma 22 (deterministic QSP route, Low–Su arXiv:2410.18178 Prop 23).

Applies the YLC fixed-point decision polynomial P(lambda/alpha) to the qubitization walk of the BE and flips the decision bit on the signal==0 branch: when |lambda/alpha| >= threshold (fire hard bound epsilon) the decision is 1 with amplitude near 1 (stop in this band and invert), while at the low end of the spectrum the decision tends to 0 (deferred to a finer band). The signal register keeps gamma garbage (P_j of the paper §5.2), erased at the end by the inverse of A'.

参数:

• a -- Hermitian BE of the self-adjoint unitary dilation.

• threshold -- Fire decision threshold (encoded spectral units, i.e. relative to alpha).

• x_edge -- Spectral upper bound divided by alpha; right end of the validation grid.

• epsilon -- Hard bound on the fire-side decision response.

• degree_cap -- Cap on the decision polynomial degree.

• synthesizer -- Optional replacement for the bundled YLC phase synthesis route.

返回:

Registers target/signal/decision; decision=1 means stopping in this band.

返回类型:

Operation

oracq.algorithms.qlss.vtaa_cks.band_inverse_step(a, coefficients, alpha_max)

W(lambda, delta) of CKS Lemma 23: banded Chebyshev inverse LCU plus uniformization rotation.

参数:

• a -- BE of the self-adjoint unitary dilation; chebyshev_block provides the odd Chebyshev powers.

• coefficients -- Truncated inverse polynomial coefficients c_k of this band (T_{2k+1} basis).

• alpha_max -- Maximum LCU 1-norm over all bands; eq. (98) uniformly scales the success amplitude down to 1/alpha_max.

返回:

Registers target/signal/flag; the branch with signal==0 and flag==1 carries h(A)psi/alpha_max (psi being the input state), where h is this band's polynomial.

返回类型:

Operation

class oracq.algorithms.qlss.vtaa_cks.VTAAConfig(order=2, terms=None, clock_steps=None, marker_epsilon=0.02, degree_cap=40, rounds=None)

基类：object

order is the base Chebyshev degree of band 1; band j scales it geometrically by 2^(j-1).

rounds holds the VTAA amplification rounds r_j per stage (None means all zero, i.e. the pure variable-time layer plus postselection); correctness does not depend on the schedule, which only affects the success rate. Production deployments should choose r_j via the amplitude estimation of Ambainis Algorithm 2 or the deterministic schedule of Low–Su (see tunable_rounds).

order = 2

terms = None

clock_steps = None

marker_epsilon = 0.02

degree_cap = 40

rounds = None

band_order(step)

Return the Chebyshev inverse polynomial degree of band step.

Band 1 takes order and each subsequent band doubles it (geometric growth in powers of 2), capped at 128; step below 1 is treated as band 1.

参数:

step -- Band index, counting from 1.

返回:

The Chebyshev degree of that band, at most 128.

返回类型:

int

band_coefficients(step)

Return the truncated inverse polynomial coefficients of band step (T_{2k+1} basis).

Computed via CKSConfig.coefficients with degree band_order(step) and truncation term count terms (None means the full degree).

参数:

step -- Band index, counting from 1.

返回:

The truncated inverse polynomial coefficient sequence on the odd Chebyshev basis.

返回类型:

tuple[float, ...]

oracq.algorithms.qlss.vtaa_cks.tunable_rounds(stage_amplitudes, thresholds=None)

Low–Su tunable VTAA schedule (arXiv:2410.18178 eq. (52)–(53)).

参数:

• stage_amplitudes -- Estimates of the "not yet failed" amplitude norms x_j per stage (obtainable via the amplitude estimation channel).

• thresholds -- Thresholds alpha_j, uniformly split by default; their sum is constant to guarantee constant loss.

返回:

A tuple of per-stage rounds r_j = max(ceil(sqrt(alpha_j)/(6 x_j) - 1/2), 0), satisfying the no-overshoot condition (2 r_j + 1) x_j <= sqrt(alpha_j).

oracq.algorithms.qlss.vtaa_cks.vtaa_cks(system, config=None, *, synthesizer=None)

CKS §5 VTAA solve kernel; takes a SparseSystem and returns the solution StateOracle.

参数:

• system -- Sparse Hermitian linear system; must carry Hermitian and spectral bound declarations.

• config -- VTAA configuration; defaults to the default configuration.

• synthesizer -- Optional replacement for the bundled QSP phase synthesis route used by the GPE decision markers.

返回:

The solution state oracle output by the variable-time amplification cascade, with correctness marked pending.

返回类型:

StateOracle

oracq.algorithms.qlss.vtaa_cks.make_vtaa_cks_qlss(config=None, *, synthesizer=None)

CKS §5 VTAA solve protocol; the input model is the same sparse access as cks_chebyshev.

参数:

• config -- VTAA configuration; defaults to the default configuration.

• synthesizer -- Optional replacement for the bundled QSP phase synthesis route used by the GPE decision markers.

返回:

The VTAA solve protocol under the sparse input model.

返回类型:

QLSSProtocol