Papers By Topics | Yupan Liu

Quantum & Quantum-Inspired (Interactive) Proof Systems

Unentangled stoquastic Merlin--Arthur proof systems: the power of unentanglement without destructive interference

Yupan Liu, and Pei Wu

Abstract arXiv

Stoquasticity, originating in physical systems free of the so-called sign problem and avoiding destructive interference from sign cancellations, gives rise to 𝖲𝗍𝗈𝗊𝖬𝖠 introduced by Bravyi, Bessen, and Terhal (2006), a quantum-inspired intermediate class between 𝖬𝖠 and 𝖠𝖬. Unentanglement similarly gives rise to 𝖰𝖬𝖠(𝟤), introduced by Kobayashi, Matsumoto, and Yamakami (CJTCS 2009), which generalizes 𝖰𝖬𝖠 to two unentangled proofs and still has only the trivial 𝖭𝖤𝖷𝖯 upper bound.

In this work, we initiate a systematic study of the power of unentanglement without destructive interference via 𝖲𝗍𝗈𝗊𝖬𝖠(𝟤), the class of unentangled stoquastic Merlin--Arthur proof systems. Although 𝖲𝗍𝗈𝗊𝖬𝖠 is semi-quantum and may collapse to 𝖬𝖠, 𝖲𝗍𝗈𝗊𝖬𝖠(𝟤) turns out to be surprisingly powerful. We establish the following results:
- 𝖭𝖯 $\subseteq$ 𝖲𝗍𝗈𝗊𝖬𝖠(𝟤) with $\widetilde{O}(\sqrt{n})$-qubit proofs and completeness error $2^{-{\rm polylog}(n)}$, paralleling the best known 𝖰𝖬𝖠(𝟤) lower bounds except for perfect completeness. On the upper-bound side, 𝖲𝗍𝗈𝗊𝖬𝖠(𝟤) $\subseteq$ 𝖤𝖷𝖯 via the Sum-of-Squares algorithm due to Barak, Kelner, and Steurer (STOC 2014). Our tightened SoS upper bound shows the essential optimality of the parameters in both our protocol and the BKS algorithm under the exponential-time hypothesis (ETH).
- 𝖲𝗍𝗈𝗊𝖬𝖠(𝟤)_𝟣 $\subseteq$ 𝖯𝖲𝖯𝖠𝖢𝖤, and the containment holds with completeness error $2^{-2^{{\rm poly}(n)}}$.
- 𝖯𝗋𝖾𝖼𝗂𝗌𝖾𝖲𝗍𝗈𝗊𝖬𝖠(𝟤), a variant of 𝖲𝗍𝗈𝗊𝖬𝖠(𝟤) with exponentially small promise gap, cannot achieve perfect completeness unless 𝖤𝖷𝖯=𝖭𝖤𝖷𝖯. In contrast, 𝖯𝗋𝖾𝖼𝗂𝗌𝖾𝖲𝗍𝗈𝗊𝖬𝖠 achieves perfect completeness, since 𝖯𝖲𝖯𝖠𝖢𝖤 $\subseteq$ 𝖯𝗋𝖾𝖼𝗂𝗌𝖾𝖲𝗍𝗈𝗊𝖬𝖠_𝟣.
- When the completeness error is negligible, 𝖲𝗍𝗈𝗊𝖬𝖠($k$)=𝖲𝗍𝗈𝗊𝖬𝖠(𝟤) for $k\geq 2$.

Our lower bounds are obtained by stoquastizing the short-proof 𝖰𝖬𝖠(𝟤) protocols via distribution testing techniques. Our upper bounds for the nearly perfect completeness case are proved via our rectangular closure testing framework, a new combinatorial technique tailored to 𝖲𝗍𝗈𝗊𝖬𝖠(𝟤)_𝟣.
A slightly improved upper bound for quantum statistical zero-knowledge

François Le Gall, Yupan Liu, and Qisheng Wang

Abstract arXiv

The complexity class Quantum Statistical Zero-Knowledge (𝖰𝖲𝖹𝖪), introduced by Watrous (FOCS 2002) and later refined in Watrous (SICOMP, 2009), has the best known upper bound 𝖰𝖨𝖯(𝟤)$\cap$𝖼𝗈-𝖰𝖨𝖯(𝟤), which follows from the inclusion 𝖰𝖨𝖯(𝟤)$\subseteq$𝖯𝖲𝖯𝖠𝖢𝖤 by Jain, Upadhyay, and Watrous (FOCS 2009). Here, 𝖰𝖨𝖯(𝟤) denotes the class of promise problems that admit two-message quantum interactive proof systems in which the honest prover is typically computationally unbounded, and 𝖼𝗈-𝖰𝖨𝖯(𝟤) denotes the complement of 𝖰𝖨𝖯(𝟤).

We slightly improve this upper bound to 𝖰𝖨𝖯(𝟤)$\cap$𝖼𝗈-𝖰𝖨𝖯(𝟤) with a quantum linear-space honest prover. A similar improvement also applies to the upper bound for the non-interactive variant 𝖭𝖨𝖰𝖲𝖹𝖪. Our main techniques are an algorithmic version of the Holevo--Helstrom measurement and the Uhlmann transform, both implementable in quantum linear space, implying polynomial-time complexity in the state dimension, using the recent space-efficient quantum singular value transformation of Le Gall, Liu, and Wang (CC, to appear).
Space-bounded quantum interactive proof systems

François Le Gall, Yupan Liu, Harumichi Nishimura, and Qisheng Wang

CCC 2025 & QIP 2025

Abstract DOI arXiv Video Slides

We introduce two models of space-bounded quantum interactive proof systems, 𝖰𝖨𝖯𝖫 and 𝖰𝖨𝖯_𝖴𝖫. The 𝖰𝖨𝖯_𝖴𝖫 model, a space-bounded variant of quantum interactive proofs 𝖰𝖨𝖯 introduced by Watrous (CC 2003) and Kitaev and Watrous (STOC 2000), restricts verifier actions to unitary circuits. In contrast, 𝖰𝖨𝖯𝖫 allows logarithmically many pinching intermediate measurements per verifier action, making it the weakest model that encompasses the classical model of Condon and Ladner (JCSS 1995).

We characterize the computational power of 𝖰𝖨𝖯𝖫 and 𝖰𝖨𝖯_𝖴𝖫. When the message number $m$ is polynomially bounded, 𝖰𝖨𝖯_𝖴𝖫⊊𝖰𝖨𝖯𝖫 unless 𝖯=𝖭𝖯:
- 𝖰𝖨𝖯𝖫^𝙷𝙲, a subclass of 𝖰𝖨𝖯𝖫 defined by a high-concentration condition on yes instances, exactly characterizes 𝖭𝖯.
- 𝖰𝖨𝖯_𝖴𝖫 is contained in 𝖯 and contains 𝖲𝖠𝖢^𝟣∪𝖡𝖰𝖫, where 𝖲𝖠𝖢^𝟣 denotes problems solvable by classical logarithmic-depth, semi-unbounded fan-in circuits.
However, this distinction vanishes when $m$ is constant. Our results further indicate that (pinching) intermediate measurements uniquely impact space-bounded quantum interactive proofs, unlike in space-bounded quantum computation, where 𝖡𝖰𝖫=𝖡𝖰_𝖴𝖫.

We also introduce space-bounded unitary quantum statistical zero-knowledge (𝖰𝖲𝖹𝖪_𝖴𝖫), a specific form of 𝖰𝖨𝖯_𝖴𝖫 proof systems with statistical zero-knowledge against any verifier. This class is a space-bounded variant of quantum statistical zero-knowledge (𝖰𝖲𝖹𝖪) defined by Watrous (SICOMP 2009). We prove that 𝖰𝖲𝖹𝖪_𝖴𝖫=𝖡𝖰𝖫, implying that the statistical zero-knowledge property negates the computational advantage typically gained from the interaction.
Quantum Merlin-Arthur proof systems for synthesizing quantum states

Hugo Delavenne, François Le Gall, Yupan Liu, and Masayuki Miyamoto

Quantum (2025)

Abstract DOI arXiv Slides

Complexity theory typically focuses on the difficulty of solving computational problems using classical inputs and outputs, even with a quantum computer. In the quantum world, it is natural to apply a different notion of complexity, namely the complexity of synthesizing quantum states. We investigate a state-synthesizing counterpart of the class 𝖭𝖯, referred to as 𝗌𝗍𝖺𝗍𝖾𝖰𝖬𝖠, which is concerned with preparing certain quantum states through a polynomial-time quantum verifier with the aid of a single quantum message from an all-powerful but untrusted prover. This is a subclass of the class 𝗌𝗍𝖺𝗍𝖾𝖰𝖨𝖯 recently introduced by Rosenthal and Yuen (ITCS 2022), which permits polynomially many interactions between the prover and the verifier. Our main result consists of error reduction of this class and its variants with an exponentially small gap or a bounded space, as well as how this class relates to other fundamental state synthesizing classes, i.e., states generated by uniform polynomial-time quantum circuits (𝗌𝗍𝖺𝗍𝖾𝖡𝖰𝖯) and space-uniform polynomial-space quantum circuits (𝗌𝗍𝖺𝗍𝖾𝖯𝖲𝖯𝖠𝖢𝖤). Furthermore, we establish that the family of 𝖴𝖰𝖬𝖠 witnesses, considered as one of the most natural candidates, is in 𝗌𝗍𝖺𝗍𝖾𝖰𝖬𝖠. Additionally, we demonstrate that 𝗌𝗍𝖺𝗍𝖾𝖰𝖢𝖬𝖠 achieves perfect completeness.
${\sf StoqMA}$ meets distribution testing

Yupan Liu

TQC 2021 (Proceedings)

Abstract DOI arXiv Video Slides

Cubitt and Montanaro (SICOMP, 2016) formulated a quantum version of Schaefer's dichotomy theorem for the local Hamiltonian problem. This quartation theorem categorizes the problem into one of four levels: 𝖯, 𝖭𝖯-complete, 𝖲𝗍𝗈𝗊𝖬𝖠-complete, or QMA-complete. The hierarchy is notable for its inclusion of a mystery class 𝖲𝗍𝗈𝗊𝖬𝖠, introduced by Bravyi, Bessen, and Terhal (2006). In this paper, we establish a link between 𝖲𝗍𝗈𝗊𝖬𝖠 and distribution testing through reversible circuits. Our first result demonstrates that the advantage of 𝖲𝗍𝗈𝗊𝖬𝖠 is due to the optimal non-negative witness. If the optimal witness is restricted to be easy witness, meaning that any quotient on the distribution's coordinates associated with the witness is efficiently computable, then the class eStoqMA is contained in MA. Remarkably, e𝖲𝗍𝗈𝗊𝖬𝖠 includes 𝖲𝗍𝗈𝗊𝖬𝖠 with perfect completeness (𝖲𝗍𝗈𝗊𝖬𝖠$_1$), providing an arguably simplified proof for 𝖲𝗍𝗈𝗊𝖬𝖠$_1$⊆𝖬𝖠 as shown in Bravyi, Bessen, and Terhal (2006), as well as Bravyi and Terhal (SICOMP, 2010). Our second result is error reduction for 𝖲𝗍𝗈𝗊𝖬𝖠 regarding soundness error, by proving that distinguishing reversible circuits with ancillary random bits is 𝖲𝗍𝗈𝗊𝖬𝖠-complete, whereas distinguishing quantum circuits is 𝖰𝖬𝖠-complete. Our results make progress towards collapsing the hierarchy 𝖬𝖠⊆𝖲𝗍𝗈𝗊𝖬𝖠⊆𝖲𝖡𝖯 in which all classes are contained in 𝖠𝖬 and collapse to 𝖭𝖯 under derandomization assumptions.
$\mathsf{StoqMA}$ vs. $\mathsf{MA}$: the power of error reduction

Dorit Aharonov, Alex B. Grilo, and Yupan Liu

Quantum (2025)

Abstract DOI arXiv

𝖲𝗍𝗈𝗊𝖬𝖠 characterizes the computational hardness of stoquastic local Hamiltonians, which is a family of Hamiltonians that does not suffer from the sign problem. Although error reduction is commonplace for many complexity classes, such as 𝖡𝖯𝖯, 𝖡𝖰𝖯, 𝖬𝖠, 𝖰𝖬𝖠, etc., this property remains open for 𝖲𝗍𝗈𝗊𝖬𝖠 since Bravyi, Bessen and Terhal defined this class in 2006. In this note, we show that error reduction for 𝖲𝗍𝗈𝗊𝖬𝖠 will imply that 𝖲𝗍𝗈𝗊𝖬𝖠=𝖬𝖠.
Towards a quantum-inspired proof for ${\sf IP} = {\sf PSPACE}$

Ayal Green, Guy Kindler, and Yupan Liu

Quantum Information & Computation (2021)

Abstract DOI arXiv

We explore quantum-inspired interactive proof systems where the prover is limited. Namely, we improve on a result by [AG17] showing a quantum-inspired interactive protocol (𝖨𝖯) for 𝖯𝗋𝖾𝖼𝗂𝗌𝖾𝖡𝖰𝖯 where the prover is only assumed to be a 𝖯𝗋𝖾𝖼𝗂𝗌𝖾𝖡𝖰𝖯 machine, and show that the result can be strengthened to show an 𝖨𝖯 for 𝖭𝖯$^{\sf P}$$^{\sf P}$ with a prover which is only assumed to be an 𝖭𝖯$^{\sf P}$$^{\sf P}$ machine - which was not known before. We also show how the protocol can be used to directly verify 𝖰𝖬𝖠 computations, thus connecting the sum-check protocol by [AAV13] with the result of [AG17, LFKN90]. Our results shed light on a quantum-inspired proof for 𝖨𝖯=𝖯𝖲𝖯𝖠𝖢𝖤, as 𝖯𝗋𝖾𝖼𝗂𝗌𝖾𝖰𝖬𝖠 captures the full 𝖯𝖲𝖯𝖠𝖢𝖤 power.

Quantum Property Testing: Complexity Classes & Algorithms

Trace estimation of quantum state powers: Sample complexity and computational hardness

Kean Chen, Yupan Liu, and Qisheng Wang

Abstract arXiv

As often emerges in various basic quantum properties such as Rényi and Tsallis entropies, the trace of quantum state powers $\mathrm{Tr}(\rho^q)$ has attracted a lot of attention. The recent work of Liu and Wang (SODA 2025) showed that, even for (possibly) non-integer $q>1$, $\mathrm{Tr}(\rho^q)$ can be estimated to within additive error $\varepsilon$ using a dimension-independent (and also rank-independent) sample complexity of $\widetilde O(1/\varepsilon^{3+\frac{2}{q-1}})$, together with a lower bound of $\Omega(1/\varepsilon)$. In addition, combining this result with subsequent work of Liu (STACS 2026) shows that the corresponding promise problem is 𝖡𝖰𝖯-complete. In this paper, we significantly improve and extend the sample complexity bounds for this problem. Furthermore, we show that for $0<q<1$, the problem does not admit an efficient estimator unless 𝖡𝖰𝖯=𝖭𝖨𝖰𝖲𝖹𝖪, which is considered highly unlikely. In particular, we have the following results:
- For $q > 2$, we settle the sample complexity with matching upper and lower bounds $\widetilde \Theta(1/\varepsilon^2)$.
- For $1 < q < 2$, we obtain an upper bound of $\widetilde O(1/\varepsilon^{\frac{2}{q-1}})$, with a lower bound of $\Omega(1/\varepsilon^{\max\{\frac{1}{q-1}, 2\}})$ for dimension-independent (in fact, rank-independent) estimators.
- For $0< q < 1$, we obtain an upper bound of $O((d/\varepsilon)^{\frac{2}{q}})$, with a lower bound of $\Omega((d/\varepsilon)^{\frac{1}{q}})$ for $d$-dimensional states (in fact, both bounds can be naturally refined to depend on the rank rather than the dimension). Accordingly, the corresponding promise problem is 𝖭𝖨𝖰𝖲𝖹𝖪-hard, which is in sharp contrast to the case of $q > 1$.

Technically, our upper bounds are obtained by (non-plug-in) quantum estimators based on weak Schur sampling, in sharp contrast to the prior approach based on quantum singular value transformation and samplizer.
Computational hardness of estimating quantum entropies via binary entropy bounds

Yupan Liu

STACS 2026

Abstract DOI arXiv Slides

We investigate the computational hardness of estimating the quantum $\alpha$-Rényi entropy $\mathrm{S}^\mathtt{R}_{\alpha}(\rho) = \frac{\ln \mathrm{Tr}(\rho^\alpha)}{1-\alpha}$ and the quantum $q$-Tsallis entropy $\mathrm{S}^\mathtt{T}_q(\rho) = \frac{1-\mathrm{Tr}(\rho^q)}{q-1}$, both of which converge to the von Neumann entropy as the order approaches $1$. The promise problems Quantum $\alpha$-Rényi Entropy Approximation (RényiQEA$_\alpha$) and Quantum $q$-Tsallis Entropy Approximation (TsallisQEA$_q$) ask whether $\mathrm{S}^\mathtt{R}_{\alpha}(\rho)$ or $\mathrm{S}^\mathtt{T}_q(\rho)$, respectively, is at least $\tau_\mathtt{Y}$ or at most $\tau_\mathtt{N}$, where $\tau_\mathtt{Y} - \tau_\mathtt{N}$ is typically a positive constant. Previous hardness results cover only the von Neumann entropy (order $1$) and some cases of the quantum $q$-Tsallis entropy, while existing approaches do not readily extend to other orders.

We establish that for all positive real $\alpha$ and $q$, and also for $\alpha=\infty$, the rank-$2$ variants Rank2RényiQEA$_\alpha$ and Rank2TsallisQEA$_q$ are 𝖡𝖰𝖯-hard. Combined with prior (rank-dependent) quantum query algorithms in Wang, Guan, Liu, Zhang, and Ying (TIT 2024), Wang, Zhang, and Li (TIT 2024), and Liu and Wang (SODA 2025), as well as one derived from O'Donnell and Wright (STOC 2016), our results imply:
- For all real orders $\alpha > 0$ or $\alpha=\infty$, and for all real orders $0 < q \leq 1$, LowRankRényiQEA$_\alpha$ and LowRankTsallisQEA$_q$ are 𝖡𝖰𝖯-complete, where both are restricted versions of RényiQEA$_\alpha$ and TsallisQEA$_q$ with $\rho$ of polynomial rank.
- For all real order $q>1$, TsallisQEA$_q$ is 𝖡𝖰𝖯-complete.

Our hardness results stem from reductions based on new inequalities relating the $\alpha$-Rényi or $q$-Tsallis binary entropies at different orders, where the reductions differ substantially from previous approaches, and the inequalities are also of independent interest.
On estimating the quantum $\ell_{\alpha}$ distance

Yupan Liu, and Qisheng Wang

ESA 2025 & AQIS 2025 (long talk)

Abstract DOI arXiv Slides

We study the computational complexity of estimating the quantum $\ell_{\alpha}$ distance ${\mathrm{T}_\alpha}(\rho_0,\rho_1)$, defined via the Schatten $\alpha$-norm $\|A\|_{\alpha} = \mathrm{Tr}(|A|^{\alpha})^{1/\alpha}$, given $\mathrm{poly}(n)$-size state-preparation circuits of $n$-qubit quantum states $\rho_0$ and $\rho_1$. This quantity serves as a lower bound on the trace distance for $\alpha > 1$. For any constant $\alpha > 1$, we develop an efficient rank-independent quantum estimator for ${\mathrm{T}_\alpha}(\rho_0,\rho_1)$ with time complexity $\mathrm{poly}(n)$, achieving an exponential speedup over the prior best results of $\exp(n)$ due to Wang, Guan, Liu, Zhang, and Ying (TIT 2024). Our improvement leverages efficiently computable uniform polynomial approximations of signed positive power functions within quantum singular value transformation, thereby eliminating the dependence on the rank of the quantum states.

Our quantum algorithm reveals a dichotomy in the computational complexity of the 𝚀𝚞𝚊𝚗𝚝𝚞𝚖 𝚂𝚝𝚊𝚝𝚎 𝙳𝚒𝚜𝚝𝚒𝚗𝚐𝚞𝚒𝚜𝚑𝚊𝚋𝚒𝚕𝚒𝚝𝚢 𝙿𝚛𝚘𝚋𝚕𝚎𝚖 𝚠𝚒𝚝𝚑 𝚂𝚌𝚑𝚊𝚝𝚝𝚎𝚗 $\alpha$-𝚗𝚘𝚛𝚖 (𝚀𝚂𝙳$_{\alpha}$, which involves deciding whether ${\mathrm{T}_\alpha}(\rho_0,\rho_1)$ is at least $2/5$ or at most $1/5$. This dichotomy arises between the cases of constant $\alpha > 1$ and $\alpha=1$:
- For any $1+\Omega(1) \leq \alpha \leq O(1)$, 𝚀𝚂𝙳$_{\alpha}$ is 𝖡𝖰𝖯-complete.
- For any $1 \leq \alpha \leq 1+\frac{1}{n}$, 𝚀𝚂𝙳$_{\alpha}$ is 𝖰𝖲𝖹𝖪-complete, implying that no efficient quantum estimator for $\mathrm{T}_\alpha(\rho_0,\rho_1)$ exists unless 𝖡𝖰𝖯=𝖰𝖲𝖹𝖪.

The hardness results follow from reductions based on new rank-dependent inequalities for the quantum $\ell_{\alpha}$ distance with $1\leq \alpha \leq \infty$, which are of independent interest.
On estimating the trace of quantum state powers

Yupan Liu, and Qisheng Wang

IEEE Transactions on Information Theory (Early Access) ; SODA 2025 & QIP 2025

Abstract DOI arXiv Slides

We investigate the computational complexity of estimating the trace of quantum state powers $\mathrm{Tr}(\rho^q)$ for an $n$-qubit mixed quantum state $\rho$, given its state-preparation circuit of size $\mathrm{poly}(n)$. This quantity is closely related to and often interchangeable with the Tsallis entropy $\mathrm{S}_q(\rho) = \frac{1 - \mathrm{Tr}(\rho^q)}{q-1}$, where $q = 1$ corresponds to the von Neumann entropy. For any non-integer $q \geq 1 + \Omega(1)$, we provide a quantum estimator for $\mathrm{S}_q(\rho)$ with time complexity $\mathrm{poly}(n)$, exponentially improving the prior best results of $\exp(n)$ due to Acharya, Issa, Shende, and Wagner (ISIT 2019), Wang, Guan, Liu, Zhang, and Ying (TIT 2024), Wang, Zhang, and Li (TIT 2024), and Wang and Zhang (ESA 2024). Our speedup is achieved by introducing efficiently computable uniform approximations of positive power functions into quantum singular value transformation.

Our quantum algorithm reveals a sharp phase transition between the case of $q=1$ and constant $q>1$ in the computational complexity of the 𝚀𝚞𝚊𝚗𝚝𝚞𝚖 $q$-𝚃𝚜𝚊𝚕𝚕𝚒𝚜 𝙴𝚗𝚝𝚛𝚘𝚙𝚢 𝙳𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚌𝚎 𝙿𝚛𝚘𝚋𝚕𝚎𝚖 (𝚃𝚜𝚊𝚕𝚕𝚒𝚜𝚀𝙴𝙳$_q$), particularly deciding whether the difference $\mathrm{S}_q(\rho_0) - \mathrm{S}_q(\rho_1)$ is at least $0.001$ or at most $-0.001$:
- For any $1+\Omega(1) \leq q \leq 2$, 𝚃𝚜𝚊𝚕𝚕𝚒𝚜𝚀𝙴𝙳$_q$ is 𝖡𝖰𝖯-complete, which implies that 𝙿𝚞𝚛𝚒𝚝𝚢 𝙴𝚜𝚝𝚒𝚖𝚊𝚝𝚒𝚘𝚗 is also 𝖡𝖰𝖯-complete.
- For any $1 \leq q \leq 1 + \frac{1}{n-1}$, 𝚃𝚜𝚊𝚕𝚕𝚒𝚜𝚀𝙴𝙳$_q$ is 𝖰𝖲𝖹𝖪-hard, leading to hardness of approximating von Neumann entropy because ${\rm S}_q(\rho) \leq {\rm S}(\rho)$, as long as 𝖡𝖰𝖯⊊𝖰𝖲𝖹𝖪.

The hardness results are derived from reductions based on new inequalities for the quantum $q$-Jensen-(Shannon-)Tsallis divergence with $1\leq q \leq 2$, which are of independent interest.
Quantum state testing beyond the polarizing regime and quantum triangular discrimination

Yupan Liu

computational complexity (2025)

Abstract DOI arXiv Slides

The complexity class Quantum Statistical Zero-Knowledge (𝖰𝖲𝖹𝖪) captures computational difficulties of the time-bounded quantum state testing problem with respect to the trace distance, known as the Quantum State Distinguishability Problem (𝚀𝚂𝙳𝙿) introduced by Watrous (FOCS 2002). However, 𝚀𝚂𝙳𝙿 is in 𝖰𝖲𝖹𝖪 merely within the polarizing regime, similar to its classical counterpart shown by Sahai and Vadhan (JACM, 2003) due to the polarization lemma (error reduction for 𝚂𝙳𝙿).

Recently, Berman, Degwekar, Rothblum, and Vasudevan (TCC 2019) extended the 𝖲𝖹𝖪 containment for 𝚂𝙳𝙿 beyond the polarizing regime via the time-bounded distribution testing problems with respect to the triangular discrimination and the Jensen-Shannon divergence. This paper introduces proper quantum analogs for these problems by defining quantum counterparts for triangular discrimination. We investigate whether the quantum analogs behave similarly to their classical counterparts and examine the limitations of existing approaches to polarization regarding quantum distances. These new 𝖰𝖲𝖹𝖪-complete problems improve 𝖰𝖲𝖹𝖪 containments for 𝚀𝚂𝙳𝙿 beyond the polarizing regime and establish a simple 𝖰𝖲𝖹𝖪-hardness for the quantum entropy difference problem (𝚀𝙴𝙳𝙿) defined by Ben-Aroya, Schwartz, and Ta-Shma (ToC 2010). Furthermore, we prove that 𝚀𝚂𝙳𝙿 with some exponentially small errors is in 𝖯𝖯, while the same problem without error is in 𝖭𝖰𝖯.

Space-Bounded Quantum Computation

Space-bounded quantum state testing via space-efficient quantum singular value transformation

François Le Gall, Yupan Liu, and Qisheng Wang

To appear in computational complexity

Abstract arXiv Slides

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 𝖼𝗈𝖱𝖰𝖫) and two-sided error (𝖡𝖰𝖫), approached from a quantum state testing perspective:
- The first family of natural complete problems for unitary 𝖼𝗈𝖱𝖰𝖫, namely space-bounded quantum state certification for trace distance and Hilbert-Schmidt distance;
- A new family of (arguably simpler) natural complete problems for 𝖡𝖰𝖫, namely 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 $\rho_0$ and $\rho_1$, respectively, with access to their ``source code''. Our goal is to decide whether $\rho_0$ is $\epsilon_1$-close to or $\epsilon_2$-far from $\rho_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 𝖰𝖲𝖹𝖪-complete or 𝖡𝖰𝖯-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.