Quantum algorithm coverage workboard¶

English · 简体中文

This document tracks oracq’s quantum-algorithm implementation coverage relative to the open-source ecosystem, ordering implementation by the principle of “input-model degrees of freedom first”. Core principle: algorithms are decoupled from input models — one algorithm definition serves several input models (the abstract / gate / qram layers) through open declarations and batched binding.

Input model vocabulary¶

Abbreviation	Input model	Repository location
SP	State preparation / amplitude encoding	`algorithms/oracles.py` StatePreparation (gate/qram)
QRAM	QRAM/QROM data lookup	`infrastructure/ir.py` Load, `oracles.py` XorDatabase/banked
SO	Sparse-matrix oracle (position + element separated)	`oracles.py` SparseAccess
BE	Block encoding / LCU	`algorithms/operators.py`, `block_encoding.py`
UO	Unitary-operator oracle (controlled U)	`interfaces.py` UnitaryProtocol
HAM	Hamiltonian representation (Pauli/sparse/low-rank)	`algorithms/hamiltonian.py`
FO	Function oracle (phase/amplitude/Boolean)	`infrastructure/mathfunc/`, `oracles.py`
CP	Direct parameterization by classical data (QUBO, variational parameters)	`algorithms/variational.py` etc.
ODE	Differential-equation input (access model for A + initial state + b)	`algorithms/ode_models.py`, `ode.py`, `qham.py`
DM	Density matrix / Gibbs state	Not implemented
EST	Sampling/measurement access (shadows, tomography)	Not implemented

Workboard¶

Status: ✅ implemented; 🚧 in progress; 📄 candidate paper (no reliable open-source implementation, or worth rewriting with this repository’s abstractions).

Class A: frameworks explicitly decoupling algorithms from input models (highest priority)¶

Entry	Algorithm	Input model	Status	Notes
A1	QSVT standard-transform library: phase synthesis (parity decomposition), fixed-point search, matrix inversion/sign function, eigenstate filtering, Hamiltonian-simulation phases	BE	✅	Gilyén et al. 2019; implemented in `algorithms/qsvt.py`, assembled on the `transforms.py` sequence skeleton
A2	PREPARE–SELECT standard decomposition: independent prepare/select oracles, coefficients bound via gate/QRAM/alias, wired through to the qubitization walk	BE/HAM	✅	Low–Chuang 2019, Babbush et al. 2018; implemented in `algorithms/prepare_select.py`, including alias sampling
A3	Quantum-walk framework: graph-oracle input model, Szegedy/MNRS marked-vertex search frameworks	FO (adjacency oracle)	✅	MNRS 2011; implemented in `algorithms/graph_walks.py`, including the three-layer adjacency oracle and hitting-time tools
—	Element distinctness / collision finding	FO	📄	Ambainis; depends on the A3 framework + Johnson-graph walks (needs nonuniform setup and extra data registers)
—	Non-Abelian HSP	FO	📄	High mathematical barrier, deferred

Class B: new input models opening new algorithm families¶

Entry	Algorithm	Input model	Status	Notes
B1	Gibbs/thermal-state preparation, quantum Metropolis	DM + HAM	✅	Implemented in `algorithms/density.py`: the three-layer purification-access paradigm + Gibbs preparation via the QSVT purification route (the DM input model is established)
B2	Quantum SDP / convex optimization (Brandão–Svore, van Apeldoorn–Gilyén)	DM/BE	✅	Implemented in `algorithms/qsdp.py`: trace-estimation probe circuits + MMW driving + per-round quantum-subroutine generation
B3	Heinrich quantum summation/integration	FO + QRAM	✅	Implemented in `algorithms/integration.py`: comparator linear readout + QAE, cross-checked across the three binding layers
B4	Jordan gradient estimation	FO (probabilistic oracle)	✅	Implemented in `algorithms/gradient.py`: three-layer phase oracle + single-query d-component readout
B5	Alias-sampling state preparation, Select-Swap QROM	CP→SP / QRAM	✅	Alias in `prepare_select.py`; Select-Swap implemented in `algorithms/data_loading.py` (with the `qrom_cost` resource cross-check)

Class C: algorithms that this repository’s abstraction level can rewrite more correctly¶

Entry	Algorithm	Input model	Status	Notes
C1	Quantum-chemistry low-rank decomposition (DF/THC/SF → LCU → BE)	HAM (low-rank tensors) → BE	✅	Implemented in `algorithms/lowrank.py`: DF (two-level synthetic rotations + controlled-rotation diagonal encoding) and THC; the products can feed qubitization_walk
C2	Recent nonlinear/stochastic ODE advances (Fokker–Planck, SDE)	ODE	✅	Implemented in `algorithms/sde.py`: conservative-form FP discretization feeding the QODEProblem contract, with analytic OU-moment cross-checks
C3	DQI (decoding quantum interferometry optimization)	CP (encoding constraints)	✅	Implemented in `algorithms/dqi.py`: Dicke states + open decoder declarations, with pointwise distribution cross-checks against Krawtchouk closed forms
C4	QRAM-based QML (QPCA, recommendation systems)	QRAM + SP	✅	QPCA implemented in `algorithms/qpca.py`: LMR density-matrix exponentiation + QPE, with a first-order convergence-rate witness; recommendation systems deferred

Implemented baseline (cross-check catalog in `applications/catalog.py`)¶

Area	Algorithms
Oracle/search/estimation	Deutsch–Jozsa, Bernstein–Vazirani, Simon, Grover, amplitude amplification, QAE/quantum counting, QPE, Hadamard/SWAP test
Fourier/number theory	QFT, QFT addition, modular multiplication, order finding
Simulation	Trotter, Taylorization, qubitization walk, QSVT sequence skeleton, OAA
Linear systems	CKS (Chebyshev), Costa (discrete adiabatic walk), the CKS §5 VTAA variable-time solver
Differential equations	LCHS, CBMD, Schrödingerization, Carleman, Euler history states, structured FD, QHAM, QFVM
Other	Variational (QAOA-MaxCut/VQE), repetition-code error correction, fixed-point arithmetic, mathfunc front end

Maintenance rules¶

New algorithms go into the matching category file; do not write legacy-import compatibility layers; register names, bit widths, and views are preserved down to backend lowering.
When editing this workboard, update the status column in sync; once an algorithm is implemented, note the implementation file on its row.
Criteria for picking new papers: the paper defines its input oracles explicitly; it can be transcribed mechanically into the protocol-contract system; its correctness can be endorsed by the contracts checks.
Per-algorithm implementation and validation details live on the algorithm pages; update the corresponding pages when editing the workboard.