論文の概要: Constant-Factor Improvements in Quantum Algorithms for Linear Differential Equations

• arxiv url: http://arxiv.org/abs/2506.20760v1
• Date: Wed, 25 Jun 2025 18:50:44 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-27 19:53:09.856088
• Title: Constant-Factor Improvements in Quantum Algorithms for Linear Differential Equations
• Title（参考訳）: 線形微分方程式に対する量子アルゴリズムの定数係数改善
• Authors: Matthew Pocrnic, Peter D. Johnson, Amara Katabarwa, Nathan Wiebe,
• Abstract要約: 我々は、ハミルトニアンシミュレーションアルゴリズムの線形結合である有望な新しい量子微分方程式解法に対する定数係数境界を証明した。 我々の新しい公式は、少なくとも2桁の精度で従来の状態よりも改善され、状態の準備にかなりのコストがかかる場合、スピードアップははるかに大きくなる可能性がある。
• 参考スコア（独自算出の注目度）: 0.46664938579243576
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Finding the solution to linear ordinary differential equations of the form $\partial_t u(t) = -A(t)u(t)$ has been a promising theoretical avenue for \textit{asymptotic} quantum speedups. However, despite the improvements to existing quantum differential equation solvers over the years, little is known about \textit{constant factor} costs of such quantum algorithms. This makes it challenging to assess the prospects for using these algorithms in practice. In this work, we prove constant factor bounds for a promising new quantum differential equation solver, the linear combination of Hamiltonian simulation (LCHS) algorithm. Our bounds are formulated as the number of queries to a unitary $U_A$ that block encodes the generator $A$. In doing so, we make several algorithmic improvements such as tighter truncation and discretization bounds on the LCHS kernel integral, a more efficient quantum compilation scheme for the SELECT operator in LCHS, as well as use of a constant-factor bound for oblivious amplitude amplification, which may be of general interest. To the best of our knowledge, our new formulae improve over previous state of the art by at least two orders of magnitude, where the speedup can be far greater if state preparation has a significant cost. Accordingly, for any previous resource estimates of time-independent linear differential equations for the most general case whereby the dynamics are not \textit{fast-forwardable}, these findings provide a 110x reduction in runtime costs. This analysis contributes towards establishing more promising applications for quantum computing.
• Abstract（参考訳）: $\partial_t u(t) = -A(t)u(t)$ という形の線型常微分方程式の解を見つけることは、 \textit{asymsymotic} 量子スピードアップの有望な理論的方法である。 しかし、長年にわたる既存の量子微分方程式解法の改善にもかかわらず、そのような量子アルゴリズムの『textit{constant factor}』コストについてはほとんど知られていない。 これにより、これらのアルゴリズムを実際に使用する可能性を評価することは困難である。 本研究では、ハミルトニアンシミュレーション(LCHS)アルゴリズムの線形結合である新しい量子微分方程式解法に対する定数係数境界の証明を行う。 私たちの境界は、ジェネレータをエンコードするブロックである$U_A$へのクエリ数として定式化されます。 そこで本研究では,LCHSカーネル積分の厳密化や離散化境界,LCHSのSELECT演算子に対するより効率的な量子コンパイルスキーム,および不規則振幅増幅のための定数要素バウンダリングなどのアルゴリズムの改良を行った。 我々の知識を最大限に活用するために、我々の新しい公式は、少なくとも2桁の精度で従来の状態よりも改善され、状態の準備にかなりのコストがかかる場合、スピードアップははるかに大きい。 したがって、最も一般的な場合における時間非依存線型微分方程式のこれまでの資源推定では、力学が \textit{fast-forwardable} でないため、これらの結果は実行コストの110倍の削減をもたらす。 この分析は量子コンピューティングのより有望な応用の確立に寄与する。

関連論文リスト

• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。 この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
  論文  参考訳（メタデータ） (2024-08-14T19:04:13Z)
• Quantum and classical algorithms for nonlinear unitary dynamics [0.5729426778193399]
  我々は$fracd|urangledtという形の非線形微分方程式に対する量子アルゴリズムを提案する。 また,Euler法に基づく古典的アルゴリズムを導入し,制限された場合の量子アルゴリズムへのコンパラブルなスケーリングを実現する。
  論文  参考訳（メタデータ） (2024-07-10T14:08:58Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。 我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
  論文  参考訳（メタデータ） (2024-01-17T18:59:38Z)
• Randomized adiabatic quantum linear solver algorithm with optimal complexity scaling and detailed running costs [0.0]
  そこで我々は, 断熱量子計算に基づく線形線形解法アルゴリズムを開発した。 このアルゴリズムは最適スケーリング$O(kappa/log$)$に改善され、$epsilon$が指数関数的に改善される。 ハミルトンシミュレーションの代わりに、より安価なランダム化されたウォーク演算子法を導入する。
  論文  参考訳（メタデータ） (2023-05-19T00:07:32Z)
• Time-marching based quantum solvers for time-dependent linear differential equations [3.1952399274829775]
  タイムマーチング戦略は、古典コンピュータ上の時間依存微分方程式を解く自然な戦略である。 時間マーチングに基づく量子解法は、時間ステップ数に関して指数関数的に成功確率を逸脱させる可能性があることを示す。 これは、量子線型系アルゴリズムに基づくものに代わる量子微分方程式の解法を設計する道を提供する。
  論文  参考訳（メタデータ） (2022-08-14T23:49:19Z)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  本稿では,n+1$ qubitsしか使用しないGoemans-Williamsonアルゴリズムの変分量子アルゴリズムを提案する。 補助量子ビット上で適切にパラメータ化されたユニタリ条件として目的行列を符号化することにより、効率的な最適化を実現する。 各種NPハード問題に対して,Goemans-Williamsonアルゴリズムの量子的効率的な実装を考案し,提案プロトコルの有効性を実証する。
  論文  参考訳（メタデータ） (2022-06-30T03:15:23Z)
• Alternatives to a nonhomogeneous partial differential equation quantum algorithm [52.77024349608834]
  Apsi(textbfr)=f(textbfr)$ という形の非等質線型偏微分方程式を解くための量子アルゴリズムを提案する。 これらの成果により、現代の技術に基づく量子アルゴリズムの実験的実装が容易になった。
  論文  参考訳（メタデータ） (2022-05-11T14:29:39Z)
• Efficient quantum algorithm for dissipative nonlinear differential equations [1.1988695717766686]
  我々は、散逸的2次2次元常微分方程式の量子アルゴリズムを開発する。 我々のアルゴリズムは複雑性$T2 qmathrmpoly(log T, log n, log 1/epsilon)/epsilon$, ここでは$T$が進化時間、$epsilon$が許容エラー、$q$が解の崩壊を測定する。
  論文  参考訳（メタデータ） (2020-11-06T04:27:00Z)

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

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