QUBO-WiSARD

QUBO-WiSARD is a research-oriented Python package for QUBO-based structural compression and RAM-node selection in WiSARD classifiers, a class of Weightless Neural Networks. This repository is also the reproduction package for the manuscript "Structural Compression of Weightless Neural Networks: A QUBO Formulation and Its Operating Range" (in paper_neurocomputing/): the reusable package lives under src/qubo_wisard/, and everything needed to reproduce the paper's experiments, results and manuscript lives alongside it.

Research status

No quantum advantage is claimed, measured, or implied anywhere in this repository.

Installation

QUBO-WiSARD is available on PyPI:

pip install qubo-wisard

Quick start

from qubo_wisard import WiSARD, QUBOSelector

# X_train, y_train, X_val, y_val, X_test: pre-binarized uint8 arrays.
model = WiSARD(input_size=64, address_size=8, seed=1, response="binary", bleach=1)
model.fit(X_train, y_train)

selector = QUBOSelector(alpha=3.0, beta=0.2, lam=1.5, k_ratio=0.6, solver="neal")
selector.fit(model, X_val, y_val)

preds = selector.predict(model, X_test)

A complete, runnable example on synthetic data (no download) is at examples/basic_usage.py.

Method overview

A trained WiSARD classifier is a collection of interchangeable RAM nodes. This work formulates the choice of which nodes to keep as a Quadratic Unconstrained Binary Optimization problem, solved once per class discriminator after training. The classifier is never retrained and the stored memories are never modified: the optimizer produces only a binary mask applied at inference. The uncompressed model is therefore an upper reference rather than a competitor, and the decisive comparison is against random selection at the same budget, which isolates the quality of the selection from the effect of shrinking the model.

QUBO formulation

The objective implemented in qubo_wisard.qubo, solved independently per class $c$:

E_c(w_c)=
-\alpha \sum_{r=1}^{R}\tilde{U}_{c,r}w_{c,r}
+\beta \sum_{r<s}\rho_{r,s}w_{c,r}w_{c,s}
+\lambda\left(\sum_{r=1}^{R}w_{c,r}-k\right)^2

which expands (using $w_r^2=w_r$ for binary variables) to the QUBO coefficients built by build_qubo_matrix:

Q[r,r] = -alpha * U_tilde[r]  +  lambda * (1 - 2k)
Q[r,s] = beta  * rho[r,s]      +  2 * lambda            (r < s)

• $\tilde{U}_{c,r}$: discriminative utility of RAM $r$ for class $c$ (compute_margin_utility). The difference between the RAM's mean activation on samples of class $c$ and on samples of every other class, normalized to $[0, 1]$ per class.
• $\rho_{r,s}$: redundancy between RAM $r$ and RAM $s$ (compute_redundancy_matrix), the absolute Pearson correlation of their activation profiles, averaged across classes. This is the metric currently implemented, not a placeholder for an arbitrary interaction term; a different redundancy metric would need its own function.
• $k=\lfloor \kappa R\rfloor$: the retention budget, k_ratio in QUBOSelector.

Setting $\beta = 0$ collapses the problem to a ranking by utility alone, so the quadratic term is what the formulation has to justify; experiments/beta_sweep/ and experiments/redundancy_check/ test exactly this.

Structural-selection pipeline

QUBOSelector.fit composes the following, in order, keeping every intermediate result on the instance rather than discarding it:

build_activation_tensor -> compute_margin_utility -> compute_redundancy_matrix
      -> build_qubo_for_all_classes -> QUBOSolver.solve (one call per class)

QUBOSelector.predict then calls predict_sparse, which looks up only the RAMs selected for each class.

Public API

from qubo_wisard import WiSARD, QUBOSelector

Lower-level functions remain directly importable and are what the two classes above compose:

from qubo_wisard.encoding import fit_thresholds, apply_thresholds, load_tabular_splits
from qubo_wisard.activation import build_activation_tensor
from qubo_wisard.utility import compute_margin_utility
from qubo_wisard.redundancy import compute_redundancy_matrix
from qubo_wisard.qubo import build_qubo_matrix, build_qubo_for_all_classes
from qubo_wisard.solver import SimulatedAnnealingSolver, QUBOSolver
from qubo_wisard.inference import predict_sparse, random_baseline_weights

After fit, QUBOSelector exposes its intermediate quantities rather than hiding them: utility_, redundancy_, qubo_matrices_, weights_, energies_, k_, solve_time_s_.

Solvers

QUBOSelector(solver=...) accepts "neal", "openjij_sa", "openjij_sqa", "qiskit", or a QUBOSolver instance directly.

The QAOA proof of concept in experiments/qaoa_poc/ maps the same QUBO to an Ising Hamiltonian and runs a statevector QAOA emulation for research purposes. It is experiment code, not a QUBOSolver backend: it is not installed by the package and should not be read as supported QAOA solver support.

Encoding

qubo_wisard.encoding implements thermometer encoding for tabular features: uniform, quantile, and gaussian threshold placement, all emitting exactly T bits per feature so comparisons across methods are cost-controlled. Thresholds are always fit on the training split only, then applied unchanged to validation/test. load_tabular_splits additionally fetches an OpenML dataset and applies the stratified split used by the tabular experiments (requires the tabular extra: scikit-learn, scipy for the gaussian method).

Headline results

Over 30 seeds per configuration, paired Wilcoxon signed-rank:

The advantage grows monotonically as compression tightens; see Limitations for where it does not hold.

Experiments and reproducibility

Environment. The reported numbers were produced under Python 3.14.4 on Ubuntu 26.04, 16 CPU cores, no GPU:

python3.14 -m venv .venv
.venv/bin/python -m pip install -r requirements-lock.txt
.venv/bin/python -m pip install -e .

Use requirements-lock.txt, not requirements.txt: the latter carries loose lower bounds and will resolve to different versions than the ones the results depend on.

The editable install (pip install -e .) makes import qubo_wisard work from any working directory; it is required by newly written or migrated experiment scripts. Older scripts still add src/ to sys.path directly and work without it, but the underlying implementation is the same package either way, imported either as qubo_wisard (current name) or qubo_wizard (a compatibility alias kept only for those older research scripts; see Research status and src/qubo_wizard/__init__.py. It is not a second supported public API: new code should always use qubo_wisard).

Data. Nothing is versioned here. The tabular datasets are fetched from OpenML with pinned versions and the image datasets through torchvision, both automatically on first run. See analysis/DATA_SETUP.md.

Experiments. Each directory under experiments/ is self-contained: a run_*.py that produces *_detailed.csv, and where applicable an analyze_*.py that produces the statistical tables. The entry points behind the main claims:

Runs are deterministic given the seed: dwave-neal receives an explicit seed and the data split is fixed by random_state=42 independently of the model seed.

Appendix C of the manuscript is the authoritative checklist: it records the splits, the objective coefficients ($\alpha = 3.0$, $\beta = 0.2$, $\lambda = 1.5$), the solver budget (500 reads, 2000 sweeps), the software versions, and the caveats.

Building the manuscript. See paper_neurocomputing/README.md.

Package tests. pytest tests/ runs the package unit tests (fast, deterministic, no network access, no dataset downloads); this is a check on the software, distinct from the experiments/ scripts that reproduce the paper's numbers.

Repository structure

.
├── src/qubo_wisard/        the reusable package: encoding, WiSARD, QUBO construction,
│                           solvers, and QUBOSelector (see qubo_wisard/__init__.py)
├── src/qubo_wizard/        compatibility alias kept for older research scripts;
│                           re-exports qubo_wisard, holds no implementation of its own
├── src/*.py (flat)         a separate course project on bit-to-RAM assignment
│                           (see README_course.md); a different problem from RAM
│                           selection, not part of the qubo_wisard package and not
│                           built into the PyPI distribution
├── experiments/            one directory per experiment: runner, results, figures
├── analysis/               shared statistical machinery and dataset setup
├── configs/                default.yaml is an older EMNIST-protocol configuration
│                           used only by the legacy exp0X_*.py scripts; the tabular
│                           protocol backing the manuscript sets its parameters
│                           directly in each experiment script, not from this file
├── paper_neurocomputing/   the manuscript (Elsevier CAS)
├── tests/                  package unit tests (pytest)
├── examples/                minimal usage examples
├── requirements-lock.txt   exact resolved environment (reproduces the numbers)
├── requirements.txt        loose bounds (development)
├── pyproject.toml
├── CITATION.cff
└── LICENSE

The flat course-project modules and the qubo_wizard alias remain in this repository, on this branch and on main, for research continuity. Earlier manuscript drafts, superseded result sets and presentation material are kept out of main and preserved on the archive/pre-submission branch instead.

Limitations

• The advantage over random selection is not established for mild compression: at $\kappa=0.9$, four of nine cells are indistinguishable from random selection, and one is significantly worse. The method targets aggressive compression.
• The contribution is RAM-node reduction under a fixed accuracy budget, not an accuracy gain; see the manuscript for the accuracy-per-byte framing.
• A memory-aware knapsack constraint, input-bit selection, and transfer to random-forest pruning were tested and did not outperform simpler baselines. These negative results are reported in the manuscript and are not pursued further in this package.
• OpenJijSASolver and OpenJijSQASolver are implemented but not verified in this environment; QiskitSamplerSolver is a stub.
• rho (redundancy) is the absolute Pearson correlation of activation profiles, averaged across classes. This is the metric the formulation was validated with; it is not generalized to an arbitrary interaction metric.

Citation

This software can currently be cited using the metadata in CITATION.cff (GitHub renders a "Cite this repository" option from it automatically). The associated manuscript is not yet published; once it is, the citation metadata will be updated with the venue and DOI.

License

MIT. See LICENSE.

Authors

Natasha Costa Fonseca (software; see CITATION.cff).