Dear all,
We are excited to have Kunal Marwaha (U Chicago) speak at the next Quantum Information
Seminar on Thurs Feb 22, 4:30-5:30 pm in Jefferson 250. Details below.
Title: On the promise of quantum advantage for classical optimization
Abstract: The holy grail of quantum computing is a practical use for today's
machines. A popular suggestion is that quantum computers can approximately solve
optimization problems better than classical computers, despite little theoretical
evidence. I take this claim seriously, analyzing and comparing average-case algorithms on
CSPs of large (but fixed) clause density. It turns out that both algorithms and
obstructions from spin glass theory naturally transfer to sparse CSPs, culminating in an
optimal algorithm among all bounded-fanout quantum and classical circuits of depth up to ε
· log n. This talk surveys several recent works, especially BFMVZ21, JMSS22, and CHM23.
With Best Regards,
Anurag Anshu
Show replies by date
A gentle reminder that this is happening tomorrow (Thurs Feb 22) 4:30-5:30 pm in Jefferson
250.
Get Outlook for iOS<https://aka.ms/o0ukef>
________________________________
From: Anshu, Anurag
Sent: Saturday, February 17, 2024 12:01:21 AM
To: quantum-info-group(a)lists.fas.harvard.edu
<quantum-info-group(a)lists.fas.harvard.edu>du>;
harvard-quantum-initiative(a)lists.fas.harvard.edu
<harvard-quantum-initiative(a)lists.fas.harvard.edu>du>; Cotler, Jordan Saul
<jcotler(a)fas.harvard.edu>du>; Sahay, Rahul <rsahay(a)g.harvard.edu>
Cc: kmarw(a)uchicago.edu <kmarw(a)uchicago.edu>
Subject: Quantum Information Seminar Feb 22 - Kunal Marwaha
Dear all,
We are excited to have Kunal Marwaha (U Chicago) speak at the next Quantum Information
Seminar on Thurs Feb 22, 4:30-5:30 pm in Jefferson 250. Details below.
Title: On the promise of quantum advantage for classical optimization
Abstract: The holy grail of quantum computing is a practical use for today's
machines. A popular suggestion is that quantum computers can approximately solve
optimization problems better than classical computers, despite little theoretical
evidence. I take this claim seriously, analyzing and comparing average-case algorithms on
CSPs of large (but fixed) clause density. It turns out that both algorithms and
obstructions from spin glass theory naturally transfer to sparse CSPs, culminating in an
optimal algorithm among all bounded-fanout quantum and classical circuits of depth up to ε
· log n. This talk surveys several recent works, especially BFMVZ21, JMSS22, and CHM23.
With Best Regards,
Anurag Anshu