Qubit-Efficient Quantum Search for Hyperdimensional Decomposition via Logarithmic Encoding

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.