論文の概要: Quantum algorithm for large-scale market equilibrium computation

• arxiv url: http://arxiv.org/abs/2405.13788v2
• Date: Thu, 31 Oct 2024 11:37:46 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-01 16:56:35.885332
• Title: Quantum algorithm for large-scale market equilibrium computation
• Title（参考訳）: 大規模市場均衡計算のための量子アルゴリズム
• Authors: Po-Wei Huang, Patrick Rebentrost,
• Abstract要約: サブ線形性能を持つ市場均衡計算のための最初の量子ランタイムアルゴリズムを提供する。 提案アルゴリズムは,従来のアルゴリズムと客観的な最適化値に到達しつつ,購入者数や商品数の観点からも,実行時の高速化を実現する。
• 参考スコア（独自算出の注目度）: 0.9208007322096533
• License:
• Abstract: Classical algorithms for market equilibrium computation such as proportional response dynamics face scalability issues with Internet-based applications such as auctions, recommender systems, and fair division, despite having an almost linear runtime in terms of the product of buyers and goods. In this work, we provide the first quantum algorithm for market equilibrium computation with sub-linear performance. Our algorithm provides a polynomial runtime speedup in terms of the product of the number of buyers and goods while reaching the same optimization objective value as the classical algorithm. Numerical simulations of a system with 16384 buyers and goods support our theoretical results that our quantum algorithm provides a significant speedup.
• Abstract（参考訳）: 比例応答ダイナミクスのような市場均衡計算のための古典的アルゴリズムは、買い手や商品の製品に関してほぼ線形のランタイムを持つにもかかわらず、オークション、レコメンダシステム、公正な分割といったインターネットベースのアプリケーションでスケーラビリティの問題に直面している。 本研究では,サブ線形性能を持つ市場均衡計算のための最初の量子アルゴリズムを提案する。 提案アルゴリズムは,従来のアルゴリズムと同じ最適化目標値に達しながら,購入者数や商品数の観点から多項式実行時の高速化を実現する。 16384の買い手と商品を持つシステムの数値シミュレーションは、我々の量子アルゴリズムが重要なスピードアップを提供するという理論的結果を支持する。

関連論文リスト

• Performance Benchmarking of Quantum Algorithms for Hard Combinatorial Optimization Problems: A Comparative Study of non-FTQC Approaches [0.0]
  本研究は、4つの異なる最適化問題にまたがっていくつかの非フォールト耐性量子コンピューティングアルゴリズムを体系的にベンチマークする。 我々のベンチマークには、変分量子固有解法など、ノイズの多い中間スケール量子(NISQ)アルゴリズムが含まれている。 以上の結果から,FTQC以外のアルゴリズムは全ての問題に対して最適に動作しないことが明らかとなり,アルゴリズム戦略の調整の必要性が浮き彫りになった。
  論文  参考訳（メタデータ） (2024-10-30T08:41:29Z)
• A Quadratic Speedup in Finding Nash Equilibria of Quantum Zero-Sum Games [102.46640028830441]
  最適行列乗算重み更新(OMMWU)アルゴリズムを導入し,平均収束複雑性を$mathcalO(d/epsilon)$ to $epsilon$-Nash equilibriaとする。 この二次的なスピードアップは、量子ゼロサムゲームにおける$epsilon$-Nash平衡の計算のための新しいベンチマークを定めている。
  論文  参考訳（メタデータ） (2023-11-17T20:38:38Z)
• Efficient DCQO Algorithm within the Impulse Regime for Portfolio Optimization [41.94295877935867]
  本稿では,デジタルカウンセバティック量子最適化(DCQO)パラダイムを用いて,ポートフォリオ最適化のための高速なディジタル量子アルゴリズムを提案する。 提案手法は,アルゴリズムの回路深度要件を特に低減し,解の精度を向上し,現在の量子プロセッサに適している。 我々は,IonQトラップイオン量子コンピュータ上で最大20量子ビットを使用するプロトコルの利点を実験的に実証した。
  論文  参考訳（メタデータ） (2023-08-29T17:53:08Z)
• Quantum speedup for combinatorial optimization with flat energy landscapes [0.0]
  我々は,最適化された量子断熱アルゴリズムと古典マルコフ連鎖モンテカルロアルゴリズムの相対的性能を解析するための理論的枠組みを開発する。
  論文  参考訳（メタデータ） (2023-06-22T18:00:00Z)
• Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
  単一画像超解像(SISR)問題を解くために,量子コンピューティングに基づくアルゴリズムを提案する。 提案したAQCアルゴリズムは、SISRの精度を維持しつつ、古典的なアナログよりも向上したスピードアップを実現する。
  論文  参考訳（メタデータ） (2023-04-18T11:57:15Z)
• Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
  我々は3つのハイブリッド量子k-Meansアルゴリズムを設計、実装、評価する。 我々は距離の計算を高速化するために量子現象を利用する。 我々は、我々のハイブリッド量子k-平均アルゴリズムが古典的バージョンよりも効率的であることを示す。
  論文  参考訳（メタデータ） (2022-12-13T16:04:16Z)
• Quantum algorithm for stochastic optimal stopping problems with applications in finance [60.54699116238087]
  有名な最小二乗モンテカルロ (LSM) アルゴリズムは、線形最小二乗回帰とモンテカルロシミュレーションを組み合わせることで、最適停止理論の問題を解決する。 プロセスへの量子アクセス、最適な停止時間を計算するための量子回路、モンテカルロの量子技術に基づく量子LSMを提案する。
  論文  参考訳（メタデータ） (2021-11-30T12:21:41Z)
• Quantum algorithms for quantum dynamics: A performance study on the spin-boson model [68.8204255655161]
  量子力学シミュレーションのための量子アルゴリズムは、伝統的に時間進化作用素のトロッター近似の実装に基づいている。 変分量子アルゴリズムは欠かせない代替手段となり、現在のハードウェア上での小規模なシミュレーションを可能にしている。 量子ゲートコストが明らかに削減されているにもかかわらず、現在の実装における変分法は量子的優位性をもたらすことはありそうにない。
  論文  参考訳（メタデータ） (2021-08-09T18:00:05Z)
• Towards quantum advantage via topological data analysis [0.0]
  ロイズ,ガーネロン,ザナルディのトポロジカルデータ解析のためのアルゴリズムの背後にある量子アルゴリズムについて検討する。 ランク推定や複雑なネットワーク解析などの問題に対して,多数の新しい量子アルゴリズムを提供する。
  論文  参考訳（メタデータ） (2020-05-06T06:31:24Z)
• Approximating the quantum approximate optimization algorithm with digital-analog interactions [0.0]
  ディジタルアナログパラダイムは変分量子近似最適化アルゴリズムに適していることを示す。 我々は,変分アルゴリズムが非変分アルゴリズムよりも有意な改善をもたらす,単一キュービット演算速度のレギュレーションを観察する。
  論文  参考訳（メタデータ） (2020-02-27T16:01:40Z)

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

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