論文の概要: Efficient quantum linear solver algorithm with detailed running costs
- arxiv url: http://arxiv.org/abs/2305.11352v1
- Date: Fri, 19 May 2023 00:07:32 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-22 17:02:07.993757
- Title: Efficient quantum linear solver algorithm with detailed running costs
- Title（参考訳）: 詳細な実行コストを伴う効率的な量子線形解法アルゴリズム
- Authors: David Jennings, Matteo Lostaglio, Sam Pallister, Andrew T Sornborger,
Yi\u{g}it Suba\c{s}{\i}
- Abstract要約: 量子信号処理に基づくフィルタリング手法を用いて,アイデアダイアバティックな量子コンピューティングを組み合わせた量子線形解法アルゴリズムを提案する。
我々のプロトコルは、初期実装において、最先端技術に対する量子線形解決器のコストを桁違いに削減する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: As we progress towards physical implementation of quantum algorithms it is
vital to determine the explicit resource costs needed to run them. Solving
linear systems of equations is a fundamental problem with a wide variety of
applications across many fields of science, and there is increasing effort to
develop quantum linear solver algorithms. Here we introduce a quantum linear
solver algorithm combining ideas from adiabatic quantum computing with
filtering techniques based on quantum signal processing. We give a closed
formula for the non-asymptotic query complexity $Q$ -- the exact number of
calls to a block-encoding of the linear system matrix -- as a function of
condition number $\kappa$, error tolerance $\epsilon$ and block-encoding
scaling factor $\alpha$. Our protocol reduces the cost of quantum linear
solvers over state-of-the-art close to an order of magnitude for early
implementations. The asymptotic scaling is $O(\kappa \log(\kappa/\epsilon))$,
slightly looser than the $O(\kappa \log(1/\epsilon))$ scaling of the
asymptotically optimal algorithm of Costa et al. However, our algorithm
outperforms the latter for all condition numbers up to $\kappa \approx
10^{32}$, at which point $Q$ is comparably large, and both algorithms are
anyway practically unfeasible. The present optimized analysis is both
problem-agnostic and architecture-agnostic, and hence can be deployed in any
quantum algorithm that uses linear solvers as a subroutine.
- Abstract（参考訳）: 量子アルゴリズムの物理的実装に向けて進むにつれ、それらを実行するのに必要な明示的なリソースコストを決定することが不可欠である。
方程式の線形系を解くことは、科学の様々な分野にまたがる幅広い応用の基本的な問題であり、量子線形解法アルゴリズムを開発する努力が増えている。
本稿では, adiabatic quantum computing のアイデアと量子信号処理に基づくフィルタリング手法を組み合わせた量子線形解法を提案する。
線形系行列のブロックエンコーディングへの呼び出しの正確な数を、条件番号$\kappa$、エラー許容度$\epsilon$、ブロックエンコーディングスケーリング係数$\alpha$の関数として、非漸近的クエリ複雑性のクローズド式を与える。
我々のプロトコルは、初期実装において、最先端技術に対する量子線形解決器のコストを桁違いに削減する。
asymptotic scaling は$o(\kappa \log(\kappa/\epsilon))$であり、$o(\kappa \log(1/\epsilon))$ costa et al の漸近的最適アルゴリズムのスケーリングよりやや緩やかである。
しかしながら、我々のアルゴリズムは、最大$\kappa \approx 10^{32}$までの条件数に対して後者よりも優れており、その時点では$Q$は可分に大きい。
現在の最適化された解析は問題非依存かつアーキテクチャ非依存であり、従って線形解法をサブルーチンとして使用する任意の量子アルゴリズムにデプロイすることができる。
関連論文リスト
- 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) - Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。
我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
論文 参考訳（メタデータ） (2024-01-17T18:59:38Z) - Fast quantum algorithm for differential equations [0.5895819801677125]
我々は、数値複雑性を持つ量子アルゴリズムを、$N$で多対数であるが、大規模なPDEに対して$kappa$とは独立に提示する。
提案アルゴリズムは,解の特徴を抽出する量子状態を生成する。
論文 参考訳（メタデータ） (2023-06-20T18:01:07Z) - Mind the $\tilde{\mathcal{O}}$: Asymptotically Better, but Still
Impractical, Quantum Distributed Algorithms [0.0]
確率の高い分散計算の量子ConGEST-CLIQUEモデルに2つのアルゴリズムを提案する。
従来のCONGEST-CLIQUEモデルでは、既知のアルゴリズムよりもラウンドとメッセージの複雑さが低い。
Groverの検索アルゴリズムの分散バージョンを使用して三角形探索を高速化する既存のフレームワークは、スピードアップのコアにある。
論文 参考訳（メタデータ） (2023-04-06T02:18:52Z) - Deterministic Nonsmooth Nonconvex Optimization [94.01526844386977]
次元自由な次元自由アルゴリズムを得るにはランダム化が必要であることを示す。
我々のアルゴリズムは、ReLUネットワークを最適化する最初の決定論的次元自由アルゴリズムを得る。
論文 参考訳（メタデータ） (2023-02-16T13:57: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) - Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。
異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。
我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
論文 参考訳（メタデータ） (2022-06-07T18:00:01Z) - Quantum Algorithm for Solving a Quadratic Nonlinear System of Equations [0.22940141855172036]
アルゴリズムの複雑さは$O(rm polylog(n/epsilon))$であり、これは次元$n$の最適古典アルゴリズムよりも指数関数的に改善される。
我々のアルゴリズムは指数関数的にQNSEの解を加速し、あらゆる非線形問題に適用できる。
論文 参考訳（メタデータ） (2021-12-03T00:27:16Z) - Optimal scaling quantum linear systems solver via discrete adiabatic
theorem [0.9846257338039974]
離散的に最適となる線形系を解くための量子アルゴリズムを開発した。
既存の最適化手法と比較して,本アルゴリズムはよりシンプルで実装が容易である。
論文 参考訳（メタデータ） (2021-11-16T00:21:37Z) - Second-order Conditional Gradient Sliding [79.66739383117232]
本稿では,emphSecond-Order Conditional Gradient Sliding (SOCGS)アルゴリズムを提案する。
SOCGSアルゴリズムは、有限個の線形収束反復の後、原始ギャップに二次的に収束する。
実現可能な領域が線形最適化オラクルを通してのみ効率的にアクセスできる場合に有用である。
論文 参考訳（メタデータ） (2020-02-20T17:52:18Z) - High-precision quantum algorithms for partial differential equations [1.4050836886292872]
量子コンピュータは、古典的アルゴリズムよりも指数関数的に高速な微分方程式系の解の量子符号化を生成することができる。
適応次有限差分法とスペクトル法に基づく量子アルゴリズムを開発した。
我々のアルゴリズムは、条件数と近似誤差が有するシステムに対して、高精度な量子線形系アルゴリズムを適用している。
論文 参考訳（メタデータ） (2020-02-18T20:32:45Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。