<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
</head>
<body>
<div style="font-family: inherit; font-size: inherit; color: inherit; background-color: transparent;">
</div>
<div style="box-sizing: border-box; margin: 0px; font-family: Roboto, Helvetica, Arial, sans-serif; caret-color: rgb(33, 33, 33)">
Time: 11:30-12 on Wed, JCL298</div>
<div style="box-sizing: border-box; margin: 0px; font-family: Roboto, Helvetica, Arial, sans-serif; caret-color: rgb(33, 33, 33)">
Lunch afterward somewhere in HP — please email me if interested so I can get a headcount. </div>
<div style="box-sizing: border-box; margin: 0px; font-family: Roboto, Helvetica, Arial, sans-serif; caret-color: rgb(33, 33, 33)">
<br>
</div>
<div style="box-sizing: border-box; margin: 0px; font-family: Roboto, Helvetica, Arial, sans-serif; caret-color: rgb(33, 33, 33)">
<br>
</div>
<div style="box-sizing: border-box; margin: 0px; font-family: Roboto, Helvetica, Arial, sans-serif; caret-color: rgb(33, 33, 33)">
Title: Unitary Complexity Theory and the Uhlmann Transformation Problem</div>
<div style="box-sizing: border-box; margin: 0px; font-family: Roboto, Helvetica, Arial, sans-serif; caret-color: rgb(33, 33, 33)">
<br style="box-sizing: border-box">
</div>
<div style="box-sizing: border-box; margin: 0px; font-family: Roboto, Helvetica, Arial, sans-serif; caret-color: rgb(33, 33, 33)">
Abstract:<span> </span><br style="box-sizing: border-box">
</div>
<div style="box-sizing: border-box; margin: 0px; font-family: Roboto, Helvetica, Arial, sans-serif; caret-color: rgb(33, 33, 33)">
<br style="box-sizing: border-box">
</div>
<div style="box-sizing: border-box; margin: 0px; font-family: Roboto, Helvetica, Arial, sans-serif; caret-color: rgb(33, 33, 33)">
<span style="box-sizing: border-box; margin: 0px">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.<span> </span><br style="box-sizing: border-box">
</span></div>
<div style="box-sizing: border-box; margin: 0px; font-family: Roboto, Helvetica, Arial, sans-serif; caret-color: rgb(33, 33, 33)">
<span style="box-sizing: border-box; margin: 0px"><br style="box-sizing: border-box">
</span></div>
<div style="box-sizing: border-box; margin: 0px; font-family: Roboto, Helvetica, Arial, sans-serif; caret-color: rgb(33, 33, 33)">
<span style="box-sizing: border-box; margin: 0px">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.</span></div>
<div style="box-sizing: border-box; margin: 0px; font-family: Roboto, Helvetica, Arial, sans-serif; caret-color: rgb(33, 33, 33)">
<span style="box-sizing: border-box; margin: 0px"><br style="box-sizing: border-box">
</span></div>
<div style="box-sizing: border-box; margin: 0px; font-family: Roboto, Helvetica, Arial, sans-serif; caret-color: rgb(33, 33, 33)">
<span style="box-sizing: border-box; margin: 0px">Joint work with Yuval Efron, Tony Metger, Alexander Proemba, Luowen Qian, and Henry Yuen.</span></div>
<br>
<div><br>
</div>
<div><br>
</div>
<div>-C<br>
I am on mobile and am responding quickly. Please excuse the brevity.</div>
<div></div>
<br>
<hr style="display:inline-block;width:98%" tabindex="-1">
<div id="divRplyFwdMsg" dir="ltr"><font face="Calibri, sans-serif" style="font-size:11pt" color="#000000"><b>From:</b> John Bostanci <chb2154@columbia.edu><br>
<b>Sent:</b> Monday, June 12, 2023 11:02 AM<br>
<b>To:</b> Christopher Kang <ctkang@uchicago.edu><br>
<b>Cc:</b> Antares Chen <antaresc@uchicago.edu>; Soumik Ghosh <soumikghosh@uchicago.edu><br>
<b>Subject:</b> Re: Visitor in Chicago!</font>
<div> </div>
</div>
<div>
<div dir="ltr">
<div>Hi Chris,</div>
<div><br>
</div>
<div>So sorry for the delay, here's the title and abstract:</div>
<div><br>
</div>
<div>Title: Unitary Complexity Theory and the Uhlmann Transformation Problem</div>
<div><br>
</div>
<div>Abstract: <br>
</div>
<div><br>
</div>
<div><span class="x_gmail-x4k7w5x x_gmail-x1h91t0o x_gmail-x1h9r5lt x_gmail-x1jfb8zj x_gmail-xv2umb2 x_gmail-x1beo9mf x_gmail-xaigb6o x_gmail-x12ejxvf x_gmail-x3igimt x_gmail-xarpa2k x_gmail-xedcshv x_gmail-x1lytzrv x_gmail-x1t2pt76 x_gmail-x7ja8zs x_gmail-x1qrby5j">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. <br>
</span></div>
<div><span class="x_gmail-x4k7w5x x_gmail-x1h91t0o x_gmail-x1h9r5lt x_gmail-x1jfb8zj x_gmail-xv2umb2 x_gmail-x1beo9mf x_gmail-xaigb6o x_gmail-x12ejxvf x_gmail-x3igimt x_gmail-xarpa2k x_gmail-xedcshv x_gmail-x1lytzrv x_gmail-x1t2pt76 x_gmail-x7ja8zs x_gmail-x1qrby5j"><br>
</span></div>
<div><span class="x_gmail-x4k7w5x x_gmail-x1h91t0o x_gmail-x1h9r5lt x_gmail-x1jfb8zj x_gmail-xv2umb2 x_gmail-x1beo9mf x_gmail-xaigb6o x_gmail-x12ejxvf x_gmail-x3igimt x_gmail-xarpa2k x_gmail-xedcshv x_gmail-x1lytzrv x_gmail-x1t2pt76 x_gmail-x7ja8zs x_gmail-x1qrby5j">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.</span></div>
<div><span class="x_gmail-x4k7w5x x_gmail-x1h91t0o x_gmail-x1h9r5lt x_gmail-x1jfb8zj x_gmail-xv2umb2 x_gmail-x1beo9mf x_gmail-xaigb6o x_gmail-x12ejxvf x_gmail-x3igimt x_gmail-xarpa2k x_gmail-xedcshv x_gmail-x1lytzrv x_gmail-x1t2pt76 x_gmail-x7ja8zs x_gmail-x1qrby5j"><br>
</span></div>
<div><span class="x_gmail-x4k7w5x x_gmail-x1h91t0o x_gmail-x1h9r5lt x_gmail-x1jfb8zj x_gmail-xv2umb2 x_gmail-x1beo9mf x_gmail-xaigb6o x_gmail-x12ejxvf x_gmail-x3igimt x_gmail-xarpa2k x_gmail-xedcshv x_gmail-x1lytzrv x_gmail-x1t2pt76 x_gmail-x7ja8zs x_gmail-x1qrby5j">Joint
work with Yuval Efron, Tony Metger, Alexander Proemba, Luowen Qian, and Henry Yuen.</span></div>
<div><span class="x_gmail-x4k7w5x x_gmail-x1h91t0o x_gmail-x1h9r5lt x_gmail-x1jfb8zj x_gmail-xv2umb2 x_gmail-x1beo9mf x_gmail-xaigb6o x_gmail-x12ejxvf x_gmail-x3igimt x_gmail-xarpa2k x_gmail-xedcshv x_gmail-x1lytzrv x_gmail-x1t2pt76 x_gmail-x7ja8zs x_gmail-x1qrby5j"><br>
</span></div>
<div><span class="x_gmail-x4k7w5x x_gmail-x1h91t0o x_gmail-x1h9r5lt x_gmail-x1jfb8zj x_gmail-xv2umb2 x_gmail-x1beo9mf x_gmail-xaigb6o x_gmail-x12ejxvf x_gmail-x3igimt x_gmail-xarpa2k x_gmail-xedcshv x_gmail-x1lytzrv x_gmail-x1t2pt76 x_gmail-x7ja8zs x_gmail-x1qrby5j">Thanks!</span></div>
<div><span class="x_gmail-x4k7w5x x_gmail-x1h91t0o x_gmail-x1h9r5lt x_gmail-x1jfb8zj x_gmail-xv2umb2 x_gmail-x1beo9mf x_gmail-xaigb6o x_gmail-x12ejxvf x_gmail-x3igimt x_gmail-xarpa2k x_gmail-xedcshv x_gmail-x1lytzrv x_gmail-x1t2pt76 x_gmail-x7ja8zs x_gmail-x1qrby5j">John
Bostanci<br>
</span></div>
</div>
<br>
<div class="x_gmail_quote">
<div dir="ltr" class="x_gmail_attr">On Tue, Jun 6, 2023 at 4:31 PM Christopher Kang <<a href="mailto:ctkang@uchicago.edu" data-auth="NotApplicable">ctkang@uchicago.edu</a>> wrote:<br>
</div>
<blockquote class="x_gmail_quote" style="margin:0px 0px 0px 0.8ex; border-left:1px solid rgb(204,204,204); padding-left:1ex">
<div class="x_msg7515787268420324494">
<div dir="ltr">
<div style="font-family:Calibri,Helvetica,sans-serif; font-size:12pt; color:rgb(0,0,0)">
I think this is doable. John, could you please send a talk title and abstract? </div>
<div style="font-family:Calibri,Helvetica,sans-serif; font-size:12pt; color:rgb(0,0,0)">
<br>
</div>
<div style="font-family:Calibri,Helvetica,sans-serif; font-size:12pt; color:rgb(0,0,0)">
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. </div>
<div>
<div style="font-family:Calibri,Helvetica,sans-serif; font-size:12pt; color:rgb(0,0,0)">
<br>
</div>
<div id="x_m_7515787268420324494Signature">
<div>
<div style="font-family:Calibri,Arial,Helvetica,sans-serif; font-size:12pt; color:rgb(0,0,0)">
<span style="font-family:Calibri,Helvetica,sans-serif">Best regards,</span></div>
<div style="font-family:Calibri,Arial,Helvetica,sans-serif; font-size:12pt; color:rgb(0,0,0)">
<span style="font-family:Calibri,Helvetica,sans-serif">Christopher Kang</span></div>
</div>
</div>
</div>
<div id="x_m_7515787268420324494appendonsend"></div>
<hr style="display:inline-block; width:98%">
<div id="x_m_7515787268420324494divRplyFwdMsg" dir="ltr"><font face="Calibri, sans-serif" color="#000000" style="font-size:11pt"><b>From:</b> John Bostanci <<a href="mailto:chb2154@columbia.edu" data-auth="NotApplicable">chb2154@columbia.edu</a>><br>
<b>Sent:</b> Sunday, June 4, 2023 11:44 AM<br>
<b>To:</b> Christopher Kang <<a href="mailto:ctkang@uchicago.edu" data-auth="NotApplicable">ctkang@uchicago.edu</a>><br>
<b>Cc:</b> Antares Chen <<a href="mailto:antaresc@uchicago.edu" data-auth="NotApplicable">antaresc@uchicago.edu</a>>; Soumik Ghosh <<a href="mailto:soumikghosh@uchicago.edu" data-auth="NotApplicable">soumikghosh@uchicago.edu</a>><br>
<b>Subject:</b> Re: Visitor in Chicago!</font>
<div> </div>
</div>
<div>
<div dir="auto">Hi Chris,</div>
<div dir="auto"><br>
</div>
<div dir="auto">Lunch isn’t a requirement for me (personally), so if it’s a hassle don’t worry about it!</div>
<div dir="auto"><br>
</div>
<div dir="auto">Thanks!</div>
<div dir="auto">John Bostanci</div>
<div><br>
<div>
<div dir="ltr">On Fri, Jun 2, 2023 at 5:08 PM Christopher Kang <<a href="mailto:ctkang@uchicago.edu" data-auth="NotApplicable">ctkang@uchicago.edu</a>> wrote:<br>
</div>
<blockquote style="margin:0px 0px 0px 0.8ex; border-left:1px solid rgb(204,204,204); padding-left:1ex">
<div dir="ltr">
<div style="font-family:Calibri,Helvetica,sans-serif; font-size:12pt; color:rgb(0,0,0)">
Is lunch a requirement? If so, we'll need to sync with leadership on budgets.</div>
<div style="font-family:Calibri,Helvetica,sans-serif; font-size:12pt; color:rgb(0,0,0)">
<br>
</div>
<hr style="display:inline-block; width:98%">
<div id="x_m_7515787268420324494x_m_4681548846828714730divRplyFwdMsg" dir="ltr"><font face="Calibri, sans-serif" style="font-size:11pt; font-family:Calibri,sans-serif; color:rgb(0,0,0)"><b style="font-family:Calibri,sans-serif">From:</b> Christopher Kang <<a href="mailto:ctkang@uchicago.edu" data-auth="NotApplicable" style="font-family:Calibri,sans-serif">ctkang@uchicago.edu</a>><br>
<b style="font-family:Calibri,sans-serif">Sent:</b> Tuesday, May 30, 2023 5:41 PM<br>
<b style="font-family:Calibri,sans-serif">To:</b> Soumik Ghosh <<a href="mailto:soumikghosh@uchicago.edu" data-auth="NotApplicable" style="font-family:Calibri,sans-serif">soumikghosh@uchicago.edu</a>></font></div>
</div>
<div dir="ltr">
<div id="x_m_7515787268420324494x_m_4681548846828714730divRplyFwdMsg" dir="ltr"><font face="Calibri, sans-serif" style="font-size:11pt; font-family:Calibri,sans-serif; color:rgb(0,0,0)"><br>
<b style="font-family:Calibri,sans-serif">Cc:</b> John Bostanci <<a href="mailto:chb2154@columbia.edu" data-auth="NotApplicable" style="font-family:Calibri,sans-serif">chb2154@columbia.edu</a>>; Antares Chen <<a href="mailto:antaresc@uchicago.edu" data-auth="NotApplicable" style="font-family:Calibri,sans-serif">antaresc@uchicago.edu</a>><br>
<b style="font-family:Calibri,sans-serif">Subject:</b> Re: Visitor in Chicago!</font>
<div> </div>
</div>
<div dir="ltr">
<div style="font-family:Calibri,Helvetica,sans-serif; font-size:12pt; color:rgb(0,0,0)">
Okay, allow me to sync with Antares on this. Hoping to have a response by EOW. </div>
<div>
<div style="font-family:Calibri,Helvetica,sans-serif; font-size:12pt; color:rgb(0,0,0)">
<br>
</div>
<div id="x_m_7515787268420324494x_m_4681548846828714730x_Signature">
<div>
<div style="font-family:Calibri,Arial,Helvetica,sans-serif; font-size:12pt; color:rgb(0,0,0)">
<span style="font-family:Calibri,Helvetica,sans-serif">Best regards,</span></div>
<div style="font-family:Calibri,Arial,Helvetica,sans-serif; font-size:12pt; color:rgb(0,0,0)">
<span style="font-family:Calibri,Helvetica,sans-serif">Christopher Kang</span></div>
</div>
</div>
</div>
<div id="x_m_7515787268420324494x_m_4681548846828714730x_appendonsend"></div>
<hr style="display:inline-block; width:98%">
<div id="x_m_7515787268420324494x_m_4681548846828714730x_divRplyFwdMsg" dir="ltr">
<font face="Calibri, sans-serif" style="font-size:11pt; font-family:Calibri,sans-serif; color:rgb(0,0,0)"><b style="font-family:Calibri,sans-serif">From:</b> Soumik Ghosh <<a href="mailto:soumikghosh@uchicago.edu" data-auth="NotApplicable" style="font-family:Calibri,sans-serif">soumikghosh@uchicago.edu</a>><br>
<b style="font-family:Calibri,sans-serif">Sent:</b> Tuesday, May 30, 2023 3:36 PM<br>
<b style="font-family:Calibri,sans-serif">To:</b> Christopher Kang <<a href="mailto:ctkang@uchicago.edu" data-auth="NotApplicable" style="font-family:Calibri,sans-serif">ctkang@uchicago.edu</a>><br>
<b style="font-family:Calibri,sans-serif">Cc:</b> John Bostanci <<a href="mailto:chb2154@columbia.edu" data-auth="NotApplicable" style="font-family:Calibri,sans-serif">chb2154@columbia.edu</a>>; Antares Chen <<a href="mailto:antaresc@uchicago.edu" data-auth="NotApplicable" style="font-family:Calibri,sans-serif">antaresc@uchicago.edu</a>><br>
<b style="font-family:Calibri,sans-serif">Subject:</b> Re: Visitor in Chicago!</font>
<div> </div>
</div>
<div dir="auto">Yes, I was thinking of the Theory lunch, if that’s possible.<br>
<br>
<div dir="ltr">
<blockquote type="cite"><br>
On May 30, 2023, at 3:35 PM, Christopher Kang <<a href="mailto:ctkang@uchicago.edu" data-auth="NotApplicable">ctkang@uchicago.edu</a>> wrote:<br>
<br>
</blockquote>
</div>
<blockquote type="cite">
<div dir="ltr">
<div style="font-family:Calibri,Helvetica,sans-serif; font-size:12pt; color:rgb(0,0,0)">
Hey Soumik and John! </div>
<div style="font-family:Calibri,Helvetica,sans-serif; font-size:12pt; color:rgb(0,0,0)">
<br>
</div>
<div style="font-family:Calibri,Helvetica,sans-serif; font-size:12pt; color:rgb(0,0,0)">
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.</div>
<div style="font-family:Calibri,Helvetica,sans-serif; font-size:12pt; color:rgb(0,0,0)">
<br>
</div>
<div style="font-family:Calibri,Helvetica,sans-serif; font-size:12pt; color:rgb(0,0,0)">
Regardless, let's try to find a way to have John present!</div>
<div>
<div style="font-family:Calibri,Helvetica,sans-serif; font-size:12pt; color:rgb(0,0,0)">
<br>
</div>
<div id="x_m_7515787268420324494x_m_4681548846828714730x_x_Signature">
<div>
<div style="font-family:Calibri,Arial,Helvetica,sans-serif; font-size:12pt; color:rgb(0,0,0)">
<span style="font-family:Calibri,Helvetica,sans-serif">Best regards,</span></div>
<div style="font-family:Calibri,Arial,Helvetica,sans-serif; font-size:12pt; color:rgb(0,0,0)">
<span style="font-family:Calibri,Helvetica,sans-serif">Christopher Kang</span></div>
</div>
</div>
</div>
<div id="x_m_7515787268420324494x_m_4681548846828714730x_x_appendonsend"></div>
<hr style="display:inline-block; width:98%">
<div id="x_m_7515787268420324494x_m_4681548846828714730x_x_divRplyFwdMsg" dir="ltr">
<font face="Calibri, sans-serif" style="font-size:11pt; font-family:Calibri,sans-serif; color:rgb(0,0,0)"><b style="font-family:Calibri,sans-serif">From:</b> Soumik Ghosh <<a href="mailto:soumikghosh@uchicago.edu" data-auth="NotApplicable" style="font-family:Calibri,sans-serif">soumikghosh@uchicago.edu</a>><br>
<b style="font-family:Calibri,sans-serif">Sent:</b> Tuesday, May 30, 2023 3:19 PM<br>
<b style="font-family:Calibri,sans-serif">To:</b> Christopher Kang <<a href="mailto:ctkang@uchicago.edu" data-auth="NotApplicable" style="font-family:Calibri,sans-serif">ctkang@uchicago.edu</a>><br>
<b style="font-family:Calibri,sans-serif">Cc:</b> John Bostanci <<a href="mailto:chb2154@columbia.edu" data-auth="NotApplicable" style="font-family:Calibri,sans-serif">chb2154@columbia.edu</a>><br>
<b style="font-family:Calibri,sans-serif">Subject:</b> Visitor in Chicago!</font>
<div> </div>
</div>
<div dir="ltr">
<div style="font-family:Calibri,Arial,Helvetica,sans-serif; font-size:12pt; color:rgb(0,0,0)">
Hi Chris!</div>
<div style="font-family:Calibri,Arial,Helvetica,sans-serif; font-size:12pt; color:rgb(0,0,0)">
<br>
</div>
<div style="font-family:Calibri,Arial,Helvetica,sans-serif; font-size:12pt; color:rgb(0,0,0)">
My friend John Bostanci, a graduate student from Henry Yuen's group in Columbia University, is visiting UChicago, from June 11<span style="font-family:Calibri,Arial,Helvetica,sans-serif"><sup style="font-family:Calibri,Arial,Helvetica,sans-serif">th</sup> to
June <span style="text-decoration:none; font-family:Calibri,Arial,Helvetica,sans-serif; display:inline; background-color:rgb(255,255,255)">
14</span><span style="margin:0px; text-decoration:none; font-family:Calibri,Arial,Helvetica,sans-serif"><sup style="font-family:Calibri,Arial,Helvetica,sans-serif">th</sup></span>. He works on many aspects of quantum computing.</span></div>
<div style="font-family:Calibri,Arial,Helvetica,sans-serif; font-size:12pt; color:rgb(0,0,0)">
<span style="font-family:Calibri,Arial,Helvetica,sans-serif"><br>
</span></div>
<div style="font-family:Calibri,Arial,Helvetica,sans-serif; font-size:12pt; color:rgb(0,0,0)">
<span style="font-family:Calibri,Arial,Helvetica,sans-serif">He was interested in giving a talk at our department's weekly CS student seminar on Wednesday. Might that be possible to arrange?</span></div>
<div style="font-family:Calibri,Arial,Helvetica,sans-serif; font-size:12pt; color:rgb(0,0,0)">
<span style="font-family:Calibri,Arial,Helvetica,sans-serif"><br>
</span></div>
<div style="font-family:Calibri,Arial,Helvetica,sans-serif; font-size:12pt; color:rgb(0,0,0)">
<span style="font-family:Calibri,Arial,Helvetica,sans-serif">Best,
<div style="font-family:Calibri,Arial,Helvetica,sans-serif">Soumik</div>
</span></div>
</div>
</div>
</blockquote>
</div>
</div>
</div>
</blockquote>
</div>
</div>
</div>
</div>
</div>
</blockquote>
</div>
</div>
</body>
</html>