Quantum Approaches for combinatorial optimisation problems

Title: quantum approaches for combinatorial optimization problems

 

Abstract: Fast-developing quantum algorithms in recent years provide a different perspective on solving combinatorial optimization problems. In this talk, I will discuss a quantum-inspired tensor-network-based algorithm for general locally constrained combinatorial optimization problems. [1] Our algorithm constructs a Hamiltonian for the problem of interest, effectively mapping it to a quantum problem, then encodes the constraints directly into a tensor network state and solves the optimal solution by evolving the system to the ground state of the Hamiltonian. We demonstrate our algorithm with the open-pit mining problem, which results in a quadratic asymptotic time complexity. Our numerical results show the effectiveness of this construction and potential applications in further studies for general combinatorial optimization problems. I will also talk about several applications of using near-term quantum computing platforms such as Rdyberg atom arrays [2], Honeywell’s trapped ion quantum processor [3] and IBM’s superconducting quantum computer [4] to solve combinatorial optimization problems such as MaxCut.

 

References:
[1] Hao et al, Frontiers in Physics 10, 906590 (2022)
[2] Ebadi et al, Science 376, 6598 (2022)
[3] Amaro et al, Quantum Science and Technology 7, 015021 (2022)
[4] Hindy et al, arXiv: 2107.11345 (2021)

 

Short bio: 
I am an assistant professor in the Physics Department at the University of Florida starting this Fall. Before joining UF, I obtained a PhD in Applied Physics at Stanford University in 2014 and worked as an Associate Staff Scientist and Staff Scientist at SLAC National Laboratory from 2017 to 2022. My research interests include developing cutting-edge algorithms to simulate quantum materials, utilising machine learning algorithms for materials discovery and modeling, and applying quantum algorithms in combinatorial optimisation problems.

Leave a Reply

Your email address will not be published. Required fields are marked *