BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Efficient Quantum State Synthesis with One Query - Gregory Rosenth
 al\, CST\, University of Cambridge 
DTSTART:20231109T141500Z
DTEND:20231109T153000Z
UID:TALK208267@talks.cam.ac.uk
CONTACT:Sergii Strelchuk
DESCRIPTION:We present a polynomial-time quantum algorithm making a single
  query (in superposition) to a classical oracle\, such that for every stat
 e |ψ⟩ there exists a choice of oracle that makes the algorithm construc
 t an exponentially close approximation of\n|ψ⟩. Previous algorithms for
  this problem either used a linear number of queries and polynomial time\,
  or a constant number of queries and polynomially many ancillae but no non
 trivial bound on the runtime. As corollaries we do the following:\n• We 
 simplify the proof that statePSPACE ⊆ stateQIP (a quantum state analogue
  of PSPACE ⊆ IP) and show that a constant number of rounds of interactio
 n suffices.\n• We show that QACf0 lower bounds for constructing explicit
  states would imply breakthrough circuit lower bounds for computing explic
 it boolean functions.\n• We prove that every n-qubit state can be constr
 ucted 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 which\, by 
 a counting argument\, is optimal for any finite gate set.\nTo appear in SO
 DA 2024. Paper available at https://arxiv.org/abs/2306.01723.
LOCATION:MR2
END:VEVENT
END:VCALENDAR