Faster Algorithms for Subset Sum using Filtered Representation Trees

We study filtered representation algorithms for random planted subset sum on $n$ input numbers at density one. Within the binary representation-tree frameworks compared here, we conditionally improve the classical running time from $2^{0.2690n+o(n)}$ of Howgrave-Graham to $2^{0.2634n+o(n)}$. With quantum access to classical memory (QRACM), the running time improves from $2^{0.2356n+o(n)}$ to $2^{0.2100n+o(n)}$. With quantum access to quantum memory (QRAQM), it improves from $2^{0.2156n+o(n)}$ to $2^{0.1980n+o(n)}$. For each new construction, total space satisfies the same upper bound as running time. The constructions combine coordinate-dependent representation laws with type-class filtering and cost models adapted to their search engines. The quantum-memory construction uses one common size for all nonroot lists, so its remaining resource rates follow from short entropy formulas. We derive every source, index, candidate and reporting cost and verify the three finite profiles using directed interval calculations. The classical and quantum-search bounds require assumptions on recursive list distributions, survival and access. The quantum-memory bound further requires a coherent-update and hard-workspace interface, whose validity is not implied by an ordinary expected update count.

Authors

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-11-17
DOI
https://doi.org/10.5281/zenodo.24308979
Primary Topic
Quantum Computing Algorithms and Architecture
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Faster Algorithms for Subset Sum using Filtered Representation Trees

Luis Iglesias, Samuel J. Adams
1 links
Zenodo (CERN European Organization for Nuclear Research)
Quantum Computing Algorithms and Architecture
preprint

Faster Algorithms for Subset Sum using Filtered Representation Trees

Luis Iglesias, Samuel J. Adams
preprint en

Abstract

We study filtered representation algorithms for random planted subset sum on $n$ input numbers at density one. Within the binary representation-tree frameworks compared here, we conditionally improve the classical running time from $2^{0.2690n+o(n)}$ of Howgrave-Graham to $2^{0.2634n+o(n)}$. With quantum access to classical memory (QRACM), the running time improves from $2^{0.2356n+o(n)}$ to $2^{0.2100n+o(n)}$. With quantum access to quantum memory (QRAQM), it improves from $2^{0.2156n+o(n)}$ to $2^{0.1980n+o(n)}$. For each new construction, total space satisfies the same upper bound as running time. The constructions combine coordinate-dependent representation laws with type-class filtering and cost models adapted to their search engines. The quantum-memory construction uses one common size for all nonroot lists, so its remaining resource rates follow from short entropy formulas. We derive every source, index, candidate and reporting cost and verify the three finite profiles using directed interval calculations. The classical and quantum-search bounds require assumptions on recursive list distributions, survival and access. The quantum-memory bound further requires a coherent-update and hard-workspace interface, whose validity is not implied by an ordinary expected update count.

Zenodo (CERN European Organization for Nuclear Research)
Quantum Computing Algorithms and Architecture
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon