Fugu-MT 論文翻訳(概要): Quantum speedup of leverage score sampling and its application

論文の概要: Quantum speedup of leverage score sampling and its application

arxiv url: http://arxiv.org/abs/2301.06107v2
Date: Sat, 16 Sep 2023 12:24:51 GMT
ステータス: 翻訳完了
システム内更新日: 2023-09-20 01:00:16.544259
Title: Quantum speedup of leverage score sampling and its application
Title（参考訳）: レバレッジスコアサンプリングの量子高速化とその応用
Authors: Changpeng Shao
Abstract要約: 本稿では,レバレッジスコアの計算を高速化する量子アルゴリズムを提案する。応用として,ベクトル解出力を用いた剛性回帰問題に対する新しい量子アルゴリズムを提案する。
参考スコア（独自算出の注目度）: 0.0
License: http://creativecommons.org/licenses/by/4.0/
Abstract: Leverage score sampling is crucial to the design of randomized algorithms for large-scale matrix problems, while the computation of leverage scores is a bottleneck of many applications. In this paper, we propose a quantum algorithm to accelerate this useful method. The speedup is at least quadratic and could be exponential for well-conditioned matrices. We also prove some quantum lower bounds, which suggest that our quantum algorithm is close to optimal. As an application, we propose a new quantum algorithm for rigid regression problems with vector solution outputs. It achieves polynomial speedups over the best classical algorithm known. In this process, we give an improved randomized algorithm for rigid regression.
Abstract（参考訳）: レバレッジスコアのサンプリングは大規模行列問題に対するランダム化アルゴリズムの設計に不可欠であるが、レバレッジスコアの計算は多くのアプリケーションのボトルネックとなっている。本稿では,この有用な手法を高速化する量子アルゴリズムを提案する。スピードアップは少なくとも二次的であり、よく条件付けられた行列に対して指数関数的である。また、いくつかの量子下界を証明し、量子アルゴリズムが最適に近いことを示唆する。応用として,ベクトル解出力を用いた剛性回帰問題に対する新しい量子アルゴリズムを提案する。既知の最良の古典的アルゴリズムよりも多項式の高速化を実現する。この過程で、剛性回帰のための改良されたランダム化アルゴリズムを与える。

関連論文リスト

Quantum Speedup for Sampling Random Spanning Trees [2.356162747014486]
我々は、$widetildeO(sqrtmn)$ timeの重み付きグラフからランダムスパンニング木をサンプリングする量子アルゴリズムを提案する。我々のアルゴリズムは、高密度グラフのサブ線形ランタイムを持ち、よく知られた古典的アルゴリズムの量子スピードアップを実現する。
論文参考訳（メタデータ） (2025-04-22T05:45:04Z)
Fast Expectation Value Calculation Speedup of Quantum Approximate Optimization Algorithm: HoLCUs QAOA [55.2480439325792]
本稿では,LCU演算子の線形結合として表現できる演算子の期待値を計算するための新しい手法を提案する。この方法は任意の量子アルゴリズムに対して一般的であり、変分量子アルゴリズムの加速に特に関心がある。
論文参考訳（メタデータ） (2025-03-03T17:15:23Z)
Quantum multi-row iteration algorithm for linear systems with non-square coefficient matrices [7.174256268278207]
古典的マルチロー反復法に着想を得た量子アルゴリズムを提案する。本アルゴリズムは,不整合系の解法に適した係数行列の要求を小さくする。
論文参考訳（メタデータ） (2024-09-06T03:32:02Z)
Generalized quantum Arimoto-Blahut algorithm and its application to quantum information bottleneck [55.22418739014892]
量子アリーモト・ブラフトアルゴリズムをRamakrishnanらにより一般化する。 3つの量子系を持つ量子情報ボトルネックに対して,我々のアルゴリズムを適用した。数値解析により,我々のアルゴリズムはアルゴリズムよりも優れていることが示された。
論文参考訳（メタデータ） (2023-11-19T00:06:11Z)
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 Levenberg--Marquardt Algorithm for optimization in Bundle Adjustment [0.0]
本稿では,正規方程式の線形系を解くための量子アルゴリズムを実装し,レバンス-マルカールトの最適化ステップを計算する。提案した量子アルゴリズムは、点数に関して、この演算の複雑さを劇的に低減する。
論文参考訳（メタデータ） (2022-03-04T13:38:21Z)
Quantum algorithm for stochastic optimal stopping problems with applications in finance [60.54699116238087]
有名な最小二乗モンテカルロ (LSM) アルゴリズムは、線形最小二乗回帰とモンテカルロシミュレーションを組み合わせることで、最適停止理論の問題を解決する。プロセスへの量子アクセス、最適な停止時間を計算するための量子回路、モンテカルロの量子技術に基づく量子LSMを提案する。
論文参考訳（メタデータ） (2021-11-30T12:21:41Z)
An optimal quantum sampling regression algorithm for variational eigensolving in the low qubit number regime [0.0]
量子サンプリング回帰(QSR)は、代替の量子古典的アルゴリズムである。低量子ビット数構造における時間的複雑さに基づいて,その利用事例を分析した。ベンチマーク問題に対するアルゴリズムの有効性を示す。
論文参考訳（メタデータ） (2020-12-04T00:01:15Z)
Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra [53.46106569419296]
我々は、リコメンダシステムと最小二乗回帰のためのクエリをサポートする古典的な(量子でない)動的データ構造を作成する。これらの問題に対する以前の量子インスパイアされたアルゴリズムは、レバレッジやリッジレベレッジスコアを偽装してサンプリングしていると我々は主張する。
論文参考訳（メタデータ） (2020-11-09T01:13:07Z)
Space-efficient binary optimization for variational computing [68.8204255655161]
本研究では,トラベリングセールスマン問題に必要なキュービット数を大幅に削減できることを示す。また、量子ビット効率と回路深さ効率のモデルを円滑に補間する符号化方式を提案する。
論文参考訳（メタデータ） (2020-09-15T18:17:27Z)

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