Fugu-MT 論文翻訳(概要): Computational aspects of the trace norm contraction coefficient

論文の概要: Computational aspects of the trace norm contraction coefficient

arxiv url: http://arxiv.org/abs/2507.16737v1
Date: Tue, 22 Jul 2025 16:22:07 GMT
ステータス: 翻訳完了
システム内更新日: 2025-07-23 21:34:14.202887
Title: Computational aspects of the trace norm contraction coefficient
Title（参考訳）: トレースノルム収縮係数の計算的側面
Authors: Idris Delsol, Omar Fawzi, Jan Kochanowski, Akshay Ramachandran,
Abstract要約: 定数係数内での量子チャネルのトレースノルム収縮係数の近似はNPハードであることが示される。また、縮約係数上の半定値プログラミング上界の収束階層も確立する。
参考スコア（独自算出の注目度）: 4.916646834691489
License: http://creativecommons.org/licenses/by/4.0/
Abstract: We show that approximating the trace norm contraction coefficient of a quantum channel within a constant factor is NP-hard. Equivalently, this shows that determining the optimal success probability for encoding a bit in a quantum system undergoing noise is NP-hard. This contrasts with the classical analogue of this problem that can clearly by solved efficiently. Our hardness results also hold for deciding if the contraction coefficient is equal to 1. As a consequence, we show that deciding if a non-commutative graph has an independence number of at least 2 is NP-hard. In addition, we establish a converging hierarchy of semidefinite programming upper bounds on the contraction coefficient.
Abstract（参考訳）: 定数係数内での量子チャネルのトレースノルム収縮係数の近似はNPハードであることが示される。同様に、ノイズを受ける量子系においてビットを符号化する最適な成功確率を決定することはNPハードであることが示される。これは、この問題を効率的に解ける古典的な類似と対照的である。我々の硬度結果は、収縮係数が 1 に等しいかどうかを決定するためにも成立する。その結果、非可換グラフが少なくとも2の独立数を持つかどうかを決定することはNPハードであることを示す。さらに、縮約係数上の半定値プログラミング上界の収束階層を確立する。

関連論文リスト

A Unified Approach to Quantum Contraction and Correlation Coefficients [10.128808054306187]
作用素単調関数によって誘導される非可換$L2(p)$空間の族を導入する。量子最大相関係数と量子 $chi2$-divergences の族を同定する。
論文参考訳（メタデータ） (2025-05-21T08:58:45Z)
Contraction of Private Quantum Channels and Private Quantum Hypothesis Testing [5.211732144306638]
プライバシ制約下でのホッケースティックの分散に対する収縮係数について検討する。また、プライベートな量子チャネルが量子学習環境における公平性とホレボ情報の安定性をどのように提供するかを示す。
論文参考訳（メタデータ） (2024-06-26T18:00:03Z)
An Analysis of Quantum Annealing Algorithms for Solving the Maximum Clique Problem [49.1574468325115]
我々は、QUBO問題として表されるグラフ上の最大傾きを見つける量子D波アンナーの能力を解析する。本稿では, 相補的な最大独立集合問題に対する分解アルゴリズムと, ノード数, 傾き数, 密度, 接続率, 解サイズの他のノード数に対する比を制御するグラフ生成アルゴリズムを提案する。
論文参考訳（メタデータ） (2024-06-11T04:40:05Z)
Quantum Soft Covering and Decoupling with Relative Entropy Criterion [11.987004396261241]
我々は,スムーズなミンエントロピーとスムーズなマックスディバージェンスの観点から,一発境界を導出することで,補題の被覆を証明した。相対エントロピー基準を用いたワンショット量子デカップリング定理を提案する。
論文参考訳（メタデータ） (2024-02-16T22:31:38Z)
Quantum complexity of the Kronecker coefficients [2.2983894078587963]
与えられたクロネッカー係数は、QMA検証器の受理証人によって区切られたベクトル空間の次元をカウントすることを示す。これは、クロネッカー係数を与えられた相対誤差の範囲内で近似することは、ある量子近似数え上げ問題の自然クラスよりも難しくないことを意味する。
論文参考訳（メタデータ） (2023-02-22T15:43:26Z)
Importance sampling for stochastic quantum simulations [68.8204255655161]
我々は、係数に応じてハミルトン式からサンプリングしてランダムな積公式を構築するqDriftプロトコルを導入する。サンプリング段階における個別のシミュレーションコストを考慮し、同じ精度でシミュレーションコストを削減可能であることを示す。格子核効果場理論を用いて数値シミュレーションを行った結果, 実験結果が得られた。
論文参考訳（メタデータ） (2022-12-12T15:06:32Z)
Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
論文参考訳（メタデータ） (2022-09-28T17:53:25Z)
Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
本稿では,n+1$ qubitsしか使用しないGoemans-Williamsonアルゴリズムの変分量子アルゴリズムを提案する。補助量子ビット上で適切にパラメータ化されたユニタリ条件として目的行列を符号化することにより、効率的な最適化を実現する。各種NPハード問題に対して,Goemans-Williamsonアルゴリズムの量子的効率的な実装を考案し,提案プロトコルの有効性を実証する。
論文参考訳（メタデータ） (2022-06-30T03:15:23Z)
Improved Quantum Algorithms for Fidelity Estimation [77.34726150561087]
証明可能な性能保証を伴う忠実度推定のための新しい,効率的な量子アルゴリズムを開発した。我々のアルゴリズムは量子特異値変換のような高度な量子線型代数技術を用いる。任意の非自明な定数加算精度に対する忠実度推定は一般に困難であることを示す。
論文参考訳（メタデータ） (2022-03-30T02:02:16Z)
Polynomial T-depth Quantum Solvability of Noisy Binary Linear Problem: From Quantum-Sample Preparation to Main Computation [0.0]
雑音二元線形問題(NBLP)の量子可解性について完全解析する。 NBLPの解くコストは、指数関数的に増大する論理量子ビットを犠牲にして、問題の規模で解決できることが示される。
論文参考訳（メタデータ） (2021-09-23T07:46:20Z)
Random quantum circuits anti-concentrate in log depth [118.18170052022323]
本研究では,典型的な回路インスタンスにおける測定結果の分布に要するゲート数について検討する。我々の反集中の定義は、予測衝突確率が分布が均一である場合よりも大きい定数因子に過ぎないということである。ゲートが1D環上で最寄りである場合と、ゲートが長距離である場合の両方において、$O(n log(n))ゲートも十分であることを示す。
論文参考訳（メタデータ） (2020-11-24T18:44:57Z)
On estimating the entropy of shallow circuit outputs [49.1574468325115]
確率分布と量子状態のエントロピーを推定することは情報処理の基本的な課題である。本稿では,有界ファンインと非有界ファンアウトのゲートを持つ対数深度回路か定数深度回路のいずれかによって生成された分布や状態に対するエントロピー推定が,少なくともLearning with Errors問題と同程度難しいことを示す。
論文参考訳（メタデータ） (2020-02-27T15:32:08Z)

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