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:Algorithms and Complexity Seminar
SUMMARY:Space-Bounded Quantum State Testing via Space-Effi
 cient Quantum Singular Value Transformation - Yupa
 n Liu (Nagoya University)
DTSTART;TZID=Europe/London:20240226T140000
DTEND;TZID=Europe/London:20240226T150000
UID:TALK212248AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/212248
DESCRIPTION:Abstract: Driven by exploring the power of quantum
  computation with a limited number of qubits\, we 
 present a novel complete characterization for spac
 e-bounded quantum computation\, which encompasses 
 settings with one-sided error (unitary coRQL) and 
 two-sided error (BQL)\, approached from a quantum 
 (mixed) state testing perspective: \n- The first f
 amily of natural complete problems for unitary coR
 QL\, namely space-bounded quantum state certificat
 ion for trace distance and Hilbert-Schmidt distanc
 e\; \n- A new family of (arguably simpler) natural
  complete problems for BQL\, namely space-bounded 
 quantum state testing for trace distance\, Hilbert
 -Schmidt distance\, and (von Neumann) entropy diff
 erence. \n\nIn the space-bounded quantum state tes
 ting problem\, we consider two logarithmic-qubit q
 uantum circuits (devices) denoted as Q_0 and Q_1\,
  which prepare quantum states ρ_0 and ρ_1\, respec
 tively\, with access to their ``source code''. Our
  goal is to decide whether ρ_0 is ε_1-close to or 
 ε_2-far from ρ_1 with respect to a specified dista
 nce-like measure. Interestingly\, unlike time-boun
 ded state testing problems\, which exhibit computa
 tional hardness depending on the chosen distance-l
 ike measure (either QSZK-complete or BQP-complete)
 \, our results reveal that the space-bounded state
  testing problems\, considering all three measures
 \, are computationally as easy as preparing quantu
 m states. \n\nOur results primarily build upon a s
 pace-efficient variant of the quantum singular val
 ue transformation (QSVT) introduced by Gilyén\, Su
 \, Low\, and Wiebe (STOC 2019)\, which is of indep
 endent interest. Our technique provides a unified 
 approach for designing space-bounded quantum algor
 ithms. Specifically\, we show that implementing QS
 VT for any bounded polynomial that approximates a 
 piecewise-smooth function incurs only a constant o
 verhead in terms of the space required for (specia
 l forms of) the projected unitary encoding. (Joint
  work with François Le Gall and Qisheng Wang\, htt
 ps://arxiv.org/abs/2308.05079)
LOCATION:Computer Laboratory\, William Gates Building\, Roo
 m SW00
CONTACT:Tom Gur
END:VEVENT
END:VCALENDAR