Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2303.01952 · Computational Complexity

Quantum state testing beyond the polarizing regime and quantum triangular discrimination

Yupan Liu

Published Sep 17, 2025• 11 citations
arXivHTMLPDF

Abstract

Abstract The complexity class Quantum Statistical Zero-Knowledge captures computational difficulties of the time-bounded quantum state testing problem with respect to the trace distance, deciding whether $$\textrm{T}(\rho_0,\rho_1)$$ T ( ρ 0 , ρ 1 ) is at least $$\alpha$$ α or at most $$\beta$$ β , known as the Quantum State Distinguishability Problem (QSDP) introduced by Watrous (FOCS 2002). However, $$\textrm{QSDP}[\alpha,\beta]$$ QSDP [ α , β ] is in only within the constant polarizing regime, where $$\alpha \, \textrm{and} \, \beta$$ α and β are constants satisfying $$\alpha^2 > \beta$$ α 2 > β (rather than $$\alpha > \beta$$ α > β ), similar to its classical counterpart shown by Sahai and Vadhan (JACM 2003) due to the polarization lemma (error reduction for SDP). Recently, Berman, Degwekar, Rothblum, and Vasudevan (TCC 2019) extended the containment of SDP beyond the polarizing regime via the time-bounded distribution testing problems with respect to the triangular discrimination and the Jensen-Shannon divergence. Our work 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 of QSDP beyond the polarizing regime and establish a simple -hardness for the quantum entropy difference problem (QEDP) defined by Ben-Aroya, Schwartz, and Ta-Shma (ToC 2010). Furthermore, we prove that QSDP with some exponentially small errors is in , while the same problem without error is in .

DOI
10.1007/s00037-025-00273-8

Related papers

Complexity-theoretic perspectives on quantum state testing

Yupan LIU

Recent advancements in quantum devices have posed an intriguing challenge of verifying their intended functionality.These devices, typically time-bounded, are often designed to prepare specific 𝑛-qubit states, denoted as 𝜌 ! and 𝜌 " .The problem of (tolerant) quantum state testing aims to design algorithms that can efficiently decide whether 𝜌 ! is either 𝜀 " -close to or 𝜀 # -far from 𝜌 " with respect to a chosen distance-like measure.This problem generalizes classical distribution testing to the quantum domain and forms a part of quantum property testing, an emerging field dedicated to developing efficient quantum testers for properties of quantum objects.The computational complexity of time-bounded state testing varies significantly with the choice of closeness measure, exhibiting a dichotomy-like behavior:• For both the trace distance (ℓ " norm) and the quantum (von Neumann) entropy difference, the problems correspond to the complexity class QSZK, as shown in Watrous (FOCS 2002), Watrous (SICOMP 2009), and Ben-Aroya, Schwartz, and Ta-Shma (CCC 2008), which is widely believed to be strictly more powerful than BQP.

•Mar 25, 2025•0 citations

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

François Le Gall, Yupan Liu, Qisheng Wang

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 ) and two-sided error ( ), approached from a quantum (mixed) state testing perspective: The first family of natural complete problems for unitary $$\text {\textsf {coRQL}} $$ coRQL , 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 (von Neumann) entropy difference. In the space-bounded quantum state testing problem, we consider two logarithmic-qubit quantum circuits (devices) denoted as $$Q_0$$ Q 0 and $$Q_1$$ Q 1 , which prepare quantum states $$\rho _0$$ ρ 0 and $$\rho _1$$ ρ 1 , respectively, with access to their “source code”. Our goal is to decide whether $$\rho _0$$ ρ 0 is $$\epsilon _1$$ ϵ 1 -close to or $$\epsilon _2$$ ϵ 2 -far from $$\rho _1$$ ρ 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.

arXiv:2308.05079•Computational Complexity•Nov 10, 2026•23 citations

A slightly improved upper bound for quantum statistical zero-knowledge

François Le Gall, Yupan Liu, Qisheng Wang

The complexity class Quantum Statistical Zero-Knowledge ($\mathsf{QSZK}$), introduced by Watrous (FOCS 2002) and later refined in Watrous (SICOMP, 2009), has the best known upper bound $\mathsf{QIP(2)} \cap \text{co-}\mathsf{QIP(2)}$, which was simplified following the inclusion $\mathsf{QIP(2)} \subseteq \mathsf{PSPACE}$ established in Jain, Upadhyay, and Watrous (FOCS 2009). Here, $\mathsf{QIP(2)}$ denotes the class of promise problems that admit two-message quantum interactive proof systems in which the honest prover is typically computationally unbounded, and $\text{co-}\mathsf{QIP(2)}$ denotes the complement of $\mathsf{QIP(2)}$. We slightly improve this upper bound to $\mathsf{QIP(2)} \cap \text{co-}\mathsf{QIP(2)}$ with a quantum linear-space honest prover. Specifically, the honest prover uses space linear in the size of the transcript of the original $\mathsf{QSZK}$ proof system. A similar improvement also applies to the upper bound for the non-interactive variant $\mathsf{NIQSZK}$. Our main techniques are algorithmic versions 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).

quant-pharXiv:2512.11597•Leibniz international proceedings in informatics•Dec 15, 2025•3 citations

On Estimating the Trace of Quantum State Powers

Yupan Liu, Qisheng Wang

We investigate the computational complexity of estimating the trace of quantum state powers tr(ρq) for annqubit mixed quantum state ρ, given its state-preparation circuit of size poly(n). This quantity is closely related to and often interchangeable with the Tsallis entropy Sq(ρ) = 1—tr(ρq)/q—1, whereq= 1 corresponds to the von Neumann entropy. For any non-integerq≥ 1 + Ω(1), we provide a quantum estimator for Sq(ρ) with time complexity 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 (TIT 2025). Our speedup is achieved by introducing efficiently computableuniform approximationsof positive power functions into quantum singular value transformation. Our quantum algorithm reveals a sharp phase transition between the case ofq= 1 and constantq> 1 in the computational complexity of the Quantumq-Tsallis Entropy Difference Problem (TsallisQEDq), particularly deciding whether the difference Sq(ρ0)−Sq(ρ1) is at least 0.001 or at most −0.001: • For any 1 + Ω (1) ≤q≤ 2, TsallisQEDqis BQP-complete, which implies that Purity Estimation is also BQP-complete. • For any 1≤q≤1+1/n— 1, TsallisQED q is QSZK-hard, leading to hardness of approximating the von Neumann entropy because Sq(ρ) ≤ S (ρ), as long as BQPQSZK. The hardness results are derived from reductions based on new inequalities for the quantumq-Jensen–(Shannon–)Tsallis divergence with 1 ≤q≤ 2, which are of independent interest.

arXiv:2410.13559•IEEE Transactions on Information Theory•Apr 14, 2026•13 citations

Quantum Distinguishing Complexity, Zero-Error Algorithms, and Statistical Zero Knowledge

Shalev Ben-David, Robin Kothari

We define a new query measure we call quantum distinguishing complexity, denoted QD(f) for a Boolean function f. Unlike a quantum query algorithm, which must output a state close to |0> on a 0-input and a state close to |1> on a 1-input, a "quantum distinguishing algorithm" can output any state, as long as the output states for any 0-input and 1-input are distinguishable. Using this measure, we establish a new relationship in query complexity: For all total functions f, Q_0(f)=O~(Q(f)^5), where Q_0(f) and Q(f) denote the zero-error and bounded-error quantum query complexity of f respectively, improving on the previously known sixth power relationship. We also define a query measure based on quantum statistical zero-knowledge proofs, QSZK(f), which is at most Q(f). We show that QD(f) in fact lower bounds QSZK(f) and not just Q(f). QD(f) also upper bounds the (positive-weights) adversary bound, which yields the following relationships for all f: Q(f) >= QSZK(f) >= QD(f) = Omega(Adv(f)). This sheds some light on why the adversary bound proves suboptimal bounds for problems like Collision and Set Equality, which have low QSZK complexity. Lastly, we show implications for lifting theorems in communication complexity. We show that a general lifting theorem for either zero-error quantum query complexity or for QSZK would imply a general lifting theorem for bounded-error quantum query complexity.

arXiv:1902.03660•Leibniz international proceedings in informatics•Jan 1, 2019•6 citations

Semidefinite extension complexity of the separable set, with applications to approximate disentanglers

Sevag Gharibian, Carsten Hecht, Dorian Rudolph

We prove quantitative lower bounds on the semidefinite extension complexity of the set of separable quantum states on $\mathbb{C}^d\otimes\mathbb{C}^d$. We consider semidefinite programs (SDPs) that approximate the maximum acceptance probability of a measurement over separable states, the optimization problem underlying QMA(2). In the extended-formulation model of Harrow, Natarajan, and Wu (HNW), all measurements share a common feasible region and an objective-independent embedding of product states that exactly reproduces their acceptance probabilities. For every $0<θ<2/7$, there are constants $c_θ,a_θ>0$ such that, for sufficiently large $d$, any such SDP with uniform additive error $0<a\le a_θ$ has size at least $d^{c_θ\min\{a^{-1/3},d^θ\}}$. The bound applies at sufficiently small constant error, is superpolynomial in $d$ whenever $a=o(1)$, and becomes $d^{Ω(d^θ)}$ when $a\le d^{-3θ}$, improving HNW's quasipolynomial bound at inverse- square error. The same bound holds for any SDP-representable convex set of states that contains all separable states and lies within trace distance $a$ of them, giving a quantitative counterpart to Fawzi's theorem that the separable set has no exact semidefinite representation. Our proof combines the quantitative pseudo-density theorem of Lee, Raghavendra, and Steurer with explicit block-positive operators and Chebyshev amplification. Our main results are supported by Lean proofs.

quant-pharXiv:2609.09033•Sep 9, 2026•1 citation
Abstract The complexity class Quantum Statistical Zero-Knowledge captures computational difficulties of the time-bounded quantum state testing problem with respect to the trace distance, deciding whether T(ρ0,ρ1)\textrm{T}(\rho_0,\rho_1)T(ρ0​,ρ1​) T ( ρ 0 , ρ 1 ) is at least α\alphaα α or at most β\betaβ β , known as the Quantum State Distinguishability Problem (QSDP) introduced by Watrous (FOCS 2002). However, QSDP[α,β]\textrm{QSDP}[\alpha,\beta]QSDP[α,β] QSDP [ α , β ] is in only within the constant polarizing regime, where α and β\alpha \, \textrm{and} \, \betaαandβ α and β are constants satisfying α2>β\alpha^2 > \betaα2>β α 2 > β (rather than α>β\alpha > \betaα>β α > β ), similar to its classical counterpart shown by Sahai and Vadhan (JACM 2003) due to the polarization lemma (error reduction for SDP). Recently, Berman, Degwekar, Rothblum, and Vasudevan (TCC 2019) extended the containment of SDP beyond the polarizing regime via the time-bounded distribution testing problems with respect to the triangular discrimination and the Jensen-Shannon divergence. Our work 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 of QSDP beyond the polarizing regime and establish a simple -hardness for the quantum entropy difference problem (QEDP) defined by Ben-Aroya, Schwartz, and Ta-Shma (ToC 2010). Furthermore, we prove that QSDP with some exponentially small errors is in , while the same problem without error is in .
Recent advancements in quantum devices have posed an intriguing challenge of verifying their intended functionality.These devices, typically time-bounded, are often designed to prepare specific 𝑛-qubit states, denoted as 𝜌 ! and 𝜌 " .The problem of (tolerant) quantum state testing aims to design algorithms that can efficiently decide whether 𝜌 ! is either 𝜀 " -close to or 𝜀 # -far from 𝜌 " with respect to a chosen distance-like measure.This problem generalizes classical distribution testing to the quantum domain and forms a part of quantum property testing, an emerging field dedicated to developing efficient quantum testers for properties of quantum objects.The computational complexity of time-bounded state testing varies significantly with the choice of closeness measure, exhibiting a dichotomy-like behavior:• For both the trace distance (ℓ " norm) and the quantum (von Neumann) entropy difference, the problems correspond to the complexity class QSZK, as shown in Watrous (FOCS 2002), Watrous (SICOMP 2009), and Ben-Aroya, Schwartz, and Ta-Shma (CCC 2008), which is widely believed to be strictly more powerful than BQP.
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 ) and two-sided error ( ), approached from a quantum (mixed) state testing perspective: The first family of natural complete problems for unitary coRQL\text {\textsf {coRQL}} coRQL coRQL , 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 (von Neumann) entropy difference. In the space-bounded quantum state testing problem, we consider two logarithmic-qubit quantum circuits (devices) denoted as Q0Q_0Q0​ Q 0 and Q1Q_1Q1​ Q 1 , which prepare quantum states ρ0\rho _0ρ0​ ρ 0 and ρ1\rho _1ρ1​ ρ 1 , respectively, with access to their “source code”. Our goal is to decide whether ρ0\rho _0ρ0​ ρ 0 is ϵ1\epsilon _1ϵ1​ ϵ 1 -close to or ϵ2\epsilon _2ϵ2​ ϵ 2 -far from ρ1\rho _1ρ1​ ρ 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.
The complexity class Quantum Statistical Zero-Knowledge (QSZK\mathsf{QSZK}QSZK), introduced by Watrous (FOCS 2002) and later refined in Watrous (SICOMP, 2009), has the best known upper bound QIP(2)∩co-QIP(2)\mathsf{QIP(2)} \cap \text{co-}\mathsf{QIP(2)}QIP(2)∩co-QIP(2), which was simplified following the inclusion QIP(2)⊆PSPACE\mathsf{QIP(2)} \subseteq \mathsf{PSPACE}QIP(2)⊆PSPACE established in Jain, Upadhyay, and Watrous (FOCS 2009). Here, QIP(2)\mathsf{QIP(2)}QIP(2) denotes the class of promise problems that admit two-message quantum interactive proof systems in which the honest prover is typically computationally unbounded, and co-QIP(2)\text{co-}\mathsf{QIP(2)}co-QIP(2) denotes the complement of QIP(2)\mathsf{QIP(2)}QIP(2). We slightly improve this upper bound to QIP(2)∩co-QIP(2)\mathsf{QIP(2)} \cap \text{co-}\mathsf{QIP(2)}QIP(2)∩co-QIP(2) with a quantum linear-space honest prover. Specifically, the honest prover uses space linear in the size of the transcript of the original QSZK\mathsf{QSZK}QSZK proof system. A similar improvement also applies to the upper bound for the non-interactive variant NIQSZK\mathsf{NIQSZK}NIQSZK. Our main techniques are algorithmic versions 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).
We investigate the computational complexity of estimating the trace of quantum state powers tr(ρq) for annqubit mixed quantum state ρ, given its state-preparation circuit of size poly(n). This quantity is closely related to and often interchangeable with the Tsallis entropy Sq(ρ) = 1—tr(ρq)/q—1, whereq= 1 corresponds to the von Neumann entropy. For any non-integerq≥ 1 + Ω(1), we provide a quantum estimator for Sq(ρ) with time complexity 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 (TIT 2025). Our speedup is achieved by introducing efficiently computableuniform approximationsof positive power functions into quantum singular value transformation. Our quantum algorithm reveals a sharp phase transition between the case ofq= 1 and constantq> 1 in the computational complexity of the Quantumq-Tsallis Entropy Difference Problem (TsallisQEDq), particularly deciding whether the difference Sq(ρ0)−Sq(ρ1) is at least 0.001 or at most −0.001: • For any 1 + Ω (1) ≤q≤ 2, TsallisQEDqis BQP-complete, which implies that Purity Estimation is also BQP-complete. • For any 1≤q≤1+1/n— 1, TsallisQED q is QSZK-hard, leading to hardness of approximating the von Neumann entropy because Sq(ρ) ≤ S (ρ), as long as BQPQSZK. The hardness results are derived from reductions based on new inequalities for the quantumq-Jensen–(Shannon–)Tsallis divergence with 1 ≤q≤ 2, which are of independent interest.
We define a new query measure we call quantum distinguishing complexity, denoted QD(f) for a Boolean function f. Unlike a quantum query algorithm, which must output a state close to |0> on a 0-input and a state close to |1> on a 1-input, a "quantum distinguishing algorithm" can output any state, as long as the output states for any 0-input and 1-input are distinguishable. Using this measure, we establish a new relationship in query complexity: For all total functions f, Q_0(f)=O~(Q(f)^5), where Q_0(f) and Q(f) denote the zero-error and bounded-error quantum query complexity of f respectively, improving on the previously known sixth power relationship. We also define a query measure based on quantum statistical zero-knowledge proofs, QSZK(f), which is at most Q(f). We show that QD(f) in fact lower bounds QSZK(f) and not just Q(f). QD(f) also upper bounds the (positive-weights) adversary bound, which yields the following relationships for all f: Q(f) >= QSZK(f) >= QD(f) = Omega(Adv(f)). This sheds some light on why the adversary bound proves suboptimal bounds for problems like Collision and Set Equality, which have low QSZK complexity. Lastly, we show implications for lifting theorems in communication complexity. We show that a general lifting theorem for either zero-error quantum query complexity or for QSZK would imply a general lifting theorem for bounded-error quantum query complexity.
We prove quantitative lower bounds on the semidefinite extension complexity of the set of separable quantum states on Cd⊗Cd\mathbb{C}^d\otimes\mathbb{C}^dCd⊗Cd. We consider semidefinite programs (SDPs) that approximate the maximum acceptance probability of a measurement over separable states, the optimization problem underlying QMA(2). In the extended-formulation model of Harrow, Natarajan, and Wu (HNW), all measurements share a common feasible region and an objective-independent embedding of product states that exactly reproduces their acceptance probabilities. For every 0<θ<2/70<θ<2/70<θ<2/7, there are constants cθ,aθ>0c_θ,a_θ>0cθ​,aθ​>0 such that, for sufficiently large ddd, any such SDP with uniform additive error 0<a≤aθ0<a\le a_θ0<a≤aθ​ has size at least dcθmin⁡{a−1/3,dθ}d^{c_θ\min\{a^{-1/3},d^θ\}}dcθ​min{a−1/3,dθ}. The bound applies at sufficiently small constant error, is superpolynomial in ddd whenever a=o(1)a=o(1)a=o(1), and becomes dΩ(dθ)d^{Ω(d^θ)}dΩ(dθ) when a≤d−3θa\le d^{-3θ}a≤d−3θ, improving HNW's quasipolynomial bound at inverse- square error. The same bound holds for any SDP-representable convex set of states that contains all separable states and lies within trace distance aaa of them, giving a quantitative counterpart to Fawzi's theorem that the separable set has no exact semidefinite representation. Our proof combines the quantitative pseudo-density theorem of Lee, Raghavendra, and Steurer with explicit block-positive operators and Chebyshev amplification. Our main results are supported by Lean proofs.