Fugu-MT 論文翻訳(概要): On estimating the quantum $\ell

論文の概要: On estimating the quantum $\ell_α$ distance

arxiv url: http://arxiv.org/abs/2505.00457v1
Date: Thu, 01 May 2025 11:15:20 GMT
ステータス: 翻訳完了
システム内更新日: 2025-05-02 19:15:55.284806
Title: On estimating the quantum $\ell_α$ distance
Title（参考訳）: 量子$\ell_α$距離の推定について
Authors: Yupan Liu, Qisheng Wang,
Abstract要約: 時間複雑性を持つ$mathrmT_alpha(rho_0,rho_1)$に対する効率的なランク独立量子推定器を開発した。我々のアルゴリズムは、量子状態微分可能性問題の計算複雑性の2分法をSchatten $alpha$-norm (QSD$_alpha$)で明らかにしている。この硬さは、1leq α leq infty$ の量子 $ell_alpha$ 距離に対する新しい階数依存の不等式に基づく還元の結果に続く。
参考スコア（独自算出の注目度）: 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.
Abstract（参考訳）: 量子$\ell_{\alpha}$ distance ${\mathrm{T}_\alpha}(\rho_0,\rho_1)$, defined by the Schatten $\alpha$-norm $\|A\|_{\alpha} = \mathrm{tr}(|A|^{\alpha})^{1/\alpha}$, given $\operatorname{poly}(n)$-size state-preparation circuits of $n$-qubit quantum state $\rho_0$ and $\rho_1$。この量は、$\alpha > 1$ のトレース距離の低い境界として機能する。任意の定数 $\alpha > 1$ に対して、Wang, Guan, Liu, Zhang, Ying (TIT 2024) による以前の最高値である $\exp(n)$ の指数的スピードアップを達成するために、時間複雑性を持つ${\mathrm{T}_\alpha}(\rho_0,\rho_1)$ の効率的なランク独立量子推定器を開発する。我々の改良は、量子特異値変換における符号付き正のパワー関数の計算可能な一様多項式近似を利用して、量子状態の階数への依存をなくす。これは${\mathrm{T}_\alpha}(\rho_0,\rho_1)$が少なくとも$2/5$か、少なくとも$1/5$かを決定することを意味する。この二分法は、定数 $\alpha > 1$ と $\alpha=1$: - 任意の $1+\Omega(1) \leq \alpha \leq O(1)$, QSD$_{\alpha}$ に対して $\mathsf{BQP}$-complete の場合に生じる。 QSD$_{\alpha}$は$\mathsf{QSZK}$-完全であり、$\mathrm{T}_\alpha(\rho_0,\rho_1)$の効率的な量子推定器が存在しないことを意味する。この硬さは、量子 $\ell_{\alpha}$ 距離が 1\leq \alpha \leq \infty$ の新たな階数依存の不等式に基づく還元の結果に続く。

関連論文リスト

The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文参考訳（メタデータ） (2024-10-26T06:21:42Z)
On estimating the trace of quantum state powers [2.637436382971936]
量子状態のトレースを推定する計算複雑性を、$n$-qubit混合量子状態$rho$に対して$texttr(rhoq)$で調べる。我々の高速化は、正のパワー関数の計算可能な一様近似を量子特異値変換に効率よく導入することで達成される。
論文参考訳（メタデータ） (2024-10-17T13:57:13Z)
Learning low-degree quantum objects [5.2373060530454625]
低次量子オブジェクトを、$ell$-distanceで$varepsilon$-errorまで学習する方法を示す。我々の主な技術的貢献は、量子チャネルと完全有界ポリリノミアルに対する新しいボネンブラスト・ヒル不等式である。
論文参考訳（メタデータ） (2024-05-17T17:36:44Z)
Basic quantum subroutines: finding multiple marked elements and summing numbers [1.1265248232450553]
量子クエリーの最適数$O(sqrtN k)$を用いて、サイズ$N$のリスト内のすべての$k$マーク要素を見つける方法を示す。
論文参考訳（メタデータ） (2023-02-20T19:11:44Z)
Low-degree learning and the metric entropy of polynomials [44.99833362998488]
少なくとも$Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon)は2辺の推定値$c(1-varepsilon)2dlogを満たす。
論文参考訳（メタデータ） (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]
制御量子状態準備(CQSP)は、与えられた$n$-qubit状態に対するすべての$iin 0,1k$に対して、$|irangle |0nrangleから |irangle |psi_irangle $への変換を提供することを目的としている。我々は、深さ$Oleft(n+k+frac2n+kn+k+mright)$とサイズ$Oleft(2n+kright)$のCQSPを実装するための量子回路を構築する。
論文参考訳（メタデータ） (2022-02-23T04:19:57Z)
Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
論文参考訳（メタデータ） (2021-08-19T16:16:48Z)
An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
論文参考訳（メタデータ） (2020-08-24T06:50:57Z)
Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
論文参考訳（メタデータ） (2020-06-06T13:34:41Z)
Fast digital methods for adiabatic state preparation [0.0]
ゲート型量子コンピュータにおいて,逆誤差の複雑多元対数を伴う断熱状態生成のための量子アルゴリズムを提案する。
論文参考訳（メタデータ） (2020-04-08T18:00:01Z)
Tight Quantum Lower Bound for Approximate Counting with Quantum States [49.6558487240078]
Aaronson, Kothari, Kretschmer, Thaler (2020) が考える数え上げ問題の次の変種に対する厳密な下界を証明する。このタスクは、入力セット$xsubseteq [n]$が$k$か$k'=(1+varepsilon)k$であるかどうかを識別する。
論文参考訳（メタデータ） (2020-02-17T10:53:50Z)
On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions [62.01594253618911]
有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
論文参考訳（メタデータ） (2020-02-09T03:39:46Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。