[Theory] Special Theory Talk Wed: John Bostanci

[Christopher Kang]

Time: 11:30-12 on Wed, JCL298
Lunch afterward somewhere in HP — please email me if interested so I can get a headcount.


Title: Unitary Complexity Theory and the Uhlmann Transformation Problem

Abstract:

Quantum complexity theory is typically focused on quantum algorithms for classical tasks -- those with classical inputs and outputs. However there has been increasing interest in studying the computational difficulty of tasks with quantum inputs and/or outputs. Examples include preparing ground states of Hamiltonians or breaking quantum cryptographic protocols. Many techniques and approaches from traditional complexity theory are inadequate for reasoning about such inherently quantum tasks, suggesting a need for a "fully quantum" complexity theory.

In this talk I discuss some facets and themes of a "fully quantum" complexity theory. One natural problem that turns out to be central to the conversation, and is also our main vehicle for introducing this new framework, is the Uhlmann Transformation Problem. I will motivate it, and discuss the pivotal role it plays when considering a "fully quantum" complexity theory. In particular, the problem turns out to be polynomial time equivalent to several seemingly unrelated problems, such as breaking a quantum bit-commitment scheme, performing optimal state transfer, and decoding the radiation of an evaporating black hole. Furthermore, the problem turns out to be complete for a "unitary complexity" analogue of SZK. One nice corollary of these result is a quantum emulation of a well known connection between One Way Functions and classical SZK.

Joint work with Yuval Efron, Tony Metger, Alexander Proemba, Luowen Qian, and Henry Yuen.



-C
I am on mobile and am responding quickly. Please excuse the brevity.

________________________________
From: John Bostanci <chb2154 at columbia.edu>
Sent: Monday, June 12, 2023 11:02 AM
To: Christopher Kang <ctkang at uchicago.edu>
Cc: Antares Chen <antaresc at uchicago.edu>; Soumik Ghosh <soumikghosh at uchicago.edu>
Subject: Re: Visitor in Chicago!

Hi Chris,

So sorry for the delay, here's the title and abstract:

Title: Unitary Complexity Theory and the Uhlmann Transformation Problem

Abstract:

Quantum complexity theory is typically focused on quantum algorithms for classical tasks -- those with classical inputs and outputs. However there has been increasing interest in studying the computational difficulty of tasks with quantum inputs and/or outputs. Examples include preparing ground states of Hamiltonians or breaking quantum cryptographic protocols. Many techniques and approaches from traditional complexity theory are inadequate for reasoning about such inherently quantum tasks, suggesting a need for a "fully quantum" complexity theory.

In this talk I discuss some facets and themes of a "fully quantum" complexity theory. One natural problem that turns out to be central to the conversation, and is also our main vehicle for introducing this new framework, is the Uhlmann Transformation Problem. I will motivate it, and discuss the pivotal role it plays when considering a "fully quantum" complexity theory. In particular, the problem turns out to be polynomial time equivalent to several seemingly unrelated problems, such as breaking a quantum bit-commitment scheme, performing optimal state transfer, and decoding the radiation of an evaporating black hole. Furthermore, the problem turns out to be complete for a "unitary complexity" analogue of SZK. One nice corollary of these result is a quantum emulation of a well known connection between One Way Functions and classical SZK.

Joint work with Yuval Efron, Tony Metger, Alexander Proemba, Luowen Qian, and Henry Yuen.

Thanks!
John Bostanci

On Tue, Jun 6, 2023 at 4:31 PM Christopher Kang <ctkang at uchicago.edu<mailto:ctkang at uchicago.edu>> wrote:
I think this is doable. John, could you please send a talk title and abstract?

My current hope is to have the talk say 11-1130 on Wed the 14th, then bring you to lunch afterwards at Nella's. We have a small budget for the summer.

Best regards,
Christopher Kang
________________________________
From: John Bostanci <chb2154 at columbia.edu<mailto:chb2154 at columbia.edu>>
Sent: Sunday, June 4, 2023 11:44 AM
To: Christopher Kang <ctkang at uchicago.edu<mailto:ctkang at uchicago.edu>>
Cc: Antares Chen <antaresc at uchicago.edu<mailto:antaresc at uchicago.edu>>; Soumik Ghosh <soumikghosh at uchicago.edu<mailto:soumikghosh at uchicago.edu>>
Subject: Re: Visitor in Chicago!

Hi Chris,

Lunch isn’t a requirement for me (personally), so if it’s a hassle don’t worry about it!

Thanks!
John Bostanci

On Fri, Jun 2, 2023 at 5:08 PM Christopher Kang <ctkang at uchicago.edu<mailto:ctkang at uchicago.edu>> wrote:
Is lunch a requirement? If so, we'll need to sync with leadership on budgets.

________________________________
From: Christopher Kang <ctkang at uchicago.edu<mailto:ctkang at uchicago.edu>>
Sent: Tuesday, May 30, 2023 5:41 PM
To: Soumik Ghosh <soumikghosh at uchicago.edu<mailto:soumikghosh at uchicago.edu>>

Cc: John Bostanci <chb2154 at columbia.edu<mailto:chb2154 at columbia.edu>>; Antares Chen <antaresc at uchicago.edu<mailto:antaresc at uchicago.edu>>
Subject: Re: Visitor in Chicago!

Okay, allow me to sync with Antares on this. Hoping to have a response by EOW.

Best regards,
Christopher Kang
________________________________
From: Soumik Ghosh <soumikghosh at uchicago.edu<mailto:soumikghosh at uchicago.edu>>
Sent: Tuesday, May 30, 2023 3:36 PM
To: Christopher Kang <ctkang at uchicago.edu<mailto:ctkang at uchicago.edu>>
Cc: John Bostanci <chb2154 at columbia.edu<mailto:chb2154 at columbia.edu>>; Antares Chen <antaresc at uchicago.edu<mailto:antaresc at uchicago.edu>>
Subject: Re: Visitor in Chicago!

Yes, I was thinking of the Theory lunch, if that’s possible.


On May 30, 2023, at 3:35 PM, Christopher Kang <ctkang at uchicago.edu<mailto:ctkang at uchicago.edu>> wrote:


Hey Soumik and John!

Just to confirm -- do you mean the Theory Lunch? If so, we'll need to check with admin. I believe tomorrow will be the last time before summer.

Regardless, let's try to find a way to have John present!

Best regards,
Christopher Kang
________________________________
From: Soumik Ghosh <soumikghosh at uchicago.edu<mailto:soumikghosh at uchicago.edu>>
Sent: Tuesday, May 30, 2023 3:19 PM
To: Christopher Kang <ctkang at uchicago.edu<mailto:ctkang at uchicago.edu>>
Cc: John Bostanci <chb2154 at columbia.edu<mailto:chb2154 at columbia.edu>>
Subject: Visitor in Chicago!

Hi Chris!

My friend John Bostanci, a graduate student from Henry Yuen's group in Columbia University, is visiting UChicago, from June 11th to June 14th. He works on many aspects of quantum computing.

He was interested in giving a talk at our department's weekly CS student seminar on Wednesday. Might that be possible to arrange?

Best,
Soumik
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20230613/5f18cc1f/attachment-0001.html>