論文の概要: A single $T$-gate makes distribution learning hard

• arxiv url: http://arxiv.org/abs/2207.03140v1
• Date: Thu, 7 Jul 2022 08:04:15 GMT
• ステータス: 処理完了
• システム内更新日: 2022-07-08 14:59:57.149863
• Title: A single $T$-gate makes distribution learning hard
• Title（参考訳）: 単一の$t$-gateは分散学習を困難にする
• Authors: Marcel Hinsche, Marios Ioannou, Alexander Nietner, Jonas Haferkamp, Yihui Quek, Dominik Hangleiter, Jean-Pierre Seifert, Jens Eisert, Ryan Sweke
• Abstract要約: この研究は、局所量子回路の出力分布の学習可能性に関する広範な評価を提供する。 ハイブリッド量子古典アルゴリズムを含む多種多様な学習アルゴリズムにおいて、深度$d=omega(log(n))$ Clifford回路に関連する生成的モデリング問題さえも困難であることを示す。
• 参考スコア（独自算出の注目度）: 56.045224655472865
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: The task of learning a probability distribution from samples is ubiquitous across the natural sciences. The output distributions of local quantum circuits form a particularly interesting class of distributions, of key importance both to quantum advantage proposals and a variety of quantum machine learning algorithms. In this work, we provide an extensive characterization of the learnability of the output distributions of local quantum circuits. Our first result yields insight into the relationship between the efficient learnability and the efficient simulatability of these distributions. Specifically, we prove that the density modelling problem associated with Clifford circuits can be efficiently solved, while for depth $d=n^{\Omega(1)}$ circuits the injection of a single $T$-gate into the circuit renders this problem hard. This result shows that efficient simulatability does not imply efficient learnability. Our second set of results provides insight into the potential and limitations of quantum generative modelling algorithms. We first show that the generative modelling problem associated with depth $d=n^{\Omega(1)}$ local quantum circuits is hard for any learning algorithm, classical or quantum. As a consequence, one cannot use a quantum algorithm to gain a practical advantage for this task. We then show that, for a wide variety of the most practically relevant learning algorithms -- including hybrid-quantum classical algorithms -- even the generative modelling problem associated with depth $d=\omega(\log(n))$ Clifford circuits is hard. This result places limitations on the applicability of near-term hybrid quantum-classical generative modelling algorithms.
• Abstract（参考訳）: サンプルから確率分布を学習する作業は、自然科学で広く行われている。 局所量子回路の出力分布は特に興味深い分布のクラスを形成し、量子アドバンテージの提案と様々な量子機械学習アルゴリズムの両方にとって重要な意味を持つ。 本研究では,局所量子回路の出力分布の学習可能性について,広範囲に評価する。 最初の結果は、これらの分布の効率的な学習可能性と効率的なシミュラビリティの関係についての洞察を与える。 具体的には、クリフォード回路に関連する密度モデリング問題を効率的に解くことができることを証明し、深さ$d=n^{\omega(1)}$回路では、1つの$t$-gateを回路に注入することはこの問題を難しくする。 この結果は、効率的なシミュラビリティが効率的学習可能性を意味するものではないことを示している。 第2の成果セットは、量子生成モデリングアルゴリズムの可能性と限界に関する洞察を提供します。 最初に、深度$d=n^{\Omega(1)}=局所量子回路に関連する生成的モデリング問題は、古典的あるいは量子的な学習アルゴリズムでは困難であることを示す。 結果として、このタスクに実用的な利点を得るために量子アルゴリズムを使うことはできない。 次に、多種多様な関連する学習アルゴリズム(例えばハイブリッド量子古典アルゴリズム)に対して、深さ$d=\omega(\log(n))$ Clifford回路に関連する生成的モデリング問題さえも困難であることを示す。 この結果は、短期的ハイブリッド量子古典生成モデリングアルゴリズムの適用性に制限を課す。

関連論文リスト

• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [63.733312560668274]
  d可変RZゲートとG-dクリフォードゲートを含む量子回路を与えられた場合、学習者は純粋に古典的な推論を行い、その線形特性を効率的に予測できるだろうか? 我々は、d で線形にスケーリングするサンプルの複雑さが、小さな予測誤差を達成するのに十分であり、対応する計算の複雑さは d で指数関数的にスケールすることを証明する。 我々は,予測誤差と計算複雑性をトレードオフできるカーネルベースの学習モデルを考案し,多くの実践的な環境で指数関数からスケーリングへ移行した。
  論文  参考訳（メタデータ） (2024-08-22T08:21:28Z)
• On verifiable quantum advantage with peaked circuit sampling [9.551919087634522]
  このような回路から1/textpoly(n)$のピーク値を得るには、圧倒的な確率で$tau_p = Omega(tau_r/n)0.19)$が必要である。 また、このモデルでは非自明なピーク性も可能であるという数値的な証拠を与える。
  論文  参考訳（メタデータ） (2024-04-22T18:00:06Z)
• Learning shallow quantum circuits [7.411898489476803]
  未知の$n$-qubit浅量子回路$U$を学習するためのアルゴリズムを提案する。 また、未知の$n$-qubit状態$lvert psi rangle$の記述を学習するための古典的なアルゴリズムも提供する。 提案手法では,局所反転に基づく量子回路表現と,これらの逆変換を組み合わせた手法を用いる。
  論文  参考訳（メタデータ） (2024-01-18T16:05:00Z)
• Adaptive Circuit Learning of Born Machine: Towards Realization of Amplitude Embedding and Data Loading [7.88657961743755]
  本稿では,ACLBM(Adaptive Circuit Learning of Born Machine)という新しいアルゴリズムを提案する。 我々のアルゴリズムは、ターゲット状態に存在する複雑な絡み合いを最もよく捉える2ビットの絡み合いゲートを選択的に統合するように調整されている。 実験結果は、振幅埋め込みによる実世界のデータの符号化における我々のアプローチの習熟度を裏付けるものである。
  論文  参考訳（メタデータ） (2023-11-29T16:47:31Z)
• On the average-case complexity of learning output distributions of quantum circuits [55.37943886895049]
  統計的クエリモデルでは,ブロックワークランダムな量子回路の出力分布の学習は平均ケースハードであることが示されている。 この学習モデルは、ほとんどの一般的な学習アルゴリズムの抽象的な計算モデルとして広く利用されている。
  論文  参考訳（メタデータ） (2023-05-09T20:53:27Z)
• Quantum Extremal Learning [0.8937790536664091]
  本稿では,関数出力を極大化する隠れ関数への入力を見つける過程である「極大学習のための量子アルゴリズム」を提案する。 量子エクストリームラーニング(quantum extremal Learning, QEL)と呼ばれるこのアルゴリズムは、データ入力と出力の関係をモデル化するために変分訓練されたパラメトリック量子回路で構成されている。
  論文  参考訳（メタデータ） (2022-05-05T17:37:26Z)
• Learnability of the output distributions of local quantum circuits [53.17490581210575]
  2つの異なるオラクルモデルにおいて、量子回路Bornマシンの学習可能性について検討する。 我々はまず,超対数深度クリフォード回路の出力分布がサンプル効率良く学習できないという負の結果を示した。 より強力なオラクルモデル、すなわちサンプルに直接アクセスすると、局所的なクリフォード回路の出力分布は計算効率よくPACを学習可能であることを示す。
  論文  参考訳（メタデータ） (2021-10-11T18:00:20Z)
• Variational Quantum Optimization with Multi-Basis Encodings [62.72309460291971]
  マルチバスグラフ複雑性と非線形活性化関数の2つの革新の恩恵を受ける新しい変分量子アルゴリズムを導入する。 その結果,最適化性能が向上し,有効景観が2つ向上し,測定の進歩が減少した。
  論文  参考訳（メタデータ） (2021-06-24T20:16:02Z)
• Fixed Depth Hamiltonian Simulation via Cartan Decomposition [59.20417091220753]
  時間に依存しない深さの量子回路を生成するための構成的アルゴリズムを提案する。 一次元横フィールドXYモデルにおけるアンダーソン局在化を含む、モデルの特殊クラスに対するアルゴリズムを強調する。 幅広いスピンモデルとフェルミオンモデルに対して正確な回路を提供するのに加えて、我々のアルゴリズムは最適なハミルトニアンシミュレーションに関する幅広い解析的および数値的な洞察を提供する。
  論文  参考訳（メタデータ） (2021-04-01T19:06:00Z)

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

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