量子半定规划框架

oracq.algorithms.qml.qsdp

Quantum semidefinite programming (QSDP) framework: Gibbs sampling plus trace estimation plus a matrix multiplicative weights outer loop.

The structure follows Brandão–Svore 2017 ("Quantum speed-ups for semidefinite programming", FOCS) and van Apeldoorn–Gilyén 2019: the solution of a feasibility SDP is approached by matrix multiplicative weights (MMW) iterations, and the key quantum subroutines of each round are (a) Gibbs state preparation of the penalty Hamiltonian (reusing the QSVT purification route of density.gibbs_purification) and (b) trace estimation Tr(A_i ρ) for the observables A_i (a Hadamard-type probe circuit over the purified state plus a block encoding).

The outer MMW driver is classical (consistent with the QSDP papers; the quantum speedup lies exactly in the two inner primitives, Gibbs preparation and trace estimation); the driver consumes Tr(A_i ρ) through an estimator callback, defaulting to the classical reference implementation of density.gibbs_state so small instances can be cross-checked, while the quantum path is generated round by round by iteration_circuits.

oracq.algorithms.qml.qsdp.trace_estimate_circuit(purification, observable, *, component='real', name=None)

Probe estimation circuit for Tr(M ρ)/α: a controlled invocation of the block encoding on the purified state (Hadamard test structure).

The Z expectation of probe equals Re/Im⟨ψ_ρ| (M/α ⊗ I) |ψ_ρ⟩; Tr(M ρ) is decoded by trace_from_probe. The environment register is a bystander only (tracing it out yields ρ), the block encoding signal joins the invocation from all zeros, and the circuit performs no measurement. purification may also be an ApproximatePurification (approximate purification): the purified state then lives only on its signal == 0 branch, the probe readout must be conditioned on that branch, and decoding uses trace_from_joint.

参数:

• purification -- Purification access handle of the Gibbs state; its system width must match the observable.

• observable -- Block encoding of the observable M.

• component -- Component to read, real or imag.

• name -- Name of the generated module; generated automatically by default.

返回:

Trace estimation probe circuit read out from the probe register, without performing any measurement.

返回类型:

Operation

oracq.algorithms.qml.qsdp.trace_from_probe(probability_one, alpha)

Decode Tr(M ρ) from the probability of measuring 1 on probe: the Z expectation is 1 − 2p, multiplied by the block encoding α.

参数:

• probability_one -- Probability of measuring 1 on probe, in [0,1].

• alpha -- Scale α of the observable block encoding, a positive real.

返回:

Estimate of Tr(M ρ).

返回类型:

float

oracq.algorithms.qml.qsdp.trace_from_joint(probe_expectation_joint, weight_signal_zero, alpha)

Decoding for the approximate purification path: Tr(M ρ) = α · E[Z_probe·1_{signal=0}] / P(signal=0).

probe_expectation_joint is the joint expectation of the probe Z expectation and the purification signal == 0 indicator, and weight_signal_zero is the probability of the purification signal == 0 branch.

参数:

• probe_expectation_joint -- Joint expectation of the probe Z expectation and the signal==0 indicator.

• weight_signal_zero -- Probability of the purification signal==0 branch, a positive real.

• alpha -- Scale α of the observable block encoding, a positive real.

返回:

Estimate of Tr(M ρ) conditioned on the successful branch.

返回类型:

float

class oracq.algorithms.qml.qsdp.SdpInstance(constraints)

基类：object

Feasibility SDP input model: find X ⪰ 0 with Tr X = 1 such that |Tr(A_i X) − b_i| ≤ ε.

constraints is a sequence of (A_i, b_i) pairs: A_i is an explicit small Hermitian matrix and b_i is a real number. The explicit-matrix path targets small instances; at scale, A_i should be replaced by a sparse-access or block-encoding access model, and the block encoding assembly of the penalty Hamiltonian is replaced accordingly (see the parameters of iteration_circuits).

constraints

property width

Number of system qubits.

property num_constraints

Number of constraints m, i.e. the number of (A_i, b_i) pairs in constraints.

oracq.algorithms.qml.qsdp.penalty_hamiltonian(instance, weights)

MMW penalty Hamiltonian H = Σ_i w_i (A_i − b_i I) (explicit small matrix).

参数:

• instance -- Feasibility SDP input model providing the (A_i, b_i) constraints.

• weights -- Weight sequence in one-to-one correspondence with the constraints, of length equal to the number of constraints.

返回:

The penalty matrix as row-nested tuples.

返回类型:

tuple[tuple[complex, ...], ...]

oracq.algorithms.qml.qsdp.classical_estimator(hamiltonian_matrix, beta, instance)

Classical reference estimation: compute all Tr(A_i ρ) from an explicit Gibbs state (for cross-checks and as the driver default).

Returns (rho, estimates): rho is the density matrix (nested tuples) and estimates are the traces of the constraints.

参数:

• hamiltonian_matrix -- Explicit Hermitian penalty matrix.

• beta -- Inverse temperature of the Gibbs distribution, a positive real.

• instance -- SDP input model providing the (A_i, b_i) constraint sequence.

返回:

(the Gibbs density matrix ρ, the sequence of trace estimates per constraint).

返回类型:

tuple[tuple[tuple[complex, ...], ...], tuple[float, ...]]

oracq.algorithms.qml.qsdp.qsdp_gibbs_solve(instance, *, epsilon, max_iterations=None, estimator=None)

Matrix multiplicative weights (MMW) feasibility solving: Hedge iterations for the symmetric zero-sum game min_X max_w Σ_i w_i v_i.

The constraint semantics are one-sided inequalities Tr(A_i X) ≤ b_i (violation v_i = Tr(A_i ρ) − b_i, only positive violations are penalized); an equality constraint should be split into the two inequalities (A_i, b_i) and (−A_i, −b_i). Each round: the Gibbs state ρ_t of the penalty Hamiltonian H_t = Σ_i w_i (A_i − b_i I), the constraint violations v_i = Tr(A_i ρ_t) − b_i, and the weights updated as w_i ∝ exp(η·v_i). The maximum violation of the averaged iterate ρ̄ decreases as O(√(ln m / T)) (the structure of Brandão–Svore 2017; the quantum speedup lies in the two inner primitives of Gibbs preparation and trace estimation, and the classical loop of this driver matches the papers).

参数:

• instance -- SdpInstance.

• epsilon -- Target violation bound; the learning rate is η = ε/4.

• max_iterations -- Iteration cap, defaulting to ceil(64·ln(m+1)/ε²); stops early once the maximum violation of the averaged iterate is ≤ epsilon.

• estimator -- Callback (hamiltonian_matrix, beta, instance) -> (rho, estimates), defaulting to classical_estimator; the quantum path should pass an estimator built on iteration_circuits.

返回:

rho (the averaged iterate, nested tuples), violations (final violations), iterations, and converged (maximum violation ≤ epsilon).

返回类型:

dict

oracq.algorithms.qml.qsdp.iteration_circuits(instance, weights, beta, *, hamiltonian_encoding, error=0.05)

Generate the quantum subroutines of a single MMW round: Gibbs purification plus a trace estimation circuit per constraint.

hamiltonian_encoding is a callable that encodes the explicit penalty matrix into a block encoding (matrix_pauli_encoding works for small instances; switch to a sparse-access or low-rank access model at scale). Returns (ApproximatePurification, [trace_estimate Operation, ...]) for the quantum path's estimator to invoke round by round.

参数:

• instance -- Feasibility SDP input model providing the (A_i, b_i) constraints.

• weights -- Constraint weight sequence for this round, of length equal to the number of constraints.

• beta -- Inverse temperature of the Gibbs purification, a positive real.

• hamiltonian_encoding -- Callback that encodes the explicit penalty matrix into a block encoding.

• error -- Purification approximation error, a positive real.

返回:

The Gibbs purification handle and the list of trace estimation circuits per constraint.

返回类型:

tuple[ApproximatePurification, list[Operation]]