Approximation algorithms are a natural remedy for classical NP-hardness, where a polynomial-time algorithm produces an approximate solution whose cost is guaranteed to be within some multiplicative factor of the optimum. The Quantum Approximation Optimization Algorithm and recent work in approximating extremal energy states of local Hamiltonians have prompted the study of quantum approximation algorithms. Can we expect these to offer provable advantages over classical counterparts? A potentially promising approach is to find optimization problems that have some underlying connection to quantum mechanics. I will discuss recent work in this vein on approximating Quantum Max Cut and other physically motivated local Hamiltonians that end up generalizing well-known classical discrete optimization problems. I will also overview recent results on quantum streaming algorithms for Max Cut and related problems, including a recently established exponential quantum streaming advantage.
Copyright. All Rights Reserved.