[Theory] FW: Theory Lunch 2023-03-29T17:30:00.000Z

[Christopher Kang]

________________________________
From: noreply+automations at airtableemail.com <noreply+automations at airtableemail.com>On Behalf OfTheoryBot (via Airtable) <noreply+automations at airtableemail.com>
Sent: Wednesday, March 29, 2023 12:06:37 AM (UTC-06:00) Central Time (US & Canada)
To: Antares Chen <antaresc at uchicago.edu>
Cc: Christopher Kang <ctkang at uchicago.edu>
Subject: Theory Lunch 2023-03-29T17:30:00.000Z


Today's Theory Lunch talk:

James Sud (University of Chicago): Estimating the Dynamics of the Quantum Approximate Optimization Algorithm

https://uchicago.zoom.us/j/91616319229?pwd=dDdXQnFXeGNubFRkZy9hTDQrcWlXdz09<https://urldefense.com/v3/__https://uchicago.zoom.us/j/91616319229?pwd=dDdXQnFXeGNubFRkZy9hTDQrcWlXdz09__;!!BpyFHLRN4TMTrA!-v8kQPcsQqah0lU-0BM3rCgvb8s4pNoJnz-XGWJJcnikLpFhsgjOlQeSslh4opDfcp3jxVExCHZn7a84QVVRg6TnVpz03yfbmH0$>

Description: The Quantum Approximate Optimization Algorithm (QAOA) is a well-studied (and much-hyped) quantum algorithm for solving combinatorial optimization problems. The circuit implementing QAOA consists of multiple layers of parameterized quantum gates. However, the performance of the algorithm with respect to classical algorithms is not well understood beyond restricted parameter and depth regimes. In this talk, we analyze the explicit formula for the evolution of a quantum state under one layer of QAOA, allowing us to describe the algorithm for any problem in any regime. An exact evaluation of this formula would take exponential time, so we leverage empirical observations about the state to form attempts to approximate the sum, including [arXiv:2211.09270 and arXiv:2201.03358]. We note that these methods are uncontrolled and seem to accurately predict QAOA performance only in certain parameter regimes, thus we label them "proxies" instead of "approximations". We describe attempts and challenges to make these methods more rigorous, thus deriving approximations with analytically-derived bounds, rather than empirically verified proxies.

Sent via Automations on         [Airtable] <https://urldefense.com/v3/__https://airtable.com?utm_medium=email&utm_source=product_team&utm_content=transactional-alerts__;!!BpyFHLRN4TMTrA!-v8kQPcsQqah0lU-0BM3rCgvb8s4pNoJnz-XGWJJcnikLpFhsgjOlQeSslh4opDfcp3jxVExCHZn7a84QVVRg6TnVpz0gNiBAL8$>
©2023 Airtable
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20230329/10d0a5c5/attachment.html>