論文の概要: Estimating the entropy of shallow circuit outputs is hard
- arxiv url: http://arxiv.org/abs/2002.12814v1
- Date: Thu, 27 Feb 2020 15:32:08 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-01 12:18:58.056326
- Title: Estimating the entropy of shallow circuit outputs is hard
- Title(参考訳): 浅い回路出力のエントロピーの推定は難しい
- Authors: Alexandru Gheorghiu, Matty J. Hoban
- Abstract要約: シャノンエントロピー推定の意思決定問題バージョンはエントロピー差分(ED)である
量子回路(QED)の類似の問題
オラクルと比較して、これらの問題は指数関数的に大きい回路と同等に難しいものではないことを示す。
- 参考スコア(独自算出の注目度): 77.34726150561087
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The decision problem version of estimating the Shannon entropy is the Entropy
Difference problem (ED): given descriptions of two circuits, determine which
circuit produces more entropy in its output when acting on a uniformly random
input. The analogous problem with quantum circuits (QED) is to determine which
circuit produces the state with greater von Neumann entropy, when acting on a
fixed input state and after tracing out part of the output. Based on plausible
complexity-theoretic assumptions, both of these problems are believed to be
intractable for polynomial-time quantum computation. In this paper, we
investigate the hardness of these problems in the case where the input circuits
have logarithmic and constant depth, respectively. We show that, relative to an
oracle, these problems cannot be as hard as their counterparts with
polynomial-size circuits. Furthermore, we show that if a certain type of
reduction from QED to the log-depth version exists, it implies that any
polynomial-time quantum computation can be performed in log depth. While this
suggests that having shallow circuits makes entropy estimation easier, we give
indication that the problem remains intractable for polynomial-time quantum
computation by proving a reduction from Learning-With-Errors (LWE) to
constant-depth ED. We then consider a potential application of our results to
quantum gravity research. First, we introduce a Hamiltonian version of QED
where one is given two local Hamiltonians and asked to estimate the
entanglement entropy difference in their ground states. We show that this
problem is at least as hard as the circuit version and then discuss a potential
experiment that would make use of the AdS/CFT correspondence to solve LWE
efficiently. We conjecture that unless the AdS/CFT bulk to boundary map is
exponentially complex, this experiment would violate the intractability
assumption of LWE.
- Abstract(参考訳): シャノンエントロピーを推定する決定問題版はエントロピー差分問題 (ED) であり、2つの回路の記述を与えられた場合、どの回路が一様ランダムな入力に作用するかを決定する。
量子回路(qed)と類似する問題は、固定入力状態および出力の一部をトレースした後に、von neumannエントロピーが大きい状態を生成する回路を決定することである。
可算な複雑性理論の仮定に基づき、これらの問題は多項式時間量子計算では難解であると考えられている。
本稿では,入力回路がそれぞれ対数深さと定数深さを持つ場合,これらの問題の硬さについて検討する。
オラクルとは対照的に、これらの問題は多項式サイズの回路と同等に難しいものではないことを示す。
さらに, qedからlog-depthバージョンへのある種の還元が存在する場合, 任意の多項式時間量子計算をログ深さで実行できることを示す。
このことは、浅い回路を持つことでエントロピー推定が容易になることを示しているが、この問題はLWE(Learning-With-Errors)から一定深度EDへの還元を証明し、多項式時間量子計算において難解であることを示す。
次に、量子重力研究への我々の結果の潜在的応用について考察する。
まず、QEDのハミルトン版を紹介し、そこでは2つの局所ハミルトニアンを与え、基底状態の絡み合いエントロピー差を推定する。
この問題は回路版と同等に難しいことを示し、LWEを効率的に解くためにAdS/CFT対応を利用した潜在的実験について議論する。
我々は、AdS/CFTバルクと境界写像が指数関数的に複雑でなければ、この実験はLWEの難解性仮定に反するであろうと推測する。
関連論文リスト
- Dense outputs from quantum simulations [1.8076403084528587]
量子密度出力問題は、時間依存の量子力学から時間累積観測値を評価する過程である。
この問題は量子制御や分光計算などの応用で頻繁に発生する。
我々は、早期および完全フォールトトレラントな量子プラットフォームの両方で動作するように設計されたアルゴリズムを提示する。
論文 参考訳(メタデータ) (2023-07-26T18:16:51Z) - Instantaneous nonlocal quantum computation and circuit depth reduction [7.148511452018054]
2パーティの量子計算は、2部構成の入力と出力を持つ計算プロセスであり、初期共有の絡み合いが存在する。
まず,ガーデニング・ホース・ガジェットとして知られる,単純化されたサブプロデューサは,絡み合いのコストを著しく低減できないことを示す。
第2部では、クリフォードゲートとTゲートの層からなる任意のユニタリ回路が、元の回路のT深さに比例した深さの測定値を持つ回路を用いて実装可能であることを示す。
論文 参考訳(メタデータ) (2023-06-15T17:57:50Z) - Hamiltonian variational ansatz without barren plateaus [0.0]
変分量子アルゴリズムは、短期量子コンピュータの最も有望な応用の1つである。
その大きな可能性にもかかわらず、数十量子ビットを超える変分量子アルゴリズムの有用性は疑問視されている。
論文 参考訳(メタデータ) (2023-02-16T19:01:26Z) - Complexity-Theoretic Limitations on Quantum Algorithms for Topological
Data Analysis [59.545114016224254]
トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。
我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。
我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
論文 参考訳(メタデータ) (2022-09-28T17:53:25Z) - Circuit Complexity in an interacting quenched Quantum Field Theory [0.0]
量子クエンチが量子場理論の回路複雑性に及ぼす影響について検討する。
待ち行列および相互作用場理論における回路複雑性の解析計算について述べる。
論文 参考訳(メタデータ) (2022-09-07T18:00:03Z) - Gaussian initializations help deep variational quantum circuits escape
from the barren plateau [87.04438831673063]
近年、変分量子回路は量子シミュレーションや量子機械学習に広く用いられている。
しかし、ランダムな構造を持つ量子回路は、回路深さと量子ビット数に関して指数関数的に消える勾配のため、トレーニング容易性が低い。
この結果、ディープ量子回路は実用的なタスクでは実現できないという一般的な信念が導かれる。
論文 参考訳(メタデータ) (2022-03-17T15:06:40Z) - Numerical Simulations of Noisy Quantum Circuits for Computational
Chemistry [51.827942608832025]
短期量子コンピュータは、小さな分子の基底状態特性を計算することができる。
計算アンサッツの構造と装置ノイズによる誤差が計算にどのように影響するかを示す。
論文 参考訳(メタデータ) (2021-12-31T16:33:10Z) - An Algebraic Quantum Circuit Compression Algorithm for Hamiltonian
Simulation [55.41644538483948]
現在の世代のノイズの多い中間スケール量子コンピュータ(NISQ)は、チップサイズとエラー率に大きく制限されている。
我々は、自由フェルミオンとして知られる特定のスピンハミルトニアンをシミュレーションするために、量子回路を効率よく圧縮するために局所化回路変換を導出する。
提案した数値回路圧縮アルゴリズムは、後方安定に動作し、$mathcalO(103)$スピンを超える回路合成を可能にするスピンの数で3次スケールする。
論文 参考訳(メタデータ) (2021-08-06T19:38:03Z) - Demonstrating robust simulation of driven-dissipative problems on
near-term quantum computers [53.20999552522241]
量子コンピュータは物理学と化学における量子力学系のシミュレーションに革命をもたらす。
現在の量子コンピュータは、訂正されていないノイズ、ゲートエラー、デコヒーレンスのためにアルゴリズムを不完全に実行している。
ここでは、量子力学における最も難しい問題の1つとして、駆動散逸多体問題の解法が本質的にエラーに対して堅牢であることを示す。
論文 参考訳(メタデータ) (2021-08-02T21:36:37Z) - Practical Quantum Computing: solving the wave equation using a quantum
approach [0.0]
量子波方程式解法の実装は、このアルゴリズムの理論的大域的複雑性と一致することを示す。
我々の実装は、量子コンピュータ上でいくつかのPDEを解くことができることを実験的に証明している。
論文 参考訳(メタデータ) (2020-03-27T15:05:31Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。