Speaker
Description
We encode the binary knapsack problem as the minimization of a diagonal quantum Hamiltonian, where the linear constraint is implemented through a Fourier‑approximated projector onto feasible bitstrings. By working on the manifold of matrix product states (MPS)---implemented natively in PyTorch with automatic differentiation---we turn the combinatorial search into a tractable continuous gradient‑based optimization. A Rényi‑entropy regularizer ensures that the only critical points of the objective are the computational basis states, that the ground state is a strict local minimum, and that all other basis states are saddle points. On flat knapsack instances the solver achieves solutions within $2\%$ of optimality for problems up to $n=15\,000$, with a time that scales linearly in $n$ and remains computationally feasible on a single CPU. Theoretical analysis and principal component analysis of the trajectory confirm that the optimization landscape is free of spurious local minima.
| Topic | Tensor methods and quantum-inspired machine learning |
|---|---|
| Additional Topic | Hybrid quantum-classical approaches for learning and optimization |