論文の概要: 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の難解性仮定に反するであろうと推測する。

関連論文リスト

• Fidelity-dissipation relations in quantum gates [0.0]
  実際の量子ゲートは、一般的に散逸環境の影響を受け、その忠実度を著しく低下させる。 本研究では,ジェネリック量子ゲートの平均忠実度と計算過程中に発生する散逸の基本的な関係を解明する。 その結果、熱力学と量子コンピューティングの深い関係に光を当て、熱力学によって課される計算の限界を明らかにした。
  論文  参考訳（メタデータ） (2023-11-27T12:31:52Z)
• Quantum complexity phase transitions in monitored random circuits [0.29998889086656577]
  監視されたランダム回路における量子状態複雑性のダイナミクスについて検討する。 正確な量子状態の複雑性の進化は、測定率を変更する際に相転移を起こす。
  論文  参考訳（メタデータ） (2023-05-24T18:00:11Z)
• Quantum process tomography of continuous-variable gates using coherent states [49.299443295581064]
  ボソニックモード超伝導回路におけるコヒーレント状態量子プロセストモグラフィ(csQPT)の使用を実証する。 符号化量子ビット上の変位とSNAP演算を用いて構築した論理量子ゲートを特徴付けることにより,本手法の結果を示す。
  論文  参考訳（メタデータ） (2023-03-02T18:08:08Z)
• Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
  トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。 我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。 我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
  論文  参考訳（メタデータ） (2022-09-28T17:53:25Z)
• Single-qubit gate teleportation provides a quantum advantage [0.0]
  ゲートテレポーテーション回路は、量子計算の優位性をもたらすと考えられる計算の最も基本的な例である。 単一量子Clifford-gate-teleportation回路であっても、このシミュレーション問題はファンインゲートが有界な定数深さの古典回路では解けない。
  論文  参考訳（メタデータ） (2022-09-28T15:11:39Z)
• Quantum circuit debugging and sensitivity analysis via local inversions [62.997667081978825]
  本稿では,回路に最も影響を及ぼす量子回路の断面をピンポイントする手法を提案する。 我々は,IBM量子マシン上に実装されたアルゴリズム回路の例に応用して,提案手法の実用性と有効性を示す。
  論文  参考訳（メタデータ） (2022-04-12T19:39:31Z)
• Gaussian initializations help deep variational quantum circuits escape from the barren plateau [87.04438831673063]
  近年、変分量子回路は量子シミュレーションや量子機械学習に広く用いられている。 しかし、ランダムな構造を持つ量子回路は、回路深さと量子ビット数に関して指数関数的に消える勾配のため、トレーニング容易性が低い。 この結果、ディープ量子回路は実用的なタスクでは実現できないという一般的な信念が導かれる。
  論文  参考訳（メタデータ） (2022-03-17T15:06:40Z)
• Quantum State Complexity in Computationally Tractable Quantum Circuits [0.0]
  本稿では,量子オートマトン回路(quantum automatedon circuits)と呼ばれる,数値計算可能な量子回路の特殊なクラスについて論じる。 オートマトン波動関数は量子状態の複雑さが高いことを示す。 局所量子回路における設計複雑性の線形成長の証拠を示す。
  論文  参考訳（メタデータ） (2020-09-11T16:25:11Z)
• Boundaries of quantum supremacy via random circuit sampling [69.16452769334367]
  Googleの最近の量子超越性実験は、量子コンピューティングがランダムな回路サンプリングという計算タスクを実行する遷移点を示している。 観測された量子ランタイムの利点の制約を、より多くの量子ビットとゲートで検討する。
  論文  参考訳（メタデータ） (2020-05-05T20:11:53Z)
• Pseudo-dimension of quantum circuits [0.0]
  量子回路の出力確率に擬似次元境界を証明した。 既知のサイズと深さの回路がPAC学習可能であることを示す。
  論文  参考訳（メタデータ） (2020-02-04T19:00:13Z)

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

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