  The Travelling Salesman Problem (TSP) is an important combinatorial
optimisation problem, and is usually solved on a quantum computer using a
Quadratic Unconstrained Binary Optimisation (QUBO) formulation or a Higher
Order Binary Optimisation(HOBO) formulation. In these formulations, penalty
terms are added to the objective function for outputs that don't map to valid
routes.
  We present a novel formulation which needs fewer binary variables, and where,
by design, there are no penalty terms because all outputs from the quantum
device are mapped to valid routes. Simulations of a quantum boson sampler were
carried out which demonstrate that larger networks can be solved with this
penalty-free formulation than with formulations with penalties. Simulations
were successfully translated to hardware by running a non-QUBO formulation with
penalties on an early experimental prototype ORCA PT-1 boson sampler. Although
we worked with a boson sampler, we believe that this novel formulation is
relevant to other quantum devices.
  This work shows that a good embedding for combinatorial optimisation problems
can solve larger problems with the same quantum computing resource. The
flexibility of boson sampling quantum devices is a powerful asset in solving
combinatorial optimisation problem, because it enables formulations where the
output string is always mapped to a valid solution, avoiding the need for
penalties.
