arXiv:2610.13621
Encoding Matters: A Qubit-Efficient Reformulation for Quantum Resilient Routing
Emanuele G. Dalla Torre, Bat-El Friedman, Daniel Porat
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.
AI Summary
The paper asks how much classical preprocessing of a routing QUBO can reduce the resources needed for near-term quantum optimization. It develops five local substitution rules using fixed source and terminal variables, endpoint edge constraints, excluded terminals, degree-two internal nodes, and edge-balance identities. Applied iteratively before QUBO construction, these rules eliminate or merge variables while retaining residual feasibility penalties. The demonstration uses a five-node, seven-edge latency-resilient routing benchmark with correlated link failures and two internally vertex-disjoint routes. For the selected source, the encoding shrinks from 24 to 7 binary variables, reducing the assignment space from $2^{24}$ to $128$. Exhaustive enumeration of the reduced model verifies that its decoded feasible assignments reproduce all five valid route pairs with unchanged objective values and the same optimum. QAOA parameters are optimized on a noiseless simulator to maximize ground-state overlap. The reduced model achieves $25.4\%$ ideal success at depth $p=4$, compared with the previously reported $1.5\%$ at $p=20$ for the canonical encoding. Execution on the same IonQ Forte Enterprise 1 device, without error mitigation, yields 60 optimal solutions in 300 shots ($20\%$), versus the benchmark’s $0.2\%$. The circuit uses 53 ZZ rotations, compared with approximately 1,000 two-qubit gates in the benchmark. The demonstrated reduction and hardware results concern one small benchmark instance. The discussion identifies scaling as an open question and proposes larger-network preprocessing and decomposition-based workflows, without testing them.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- Letter