tsp-quantum-preprocessing

# TSP Quantum Preprocessing ## Description Preprocessing strategy for combinatorial optimization problems that significantly reduces model size by restricting candidate edges/arcs to the k lowest-cost neighbors per vertex. Reduces decision variables from O(n²) to O(kn) while preserving solution quality. Evaluated with both classical solvers and quantum optimization techniques, showing improvements in computational time and optimality gaps. ## Activation Keywords - TSP preprocessing - quantum TSP - candidate arc reduction - combinatorial optimization preprocessing - quantum preprocessing - 旅行商问题预处理 - 量子组合优化 ## Core Concepts ### k-Nearest Neighbor Arc Filtering For a TSP with n cities: - Original formulation: n(n-1) binary variables (all possible arcs) - After preprocessing: n×k variables (only k nearest neighbors per city) - Typical k: 5-15 (problem-dependent) ### Subtour Elimination Preservation The preprocessing maintains subtour elimination constraints (MTZ or DFJ) on the reduced graph. The key insight: optimal tours rarely use edges that are not among the k-nearest neighbors. ### Quantum Optimization Benefits 1. **Reduced qubit count**: Fewer binary variables → fewer qubits needed 2. **Sparser coupling graph**: Fewer constraints → easier embedding 3. **Faster convergence**: Smaller search space → fewer QAOA iterations 4. **Lower chain breaks**: Less dense logical graph → better minor embedding ## Usage Patterns ### Pattern 1: Classical Preprocessing for Quantum Optimization 1. Compute pairwise distance/cost matrix for all n nodes 2. For each node, select k nearest neighbors (k = O(log n) or problem-specific) 3. Build reduced cost matrix with only selected edges 4. Formulate QUBO/Ising model on reduced graph 5. Solve with QAOA, quantum annealing, or classical solver ### Pattern 2: Adaptive k Selection 1. Start with small k (e.g., k=3) 2. Solve and check solution quality 3. If infeasible (no valid tour found): increment k 4. Repeat until feasible solution found 5. The optimal k balances solution quality vs. computational cost ### Pattern 3: Extension Beyond TSP Applicable to any graph optimization problem: - Vehicle Routing Problem (VRP) - Steiner Tree Problem - Facility Location - Network Design For each, define the "neighbor" relationship appropriate to the problem structure. ## Tools Used - networkx: Graph construction, k-NN computation - qiskit/dwave: Quantum optimization solvers - gurobi/cplex: Classical baseline comparison - numpy: Distance matrix computation ## Error Handling ### No Feasible Solution Found - Symptom: Reduced graph has no valid solution - Fix: Increase k, check if original problem is feasible - Recovery: Fall back to full graph formulation ### Preprocessing Removes Optimal Edge - Symptom: Optimal solution uses edges not in k-NN set - Fix: Use adaptive k with iterative refinement - Alternative: Add a small set of "long-range" edges strategically ### Quantum Embedding Still Fails After Preprocessing - Symptom: Even reduced graph too dense for hardware - Fix: Further reduce k, or use QAOA instead of quantum annealing ## Examples ### Example 1: TSP on 100-City Instance Original: 100×99 = 9900 binary variables Preprocessed (k=10): 100×10 = 1000 binary variables (90% reduction) Results on TSPLIB benchmarks: - Classical solver (Gurobi): 3x faster on preprocessed instance - QAOA: Feasible embedding on hardware (was infeasible before) - Optimality gap: < 2% for k≥8 ## Resources - arXiv:2603.23290 - Traveling Salesman Problem with a Preprocessing Method for Classical and Quantum Optimization - TSPLIB benchmark instances - QAOA literature (Farhi et al.) ## Related Skills - quantum-optimization-qaoa - quantum-computing-patterns - qbalance-quantum-workflow-optimization