2026-07-15 04:00 UTCOriginal source2 min readUpdated: 2026-07-15 08:16 UTC

Qubit-Efficient Quantum Search for Hyperdimensional Decomposition via Logarithmic Encoding

This paper proposes a qubit-efficient quantum framework for hyperdimensional computing decomposition that reduces representation cost from O(D) to O(log D) by introducing logarithmic hypervector and binding encodings, combined with a modified Dürr-Høyer search procedure, maintaining O(√N^F) search complexity while achieving up to 2000× qubit reduction.

SourcearXiv Machine LearningAuthor: Sanggeon Yun, Hyunwoo Oh, Ryozo Masukawa, Raheeb Hassan, Mohsen Imani

-->

[Submitted on 11 Jul 2026]

Title:Qubit-Efficient Quantum Search for Hyperdimensional Decomposition via Logarithmic Encoding

View a PDF of the paper titled Qubit-Efficient Quantum Search for Hyperdimensional Decomposition via Logarithmic Encoding, by Sanggeon Yun and 4 other authors

View PDF HTML (experimental)

Abstract:Hyperdimensional Computing (HDC) represents symbols using high-dimensional hypervectors of dimension $D$. In hypervector decomposition, the objective is to recover $F$ constituent hypervectors, each drawn from a codebook of size $N$, from a bound target hypervector. This requires searching over $N^F$ candidate tuples, making the task computationally prohibitive at scale. Recent quantum approach provides a quadratic search advantage, but typically rely on qubit-inefficient $O(D)$-qubit hypervector representations. We propose a qubit-efficient quantum framework for HDC decomposition that reduces the representation cost to $O(\log D)$. The framework introduces logarithmic hypervector and binding encodings, together with a reversible hypervector lookup operator for circuit-level manipulation of dense hypervectors. Combined with a modified Dürr-Høyer search procedure, the method preserves $O(\sqrt{N^F})$ search complexity while substantially reducing qubit usage. Experimental results validate correct similarity computation, accurate decomposition in executable regimes, and significantly improved qubit scaling over baselines based on explicit $D$-qubit hypervector encodings, achieving up to $2{,}000\times$ fewer qubits.

Comments: Accepted to ICCAD 2026

Subjects:

Machine Learning (cs.LG)

Cite as: arXiv:2607.11936 [cs.LG]

(or arXiv:2607.11936v1 [cs.LG] for this version)

https://doi.org/10.48550/arXiv.2607.11936

arXiv-issued DOI via DataCite

Submission history

From: Sanggeon Yun [view email] [v1] Sat, 11 Jul 2026 06:56:04 UTC (5,754 KB)

Full-text links:

Access Paper:

View a PDF of the paper titled Qubit-Efficient Quantum Search for Hyperdimensional Decomposition via Logarithmic Encoding, by Sanggeon Yun and 4 other authors

View PDF

HTML (experimental)

TeX Source

view license

Current browse context:

cs.LG

new | recent | 2026-07

Change to browse by:

References & Citations

NASA ADS

Google Scholar

Semantic Scholar

Data provided by:

Bibliographic Tools

Bibliographic and Citation Tools

Bibliographic Explorer Toggle

Bibliographic Explorer (What is the Explorer?)

Connected Papers Toggle

Connected Papers (What is Connected Papers?)

Litmaps Toggle

Litmaps (What is Litmaps?)

scite.ai Toggle

scite Smart Citations (What are Smart Citations?)

Code, Data, Media

Code, Data and Media Associated with this Article

alphaXiv Toggle

alphaXiv (What is alphaXiv?)

Links to Code Toggle

CatalyzeX Code Finder for Papers (What is CatalyzeX?)

DagsHub Toggle

DagsHub (What is DagsHub?)

GotitPub Toggle

Gotit.pub (What is GotitPub?)

Huggingface Toggle

Hugging Face (What is Huggingface?)

ScienceCast Toggle

ScienceCast (What is ScienceCast?)

Demos

Replicate Toggle

Replicate (What is Replicate?)

Spaces Toggle

Hugging Face Spaces (What is Spaces?)

Spaces Toggle

TXYZ.AI (What is TXYZ.AI?)