論文の概要: 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 estimation of trainability for variational quantum circuits [58.09028887465797]
変分量子回路は、よく知られたバレンプラトーの呪いに悩まされる。
変動量子回路のコスト関数とその分散を効率よく計算する方法を見出した。
論文 参考訳(メタデータ) (2023-02-09T14:05:18Z) - Riemannian quantum circuit optimization for Hamiltonian simulation [2.7893127028447813]
ハミルトンシミュレーションは量子コンピューティングの自然な応用である。
翻訳不変系では、そのような回路トポロジのゲートは古典的なコンピュータでさらに最適化することができる。
一次元格子上のイジングとハイゼンベルクのモデルに対して、我々は桁違いの精度の向上を達成する。
論文 参考訳(メタデータ) (2022-12-15T00:00:17Z) - Structure Learning of Quantum Embeddings [68.8204255655161]
最適化手法により最適な量子埋め込みを自動的に選択するアルゴリズムを提案する。
我々は、我々のアプローチの性能向上を示すために、人工データセットと実世界のデータセットの両方を使用しました。
論文 参考訳(メタデータ) (2022-09-22T16:42:14Z) - A Quantum Algorithm for Computing All Diagnoses of a Switching Circuit [73.70667578066775]
ほとんどの人造システム、特にコンピュータは決定論的に機能する。
本稿では、量子物理学が確率法則に従うときの直観的なアプローチである量子情報理論による接続を提供する。
論文 参考訳(メタデータ) (2022-09-08T17:55:30Z) - Quantum Extremal Learning [0.8937790536664091]
本稿では,関数出力を極大化する隠れ関数への入力を見つける過程である「極大学習のための量子アルゴリズム」を提案する。
量子エクストリームラーニング(quantum extremal Learning, QEL)と呼ばれるこのアルゴリズムは、データ入力と出力の関係をモデル化するために変分訓練されたパラメトリック量子回路で構成されている。
論文 参考訳(メタデータ) (2022-05-05T17:37:26Z) - Limitations of variational quantum algorithms: a quantum optimal
transport approach [11.202435939275675]
我々は、ノイズとノイズレスの両体制において、標準NISQ提案の極めて厳密な境界を得る。
境界は、QAOAのような両方の回路モデルアルゴリズムと、量子アニールのような連続時間アルゴリズムの性能を制限する。
論文 参考訳(メタデータ) (2022-04-07T13:58:44Z) - The complexity of quantum support vector machines [3.8998241153792454]
量子サポートベクトルマシンは、カーネル関数を定義するために量子回路を使用する。
我々は、カーネル化された原始問題は、ペガソスと呼ばれる既知の古典的アルゴリズムの一般化を用いて、$mathcalO(min M2, varepsilon6, 1/varepsilon10 )$評価で解けるという経験的な仮定の下で証明する。
論文 参考訳(メタデータ) (2022-02-28T19:01:17Z) - Learnability of the output distributions of local quantum circuits [53.17490581210575]
2つの異なるオラクルモデルにおいて、量子回路Bornマシンの学習可能性について検討する。
我々はまず,超対数深度クリフォード回路の出力分布がサンプル効率良く学習できないという負の結果を示した。
より強力なオラクルモデル、すなわちサンプルに直接アクセスすると、局所的なクリフォード回路の出力分布は計算効率よくPACを学習可能であることを示す。
論文 参考訳(メタデータ) (2021-10-11T18:00:20Z) - A quantum algorithm for training wide and deep classical neural networks [72.2614468437919]
勾配勾配勾配による古典的トレーサビリティに寄与する条件は、量子線形系を効率的に解くために必要な条件と一致することを示す。
MNIST画像データセットがそのような条件を満たすことを数値的に示す。
我々は、プールを用いた畳み込みニューラルネットワークのトレーニングに$O(log n)$の実証的証拠を提供する。
論文 参考訳(メタデータ) (2021-07-19T23:41:03Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。