論文の概要: Generalized Zurek's bound on the cost of an individual classical or
quantum computation
- arxiv url: http://arxiv.org/abs/2301.06838v1
- Date: Tue, 17 Jan 2023 12:35:08 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-18 14:20:06.443706
- Title: Generalized Zurek's bound on the cost of an individual classical or
quantum computation
- Title（参考訳）: 個々の古典的あるいは量子計算のコストに縛られる一般化ズレックの一般化
- Authors: Artemy Kolchinsky
- Abstract要約: Zurekは、このコストは$K(xvert y)$、条件付きコルモゴロフ複雑性$x$$$$$$$$$$$によって与えられると提案した。
我々は、$K(xvert y)$が$x$から$y$にマッピングする基本的なコストであることを示す。
この結果は、第2法則と物理教会チューリング論との関係に意味を持つ「アルゴリズム的揺らぎ定理」の一種である。
- 参考スコア（独自算出の注目度）: 1.95804735329484
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the minimal thermodynamic cost of an individual computation,
where a single input $x$ is transformed into a single output $y$. In prior
work, Zurek proposed that this cost was given by $K(x\vert y)$, the conditional
Kolmogorov complexity of $x$ given $y$ (up to an additive constant which does
not depend on $x$ or $y$). However, this result was derived from an informal
argument, applied only to deterministic computations, and had an arbitrary
dependence on the choice of physical protocol (via the additive constant). Here
we use stochastic thermodynamics to derive a generalized version of Zurek's
bound from a rigorous Hamiltonian formulation. Our bound applies to all quantum
and classical processes, whether noisy or deterministic, and it explicitly
captures the dependence on the protocol. We show that $K(x\vert y)$ is a
fundamental cost of mapping $x$ to $y$ which must be paid using some
combination of heat, noise, and protocol complexity, implying a tradeoff
between these three resources. We also show that this bound is achievable. Our
result is a kind of "algorithmic fluctuation theorem" which has implications
for the relationship between the Second Law and the Physical Church-Turing
thesis.
- Abstract（参考訳）: 個々の計算の最小熱力学的コストを考えると、1つの入力$x$が1つの出力$y$に変換される。
以前の研究で、ズレックは、このコストは$K(x\vert y)$、条件付きコルモゴロフ複雑性$x$$$$y$($x$または$y$に依存しない加法定数まで)によって与えられると提案した。
しかし、この結果は非公式な議論から導出され、決定論的計算にのみ適用され、(加法定数を通じて)物理プロトコルの選択に任意に依存する。
ここでは確率的熱力学を用いて、厳密なハミルトン公式からzurekの束縛の一般化バージョンを導出する。
私たちの境界は、ノイズや決定論に関わらず、すべての量子プロセスや古典プロセスに適用され、プロトコルへの依存を明示的に捉えます。
k(x\vert y)$ は、x$ から $y$ へのマッピングの基本的なコストであり、熱、ノイズ、プロトコルの複雑さの組み合わせで払わなければならない。
また、この境界は達成可能であることも示します。
この結果は、第2法則と物理教会チューリング論との関係に意味を持つ「アルゴリズム的揺らぎ定理」の一種である。
関連論文リスト
- Settling the Sample Complexity of Online Reinforcement Learning [92.02082223856479]
バーンインコストを発生させることなく、最小限の最適後悔を実現する方法を示す。
最適値/コストや一定の分散といった問題依存量の影響を明らかにするために、我々の理論を拡張します。
論文 参考訳（メタデータ） (2023-07-25T15:42:11Z) - Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。
異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。
我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
論文 参考訳（メタデータ） (2022-06-07T18:00:01Z) - Non-local computation of quantum circuits with small light cones [0.0]
ポートベースのテレポーテーションは、一度に少数の量子ビットでのみ行われる場合、はるかに少ない絡み合いになる。
我々は、プロトコルの絡み合いコストが既知のプロトコルよりも良くスケールする、明示的なユニタリのクラスを提供する。
論文 参考訳（メタデータ） (2022-03-18T18:00:06Z) - Classical Verification of Quantum Computations in Linear Time [2.3465488122819123]
複雑度$O(poly(kappa)|C|)$という,既存のプロトコルよりもはるかに高速なCVQCプロトコルを提供する。
我々のプロトコルは、ノイズの多いトラップドアの爪のない関数の存在を前提として、量子ランダムオラクルモデル [arXiv:1008.0931] において安全である。
また、$|+thetarangle=frac1sqrt2(|0rangle+eithetapi/4|1rangle)の状態に対する新しい古典的なチャネルリモート状態準備プロトコルも提供します。
論文 参考訳（メタデータ） (2022-02-28T18:05:53Z) - A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。
振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
論文 参考訳（メタデータ） (2022-01-31T22:19:49Z) - Causality Constraint on Circuit Complexity from $COSMOEFT$ [1.5643170704979468]
本稿では,回路複雑度測定とエンタングルメントエントロピーのスケール係数および$c_s$に対する挙動について検討する。
窓の内側には、因果性と宇宙観測の両方によって支えられる0.024leq c_sleq 1$という、興味深い未発見の様々な特徴がある。
論文 参考訳（メタデータ） (2021-11-22T19:09:51Z) - Affine Quantization of the Harmonic Oscillator on the Semi-bounded
domain $(-b,\infty)$ for $b: 0 \rightarrow \infty$ [0.0]
affine Quantization (AQ) Fantoni と Klauder (arXiv:2109.13447,Phys. D bf 103, 076013 (2021) を用いて古典システムの量子対向体への変換を研究する。
我々はこの問題を$b rightarrow infty$で数値的に解き、Gouba (arXiv:2005.08696,J. High Energy Phys., Gravitation Cosmol) の結果を確認した。
論文 参考訳（メタデータ） (2021-11-20T22:52:45Z) - Annihilating Entanglement Between Cones [77.34726150561087]
ローレンツ錐体は、ある種の強いレジリエンス特性を満たす対称基底を持つ唯一の円錐体であることを示す。
我々の証明はローレンツ・コーンの対称性を利用しており、エンタングルメント蒸留のプロトコルに類似した2つの構造を適用している。
論文 参考訳（メタデータ） (2021-10-22T15:02:39Z) - Permutation Compressors for Provably Faster Distributed Nonconvex
Optimization [68.8204255655161]
本稿では,Gorbunov et al (2021) の MARINA 法が,理論的な通信複雑性の観点から最先端の手法とみなすことができることを示す。
MARINAの理論は、古典的な独立圧縮機設定を超えて、潜在的にエミュレートされた圧縮機の理論を支持するものである。
論文 参考訳（メタデータ） (2021-10-07T09:38:15Z) - Lower Bounds for XOR of Forrelations [7.510385608531827]
我々は Forrelation 関数の独立コピー $k$ の XOR について検討する。
また、任意の準ポリノミカルサイズの定数深さ回路が、ランダムな推測に対して準ポリノミカルに小さな優位性を持つことを示す。
論文 参考訳（メタデータ） (2020-07-07T17:05:09Z) - Quantum Communication Complexity of Distribution Testing [114.31181206328276]
2人のプレーヤーが1つのディストリビューションから$t$のサンプルを受け取ります。
目標は、2つの分布が等しいか、または$epsilon$-far であるかどうかを決定することである。
この問題の量子通信複雑性が$tildeO$(tepsilon2)$ qubitsであることを示す。
論文 参考訳（メタデータ） (2020-06-26T09:05:58Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。