論文の概要: Block-encoding based quantum algorithm for linear systems with
displacement structures
- arxiv url: http://arxiv.org/abs/1912.12212v2
- Date: Tue, 5 Oct 2021 08:57:04 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-09 23:26:03.279530
- Title: Block-encoding based quantum algorithm for linear systems with
displacement structures
- Title（参考訳）: 変位構造を持つ線形系のブロックエンコーディングに基づく量子アルゴリズム
- Authors: Lin-Chun Wan, Chao-Hua Yu, Shi-Jie Pan, Su-Juan Qin, Fei Gao, Qiao-Yan
Wen
- Abstract要約: 本稿では, 変位構造を持つ線形系を解くために, 効率よく, メモリリデュースした量子アルゴリズムを提案する。
提案したブロックエンコーディングは、古典的アルゴリズムの次元に関して二次的なスピードアップを提供する。
量子線形系の解法の一つを時系列の線形予測に適用する。
- 参考スコア（独自算出の注目度）: 4.145426157018113
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Matrices with the displacement structures of circulant, Toeplitz, and Hankel
types as well as matrices with structures generalizing these types are
omnipresent in computations of sciences and engineering. In this paper, we
present efficient and memory-reduced quantum algorithms for solving linear
systems with such structures by devising a new approach to implement the
block-encodings of these structured matrices. More specifically, by decomposing
$n\times n$ dense matrices into linear combinations of displacement matrices,
we first deduce the parameterized representations of the matrices with
displacement structures so that they can be treated similarly. With such
representations, we then construct $\epsilon$-approximate block-encodings of
these structured matrices in two different data access models, i.e., the
black-box model and the QRAM data structure model. It is shown the quantum
linear system solvers based on the proposed block-encodings provide a quadratic
speedup with respect to the dimension over classical algorithms in the
black-box model and an exponential speedup in the QRAM data structure model. In
particular, these linear system solvers subsume known results with significant
improvements and also motivate new instances where there was no specialized
quantum algorithm before. As an application, one of the quantum linear system
solvers is applied to the linear prediction of time series, which justifies the
claimed quantum speedup is achievable for problems of practical interest.
- Abstract（参考訳）: サーキュラント、トエプリッツ、ハンケル型の変位構造を持つ行列や、これらの型を一般化する構造を持つ行列は、科学や工学の計算において一様である。
本稿では、これらの構造行列のブロックエンコーディングを実装するための新しいアプローチを考案し、そのような構造を持つ線形系を解くための効率的でメモリレデュースな量子アルゴリズムを提案する。
より具体的には、$n\times n$ dense matricesを変位行列の線形結合に分解することにより、行列のパラメータ化表現を変位構造で導出し、同様に扱うことができる。
このような表現を用いて、2つの異なるデータアクセスモデル、すなわちブラックボックスモデルとqramデータ構造モデルにおける構造化行列の$\epsilon$-approximateブロックエンコーディングを構築する。
提案するブロックエンコーディングに基づく量子線形システムソルバは,ブラックボックスモデルにおける古典的アルゴリズム上の次元に対する二次的高速化と,qramデータ構造モデルにおける指数的高速化を提供する。
特に、これらの線形システム解法は、既知の結果を大幅に改善し、以前に特別な量子アルゴリズムがなかった新しいインスタンスを動機付けている。
応用として、量子線形系ソルバの1つを時系列の線形予測に適用し、主張された量子スピードアップが実用上の問題に対して達成可能であることを正当化する。
関連論文リスト
- A general quantum matrix exponential dimensionality reduction framework
based on block-encoding [4.501305807267216]
行列指数次元還元(MEDR)は、線形次元化(DR)アルゴリズムに現れる小さなサンプルサイズの問題を扱う。
高複雑性がこの種のDRアルゴリズムのボトルネックとなるのは、大規模な行列指数固有確率を解く必要があるからである。
我々はブロックエンコーディング技術に基づくMEDRのための汎用量子アルゴリズムフレームワークを設計する。
論文 参考訳（メタデータ） (2023-06-16T03:36:03Z) - Vectorization of the density matrix and quantum simulation of the von
Neumann equation of time-dependent Hamiltonians [65.268245109828]
我々は、von-Neumann方程式を線形化するための一般的なフレームワークを開発し、量子シミュレーションに適した形でレンダリングする。
フォン・ノイマン方程式のこれらの線型化のうちの1つは、状態ベクトルが密度行列の列重ね元となる標準的な場合に対応することを示す。
密度行列の力学をシミュレートする量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-06-14T23:08:51Z) - A Recursively Recurrent Neural Network (R2N2) Architecture for Learning
Iterative Algorithms [64.3064050603721]
本研究では,リカレントニューラルネットワーク (R2N2) にランゲ・クッタニューラルネットワークを一般化し,リカレントニューラルネットワークを最適化した反復アルゴリズムの設計を行う。
本稿では, 線形方程式系に対するクリロフ解法, 非線形方程式系に対するニュートン・クリロフ解法, 常微分方程式に対するルンゲ・クッタ解法と類似の繰り返しを計算問題クラスの入力・出力データに対して提案した超構造内における重みパラメータの正規化について述べる。
論文 参考訳（メタデータ） (2022-11-22T16:30:33Z) - A quantum algorithm for solving eigenproblem of the Laplacian matrix of
a fully connected weighted graph [4.045204834863644]
完全連結重み付きグラフのラプラシア行列の固有確率を解くための効率的な量子アルゴリズムを提案する。
具体的には,ブロック符号化フレームワークに基づく最適ハミルトンシミュレーション手法を採用する。
また、このアルゴリズムは対称(非対称)正規化ラプラス行列の固有確率を解くために拡張可能であることを示す。
論文 参考訳（メタデータ） (2022-03-28T02:24:08Z) - High-Dimensional Sparse Bayesian Learning without Covariance Matrices [66.60078365202867]
共分散行列の明示的な構成を避ける新しい推論手法を提案する。
本手法では, 数値線形代数と共役勾配アルゴリズムの対角線推定結果とを結合する。
いくつかのシミュレーションにおいて,本手法は計算時間とメモリにおける既存手法よりも拡張性が高い。
論文 参考訳（メタデータ） (2022-02-25T16:35:26Z) - Quantum algorithms for matrix operations and linear systems of equations [65.62256987706128]
本稿では,「Sender-Receiver」モデルを用いた行列演算のための量子アルゴリズムを提案する。
これらの量子プロトコルは、他の量子スキームのサブルーチンとして使用できる。
論文 参考訳（メタデータ） (2022-02-10T08:12:20Z) - On the application of Sylvester's law of inertia to QUBO formulations
for systems of linear equations [0.2538209532048866]
我々はSylvesterの慣性則を適用して線形方程式系のQUBO定式化を開発する。
提案アルゴリズムは,量子コンピュータ上での線形方程式の高次元系を効果的に実装できることを期待する。
論文 参考訳（メタデータ） (2021-11-19T07:55:10Z) - Linear embedding of nonlinear dynamical systems and prospects for
efficient quantum algorithms [74.17312533172291]
有限非線形力学系を無限線型力学系(埋め込み)にマッピングする方法を述べる。
次に、有限線型系 (truncation) による結果の無限線型系を近似するアプローチを検討する。
論文 参考訳（メタデータ） (2020-12-12T00:01:10Z) - Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra [53.46106569419296]
我々は、リコメンダシステムと最小二乗回帰のためのクエリをサポートする古典的な(量子でない)動的データ構造を作成する。
これらの問題に対する以前の量子インスパイアされたアルゴリズムは、レバレッジやリッジレベレッジスコアを偽装してサンプリングしていると我々は主張する。
論文 参考訳（メタデータ） (2020-11-09T01:13:07Z) - Fast inversion, preconditioned quantum linear system solvers, and fast
evaluation of matrix functions [4.327821619134312]
量子線形系を解くためのプレコンディショナーとして使用できる高速反転と呼ばれる量子プリミティブを導入する。
量子多体系の単一粒子グリーン関数の計算における事前条件付き線形システム解法の適用例を示す。
論文 参考訳（メタデータ） (2020-08-30T23:24:58Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。