Permutation trick lets quantum memory find patterns without uniform superpositions

One of the most tantalizing promises of quantum computing is the ability to store many patterns in a single quantum state and then pull out exactly the one you are looking for. This is the core idea behind quantum associative memory and quantum nearest neighbor search, two building blocks that researchers have long hoped would give quantum machine learning a decisive edge. A new study by Andreas Wichert of INESC-ID and the Instituto Superior Técnico at the University of Lisbon, published in Quantum Machine Intelligence, describes a fresh way to do precisely that. The work introduces an encoding scheme called the permutation technique, along with a modified version of Grover’s search algorithm that works correctly even when the stored patterns do not form a uniform quantum superposition, a condition that has quietly undermined earlier approaches to quantum memory retrieval.

The problem the paper tackles begins with the most basic step: loading data. Suppose you want to store k binary vectors, each of dimension m, in the amplitudes of an m-qubit register. In principle, a quantum register of m qubits spans a Hilbert space of dimension n = 2^m, so a single state can encode an enormous table of patterns at once. This is the appeal of basis encoding, in which each classical bit string corresponds directly to a computational basis state of the register. The catch is that preparing such a state is itself a nontrivial circuit-design problem, and the structure of the resulting superposition depends heavily on how the loading procedure is built.

Wichert’s permutation technique offers a structurally simpler alternative to the well-known storage algorithm of Ventura and Martinez, which dates back to the late 1990s and was one of the first serious proposals for quantum associative memory. Instead of building the superposition of stored patterns through a sequence of operations tied to the individual vectors, the permutation approach constructs the state by permuting basis states, exploiting the fact that any superposition over the stored patterns can be reached by rearranging amplitudes that are already present in a standard initial state. The result is a loading procedure with a cleaner circuit structure, and, importantly, one that can be compressed further when the stored vectors are strongly correlated with one another. In that case a companion procedure, the reduce algorithm, squeezes the representation down by removing redundancy shared among the patterns.

Here, however, the deeper difficulty emerges, and it is the one that gives the paper its central contribution. The superposition produced by loading k patterns into an n-dimensional register is generally non-uniform: some basis states carry larger amplitudes than others, because the number of stored patterns is typically far smaller than the size of the full space. Grover’s algorithm, the celebrated quantum search procedure that finds a marked item in a database with only O(√n) oracle calls, was designed under the assumption that the search space is uniformly distributed. Its amplitude amplification mechanism rotates the quantum state in a two-dimensional plane spanned by the uniform superposition and the target state. When the initial distribution is not uniform, that geometric picture breaks down, and applying Grover’s iterations directly to a non-uniform superposition of stored patterns fails to amplify the correct target.

This failure mode is more than a technical footnote. It means that a naive combination of a pattern-loading routine and textbook Grover search does not yield a working quantum memory, even though both ingredients individually seem to fit together. Earlier retrieval schemes, including the Ventura–Martinez approach, effectively paid for this mismatch by scaling with the full dimension of the register: their retrieval cost grows as O(√n), where n = 2^m. When the number of stored patterns k is much smaller than n, which is the typical and most interesting regime for a memory, that quadratic dependence on the ambient dimension wastes much of the potential advantage.

Wichert’s solution, which he calls the permutation trick, is a modified, permutation-based variant of Grover’s algorithm that restores correct search behavior over the non-uniform superposition. The key insight is that the permutation structure used to load the patterns can also be used to redefine how amplitude amplification is applied, so that the amplification acts on the distribution actually present in the register rather than on an assumed uniform one. With this correction in place, retrieval completes in O(√k) oracle calls for k stored patterns, independent of the ambient dimension n = 2^m. In other words, the cost of finding a pattern by its content scales with the size of the memory, not with the size of the Hilbert space it happens to live in.

The contrast with the earlier approach is stark when spelled out numerically. Consider a register of just 20 qubits, giving n = 2^20, or roughly one million basis states. If the memory holds only a few hundred patterns, the Ventura–Martinez retrieval procedure would require on the order of a thousand oracle calls, tracking the square root of a million, while the permutation-based retrieval needs only on the order of the square root of the pattern count, a few tens of calls. As the gap between k and n widens, so does the advantage. This is exactly the regime in which quantum associative memory is supposed to shine, since a memory that only pays for the patterns it actually stores is the quantum analogue of what associative memories in the brain and in classical neural networks are admired for.

The paper demonstrates the storage and retrieval principles through two applications that anchor the abstract machinery in concrete tasks. The first is quantum associative memory, in which a partial or corrupted cue is presented and the system returns the stored pattern most closely matching it, echoing the classical Hopfield and Kohonen models of associative memory that have influenced cognitive science and neural network research for decades. The second is quantum nearest neighbor search, the problem of finding the stored vector closest to a query vector, which underlies many classification and clustering methods in machine learning. In both settings, the permutation trick provides the retrieval engine, showing that the same corrected search primitive supports content-based access to quantum-encoded data across different use cases.

Practical considerations are not ignored. The work is accompanied by a freely available Jupyter notebook providing a step-by-step implementation in Qiskit, the open-source software development kit for programming quantum computers at the level of circuits and algorithms, developed around IBM Quantum hardware. Notably, Qiskit uses little-endian notation for qubit indexing, a detail that anyone reproducing the circuits must keep in mind. The availability of runnable code matters because the field of quantum machine learning has repeatedly been cautioned, most famously by Scott Aaronson in 2015, to read the fine print: many proposed quantum speedups come with data-loading costs or state-preparation overheads that erase the advantage end to end. By making the loading procedure structurally simpler and by keeping retrieval costs tied to the pattern count rather than the register dimension, the permutation technique speaks directly to that concern.

The broader significance of the result lies in what it clarifies about where quantum advantage can realistically come from in memory and search tasks. Grover’s algorithm is provably optimal for unstructured search over a uniform space, as Christof Zalka showed in 1999, so no variant can beat its quadratic scaling in that setting. But real memories are not uniform haystacks; they are sparse, structured collections of correlated patterns. Wichert’s permutation trick shows that when the encoding itself carries structure, the search procedure can be reshaped to exploit it, converting a dependence on the exponentially large ambient space into a dependence on the genuinely stored content. For near-term quantum hardware, where qubit counts and circuit depths remain precious resources, a scheme that is simpler to load, compressible for correlated data, and scalable in the number of patterns rather than the dimension of the space offers a more credible route to pattern storage and content-based retrieval. Whether such memories will ultimately outperform classical hardware remains an open empirical question, but this work sharpens the theoretical map of the terrain, identifying precisely where the uniformity assumption fails and how a permutation-based correction can rescue quantum search from that failure.

Subject of Research: Quantum algorithms for encoding and retrieving binary vectors in quantum associative memory and nearest neighbor search

Article Title: Quantum algorithm for binary vector encoding and retrieval utilizing the permutation trick

Article References: Quantum algorithm for binary vector encoding and retrieval utilizing the permutation trick. (n.d.). https://doi.org/10.1007/s42484-026-00454-w

Image Credits: AI Generated

DOI: 10.1007/s42484-026-00454-w

Keywords: quantum computing, quantum associative memory, Grover's algorithm, basis encoding, quantum nearest neighbor search, amplitude amplification, non-uniform superposition, quantum machine learning, Qiskit, pattern retrieval, Ventura–Martinez algorithm, permutation technique