論文の概要: An Efficient Quantum Algorithm for Linear System Problem in Tensor Format

• arxiv url: http://arxiv.org/abs/2403.19829v1
• Date: Thu, 28 Mar 2024 20:37:32 GMT
• ステータス: 処理完了
• システム内更新日: 2024-04-01 17:13:56.525864
• Title: An Efficient Quantum Algorithm for Linear System Problem in Tensor Format
• Title（参考訳）: テンソル形式における線形系問題に対する効率的な量子アルゴリズム
• Authors: Zeguan Wu, Sidhant Misra, Tamás Terlaky, Xiu Yang, Marc Vuffray,
• Abstract要約: 本稿では,最近のアディバティック・インスパイアされたQLSAの進歩に基づく量子アルゴリズムを提案する。 実装の全体的な複雑さは、その次元において多対数的であることを厳密に示します。
• 参考スコア（独自算出の注目度）: 4.264200809234798
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Solving linear systems is at the foundation of many algorithms. Recently, quantum linear system algorithms (QLSAs) have attracted great attention since they converge to a solution exponentially faster than classical algorithms in terms of the problem dimension. However, low-complexity circuit implementations of the oracles assumed in these QLSAs constitute the major bottleneck for practical quantum speed-up in solving linear systems. In this work, we focus on the application of QLSAs for linear systems that are expressed as a low rank tensor sums, which arise in solving discretized PDEs. Previous works uses modified Krylov subspace methods to solve such linear systems with a per-iteration complexity being polylogarithmic of the dimension but with no guarantees on the total convergence cost. We propose a quantum algorithm based on the recent advances on adiabatic-inspired QLSA and perform a detailed analysis of the circuit depth of its implementation. We rigorously show that the total complexity of our implementation is polylogarithmic in the dimension, which is comparable to the per-iteration complexity of the classical heuristic methods.
• Abstract（参考訳）: 線形システムの解決は多くのアルゴリズムの基礎にある。 近年、量子線形システムアルゴリズム (QLSA) は、問題次元の観点から古典的アルゴリズムよりも指数関数的に高速な解に収束するため、大きな注目を集めている。 しかし、これらのQLSAで想定されるオラクルの低複雑さ回路実装は、線形系を解くための実用的な量子スピードアップのボトルネックとなっている。 本研究では、低階テンソル和として表される線形システムに対するQLSAの適用に焦点を当て、離散化されたPDEの解法で生じる。 以前の研究は、修正されたクリロフ部分空間法を用いて、次元の多対数的であるが、総収束コストの保証がない、一点当たりの複雑性を持つような線型系を解く。 本稿では,近年の断熱型QLSAの進歩に基づく量子アルゴリズムを提案し,その実装の回路深さを詳細に解析する。 我々は,古典的ヒューリスティック手法の解法毎の複雑性に匹敵する次元において,実装の全体的な複雑さが多元対数的であることを厳密に示す。

関連論文リスト

• Shadow Quantum Linear Solver: A Resource Efficient Quantum Algorithm for Linear Systems of Equations [0.8437187555622164]
  本稿では,デジタル量子デバイス上での量子線形システム問題(QLSP)の解法を提案する。 その結果、大きな制御されたユニタリの必要性を回避し、システムサイズで対数的な多くの量子ビットを必要とする量子アルゴリズムが実現した。 これを、線形代数の分解定理を利用して、2次元格子における離散化されたラプラス方程式を解くことで、実用的妥当性の物理問題に適用する。
  論文  参考訳（メタデータ） (2024-09-13T15:46:32Z)
• A Catalyst Framework for the Quantum Linear System Problem via the Proximal Point Algorithm [9.804179673817574]
  古典的近位点法(PPA)に着想を得た量子線形系問題(QLSP)に対する新しい量子アルゴリズムを提案する。 提案手法は,既存のtexttimattQLSP_solverを経由した修正行列の逆変換が可能なメタアルゴリズムとみなすことができる。 ステップサイズ$eta$を慎重に選択することにより、提案アルゴリズムは線形システムに対して、以前のアプローチの適用性を阻害する条件数への依存を軽減するために、効果的に事前条件を定めることができる。
  論文  参考訳（メタデータ） (2024-06-19T23:15:35Z)
• Hybrid quantum-classical and quantum-inspired classical algorithms for solving banded circulant linear systems [0.8192907805418583]
  帯状循環系に対する量子状態の組み合わせの凸最適化に基づく効率的なアルゴリズムを提案する。 帯状循環行列を巡回置換に分解することにより, 量子状態の組み合わせによる近似解を$K$とする。 我々は,従来のシミュレーションと実際のIBM量子コンピュータ実装を用いて本手法を検証し,熱伝達などの物理問題への適用性を示した。
  論文  参考訳（メタデータ） (2023-09-20T16:27:16Z)
• Quantum Relaxation for Linear Systems in Finite Element Analysis [0.0]
  ゲートベース量子コンピュータの反復的アプローチとして,リニアシステム(qRLS)の量子緩和を提案する。 このシステムは、QLSAの最先端量子信号処理(QSP)変種を用いて、有限要素問題の実用的な反復解を可能にする。 これは指数効率の向上を表しており、量子ハードウェア上での反復有限要素問題の解法に対する新しいアプローチを提供する。
  論文  参考訳（メタデータ） (2023-08-02T18:31:33Z)
• An Inexact Feasible Quantum Interior Point Method for Linearly Constrained Quadratic Optimization [0.0]
  量子線形システムアルゴリズム(QLSA)は、線形システムの解法に依存するアルゴリズムを高速化する可能性がある。 本研究では, 線形制約付き2次最適化問題の解法において, 実効性のないQIPM(Inexact-Feasible QIPM)を提案する。
  論文  参考訳（メタデータ） (2023-01-13T01:36:13Z)
• Accelerating the training of single-layer binary neural networks using the HHL quantum algorithm [58.720142291102135]
  Harrow-Hassidim-Lloyd (HHL) の量子力学的実装から有用な情報が抽出可能であることを示す。 しかし,本論文では,HHLの量子力学的実装から有用な情報を抽出し,古典的側面における解を見つける際の複雑性を低減することを目的としている。
  論文  参考訳（メタデータ） (2022-10-23T11:58:05Z)
• First-Order Algorithms for Nonlinear Generalized Nash Equilibrium Problems [88.58409977434269]
  非線形一般化ナッシュ均衡問題(NGNEP)における平衡計算の問題を考える。 我々の貢献は、2次ペナルティ法と拡張ラグランジアン法に基づく2つの単純な一階アルゴリズムフレームワークを提供することである。 これらのアルゴリズムに対する漸近的理論的保証を提供する。
  論文  参考訳（メタデータ） (2022-04-07T00:11:05Z)
• Detailed Account of Complexity for Implementation of Some Gate-Based Quantum Algorithms [55.41644538483948]
  特に、状態準備および読み出しプロセスのような実装のいくつかのステップは、アルゴリズム自体の複雑さの側面を超越することができる。 本稿では、方程式の線形系と微分方程式の線形系を解くための量子アルゴリズムの完全な実装に関わる複雑性について述べる。
  論文  参考訳（メタデータ） (2021-06-23T16:33:33Z)
• Fixed Depth Hamiltonian Simulation via Cartan Decomposition [59.20417091220753]
  時間に依存しない深さの量子回路を生成するための構成的アルゴリズムを提案する。 一次元横フィールドXYモデルにおけるアンダーソン局在化を含む、モデルの特殊クラスに対するアルゴリズムを強調する。 幅広いスピンモデルとフェルミオンモデルに対して正確な回路を提供するのに加えて、我々のアルゴリズムは最適なハミルトニアンシミュレーションに関する幅広い解析的および数値的な洞察を提供する。
  論文  参考訳（メタデータ） (2021-04-01T19:06:00Z)
• Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra [53.46106569419296]
  我々は、リコメンダシステムと最小二乗回帰のためのクエリをサポートする古典的な(量子でない)動的データ構造を作成する。 これらの問題に対する以前の量子インスパイアされたアルゴリズムは、レバレッジやリッジレベレッジスコアを偽装してサンプリングしていると我々は主張する。
  論文  参考訳（メタデータ） (2020-11-09T01:13:07Z)
• Iterative Algorithm Induced Deep-Unfolding Neural Networks: Precoding Design for Multiuser MIMO Systems [59.804810122136345]
  本稿では,AIIDNN(ディープ・アンフォールディング・ニューラルネット)を一般化した,ディープ・アンフォールディングのためのフレームワークを提案する。 古典的重み付き最小二乗誤差(WMMSE)反復アルゴリズムの構造に基づく効率的なIAIDNNを提案する。 提案したIAIDNNは,計算複雑性を低減した反復WMMSEアルゴリズムの性能を効率よく向上することを示す。
  論文  参考訳（メタデータ） (2020-06-15T02:57:57Z)

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

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