Qubit-Efficient Quantum Search for Hyperdimensional Decomposition via Logarithmic Encoding

• URL: http://arxiv.org/abs/2607.11936v1
• Date: Sat, 11 Jul 2026 06:56:04 GMT
• Title: Qubit-Efficient Quantum Search for Hyperdimensional Decomposition via Logarithmic Encoding
• Abstract summary: Hyperdimensional Computing (HDC) represents symbols using high-dimensional hypervectors of dimension $D$.<n>We propose a qubit-efficient framework for HDC decomposition that reduces the representation cost to $O(log D)$.
• Score: 7.668053149186826
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• RSLM: Training-Free Vector Quantization for Approximate Nearest Neighbor Search [0.4077787659104315]
  RSLM is a family of training-free vector quantization codecs compressing embeddings to 1--4 bits per dimension.<n>We reduce memory cost and memory bandwidth of a typical large-scale Approximate Nearest Neighbor (ANN) search system.<n>Our major innovation is that we correct the $L$ norm of the final reconstructed vector rather than just the residual.
  arXiv  Detail & Related papers  (2026-08-31T07:40:57Z)
• Quantum Speedups for Stochastic Optimization with Heavy-Tailed Noise [49.730496294398726]
  We develop a novel quantum mean estimator for heavy-tailed random variables.<n>We derive stronger lower bounds for tail index>4/3$, showing that a nontrivial dependence on a dimension is unavoidable.<n>For a convex objective function, we propose a quantum projected gradient descent method.
  arXiv  Detail & Related papers  (2026-07-28T09:29:37Z)
• No More K-means: Single-Stage Sparse Coding for Efficient Multi-Vector Retrieval [51.43543998583709]
  Single-stage Sparse Retrieval (SSR) is a paradigm shift that replaces expensive clustering with efficient sparse coding.<n>It reduces indexing time by 15x compared to ColBERTv2, halves retrieval latency, and simultaneously improves retrieval performance.
  arXiv  Detail & Related papers  (2026-05-28T15:53:34Z)
• Block encoding of sparse matrices with a periodic diagonal structure [67.45502291821956]
  We provide an explicit quantum circuit for block encoding a sparse matrix with a periodic diagonal structure.<n>Various applications for the presented methodology are discussed in the context of solving differential problems.
  arXiv  Detail & Related papers  (2026-02-11T07:24:33Z)
• A fast and exact approach for stabilizer Rényi entropy via the XOR-FWHT algorithm [0.5735035463793009]
  Quantum advantage is widely understood to rely on key quantum resources beyond entanglement.<n>However, a direct brute-force of all Pauli strings and the corresponding expectation values from a length-$2N$ state vector, where $N$ is the system size, yields an overall computational cost scaling as $O(8N)$.<n>Here we reformulate the second-order stabilizer Rényi entropy in a bitstring language, expose an underlying XOR-convolution structure on $mathbb ZN$, and reduce the computation to $2N$ fast Walsh-Hadamard transforms of length
  arXiv  Detail & Related papers  (2025-12-31T07:35:47Z)
• Linearithmic Clean-up for Vector-Symbolic Key-Value Memory with Kroneker Rotation Products [4.502446902578007]
  A computational bottleneck in current Vector-Symbolic Architectures is the clean-up'' step.<n>We present a new codebook representation that supports efficient clean-up.<n>The resulting clean-up time complexity is linearithmic, i.e. $mathcalO(N,textlog,N)$.
  arXiv  Detail & Related papers  (2025-06-18T18:23:28Z)
• Hyperdimensional Quantum Factorization [12.607568833115407]
  HDQF encodes potential factors as a quantum superposition using qubit states and bipolar vector representation. This yields a quadratic speedup over classical search methods and effectively mitigates Hypervector Factorization capacity issues.
  arXiv  Detail & Related papers  (2024-06-13T20:50:02Z)
• Quantum encoder for fixed Hamming-weight subspaces [0.0]
  We present an exact $n$-qubit computational-basis amplitude encoder of real- or complex data vectors of $d=binomnk$valued into a subspace of fixed Hamming weight $k$.<n>We show how our encoder can improve the performance of variational quantum algorithms for problems that include particle-string symmetries.<n>Our results constitute a versatile framework for quantum data compression with various potential applications in fields such as quantum chemistry, quantum machine learning, and constrained $k$ optimizations.
  arXiv  Detail & Related papers  (2024-05-30T18:26:41Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$. We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
  arXiv  Detail & Related papers  (2024-01-17T18:59:38Z)
• Factorizers for Distributed Sparse Block Codes [45.29870215671697]
  We propose a fast and highly accurate method for factorizing distributed block codes (SBCs) Our iterative factorizer introduces a threshold-based nonlinear activation, conditional random sampling, and an $ell_infty$-based similarity metric. We demonstrate the feasibility of our method on four deep CNN architectures over CIFAR-100, ImageNet-1K, and RAVEN datasets.
  arXiv  Detail & Related papers  (2023-03-24T12:31:48Z)
• Efficient Nearest Neighbor Search for Cross-Encoder Models using Matrix Factorization [60.91600465922932]
  We present an approach that avoids the use of a dual-encoder for retrieval, relying solely on the cross-encoder. Our approach provides test-time recall-vs-computational cost trade-offs superior to the current widely-used methods.
  arXiv  Detail & Related papers  (2022-10-23T00:32:04Z)
• Rapid Person Re-Identification via Sub-space Consistency Regularization [51.76876061721556]
  Person Re-Identification (ReID) matches pedestrians across disjoint cameras. Existing ReID methods adopting real-value feature descriptors have achieved high accuracy, but they are low in efficiency due to the slow Euclidean distance computation. We propose a novel Sub-space Consistency Regularization (SCR) algorithm that can speed up the ReID procedure by 0.25$ times.
  arXiv  Detail & Related papers  (2022-07-13T02:44:05Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.