論文の概要: Bosonic Quantum Computational Complexity
- arxiv url: http://arxiv.org/abs/2410.04274v1
- Date: Sat, 5 Oct 2024 19:43:41 GMT
- ステータス: 処理完了
- システム内更新日: 2024-11-02 08:49:52.157793
- Title: Bosonic Quantum Computational Complexity
- Title（参考訳）: Bosonic Quantum Computational Complexity
- Authors: Ulysse Chabaud, Michael Joseph, Saeed Mehraban, Arsalan Motamedi,
- Abstract要約: 私たちはそのような研究計画の基礎をつくった。
本稿では,BQPのボゾン一般化に基づく自然複雑性クラスと問題を紹介する。
ボソニックハミルトニアンのスペクトルの有界性を決定する問題はコ-NPハードであることを示す。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Quantum computing involving physical systems with continuous degrees of freedom, such as the quantum states of light, has recently attracted significant interest. However, a well-defined quantum complexity theory for these bosonic computations over infinite-dimensional Hilbert spaces is missing. In this work, we lay foundations for such a research program. We introduce natural complexity classes and problems based on bosonic generalizations of BQP, the local Hamiltonian problem, and QMA. We uncover several relationships and subtle differences between standard Boolean classical and discrete variable quantum complexity classes and identify outstanding open problems. In particular: 1. We show that the power of quadratic (Gaussian) quantum dynamics is equivalent to the class BQL. More generally, we define classes of continuous-variable quantum polynomial time computations with a bounded probability of error based on higher-degree gates. Due to the infinite dimensional Hilbert space, it is not a priori clear whether a decidable upper bound can be obtained for these classes. We identify complete problems for these classes and demonstrate a BQP lower and EXPSPACE upper bound. We further show that the problem of computing expectation values of polynomial bosonic observables is in PSPACE. 2. We prove that the problem of deciding the boundedness of the spectrum of a bosonic Hamiltonian is co-NP-hard. Furthermore, we show that the problem of finding the minimum energy of a bosonic Hamiltonian critically depends on the non-Gaussian stellar rank of the family of energy-constrained states one optimizes over: for constant stellar rank, it is NP-complete; for polynomially-bounded rank, it is in QMA; for unbounded rank, it is undecidable.
- Abstract（参考訳）: 光の量子状態のような連続的な自由度を持つ物理系を含む量子コンピューティングは、最近大きな関心を集めている。
しかし、無限次元ヒルベルト空間上のこれらのボソニック計算に対するよく定義された量子複雑性理論は欠落している。
本研究では,このような研究プログラムの基礎を定めている。
自然複雑性クラスとBQP, 局所ハミルトン問題, およびQMAのボゾン一般化に基づく問題を導入する。
標準ブール古典および離散変数量子複雑性クラス間のいくつかの関係と微妙な違いを発見し、顕著な開問題を特定する。
特に、 1. 二次(ガウス)量子力学のパワーはクラス BQL と同値であることを示す。
より一般に、高次ゲートに基づく誤差の有界確率を持つ連続変数量子多項式時間計算のクラスを定義する。
無限次元ヒルベルト空間(英語版)により、これらのクラスに対して決定可能な上界が得られうるかどうかが事前に明らかでない。
これらのクラスに対する完全な問題を特定し、BQPを低く、EXPSPACEを上界に示す。
さらに,多項式ボソニックオブザーバブルの期待値の計算問題はPSPACEにあることを示す。
2. ボゾンハミルトニアンのスペクトルの有界性を決定する問題はコ-NPハードであることを示す。
さらに、ボゾンハミルトニアンの最小エネルギーを求める問題は、エネルギー制約状態の族(英語版)の非ガウス星級数(英語版)(non-Gaussian stellar rank of the family of energy-constrained states)に大きく依存していることが示される: 一定の星位の場合、NP完全である; 多項式有界ランクの場合、QMAであり、非有界ランクの場合、決定不可能である。
関連論文リスト
- A Dequantized Algorithm for the Guided Local Hamiltonian Problem [2.891413712995642]
誘導局所ハミルトニアン問題(GLH)は量子コンピュータ上で効率よく解くことができ、BQP完全であることが証明されている。
これにより、GLH問題は古典計算と量子計算の基本的な分離を探求するための貴重なフレームワークとなる。
ランダム化量子想像時間進化量子アルゴリズムの量子化古典アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-11-25T07:38:16Z) - The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
非負の振幅を持つ非絡み合った量子証明のパワー、つまり $textQMA+(2)$ を表すクラスについて研究する。
特に,小集合拡張,ユニークなゲーム,PCP検証のためのグローバルプロトコルを設計する。
QMA(2) が $textQMA+(2)$ に等しいことを示す。
論文 参考訳（メタデータ） (2024-02-29T01:35:46Z) - Quantum Merlin-Arthur proof systems for synthesizing quantum states [0.0]
クラスNP合成における状態合成法について検討した。
我々は、最も自然な候補者の1つであるUQMA目撃者の家族が国家QMAであることを確認した。
状態QCMAが完全性を達成することを実証する。
論文 参考訳（メタデータ） (2023-03-03T12:14:07Z) - Hamiltonian variational ansatz without barren plateaus [0.0]
変分量子アルゴリズムは、短期量子コンピュータの最も有望な応用の1つである。
その大きな可能性にもかかわらず、数十量子ビットを超える変分量子アルゴリズムの有用性は疑問視されている。
論文 参考訳（メタデータ） (2023-02-16T19:01:26Z) - Optimal lower bounds for Quantum Learning via Information Theory [3.093890460224435]
我々は、PACとモデルの両方において、情報理論的アプローチにより、量子サンプルの複雑さに対して最適な下界を導出する。
次に、確率論から古典的な問題であるクーポンコレクタ問題(英語版)の量子アナログに目を向ける。
量子クーポンコレクター問題のすべての側面は、関連するグラム行列のスペクトルの性質について研究する。
論文 参考訳（メタデータ） (2023-01-05T18:55:04Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - Complexity-Theoretic Limitations on Quantum Algorithms for Topological
Data Analysis [59.545114016224254]
トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。
我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。
我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
論文 参考訳（メタデータ） (2022-09-28T17:53:25Z) - Theory of Quantum Generative Learning Models with Maximum Mean
Discrepancy [67.02951777522547]
量子回路ボルンマシン(QCBM)と量子生成逆ネットワーク(QGAN)の学習可能性について検討する。
まず、QCBMの一般化能力を解析し、量子デバイスがターゲット分布に直接アクセスできる際の優位性を同定する。
次に、QGANの一般化誤差境界が、採用されるAnsatz、クォーディットの数、入力状態に依存することを示す。
論文 参考訳（メタデータ） (2022-05-10T08:05:59Z) - Experimental violations of Leggett-Garg's inequalities on a quantum
computer [77.34726150561087]
単一および多ビット系におけるLeggett-Garg-Bellの不等式違反を実験的に観察する。
本分析では, 量子プラットフォームの限界に注目し, 上記の相関関数は, 量子ビットの数や回路深さが大きくなるにつれて, 理論的予測から逸脱することを示した。
論文 参考訳（メタデータ） (2021-09-06T14:35:15Z) - Limits of quantum speed-ups for computational geometry and other
problems: Fine-grained complexity via quantum walks [0.0]
いくつかの計算問題に対して、量子アルゴリズムの時間的複雑さを最適に下界として証明する。
我々の下界のほとんどは、既知の上界と一致しているため、量子スピードアップに厳しい制限が課せられるため、最適である。
論文 参考訳（メタデータ） (2021-06-03T17:22:08Z) - The principle of majorization: application to random quantum circuits [68.8204255655161]
i) 普遍的、ii) 古典的シミュラブル、iii) 普遍的、古典的シミュラブルの3つのクラスが考慮された。
回路のすべての族が平均的に正規化の原理を満たすことを検証した。
明らかな違いは、状態に関連したローレンツ曲線のゆらぎに現れる。
論文 参考訳（メタデータ） (2021-02-19T16:07:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。