Quantum linear systems

oracq.algorithms.qlss.qlss

Linear-system input contracts, the Costa walk, and the CKS Chebyshev solver.

class oracq.algorithms.qlss.qlss.SpectralPromise(norm_upper, sigma_min_lower, evidence='caller_declared_unverified')[source]

Bases: object

Matrix spectral bounds declared by the caller; the language does not verify the declarations.

Variables:

  • norm_upper (float) – Declared upper bound on the matrix norm.

  • sigma_min_lower (float) – Declared lower bound on the minimum singular value; must be positive and not exceed norm_upper.

  • evidence (str) – Marker for the source of the declaration; the default denotes an unverified caller declaration.

norm_upper
sigma_min_lower
evidence = 'caller_declared_unverified'
inverse_bound(alpha)[source]

Derive an upper spectral bound for the encoded inverse operator from the declared singular value lower bound.

Parameters:

alpha – Block-encoding normalization factor actually consumed.

Returns:

max(1, alpha / sigma_min_lower).

Return type:

float

Raises:

ValidationError – alpha is below the declared singular value lower bound.

class oracq.algorithms.qlss.qlss.SparseSystem(access, value_format, entry_bound, rhs, spectrum, diagonal_nonnegative=False, hermitian=False)[source]

Bases: object

Sparse Hermitian problem over finite element words and a shared RHS; matrix properties are caller-declared.

access
value_format
entry_bound
rhs
spectrum
diagonal_nonnegative = False
hermitian = False
class oracq.algorithms.qlss.qlss.BlockSystem(encoding, rhs, spectrum)[source]

Bases: object

Linear problem under the block-encoding input model.

Variables:
encoding
rhs
spectrum
property inverse_norm_bound

Inverse spectral bound max(1, alpha / sigma_min_lower) of the encoded matrix A/alpha.

class oracq.algorithms.qlss.qlss.LinearSystem(sparse=None, block=None, physical_width=None, physical_high_value=0, rhs_norm=None, data_assumptions=())[source]

Bases: object

Problem-layer linear system: exactly one source input model plus readout and norm declarations.

Variables:

  • sparse (oracq.algorithms.qlss.qlss.SparseSystem | None) – Sparse source input model; exactly one of this and block.

  • block (oracq.algorithms.qlss.qlss.BlockSystem | None) – Block-encoding source input model; exactly one of this and sparse.

  • physical_width (int | None) – Width of the low target bits occupied by the physical solution; omitted means full width.

  • physical_high_value (int) – Integer value that the discarded high bits must equal when selecting the physical subspace.

  • rhs_norm (float | None) – Classical right-hand side norm; the physical magnitude of the solution can only be recovered when provided.

  • data_assumptions (tuple[str, ...]) – Data assumptions recorded alongside the solve result.

sparse = None
block = None
physical_width = None
physical_high_value = 0
rhs_norm = None
data_assumptions = ()
block_input()[source]

Normalize the source input to a BlockSystem and report the adaptation trace.

Returns:

The block-encoding problem and a step-by-step adaptation description.

Return type:

tuple[BlockSystem, tuple[str, …]]

Raises:

ValidationError – The sparse source lacks a Hermitian declaration, so the CKS sparse adaptation cannot proceed.

class oracq.algorithms.qlss.qlss.SolveResult(state, norm_probe, input_alpha, encoded_inverse_bound, rhs_norm, adapter_trace, kernel_status='prototype; solver accuracy pending')[source]

Bases: object

Protocol solve output: the physical-subspace solution state, an independent norm probe, and provenance.

Variables:

  • state (oracq.algorithms.input_model.oracles.StateOracle) – Solution state oracle after selecting the physical subspace.

  • norm_probe (oracq.algorithms.input_model.oracles.StateOracle) – Norm probe oracle on the branch where the solve and matrix probes jointly succeed.

  • input_alpha (float) – Block-encoding normalization factor actually consumed by the solve.

  • encoded_inverse_bound (float) – Upper spectral bound of the encoded inverse operator.

  • rhs_norm (float | None) – Classical right-hand side norm; when missing, the physical magnitude of the solution cannot be recovered.

  • adapter_trace (tuple[str, ...]) – Record of adaptation steps from the source input to the kernel.

  • kernel_status (str) – Kernel maturity declaration.

state
norm_probe
input_alpha
encoded_inverse_bound
rhs_norm
adapter_trace
kernel_status = 'prototype; solver accuracy pending'
state_oracle()[source]

Return the StateOracle of the physical-subspace solution state.

Returns:

Readout handle of the physical-subspace solution state.

Return type:

StateOracle

property operation

The RIR Operation corresponding to the solution state.

recover_norm(solver_success, joint_matrix_success)[source]

Recover the norm of the solution vector from two success probabilities.

Parameters:

  • solver_success – Success probability of the solver probe alone.

  • joint_matrix_success – Joint success probability of the solver and matrix probes.

Returns:

The right-hand side norm divided by the product of input_alpha and the square root of the joint-to-standalone success probability ratio.

Return type:

float

Raises:

ValidationError – The classical right-hand side norm is missing, or the probability values or ordering are invalid.

class oracq.algorithms.qlss.qlss.QLSSSolver(name, input_model, kernel, legacy=None)[source]

Bases: object

Quantum linear-system protocol: contract validation, kernel dispatch, and assembly of a composable result.

Variables:
provides = (<class 'oracq.algorithms.input_model.interfaces.StateOracleProtocol'>,)
name
input_model
kernel
legacy = None
property contract

Return the AlgorithmContract for A and b according to the input model.

The sparse model accepts only sparse oracles; the block-encoding model accepts both block-encoding and sparse interfaces. A and b must have the same width; spectral bounds and the matrix interpretation are caller-declared.

check(problem)[source]

Run neither the kernel nor the adapters; produce a full report on structure, capabilities, and required adaptations.

Parameters:

problem – The linear-system problem to check; the valid type is LinearSystem.

Returns:

A contract report summarizing the input type, a zero right-hand side, spectral declaration conflicts, and the required adaptation steps.

Return type:

ContractReport

solve(problem)[source]

Solve a LinearSystem and assemble the SolveResult.

The contract check runs first, then the source input goes to the kernel according to input_model; afterwards the physical subspace is selected, protocol provenance attributes are written, and the independent matrix norm probe is assembled.

Parameters:

problem – The linear system to solve.

Returns:

The solution state, norm probe, and provenance.

Return type:

SolveResult

Raises:

ValidationError – The contract is not satisfied, the right-hand side is zero, the kernel output is invalid, or widths mismatch.

oracq.algorithms.qlss.qlss.QLSSProtocol

alias of QLSSSolver

class oracq.algorithms.qlss.qlss.CostaConfig(steps=2, kappa=4.0, schedule_power=1.5, filter_degree=2, filter_attenuation=0.2)[source]

Bases: object

Schedule and Dolph–Chebyshev filter configuration for the Costa parameterized quantum walk.

kappa is the inverse spectral bound of the actually encoded matrix A/alpha, not cond(A) at an arbitrary scale; the problem layer overrides it automatically using the system’s inverse_norm_bound.

Variables:

  • steps (int) – Number of chained walk steps; step i takes the schedule point (i+1)/steps.

  • kappa (float) – Inverse spectral bound of the encoded matrix A/alpha, i.e. the assumption sigma_min(A/alpha) >= 1/kappa; at least 1.

  • schedule_power (float) – Exponent of the interpolation schedule; cannot equal 1.

  • filter_degree (int) – Degree of the Dolph–Chebyshev filter; an even number of at least 2.

  • filter_attenuation (float) – Sidelobe level of the filter; smaller means stronger stopband suppression; lies strictly between 0 and 1.

steps = 2
kappa = 4.0
schedule_power = 1.5
filter_degree = 2
filter_attenuation = 0.2
class oracq.algorithms.qlss.qlss.FilterPlan(weights, stride=1, offset=0, method='explicit')[source]

Bases: object

LCU description of a Laurent polynomial filter over walk powers.

Variables:

  • weights (tuple[float, ...]) – LCU weights for each walk power.

  • stride (int) – Power spacing between adjacent terms; at least 1.

  • offset (int) – Starting power; when negative, inverse powers are realized via the adjoint.

  • method (str) – Construction method marker.

weights
stride = 1
offset = 0
method = 'explicit'
oracq.algorithms.qlss.qlss.dolph_chebyshev_plan(degree=2, attenuation=0.2)[source]

Construct an even-degree Dolph–Chebyshev LCU via Laurent polynomial recursion.

Parameters:

  • degree – Filter degree; an even number of at least 2.

  • attenuation – Stopband attenuation, in (0,1).

Returns:

A walk-power filter plan starting at power −degree with power spacing 2.

Return type:

FilterPlan

oracq.algorithms.qlss.qlss.schedule(s, kappa, power=1.5)[source]

Evaluate the Costa interpolation schedule at schedule point s.

Parameters:

  • s – Schedule point, between 0 and 1.

  • kappa – Inverse spectral bound of the encoded matrix; at least 1.

  • power – Schedule exponent; cannot equal 1.

Returns:

The interpolation parameter f(s); degenerates to s when kappa is 1.

Return type:

float

Raises:

ValidationError – kappa is below 1, power equals 1, or s is out of range.

oracq.algorithms.qlss.qlss.costa_walk(a, bprep, fs)[source]

Assemble the single-step operator of the Costa parameterized quantum walk.

It builds in order the RHS zero-state reflection, the schedule rotation, and the controlled forward and inverse block-encoding invocations, and finishes with a positive reflection on all signal bits.

Parameters:

  • a – Block encoding of the matrix A.

  • bprep – State preparation of the right-hand side b, with the same width as a.

  • fs – Interpolation parameter at the schedule point, between 0 and 1.

Returns:

The walk operator with a target/signal interface; signal consists of the BE signal bits, the RHS work bits, and four walk ancilla bits, in that order.

Return type:

Operation

Raises:

ValidationError – The input contract is not satisfied, widths mismatch, or the schedule point is out of range.

oracq.algorithms.qlss.qlss.unary_weight_preparation(weights)[source]

Prepare an LCU weight superposition over a unary prefix chain.

Parameters:

weights – Weight sequence; entries are non-negative, the sum is positive, and there are at least two entries.

Returns:

A zero-input state preparation on the target register; the prefix state with the first k bits one and the rest zero has probability proportional to weights[k].

Return type:

Operation

Raises:

ValidationError – The weights are empty, contain negative or non-finite values, sum to zero, or number fewer than two.

oracq.algorithms.qlss.qlss.lcu_filter(walk, plan)[source]

Coherently superpose a Laurent polynomial filter over walk powers.

The weight plan.weights[k] acts on walk power plan.offset + k * plan.stride; negative powers are realized via the adjoint of the walk operator.

Parameters:

  • walk – Walk operator exposing only a target/signal interface.

  • plan – Weight and power configuration of the polynomial.

Returns:

A target/signal interface; signal appends clock bits beyond the walk signal bits.

Return type:

Operation

Raises:

ValidationError – The walk register interface does not match, or the filter power configuration is invalid.

oracq.algorithms.qlss.qlss.costa_qlss(a, bprep, config=None, *, filtering=None)[source]

Costa walk solve kernel: prepare the RHS, chain the walks at each schedule point, and apply the filter.

Parameters:

  • a – Block encoding of the matrix A.

  • bprep – State preparation of the right-hand side b, with the same width as a.

  • config – Walk schedule and filter configuration; defaults to the CostaConfig defaults when omitted.

  • filtering – Explicit filter plan; when omitted, a Dolph–Chebyshev plan is generated from the configuration.

Returns:

The solve circuit; the success condition is all-zero signal, with probability and accuracy unverified.

Return type:

StateOracle

Raises:

ValidationError – steps is not a positive integer, or validation of an underlying building block failed.

oracq.algorithms.qlss.qlss.make_costa_qlss(config=None)[source]

Declare BE input; the problem layer automatically derives the actual schedule parameters from alpha/sigma_min.

Parameters:

config – Costa walk solve configuration; defaults to the default configuration.

Returns:

The Costa solve protocol under the block-encoding input model, with a two-argument legacy entry.

Return type:

QLSSSolver

class oracq.algorithms.qlss.qlss.CKSConfig(order=2, terms=None)[source]

Bases: object

Truncation configuration of the CKS basic Chebyshev inverse-operator expansion.

Variables:

  • order (int) – Order of the Chebyshev expansion, in the range 1..128.

  • terms (int | None) – Number of truncated terms actually kept; defaults to order when omitted.

order = 2
terms = None
coefficients()[source]

Compute the LCU weights of the truncated Chebyshev expansion of 1/x.

Returns:

The truncated coefficient sequence; term j pairs with the odd power T_(2j+1).

Return type:

tuple[float, …]

Raises:

ValidationError – order is outside 1..128, or the truncation term count is invalid.

oracq.algorithms.qlss.qlss.cks_chebyshev(system, config=None)[source]

CKS basic Chebyshev solve kernel, accepting the sparse Hermitian input model.

It applies the truncated Chebyshev expansion of 1/x to the sparse block encoding, then applies the inverse-operator LCU to the RHS preparation.

Parameters:

  • system – The sparse Hermitian linear system described by a SparseSystem.

  • config – Expansion order and truncation configuration; defaults to the CKSConfig defaults when omitted.

Returns:

The solve circuit; basic LCU only, without VTAA, with prototype-level accuracy claims.

Return type:

StateOracle

Raises:

ValidationError – The input lacks a Hermitian declaration.

oracq.algorithms.qlss.qlss.make_cks_qlss(config=None)[source]

Construct the CKS solve protocol for sparse input.

Parameters:

config – The CKSConfig passed to the kernel; defaults when omitted.

Returns:

A solve protocol with input_model sparse.

Return type:

QLSSSolver