論文の概要: Quantum multi-row iteration algorithm for linear systems with non-square coefficient matrices
- arxiv url: http://arxiv.org/abs/2409.04010v2
- Date: Mon, 9 Sep 2024 02:57:20 GMT
- ステータス: 処理完了
- システム内更新日: 2024-09-10 13:16:17.368720
- Title: Quantum multi-row iteration algorithm for linear systems with non-square coefficient matrices
- Title（参考訳）: 非二乗係数行列を持つ線形系に対する量子多列反復アルゴリズム
- Authors: Weitao Lin, Guojing Tian, Xiaoming Sun,
- Abstract要約: 古典的マルチロー反復法に着想を得た量子アルゴリズムを提案する。
本アルゴリズムは,不整合系の解法に適した係数行列の要求を小さくする。
- 参考スコア（独自算出の注目度）: 7.174256268278207
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In the field of quantum linear system algorithms, quantum computing has realized exponential computational advantages over classical computing. However, the focus has been on square coefficient matrices, with few quantum algorithms addressing non-square matrices. Towards this kind of problems defined by $ Ax = b $ where $ A $$ \in\mathbb{R}^{m \times n} $, we propose a quantum algorithm inspired by the classical multi-row iteration method and provide an explicit quantum circuit based on the quantum comparator and Quantum Random Access Memory (QRAM). The time complexity of our quantum multi-row iteration algorithm is $ O(K \log m) $, with $ K $ representing the number of iteration steps, which demonstrates an exponential speedup compared to the classical version. Based on the convergence of the classical multi-row iteration algorithm, we prove that our quantum algorithm converges faster than the quantum one-row iteration algorithm presented in [Phys. Rev. A, 101, 022322 (2020)]. Moreover, our algorithm places less demand on the coefficient matrix, making it suitable for solving inconsistent systems and quadratic optimization problems.
- Abstract（参考訳）: 量子線形系アルゴリズムの分野では、量子コンピューティングは古典計算よりも指数関数計算の優位性を実現している。
しかし、焦点は平方係数行列であり、非平方行列に対処する量子アルゴリズムはほとんどない。
Ax = b $ where $ A $$ \in\mathbb{R}^{m \times n} $ で定義されるこのような問題に対して、古典的マルチロー反復法にインスパイアされた量子アルゴリズムを提案し、量子コンパレータと量子ランダムアクセスメモリ(QRAM)に基づく明示的な量子回路を提供する。
量子マルチロー反復アルゴリズムの時間的複雑さは、O(K \log m)$で、反復ステップの数を表す$K$であり、古典的なバージョンと比較して指数的なスピードアップを示している。
古典的マルチロー反復アルゴリズムの収束に基づいて,我々の量子アルゴリズムは[Phys. A, 101, 022322 (2020)]で示される量子ワンロー反復アルゴリズムよりも早く収束することが証明された。
さらに,本アルゴリズムは係数行列に対する需要を小さくし,不整合系の解法や二次最適化問題に適している。
関連論文リスト
- 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) - The Algorithm for Solving Quantum Linear Systems of Equations With Coherent Superposition and Its Extended Applications [8.8400072344375]
コヒーレント重ね合わせを持つ方程式の量子線型系を解くための2つの量子アルゴリズムを提案する。
2つの量子アルゴリズムは、ランクと一般解の両方を1つの測定で計算できる。
分析の結果,提案アルゴリズムは主に軽量対称暗号に対する攻撃に適していることがわかった。
論文 参考訳（メタデータ） (2024-05-11T03:03:14Z) - Generalized quantum Arimoto-Blahut algorithm and its application to
quantum information bottleneck [55.22418739014892]
量子アリーモト・ブラフトアルゴリズムをRamakrishnanらにより一般化する。
3つの量子系を持つ量子情報ボトルネックに対して,我々のアルゴリズムを適用した。
数値解析により,我々のアルゴリズムはアルゴリズムよりも優れていることが示された。
論文 参考訳（メタデータ） (2023-11-19T00:06:11Z) - A Quadratic Speedup in Finding Nash Equilibria of Quantum Zero-Sum Games [102.46640028830441]
最適行列乗算重み更新(OMMWU)アルゴリズムを導入し,平均収束複雑性を$mathcalO(d/epsilon)$ to $epsilon$-Nash equilibriaとする。
この二次的なスピードアップは、量子ゼロサムゲームにおける$epsilon$-Nash平衡の計算のための新しいベンチマークを定めている。
論文 参考訳（メタデータ） (2023-11-17T20:38:38Z) - Qubit-Efficient Randomized Quantum Algorithms for Linear Algebra [3.4137115855910767]
本稿では,行列関数からのサンプリング作業のためのランダム化量子アルゴリズムのクラスを提案する。
量子ビットの使用は純粋にアルゴリズムであり、量子データ構造には追加の量子ビットは必要ない。
論文 参考訳（メタデータ） (2023-02-03T17:22:49Z) - Quantum speedup of leverage score sampling and its application [0.0]
本稿では,レバレッジスコアの計算を高速化する量子アルゴリズムを提案する。
応用として,ベクトル解出力を用いた剛性回帰問題に対する新しい量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-15T14:40:18Z) - Solving the semidefinite relaxation of QUBOs in matrix multiplication
time, and faster with a quantum computer [0.20999222360659603]
いくつかの量子SDOソルバは、低精度な状態において高速化を提供する。
この事実を利用してアルゴリズムの精度への依存を指数関数的に改善する。
我々のアルゴリズムの量子実装は、$mathcalO left(ns + n1.5 cdot textpolylog left(n, | C |_F, frac1epsilon right)$の最悪の実行時間を示す。
論文 参考訳（メタデータ） (2023-01-10T23:12:05Z) - Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
我々は3つのハイブリッド量子k-Meansアルゴリズムを設計、実装、評価する。
我々は距離の計算を高速化するために量子現象を利用する。
我々は、我々のハイブリッド量子k-平均アルゴリズムが古典的バージョンよりも効率的であることを示す。
論文 参考訳（メタデータ） (2022-12-13T16:04:16Z) - Quantum Algorithm For Estimating Eigenvalue [0.0]
与えられたエルミート行列の大きさで最大の固有値を推定するための量子アルゴリズムを提供する。
我々の量子プロシージャは、同じ問題を解決する古典的なアルゴリズムと比較して指数的なスピードアップを得ることができる。
論文 参考訳（メタデータ） (2022-11-11T13:02:07Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳（メタデータ） (2022-05-26T20:32:36Z) - Quantum Gram-Schmidt Processes and Their Application to Efficient State
Read-out for Quantum Algorithms [87.04438831673063]
本稿では、生成した状態の古典的ベクトル形式を生成する効率的な読み出しプロトコルを提案する。
我々のプロトコルは、出力状態が入力行列の行空間にある場合に適合する。
我々の技術ツールの1つは、Gram-Schmidt正則手順を実行するための効率的な量子アルゴリズムである。
論文 参考訳（メタデータ） (2020-04-14T11:05:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。