Many-Qudit representation for the Travelling Salesman Problem Optimisation

Abstract

We present a map from the travelling salesman problem (TSP), a prototypical NP-complete combinatorial optimisation task, to the ground state associated with a system of many-qudits. Conventionally, the TSP is cast into a quadratic unconstrained binary optimisation (QUBO) problem, that can be solved on an Ising machine. The size of the corresponding physical system's Hilbert space is $2^{N^2}$, where $N$ is the number of cities considered in the TSP. Our proposal provides a many-qudit system with a Hilbert space of dimension $2^{N{\log }_{2}N}$, which is considerably smaller than the dimension of the Hilbert space of the system resulting from the usual QUBO map. This reduction can yield a significant speedup in quantum and classical computers. We simulate and validate our proposal using variational Monte Carlo with a neural quantum state, solving the TSP in a linear layout for up to almost 100 cities.

arXiv comment9 pages, 4 figures

References in corpus (22)

• The density-matrix renormalization group in the age of matrix product states
• Hardware-efficient Variational Quantum Eigensolver for Small Molecules and Quantum Magnets
• Ising formulations of many NP problems
• Solving the Quantum Many-Body Problem with Artificial Neural Networks
• Adiabatic Quantum Computing
• Quantum Search by Local Adiabatic Evolution
• Qudits and high-dimensional quantum computing
• Restricted-Boltzmann-Machine Learning for Solving Strongly Correlated Quantum Systems
• Floquet engineering of correlated tunneling in the Bose-Hubbard model with ultracold atoms
• Strong-coupling of quantum dots in microcavities
• Probing for quantum speedup in spin glass problems with planted solutions
• High-dimensional optical quantum logic in large operational spaces
• NetKet: A Machine Learning Toolkit for Many-Body Quantum Systems
• Quantum amplification of boson-mediated interactions
• Helping restricted Boltzmann machines with quantum-state representation by restoring symmetry
• Boosting Monte Carlo simulations of spin glasses using autoregressive neural networks
• Multilevel Combinatorial Optimization Across Quantum Architectures
• High-fidelity software-defined quantum logic on a superconducting qudit
• Deep Learning-Enhanced Variational Monte Carlo Method for Quantum Many-Body Physics
• Measures of quantum computing speedup
• Discrete Polynomial Optimization with Coherent Networks of Condensates and Complex Coupling Switching
• Phase diagram reconstruction of the Bose-Hubbard model with a Restricted Boltzmann Machine wavefunction

Cited by in corpus (6)

• Algorithmic QUBO Formulations for k-SAT and Hamiltonian Cycles
• Supplementing Recurrent Neural Networks with Annealing to Solve Combinatorial Optimization Problems
• Variational Quantum Multi-Objective Optimization
• Multi-qudit interactions in molecular spins
• Inequality constraints in variational quantum circuits with qudits
• Variational decision diagrams for quantum-inspired machine learning applications