Encoding Matters: A Qubit-Efficient Reformulation for Quantum Resilient Routing

AI summary

Overview

Research area: Quantum optimization / quantum computing for logistics and network routing — specifically, qubit-efficient problem encoding (QUBO formulation) for gate-based QAOA hardware in the NISQ era.

Technical level: Intermediate. The paper uses standard QUBO and QAOA language and assumes familiarity with binary variables, penalty terms, and variational circuits, but the central argument — encoding redundancy removal — is explained through concrete graph rules rather than heavy formalism.

Scope (one sentence): The paper introduces a set of five local, deterministic rules that reduce a canonical node-edge routing encoding from 24 qubits to 7 while preserving the optimization objective, and demonstrates on a trapped-ion device that this reformulation raises the hardware success probability from 0.2% to 20%.

What This Paper Is About

Quantum optimization problems must be rewritten as binary (Ising/QUBO) models before they can run on a quantum computer, and the way that rewrite is done determines how many qubits and gates the final circuit needs. Canonical graph encodings keep many variables that are logically fixed by the routing task, implied by local topology, or redundant once exclusion constraints are applied — all of which cost qubits and add noise exposure. The authors' goal is to show that stripping out this redundancy before building the QUBO produces much better performance on existing hardware, using a published latency-resilient routing benchmark as the test case.

Key Contributions

1. A rule-based encoding reduction method: Five deterministic, local logical rules (source/terminal fixing, incident-edge substitution, complementary-terminal exclusion, degree-2 internal-node merging, and internal-node elimination by edge balance) that simplify a canonical node-edge formulation without changing the optimization target.
2. A concrete demonstration of scaling in qubit count: On the 5-node, 7-edge benchmark network (24 canonical binary variables, 12 per path), the reduction collapses the model to 7 independent logical variables, q0 through q6, reducing the search space from 2^24 ≈ 1.7×10^7 assignments to 2^7 = 128.
3. A verified reduced QUBO with explicit penalty terms: The reduced model's validity conditions are re-expressed as three local quadratic penalties (C_source, C_node, C_overlap) sharing a single coefficient α = 10, with equivalence to the canonical formulation checked by exhaustive enumeration of all 128 assignments.
4. A head-to-head hardware and simulator comparison: Ideal-simulation and trapped-ion execution results for the reduced model against the published benchmark, including a roughly 100× hardware success-probability gain and a large reduction in two-qubit gate count.

Main Findings

• Qubit count falls from 24 to 7: The canonical encoding requires 24 qubits (two paths, 12 binary variables each), while the reduced encoding requires 7 qubits, a search space of 128 assignments instead of approximately 1.7×10^7.
• Equivalence is verified exhaustively: All 2^7 = 128 assignments of the reduced model were enumerated; after decoding, the valid assignments reproduce the complete set of valid routes of the canonical formulation with unchanged objective values, including the same optimal route and ground-state energy.
• The gain appears already in ideal simulation, not only on noisy hardware: The canonical encoding's ideal success probability with p = 20 QAOA layers is reported as 1.5%; the reduced encoding reaches 25.4% already at p = 4. The authors describe this as more than a 10× improvement in ideal simulation, and stress that the advantage is therefore present at the level of representation.
• Hardware success probability rises from 0.2% to 20%: On the same IonQ Forte Enterprise 1 trapped-ion device accessed through Amazon Braket, with no error mitigation, the reduced p = 4 circuit recovered the optimal solution in 60 out of 300 shots across three independent 100-shot runs — a success probability of 20%, described as a 100× improvement over the benchmark's 0.2%.
• Entangling-gate count drops sharply: The reduced results were obtained using just 53 ZZ rotations, compared with approximately 1000 two-qubit gates in the benchmark implementation.
• The rules are local, so no path enumeration is needed: Each rule acts on fixed-size graph neighborhoods (a node and its incident edges), so the reduction can in principle be applied to larger networks without first enumerating all source–terminal paths.
• The benchmark case: The hardware comparison uses source vertex s = S2, which admits five valid route pairs and is the correlated-failure case executed on hardware in the original benchmark study; the topology has 5 nodes and 7 edges.

Methodology in Plain English

The starting point is the standard way of encoding a routing problem: give every node and every edge a binary variable saying whether it is used, and repeat that for each path you need to route. That is easy to construct but wasteful.

The authors then apply five tidy-up rules, repeatedly, until nothing more can be simplified:

1. Endpoints are always on. The source and each terminal node must be active, so their variables are fixed to 1 — they were never real choices.
2. Endpoints have exactly one outgoing edge. If a node fixed to 1 has two candidate edges, the second is just the complement of the first; with three candidates, two variables suffice and the third is one minus the other two.
3. A path may not run through another path's terminal. Those terminal nodes and their directly connecting edges are fixed to 0.
4. A degree-2 internal node is its two edges. If a node has exactly two remaining candidate edges, the node variable and both edge variables are identical, so all three collapse into one binary degree of freedom.
5. Flow balance removes internal nodes. Continuity requires the number of used incident edges to be twice the node's activation; if the substitutions leave exactly one surviving variable on the right-hand side, the node variable is replaced by it (if the expression could take values outside {0, 1}, the node variable and its constraint are kept).

On the benchmark network, this collapses 24 variables to 7. The remaining validity conditions are written as local quadratic penalty terms with a common weight α = 10 chosen large enough to separate valid from constraint-violating assignments, and the original latency and joint-failure cost terms are added on top. The authors then build a QAOA circuit with p layers, optimize its parameters on a noiseless simulator by maximizing statevector overlap with the ground-state subspace (multi-start search refined with the bounded L-BFGS-B optimizer), and run the optimized p = 4 circuit on the trapped-ion device.

Why This Matters

Impact on research: The paper reframes near-term quantum performance as an encoding problem rather than purely a hardware or error-mitigation problem. It argues that encoding choices determine how much noise an algorithm must tolerate, and it provides a reproducible, rule-based preprocessing procedure that is compatible with any downstream QUBO/QAOA workflow. The verified equivalence check (exhaustive enumeration of 128 assignments) gives a concrete standard for validating reductions.

Real-world applications:

• Telecommunications: Latency-resilient Layer 3 routing with dual-link failure — the benchmark itself — where path choices must survive correlated link failures.
• Logistics and supply-chain planning: Multi-path routing and flow problems on structured graphs, where exclusion and continuity constraints create the same redundancy.
• Energy and resource allocation: Constrained assignment problems whose canonical encodings carry fixed or implied variables.
• Finance: Portfolio and allocation models currently limited by the cost of representing classical constraints on noisy circuits.

Industry relevance: The authors are affiliated with QuantyMize Quantum Advance Ltd. (Tel Aviv), and the encoding methods are the subject of a pending patent application. The practical framing — solution reliability, shot efficiency, and compute cost — targets operational settings where a 100× swing in success probability changes whether a hardware run is worth performing at all. The paper also positions better small-graph solvers as building blocks inside hybrid decomposition workflows, which is how larger industrial instances would actually be attacked.

Future Directions

• Scaling behavior on larger networks. The paper reports only the 5-node, 7-edge benchmark; how much reduction the five rules achieve on larger graphs, and how the ratio of surviving to canonical variables behaves, is not established empirically here.
• Rule generalization. The authors state the precise definition of each rule depends on the problem at hand and that the approach generalizes to other network and logistic problems, but alternative problem classes (scheduling, flow, multi-commodity variants) are not tested.
• Integration into hybrid decomposition workflows. The proposed role for the method is as preprocessing that shrinks subgraphs before mapping to quantum hardware; how this composes with classical-quantum splitting strategies remains an open engineering question.
• Whether encoding reduction can substitute for, or compound with, error mitigation. The hardware runs were performed without error mitigation, so the combined effect of reduced encodings plus mitigation techniques is not reported.

Target Audience

Researchers and practitioners working on near-term quantum optimization — particularly those mapping logistics, routing, and network problems onto QUBO/Ising models and running QAOA on real hardware. It is also useful for quantum algorithm teams in industry who need to justify preprocessing investment before hardware scaling, and for graduate students looking for a clear worked example of how encoding choices propagate into qubit count, gate count, and measured success probability. Readers seeking a new variational algorithm or a theoretical complexity result will not find one here; the contribution is a formulation methodology with an end-to-end hardware demonstration.

Authors’ abstract

Qubits are powerful computational resources because each additional qubit doubles the size of the accessible state space. This expressive power comes at a cost: adding qubits also increases circuit size, constraint overhead, and exposure to hardware noise. These limitations are especially critical for near-term quantum computers, making the number of qubits required to formulate a problem a central practical concern. In this work, we present a method for efficiently mapping logistics and routing problems onto qubits through structure-aware encoding reduction. We demonstrate the method on a benchmark problem of latency-resilient routing under dual-link failures. For this benchmark, the reduced formulation substantially lowers both the qubit count and the compiled circuit complexity while preserving the original optimization task. By running the reduced model on the same trapped-ion quantum computer as the benchmark, we obtain a 100X improvement in the success probability. This finding shows how careful problem formulation can make current quantum hardware substantially more effective for practical optimization.