BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Space-Bounded Quantum State Testing via Space-Efficient Quantum Si
 ngular Value Transformation - Yupan Liu (Nagoya University)
DTSTART:20240226T140000Z
DTEND:20240226T150000Z
UID:TALK212248@talks.cam.ac.uk
CONTACT:Tom Gur
DESCRIPTION:Abstract: Driven by exploring the power of quantum computation
  with a limited number of qubits\, we present a novel complete characteriz
 ation for space-bounded quantum computation\, which encompasses settings w
 ith one-sided error (unitary coRQL) and two-sided error (BQL)\, approached
  from a quantum (mixed) state testing perspective: \n- The first family of
  natural complete problems for unitary coRQL\, namely space-bounded quantu
 m state certification for trace distance and Hilbert-Schmidt distance\; \n
 - A new family of (arguably simpler) natural complete problems for BQL\, n
 amely space-bounded quantum state testing for trace distance\, Hilbert-Sch
 midt distance\, and (von Neumann) entropy difference. \n\nIn the space-bou
 nded quantum state testing problem\, we consider two logarithmic-qubit qua
 ntum circuits (devices) denoted as Q_0 and Q_1\, which prepare quantum sta
 tes ρ_0 and ρ_1\, respectively\, with access to their ``source code''. O
 ur goal is to decide whether ρ_0 is ε_1-close to or ε_2-far from ρ_1 w
 ith respect to a specified distance-like measure. Interestingly\, unlike t
 ime-bounded state testing problems\, which exhibit computational hardness 
 depending on the chosen distance-like measure (either QSZK-complete or BQP
 -complete)\, our results reveal that the space-bounded state testing probl
 ems\, considering all three measures\, are computationally as easy as prep
 aring quantum states. \n\nOur results primarily build upon a space-efficie
 nt variant of the quantum singular value transformation (QSVT) introduced 
 by Gilyén\, Su\, Low\, and Wiebe (STOC 2019)\, which is of independent in
 terest. Our technique provides a unified approach for designing space-boun
 ded quantum algorithms. Specifically\, we show that implementing QSVT for 
 any bounded polynomial that approximates a piecewise-smooth function incur
 s only a constant overhead in terms of the space required for (special for
 ms of) the projected unitary encoding. (Joint work with François Le Gall 
 and Qisheng Wang\, https://arxiv.org/abs/2308.05079)
LOCATION:Computer Laboratory\, William Gates Building\, Room SW00
END:VEVENT
END:VCALENDAR