Algorithm catalog

English · 简体中文

The algorithm library is organized into ten subpackages by purpose: input_model (input models and data access), common (shared primitives), qlss (linear systems), qnlss (nonlinear systems), qode (ordinary differential equations), qpde (partial differential equations), qml (quantum machine learning), optimization (quantum optimization and variational methods), basics (basic example algorithms), and qec (quantum error correction). The table below lists the entry files, what is implemented, and the boundaries to keep in mind when using them. The API reference lists the full signatures; the per-algorithm pages are grouped by family — see the navigation below.

Subpackage	File	Implementation and scope
input_model	contracts.py	Checkable input contracts: oracle capabilities/specifications, protocol contracts, and acceptance reports
input_model	operators.py	BlockEncoding class and basic compositions such as identity/product/scale/LCU
input_model	oracles.py	The four oracle paradigms XorDatabase, StatePreparation, StateOracle, SparseAccess and the abstract/gate/qram factories
input_model	interfaces.py	Shared protocols such as StatePreparation/Unitary/BlockEncoding and adaptation functions
input_model	block_encoding.py	Block-encoding algebraic composition: tensor, direct_sum, projector, lcu, pauli_word, and more
input_model	sparse.py	Adaptation from sparse access to block encodings, including the Chebyshev block and reversible table lookup
input_model	spectral.py	Spectral diagonal block encodings, sparse spectral block encodings, and spectral state preparation
input_model	lowrank.py	Quantum-chemistry low-rank decomposition (DF/THC) Hamiltonian LCU/block encodings
input_model	data_loading.py	Select-Swap QROM data loading and its cost model
input_model	qdata.py	QVector/QMatrix quantum data structures (squared-norm trees and sample-and-query)
input_model	density.py	Density-matrix purification access, Gibbs state preparation, and classical tools such as trace distance
input_model	qham.py	Constructing QODE inputs from finite HAM closures and the physical output channel
input_model	graph_walks.py	Graph-oracle input models and the Szegedy/MNRS walk-search framework
common	prepare_select.py	The standard PREPARE–SELECT decomposition of an LCU and alias sampling
common	qsvt.py	Standard QSVT transforms: QSP phases, matrix inversion, eigenstate filtering, fixed-point search
common	transforms.py	Assembly of qubitization, QSVT with explicit phase sequences, and oblivious amplification
common	state_preparation.py	Initial-state composition: extended initial states, physical subspace selection, applying a BE to a state
common	hamiltonian.py	Pauli-term evolution, Trotter composition, Taylor BE, and the injectable QSP interface
common	fourier.py	Forward/inverse QFT, zero-width work adaptation, and Fourier addition modulo \(2^n\)
common	arithmetic.py	Reversible fixed-point arithmetic: Boolean SSA networks, compute/uncompute, native registration
common	estimation.py	QPE, canonical amplitude estimation, Hadamard test, swap test
common	search.py	Grover, the Grover iterate, and amplitude amplification of a success subspace
common	walks.py	Hadamard coined walks on periodic lattices
common	spectral_synthesis.py	Operator-level synthesis optimization of spectral circuits (uniformly controlled preparation, fanout merging)
common	integration.py	Heinrich quantum summation and numerical integration
qlss	qlss.py	Problem contracts, Costa walk/filter, and the CKS base Chebyshev/LCU routes
qlss	vtaa_cks.py	CKS §5 variable-time amplitude amplification: QSP verdict clock, banded inverse LCU, Ambainis nested amplification, and A’ uncomputation
qnlss	newton.py	Quantum Newton method: M_F data structure, differenced Jacobian oracle
qnlss	carleman.py	Finite-order Carleman tensor lifting for polynomial ODEs
qode	ode.py	QODE protocol and Euler history assembly; concrete methods live in separate files
qode	ode_models.py	Hermitian anti-Hermitian decomposition and the LinearODE shared input model
qode	cbmd.py	Contour-decomposition matrix functions and evolution assembly
qode	lchs.py	Finite weighted sums of Hermitian branches for dissipative linear evolution
qode	schrodingerization.py	Quantum representation of non-unitary evolution via auxiliary coordinates + Fourier transform
qode	sde.py	Input models from Fokker–Planck/SDE to linear ODEs and classical witnesses
qode	legacy.py	Compatibility layer of the early evolution factories (make_lchs_qode and friends)
qpde	pde.py	Thin QPDE input and solve wrapper on top of the QODE protocol
qml	recommendation.py	Kerenidis–Prakash quantum recommendation systems
qml	qpca.py	Quantum principal component analysis via density-matrix exponentiation + phase estimation
qml	qsdp.py	Quantum semidefinite programming framework from Gibbs sampling + trace estimation + matrix multiplicative weights
qml	qcnn.py	Classical-side tensor/convolution/pooling logic of quantum convolutional neural networks
qml	qcnn_layer.py	Quantum building blocks of quantum convolutional neural networks
optimization	dqi.py	DQI decoded quantum interference: GF(2) max-XORSAT
optimization	variational.py	Parameterized ansätze, MaxCut QAOA, Pauli measurements, and VQE measurement-circuit collections
optimization	gradient.py	Jordan quantum gradient estimation
basics	oracle_algorithms.py	D-J, Bernstein–Vazirani, Simon sampling; Simon’s GF(2) elimination runs on the classical side
basics	number_theory.py	Finite-size modular-multiplication permutations, QPE order finding, continued-fraction factor-candidate post-processing
qec	error_correction.py	Encoding and coherent recovery of the three-qubit bit/phase-flip repetition code

How to choose a starting point

If the input is a Boolean function, start with the query and search family. To estimate a probability or an expectation value, start with estimation. Given a decomposition into Hamiltonian terms, Trotter is available; with only an operator block encoding, choose an implementation that consumes that access model.

PDE algorithms first construct the spatial-discretization inputs, then choose the QODE or the linearization route. Data living in QRAM does not mean the matrix is already block encoded; the input-adaptation step still has to be explicit.

Running the gallery

uv run python examples/algorithm_gallery.py
PYTHONPATH=src /path/to/backend/python examples/algorithm_gallery.py --native

The gallery contains 22 small examples, including different applications of the same algorithm, for example amplitude estimation and quantum counting. They illustrate interfaces and readout methods; they are not 22 unrelated algorithms.

Implementation basis

Fourier addition follows Draper’s QFT adder construction. Amplitude amplification and estimation follow the framework of Brassard et al.. The QAOA cost/mixer layering follows the original algorithm of Farhi et al.. Order finding and the classical factor post-processing follow Shor’s construction.

The current modular multiplication uses capped permutation synthesis, by default at most 8 bits; it exercises the order-finding interface and circuit and does not represent scalable Shor modular arithmetic. VQE and QAOA provide the quantum circuits; the classical optimizer is chosen by the application. QSVT receives caller-provided phase sequences and does not include a general phase solver.

Algorithm pages

One page per algorithm, describing the interface, input model, implementation notes, and where to find the validation evidence. The algorithm pages are organized into thirteen families, starting with data loading and input models and ending with applications and infrastructure; the line under each page’s title records its category (C1–C6 or the application layer) and defining module — the category definitions are in the validation plan.

Algorithm families

• Data Loading and Input Models
• Basic Query Algorithms
• Query and Search
• Fourier and Arithmetic
• Estimation and Testing
• Hamiltonian Evolution and QSVT
• Quantum Linear Systems
• Differential Equations
• Variational and Optimization
• Quantum Walks
• Quantum Machine Learning
• Quantum Error Correction
• Applications and Infrastructure

Numerical validation

Paper-grade numerical experiments for quantum semidefinite programming (qsdp.py, no dedicated page yet) and its inner primitives in density.py (purification access, Gibbs state preparation) are in tests/verification/verify_misc_algorithms.py (the misc_algorithms group), all executed on real backends with fully independent classical oracles (numpy eigendecomposition / eigvalsh / closed-form expressions).

Experiment design: (a) purification witness — the purified state of a 2×2 complex density matrix (off-diagonal entries 0.1±0.05j) is prepared by gate_purification and, after taking the partial trace over the environment, cross-checked against the original matrix element by element; (b) Gibbs purification — two instances, diagonal \(H = \mathrm{diag}(1, -0.5)\) (\(\beta = 0.6\)) and dense non-diagonal \(H\) (\(\beta = 0.8\)), with error = 0.05; the normalized reduced state of the postselected signal == 0 branch is compared against the numpy Gibbs state \(e^{-\beta H}/Z\), plus convergence sweeps at error = 0.4/0.2/0.1; (c) trace estimation — probe readouts of trace_estimate_circuit for the Z/X/Y Pauli observables on a complex density matrix against the numpy trace \(\mathrm{Tr}(P\rho)\), and joint decoding of trace_from_joint along the Gibbs approximate-purification path; (d) MMW driver — a four-constraint feasibility instance (equalities \(r_z = 0.2\), \(r_x = 0.1\) split into two-sided inequalities, \(\varepsilon = 0.08\)); after convergence, the returned average iterate \(\bar\rho\) is independently audited for PSD/trace-1/violations; (e) single quantum round — estimates produced on the reference executor by the Gibbs purification + per-constraint trace-estimation circuits generated by iteration_circuits are compared with a classical estimator constraint by constraint.

Key metrics:

Case	Scale	Paths	Metric	Value
purification-partial-trace	2 qubits	four-path full-amplitude cross-check	max elementwise error	1.1e-16
gibbs-purification-diagonal	9 qubits, qsp_degree 3	reference + rir-pysparq + originir-ext	trace distance / postselection success rate	3.0e-5 / 0.0965
gibbs-purification-nondiagonal	13 qubits, qsp_degree 3	same	trace distance / postselection success rate	1.9e-6 / 0.1130
gibbs-error-scaling	error = 0.4/0.2/0.1	reference	trace distance	5.6e-4 / 8.7e-5 / 8.7e-5 (all ≤ error, monotone non-increasing)
trace-estimate-pauli-xyz	≤5 qubits	three paths	Tr(Zρ)/Tr(Xρ)/Tr(Yρ) estimates	0.4 / 0.2 / 0.1 (max error 5.3e-16)
trace-estimate-joint-gibbs	10 qubits	reference + rir-pysparq	Tr(Zρ_gibbs) joint decoding	−0.42196 vs −0.42190 (error 6.0e-5)
qsdp-mmw-driver-feasibility	4 constraints, 256 iterations	classical driver	convergence / max violation / min eigenvalue	✓ / 0.0738 ≤ 0.08 / 0.4295
qsdp-mmw-quantum-round	2 constraints, single round	reference + rir-pysparq	max difference, quantum vs classical estimate	2.3e-6

Reproduction:

PYTHONPATH=src /home/agony/projects/qcfd-dev/quantum-cfd-software/.venv/bin/python tests/verification/verify_misc_algorithms.py

Artifacts: out/verification/misc_algorithms.json (24 cases, all passing; this section covers the eight purification-*, gibbs-*, trace-estimate-*, and qsdp-* cases). Numerical validation of the group’s remaining algorithms is on their own pages (density-matrix exponentiation, QPCA, DQI, variational ansätze, VQE, QAOA, repetition codes).

Numerical validation (application catalog and infrastructure modules)

All entries of applications/catalog.py and applications/gallery.py are covered by the nt_qlss_sde group in tests/verification/verify_nt_qlss_sde.py: every entry runs on real backends (rir-pysparq, adapter-pysparq, some including the reference executor) and is cross-checked amplitude by amplitude against the reference executor; oracle-level numerical correctness is carried by the validation sections of the underlying algorithms’ own pages (number theory, CKS, and so on — see the corresponding pages in this catalog).

Experiment design: the 22 gallery examples are cross-checked at full amplitude on three backends (reference / rir-pysparq / adapter-pysparq); of the 33 catalog examples, 31 are cross-checked reference vs rir-pysparq (stateprep_qram doubles as the regression sentinel for pysparq.rir work-bit uncomputation and is also full-state cross-checked against the adapter), while qham_qode and qham_qpde — with more than \(10^6\) expansion steps and roughly 60–90 seconds per backend — complete their reference vs adapter cross-checks through spawned concurrent subprocesses. These entries are assembly examples: their numerical content (modular-multiplication permutations, order-finding distributions, CKS solution states, and so on) is certified by the independent oracle validations on each algorithm’s page; the catalog level only pins down assembly determinism and does not repeat physical oracles — which is why catalog/gallery entries are covered by “structural tests + cross-backend comparison” rather than independent numerical oracles.

Key metrics:

Case	Scale	Paths	Metric	Value
gallery-* (22 examples)	small instances	three backends	max cross-backend amplitude deviation	0.0 (all)
catalog-* (29 examples)	small instances	reference + rir-pysparq	max cross-backend amplitude deviation	≤ 1.4e-16
catalog-stateprep_qram	QRAM angle table	three backends	full-state deviation / work-bit residue	0.0 / 0.0
catalog-qham_qode, qham_qpde	39296 states	reference + adapter	max cross-backend amplitude deviation	1.8e-9

Reproduction:

PYTHONPATH=src /home/agony/projects/qcfd-dev/quantum-cfd-software/.venv/bin/python tests/verification/verify_nt_qlss_sde.py

Artifacts: out/verification/nt_qlss_sde.json (gallery-* 22 examples, catalog-* 33 examples).