Join OPTIMA and Melbourne Initiative for Quantum Technology for this special joint seminar event presented by OPTIMA Centre Director, Pro Vice-Chancellor (Research Capability) at The University of Melbourne, and a Melbourne Laureate Professor of Applied Mathematics in the School of Mathematics and Statistics, Professor Kate Smith-Miles AO FAA.
Abstract:
Over the last two decades, the travelling salesperson problem (TSP) has been used as a benchmark problem to explore the advantage of quantum computers over conventional computers. Its advantages include being easy to understand, highlighting the challenges of searching through an exponentially growing number of possible solutions, with direct applications to large-scale transportation and logistics problems in industry.
However, we argue that the TSP is not a problem well-suited to current QUBO-based quantum optimisation methods (like quantum annealing (QA) and QAOA). At what point is a call made that quantum advantage is not likely, and efforts should be focused on other problems?
This talk reviews 20 years of efforts to conclude current quantum methods are unlikely to ever be competitive with the classical state of the art for TSP and many other constrained optimisation problems. We offer mathematical arguments for why QUBO-based methods are not well suited for tackling the challenges of the TSP landscape, drawing parallels with similar observations made almost four decades ago for QUBO-based neural networks.
We discuss the numerous challenges that must be overcome for current quantum methods to handle constrained optimisation. Finally, we discuss more promising directions for quantum optimisation using non-QUBO-based hybrid approaches, where quantum search could accelerate components of conventional algorithms.
This talk is based on the following recently published paper in Quantum Science and Technology:
https://iopscience.iop.org/article/10.1088/2058-9565/add61d
Presenter
Prof. Kate Smith-Miles
Kate Smith-Miles AO FAA is Pro Vice-Chancellor (Research Capability) and a Melbourne Laureate Professor in the School of Mathematics and Statistics at The University of Melbourne. She is also Director of the ARC Training Centre in Optimisation Technologies, Integrated Methodologies, and Applications (OPTIMA). She has previously held a five year Laureate Fellowship from the Australian Research Council with a Georgina Sweet Award, and has held positions as President of the Australian Mathematical Society (2016-2018), a member of the Australian Research Council College of Experts (2017-2019), and Associate Dean (Enterprise and Innovation) in the University’s Faculty of Science (2019-2023). Prior to joining The University of Melbourne in September 2017, she was Professor of Applied Mathematics at Monash University, where she was also Head of the School of Mathematical Sciences (2009-2014), and inaugural Director of the Monash Academy for Cross & Interdisciplinary Mathematical Applications (MAXIMA) from 2013-2017. She was also previously Head of the School of Engineering and Information Technology at Deakin University (2006-2009) with a Chair in Engineering. She obtained her first Professorship in Information Technology at Monash University, where she worked from 1996-2006. Professorships in three disciplines (mathematics, engineering, and information technology) have given her an interdisciplinary breadth reflected in much of her research.
