論文の概要: Computational Complexity of Learning Efficiently Generatable Pure States
- arxiv url: http://arxiv.org/abs/2410.04373v1
- Date: Sun, 6 Oct 2024 06:25:36 GMT
- ステータス: 処理完了
- システム内更新日: 2024-11-02 08:10:32.595131
- Title: Computational Complexity of Learning Efficiently Generatable Pure States
- Title（参考訳）: 学習効率の良い生成可能な純状態の計算複雑性
- Authors: Taiga Hiroka, Min-Hsiu Hsieh,
- Abstract要約: 量子状態学習の計算複雑性について検討する。
未知の量子状態が純粋な状態であることを約束し、効率的に生成可能であるならば、量子時間アルゴリズムが存在することを示す。
また、学習量子状態の硬さと量子暗号の関連性も観察する。
- 参考スコア（独自算出の注目度）: 11.180439223883962
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Understanding the computational complexity of learning efficient classical programs in various learning models has been a fundamental and important question in classical computational learning theory. In this work, we study the computational complexity of quantum state learning, which can be seen as a quantum generalization of distributional learning introduced by Kearns et.al [STOC94]. Previous works by Chung and Lin [TQC21], and B\u{a}descu and O$'$Donnell [STOC21] study the sample complexity of the quantum state learning and show that polynomial copies are sufficient if unknown quantum states are promised efficiently generatable. However, their algorithms are inefficient, and the computational complexity of this learning problem remains unresolved. In this work, we study the computational complexity of quantum state learning when the states are promised to be efficiently generatable. We show that if unknown quantum states are promised to be pure states and efficiently generateable, then there exists a quantum polynomial time algorithm $A$ and a language $L \in PP$ such that $A^L$ can learn its classical description. We also observe the connection between the hardness of learning quantum states and quantum cryptography. We show that the existence of one-way state generators with pure state outputs is equivalent to the average-case hardness of learning pure states. Additionally, we show that the existence of EFI implies the average-case hardness of learning mixed states.
- Abstract（参考訳）: 様々な学習モデルにおける学習効率のよい古典的プログラムの計算複雑性を理解することは、古典的学習理論において基礎的で重要な問題である。
本研究では,Kearnsらによって導入された分散学習の量子一般化として見ることができる量子状態学習の計算複雑性について検討する。
Chung と Lin [TQC21] と B\u{a}descu と O$'$Donnell [STOC21] による以前の研究は、量子状態学習のサンプルの複雑さを研究し、未知の量子状態が効率的に生成可能であれば多項式コピーが十分であることを示した。
しかし、アルゴリズムは非効率であり、この学習問題の計算複雑性は未解決のままである。
本研究では、状態が効率的に生成可能であることを約束する量子状態学習の計算複雑性について検討する。
未知の量子状態が純粋状態であることを約束し、効率的に生成可能であるなら、量子多項式時間アルゴリズム$A$と言語$L \in PP$が存在して、$A^L$はその古典的な記述を学べることを示す。
また、学習量子状態の硬さと量子暗号の関連性も観察する。
純粋な状態出力を持つ一方通行状態生成器の存在は、学習純状態の平均ケース硬度と等価であることを示す。
さらに、EFIの存在は、混合状態の学習における平均的なケース硬さを意味することを示す。
関連論文リスト
- Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [63.733312560668274]
d可変RZゲートとG-dクリフォードゲートを含む量子回路を与えられた場合、学習者は純粋に古典的な推論を行い、その線形特性を効率的に予測できるだろうか?
我々は、d で線形にスケーリングするサンプルの複雑さが、小さな予測誤差を達成するのに十分であり、対応する計算の複雑さは d で指数関数的にスケールすることを証明する。
我々は,予測誤差と計算複雑性をトレードオフできるカーネルベースの学習モデルを考案し,多くの実践的な環境で指数関数からスケーリングへ移行した。
論文 参考訳（メタデータ） (2024-08-22T08:21:28Z) - Efficient learning of quantum states prepared with few fermionic non-Gaussian gates [0.0]
ガウスゲートの任意の数で用意された$n$フェルミオンモード上での学習状態の効率的なアルゴリズムを提案する。
我々の研究は、ガウス門をほとんど持たない状態の構造に光を当て、回路の複雑さを改良した上界を提供する。
論文 参考訳（メタデータ） (2024-02-28T19:18:27Z) - Learning quantum states and unitaries of bounded gate complexity [2.034135396070497]
我々は、G$2量子ビットゲートを持つ量子回路によって生成された状態を微量なトレース距離に学習するには、G$で線形にスケールするサンプル複雑性が必要であることを証明した。
また、$G$ゲートによって生成されるユニタリを、小さな平均ケースエラーに対して線形に$G$で学習するのに最適なクエリの複雑さが証明される。
論文 参考訳（メタデータ） (2023-10-30T18:00:03Z) - Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
我々は3つのハイブリッド量子k-Meansアルゴリズムを設計、実装、評価する。
我々は距離の計算を高速化するために量子現象を利用する。
我々は、我々のハイブリッド量子k-平均アルゴリズムが古典的バージョンよりも効率的であることを示す。
論文 参考訳（メタデータ） (2022-12-13T16:04:16Z) - A single $T$-gate makes distribution learning hard [56.045224655472865]
この研究は、局所量子回路の出力分布の学習可能性に関する広範な評価を提供する。
ハイブリッド量子古典アルゴリズムを含む多種多様な学習アルゴリズムにおいて、深度$d=omega(log(n))$ Clifford回路に関連する生成的モデリング問題さえも困難であることを示す。
論文 参考訳（メタデータ） (2022-07-07T08:04:15Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳（メタデータ） (2022-05-26T20:32:36Z) - Revisiting dequantization and quantum advantage in learning tasks [3.265773263570237]
サンプルとクエリ(SQ)アクセスを持つ古典的アルゴリズムは量子状態入力を持つ量子アルゴリズムよりも指数関数的に高速に学習タスクを実現できることを示す。
これらの結果から,SQアクセスが量子状態入力に対して強すぎるため,指数的量子優位性が欠如していることが示唆された。
論文 参考訳（メタデータ） (2021-12-01T20:05:56Z) - On exploring the potential of quantum auto-encoder for learning quantum systems [60.909817434753315]
そこで我々は,古典的な3つのハードラーニング問題に対処するために,QAEに基づく効果的な3つの学習プロトコルを考案した。
私たちの研究は、ハード量子物理学と量子情報処理タスクを達成するための高度な量子学習アルゴリズムの開発に新たな光を当てています。
論文 参考訳（メタデータ） (2021-06-29T14:01:40Z) - Density functionals and Kohn-Sham potentials with minimal wavefunction
preparations on a quantum computer [0.0]
量子コンピュータの潜在的な応用の1つは、量子化学システムを解くことである。
本稿では,十分に強力な量子コンピュータから,機械学習モデルとしての正確な機能を得る方法を示す。
論文 参考訳（メタデータ） (2020-08-12T22:50:39Z) - Characterization of quantum states based on creation complexity [0.0]
量子状態の生成複雑性は、基本初期状態から生成するために必要な基本ゲートの最小数である。
完全に一般の量子状態が指数関数的に困難であること(生成の複雑さを判断するためには、指数関数的に量子ビットの個数と指数関数的にスケールするいくつかのステップが要求される)を示す。
次に、生成複雑性の大きい大規模な量子状態が、任意の候補量子状態が与えられたとき、そのクラスに属するか否かを任意に高い成功確率で決定するための効率的な係数サンプリング手順を設計できるような共通の係数特徴を持つことを示す。
論文 参考訳（メタデータ） (2020-04-28T21:12:45Z) - Quantum Gram-Schmidt Processes and Their Application to Efficient State
Read-out for Quantum Algorithms [87.04438831673063]
本稿では、生成した状態の古典的ベクトル形式を生成する効率的な読み出しプロトコルを提案する。
我々のプロトコルは、出力状態が入力行列の行空間にある場合に適合する。
我々の技術ツールの1つは、Gram-Schmidt正則手順を実行するための効率的な量子アルゴリズムである。
論文 参考訳（メタデータ） (2020-04-14T11:05:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。