TL;DR
This paper introduces the first natural complete problems for one-sided error quantum logspace ($\mathsf{coRQ_UL}$) and a new family of complete problems for two-sided quantum logspace ($\mathsf{BQL}$) based on quantum state testing. It demonstrates that testing properties (trace distance, Hilbert-Schmidt distance, and entropy difference) of states generated by logspace quantum circuits is computationally as easy as preparing them. Crucially, the authors achieve this by developing a space-efficient framework for Quantum Singular Value Transformation (QSVT) using averaged Chebyshev polynomial approximations.
What Problem Does This Paper Address?
Understanding the limits of space-bounded quantum computation—what can be computed using only logarithmic quantum memory ($\sim O(\log n)$ qubits)—is a fundamental question in quantum complexity theory. While polynomial-time quantum classes ($\mathsf{BQP}$, $\mathsf{QMA}$) are well-characterized by natural problems, complete problems for quantum logspace ($\mathsf{BQL}$) have historically been confined to synthetic, well-conditioned linear algebra tasks (such as matrix inversion and determinants). Furthermore, the one-sided error class $\mathsf{coRQ_UL}$ had no known natural complete problems.
In time-bounded computation, quantum state testing shows an intriguing split: distinguishing states in the $\ell_2$ (Hilbert-Schmidt) metric is in $\mathsf{BQP}$, whereas distinguishing them in the $\ell_1$ (trace) distance or estimating entropy differences is $\mathsf{QSZK}$-complete (believed to be strictly harder than $\mathsf{BQP}$). The authors set out to determine whether this computational gap persists under memory-constrained (space-bounded) settings.
Methods
The paper’s core technical innovation is a space-efficient Quantum Singular Value Transformation (QSVT):
- Averaged Chebyshev Truncation: Standard QSVT pre-processing requires finding rotation phase angles via polynomial root finding, which lacks space-efficient algorithms. Instead, the authors use de La Vallée Poussin partial sums (averaged Chebyshev truncations) to approximate piecewise-smooth functions. This achieves uniform approximation error independent of the degree $d$ (improving on previous $O(\log d)$ error bounds).
- Space-Efficient Coefficient Generation:
- For continuously bounded functions (e.g., the sign function $\operatorname{sgn}(x)$), Chebyshev coefficients are computed deterministically in $O(\log d)$ space via the composite trapezium rule.
- For piecewise-smooth functions (e.g., $\ln(1/x)$), coefficients are computed in bounded-error randomized logspace using sub-stochastic matrix powering mapped to random walks on directed graphs.
- Algorithmic Holevo-Helstrom Measurement: By applying space-efficient QSVT to block-encodings of $(\rho_0 - \rho_1)/2$ using a polynomial approximation of $\operatorname{sgn}(x)$, the authors explicitly implement the optimal Holevo-Helstrom state discrimination measurement.
- Exact Amplitude Amplification: For one-sided error certification ($\mathsf{coRQ_UL}$), the parity preservation of odd QSVT polynomials ensures an exact zero-shift for identical states, allowing exact amplitude amplification to achieve perfect completeness.
Datasets
Not discussed in the paper (this is a theoretical paper in computational complexity and quantum algorithms; no empirical datasets or benchmarks were used).
Key Insights and Ideas
- Metric Collapse in Bounded Space: In polynomial time, trace distance and entropy testing are much harder than state preparation. In quantum logspace, this hardness gap disappears: testing states under trace distance, Hilbert-Schmidt distance, and von Neumann entropy difference are all equivalent in complexity to quantum state preparation itself ($\mathsf{BQL}$-complete).
- Bypassing the Angle-Finding Bottleneck: Standard Quantum Signal Processing (QSP) angles cannot easily be found in logspace. Translating Chebyshev approximations into Linear Combinations of Unitaries (LCU) followed by robust oblivious amplitude amplification enables singular value transformation within linear space overhead.
- First Natural $\mathsf{coRQ_UL}$-Complete Problems: Certifying whether two logspace-generated states are identical or far in trace/Hilbert-Schmidt distance characterizes one-sided error quantum logspace, resolving a longstanding gap in quantum structural complexity.
Key Results
- $\mathsf{coRQ_UL}$-Completeness: Quantum state certification problems $\mathrm{\overline{CertQSD}}_{\log}$ (trace distance) and $\mathrm{\overline{CertQHS}}_{\log}$ (Hilbert-Schmidt distance) are $\mathsf{coRQ_UL}$-complete for any gap $\alpha(n) \ge 1/\operatorname{poly}(n)$.
- $\mathsf{BQL}$-Completeness: Promise problems for trace distance ($\mathrm{GapQSD}_{\log}$), quantum entropy difference ($\mathrm{GapQED}_{\log}$), quantum Jensen-Shannon divergence ($\mathrm{GapQJS}_{\log}$), and Hilbert-Schmidt distance ($\mathrm{GapQHS}_{\log}$) are all $\mathsf{BQL}$-complete.
- Algorithmic Holevo-Helstrom Bound: For $n$-qubit polynomial-size circuits, an approximate Holevo-Helstrom measurement with additive error $2^{-n}$ can be implemented in quantum single-exponential time $2^{O(n)}$ and linear space $O(n)$.
- Improved $\mathsf{QSZK}$ Upper Bound: As an immediate corollary, $\mathrm{GapQSD}$ (and thus any problem in $\mathsf{QSZK}$) is in $\mathsf{QIP}(2)$ with an honest prover that operates in single-exponential time and linear quantum space.
Limitations and Future Work
- Quadratic Query Overhead: Space-efficient QSVT requires $O(d^2)$ queries to the underlying unitary encoding $U$, unlike time-efficient QSVT which achieves optimal $O(d)$. Finding a space-efficient algorithm with $O(d)$ query complexity remains open.
- Ancilla Accumulation: Iterating space-efficient QSVT super-constantly many times linearly accumulates ancillary qubits, making it tricky to directly apply to iterated algorithms (such as positive semidefinite programming solvers) without exceeding logspace bounds.
- General Angle-Finding in Small Space: Developing a general, space-efficient algorithm for finding QSP phase angles directly remains an unsolved open problem.
Summary updated