論文の概要: Solving the semidefinite relaxation of QUBOs in matrix multiplication
time, and faster with a quantum computer
- arxiv url: http://arxiv.org/abs/2301.04237v3
- Date: Thu, 11 May 2023 10:45:58 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-12 18:21:42.598859
- Title: Solving the semidefinite relaxation of QUBOs in matrix multiplication
time, and faster with a quantum computer
- Title（参考訳）: 行列乗算時間におけるQUBOの半定緩和の解法と量子コンピュータによる高速化
- Authors: Brandon Augustino, Giacomo Nannicini, Tam\'as Terlaky and Luis Zuluaga
- Abstract要約: いくつかの量子SDOソルバは、低精度な状態において高速化を提供する。
この事実を利用してアルゴリズムの精度への依存を指数関数的に改善する。
我々のアルゴリズムの量子実装は、$mathcalO left(ns + n1.5 cdot textpolylog left(n, | C |_F, frac1epsilon right)$の最悪の実行時間を示す。
- 参考スコア（独自算出の注目度）: 0.20999222360659603
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Recent works on quantum algorithms for solving semidefinite optimization
(SDO) problems have leveraged a quantum-mechanical interpretation of positive
semidefinite matrices to develop methods that obtain quantum speedups with
respect to the dimension $n$ and number of constraints $m$. While their
dependence on other parameters suggests no overall speedup over classical
methodologies, some quantum SDO solvers provide speedups in the low-precision
regime. We exploit this fact to our advantage, and present an iterative
refinement scheme for the Hamiltonian Updates algorithm of Brand\~ao et al.
(Quantum 6, 625 (2022)) to exponentially improve the dependence of their
algorithm on precision. As a result, we obtain a classical algorithm to solve
the semidefinite relaxation of Quadratic Unconstrained Binary Optimization
problems (QUBOs) in matrix multiplication time. Provided access to a quantum
read/classical write random access memory (QRAM), a quantum implementation of
our algorithm exhibits a worst case running time of $\mathcal{O} \left(ns +
n^{1.5} \cdot \text{polylog} \left(n, \| C \|_F, \frac{1}{\epsilon} \right)
\right)$.
- Abstract（参考訳）: 半定値最適化(SDO)問題を解く量子アルゴリズムに関する最近の研究は、正半定値行列の量子力学的解釈を利用して、次元$n$と制約数$m$に関する量子スピードアップを求める方法を開発した。
他のパラメータへの依存は古典的手法よりも全体的なスピードアップを示さないが、量子SDOソルバによっては低精度な方式でスピードアップを提供する。
我々はこの事実を有利に活用し,brand\~ao et al. (quantum 6, 625 (2022)) のハミルトニアン更新アルゴリズムの反復的改良スキームを提案し,アルゴリズムの精度依存性を指数関数的に改善する。
その結果,行列乗算時間における二次非拘束二元最適化問題 (qubos) の半定義緩和を解く古典的なアルゴリズムが得られる。
量子リード/古典的書き込みランダムアクセスメモリ(QRAM)へのアクセスにより、我々のアルゴリズムの量子実装は、$\mathcal{O} \left(ns + n^{1.5} \cdot \text{polylog} \left(n, \| C \|_F, \frac{1}{\epsilon} \right)$の最悪の実行時間を示す。
関連論文リスト
- Quantum multi-row iteration algorithm for linear systems with non-square coefficient matrices [7.174256268278207]
古典的マルチロー反復法に着想を得た量子アルゴリズムを提案する。
本アルゴリズムは,不整合系の解法に適した係数行列の要求を小さくする。
論文 参考訳（メタデータ） (2024-09-06T03:32:02Z) - 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) - Tensor Decompositions and Adiabatic Quantum Computing for Discovering Practical Matrix Multiplication Algorithms [1.5540058359482858]
本稿では,実用的な行列乗算アルゴリズムの発見と,量子コンピュータ上での分解計算のための2つのアルゴリズムの開発に焦点をあてる。
アルゴリズムは高次非制約バイナリ最適化(HUBO)問題として表現される。
最大分解長よりも短い長さを固定することにより、全体最適化問題の解がより高速な行列乗算アルゴリズムが得られることを示す。
論文 参考訳（メタデータ） (2024-06-19T10:05:57Z) - Quantum Algorithms for the Pathwise Lasso [1.8058773918890538]
古典的LARS(Least Angle Regression)パスワイズアルゴリズムに基づく新しい量子高次元線形回帰アルゴリズムを提案する。
我々の量子アルゴリズムは、ペナルティ項が変化するにつれて、完全な正規化パスを提供するが、特定の条件下では、イテレーション毎に2次的に高速である。
我々は、KKT条件の近似バージョンと双対性ギャップにより、LARSアルゴリズムがエラーに対して堅牢であることを証明した。
論文 参考訳（メタデータ） (2023-12-21T18:57:54Z) - Efficient Quantum Algorithms for Quantum Optimal Control [2.9370710299422607]
本稿では,量子最適制御問題を解くための効率的な量子アルゴリズムを提案する。
本アルゴリズムは,時間依存型ハミルトンシミュレーション法と高速勾配推定アルゴリズムに基づく。
我々の量子アルゴリズムはフォールトトレラントな量子コンピュータを必要とする。
論文 参考訳（メタデータ） (2023-04-05T17:33:57Z) - Quantum speedup of leverage score sampling and its application [0.0]
本稿では,レバレッジスコアの計算を高速化する量子アルゴリズムを提案する。
応用として,ベクトル解出力を用いた剛性回帰問題に対する新しい量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-15T14:40:18Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - Complexity-Theoretic Limitations on Quantum Algorithms for Topological
Data Analysis [59.545114016224254]
トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。
我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。
我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
論文 参考訳（メタデータ） (2022-09-28T17:53:25Z) - 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) - Quantum algorithm for stochastic optimal stopping problems with
applications in finance [60.54699116238087]
有名な最小二乗モンテカルロ (LSM) アルゴリズムは、線形最小二乗回帰とモンテカルロシミュレーションを組み合わせることで、最適停止理論の問題を解決する。
プロセスへの量子アクセス、最適な停止時間を計算するための量子回路、モンテカルロの量子技術に基づく量子LSMを提案する。
論文 参考訳（メタデータ） (2021-11-30T12:21:41Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。