論文の概要: On the quantum computational complexity of classical linear dynamics with geometrically local interactions: Dequantization and universality

• arxiv url: http://arxiv.org/abs/2505.10445v1
• Date: Thu, 15 May 2025 16:06:22 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-16 22:29:06.402828
• Title: On the quantum computational complexity of classical linear dynamics with geometrically local interactions: Dequantization and universality
• Title（参考訳）: 幾何学的局所的相互作用を持つ古典線形力学の量子計算複雑性について:定式化と普遍性
• Authors: Kazuki Sakamoto, Keisuke Fujii,
• Abstract要約: 量子アルゴリズムは、古典力学と長距離相互作用をシミュレートする際、古典的アルゴリズムよりも指数的なスピードアップを提供する。 偏微分方程式から生じるような多くの実世界の古典系は局所的な相互作用しか示さない。 この研究は、偏微分方程式によって支配される古典力学の複雑さに関する新たな洞察を与える。
• 参考スコア（独自算出の注目度）: 0.9002260638342727
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The simulation of large-scale classical systems in exponentially small space on quantum computers has gained attention. The prior work demonstrated that a quantum algorithm offers an exponential speedup over any classical algorithm in simulating classical dynamics with long-range interactions. However, many real-world classical systems, such as those arising from partial differential equations, exhibit only local interactions. The question remains whether quantum algorithms can still provide exponential speedup under this condition. In this work, we thoroughly characterize the computational complexity of quantum algorithms for simulating such geometrically local systems. First, we dequantize the quantum algorithm for simulating short-time (polynomial-time) dynamics of such systems. This implies that the problem of simulating this dynamics does not yield any exponential quantum advantage. Second, we show that quantum algorithms for short-time dynamics have the same computational complexity as polynomial-time probabilistic classical computation. Third, we show that the computational complexity of quantum algorithms for long-time (exponential-time) dynamics is captured by exponential-time and polynomial-space quantum computation. This suggests a super-polynomial time advantage when restricting the computation to polynomial-space, or an exponential space advantage otherwise. This work offers new insights into the complexity of classical dynamics governed by partial differential equations, providing a pathway for achieving quantum advantage in practical problems.
• Abstract（参考訳）: 量子コンピュータ上の指数関数的に小さな空間における大規模古典システムのシミュレーションが注目されている。 以前の研究は、量子アルゴリズムが古典力学を長距離相互作用でシミュレートする際、古典的アルゴリズムよりも指数的なスピードアップを提供することを示した。 しかし、偏微分方程式から生じるような多くの実世界の古典系は局所的な相互作用しか示さない。 量子アルゴリズムがこの条件下で指数的なスピードアップを提供できるかどうかはまだ疑問が残る。 本研究では,そのような幾何学的局所系をシミュレートする量子アルゴリズムの計算複雑性を徹底的に特徴づける。 まず、このようなシステムの短時間(多項式時間)力学をシミュレーションするための量子アルゴリズムを定式化する。 これは、この力学をシミュレートする問題は指数量子上の優位性をもたらすものではないことを意味する。 第二に、短時間の力学に対する量子アルゴリズムは多項式時間確率的古典計算と同じ計算複雑性を持つことを示す。 第3に、時間的(指数的)動的量子論における量子アルゴリズムの計算複雑性は指数時間および多項式空間量子計算によって捉えられることを示す。 このことは、計算を多項式空間に制限する際の超多項式時間優位性や指数空間優位性を示唆している。 この研究は、偏微分方程式によって支配される古典力学の複雑さに関する新たな洞察を与え、実際的な問題において量子上の優位性を達成するための経路を提供する。

関連論文リスト

• An Efficient Classical Algorithm for Simulating Short Time 2D Quantum Dynamics [2.891413712995642]
  本稿では,2次元量子システムにおける短時間のダイナミクスをシミュレーションする,効率的な古典的アルゴリズムを提案する。 この結果から, 短時間2次元量子力学の複雑さに固有の単純さが明らかとなった。 この研究は、古典計算と量子計算の境界についての理解を深める。
  論文  参考訳（メタデータ） (2024-09-06T09:59:12Z)
• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [63.733312560668274]
  d可変RZゲートとG-dクリフォードゲートを含む量子回路を与えられた場合、学習者は純粋に古典的な推論を行い、その線形特性を効率的に予測できるだろうか? 我々は、d で線形にスケーリングするサンプルの複雑さが、小さな予測誤差を達成するのに十分であり、対応する計算の複雑さは d で指数関数的にスケールすることを証明する。 我々は,予測誤差と計算複雑性をトレードオフできるカーネルベースの学習モデルを考案し,多くの実践的な環境で指数関数からスケーリングへ移行した。
  論文  参考訳（メタデータ） (2024-08-22T08:21:28Z)
• Evaluation of phase shifts for non-relativistic elastic scattering using quantum computers [39.58317527488534]
  本研究は, 量子コンピュータ上での一般相対論的非弾性散乱過程の位相シフトを求めるアルゴリズムの開発を報告する。
  論文  参考訳（メタデータ） (2024-07-04T21:11:05Z)
• Solving reaction dynamics with quantum computing algorithms [42.408991654684876]
  線形応答によって支配される異なる反応を記述することに関連する応答関数の量子アルゴリズムについて検討する。 我々は原子核物理学の応用に焦点をあて、格子上の量子ビット効率のマッピングを検討し、現実的な散乱シミュレーションに必要な大量の量を効率的に表現することができる。
  論文  参考訳（メタデータ） (2024-03-30T00:21:46Z)
• Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
  我々は3つのハイブリッド量子k-Meansアルゴリズムを設計、実装、評価する。 我々は距離の計算を高速化するために量子現象を利用する。 我々は、我々のハイブリッド量子k-平均アルゴリズムが古典的バージョンよりも効率的であることを示す。
  論文  参考訳（メタデータ） (2022-12-13T16:04:16Z)
• Classical simulation of short-time quantum dynamics [0.0]
  局所観測可能量と非局所量のダイナミクスを近似する古典的アルゴリズムを提案する。 我々は、新しい量子速度限界、動的相転移の束縛、および製品状態の束縛された濃度を短期間に発展させた。
  論文  参考訳（メタデータ） (2022-10-20T18:00:04Z)
• Quantum algorithms for quantum dynamics: A performance study on the spin-boson model [68.8204255655161]
  量子力学シミュレーションのための量子アルゴリズムは、伝統的に時間進化作用素のトロッター近似の実装に基づいている。 変分量子アルゴリズムは欠かせない代替手段となり、現在のハードウェア上での小規模なシミュレーションを可能にしている。 量子ゲートコストが明らかに削減されているにもかかわらず、現在の実装における変分法は量子的優位性をもたらすことはありそうにない。
  論文  参考訳（メタデータ） (2021-08-09T18:00:05Z)
• Computational power of one- and two-dimensional dual-unitary quantum circuits [0.6946929968559495]
  古典的にシミュラブルな量子回路は、量子計算が古典的な計算より強力になったり、同等になったりすることを教えてくれます。 我々は、最近非平衡物理学の正確な解法モデルとして研究されているデュアルユニタリ量子回路(DUQC)を利用している。
  論文  参考訳（メタデータ） (2021-03-16T17:37:11Z)

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

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