Qubit-Efficient Quantum Search for Hyperdimensional Decomposition via Logarithmic Encoding

arXiv:2607.11936v1 Announce Type: new 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 Durr-H{o}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{,}000imes fewer qubits.

Related

• AMS-HD: Hyperdimensional Computing for Real-Time and Energy-Efficient Acute Mountain Sickness Detection
• A Quantum Reservoir Architecture for Chaotic Forecasting and a Test of Whether Its High Dimension Helps
• Q-PhotoNAS: Hybrid Quantum Neural Architecture Search Framework on Photonic Devices

Source: arXiv cs.LG | 2026-07-15