Variational (matrix) product states for combinatorial optimization
Abstract
To compute approximate solutions for combinatorial optimization problems, we describe variational methods based on the product state (PS) and matrix product state (MPS) ansatzes. We perform variational energy minimization with respect to a quantum annealing Hamiltonian and utilize randomness by embedding the approaches in the metaheuristic iterated local search (ILS). The resulting quantum-inspired ILS algorithms are benchmarked on maximum cut problems of up to 50000 variables. We show that they can outperform traditional (M)PS methods, classical ILS, the quantum approximate optimization algorithm and other variational quantum-inspired solvers.
Summary
This paper introduces two novel quantum-inspired algorithms, QiILS (Quantum-inspired Iterated Local Search) and QiIGS (Quantum-inspired Iterative Global Search), for solving combinatorial optimization problems. These algorithms combine variational methods based on product states (PS) and matrix product states (MPS) with the classical metaheuristic Iterated Local Search (ILS). The core idea is to leverage quantum annealing Hamiltonians within the ILS framework to guide the search for optimal solutions. QiILS performs iterative DMRG optimizations followed by perturbations, while QiIGS employs a parallelizable global gradient descent approach. The authors benchmarked these algorithms on MaxCut problems with up to 50,000 variables, demonstrating that they outperform traditional (M)PS methods, classical ILS, the Quantum Approximate Optimization Algorithm (QAOA), and other variational quantum-inspired solvers like LQA and GCS. Specifically, QiILS achieves better performance than QAOA and other solvers on Gset instances (G1-G10 and G12). QiIGS provides an order-of-magnitude speedup compared to QiILS for the largest MaxCut instance (G81) while maintaining comparable accuracy. The key contribution lies in showing that a strategic blend of classical optimization techniques with quantum-inspired elements, particularly the use of entanglement-limited MPS and deliberate randomness, can lead to superior performance in solving combinatorial optimization problems. This work highlights the potential of hybrid classical-quantum approaches, even without relying on actual quantum hardware.
Key Insights
- •Novel Algorithms: Introduced QiILS and QiIGS, hybrid classical-quantum algorithms for combinatorial optimization based on combining MPS/PS with Iterated Local Search.
- •Superior Performance: QiILS outperforms classical ILS, QAOA, LQA, and GCS on MaxCut problems (Gset instances G1-G10 and G12).
- •Parallelization: QiIGS, using global gradient updates, is embarrassingly parallel and achieves an order-of-magnitude speedup over QiILS for a 20,000-variable MaxCut instance (G81) due to GPU acceleration.
- •Entanglement Trade-off: Optimizing unentangled product states (PSs) over many ILS iterations can be more efficient than optimizing entangled MPSs with limited iterations, especially for larger problem sizes, suggesting a trade-off between entanglement and computational cost.
- •Hyperparameter Sensitivity: The performance of QiILS is highly sensitive to the perturbation strength (p), with optimal values varying based on the problem type (unweighted vs. weighted graphs).
- •Selection of Lambda: The paper proposes two methods for selecting the λ parameter: visual identification from performance diagrams, and golden-section search (GSS) to maximize the decay rate of the energy.
- •Runtime analysis: QiILS and ILS exhibit similar per-sweep efficiency, while LQA and GCS have higher computational overhead due to their more complex update mechanisms. GCS is roughly 9000 times slower than QiILS per sweep.
Practical Implications
- •Real-world Applications: The algorithms can be applied to various combinatorial optimization problems relevant to industries such as manufacturing, transportation, and telecommunications.
- •Beneficiaries: Researchers and engineers working on optimization algorithms, particularly those interested in quantum-inspired methods, can benefit from these results.
- •Practical Implementation: Practitioners can implement QiILS and QiIGS using readily available libraries like ITensor and leverage GPU parallelization for QiIGS to solve large-scale optimization problems.
- •Benchmarking Framework: The proposed techniques offer a useful classical framework to benchmark and challenge current and future quantum algorithms for combinatorial optimization, providing a baseline for comparison.
- •Future Research: The work opens up future research directions exploring other tensor network architectures, different perturbation strategies, and applications to a wider range of combinatorial optimization problems, as well as further exploration of the trade-off between entanglement and computational cost.