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 .
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) T ( ρ 0 , ρ 1 ) is at least α α or at most β β , known as the Quantum State Distinguishability Problem (QSDP) introduced by Watrous (FOCS 2002). However, QSDP[α,β] QSDP [ α , β ] is in only within the constant polarizing regime, where αandβ α and β are constants satisfying α2>β α 2 > β (rather than α>β α > β ), 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.
The complexity class Quantum Statistical Zero-Knowledge (QSZK), introduced by Watrous (FOCS 2002) and later refined in Watrous (SICOMP, 2009), has the best known upper bound QIP(2)∩co-QIP(2), which was simplified following the inclusion QIP(2)⊆PSPACE established in Jain, Upadhyay, and Watrous (FOCS 2009). Here, 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) denotes the complement of QIP(2).
We slightly improve this upper bound to 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 proof system. A similar improvement also applies to the upper bound for the non-interactive variant 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. 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≤aθ has size at least dcθ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≤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.
Quantum Stein’s lemma is a cornerstone of quantum statistics and concerns the problem of correctly identifying a quantum state, given the knowledge that it is one of two specific states (ρ or σ). It was originally derived in the asymptotic i.i.d. setting, in which arbitrarily many (say, n) identical copies of the state (ρ⊗n or σ⊗n) are considered to be available. In this setting, the lemma states that, for any given upper bound on the probability αn of erroneously inferring the state to be σ, the probability βn of erroneously inferring the state to be ρ decays exponentially in n, with the rate of decay converging to the relative entropy of the two states. The second order asymptotics for quantum hypothesis testing, which establishes the speed of convergence of this rate of decay to its limiting value, was derived in the i.i.d. setting independently by Tomamichel and Hayashi, and Li. We extend this result to settings beyond i.i.d. Examples of these include Gibbs states of quantum spin systems (with finite-range, translation-invariant interactions) at high temperatures, and quasi-free states of fermionic lattice gases.