Implementing the Maxcut problem on a quantum computer
Maxcut is a problem from graph theory, where a network of connected nodes, also known as a graph, is divided into two partitions such that the number of edges between the two partitions is maximised. The relevance of this problem to the Port of Dover is that the nodes of the graph can represent traffic checkpoints, and the edges of the graphs can represent the routes traffic follows between these points, allowing increased insight into traffic flows.
What was done?
The problem was formulated as a Quantum Unconstrained Binary Optimization (QUBO) problem and simulated on the ORCA Software Development Kit (SDK). Different binary variables encoded which network partition each node was in. The quantum boson sampler produced binary strings which were mapped to the relevant binary variables and the boson beam splitter angles were tuned classically to find the binary string which corresponded to the optimum solution.
Digital Catapult gave education and training on quantum optimisation, including use of the ORCA SDK to set up and solve optimisation problems, and supported the Port of Dover team in completing their quantum notebook, and to disseminate their learnings at the final QTAP showcase.
What were the results?
The problem, with nine nodes, was solved by simulating the ORCA SDK and the solution suggested insights into minimising congestion. Although the solution could have been found classically with a specialised solver, or even by brute force, the Port of Dover participants were able to gain knowledge of quantum optimisation by setting up and simulating a practical example and overcoming the challenge of translating complex traffic flow dynamics into a QUBO framework.
The work sparked interest among Port of Dover stakeholders to continue to explore quantum computing solutions to enhance traffic management and port logistics. Siti Fariya, Simulation Modeller Specialist at the Port of Dover explained that the team are “hoping to find a consortium to work with us for the future development of quantum computing.”
