Episode 151 Near-Term Quantum Algorithms for Optimization One of the most prominent applications of quantum computers is to solving hard constraint satisfaction and optimization problems. In this talk, I will discuss recent work on the applicability of the near-term quantum algorithm QAOA (the Quantum Approximate Optimization Algorithm) to problems in this domain. First I will discuss theoretical and numerical results on the ability of QAOA to solve the fundamental boolean satisfiability problem, in the form of random k-SAT. In this setting, based on these results, QAOA may be able to outperform leading classical algorithms. Second, I will discuss whether QAOA could be applied to solve hard protein folding problems. In this case, the situation seems more challenging and QAOA may not significantly outperform existing methods. This talk will primarily be based on the papers arXiv:2208.06909 (joint work with Sami Boulebnane) and arXiv:2204.01821 (joint work with Sami Boulebnane, Xavier Lucas, Agnes Meyder, and Stanislaw Adaszewski). Ashley Montanaro has worked in the field of quantum computing for 20 years, specialising in quantum algorithms and quantum computational complexity, and has published over 50 papers on this topic. He holds a PhD in quantum computing from the University of Bristol, supervised by Prof. Richard Jozsa, has been a postdoctoral fellow at the University of Cambridge, and is now Professor of Quantum Computation at Bristol. He holds an ERC Consolidator grant and was awarded a Whitehead Prize in 2017 by the London Mathematical Society. He served on the Steering Committee of the international conference on Quantum Information Processing (QIP) from 2016-19, and was a Founding Editor of the journal Quantum. He is co-founder and CEO of Phasecraft, a quantum software startup whose goal is to get the most out of near-term quantum computers.