論文の概要: Quantum Algorithm for Vector Set Orthogonal Normalization and Matrix QR Decomposition with Polynomial Speedup

• arxiv url: http://arxiv.org/abs/2412.19090v1
• Date: Thu, 26 Dec 2024 07:04:34 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-30 17:25:53.822482
• Title: Quantum Algorithm for Vector Set Orthogonal Normalization and Matrix QR Decomposition with Polynomial Speedup
• Title（参考訳）: ベクトル集合直交正規化のための量子アルゴリズムと多項式スピードアップによる行列QR分解
• Authors: Zi-Ming Li, Yu-xi Liu,
• Abstract要約: グラムシュミット過程はベクトル集合正規化と行列QR分解を解くために広く用いられている。 既存の方法には、システム次元の$N$で$O(N3)$をスケーリングする、高い複雑性の問題がある。 本稿では,グラマーシュミット過程と量子位相推定のアイデアに基づいて,これらの2つの問題を解く量子アルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 4.913177281640608
• License:
• Abstract: Vector set orthogonal normalization and matrix QR decomposition are fundamental problems in matrix analysis with important applications in many fields. We know that Gram-Schmidt process is a widely used method to solve these two problems. However, the existing methods, including Gram-Schmidt process have problems of high complexity, scaling $O(N^3)$ in the system dimension $N$, which leads to difficulties when calculating large-scale or ill-conditioned problems. With the development of quantum information processing, a series of quantum algorithms have been proposed, providing advantages and speedups over classical algorithms in many fields. In this paper, we propose quantum algorithms to solve these two problems based on the idea of Gram-Schmidt process and quantum phase estimation. The complexity of proposed quantum algorithms is also theoretically and numerically analyzed. We find that our algorithms provide polynomial acceleration over the best-known classical and quantum algorithms on these two problems, scaling $O(N^2\mathrm{poly}(\log N))$ in the dimension $N$ of the system.
• Abstract（参考訳）: ベクトル集合の直交正規化と行列QR分解は多くの分野において重要な応用を持つ行列解析の基本的な問題である。 この2つの問題を解くために,Gram-Schmidtプロセスが広く用いられている方法であることが分かっている。 しかし、Gram-Schmidtプロセスを含む既存の手法は、システム次元で$O(N^3)$をスケーリングすることで、大規模または不飽和な問題を計算するのに困難をもたらす。 量子情報処理の開発により、多くの分野において古典的アルゴリズムよりも利点とスピードアップを提供する一連の量子アルゴリズムが提案されている。 本稿では,Gram-Schmidtプロセスと量子位相推定のアイデアに基づいて,これらの2つの問題を解く量子アルゴリズムを提案する。 提案する量子アルゴリズムの複雑さも理論的、数値的に解析される。 我々のアルゴリズムは、これらの2つの問題においてよく知られた古典的および量子的アルゴリズムに対して多項式加速度を提供し、$O(N^2\mathrm{poly}(\log N))$をシステムの次元$N$でスケーリングする。

関連論文リスト

• Quantum multi-row iteration algorithm for linear systems with non-square coefficient matrices [7.174256268278207]
  古典的マルチロー反復法に着想を得た量子アルゴリズムを提案する。 本アルゴリズムは,不整合系の解法に適した係数行列の要求を小さくする。
  論文  参考訳（メタデータ） (2024-09-06T03:32:02Z)
• A quantum-classical hybrid algorithm with Ising model for the learning with errors problem [13.06030390635216]
  本稿では,Ising Model (HAWI) を用いた量子古典ハイブリッドアルゴリズムを提案し,LWE問題に対処する。 我々は、ハミルトンの低エネルギーレベルを同定して解を抽出し、現在のノイズの多い中間スケール量子(NISQ)デバイスの実装に適したものにする。 我々のアルゴリズムは反復であり、その時間複雑性はハミルトンの低エネルギーレベルを見つけるために使われる特定の量子アルゴリズムに依存する。
  論文  参考訳（メタデータ） (2024-08-15T05:11:35Z)
• 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)
• A hybrid quantum-classical algorithm for multichannel quantum scattering of atoms and molecules [62.997667081978825]
  原子と分子の衝突に対するシュリンガー方程式を解くためのハイブリッド量子古典アルゴリズムを提案する。 このアルゴリズムはコーン変分原理の$S$-matrixバージョンに基づいており、基本散乱$S$-matrixを計算する。 大規模多原子分子の衝突をシミュレートするために,アルゴリズムをどのようにスケールアップするかを示す。
  論文  参考訳（メタデータ） (2023-04-12T18:10:47Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)
• Polynomial T-depth Quantum Solvability of Noisy Binary Linear Problem: From Quantum-Sample Preparation to Main Computation [0.0]
  雑音二元線形問題(NBLP)の量子可解性について完全解析する。 NBLPの解くコストは、指数関数的に増大する論理量子ビットを犠牲にして、問題の規模で解決できることが示される。
  論文  参考訳（メタデータ） (2021-09-23T07:46:20Z)
• Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
  3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。 本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。 提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
  論文  参考訳（メタデータ） (2021-07-08T17:59:55Z)
• A Grand Unification of Quantum Algorithms [0.0]
  最近、多くの量子アルゴリズムが量子特異値変換(quantum singular value transformation)と呼ばれる手法で結合された。 本稿では,まず量子信号処理を量子固有値変換に一般化する方法について解説する。 次に、QSVTを用いて、探索、位相推定、ハミルトニアンシミュレーションのための直感的な量子アルゴリズムを構築する。
  論文  参考訳（メタデータ） (2021-05-06T17:46:33Z)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  本研究では,トラベリングセールスマン問題に必要なキュービット数を大幅に削減できることを示す。 また、量子ビット効率と回路深さ効率のモデルを円滑に補間する符号化方式を提案する。
  論文  参考訳（メタデータ） (2020-09-15T18:17:27Z)
• Electronic structure with direct diagonalization on a D-Wave quantum annealer [62.997667081978825]
  本研究は、D-Wave 2000Q量子アニール上の分子電子ハミルトニアン固有値-固有ベクトル問題を解くために、一般量子アニール固有解法(QAE)アルゴリズムを実装した。 そこで本研究では,D-Waveハードウェアを用いた各種分子系における基底および電子励起状態の取得について述べる。
  論文  参考訳（メタデータ） (2020-09-02T22:46:47Z)

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

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