I know that it takes billions of years to solve the travelling sales man when n = 25 (Number of cities). I am wondering how fast can a quantum computer solve the travelling sales man problem (for example, A quantum computer with 500 qubits) .I know that a quantum computer with n qubits can make 2^n in a single step and so a quantum computer with 500 qubits can make 2^500 calculations in a single step.
In classical computers, TSM has a time complexity of O(2^n). What is the time complexity if we deal with quantum computers for TSM ?
Also can a quantum traverse any loop in no time ??