# Qubit-Efficient Quantum Search for Hyperdimensional Decomposition via Logarithmic Encoding

arXiv: https://arxiv.org/abs/2607.11936 · HTML: https://mlsanity.com/paper/2607.11936/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 33 references that are in the map.
- First posted on arXiv 11 Jul 2026.

## Builds on (most cited first, 7 of 7)

- [A Survey on Hyperdimensional Computing aka Vector Symbolic Architectures, Part II: Applications, Cognitive Models, and Challenges](https://mlsanity.com/paper/2112.15424/) (2021)
- [Learning to Decode the Surface Code with a Recurrent, Transformer-Based Neural Network](https://mlsanity.com/paper/2310.05900/) (2023)
- [Hyperdimensional computing as a framework for systematic aggregation of image descriptors](https://mlsanity.com/paper/2101.07720/) (2021)
- [Quantum Policy Iteration via Amplitude Estimation and Grover Search -- Towards Quantum Advantage for Reinforcement Learning](https://mlsanity.com/paper/2206.04741/) (2022)
- [NeuroHash: A Hyperdimensional Neuro-Symbolic Framework for Spatially-Aware Image Hashing and Retrieval](https://mlsanity.com/paper/2404.11025/) (2024)
- [Accelerating Quantum Reinforcement Learning with a Quantum Natural Policy Gradient Based Approach](https://mlsanity.com/paper/2501.16243/) (2025)
- [DecoHD: Decomposed Hyperdimensional Classification under Extreme Memory Budgets](https://mlsanity.com/paper/2511.03911/) (2025)

## Abstract (arXiv)

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 NF 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"urr-Hoyer search procedure, the method preserves O(√NF) 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× fewer qubits.