論文の概要: Complexity of Quadratic Bosonic Hamiltonian Simulation: $\mathsf{BQP}$-Completeness and $\mathsf{PostBQP}$-Hardness

• arxiv url: http://arxiv.org/abs/2603.26561v1
• Date: Fri, 27 Mar 2026 16:25:41 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-30 21:49:48.587569
• Title: Complexity of Quadratic Bosonic Hamiltonian Simulation: $\mathsf{BQP}$-Completeness and $\mathsf{PostBQP}$-Hardness
• Title（参考訳）: 二次ボソニックハミルトニアンシミュレーションの複雑さ:$\mathsf{BQP}$-完全性と$\mathsf{PostBQP}$-ハードネス
• Authors: Lilith Zschetzsche, Refik Mansuroğlu, Norbert Schuch,
• Abstract要約: 二次ボゾン問題の幅広いクラスを導入し、それらが$mathsfBQP$-completeであることが証明する。 上記のクラスをさらに一般の二次ハミルトン群に拡張すると、$mathsfPostBQP$-hard問題が発生することを示す。 これは、量子コンピュータ上の大きな量子システムをシミュレートする複雑さの急激な遷移と、古典的および量子コンピュータにおけるシミュレーションの複雑さの差を明らかにしている。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The computational complexity of simulating the dynamics of physical quantum systems is a central question at the interface of quantum physics and computer science. In this work, we address this question for the simulation of exponentially large bosonic Hamiltonians with quadratic interactions. We present two results: First, we introduce a broad class of quadratic bosonic problems for which we prove that they are $\mathsf{BQP}$-complete. Importantly, this class includes two known $\mathsf{BQP}$-complete problems as special cases: Classical oscillator networks and continuous-time quantum walks. Second, we show that extending the aforementioned class to even more general quadratic Hamiltonians results in a $\mathsf{PostBQP}$-hard problem. This reveals a sharp transition in the complexity of simulating large quantum systems on a quantum computer, as well as in the difference in complexity between their simulation on classical and quantum computers.
• Abstract（参考訳）: 物理量子系の力学をシミュレートする計算複雑性は、量子物理学と計算機科学のインターフェースにおける中心的な問題である。 本研究では,2次相互作用を持つ指数関数的に大きなボソニックハミルトニアンのシミュレーションについて,この問題に対処する。 まず、これらが$\mathsf{BQP}$-完全であることを証明した2次ボゾン問題の幅広いクラスを導入する。 重要なことに、このクラスは特殊ケースとして既知の $\mathsf{BQP}$完全問題:古典振動子ネットワークと連続時間量子ウォークを含む。 次に、上記のクラスをより一般の二次ハミルトン群に拡張すると、$\mathsf{PostBQP}$-hard問題が発生することを示す。 これは、量子コンピュータ上の大きな量子システムをシミュレートする複雑さの急激な遷移と、古典的および量子コンピュータにおけるシミュレーションの複雑さの差を明らかにしている。

関連論文リスト

• Quantum simulation of massive Thirring and Gross--Neveu models for arbitrary number of flavors [40.72140849821964]
  我々は、任意の数のフェルミオンフレーバーを持つ巨大なThiringとGross-Neveuモデルを、大きさ$L$の空間1次元格子上で離散化した$N_f$と考えている。 我々は、N_f = 1,2,3,4$の20キュービットまでのシステムサイズに優れた忠実度を持つ両モデルの基底状態を作成する。 我々の研究は、大規模なN_f$フェルミオン量子場理論モデルのリアルタイムダイナミクスの量子シミュレーションに向けた具体的なステップである。
  論文  参考訳（メタデータ） (2026-02-25T19:00:01Z)
• On the Complexity of Decoded Quantum Interferometry [39.951444958798014]
  最近提案された近似最適化のための量子アルゴリズムであるDecoded Quantum Interferometry (DQI) の複雑さについて検討した。 我々は、DQIは古典的なシミュレートが困難であり、その硬さは指数関数的に大きな隠れ部分集合を見つけることから生じると論じる。
  論文  参考訳（メタデータ） (2025-09-17T21:31:58Z)
• Quantum algorithms based on quantum trajectories [0.4870012761464388]
  O(T + log(1/epsilon))$ の加法的複雑性はリンドブラディアンの大規模なクラスのシミュレーションに到達可能であることを示す。 この研究で、量子軌道に基づく新しい量子アルゴリズムを構築することにより、Lindbladianの大規模クラスのシミュレーションに$O(T + log(1/epsilon))$の加法的複雑性が到達可能であることを示す。
  論文  参考訳（メタデータ） (2025-09-12T17:27:25Z)
• Improved separation between quantum and classical computers for sampling and functional tasks [3.618534280726541]
  本稿では、量子コンピュータが古典的コンピュータを超えた計算が可能であるという既存の証拠をさらに強調する。 i)ポストセレクションを持つ量子コンピュータは、ポストセレクションを持つ古典的コンピュータと同じくらい強力である。 正確な数え上げオラクルで解ける問題と近似数え上げオラクルで解ける問題の間に同値性が存在すると証明すると、階層構造はその第2レベルに崩壊する。
  論文  参考訳（メタデータ） (2024-10-28T11:30:10Z)
• Quantum Algorithms in a Superposition of Spacetimes [5.475280561991127]
  量子コンピュータは私たちの情報処理能力に革命をもたらすと期待されている。 量子重力(QG)に基づく自然計算モデルの最初の例を示す。 量子コンピュータは,計算機科学の基本的な2つの問題を時間内に解くことができることを示す。
  論文  参考訳（メタデータ） (2024-03-05T13:05:07Z)
• Quantum Depth in the Random Oracle Model [57.663890114335736]
  浅量子回路の計算能力と古典計算の組合せを包括的に評価する。 いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
  論文  参考訳（メタデータ） (2022-10-12T17:54:02Z)
• Oracle separations of hybrid quantum-classical circuits [68.96380145211093]
  量子計算の2つのモデル: CQ_dとQC_d。 CQ_dは、d-d-deepth量子コンピュータのシナリオを何度も捉え、QC_dは測定ベースの量子計算に類似している。 CQ_dとQC_dの類似性にもかかわらず、2つのモデルは本質的にはCQ_d $nsubseteq$QC_dとQC_d $nsubseteq$CQ_dである。
  論文  参考訳（メタデータ） (2022-01-06T03:10:53Z)
• An Algebraic Quantum Circuit Compression Algorithm for Hamiltonian Simulation [55.41644538483948]
  現在の世代のノイズの多い中間スケール量子コンピュータ(NISQ)は、チップサイズとエラー率に大きく制限されている。 我々は、自由フェルミオンとして知られる特定のスピンハミルトニアンをシミュレーションするために、量子回路を効率よく圧縮するために局所化回路変換を導出する。 提案した数値回路圧縮アルゴリズムは、後方安定に動作し、$mathcalO(103)$スピンを超える回路合成を可能にするスピンの数で3次スケールする。
  論文  参考訳（メタデータ） (2021-08-06T19:38:03Z)
• Long-Time Error-Mitigating Simulation of Open Quantum Systems on Near Term Quantum Computers [38.860468003121404]
  本研究では,最大2千個のエンタングゲートを含むディープ回路においても,ハードウェアエラーに対する堅牢性を示す量子ハードウェア上でのオープン量子システムシミュレーションについて検討する。 我々は, 無限の熱浴に結合した2つの電子系をシミュレートする: 1) 駆動電界における放散自由電子系, 2) 磁場中の単一軌道における2つの相互作用電子の熱化 - ハバード原子。 この結果から, 開放量子系シミュレーションアルゴリズムは, ノイズの多いハードウェア上で, 同様に複雑な非散逸性アルゴリズムをはるかに上回ることができることを示した。
  論文  参考訳（メタデータ） (2021-08-02T21:36:37Z)
• Computational power of one- and two-dimensional dual-unitary quantum circuits [0.6946929968559495]
  古典的にシミュラブルな量子回路は、量子計算が古典的な計算より強力になったり、同等になったりすることを教えてくれます。 我々は、最近非平衡物理学の正確な解法モデルとして研究されているデュアルユニタリ量子回路(DUQC)を利用している。
  論文  参考訳（メタデータ） (2021-03-16T17:37:11Z)

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

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