論文の概要: Clifford Circuits can be Properly PAC Learned if and only if
$\textsf{RP}=\textsf{NP}$
- arxiv url: http://arxiv.org/abs/2204.06638v4
- Date: Tue, 6 Jun 2023 00:15:47 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-08 00:01:29.440732
- Title: Clifford Circuits can be Properly PAC Learned if and only if
$\textsf{RP}=\textsf{NP}$
- Title（参考訳）: clifford回路は、$\textsf{rp}=\textsf{np}$の場合のみ、適切なpac学習が可能である。
- Authors: Daniel Liang
- Abstract要約: クラフォード回路の適切な学習は、textsfRP = textsfNP$ がなければ古典的な学習者にとって困難であることを示す。
また,$textsfNP subseteq textsfRQP$。
- 参考スコア（独自算出の注目度）: 1.14219428942199
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Given a dataset of input states, measurements, and probabilities, is it
possible to efficiently predict the measurement probabilities associated with a
quantum circuit? Recent work of Caro and Datta (2020) studied the problem of
PAC learning quantum circuits in an information theoretic sense, leaving open
questions of computational efficiency. In particular, one candidate class of
circuits for which an efficient learner might have been possible was that of
Clifford circuits, since the corresponding set of states generated by such
circuits, called stabilizer states, are known to be efficiently PAC learnable
(Rocchetto 2018). Here we provide a negative result, showing that proper
learning of CNOT circuits is hard for classical learners unless $\textsf{RP} =
\textsf{NP}$. As the classical analogue and subset of Clifford circuits, this
naturally leads to a hardness result for Clifford circuits as well.
Additionally, we show that if $\textsf{RP} = \textsf{NP}$ then there would
exist efficient proper learning algorithms for CNOT and Clifford circuits. By
similar arguments, we also find that an efficient proper quantum learner for
such circuits exists if and only if $\textsf{NP} \subseteq \textsf{RQP}$.
- Abstract（参考訳）: 入力状態、測定、確率のデータセットを考えると、量子回路に関連する測定確率を効率的に予測することは可能か?
Caro and Datta (2020) の最近の研究は、情報理論的な意味でPAC学習量子回路の問題を研究し、計算効率に関するオープンな疑問を残した。
特に、効率的な学習が可能な回路の候補クラスはクリフォード回路であり、そのような回路によって生成される対応する状態の集合は安定化状態と呼ばれ、効率的にpac学習可能であることが知られている(rocchetto 2018)。
ここでは、CNOT回路の適切な学習が、$\textsf{RP} = \textsf{NP}$でない限り、古典的な学習者にとって難しいことを示す。
古典的なクリフォード回路のアナログと部分集合として、これはクリフォード回路の硬度結果にも自然に導かれる。
さらに、$\textsf{RP} = \textsf{NP}$ であれば、CNOT と Clifford 回路に対して効率的な適切な学習アルゴリズムが存在することを示す。
同様の議論により、そのような回路に対する効率的な固有量子学習器が存在するのは、$\textsf{NP} \subseteq \textsf{RQP}$である。
関連論文リスト
- Polynomial-Time Classical Simulation of Noisy Circuits with Naturally Fault-Tolerant Gates [0.22499166814992438]
現実的にノイズの多いクリフォード回路を持つ大深度での量子的優位性は存在しないことを示す。
このアルゴリズムの背後にある重要な洞察は、分散ノイズが長距離の絡み合いの崩壊を引き起こすことである。
この結果を証明するため、パーコレーション理論の手法とパウリ経路解析のツールを融合する。
論文 参考訳（メタデータ） (2024-11-04T19:11:58Z) - Learning shallow quantum circuits [7.411898489476803]
未知の$n$-qubit浅量子回路$U$を学習するためのアルゴリズムを提案する。
また、未知の$n$-qubit状態$lvert psi rangle$の記述を学習するための古典的なアルゴリズムも提供する。
提案手法では,局所反転に基づく量子回路表現と,これらの逆変換を組み合わせた手法を用いる。
論文 参考訳（メタデータ） (2024-01-18T16:05:00Z) - On the Pauli Spectrum of QAC0 [2.3436632098950456]
我々は、$mathsfQAC0$のパウリスペクトルが低度濃度を満たすと推測する。
我々は新しい回路の低境界と学習結果を応用として得る。
論文 参考訳（メタデータ） (2023-11-16T07:25:06Z) - Simulation of IBM's kicked Ising experiment with Projected Entangled
Pair Operator [71.10376783074766]
我々は最近,誤りを軽減した量子回路を用いてエミュレートされた127量子ビットキックド・イジングモデルの古典的シミュレーションを行った。
提案手法はハイゼンベルク図の射影的絡み合ったペア作用素(PEPO)に基づいている。
我々はクリフォード展開理論を開発し、正確な期待値を計算し、それらをアルゴリズムの評価に利用する。
論文 参考訳（メタデータ） (2023-08-06T10:24:23Z) - On the average-case complexity of learning output distributions of
quantum circuits [55.37943886895049]
統計的クエリモデルでは,ブロックワークランダムな量子回路の出力分布の学習は平均ケースハードであることが示されている。
この学習モデルは、ほとんどの一般的な学習アルゴリズムの抽象的な計算モデルとして広く利用されている。
論文 参考訳（メタデータ） (2023-05-09T20:53:27Z) - Learning efficient decoders for quasi-chaotic quantum scramblers [3.823356975862005]
我々は,スクランブラーの知識がなくても,スクランブラー情報の検索が可能であることを示す。
古典デコーダは、ランダムなユニタリによってスクランブルされた情報の1つを忠実に検索することができる。
結果は古典的な形で量子ユニタリの正則性を学ぶことができることを示している。
論文 参考訳（メタデータ） (2022-12-21T20:19:53Z) - Quantum Depth in the Random Oracle Model [57.663890114335736]
浅量子回路の計算能力と古典計算の組合せを包括的に評価する。
いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
論文 参考訳（メタデータ） (2022-10-12T17:54:02Z) - A single $T$-gate makes distribution learning hard [56.045224655472865]
この研究は、局所量子回路の出力分布の学習可能性に関する広範な評価を提供する。
ハイブリッド量子古典アルゴリズムを含む多種多様な学習アルゴリズムにおいて、深度$d=omega(log(n))$ Clifford回路に関連する生成的モデリング問題さえも困難であることを示す。
論文 参考訳（メタデータ） (2022-07-07T08:04:15Z) - Learning quantum circuits of some $T$ gates [10.609715843964263]
クリフォード群以外の回路を扱う方法は不明である。
本稿では,$T$-depth 1回路の出力状態が,フルT$-rankを安定化器擬似混合器で表すことができることを示す。
論文 参考訳（メタデータ） (2021-06-23T16:43:01Z) - On the realistic worst case analysis of quantum arithmetic circuits [69.43216268165402]
量子回路の設計における直観は誤解を招く可能性があることを示す。
また,T数を減らすことで,全深度を増大させることができることを示した。
リップルキャリーを用いた加算回路と乗算回路について述べる。
論文 参考訳（メタデータ） (2021-01-12T21:36:16Z) - Machine Learning Optimization of Quantum Circuit Layouts [63.55764634492974]
本稿では量子回路マッピングQXXとその機械学習バージョンQXX-MLPを紹介する。
後者は、レイアウトされた回路の深さが小さくなるように最適なQXXパラメータ値を自動的に推論する。
近似を用いてレイアウト法を学習可能な経験的証拠を提示する。
論文 参考訳（メタデータ） (2020-07-29T05:26:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。