Trying to solve this problem naively (brute-force) by calculating the cost of all possible routes, one would end up considering a factorial growing number of routes in the number of cities (more precisely, \((n-1)!/2\) routes for a symmetric TSP, where the cost to travel from node A to node B is the same in each direction). As an example, for only 10 cities already over 180 000 routes must be considered, which grows to almost 240 000 000 for just 3 cities more.There are different ways of formulating the problem mathematically. In general, binary variables are used and could e.g. describe whether a certain edge between two nodes is part of the route ( \(x_{ij}=1\) if the edge between node \(i\) and \(j\) is part of the considered route, 0 otherwise). Another formulation would be to describe, at which point of a route a given node is visited ( \(x_{it}\) if node \(i\) is visited at time/step \(t\) of the route, 0 otherwise).

In order to tackle the problem with a quantum computer (or a quantum annealer), the latter formulation is suited for expressing the cost via a so-called Hamiltonian, which is an object often encountered when dealing with optimization problems in the quantum realm. The Hamiltonian has different energy levels, which, in this scenario, encode different routes and finding the so-called ground state of the Hamiltonian corresponds to finding the optimal route through the graph.

Finding the ground state with a quantum computer can be achieved by various means, e.g. the Quantum Approximate Optimization Algorithm (QAOA), the Variational Quantum Eigensolver (VQE) or Quantum Annealing (QA). These methods, as well as variations, build the core of the Anaqor Fleet Routing service, which  also incorporates Machine Learning techniques for the pre-processing of the considered graph data.

A quote from Richard Feynman, world-famous physicist and nobel-prize winner, is “nature isn’t classical, dammit, and if you want to make a simulation of nature, you’d better make it quantum mechanical”. This is exactly what lies behind the motivation for solving quantum chemistry problems with a quantum computer – called quantum simulation.

All the information about a molecule is contained in its Hamiltonian, which dominantly takes into account the electrostatic potential between the different building blocks. The second quantized version of this Hamiltonian is ideally suited to be transformed into a qubit-compatible form (e.g. via the Jordan-Wigner or Parity-Transformation), which serves as Input for the quantum algorithm of choice. Here, most approaches utilize the variational principle which states, that the minimum of the expectation of the Hamiltonian corresponds to the ground state energy. Finding this ground state is at the heart of the electronic structure problem and can be approached via different hybrid methods, e.g. the Variational Quantum Eigensolver (VQE) or a quantum version of a restricted Boltzmann Machine (QBM).