On estimating the quantum $\ell_α$ distance

• URL: http://arxiv.org/abs/2505.00457v1
• Date: Thu, 01 May 2025 11:15:20 GMT
• Title: On estimating the quantum $\ell_α$ distance
• Authors: Yupan Liu, Qisheng Wang,
• Abstract summary: We develop an efficient rank-independent quantum estimator for $mathrmT_alpha(rho_0,rho_1)$ with time complexity.<n>Our algorithm reveals a dichotomy in the computational complexity of the Quantum State Distinguishability Problem with Schatten $alpha$-norm (QSD$_alpha$)<n>The hardness results follow from reductions based on new rank-dependent inequalities for the quantum $ell_alpha$ distance with $1leq alpha leq infty$, which are of independent interest.
• Score: 2.637436382971936
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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 $\operatorname{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 $\operatorname{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 Quantum State Distinguishability Problem with Schatten $\alpha$-norm (QSD$_{\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)$, QSD$_{\alpha}$ is $\mathsf{BQP}$-complete. - For any $1 \leq \alpha \leq 1+\frac{1}{n}$, QSD$_{\alpha}$ is $\mathsf{QSZK}$-complete, implying that no efficient quantum estimator for $\mathrm{T}_\alpha(\rho_0,\rho_1)$ exists unless $\mathsf{BQP} = \mathsf{QSZK}$. 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.

Related papers

• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  We show that this problem has randomized communication complexity $Omega(frac1kcdot n2log|mathbbF|)$. As an application, we obtain an $Omega(frac1kcdot n2log|mathbbF|)$ space lower bound for any streaming algorithm with $k$ passes.
  arXiv  Detail & Related papers  (2024-10-26T06:21:42Z)
• On estimating the trace of quantum state powers [2.637436382971936]
  We investigate the computational complexity of estimating the trace of quantum state powers $texttr(rhoq)$ for an $n$-qubit mixed quantum state $rho$.<n>Our speedup is achieved by introducing efficiently computable uniform approximations of positive power functions into quantum singular value transformation.
  arXiv  Detail & Related papers  (2024-10-17T13:57:13Z)
• Learning low-degree quantum objects [5.2373060530454625]
  We show how to learn low-degree quantum objects up to $varepsilon$-error in $ell$-distance. Our main technical contributions are new Bohnenblust-Hille inequalities for quantum channels and completely boundedpolynomials.
  arXiv  Detail & Related papers  (2024-05-17T17:36:44Z)
• Basic quantum subroutines: finding multiple marked elements and summing numbers [1.1265248232450553]
  We show how to find all $k$ marked elements in a list of size $N$ using the optimal number $O(sqrtN k)$ of quantum queries.
  arXiv  Detail & Related papers  (2023-02-20T19:11:44Z)
• Low-degree learning and the metric entropy of polynomials [44.99833362998488]
  We prove that any (deterministic or randomized) algorithm which learns $mathscrF_nd$ with $L$-accuracy $varepsilon$ requires at least $Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon) satisfies the two-sided estimate $$c (1-varepsilon)2dlog
  arXiv  Detail & Related papers  (2022-03-17T23:52:08Z)
• Optimal (controlled) quantum state preparation and improved unitary synthesis by quantum circuits with any number of ancillary qubits [20.270300647783003]
  Controlled quantum state preparation (CQSP) aims to provide the transformation of $|irangle |0nrangle to |irangle |psi_irangle $ for all $iin 0,1k$ for the given $n$-qubit states. We construct a quantum circuit for implementing CQSP, with depth $Oleft(n+k+frac2n+kn+k+mright)$ and size $Oleft(2n+kright)$
  arXiv  Detail & Related papers  (2022-02-23T04:19:57Z)
• Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
  We study the problem of PAC learning halfspaces on $mathbbRd$ with Massart noise under Gaussian marginals. Our results qualitatively characterize the complexity of learning halfspaces in the Massart model.
  arXiv  Detail & Related papers  (2021-08-19T16:16:48Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  We prove that for every decision tree, the absolute values of the Fourier coefficients of a given order $ellsqrtbinomdell (1+log n)ell-1,$ sum to at most $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, and $c>0$ is an absolute constant.
  arXiv  Detail & Related papers  (2020-08-24T06:50:57Z)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  Given an MDP with $S$ states, $A$ actions, the discount factor $gamma in (0,1)$, and an approximation threshold $epsilon > 0$, we provide a model-free algorithm to learn an $epsilon$-optimal policy. For small enough $epsilon$, we show an improved algorithm with sample complexity.
  arXiv  Detail & Related papers  (2020-06-06T13:34:41Z)
• Fast digital methods for adiabatic state preparation [0.0]
  We present a quantum algorithm for adiabatic state preparation on a gate-based quantum computer, with complexity polylogarithmic in the inverse error.
  arXiv  Detail & Related papers  (2020-04-08T18:00:01Z)
• Tight Quantum Lower Bound for Approximate Counting with Quantum States [49.6558487240078]
  We prove tight lower bounds for the following variant of the counting problem considered by Aaronson, Kothari, Kretschmer, and Thaler ( 2020) The task is to distinguish whether an input set $xsubseteq [n]$ has size either $k$ or $k'=(1+varepsilon)k$.
  arXiv  Detail & Related papers  (2020-02-17T10:53:50Z)
• On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions [62.01594253618911]
  We exploit the finite noise structure of finite sums to derive a matching $O(n2)$-upper bound under the global oracle model. Following a similar approach, we propose a novel adaptation of SVRG which is both emphcompatible with oracles, and achieves complexity bounds of $tildeO(n2+nsqrtL/mu)log (1/epsilon)$ and $O(nsqrtL/epsilon)$, for $mu>0$ and $mu=0$
  arXiv  Detail & Related papers  (2020-02-09T03:39:46Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.