  This paper studies the Hamiltonian Cycle Problem (HCP) and the Traveling
Salesman Problem (TSP) on D-Wave's quantum systems. Initially, motivated by the
fact that most libraries present their benchmark instances in terms of
adjacency matrices, we develop a novel matrix formulation for the HCP and TSP
Hamiltonians, which enables the seamless and automatic integration of benchmark
instances in quantum platforms. our extensive experimental tests have led us to
some interesting conclusions. D-Wave's {\tt Advantage\_system4.1} is more
efficient than {\tt Advantage\_system1.1} both in terms of qubit utilization
and quality of solutions. Finally, we experimentally establish that D-Wave's
Hybrid solvers always provide a valid solution to a problem, without violating
the QUBO constraints, even for arbitrarily big problems, of the order of $120$
nodes. When solving TSP instances, the solutions produced by the quantum
annealer are often invalid, in the sense that they violate the topology of the
graph. To address this use we advocate the use of \emph{min-max normalization}
for the coefficients of the TSP Hamiltonian. Finally, we present a thorough
mathematical analysis on the precise number of constraints required to express
the HCP and TSP Hamiltonians. This analysis, explains quantitatively why,
almost always, running incomplete graph instances requires more qubits than
complete instances. It turns out that incomplete graph require more quadratic
constraints than complete graphs, a fact that has been corroborated by a series
of experiments.
