Qubit-Efficient Quantum Search for Hyperdimensional Decomposition via Logarithmic Encoding

# Qubit-Efficient Quantum Search for Hyperdimensional Decomposition via Logarithmic Encoding
Source: [https://arxiv.org/html/2607.11936](https://arxiv.org/html/2607.11936)
,Hyunwoo OhUniversity of California, IrvineIrvineCAUSA[hyunwooo@uci\.edu](https://arxiv.org/html/2607.11936v1/mailto:[email protected]),Ryozo MasukawaUniversity of California, IrvineIrvineCAUSA[rmasukaw@uci\.edu](https://arxiv.org/html/2607.11936v1/mailto:[email protected]),Raheeb HassanUniversity of California, IrvineIrvineCAUSA[raheebh@uci\.edu](https://arxiv.org/html/2607.11936v1/mailto:[email protected])andMohsen ImaniUniversity of California, IrvineIrvineCAUSA[m\.imani@uci\.edu](https://arxiv.org/html/2607.11936v1/mailto:[email protected])

###### Abstract\.

Hyperdimensional Computing \(HDC\) represents symbols using high\-dimensional hypervectors of dimensionDD\. In hypervector decomposition, the objective is to recoverFFconstituent hypervectors, each drawn from a codebook of sizeNN, from a bound target hypervector\. This requires searching overNFN^\{F\}candidate tuples, making the task computationally prohibitive at scale\. Recent quantum approach provides a quadratic search advantage, but typically rely on qubit\-inefficient𝒪​\(D\)\\mathcal\{O\}\(D\)\-qubit hypervector representations\. We propose a qubit\-efficient quantum framework for HDC decomposition that reduces the representation cost to𝒪​\(log⁡D\)\\mathcal\{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𝒪​\(NF\)\\mathcal\{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 explicitDD\-qubit hypervector encodings, achieving up to2,000×2\{,\}000\\timesfewer qubits\.

## 1\.Introduction

![Refer to caption](https://arxiv.org/html/2607.11936v1/x1.png)Figure 1\.Current quantum hardware does not yet provide the combination of very large qubit counts and low error rates required by prior explicit\-dimension HDC decomposition methods, which use𝒪​\(D\)\\mathcal\{O\}\(D\)qubits for aDD\-dimensional hypervector\. This motivates our logarithmic\-qubit approach, which reduces the representation cost to𝒪​\(log⁡D\)\\mathcal\{O\}\(\\log D\)qubits and is better aligned with near\-term hardware\.Quantum computing\(Nielsen and Chuang,[2010](https://arxiv.org/html/2607.11936#bib.bib154)\)offers a fundamentally different computational model for solving search and optimization problems by exploiting superposition, interference, and amplitude amplification\(Nielsen and Chuang,[2010](https://arxiv.org/html/2607.11936#bib.bib154); Grover,[1996](https://arxiv.org/html/2607.11936#bib.bib147); Dalzellet al\.,[2023](https://arxiv.org/html/2607.11936#bib.bib153); Boyeret al\.,[1998](https://arxiv.org/html/2607.11936#bib.bib161); Brassardet al\.,[2000](https://arxiv.org/html/2607.11936#bib.bib162)\)\. One of its most important algorithmic advantages is the ability to reduce the complexity of unstructured search from linear to square\-root scaling in the size of the search space\. This makes quantum search especially attractive for machine learning problems whose dominant cost arises from combinatorial candidate selection rather than feature extraction alone\(Wiedemannet al\.,[2022](https://arxiv.org/html/2607.11936#bib.bib157); Xu and Aggarwal,[2025](https://arxiv.org/html/2607.11936#bib.bib158); Wiebeet al\.,[2015](https://arxiv.org/html/2607.11936#bib.bib163)\)\.

A representative instance of this opportunity arises in*Hyperdimensional Computing*\(HDC\), also known as Vector Symbolic Architectures\(Kanerva,[2009](https://arxiv.org/html/2607.11936#bib.bib112); Plate,[1995](https://arxiv.org/html/2607.11936#bib.bib145)\)\. HDC represents information using high\-dimensional vectors, called hypervectors, together with simple algebraic operations such as*binding*and*bundling*\(Kanerva,[2009](https://arxiv.org/html/2607.11936#bib.bib112); Plate,[1995](https://arxiv.org/html/2607.11936#bib.bib145)\)\. These operations support efficient compositional representations of structured information, including tuples, sequences, and symbolic memories, while preserving lightweight computation in high\-dimensional spaces\. HDC has attracted renewed interest not only as a standalone computing paradigm, but also as a structured layer on top of deep learning systems\. In such hybrid models, deep neural networks \(DNNs\) serve as powerful feature extractors, whereas HDC provides more interpretable and explicitly compositional structure over the resulting representations\(Rahimiet al\.,[2017](https://arxiv.org/html/2607.11936#bib.bib146); Neubert and Schubert,[2021](https://arxiv.org/html/2607.11936#bib.bib155); Yunet al\.,[2024](https://arxiv.org/html/2607.11936#bib.bib139); Barkamet al\.,[2023](https://arxiv.org/html/2607.11936#bib.bib156); Leeet al\.,[2023](https://arxiv.org/html/2607.11936#bib.bib164)\)\. This integration is particularly attractive in settings where the representational power of DNNs is desired together with the symbolic structure and controllability offered by HDC\.

A key obstacle, however, lies in*decomposition*: recovering the constituent hypervectors from a composite representation\. This problem is especially important in hybrid DNN–HDC systems, where one may wish to interpret, manipulate, or retrieve the symbolic factors encoded in a learned hypervector\(Memisevic and Hinton,[2010](https://arxiv.org/html/2607.11936#bib.bib166); Fradyet al\.,[2020](https://arxiv.org/html/2607.11936#bib.bib167); Yunet al\.,[2026](https://arxiv.org/html/2607.11936#bib.bib114); Pilliguaet al\.,[2025](https://arxiv.org/html/2607.11936#bib.bib168)\)\. If a target hypervector is formed by bindingFFfactors and each factor is drawn from a codebook of sizeNN, then exact recovery requires searching overNFN^\{F\}possible tuples\. The resulting exponential search space rapidly becomes the dominant computational bottleneck, even though the forward HDC operations themselves remain simple\(Kleykoet al\.,[2023](https://arxiv.org/html/2607.11936#bib.bib165); Poduvalet al\.,[2024](https://arxiv.org/html/2607.11936#bib.bib149)\)\.

A recent effort to address this challenge is Hyperdimensional Quantum Maximum Finding \(HDQMF\)\(Poduvalet al\.,[2024](https://arxiv.org/html/2607.11936#bib.bib149)\), which applies a Grover\-style quantum search strategy to HDC decomposition and achieves the expected quadratic improvement from𝒪​\(NF\)\\mathcal\{O\}\(N^\{F\}\)to𝒪​\(NF\)\\mathcal\{O\}\(\\sqrt\{N^\{F\}\}\)\(Grover,[1996](https://arxiv.org/html/2607.11936#bib.bib147)\)\. While promising, two important limitations remain\. First,the prior formulation is*qubit\-inefficient*: it represents aDD\-dimensional hypervector using𝒪​\(D\)\\mathcal\{O\}\(D\)qubits, which is incompatible with the high\-dimensional regime in which HDC is typically deployed, often withD≳104D\\gtrsim 10^\{4\}\. At the same time, scaling the number of reliably controllable entangled qubits remains a major challenge in quantum hardware\([J\. Kelly \(2018\)](https://arxiv.org/html/2607.11936#bib.bib159);[22](https://arxiv.org/html/2607.11936#bib.bib169);[J\. Bausch, A\. W\. Senior, F\. J\. Heras, T\. Edlich, A\. Davies, M\. Newman, C\. Jones, K\. Satzinger, M\. Y\. Niu, S\. Blackwell,et al\.\(2024\)](https://arxiv.org/html/2607.11936#bib.bib170)\), and current state\-of\-the\-art reliable processors still operate only at roughly the10210^\{2\}\-qubit scale\([20](https://arxiv.org/html/2607.11936#bib.bib160)\)\. Consequently, qubit\-efficient hyperdimensional methods are essential for realizing practically meaningful quantum advantage, as illustrated in[Figure 1](https://arxiv.org/html/2607.11936#S1.F1)\. Second,the prior formulation does not provide a detailed gate\-level realization of how dense hypervectors are loaded and manipulated within the circuit, instead treating hypervector access at a conceptual level\. These limitations make it difficult to assess whether the approach can be implemented concretely while retaining meaningful scalability\.

In this work, we propose aqubit\-efficient and circuit\-realizable quantum framework for HDC decompositionthat addresses both limitations while preserving the same asymptotic search complexity as prior quantum work\. To resolve the qubit\-efficiency issue, we introduce*logarithmic hypervector encoding*and*logarithmic binding encoding*, which represent and manipulateDD\-dimensional hypervectors using only𝒪​\(log⁡D\)\\mathcal\{O\}\(\\log D\)qubits rather than𝒪​\(D\)\\mathcal\{O\}\(D\)\. To resolve the circuit\-realization issue, we introduce a*hypervector lookup operator*that provides an explicit gate\-level mechanism for retrieving and applying dense hypervector coordinates within the circuit\. Building on these components, we formulate a modified Dürr–Høyer quantum search procedure\(Durr and Hoyer,[1996](https://arxiv.org/html/2607.11936#bib.bib148)\)for fast HDC decomposition, retaining the𝒪​\(NF\)\\mathcal\{O\}\(\\sqrt\{N^\{F\}\}\)search complexity of prior quantum approaches while using substantially fewer qubits\.

We evaluate the proposed framework through circuit\-level validation and decomposition experiments across a range of problem settings\. The results show that the proposed circuits compute the intended HDC similarity score correctly, recover the correct decomposition in executable regimes, and achieve substantially improved qubit scaling relative to explicit hypervector encoding\-based quantum baselines\.

Our main contributions are summarized as follows:

1. \(1\)We introducelogarithmic hypervector encoding and logarithmic binding encodingfor quantum HDC decomposition,reducing hypervector representation cost from𝒪​\(D\)\\mathcal\{O\}\(D\)qubits to𝒪​\(log⁡D\)\\mathcal\{O\}\(\\log D\)qubits\.
2. \(2\)We propose ahypervector lookup operatorthat provides an explicit circuit\-level realization of dense hypervector access and manipulation\.
3. \(3\)We develop amodified Dürr–Høyer quantum search framework for HDC decompositionthat preserves the quadratic search improvement of prior quantum approaches while operating with substantially fewer qubits\.
4. \(4\)Weempirically validate the proposed methodthrough circuit\-level correctness experiments, decomposition accuracy studies, and qubit\-scaling analysis\.

## 2\.Preliminaries

### 2\.1\.Hyperdimensional Computing

HDC basics\.HDC is a representation and computation paradigm that encodes information using high\-dimensional distributed vectors, called*hypervectors*\(Kanerva,[2009](https://arxiv.org/html/2607.11936#bib.bib112); Plate,[1995](https://arxiv.org/html/2607.11936#bib.bib145)\), typically with dimensionalityDDin the thousands or tens of thousands\. A hypervector may represent a symbol, an attribute, or a structured object\. A central property of HDC is that complex structures can be constructed through a small set of algebraic operations while preserving computational simplicity\. In this work, we focus on the standard bipolar setting, where each hypervector is given byh∈\{−1,\+1\}Dh\\in\\\{\-1,\+1\\\}^\{D\}\. Two fundamental HDC operations are*binding*and*bundling*\. In this work, we denote binding by⊙\\odot\. Binding combines multiple hypervectorsh1,h2,…h\_\{1\},h\_\{2\},\\dotsinto a single composite hypervectorhhaccording to

\(1\)h=h1⊙h2⊙⋯,h=h\_\{1\}\\odot h\_\{2\}\\odot\\cdots,which, in the bipolar setting considered here, is implemented by elementwise multiplication,

\(2\)h​\[u\]=∏jhj​\[u\],h\[u\]=\\prod\_\{j\}h\_\{j\}\[u\],whereh​\[u\]h\[u\]denotes theuu\-th coordinate ofhh, withu∈\{0,1,…,D−1\}u\\in\\\{0,1,\\dots,D\-1\\\}\. Bundling aggregates multiple hypervectors into a single memory\-like representation\(Kanerva,[2009](https://arxiv.org/html/2607.11936#bib.bib112); Plate,[1995](https://arxiv.org/html/2607.11936#bib.bib145)\), typically through elementwise addition followed by an optional normalization or thresholding step\. To compare such composed hypervectors, we measure similarity by the normalized bipolar correlation

\(3\)δ​\(a,b\)=1D​∑u=0D−1a​\[u\]​b​\[u\],\\delta\(a,b\)=\\frac\{1\}\{D\}\\sum\_\{u=0\}^\{D\-1\}a\[u\]\\,b\[u\],which takes values in\[−1,1\]\[\-1,1\], equals11whena=ba=b, and is typically close to0for unrelated hypervectors\. Together, these operations allow HDC systems to represent structured objects such as tuples, sequences, and graphs while retaining low computational cost\.

HDC decomposition problem\.Although HDC operations make information composition highly efficient, recovering the underlying factors from a composite representation is computationally difficult\. In particular, if a composite hypervector is constructed by bindingFFfactors and each factor is selected from a codebook of sizeNN, then exact decomposition requires searching overNFN^\{F\}possible tuples in the worst case\. Thus the search space grows exponentially with the number of factors, yielding a computational complexity of𝒪​\(NF\)\\mathcal\{O\}\(N^\{F\}\)before accounting for the cost of evaluating the similarity of each candidate\. In this work, we focus on the decomposition problem for bound hypervectors\.

### 2\.2\.Quantum Computing

Quantum computing basics\.Quantum computing\(Nielsen and Chuang,[2010](https://arxiv.org/html/2607.11936#bib.bib154)\)provides a computational model based on the manipulation of quantum states through unitary operations\. The fundamental unit of quantum information is the*qubit*, whose state lies in a two\-dimensional complex vector space spanned by the computational basis states\|0⟩\\ket\{0\}and\|1⟩\\ket\{1\}\. Annn\-qubit system lies in a2n2^\{n\}\-dimensional Hilbert space\(Vourdas,[2004](https://arxiv.org/html/2607.11936#bib.bib171)\), enabling a compact representation of exponentially large state spaces using only a linear number of physical qubits\. Computation is performed by applying quantum gates, which are unitary transformations acting on one or more qubits\. By exploiting superposition and interference, quantum circuits can amplify amplitudes corresponding to desirable solutions while suppressing others\. A canonical example is Grover’s search algorithm\(Grover,[1996](https://arxiv.org/html/2607.11936#bib.bib147)\), which achieves a quadratic speedup for unstructured search\.

Qubit scalability\.A central challenge in practical quantum computing is the limited scalability of reliable qubit systems\([J\. Kelly \(2018\)](https://arxiv.org/html/2607.11936#bib.bib159);[22](https://arxiv.org/html/2607.11936#bib.bib169);[J\. Bausch, A\. W\. Senior, F\. J\. Heras, T\. Edlich, A\. Davies, M\. Newman, C\. Jones, K\. Satzinger, M\. Y\. Niu, S\. Blackwell,et al\.\(2024\)](https://arxiv.org/html/2607.11936#bib.bib170)\)\. Unlike classical bits, qubits must preserve coherent quantum states and, when entangled, jointly occupy a tensor\-product Hilbert space\. The difficulty of maintaining coherence, controlling multi\-qubit interactions, and suppressing noise increases rapidly with system size\. As a result, quantum algorithms that require large numbers of qubits are often impractical on current hardware\([J\. Kelly \(2018\)](https://arxiv.org/html/2607.11936#bib.bib159);[20](https://arxiv.org/html/2607.11936#bib.bib160)\)\. This limitation is especially severe for algorithms that require a large number of qubits\.

Quantum HDC decomposition\.Recent work introduced Hyperdimensional Quantum Maximum Finding\(Poduvalet al\.,[2024](https://arxiv.org/html/2607.11936#bib.bib149)\), which applies a modified Grover\-style quantum search procedure to the HDC decomposition problem\. While that approach reduces the search complexity from𝒪​\(NF\)\\mathcal\{O\}\(N^\{F\}\)to𝒪​\(NF\)\\mathcal\{O\}\(\\sqrt\{N^\{F\}\}\), it does so using what we refer to asexplicit hypervector encodings, in which each hypervector dimension is represented by a separate qubit\. For realistic HDC regimes, whereDDis often on the order of10410^\{4\}, this qubit requirement is prohibitively large relative to currently available quantum hardware\([20](https://arxiv.org/html/2607.11936#bib.bib160)\), whose commercially accessible systems are still typically in the low\-hundreds\-of\-qubits regime rather than the tens\-of\-thousands required by such encodings\. In this work, we instead develop a qubit\-efficient quantum HDC decomposition method that uses𝒪​\(log⁡D\)\\mathcal\{O\}\(\\log D\)qubits for hypervector representation rather than𝒪​\(D\)\\mathcal\{O\}\(D\), while preserving the ability to perform decomposition through quantum search\.

## 3\.Problem Formulation

We consider the problem of*codebook\-constrained hypervector decomposition*\. Let

\(4\)Cf=\{hf,0,hf,1,…,hf,N−1\}⊂\{−1,\+1\}D,f∈\{1,…,F\},C\_\{f\}=\\\{h\_\{f,0\},h\_\{f,1\},\\dots,h\_\{f,N\-1\}\\\}\\subset\\\{\-1,\+1\\\}^\{D\},\\quad f\\in\\\{1,\\dots,F\\\},denote theff\-th codebook, whereFFis the number of factors,NNis the number of candidate hypervectors in each codebook, andDDis the hypervector dimension\. A candidate decomposition is specified by a tuple

\(5\)𝐧=\(n1,…,nF\)∈\{0,1,…,N−1\}F\.\\mathbf\{n\}=\(n\_\{1\},\\dots,n\_\{F\}\)\\in\\\{0,1,\\dots,N\-1\\\}^\{F\}\.Given such a tuple, the corresponding composite hypervector is defined by the HDC binding operation

\(6\)b𝐧=h1,n1⊙h2,n2⊙⋯⊙hF,nF,b\_\{\\mathbf\{n\}\}=h\_\{1,n\_\{1\}\}\\odot h\_\{2,n\_\{2\}\}\\odot\\cdots\\odot h\_\{F,n\_\{F\}\},where⊙\\odotdenotes elementwise bipolar multiplication\. Equivalently, for each coordinateu∈\{0,1,…,D−1\}u\\in\\\{0,1,\\dots,D\-1\\\},

\(7\)b𝐧​\[u\]=∏f=1Fhf,nf​\[u\]\.b\_\{\\mathbf\{n\}\}\[u\]=\\prod\_\{f=1\}^\{F\}h\_\{f,n\_\{f\}\}\[u\]\.
We assume that a target hypervectory∈\{−1,\+1\}Dy\\in\\\{\-1,\+1\\\}^\{D\}is generated by binding one entry from each codebook, possibly followed by mild corruption or noise\. The decomposition task is to recover the generating tuple by solving

\(8\)𝐧⋆=arg⁡max𝐧∈\{0,1,…,N−1\}F⁡δ​\(y,b𝐧\),\\mathbf\{n\}^\{\\star\}=\{\\arg\\max\}\_\{\\mathbf\{n\}\\in\\\{0,1,\\dots,N\-1\\\}^\{F\}\}\\delta\(y,b\_\{\\mathbf\{n\}\}\),where

\(9\)δ​\(y,b𝐧\)=1D​∑u=0D−1y​\[u\]​b𝐧​\[u\]\\delta\(y,b\_\{\\mathbf\{n\}\}\)=\\frac\{1\}\{D\}\\sum\_\{u=0\}^\{D\-1\}y\[u\]\\,b\_\{\\mathbf\{n\}\}\[u\]is the normalized bipolar similarity between the target hypervector and the candidate composite hypervector\. This formulation makes the computational bottleneck explicit\. A direct classical method must evaluateδ​\(y,b𝐧\)\\delta\(y,b\_\{\\mathbf\{n\}\}\)for every candidate tuple𝐧∈\{0,1,…,N−1\}F\\mathbf\{n\}\\in\\\{0,1,\\dots,N\-1\\\}^\{F\}\. WithNFN^\{F\}possible tuples and a fixed hypervector dimensionalityDD, the total runtime is

\(10\)𝒪​\(NF​D\)=𝒪​\(NF\),\\mathcal\{O\}\(N^\{F\}D\)=\\mathcal\{O\}\(N^\{F\}\),where the second equality follows becauseDDis treated as a constant\. Thus, the primary computational challenge in hypervector decomposition is the exponential growth in the number of candidate tuples with respect to the number of factorsFF\.

## 4\.Methodology

![Refer to caption](https://arxiv.org/html/2607.11936v1/x2.png)Figure 2\.Similarity\-extraction circuit used to compute the HDC similarity score\. The data register is initialized in\|\+⟩⊗q\\ket\{\+\}^\{\\otimes q\}, the candidate\-bound phase oracleUb𝐧U\_\{b\_\{\\mathbf\{n\}\}\}and target phase oracleUyU\_\{y\}are applied, and a final Walsh–Hadamard transform maps the normalized bipolar similarityδ​\(y,b𝐧\)\\delta\(y,b\_\{\\mathbf\{n\}\}\)into the amplitude of the basis state\|0q⟩\\ket\{0^\{q\}\}\. Measurement of the data register therefore reveals the overlap structure needed for score evaluation\.![Refer to caption](https://arxiv.org/html/2607.11936v1/x3.png)Figure 3\.Compute–phase–uncompute threshold oracle used inside the modified Dürr–Høyer maximum\-finding procedure\. Starting from a superposition over tuple candidates and hypervector coordinates, the circuit performs coherent binding, applies the target\-dependent similarity extraction, computes whether the candidate score exceeds the current thresholdτ\\tau, applies a phase flip to marked tuples, and then uncomputes all work registers\. This reversible structure is required so that amplitude amplification acts only on the tuple register without leaving residual garbage entanglement\.![Refer to caption](https://arxiv.org/html/2607.11936v1/x4.png)Figure 4\.One amplitude\-amplification step used inside the modified Dürr–Høyer maximum\-finding routine\. The threshold oracleOτO\_\{\\tau\}marks tuples whose score exceeds the current incumbent threshold, and the diffusion operatorDA=2​\|A⟩​⟨A\|−ID\_\{A\}=2\\ket\{A\}\\\!\\bra\{A\}\-Iamplifies their amplitudes relative to non\-improving tuples\. This circuit should be interpreted as an internal subroutine of maximum finding rather than as a standalone search algorithm\.![Refer to caption](https://arxiv.org/html/2607.11936v1/x5.png)Figure 5\.Tiny two\-factor example illustrating the overall structure of the proposed framework\. The tuple register is prepared in superposition, controlled selection operatorsSELECT1\\mathrm\{SELECT\}\_\{1\}andSELECT2\\mathrm\{SELECT\}\_\{2\}synthesize the candidate bound hypervector on the shared data register, and the target\-dependent similarity computation extracts the score by concentrating amplitude on\|0q⟩\\ket\{0^\{q\}\}\. The figure provides a minimal concrete instance of coherent binding followed by score extraction\.We now describe the proposed quantum framework\. The central idea is to separate the combinatorial search space of candidate tuples from the coordinate space of the hypervectors themselves\. Unlike prior approaches based onexplicit hypervector encodings, which allocate one qubit per hypervector dimension, we introduce what we calllogarithmic hypervector encodingswithlogarithmic binding encodings\. In this representation, the tuple search is carried by one register, while theDD\-dimensional hypervectors are represented on a shared coordinate register using only𝒪​\(log⁡D\)\\mathcal\{O\}\(\\log D\)qubits\. Similarity is extracted through a similarity computation that maps the HDC score into the amplitude of a distinguished basis state\. This score is then used inside a modified Dürr–Høyer maximum\-finding routine\.

### 4\.1\.Overall Architecture

The quantum state is organized into three logical parts\. The tuple register stores the candidate tuple𝐧\\mathbf\{n\}using the proposed logarithmic binding encoding, while the data register stores the associatedDD\-dimensional hypervector using the proposed logarithmic hypervector encoding\. Ancillary qubits support reversible lookup, phase kickback, score comparison, and threshold marking, which will be introduced later subsection in detail\. IfD=2qD=2^\{q\}, then the data register containsq=log2⁡Dq=\\log\_\{2\}Dqubits\. The tuple register containsF​⌈log2⁡N⌉F\\lceil\\log\_\{2\}N\\rceilqubits\. Operationally, the method proceeds as follows\. The tuple register is prepared in superposition over all candidate tuples\. Conditioned on each tuple branch, the circuit synthesizes the corresponding bound hypervector on the shared data register\. A target\-dependent similarity computation then maps the HDC similarity score into the amplitude of\|0q⟩\\ket\{0^\{q\}\}\. This score is converted into a threshold predicate and used within modified Dürr–Høyer maximum finding\.[Figure 5](https://arxiv.org/html/2607.11936#S4.F5)illustrates the tuple\-conditioned binding stage,[Figure 2](https://arxiv.org/html/2607.11936#S4.F2)shows the similarity extraction stage, and[Figure 3](https://arxiv.org/html/2607.11936#S4.F3)and[Figure 4](https://arxiv.org/html/2607.11936#S4.F4)show the search subroutine\.

### 4\.2\.Logarithmic Hypervector and Binding Encodings

Logarithmic hypervector encoding\.LetD=2qD=2^\{q\}\. Instead of storing a hypervector explicitly acrossDDqubits, we encode it as a phase pattern over the computational basis of aqq\-qubit coordinate register:

\(11\)\|h⟩=1D​∑u=0D−1h​\[u\]​\|u⟩\.\\ket\{h\}=\\frac\{1\}\{\\sqrt\{D\}\}\\sum\_\{u=0\}^\{D\-1\}h\[u\]\\ket\{u\}\.All basis states have equal magnitude1/D1/\\sqrt\{D\}, while the signh​\[u\]∈\{−1,\+1\}h\[u\]\\in\\\{\-1,\+1\\\}is encoded in the phase\. Equivalently, define the diagonal phase oracle

\(12\)Uh​\|u⟩=h​\[u\]​\|u⟩,Uh=diag​\(h​\[0\],h​\[1\],…,h​\[D−1\]\)\.U\_\{h\}\\ket\{u\}=h\[u\]\\ket\{u\},\\quad U\_\{h\}=\\mathrm\{diag\}\(h\[0\],h\[1\],\\dots,h\[D\-1\]\)\.ApplyingUhU\_\{h\}to\|\+⟩⊗q\\ket\{\+\}^\{\\otimes q\}produces the encoded state:

\(13\)Uh​\|\+⟩⊗q=1D​∑u=0D−1h​\[u\]​\|u⟩\.U\_\{h\}\\ket\{\+\}^\{\\otimes q\}=\\frac\{1\}\{\\sqrt\{D\}\}\\sum\_\{u=0\}^\{D\-1\}h\[u\]\\ket\{u\}\.This reduces the qubit cost of representing aDD\-dimensional hypervector from𝒪​\(D\)\\mathcal\{O\}\(D\)to𝒪​\(log⁡D\)\\mathcal\{O\}\(\\log D\)\.

Example 1:Logarithmic\-qubit hypervector encodingSupposeD=8D=8, so the data register hasq=3q=3qubits\. Leth=\[\+1,−1,\+1,−1,−1,\+1,\+1,−1\]\.h=\[\+1,\-1,\+1,\-1,\-1,\+1,\+1,\-1\]\.Then\|h⟩=18​\(\|0⟩−\|1⟩\+\|2⟩−\|3⟩−\|4⟩\+\|5⟩\+\|6⟩−\|7⟩\)\.\\ket\{h\}=\\frac\{1\}\{\\sqrt\{8\}\}\\bigl\(\\ket\{0\}\-\\ket\{1\}\+\\ket\{2\}\-\\ket\{3\}\-\\ket\{4\}\+\\ket\{5\}\+\\ket\{6\}\-\\ket\{7\}\\bigr\)\.Thus a dense eight\-dimensional hypervector is represented using only three qubits\.

Logarithmic binding encoding\.Binding in bipolar hypervectors is multiplicative in each hyperdimension\. If

\(14\)b=a\(1\)⊙a\(2\)⊙⋯⊙a\(F\),b=a^\{\(1\)\}\\odot a^\{\(2\)\}\\odot\\cdots\\odot a^\{\(F\)\},then for every dimensionuu,

\(15\)b​\[u\]=∏f=1Fa\(f\)​\[u\]\.b\[u\]=\\prod\_\{f=1\}^\{F\}a^\{\(f\)\}\[u\]\.Under the proposed logarithmic hypervector encoding, this implies that the phase oracle of the bound hypervector is simply the product of the phase oracles of its factors:

\(16\)Ub=∏f=1FUa\(f\)\.U\_\{b\}=\\prod\_\{f=1\}^\{F\}U\_\{a^\{\(f\)\}\}\.Since all factor oracles are diagonal in the same computational basis, the multiplication is exact and introduces no additional representational overhead\. Therefore, for any fixed candidate tuple𝐧=\(n1,…,nF\)\\mathbf\{n\}=\(n\_\{1\},\\dots,n\_\{F\}\), the corresponding bound hypervector can be represented as

\(17\)\|b𝐧⟩=Ub𝐧​\|\+⟩⊗q,Ub𝐧=∏f=1FUf,nf\.\\ket\{b\_\{\\mathbf\{n\}\}\}=U\_\{b\_\{\\mathbf\{n\}\}\}\\ket\{\+\}^\{\\otimes q\},\\qquad U\_\{b\_\{\\mathbf\{n\}\}\}=\\prod\_\{f=1\}^\{F\}U\_\{f,n\_\{f\}\}\.This defines the logarithmic binding encoding for an individual candidate tuple\.

### 4\.3\.Hypervector Lookup Operator

The logarithmic hypervector encoding described above assumes coherent access to individual hypervector coordinateshf,j​\[u\]h\_\{f,j\}\[u\]for each codebook entryhf,jh\_\{f,j\}\. To realize this access within a circuit model, we introduce ahypervector lookup operator, which retrieves the sign of theuu\-th coordinate of the selected codebook hypervector and converts it into a quantum\-computable form\. For each factorff, define the binary lookup table

\(18\)Tf​\(j,u\)=\{0,hf,j​\[u\]=\+1,1,hf,j​\[u\]=−1\.T\_\{f\}\(j,u\)=\\begin\{cases\}0,&h\_\{f,j\}\[u\]=\+1,\\\\ 1,&h\_\{f,j\}\[u\]=\-1\.\\end\{cases\}This is a classical sign table for the codebook\. The corresponding reversible lookup operator is

\(19\)Lf:\|j⟩​\|u⟩​\|b⟩↦\|j⟩​\|u⟩​\|b⊕Tf​\(j,u\)⟩\.L\_\{f\}:\\ket\{j\}\\ket\{u\}\\ket\{b\}\\mapsto\\ket\{j\}\\ket\{u\}\\ket\{b\\oplus T\_\{f\}\(j,u\)\}\.At the matrix level,

\(20\)Lf=∑j=0N−1∑u=0D−1\|j,u⟩​⟨j,u\|⊗XTf​\(j,u\)\.L\_\{f\}=\\sum\_\{j=0\}^\{N\-1\}\\sum\_\{u=0\}^\{D\-1\}\\ket\{j,u\}\\\!\\bra\{j,u\}\\otimes X^\{T\_\{f\}\(j,u\)\}\.
When the ancilla is initialized in\|−⟩=\(\|0⟩−\|1⟩\)/2\\ket\{\-\}=\(\\ket\{0\}\-\\ket\{1\}\)/\\sqrt\{2\}, phase kickback converts the Boolean lookup into the desired sign phase:

\(21\)Lf​\|j⟩​\|u⟩​\|−⟩=\(−1\)Tf​\(j,u\)​\|j⟩​\|u⟩​\|−⟩=hf,j​\[u\]​\|j⟩​\|u⟩​\|−⟩\.L\_\{f\}\\ket\{j\}\\ket\{u\}\\ket\{\-\}=\(\-1\)^\{T\_\{f\}\(j,u\)\}\\ket\{j\}\\ket\{u\}\\ket\{\-\}=h\_\{f,j\}\[u\]\\ket\{j\}\\ket\{u\}\\ket\{\-\}\.Thus the lookup operator induces the exact controlled phase oracle

\(22\)U~f=∑j=0N−1\|j⟩​⟨j\|⊗Uf,j,\\widetilde\{U\}\_\{f\}=\\sum\_\{j=0\}^\{N\-1\}\\ket\{j\}\\\!\\bra\{j\}\\otimes U\_\{f,j\},where

\(23\)Uf,j=diag​\(hf,j​\[0\],hf,j​\[1\],…,hf,j​\[D−1\]\)\.U\_\{f,j\}=\\mathrm\{diag\}\\bigl\(h\_\{f,j\}\[0\],h\_\{f,j\}\[1\],\\dots,h\_\{f,j\}\[D\-1\]\\bigr\)\.
Example 2:Dense lookup for a tiny codebookLetN=2N=2andD=4D=4, withh0=\[\+1,−1,\+1,−1\],h1=\[−1,−1,\+1,\+1\]\.h\_\{0\}=\[\+1,\-1,\+1,\-1\],\\qquad h\_\{1\}=\[\-1,\-1,\+1,\+1\]\.ThenT=\[01011100\],T=\\begin\{bmatrix\}0&1&0&1\\\\ 1&1&0&0\\end\{bmatrix\},and the lookup inducesU~=\|0⟩​⟨0\|⊗diag​\(\+1,−1,\+1,−1\)\+\|1⟩​⟨1\|⊗diag​\(−1,−1,\+1,\+1\)\.\\widetilde\{U\}=\\ket\{0\}\\\!\\bra\{0\}\\otimes\\mathrm\{diag\}\(\+1,\-1,\+1,\-1\)\+\\ket\{1\}\\\!\\bra\{1\}\\otimes\\mathrm\{diag\}\(\-1,\-1,\+1,\+1\)\.This example shows how arbitrary dense codebooks are supported\.

### 4\.4\.Coherent Binding Over Candidates

Having defined the logarithmic binding encoding for a fixed tuple, we now show how to construct it coherently across the entire candidate space\. The key idea is to place the tuple register in superposition and apply tuple\-controlled phase operators on a shared data register\. This yields a joint quantum state in which each tuple branch is paired with the logarithmic hypervector encoding of its corresponding bound hypervector\. The tuple register is initialized in the uniform superposition

\(24\)\|A⟩=1NF​∑𝐧∈\{0,1,…,N−1\}F\|𝐧⟩,\|𝐧⟩=\|n1⟩​⋯​\|nF⟩,\\ket\{A\}=\\frac\{1\}\{\\sqrt\{N^\{F\}\}\}\\sum\_\{\\mathbf\{n\}\\in\\\{0,1,\\dots,N\-1\\\}^\{F\}\}\\ket\{\\mathbf\{n\}\},\\qquad\\ket\{\\mathbf\{n\}\}=\\ket\{n\_\{1\}\}\\cdots\\ket\{n\_\{F\}\},and the data register is initialized in\|\+⟩⊗q\\ket\{\+\}^\{\\otimes q\}\. For each factorff, define the controlled selection operator

\(25\)SELECTf=∑j=0N−1\|j⟩​⟨j\|nf⊗Uf,j\.\\mathrm\{SELECT\}\_\{f\}=\\sum\_\{j=0\}^\{N\-1\}\\ket\{j\}\\\!\\bra\{j\}\_\{n\_\{f\}\}\\otimes U\_\{f,j\}\.The full tuple\-conditioned binding operator is

\(26\)BIND=∏f=1FSELECTf\.\\mathrm\{BIND\}=\\prod\_\{f=1\}^\{F\}\\mathrm\{SELECT\}\_\{f\}\.Because allUf,jU\_\{f,j\}are diagonal on the shared data register, theSELECTf\\mathrm\{SELECT\}\_\{f\}commute\. ApplyingBIND\\mathrm\{BIND\}yields

\(27\)BIND​\(\|A⟩⊗\|\+⟩⊗q\)=1NF​∑𝐧∈\{0,1,…,N−1\}F\|𝐧⟩​\|b𝐧⟩\.\\mathrm\{BIND\}\\bigl\(\\ket\{A\}\\otimes\\ket\{\+\}^\{\\otimes q\}\\bigr\)=\\frac\{1\}\{\\sqrt\{N^\{F\}\}\}\\sum\_\{\\mathbf\{n\}\\in\\\{0,1,\\dots,N\-1\\\}^\{F\}\}\\ket\{\\mathbf\{n\}\}\\ket\{b\_\{\\mathbf\{n\}\}\}\.
This identity is central\. It shows that all candidate bindings are represented simultaneously using one sharedqq\-qubit data register\. The exponential search space is carried by the tuple register, not by duplicating the hypervector representation\.[Figure 5](https://arxiv.org/html/2607.11936#S4.F5)depicts this idea in a small two\-factor circuit\.

Example 3:Two\-factor coherent bindingConsiderF=2F=2,N=2N=2, andD=8D=8\. The tuple register spans the four branches\|00⟩,\|01⟩,\|10⟩,\|11⟩\.\\ket\{00\},\\ \\ket\{01\},\\ \\ket\{10\},\\ \\ket\{11\}\.After applyingSELECT1\\mathrm\{SELECT\}\_\{1\}andSELECT2\\mathrm\{SELECT\}\_\{2\}, the joint state becomes12​\(\|00⟩​\|b00⟩\+\|01⟩​\|b01⟩\+\|10⟩​\|b10⟩\+\|11⟩​\|b11⟩\)\.\\frac\{1\}\{2\}\\bigl\(\\ket\{00\}\\ket\{b\_\{00\}\}\+\\ket\{01\}\\ket\{b\_\{01\}\}\+\\ket\{10\}\\ket\{b\_\{10\}\}\+\\ket\{11\}\\ket\{b\_\{11\}\}\\bigr\)\.For a fixed hyperdimension label\|u⟩\\ket\{u\}, the effective sign may differ across tuple branches because the sign is attached to the joint basis state\|𝐧⟩​\|u⟩\\ket\{\\mathbf\{n\}\}\\ket\{u\}, not to\|u⟩\\ket\{u\}alone\.

### 4\.5\.Similarity Extraction by Walsh–Hadamard Overlap

Once a candidate bound hypervector has been prepared on the data register, we evaluate its similarity with the target hypervectoryy\. Define the target phase oracle

\(28\)Uy​\|u⟩=y​\[u\]​\|u⟩\.U\_\{y\}\\ket\{u\}=y\[u\]\\ket\{u\}\.Acting on\|b𝐧⟩\\ket\{b\_\{\\mathbf\{n\}\}\}, this yields

\(29\)Uy​\|b𝐧⟩=1D​∑u=0D−1y​\[u\]​b𝐧​\[u\]​\|u⟩\.U\_\{y\}\\ket\{b\_\{\\mathbf\{n\}\}\}=\\frac\{1\}\{\\sqrt\{D\}\}\\sum\_\{u=0\}^\{D\-1\}y\[u\]\\,b\_\{\\mathbf\{n\}\}\[u\]\\ket\{u\}\.Applying the Walsh–Hadamard transformH⊗qH^\{\\otimes q\}maps the average of these signed amplitudes to the basis state\|0q⟩\\ket\{0^\{q\}\}\. The amplitude on\|0q⟩\\ket\{0^\{q\}\}is therefore

\(30\)δ𝐧=1D​∑u=0D−1y​\[u\]​b𝐧​\[u\]\.\\delta\_\{\\mathbf\{n\}\}=\\frac\{1\}\{D\}\\sum\_\{u=0\}^\{D\-1\}y\[u\]\\,b\_\{\\mathbf\{n\}\}\[u\]\.This is exactly the HDC similarity score\. Hence the decomposition score is encoded as an amplitude that can be interrogated by quantum search subroutines\.[Figure 2](https://arxiv.org/html/2607.11936#S4.F2)shows this similarity\-extraction circuit\.

Example 4:Exact similarity extractionLetD=4D=4, lety=\[\+1,−1,\+1,−1\],y=\[\+1,\-1,\+1,\-1\],and first considerb𝐧=\[\+1,−1,\+1,−1\]\.b\_\{\\mathbf\{n\}\}=\[\+1,\-1,\+1,\-1\]\.Thenδ𝐧=1\\delta\_\{\\mathbf\{n\}\}=1, and after applyingUyU\_\{y\}followed byH⊗2H^\{\\otimes 2\}, all amplitude concentrates on\|00⟩\\ket\{00\}\. If insteadb𝐧=\[\+1,\+1,−1,−1\],b\_\{\\mathbf\{n\}\}=\[\+1,\+1,\-1,\-1\],thenδ𝐧=0\\delta\_\{\\mathbf\{n\}\}=0, and the amplitude on\|00⟩\\ket\{00\}vanishes\. The similarity\-extraction circuit therefore separates correct and incorrect candidates through amplitude concentration\.

### 4\.6\.Maximum Finding via Modified Dürr–Høyer Quantum Search

The similarity\-extraction circuit yields a score oracle\. We now embed it in a modified Dürr–Høyer maximum\-finding procedure\. The modification lies not in the outer logic of Dürr–Høyer itself, but in the way the comparison score is produced and marked: our score oracle is implemented through a logarithmic\-qubit hypervector circuit rather than through explicit hypervector\-state storage\.

Threshold oracle\.Letτ∈\[−1,1\]\\tau\\in\[\-1,1\]be the current threshold\. Define the Boolean predicate

\(31\)fτ​\(𝐧\)=\{1,δ𝐧\>τ,0,δ𝐧≤τ\.f\_\{\\tau\}\(\\mathbf\{n\}\)=\\begin\{cases\}1,&\\delta\_\{\\mathbf\{n\}\}\>\\tau,\\\\ 0,&\\delta\_\{\\mathbf\{n\}\}\\leq\\tau\.\\end\{cases\}The corresponding phase\-marking oracle is

\(32\)Oτ​\|𝐧⟩=\(−1\)fτ​\(𝐧\)​\|𝐧⟩\.O\_\{\\tau\}\\ket\{\\mathbf\{n\}\}=\(\-1\)^\{f\_\{\\tau\}\(\\mathbf\{n\}\)\}\\ket\{\\mathbf\{n\}\}\.At the circuit level, this oracle must be implemented reversibly\. The score is first computed into workspace, then compared againstτ\\tau, then converted into a phase flip, and finally uncomputed:

\(33\)\|𝐧⟩​\|0⟩⟶\|𝐧⟩​\|fτ​\(𝐧\)⟩⟶\(−1\)fτ​\(𝐧\)​\|𝐧⟩​\|fτ​\(𝐧\)⟩⟶\(−1\)fτ​\(𝐧\)​\|𝐧⟩​\|0⟩\.\\ket\{\\mathbf\{n\}\}\\ket\{0\}\\longrightarrow\\ket\{\\mathbf\{n\}\}\\ket\{f\_\{\\tau\}\(\\mathbf\{n\}\)\}\\longrightarrow\(\-1\)^\{f\_\{\\tau\}\(\\mathbf\{n\}\)\}\\ket\{\\mathbf\{n\}\}\\ket\{f\_\{\\tau\}\(\\mathbf\{n\}\)\}\\longrightarrow\(\-1\)^\{f\_\{\\tau\}\(\\mathbf\{n\}\)\}\\ket\{\\mathbf\{n\}\}\\ket\{0\}\.The final uncomputation is necessary to avoid residual entanglement with work registers\.[Figure 3](https://arxiv.org/html/2607.11936#S4.F3)shows this compute–phase–uncompute structure\.

Example 5:Threshold markingSuppose three candidate tuples have similaritiesδ𝐧1=0\.82,δ𝐧2=0\.41,δ𝐧3=0\.76\.\\delta\_\{\\mathbf\{n\}\_\{1\}\}=0\.82,\\qquad\\delta\_\{\\mathbf\{n\}\_\{2\}\}=0\.41,\\qquad\\delta\_\{\\mathbf\{n\}\_\{3\}\}=0\.76\.If the threshold isτ=0\.75\\tau=0\.75, thenfτ​\(𝐧1\)=1,fτ​\(𝐧2\)=0,fτ​\(𝐧3\)=1\.f\_\{\\tau\}\(\\mathbf\{n\}\_\{1\}\)=1,\\qquad f\_\{\\tau\}\(\\mathbf\{n\}\_\{2\}\)=0,\\qquad f\_\{\\tau\}\(\\mathbf\{n\}\_\{3\}\)=1\.The threshold oracle therefore flips phase for𝐧1\\mathbf\{n\}\_\{1\}and𝐧3\\mathbf\{n\}\_\{3\}, while leaving𝐧2\\mathbf\{n\}\_\{2\}unchanged\.

Maximum finding procedure\.We now embed the threshold oracle into the Dürr–Høyer framework\. The procedure maintains an incumbent tuple𝐧best\\mathbf\{n\}\_\{\\mathrm\{best\}\}, uses its score as the current threshold, and searches for a tuple whose score exceeds that threshold\. If one is found, the incumbent is updated; if not, the current incumbent is retained\. Each improvement step is implemented by amplitude amplification using the oracleOτO\_\{\\tau\}and the diffusion operator

\(34\)DA=2​\|A⟩​⟨A\|−I\.D\_\{A\}=2\\ket\{A\}\\\!\\bra\{A\}\-I\.[Figure 4](https://arxiv.org/html/2607.11936#S4.F4)shows one such iteration\. The resulting algorithm is best understood as modified Dürr–Høyer maximum finding rather than as a separate Grover search procedure\. Grover\-style amplification appears as an internal subroutine, but the outer logic is a maximum\-finding routine over tuple scores\.

The full pipeline is summarized in[Algorithm 1](https://arxiv.org/html/2607.11936#alg1)\. The figures show the circuit structure of the core subroutines, while the pseudocode summarizes how these subroutines are assembled into the complete decomposition procedure\.

1:Prepare the tuple register in

\|A⟩=1NF​∑𝐧\|𝐧⟩\\ket\{A\}=\\frac\{1\}\{\\sqrt\{N^\{F\}\}\}\\sum\_\{\\mathbf\{n\}\}\\ket\{\\mathbf\{n\}\}
2:Prepare the data register in

\|\+⟩⊗q\\ket\{\+\}^\{\\otimes q\}
3:Construct the tuple\-conditioned binding circuit

BIND\\mathrm\{BIND\}
4:Construct the target overlap circuit using

UyU\_\{y\}and

H⊗qH^\{\\otimes q\}
5:Initialize an incumbent tuple

𝐧best\\mathbf\{n\}\_\{\\mathrm\{best\}\}
6:repeat

7:Set

τ←δ𝐧best\\tau\\leftarrow\\delta\_\{\\mathbf\{n\}\_\{\\mathrm\{best\}\}\}
8:Build the threshold oracle

OτO\_\{\\tau\}
9:Apply modified Dürr–Høyer search to find an improving tuple

10:Update

𝐧best\\mathbf\{n\}\_\{\\mathrm\{best\}\}if an improving tuple is found

11:untiltermination

12:Measure the tuple register and return

𝐧best\\mathbf\{n\}\_\{\\mathrm\{best\}\}

Algorithm 1Qubit\-Efficient HDC Decomposition

## 5\.Experimental Results

We evaluate the proposed logarithmic hypervector and logarithmic binding encoding\-based quantum framework from three complementary perspectives:\(i\)*whether the circuit computes the intended HDC similarity score correctly*,\(ii\)*whether the resulting decomposition pipeline reliably recovers the correct tuple across a broad range of problem settings*, and\(iii\)*whether the proposed representation provides favorable qubit\-scaling behavior relative to the prior explicit hypervector encoding\-based quantum baseline*\.

### 5\.1\.Experimental Setup

All experiments use synthetic dense bipolar codebooks with entries in\{−1,\+1\}D\\\{\-1,\+1\\\}^\{D\}\. For each trial, we randomly generateFFcodebooks, each containingNNcandidate hypervectors, sample one codeword from each codebook, and form the target hypervector by bipolar binding\. When noise is considered, we corrupt the target by randomly flipping a prescribed fraction of coordinates\. This produces controlled decomposition instances with known ground\-truth tuples\. For executable quantum experiments, we implement the proposed HDC decomposition circuit in Qiskit\(Javadi\-Abhariet al\.,[2024](https://arxiv.org/html/2607.11936#bib.bib172)\)and simulate it with Qiskit Aer\. We use both statevector simulation, to verify exact amplitude behavior, and shot\-based simulation, to evaluate finite\-sampling effects under realistic measurement budgets\. The primary shot counts used in the experiments are256256,10241024, and20482048, depending on each evaluation\. For decomposition experiments, we evaluate small\-to\-moderate settings that remain executable under repeated circuit simulation, including factorsF∈\{2,3,4,5\}F\\in\\\{2,3,4,5\\\}, codebook sizesN∈\{2,3,4,5\}N\\in\\\{2,3,4,5\\\}, and hypervector dimensionsD∈\{8,16,32,64\}D\\in\\\{8,16,32,64\\\}, subject to executable search\-space limits\.

### 5\.2\.Correctness of the Similarity\-Extraction Circuit

![Refer to caption](https://arxiv.org/html/2607.11936v1/x6.png)Figure 6\.Correctness of the proposed logarithmic\-qubit similarity\-extraction circuit\.\(a\)Exact HDC similarity versus the amplitude extracted from statevector simulation, showing near\-perfect agreement with the identity line\.\(b\)Exact similarity magnitude versus shot\-based estimates for multiple shot budgets\.\(c\)Dense setting\-wise summary of estimation error across representative\(F,N,D\)\(F,N,D\)configurations\. Across all panels, the results confirm that the proposed circuit computes the intended similarity signal and that measurement error decreases as the shot budget increases\.[Figure 6](https://arxiv.org/html/2607.11936#S5.F6)evaluates whether the proposed logarithmic hypervector encoding\-based similarity\-extraction circuit correctly computes the intended HDC similarity score\. In[Figure 6](https://arxiv.org/html/2607.11936#S5.F6)\(a\), the amplitude extracted from exact statevector simulation lies almost perfectly on the identity line when plotted against the analytical HDC similarity\. This confirms that the circuit implements the desired similarity computation exactly at the wavefunction level\. Equivalently, the amplitude associated with\|0q⟩\\ket\{0^\{q\}\}matches the theoretical scoreδ​\(y,b𝐧\)\\delta\(y,b\_\{\\mathbf\{n\}\}\), consistent with the construction described in the methodology\.[Figure 6](https://arxiv.org/html/2607.11936#S5.F6)\(b\) shows that this agreement is preserved under finite\-shot simulation\. Although measurement noise introduces dispersion around the ideal line, the shot\-based estimates become increasingly concentrated near the exact similarity magnitude as the number of shots increases\.[Figure 6](https://arxiv.org/html/2607.11936#S5.F6)\(c\) further summarizes the estimation error across a broad range of experimental settings, showing that the circuit remains accurate and stable over diverse decomposition configurations\. Overall, these results provide strong empirical evidence that the proposed circuit faithfully and reliably computes the intended HDC similarity score\.

### 5\.3\.Decomposition Accuracy Across Problem Settings

![Refer to caption](https://arxiv.org/html/2607.11936v1/x7.png)Figure 7\.Decomposition accuracy of the proposed method across problem settings\.\(a\)Exact recovery rate versus the number of factorsFF\.\(b\)Exact recovery rate versus the number of candidate hypervectors per factorNN\.\(c\)Exact recovery rate versus the hypervector dimensionDD\.\(d\)Exact recovery rate under increasing target corruption\. Shaded regions indicate one standard deviation across repeated trials\.We next evaluate the end\-to\-end decomposition accuracy of the proposed method over a broad range of executable settings, as summarized in[Figure 7](https://arxiv.org/html/2607.11936#S5.F7)\. In particular, we vary the number of factorsFF, the number of candidate hypervectors per factorNN, and the hypervector dimensionDD, with the corresponding results shown in[Figure 7](https://arxiv.org/html/2607.11936#S5.F7)\(a\),[Figure 7](https://arxiv.org/html/2607.11936#S5.F7)\(b\), and[Figure 7](https://arxiv.org/html/2607.11936#S5.F7)\(c\), respectively\. Across all tested settings, the proposed method achieves100%100\\%exact recovery, demonstrating that the logarithmic\-qubit construction preserves the correctness of HDC decomposition over diverse problem configurations\.[Figure 7](https://arxiv.org/html/2607.11936#S5.F7)\(d\) further examines robustness under increasing target corruption\. The proposed method maintains100%100\\%exact recovery under moderate noise levels, indicating that the decomposition procedure remains stable even when the target hypervector is partially corrupted\. Taken together, these results show that the proposed framework is not only correct in ideal settings, but also accurate and robust across a broad range of decomposition regimes and moderate levels of target corruption\.

![Refer to caption](https://arxiv.org/html/2607.11936v1/x8.png)Figure 8\.Decomposition\-specific search dynamics under the modified Dürr–Høyer procedure\.\(a\)Probability trajectory of the true decomposition tuple and the strongest incorrect tuple for a representative instance\.\(b\)Heatmap of the full tuple\-state probability distribution across search iterations\. The plots show that probability mass is amplified toward the correct decomposition tuple and that the separation between the correct and strongest incorrect candidates increases over the search process\.We further examine the search dynamics of the proposed method on actual decomposition instances in[Figure 8](https://arxiv.org/html/2607.11936#S5.F8)\.[Figure 8](https://arxiv.org/html/2607.11936#S5.F8)\(a\) shows that the probability of the true tuple increases steadily across search iterations, while the strongest incorrect tuple remains consistently lower\. This is precisely the behavior intended by the modified Dürr–Høyer procedure: amplitude is progressively concentrated on tuples whose scores exceed the current threshold, and when the correct tuple is the unique highest\-scoring candidate, its probability should become dominant after an appropriate number of iterations\.[Figure 8](https://arxiv.org/html/2607.11936#S5.F8)\(b\) provides a more complete view of this evolution through a heatmap over the tuple\-state distribution\. Most candidate tuples remain at very low probability throughout the search, whereas the true tuple is selectively amplified\. The highlighted reference box marks the correct tuple and shows that the dominant probability mass aligns with the intended decomposition candidate, rather than diffusing arbitrarily across the search space\. These results provide direct evidence that the proposed search procedure behaves as expected on the decomposition problem itself, not merely on an abstract search benchmark\.

### 5\.4\.Qubit Efficiency

![Refer to caption](https://arxiv.org/html/2607.11936v1/x9.png)Figure 9\.Qubit requirement comparison between the proposed logarithmic hypervector encoding and an explicit hypervector encoding\-based quantum baseline across different hyperdimensionsDD\. For small, executable settings, we report the actual transpiled circuit width\. For larger values ofDD, where full circuit simulation is no longer practical, we report the theoretically derived*expected*qubit count\.\(a\)Actual transpiled circuit width on executable instances \(left\) and theory\-driven qubit scaling based on the expected number of required qubits \(right\)\.\(b\)Fine\-grained qubit scalability analysis across different numbers of factorsFF, including the qubit reduction factor achieved by the proposed method \(left\) and the proposed qubit requirement across hypervector dimensions for different values ofFF\(right\)\. These results highlight the central qubit\-efficiency advantage of our framework\.[Figure 9](https://arxiv.org/html/2607.11936#S5.F9)directly evaluates the central architectural claim of the paper: the proposed framework is substantially more qubit\-efficient than explicit\-dimension quantum encodings\. As shown in the left panel of[Figure 9](https://arxiv.org/html/2607.11936#S5.F9)\(a\), even the executable circuit instances already require fewer qubits under the proposed design than under the explicit baseline\. The scalability gap becomes far more pronounced in the larger, theory\-driven analysis\. In the right panel of[Figure 9](https://arxiv.org/html/2607.11936#S5.F9)\(a\), the required number of qubits under the proposed method grows only logarithmically with the hypervector dimensionDD, whereas the explicit baseline grows linearly inDD\. This distinction is especially important in the high\-dimensional regime where HDC is most useful\. The left panel of[Figure 9](https://arxiv.org/html/2607.11936#S5.F9)\(b\) shows that the qubit reduction factor increases rapidly asDDgrows, reaching approximately2,000×2\{,\}000\\timesin the evaluated range\. The right panel of[Figure 9](https://arxiv.org/html/2607.11936#S5.F9)\(b\) further illustrates that the proposed method remains compact even as the problem dimension increases, whereas the explicit encoding quickly becomes impractical\. Overall, these results provide strong evidence that the proposed logarithmic\-qubit design resolves a fundamental scalability limitation of prior explicit hypervector encodings\.

## 6\.Conclusion

We presented a qubit\-efficient quantum framework for hyperdimensional decomposition based on logarithmic hypervector encoding, logarithmic binding encoding, and an explicit hypervector lookup operator\. The proposed method preserves the𝒪​\(NF\)\\mathcal\{O\}\(\\sqrt\{N^\{F\}\}\)quantum search complexity of prior work while reducing hypervector representation cost from𝒪​\(D\)\\mathcal\{O\}\(D\)qubits to𝒪​\(log⁡D\)\\mathcal\{O\}\(\\log D\)\. Experiments verified correct similarity computation, accurate decomposition in executable regimes, and substantial qubit savings, reaching approximately2,000×2\{,\}000\\timesreduction in the evaluated high\-dimensional setting\. These results show that qubit\-efficient circuit design is essential for making quantum HDC decomposition meaningfully closer to practical implementation\.

###### Acknowledgements\.

This work was supported in part by the DARPA Young Faculty Award, the National Science Foundation \(NSF\) under Grants \#2127780, \#2319198, \#2321840, \#2312517, and \#2235472, the Semiconductor Research Corporation \(SRC\), the Office of Naval Research through the Young Investigator Program Award, and Grants \#N00014\-21\-1\-2225 and N00014\-24\-1\-2547, Army Research Office Grant \#W911NF2410360\. Additionally, support was provided by the Air Force Office of Scientific Research under Award \#FA9550\-22\-1\-0253\.

## References

- H\. E\. Barkam, S\. Yun, H\. Chen, P\. Gensler, A\. Mema, A\. Ding, G\. Michelogiannakis, H\. Amrouch, and M\. Imani \(2023\)Reliable hyperdimensional reasoning on unreliable emerging technologies\.In2023 IEEE/ACM International Conference on Computer Aided Design \(ICCAD\),pp\. 1–9\.Cited by:[§1](https://arxiv.org/html/2607.11936#S1.p2.1)\.
- J\. Bausch, A\. W\. Senior, F\. J\. Heras, T\. Edlich, A\. Davies, M\. Newman, C\. Jones, K\. Satzinger, M\. Y\. Niu, S\. Blackwell,et al\.\(2024\)Learning high\-accuracy error decoding for quantum processors\.Nature635\(8040\),pp\. 834–840\.Cited by:[§1](https://arxiv.org/html/2607.11936#S1.p4.6),[§2\.2](https://arxiv.org/html/2607.11936#S2.SS2.p2.1)\.
- M\. Boyer, G\. Brassard, P\. Høyer, and A\. Tapp \(1998\)Tight bounds on quantum searching\.Fortschritte der Physik: Progress of Physics46\(4\-5\),pp\. 493–505\.Cited by:[§1](https://arxiv.org/html/2607.11936#S1.p1.1)\.
- G\. Brassard, P\. Hoyer, M\. Mosca, and A\. Tapp \(2000\)Quantum amplitude amplification and estimation\.arXiv preprint quant\-ph/0005055\.Cited by:[§1](https://arxiv.org/html/2607.11936#S1.p1.1)\.
- A\. M\. Dalzell, S\. McArdle, M\. Berta, P\. Bienias, C\. Chen, A\. Gilyén, C\. T\. Hann, M\. J\. Kastoryano, E\. T\. Khabiboulline, A\. Kubica,et al\.\(2023\)Quantum algorithms: a survey of applications and end\-to\-end complexities\.arXiv preprint arXiv:2310\.03011\.Cited by:[§1](https://arxiv.org/html/2607.11936#S1.p1.1)\.
- C\. Durr and P\. Hoyer \(1996\)A quantum algorithm for finding the minimum\.arXiv preprint quant\-ph/9607014\.Cited by:[§1](https://arxiv.org/html/2607.11936#S1.p5.4)\.
- E\. P\. Frady, S\. J\. Kent, B\. A\. Olshausen, and F\. T\. Sommer \(2020\)Resonator networks, 1: an efficient solution for factoring high\-dimensional, distributed representations of data structures\.Neural computation32\(12\),pp\. 2311–2331\.Cited by:[§1](https://arxiv.org/html/2607.11936#S1.p3.3)\.
- L\. K\. Grover \(1996\)A fast quantum mechanical algorithm for database search\.InProceedings of the twenty\-eighth annual ACM symposium on Theory of computing,pp\. 212–219\.Cited by:[§1](https://arxiv.org/html/2607.11936#S1.p1.1),[§1](https://arxiv.org/html/2607.11936#S1.p4.6),[§2\.2](https://arxiv.org/html/2607.11936#S2.SS2.p1.4)\.
- A\. Javadi\-Abhari, M\. Treinish, K\. Krsulich, C\. J\. Wood, J\. Lishman, J\. Gacon, S\. Martiel, P\. D\. Nation, L\. S\. Bishop, A\. W\. Cross,et al\.\(2024\)Quantum computing with qiskit\.arXiv preprint arXiv:2405\.08810\.Cited by:[§5\.1](https://arxiv.org/html/2607.11936#S5.SS1.p1.9)\.
- P\. Kanerva \(2009\)Hyperdimensional computing: an introduction to computing in distributed representation with high\-dimensional vectors\.Cognitive Computation\.Cited by:[§1](https://arxiv.org/html/2607.11936#S1.p2.1),[§2\.1](https://arxiv.org/html/2607.11936#S2.SS1.p1.5),[§2\.1](https://arxiv.org/html/2607.11936#S2.SS1.p1.9)\.
- J\. Kelly \(2018\)Google Research\.Note:Posted by Julian Kelly, Research Scientist, Quantum AI LabExternal Links:[Link](https://research.google/blog/a-preview-of-bristlecone-googles-new-quantum-processor/)Cited by:[§1](https://arxiv.org/html/2607.11936#S1.p4.6),[§2\.2](https://arxiv.org/html/2607.11936#S2.SS2.p2.1)\.
- D\. Kleyko, D\. Rachkovskij, E\. Osipov, and A\. Rahimi \(2023\)A survey on hyperdimensional computing aka vector symbolic architectures, part ii: applications, cognitive models, and challenges\.ACM Computing Surveys55\(9\),pp\. 1–52\.Cited by:[§1](https://arxiv.org/html/2607.11936#S1.p3.3)\.
- H\. Lee, J\. Kim, H\. Chen, A\. Zeira, N\. Srinivasa, M\. Imani, and Y\. Kim \(2023\)Comprehensive integration of hyperdimensional computing with deep learning towards neuro\-symbolic ai\.In2023 60th ACM/IEEE Design Automation Conference \(DAC\),pp\. 1–6\.Cited by:[§1](https://arxiv.org/html/2607.11936#S1.p2.1)\.
- R\. Memisevic and G\. E\. Hinton \(2010\)Learning to represent spatial transformations with factored higher\-order boltzmann machines\.Neural computation22\(6\),pp\. 1473–1492\.Cited by:[§1](https://arxiv.org/html/2607.11936#S1.p3.3)\.
- P\. Neubert and S\. Schubert \(2021\)Hyperdimensional computing as a framework for systematic aggregation of image descriptors\.InProceedings of the IEEE/CVF conference on computer vision and pattern recognition,pp\. 16938–16947\.Cited by:[§1](https://arxiv.org/html/2607.11936#S1.p2.1)\.
- M\. A\. Nielsen and I\. L\. Chuang \(2010\)Quantum computation and quantum information\.Cambridge university press\.Cited by:[§1](https://arxiv.org/html/2607.11936#S1.p1.1),[§2\.2](https://arxiv.org/html/2607.11936#S2.SS2.p1.4)\.
- M\. Pilligua, D\. Xue, and J\. Vazquez\-Corral \(2025\)HyperNVD: accelerating neural video decomposition via hypernetworks\.InProceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition,pp\. 22933–22942\.Cited by:[§1](https://arxiv.org/html/2607.11936#S1.p3.3)\.
- T\. A\. Plate \(1995\)Holographic reduced representations\.IEEE Transactions on Neural networks6\(3\),pp\. 623–641\.Cited by:[§1](https://arxiv.org/html/2607.11936#S1.p2.1),[§2\.1](https://arxiv.org/html/2607.11936#S2.SS1.p1.5),[§2\.1](https://arxiv.org/html/2607.11936#S2.SS1.p1.9)\.
- P\. P\. Poduval, Z\. Zou, and M\. Imani \(2024\)Hdqmf: holographic feature decomposition using quantum algorithms\.InProceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition,pp\. 10978–10987\.Cited by:[§1](https://arxiv.org/html/2607.11936#S1.p3.3),[§1](https://arxiv.org/html/2607.11936#S1.p4.6),[§2\.2](https://arxiv.org/html/2607.11936#S2.SS2.p3.6)\.
- \[20\]\(2025\)Quantum error correction below the surface code threshold\.Nature638\(8052\),pp\. 920–926\.Cited by:[§1](https://arxiv.org/html/2607.11936#S1.p4.6),[§2\.2](https://arxiv.org/html/2607.11936#S2.SS2.p2.1),[§2\.2](https://arxiv.org/html/2607.11936#S2.SS2.p3.6)\.
- A\. Rahimi, S\. Datta, D\. Kleyko, E\. P\. Frady, B\. Olshausen, P\. Kanerva, and J\. M\. Rabaey \(2017\)High\-dimensional computing as a nanoscalable paradigm\.IEEE Transactions on Circuits and Systems I: Regular Papers64\(9\),pp\. 2508–2521\.Cited by:[§1](https://arxiv.org/html/2607.11936#S1.p2.1)\.
- \[22\]\(2023\)Suppressing quantum errors by scaling a surface code logical qubit\.Nature614\(7949\),pp\. 676–681\.Cited by:[§1](https://arxiv.org/html/2607.11936#S1.p4.6),[§2\.2](https://arxiv.org/html/2607.11936#S2.SS2.p2.1)\.
- A\. Vourdas \(2004\)Quantum systems with finite hilbert space\.Reports on Progress in Physics67\(3\),pp\. 267–320\.Cited by:[§2\.2](https://arxiv.org/html/2607.11936#S2.SS2.p1.4)\.
- N\. Wiebe, A\. Kapoor, and K\. M\. Svore \(2015\)Quantum algorithms for nearest\-neighbor methods for supervised and unsupervised learning\.Quantum Information & Computation15\(3\-4\),pp\. 316–356\.Cited by:[§1](https://arxiv.org/html/2607.11936#S1.p1.1)\.
- S\. Wiedemann, D\. Hein, S\. Udluft, and C\. Mendl \(2022\)Quantum policy iteration via amplitude estimation and grover search–towards quantum advantage for reinforcement learning\.Transactions on Machine Learning Research\.Cited by:[§1](https://arxiv.org/html/2607.11936#S1.p1.1)\.
- Y\. Xu and V\. Aggarwal \(2025\)Accelerating quantum reinforcement learning with a quantum natural policy gradient based approach\.InInternational Conference on Machine Learning,pp\. 69059–69077\.Cited by:[§1](https://arxiv.org/html/2607.11936#S1.p1.1)\.
- S\. Yun, R\. Masukawa, S\. Jeong, M\. Imani, and M\. Imani \(2024\)Neurohash: a hyperdimensional neuro\-symbolic framework for spatially\-aware image hashing and retrieval\.IEEE International Conference on Acoustics, Speech and Signal Processing \(ICASSP\)\.Cited by:[§1](https://arxiv.org/html/2607.11936#S1.p2.1)\.
- S\. Yun, H\. Oh, R\. Masukawa, and M\. Imani \(2026\)DecoHD: decomposed hyperdimensional classification under extreme memory budgets\.In2026 Design, Automation & Test in Europe Conference & Exhibition \(DATE\),Cited by:[§1](https://arxiv.org/html/2607.11936#S1.p3.3)\.