論文の概要: Quantum Time-Space Tradeoffs for Exponential Dynamic Programming

• arxiv url: http://arxiv.org/abs/2604.02233v1
• Date: Thu, 02 Apr 2026 16:28:18 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-03 14:21:10.916303
• Title: Quantum Time-Space Tradeoffs for Exponential Dynamic Programming
• Title（参考訳）: 指数動的プログラミングのための量子時間空間トレードオフ
• Authors: Susanna Caroppo, Jevgēnijs Vihrovs, Dārta Zajakina, Aleksejs Zajakins,
• Abstract要約: 従来のアルゴリズムよりもスピードアップを維持しながら、時間的に取引することで、空間の複雑さを改善する方法について検討する。 これらのアルゴリズムのパラメータを調整し、「量子化」古典戦略と組み合わせることで得られる新しい量子時空間トレードオフを示す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We investigate the quantum algorithms for dynamic programming by Ambainis et al. (SODA'19). While giving provable complexity speedups and applicable to a variety of NP-hard problems, these algorithms have a notable drawback: they require a large amount of Quantum Random Access Memory (QRAM), which potentially could be very challenging to implement in a physical quantum computer. In this work, we study how we can improve the space complexity by trading it for time, while still retaining a speedup over the classical algorithms. We show novel quantum time-space tradeoffs, which we obtain by adjusting the parameters of these algorithms and combining them with "quantized" classical strategies.
• Abstract（参考訳）: 本稿では,Ambainis et al (SODA'19) による動的プログラミングの量子アルゴリズムについて検討する。 証明可能な複雑性のスピードアップを提供し、様々なNPハード問題に適用できる一方で、これらのアルゴリズムには大きな量子ランダムアクセスメモリ(QRAM)を必要とするという大きな欠点がある。 本研究では,従来のアルゴリズムの高速化を保ちながら,時間的トレーディングによって空間の複雑さを改善する方法について検討する。 これらのアルゴリズムのパラメータを調整し、「量子化」古典戦略と組み合わせることで得られる新しい量子時空間トレードオフを示す。

関連論文リスト

• Quantum DPLL and Generalized Constraints in Iterative Quantum Algorithms [0.0]
  我々は,古典的欲求や局所探索アルゴリズムと密接に関連する,ハイブリッド量子アルゴリズムのクラスを探索する。 そこで我々は,よく知られた古典的デービス・プットナム・ローデマン・ローブランド(DPLL)アルゴリズムのハイブリッド量子バージョンを開発した。
  論文  参考訳（メタデータ） (2025-09-02T18:00:05Z)
• On the quantum computational complexity of classical linear dynamics with geometrically local interactions: Dequantization and universality [3.3083504598202733]
  量子アルゴリズムは、古典力学と長距離相互作用をシミュレートする際、古典的アルゴリズムよりも指数的なスピードアップを提供する。 偏微分方程式から生じるような多くの実世界の古典系は局所的な相互作用しか示さない。 この研究は、偏微分方程式によって支配される古典力学の複雑さに関する新たな洞察を与える。
  論文  参考訳（メタデータ） (2025-05-15T16:06:22Z)
• Quantum Subroutine for Variance Estimation: Algorithmic Design and Applications [80.04533958880862]
  量子コンピューティングは、アルゴリズムを設計する新しい方法の基礎となる。 どの場の量子スピードアップが達成できるかという新たな課題が生じる。 量子サブルーチンの設計は、従来のサブルーチンよりも効率的で、新しい強力な量子アルゴリズムに固い柱を向ける。
  論文  参考訳（メタデータ） (2024-02-26T09:32:07Z)
• Variational Quantum Algorithms for the Allocation of Resources in a Cloud/Edge Architecture [1.072460284847973]
  変分量子アルゴリズムは, 近い将来, 古典的アルゴリズムの代替となる可能性が示唆された。 特に、2つのアルゴリズム、すなわち量子近似最適化アルゴリズム(QAOA)と変分量子固有解器(VQE)の性能を比較した。 シミュレーション実験は、クラウドと2つのエッジノードを含む %CM230124 の単純な問題に対して実施され、VQE アルゴリズムは、検索空間を制限できる適切な回路テクスタイタンサッチを備えている場合に、より良い性能を保証することを示す。
  論文  参考訳（メタデータ） (2024-01-25T17:37:40Z)
• Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
  我々は3つのハイブリッド量子k-Meansアルゴリズムを設計、実装、評価する。 我々は距離の計算を高速化するために量子現象を利用する。 我々は、我々のハイブリッド量子k-平均アルゴリズムが古典的バージョンよりも効率的であることを示す。
  論文  参考訳（メタデータ） (2022-12-13T16:04:16Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。 我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。 絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
  論文  参考訳（メタデータ） (2022-05-26T20:32:36Z)
• 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)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  本研究では,トラベリングセールスマン問題に必要なキュービット数を大幅に削減できることを示す。 また、量子ビット効率と回路深さ効率のモデルを円滑に補間する符号化方式を提案する。
  論文  参考訳（メタデータ） (2020-09-15T18:17:27Z)

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

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