Space-bounded quantum state testing via space-efficient quantum singular value transformation
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929352994717696 |
|---|---|
| author | Gall, François Le Liu, Yupan Wang, Qisheng |
| author_facet | Gall, François Le Liu, Yupan Wang, Qisheng |
| contents | 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 state testing perspective:
- The first family of natural complete problems for unitary coRQL, i.e., space-bounded quantum state certification for trace distance and Hilbert-Schmidt distance;
- A new family of natural complete problems for BQL, i.e., space-bounded quantum state testing for trace distance, Hilbert-Schmidt distance, and quantum 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, our results reveal that the space-bounded state testing problems all correspond to the same class. Moreover, our algorithms on the trace distance inspire an algorithmic Holevo-Helstrom measurement, implying QSZK is in QIP(2) with a quantum linear-space honest prover.
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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2308_05079 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Space-bounded quantum state testing via space-efficient quantum singular value transformation Gall, François Le Liu, Yupan Wang, Qisheng Quantum Physics Computational Complexity 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 state testing perspective: - The first family of natural complete problems for unitary coRQL, i.e., space-bounded quantum state certification for trace distance and Hilbert-Schmidt distance; - A new family of natural complete problems for BQL, i.e., space-bounded quantum state testing for trace distance, Hilbert-Schmidt distance, and quantum 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, our results reveal that the space-bounded state testing problems all correspond to the same class. Moreover, our algorithms on the trace distance inspire an algorithmic Holevo-Helstrom measurement, implying QSZK is in QIP(2) with a quantum linear-space honest prover. 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. |
| title | Space-bounded quantum state testing via space-efficient quantum singular value transformation |
| topic | Quantum Physics Computational Complexity |
| url | https://arxiv.org/abs/2308.05079 |