What was done?
The problem was formulated as a Quantum Unconstrained Binary Optimisation (QUBO) problem and simulated on the ORCA Software Development Kit (SDK) using a standard formulation by Lucas, an American Theoretical Physicist. The problem used different binary strings encoding different routes through the network. For example, imagine visiting locations 1, 2, 3 and 4 in the cycle 1 → 4 → 3 → 2 → 1 – this problem is encoded as a binary string of 0001 1000 0100 0010 where the position of the “1” from the left represents the location visited (first, fourth, third and second positions). If the binary strings encoded an invalid route, then a penalty term was applied. The quantum boson sampler produced binary strings and the boson beam splitter angles were tuned classically to find the binary string which corresponded to the shortest path through the network.
Although the Lucas formulation worked well in simulation, it needed too long a binary string to run on the ORCA PT-1 prototype quantum computer, so Digital Catapult’s quantum computing experts worked with the Bahut team to develop a new formulation that leveraged the flexibility of the boson sampler to reduce the length of the binary string, enabling the example to run on a real quantum computer.
When this formulation was simulated it was found to work for networks with up to 15 different locations. Since then a further improvement has been made to find solutions with networks of up to 48 locations in simulations, proving the capabilities of a quantum computer to solve a complex Travelling Salesman Problem.
What was learnt?
Bahut gained experience in quantum computing by solving a real business problem on a quantum computer, and has used the programme as a springboard to start building partnerships with logistical providers.
