BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:CQIF Seminar
SUMMARY:Efficient Quantum State Synthesis with One Query -
Gregory Rosenthal\, CST\, University of Cambridge
DTSTART;TZID=Europe/London:20231109T141500
DTEND;TZID=Europe/London:20231109T153000
UID:TALK208267AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/208267
DESCRIPTION:We present a polynomial-time quantum algorithm mak
ing a single query (in superposition) to a classic
al oracle\, such that for every state |ψ⟩ there ex
ists a choice of oracle that makes the algorithm c
onstruct an exponentially close approximation of\n
|ψ⟩. Previous algorithms for this problem either u
sed a linear number of queries and polynomial time
\, or a constant number of queries and polynomiall
y many ancillae but no nontrivial bound on the run
time. As corollaries we do the following:\n• We si
mplify the proof that statePSPACE ⊆ stateQIP (a qu
antum state analogue of PSPACE ⊆ IP) and show that
a constant number of rounds of interaction suffic
es.\n• We show that QACf0 lower bounds for constru
cting explicit states would imply breakthrough cir
cuit lower bounds for computing explicit boolean f
unctions.\n• We prove that every n-qubit state can
be constructed to within 0.01 error by an O(2^n/n
)-size circuit over an appropriate finite gate set
. More generally we give a size-error tradeoff whi
ch\, by a counting argument\, is optimal for any f
inite gate set.\nTo appear in SODA 2024. Paper ava
ilable at https://arxiv.org/abs/2306.01723.
LOCATION:MR2
CONTACT:Sergii Strelchuk
END:VEVENT
END:VCALENDAR