論文の概要: Quantum DPLL and Generalized Constraints in Iterative Quantum Algorithms
- arxiv url: http://arxiv.org/abs/2509.02689v1
- Date: Tue, 02 Sep 2025 18:00:05 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-09-04 21:40:46.294965
- Title: Quantum DPLL and Generalized Constraints in Iterative Quantum Algorithms
- Title（参考訳）: 反復量子アルゴリズムにおける量子DPLLと一般化制約
- Authors: Lucas T. Brady, Stuart Hadfield,
- Abstract要約: 我々は,古典的欲求や局所探索アルゴリズムと密接に関連する,ハイブリッド量子アルゴリズムのクラスを探索する。
そこで我々は,よく知られた古典的デービス・プットナム・ローデマン・ローブランド(DPLL)アルゴリズムのハイブリッド量子バージョンを開発した。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Too often, quantum computer scientists seek to create new algorithms entirely fresh from new cloth when there are extensive and optimized classical algorithms that can be generalized wholesale. At the same time, one may seek to maintain classical advantages of performance and runtime bounds, while enabling potential quantum improvement. Hybrid quantum algorithms tap into this potential, and here we explore a class of hybrid quantum algorithms called Iterative Quantum Algorithms (IQA) that are closely related to classical greedy or local search algorithms, employing a structure where the quantum computer provides information that leads to a simplified problem for future iterations. Specifically, we extend these algorithms beyond past results that considered primarily quadratic problems to arbitrary k-local Hamiltonians, proposing a general framework that incorporates logical inference in a fundamental way. As an application we develop a hybrid quantum version of the well-known classical Davis-Putnam-Logemann-Loveland (DPLL) algorithm for satisfiability problems, which embeds IQAs within a complete backtracking based tree search framework. Our results also provide a general framework for handling problems with hard constraints in IQAs. We further show limiting cases of the algorithms where they reduce to classical algorithms, and provide evidence for regimes of quantum improvement.
- Abstract（参考訳）: 量子コンピュータの科学者たちは、広範で最適化された古典的アルゴリズムが一般化可能な場合、新しい布から完全に新しいアルゴリズムを創り出そうとする。
同時に、パフォーマンスと実行時のバウンダリの古典的なアドバンテージを維持しつつ、潜在的な量子的改善を可能にしようとすることもある。
ここでは、古典的欲求や局所探索アルゴリズムと密接な関係を持つ、Iterative Quantum Algorithms (IQA) と呼ばれるハイブリッド量子アルゴリズムのクラスを探索し、量子コンピュータが将来の反復に単純な問題をもたらす情報を提供する構造を用いる。
具体的には、これらのアルゴリズムを、主に二次的な問題を任意の k-局所ハミルトニアンに拡張し、論理的推論を基本的な方法で組み込んだ一般的なフレームワークを提案する。
アプリケーションとして、よく知られた古典的デービス・プットナム・ローデマン・ローベランド(DPLL)アルゴリズムのハイブリッド量子バージョンを開発し、完全なバックトラックベースツリーサーチフレームワークにIQAsを組み込む。
また, IQAの厳しい制約に対処するための一般的なフレームワークも提供する。
さらに、古典的なアルゴリズムに還元されるアルゴリズムの制限事例を示し、量子改善の状況を示す証拠を提供する。
関連論文リスト
- Quantum Subroutines in Branch-Price-and-Cut for Vehicle Routing [0.0]
この研究で、限られた資源を持つ量子がNPハード問題に対する大規模な正確な最適化アルゴリズムにどのように統合できるかを実証する。
我々のアルゴリズムの重要な特徴は、量子によって返される最良の解からではなく、あるコスト閾値以下の全ての解から得られることである。
論文 参考訳（メタデータ） (2024-12-20T08:27:23Z) - Quantum Subroutine for Variance Estimation: Algorithmic Design and Applications [80.04533958880862]
量子コンピューティングは、アルゴリズムを設計する新しい方法の基礎となる。
どの場の量子スピードアップが達成できるかという新たな課題が生じる。
量子サブルーチンの設計は、従来のサブルーチンよりも効率的で、新しい強力な量子アルゴリズムに固い柱を向ける。
論文 参考訳（メタデータ） (2024-02-26T09:32:07Z) - Quantum algorithms: A survey of applications and end-to-end complexities [88.57261102552016]
期待されている量子コンピュータの応用は、科学と産業にまたがる。
本稿では,量子アルゴリズムの応用分野について検討する。
私たちは、各領域における課題と機会を"エンドツーエンド"な方法で概説します。
論文 参考訳（メタデータ） (2023-10-04T17:53:55Z) - 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) - Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
単一画像超解像(SISR)問題を解くために,量子コンピューティングに基づくアルゴリズムを提案する。
提案したAQCアルゴリズムは、SISRの精度を維持しつつ、古典的なアナログよりも向上したスピードアップを実現する。
論文 参考訳（メタデータ） (2023-04-18T11:57:15Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳（メタデータ） (2022-05-26T20:32:36Z) - Quantum-accelerated constraint programming [0.377986002491873]
Constraint (CP) は制約満足度とプログラミング最適化問題のモデル化と解決に使用されるパラダイムである。
量子アルゴリズムは、推論と探索の両方のレベルでCPを加速することを示す。
論文 参考訳（メタデータ） (2021-03-08T01:29:53Z) - Towards quantum advantage via topological data analysis [0.0]
ロイズ,ガーネロン,ザナルディのトポロジカルデータ解析のためのアルゴリズムの背後にある量子アルゴリズムについて検討する。
ランク推定や複雑なネットワーク解析などの問題に対して,多数の新しい量子アルゴリズムを提供する。
論文 参考訳（メタデータ） (2020-05-06T06:31:24Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。