Space-Bounded Quantum State Testing via Space-Efficient Quantum Singular Value Transformation

Add to your list(s) Download to your calendar using vCal

• Yupan Liu (Nagoya University)
• Monday 26 February 2024, 14:00-15:00
• Computer Laboratory, William Gates Building, Room SW00.

If you have a question about this talk, please contact Tom Gur.

Abstract: Driven by exploring the power of quantum computation with a limited number of qubits, we present a novel complete characterization for space-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: - The first family of natural complete problems for unitary coRQL, namely space-bounded quantum state certification for trace distance and Hilbert-Schmidt distance; - 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 difference.

In the space-bounded quantum state testing problem, we consider two logarithmic-qubit quantum circuits (devices) denoted as Q_0 and Q_1, which prepare quantum states ρ_0 and ρ_1, respectively, 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 distance-like measure. Interestingly, unlike time-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 problems, considering all three measures, are computationally as easy as preparing quantum states.

Our results primarily build upon a space-efficient variant of the quantum singular value transformation (QSVT) introduced by Gilyén, Su, Low, and Wiebe (STOC 2019), which is of independent interest. Our technique provides a unified approach for designing space-bounded quantum algorithms. Specifically, we show that implementing QSVT for any bounded polynomial that approximates a piecewise-smooth function incurs only a constant overhead in terms of the space required for (special forms of) the projected unitary encoding. (Joint work with François Le Gall and Qisheng Wang, https://arxiv.org/abs/2308.05079)

This talk is part of the Algorithms and Complexity Seminar series.

This talk is included in these lists:

• Algorithms and Complexity Seminar
• All Talks (aka the CURE list)
• Cambridge talks
• Computer Laboratory, William Gates Building, Room SW00
• Department of Computer Science and Technology talks and seminars
• Interested Talks
• School of Technology
• Trust & Technology Initiative - interesting events
• bld31
• ki287

Note that ex-directory lists are not shown.