Previous record was 21 = 3 * 7 if I recall correctly

There is no known polynomial time algorithm for TSP. AFAIK there are quantum algorithms for TSP with quadratic speedup in comparison to the brute force method (still exponential though).

The one thing quantum computers are (currently and theoretically) able to solve efficiently is the factorization problem, but are very much limited by low qubit number, i.e. engineering problems.