Searching for quantum advantage in optimisation: myths, maths, and the travelling salesman problem скачать в хорошем качестве

Searching for quantum advantage in optimisation: myths, maths, and the travelling salesman problem

Speaker: Professor Kate Smith-Miles AO FAA OPTIMA _University of Melbourne This seminar was presented as a special joint OPTIMA & MIQT Quantum seminar event Title: Searching for quantum advantage in optimisation: myths, maths, and the travelling salesman problem Summary: This talk is based on the following recently published paper in Quantum Science and Technology: The travelling salesperson problem and the challenges of near-term quantum advantage [https://iopscience.iop.org/article/10...]. Over the last two decades, the Travelling Salesperson Problem (TSP) has been used as a benchmark to explore the potential advantage of quantum computers over classical ones. While the TSP is intuitive and relevant to large-scale transport and logistics, we argue it is not well-suited to current QUBO-based quantum optimisation methods such as quantum annealing (QA) and QAOA. This talk reviews two decades of research concluding that current quantum methods are unlikely to outperform classical state-of-the-art approaches for TSP and similar constrained optimisation problems. We present mathematical arguments explaining the limitations of QUBO-based methods, drawing parallels with early neural network research. The talk concludes with promising directions for quantum optimisation using non-QUBO-based hybrid approaches, where quantum search may accelerate components of conventional algorithms. Bio: Kate Smith-Miles has significant leadership experience that cuts across academic disciplines and extensive industry engagement experience. She is a Melbourne Laureate Professor of Applied Mathematics, and Pro Vice-Chancellor (Research Capability) at The University of Melbourne. Before becoming the OPTIMA Centre Director, she was foundational Director of the Monash Academy for Cross & Interdisciplinary Mathematical Applications (MAXIMA). She recently concluded a 5-year ARC Georgina Sweet Australian Laureate Fellowship, which advanced a new methodology known as Instance Space Analysis [http://matilda.unimelb.edu.au/] for rigorously stress-testing algorithms to ensure trust. She has completed 7 ARC Linkage Projects, several other industry contract research projects, and has supervised over 30 PhD students and over 30 postdoctoral fellows. She has collaborated with industry in manufacturing, energy, security, defence, healthcare, and finance. As Chair of the Advisory Board for the Choose Maths program – a $22m partnership between BHP Billiton Foundation and the Australian Mathematical Sciences Institute – she has provided leadership to increase female participation in mathematics through mentoring, outreach and training.