[Theory] [Theory Lunch] Vishnu Iyer, Wednesday 10/26 12:30pm-1:30pm, JCL 298.

[Antares Chen]

************************************************************
**************************

*Date**:* October 26, 2022
*Time: *12:30pm CT
*Location: *JCL 298

Speaker: Vishnu Iyer <https://vishnuiyer.org/>

*Title: *Low-Stabilizer-Complexity Quantum States Are Not Pseudorandom

*Zoom: *[link
<https://uchicago.zoom.us/j/98326935804?pwd=ZFJGYUNXb2dkTFFQNWllM1JybUJwUT09>
]

*Abstract:* We show that quantum states with "low stabilizer complexity"
can be efficiently distinguished from Haar-random. Specifically, given an
$n$-qubit pure state $\lvert \psi \rangle$, we give an efficient algorithm
that distinguishes whether $\lvert \psi \rangle$ is (i) Haar-random or (ii)
a state with stabilizer fidelity at least $\frac{1}{k}$ (i.e., has fidelity
at least $\frac{1}{k}$ with some stabilizer state), promised that one of
these is the case. With black-box access to $\lvert \psi \rangle$, our
algorithm uses $O \big( k^{12} \cdot \log(1/\delta) \big)$ copies of
$\lvert \psi \\rangle$ and $O\big( nk^{12} \cdot \log (1/\\delta) \big)$
time to succeed with probability at least $1 - \delta$, and, with access to
a state preparation unitary for $\lvert \psi \rangle$ (and its inverse),
$O\big( k^{3} \cdot \\log(1/\delta) \big)$ queries and $O(nk^{3} \cdot
\log(1/ \delta) \big)$ time suffice.

As a corollary, we prove that $\omega\big( \log(n) \big)$ $T$-gates are
necessary for any $\mathsf{Clifford} + T$ circuit to prepare
computationally pseudorandom quantum states, a first-of-its-kind lower
bound.

Based on https://arxiv.org/abs/2209.14530

[Theory Lunch Webpage
<https://urldefense.com/v3/__https://orecchia.net/event/theory-lunch/__;!!BpyFHLRN4TMTrA!pwdRh9yLA-IBD6NCNvREJGd9Nj5jtC6_N-AowF6HSwIQeb1FPAmu0L_tAswwp_F5nRs$>
]
[Theory Lunch Calendar
<https://urldefense.com/v3/__https://calendar.google.com/calendar/u/0/embed?src=c_osgf1c1qemdras8mu7l7pdhjrs@group.calendar.google.com&ctz=America*Chicago__;Lw!!BpyFHLRN4TMTrA!pwdRh9yLA-IBD6NCNvREJGd9Nj5jtC6_N-AowF6HSwIQeb1FPAmu0L_tAsww4XtIRnQ$>
]

************************************************************
**************************
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20221024/ad03e99b/attachment.html>