論文の概要: Left-Deep Join Order Selection with Higher-Order Unconstrained Binary Optimization on Quantum Computers

• arxiv url: http://arxiv.org/abs/2502.00362v1
• Date: Sat, 01 Feb 2025 08:00:36 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-05 14:56:31.344762
• Title: Left-Deep Join Order Selection with Higher-Order Unconstrained Binary Optimization on Quantum Computers
• Title（参考訳）: 量子コンピュータ上での高次非拘束二項最適化による左深結合次数選択
• Authors: Valter Uotila,
• Abstract要約: 結合順序最適化は、クエリ最適化の最も重要な問題の一つである。 結合次数最適化のための3つの新しい量子最適化アルゴリズムを提案する。 我々は、結合順序選択のための古典的アルゴリズムと量子的アルゴリズムの間に重要な理論的接続を設定した。
• 参考スコア（独自算出の注目度）: 1.5540058359482858
• License:
• Abstract: Join order optimization is among the most crucial query optimization problems, and its central position is also evident in the new research field where quantum computing is applied to database optimization and data management. In the field, join order optimization is the most studied database problem, usually tackled with a quadratic unconstrained binary optimization model, which is solved with various meta-heuristics such as quantum annealing, quantum approximate optimization algorithm, or variational quantum eigensolver. In this work, we continue developing quantum computing techniques for join order optimization by presenting three novel quantum optimization algorithms. These algorithms are based on a higher-order unconstrained binary optimization model, which is a generalization of the quadratic model and has not previously been applied to database problems. Theoretically, these optimization problems naturally map to universal quantum computers and quantum annealers. Compared to previous research, two of our algorithms are the first quantum algorithms to precisely model the join order cost function. We prove theoretical bounds by showing that these two methods encode the same plans as the dynamic programming algorithm without cross-products, which provides the optimal result up to cross-products. The third algorithm reaches at least as good plans as the greedy algorithm without cross-products. These results set an important theoretical connection between the classical and quantum algorithms for join order selection, which has not been studied in the previous research. To demonstrate our algorithms' practical usability, we have conducted an experimental evaluation on thousands of clique, cycle, star, tree, and chain query graphs using quantum and classical solvers.
• Abstract（参考訳）: 結合順序最適化はクエリ最適化の最も重要な問題の一つであり、その中心的な位置は、データベース最適化やデータ管理に量子コンピューティングを適用する新しい研究分野においても明らかである。 この分野では、結合次数最適化は最も研究されているデータベース問題であり、通常、量子アニール、量子近似最適化アルゴリズム、変分量子固有解法などの様々なメタヒューリスティックで解決される2次非拘束バイナリ最適化モデルに対処する。 本研究では,3つの新しい量子最適化アルゴリズムを提示することにより,結合次数最適化のための量子コンピューティング技術の開発を継続する。 これらのアルゴリズムは2次モデルの一般化であり、これまでデータベース問題には適用されていなかった高次非制約バイナリ最適化モデルに基づいている。 理論的には、これらの最適化問題は自然に普遍的な量子コンピュータや量子アニールにマップされる。 これまでの研究では、2つのアルゴリズムが結合順序のコスト関数を正確にモデル化した最初の量子アルゴリズムであった。 我々は,これらの2つの手法が,クロスプロデューサを含まない動的プログラミングアルゴリズムと同じ計画を符号化し,クロスプロデューサに最適な結果を与えることを示すことによって理論的境界を証明した。 第3のアルゴリズムは、クロスプロダクティヴなアルゴリズムよりも少なくとも良い計画に達する。 これらの結果は、結合次数選択のための古典的アルゴリズムと量子的アルゴリズムの間に重要な理論的関係を定めているが、これは以前の研究では研究されていない。 提案アルゴリズムの実用的なユーザビリティを実証するため,量子および古典的解法を用いて,数千の傾き,サイクル,スター,ツリー,チェーンクエリグラフを実験的に評価した。

関連論文リスト

• Provably Faster Algorithms for Bilevel Optimization via Without-Replacement Sampling [96.47086913559289]
  勾配に基づくアルゴリズムはバイレベル最適化に広く用いられている。 本研究では,より高速な収束率を実現する非置換サンプリングに基づくアルゴリズムを提案する。 合成および実世界の両方のアプリケーションに対してアルゴリズムを検証する。
  論文  参考訳（メタデータ） (2024-11-07T17:05:31Z)
• 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)
• 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)
• Randomized Benchmarking of Local Zeroth-Order Optimizers for Variational Quantum Systems [65.268245109828]
  古典学のパフォーマンスを、半ランダム化された一連のタスクで比較する。 量子システムにおける一般に好適な性能とクエリ効率のため、局所ゼロ階数に着目する。
  論文  参考訳（メタデータ） (2023-10-14T02:13:26Z)
• Iterative Quantum Algorithms for Maximum Independent Set: A Tale of Low-Depth Quantum Algorithms [0.0]
  我々は、反復最大量子アルゴリズム(Iterative Maximum Quantum Algorithms)と呼ばれる、量子最適化のための新しいハイブリッドアプローチのクラスについて研究する。 深度$p=1$のQAOAの場合、このアルゴリズムはMISの古典的欲求アルゴリズムと全く同じ操作と選択を行う。
  論文  参考訳（メタデータ） (2023-09-22T18:00:03Z)
• Classically-Boosted Quantum Optimization Algorithm [0.0]
  我々は、量子最適化を強化するために既存の古典的手法を活用する自然なアプローチを探求する。 具体的には、近似解を見つけるために古典的なアルゴリズムを実行し、量子回路を用いて高品質な解の「近傍」を探索する。 CBQOA の Max 3SAT および Max Bisection への応用を実証し,これらの問題に対する従来のアプローチよりも優れていることを示す実証的証拠を提供する。
  論文  参考訳（メタデータ） (2022-03-25T23:36:14Z)
• Stochastic optimization algorithms for quantum applications [0.0]
  本稿では、一階法、二階法、量子自然勾配最適化法の使用法を概観し、複素数体で定義される新しいアルゴリズムを提案する。 全ての手法の性能は、変分量子固有解法、量子状態の量子制御、および量子状態推定に応用して評価される。
  論文  参考訳（メタデータ） (2022-03-11T16:17:05Z)
• Variational Quantum Optimization with Multi-Basis Encodings [62.72309460291971]
  マルチバスグラフ複雑性と非線形活性化関数の2つの革新の恩恵を受ける新しい変分量子アルゴリズムを導入する。 その結果,最適化性能が向上し,有効景観が2つ向上し,測定の進歩が減少した。
  論文  参考訳（メタデータ） (2021-06-24T20:16:02Z)
• Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
  バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。 両レベル最適化のための2つの新しいアルゴリズムを提案する。 両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
  論文  参考訳（メタデータ） (2021-06-08T21:05:30Z)
• Warm-starting quantum optimization [6.832341432995627]
  最適化問題の緩和解に対応する初期状態を用いて量子最適化を温める方法について論じる。 これにより、量子アルゴリズムは古典的なアルゴリズムの性能保証を継承することができる。 同じ考えを他のランダム化ラウンドスキームや最適化問題に適用するのは簡単である。
  論文  参考訳（メタデータ） (2020-09-21T18:00:09Z)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  本研究では,トラベリングセールスマン問題に必要なキュービット数を大幅に削減できることを示す。 また、量子ビット効率と回路深さ効率のモデルを円滑に補間する符号化方式を提案する。
  論文  参考訳（メタデータ） (2020-09-15T18:17:27Z)

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

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