Quantum programmers have long faced a subtle frustration at the heart of every quantum algorithm: after all the elegance of superposition, the measurement step collapses the entire richly structured quantum state into just one answer. A team of researchers at the Universidad Politécnica de Cartagena in Spain now proposes a clever workaround that attacks the problem at its source—by changing how information is written into qubits in the first place. Their new scheme, called Multi-Unary encoding, allows a single set of input qubits to carry multiple valid values simultaneously, a property no prior encoding scheme has offered, and it promises to make Grover’s celebrated search algorithm noticeably more efficient.
Encoding is one of the first and most consequential decisions in designing a quantum program. Just as classical computers must decide how to represent integers or characters as bits, quantum algorithms must map problem variables—whether they denote colors, routes, or cluster assignments—onto the quantum states of a register. Over the past decade, researchers have adapted classical schemes such as one-hot, binary, and Gray codes to qubits, and have invented quantum-native alternatives like angle encoding, amplitude encoding, and Schmidt decomposition. Each approach embodies a trade-off between the number of qubits consumed and the complexity of the circuits needed to operate on them. One-hot encoding, in which one bit is reserved for every possible value a variable can take and exactly one of those bits is set to 1, is particularly popular because it is simple to encode, decode, and check for validity—even though it is wasteful in qubit count. A variable with four possible values, for instance, needs four qubits under one-hot rules, yielding the four allowed states 0001, 0010, 0100, and 1000.
The insight behind Multi-Unary is disarmingly simple. Instead of requiring that exactly one bit be set to 1, the scheme requires only that at least one bit be set to 1, with the single forbidden state being the all-zero string. Under this relaxation, the four-qubit register above can represent not just four values but fifteen—the full set of non-zero bit strings. Because more than one value can live in the same group of qubits, the Spanish team describes Multi-Unary as a “dense” encoding scheme, and, to their knowledge, it is the first encoding in the quantum computing literature with this property. The consequence is profound for algorithms like Grover’s: a single measured bit string can now encode several valid assignments at once, so the quantum state effectively contains and delivers multiple solutions in a single shot.
Grover’s algorithm, first proposed in 1996, searches an unstructured space of size N containing M solutions with a complexity of O(√(N/M)), a quadratic speedup over any classical method. The algorithm begins by placing the input qubits into an equal superposition of all possible states. It then applies an oracle—a quantum subroutine that recognizes valid solutions and flips their phase by π radians—followed by a diffusion operation that inverts the amplitudes about their mean, amplifying the marked states. Each oracle-plus-diffusion cycle is one Grover iteration, and the probability of measuring a solution after i iterations is given by P = sin²((2i+1)·θg), where θg = arcsin(√(M/N)). The optimal number of iterations scales as R ≤ ⌈(π/4)√(N/M)⌉. Crucially, both the success probability and the required iteration count depend on the ratio M/N: the more states qualify as solutions, the better.
This is exactly where Multi-Unary shines. By enlarging the set of bit strings that count as legitimate solutions, the scheme increases M, which the team proves mathematically raises the success probability P and lowers the required number of Grover iterations R. They derive the partial derivatives of both quantities with respect to M, showing rigorously that P grows monotonically and R shrinks monotonically over the entire operating range. The practical payoff comes in three forms: a higher chance that any given measurement yields a solution, fewer oracle calls needed to maximize that chance, and measured outputs that can bundle multiple solutions into one value, reducing the total number of circuit executions—or “shots”—needed to recover a desired fraction of all solutions.
To demonstrate the idea concretely, the researchers applied Multi-Unary to the graph coloring problem, a canonical combinatorial challenge that asks for the assignment of k colors to the nodes of a graph such that no two adjacent nodes share a color. Graph coloring matters well beyond theory—it underpins scheduling, register allocation, and resource assignment tasks—and it has become a standard benchmark for quantum algorithms, tackled previously with quantum annealing, variational approaches, and Grover-based oracles using both binary and one-hot encodings. In the Spanish team’s demonstration, a six-node, six-edge graph is colored with three colors, the minimum possible.
Their oracle design rests on quantum counters, built from multi-controlled X gates, which tally constraint violations. The logic proceeds in three steps. First, for each node, the counter is incremented if all of that node’s color qubits are zero—penalizing strings that violate the Multi-Unary rule that every variable must carry at least one value. Second, for every edge and every color, the counter is incremented if both endpoints display that same color simultaneously, penalizing genuine coloring conflicts. Third, only strings for which the counter reads zero—strings satisfying every constraint—have their phases rotated by a multi-controlled Z gate, marking them for amplification. A single ancilla qubit acts as a trigger that fires each counter increment and is uncomputed immediately afterward, while the remaining ancillas store the running count. The design also incorporates a subtle optimization: because early counter increments only touch the least significant bits of the count, the number of controls on successive increment gates can be grown gradually, trimming expensive multi-controlled gates.
The resource analysis for the example circuit is instructive. The complete oracle comprises 367 gates, of which 284 are controlled X gates—and 188 of those, fully 66.2 percent, implement the counter alone, underscoring how central counting is to this style of oracle construction. The circuit depth is 287 layers, dominated by the trigger qubit through which every increment must pass. Simulating the full circuit with 36 Grover iterations—the number that maximizes success probability—yielded a 99.88 percent chance of measuring a solution, and a histogram of 1,000 shots in Qiskit’s Aer simulator recovered 126 distinct solution values, with only two spurious non-solutions appearing once each, a rate consistent with statistical expectations.
The headline result is the sheer expansion of the solution space. Under a conventional one-hot oracle, the example graph has exactly 48 valid colorings. With Multi-Unary, the number of solution values jumps to 126—78 additional bit strings that are also valid, thanks to nodes that can carry more than one compatible color. This flexibility arises naturally in real graphs: leaf nodes and nodes with low connectivity often admit several admissible colors, and Multi-Unary lets the quantum state express that freedom directly. Decoding is straightforward: any measured variable whose bits contain more than one 1 is expanded into as many one-hot candidates as there are set bits, each assigning a single value while preserving the rest. In one worked example, the output string 011 010 001 100 010 101—where two nodes each hold two colors—unpacks into four distinct, fully valid colorings of the graph. A single measurement delivered four answers.
The authors are careful to position their contribution honestly. Binary encoding still wins on raw qubit count—a 50-node graph with 10 colors needs 200 binary-encoded input qubits versus 500 for one-hot or Multi-Unary—but binary circuits must then explicitly reject the invalid states corresponding to out-of-range values, adding gates and ancillas that Multi-Unary avoids by construction. Indeed, validity checking is where Multi-Unary beats its closest cousin outright: the only forbidden state under Multi-Unary is the all-zero string, detectable with a simple NOR gate, whereas one-hot verification requires a counter to confirm that exactly one bit is set. Because encoding and decoding work identically in both schemes, the team argues that Multi-Unary could outright replace one-hot encoding, with migration requiring changes only to the oracle’s validity-check portion—and a simpler oracle as a reward. The advantage does taper off for densely connected graphs, where fewer nodes admit multiple colors and the scheme converges back toward plain one-hot behavior.
The implications reach beyond graph coloring. The researchers point to shortest-path, graph coverage, and clustering problems as natural targets, and note that their encoding could slot into emerging frameworks like the discrete quantum intermediate representation proposed for encoding-independent optimization. For today’s noisy, resource-starved quantum hardware, where every ancilla qubit and every additional Grover iteration carries a real cost, a scheme that squeezes multiple solutions into the same qubits—and trims the iteration count as a bonus—offers a rare kind of free lunch. If quantum computing’s near-term future depends on getting the most out of every qubit, Multi-Unary suggests that sometimes the smartest move is not a new algorithm, but a new way of writing the problem down.
Subject of Research: Dense input encoding for quantum circuit algorithms; application of the Multi-Unary scheme to Grover’s algorithm and the graph coloring problem
Subject of Research: Technology and Engineering
Article Title: Multi-Unary: a dense input encoding scheme for the quantum circuit model
Article References: Alonso, D., Sánchez, P., Álvarez, B., & Terroso-Sáenz, F. (2026). Multi-Unary: a dense input encoding scheme for the quantum circuit model. Quantum Information Processing, 25(9), Article 304. https://doi.org/10.1007/s11128-026-05316-9
Image Credits: AI Generated
DOI: 10.1007/s11128-026-05316-9
Keywords: quantum computing, Multi-Unary encoding, Grover’s algorithm, graph coloring, one-hot encoding, quantum oracles, dense encoding, quantum counters, Qiskit, combinatorial optimization
Cite Scienmag News
APA MLA Chicago
Katie Riggs. (September 5, 2026). New Multi-Unary encoding scheme packs dense inputs into quantum circuits. Scienmag. https://scienmag.com/new-multi-unary-encoding-scheme-packs-dense-inputs-into-quantum-circuits/
Katie Riggs. “New Multi-Unary encoding scheme packs dense inputs into quantum circuits.” Scienmag, 5 September 2026, https://scienmag.com/new-multi-unary-encoding-scheme-packs-dense-inputs-into-quantum-circuits/. Accessed 5 September 2026.
Katie Riggs. “New Multi-Unary encoding scheme packs dense inputs into quantum circuits.” Scienmag. September 5, 2026. https://scienmag.com/new-multi-unary-encoding-scheme-packs-dense-inputs-into-quantum-circuits/
Copy citation Download RIS
Tags: dense input encoding in quantum algorithmsdense quantum input encodingGrover’s algorithm efficiencyGrover’s search algorithm efficiencymulti-unary encodingquantum algorithmsquantum circuit optimizationquantum computing researchquantum data encoding methodsquantum data representationQuantum encoding schemesquantum information encodingquantum programming techniquesquantum search algorithmsquantum state measurementqubit information representationqubit state manipulationsuperposition in quantum computing
