論文の概要: Beyond asymptotic scaling: Comparing functional quantum linear solvers
- arxiv url: http://arxiv.org/abs/2503.21420v1
- Date: Thu, 27 Mar 2025 12:09:52 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-03-28 12:52:01.561908
- Title: Beyond asymptotic scaling: Comparing functional quantum linear solvers
- Title（参考訳）: 漸近スケーリングを超えて:関数型量子線形解法の比較
- Authors: Andreea-Iulia Lefterovici, Michael Perk, Debora Ramacciotti, Antonio F. Rotundo, S. E. Skelton, Martin Steinbach,
- Abstract要約: 多くの量子線形解法(QLS)が開発され、最も優れたオラクル最悪のケースの複雑性を達成するために競合している。
ほとんどのQLSはフォールトトレラントな量子コンピュータを前提としているため、実際のハードウェアでベンチマークを行うことはできない。
近似行列反転関数を直接実装する4つのよく知られたQVTアルゴリズムについて考察する。
- 参考スコア（独自算出の注目度）: 0.0
- License:
- Abstract: Solving systems of linear equations is a key subroutine in many quantum algorithms. In the last 15 years, many quantum linear solvers (QLS) have been developed, competing to achieve the best asymptotic worst-case complexity. Most QLS assume fault-tolerant quantum computers, so they cannot yet be benchmarked on real hardware. Because an algorithm with better asymptotic scaling can underperform on instances of practical interest, the question of which of these algorithms is the most promising remains open. In this work, we implement a method to partially address this question. We consider four well-known QLS algorithms which directly implement an approximate matrix inversion function: the Harrow-Hassidim-Lloyd algorithm, two algorithms utilizing a linear combination of unitaries, and one utilizing the quantum singular value transformation (QSVT). These methods, known as functional QLS, share nearly identical assumptions about the problem setup and oracle access. Their computational cost is dominated by query calls to a matrix oracle encoding the problem one wants to solve. We provide formulas to count the number of queries needed to solve specific problem instances; these can be used to benchmark the algorithms on real-life instances without access to quantum hardware. We select three data sets: random generated instances that obey the assumptions of functional QLS, linear systems from simplex iterations on MIPLIB, and Poisson equations. Our methods can be easily extended to other data sets and provide a high-level guide to evaluate the performance of a QLS algorithm. In particular, our work shows that HHL underperforms in comparison to the other methods across all data sets, often by orders of magnitude, while the QSVT-based method shows the best performance.
- Abstract（参考訳）: 線形方程式の解法系は、多くの量子アルゴリズムにおいて重要なサブルーチンである。
過去15年間で、多くの量子線形解法(QLS)が開発され、最も漸近的な最悪のケースの複雑さを達成するために競っている。
ほとんどのQLSはフォールトトレラントな量子コンピュータを前提としているため、実際のハードウェアでベンチマークを行うことはできない。
より優れた漸近的スケーリングを持つアルゴリズムは、実用的関心の事例では性能が劣る可能性があるため、これらのアルゴリズムのどちらが最も有望かという問題は、まだ未解決のままである。
本研究では,この問題を部分的に解決する手法を実装した。
Harrow-Hassidim-Lloydアルゴリズム、ユニタリの線形結合を利用する2つのアルゴリズム、量子特異値変換(QSVT)を利用する1つのアルゴリズムについて考察する。
これらの手法は関数型QLSと呼ばれ、問題設定とオラクルアクセスに関するほぼ同一の仮定を共有している。
彼らの計算コストは、解決したい問題を符号化する行列オラクルへの問い合わせによって支配される。
特定の問題インスタンスを解くのに必要なクエリ数をカウントするために公式を提供し、量子ハードウェアにアクセスせずに実際のインスタンス上でアルゴリズムをベンチマークするために使用できる。
関数型QLSの仮定に従うランダム生成インスタンス、MIPLIB上の単純反復からの線形システム、ポアソン方程式の3つのデータセットを選択する。
提案手法は,他のデータセットに容易に拡張可能であり,QLSアルゴリズムの性能を評価するための高レベルガイドを提供する。
特に、我々の研究は、HHLが全てのデータセットにまたがる他の手法と比較して、しばしば桁違いに性能が低下していることを示し、QSVTベースの手法は最高の性能を示している。
関連論文リスト
- Quantum Discrete Adiabatic Linear Solver based on Block Encoding and Eigenvalue Separator [5.138262101775231]
量子コンピューティングの台頭は、量子線形系問題への関心を喚起した。
HHLアルゴリズムの性能は条件数の二乗に依存して制約される。
本研究はブロック符号化と固有値分離に基づく量子離散断熱線形解法を提案する。
論文 参考訳（メタデータ） (2024-12-09T04:50:48Z) - Shadow Quantum Linear Solver: A Resource Efficient Quantum Algorithm for Linear Systems of Equations [0.8437187555622164]
本稿では,デジタル量子デバイス上での量子線形システム問題(QLSP)の解法を提案する。
その結果、大きな制御されたユニタリの必要性を回避し、システムサイズで対数的な多くの量子ビットを必要とする量子アルゴリズムが実現した。
これを、線形代数の分解定理を利用して、2次元格子における離散化されたラプラス方程式を解くことで、実用的妥当性の物理問題に適用する。
論文 参考訳（メタデータ） (2024-09-13T15:46:32Z) - 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) - An Efficient Quantum Algorithm for Linear System Problem in Tensor Format [4.264200809234798]
本稿では,最近のアディバティック・インスパイアされたQLSAの進歩に基づく量子アルゴリズムを提案する。
実装の全体的な複雑さは、その次元において多対数的であることを厳密に示します。
論文 参考訳（メタデータ） (2024-03-28T20:37:32Z) - Two quantum algorithms for solving the one-dimensional
advection-diffusion equation [0.0]
2つの量子アルゴリズムが周期的境界条件を持つ線形一次元対流拡散方程式の数値解に対して提示される。
量子ビット数の増加に伴う精度と性能を、ポイントごとに比較する。
論文 参考訳（メタデータ） (2023-12-30T21:23:15Z) - Unifying (Quantum) Statistical and Parametrized (Quantum) Algorithms [65.268245109828]
我々はカーンズのSQオラクルとヴァリアントの弱い評価オラクルからインスピレーションを得ます。
評価クエリから学習するための非条件の下限を出力する,広範かつ直感的なフレームワークを提案する。
論文 参考訳（メタデータ） (2023-10-26T18:23:21Z) - 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) - 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) - Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。
本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。
提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
論文 参考訳（メタデータ） (2021-07-08T17:59:55Z) - Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
形状対応を見つけることは、NP-hard quadratic assignment problem (QAP)として定式化できる。
本稿では,アルファ拡大アルゴリズムに触発されたQAPの反復量子法Q-Matchを提案する。
Q-Match は、実世界の問題にスケールできるような長文対応のサブセットにおいて、反復的に形状マッチング問題に適用できる。
論文 参考訳（メタデータ） (2021-05-06T17:59:38Z) - Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra [53.46106569419296]
我々は、リコメンダシステムと最小二乗回帰のためのクエリをサポートする古典的な(量子でない)動的データ構造を作成する。
これらの問題に対する以前の量子インスパイアされたアルゴリズムは、レバレッジやリッジレベレッジスコアを偽装してサンプリングしていると我々は主張する。
論文 参考訳（メタデータ） (2020-11-09T01:13:07Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。