論文の概要: A Parallel and Distributed Quantum SAT Solver Based on Entanglement and Quantum Teleportation

• arxiv url: http://arxiv.org/abs/2308.03344v1
• Date: Mon, 7 Aug 2023 06:52:06 GMT
• ステータス: 処理完了
• システム内更新日: 2023-08-08 14:52:42.959881
• Title: A Parallel and Distributed Quantum SAT Solver Based on Entanglement and Quantum Teleportation
• Title（参考訳）: 絡み合いと量子テレポーテーションに基づく並列分散量子SATソルバ
• Authors: Shang-Wei Lin, Tzu-Fan Wang, Yean-Ru Chen, Zhe Hou, David San\'an, Yon Shin Teo
• Abstract要約: 並列量子SATソルバは,線形時間 O(m) から定数時間 O(1) までの繰り返しの時間複雑性を,余分な絡み合った量子ビットを用いて低減する。 我々は、我々のアプローチの正しさを証明し、シミュレーションでそれらを実証した。
• 参考スコア（独自算出の注目度）: 1.5201992393140886
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Boolean satisfiability (SAT) solving is a fundamental problem in computer science. Finding efficient algorithms for SAT solving has broad implications in many areas of computer science and beyond. Quantum SAT solvers have been proposed in the literature based on Grover's algorithm. Although existing quantum SAT solvers can consider all possible inputs at once, they evaluate each clause in the formula one by one sequentially, making the time complexity O(m) -- linear to the number of clauses m -- per Grover iteration. In this work, we develop a parallel quantum SAT solver, which reduces the time complexity in each iteration from linear time O(m) to constant time O(1) by utilising extra entangled qubits. To further improve the scalability of our solution in case of extremely large problems, we develop a distributed version of the proposed parallel SAT solver based on quantum teleportation such that the total qubits required are shared and distributed among a set of quantum computers (nodes), and the quantum SAT solving is accomplished collaboratively by all the nodes. We have proved the correctness of our approaches and demonstrated them in simulations.
• Abstract（参考訳）: boolean satisfiability (sat) はコンピュータ科学における根本的な問題である。 SAT問題解決のための効率的なアルゴリズムを見つけることは、コンピュータ科学など多くの分野において幅広い意味を持つ。 量子SATソルバはGroverのアルゴリズムに基づく文献で提案されている。 既存の量子satソルバは、全ての可能な入力を一度に考慮することができるが、式の各節を1つずつ順次評価し、時間複雑性o(m) -- グルーバー反復当たりの節数に線形である。 本研究では,線形時間 o(m) から定数時間 o(1) への各イテレーションの時間複雑性を,余剰エンタングル量子ビットを用いて削減する並列量子satソルバを開発した。 極端に大きな問題が発生した場合、我々のソリューションのスケーラビリティをさらに向上するため、提案した並列SATソルバの分散バージョンを量子テレポーテーションに基づいて開発し、必要な全量子ビットを複数の量子コンピュータ(ノード)間で共有分散し、量子SATソルバを全ノードで協調的に実現した。 我々は、我々のアプローチの正しさを証明し、シミュレーションでそれらを実証した。

関連論文リスト

• Quantum Approximate Optimisation for Not-All-Equal SAT [9.427635404752936]
  変動量子アルゴリズムのQAOAを、満足度問題(SAT: Not-All-Equal SAT)の変種に適用する。 両ソルバのランタイムは問題サイズとともに指数関数的にスケールするが,QAOAのスケーリングは回路深さが十分に大きい場合に小さくなることを示す。
  論文  参考訳（メタデータ） (2024-01-05T15:11:24Z)
• Quantum algorithms: A survey of applications and end-to-end complexities [90.05272647148196]
  期待されている量子コンピュータの応用は、科学と産業にまたがる。 本稿では,量子アルゴリズムの応用分野について検討する。 私たちは、各領域における課題と機会を"エンドツーエンド"な方法で概説します。
  論文  参考訳（メタデータ） (2023-10-04T17:53:55Z)
• Machine Learning for SAT: Restricted Heuristics and New Graph Representations [0.8870188183999854]
  SATは、自動スケジューリングを含む多くのアプリケーションにおいて、基本的なNP完全問題である。 大きなインスタンスを解決するためには、SATソルバは、例えばDPLLとCDCLソルバの分岐変数を選択するなど、ブールアンに依存する必要がある。 我々は、訓練されたMLモデルでいくつかの初期ステップを行い、古典的なランタイムに制御をリリースする戦略を提案する。
  論文  参考訳（メタデータ） (2023-07-18T10:46:28Z)
• A hybrid Quantum proposal to deal with 3-SAT problem [75.38606213726906]
  本稿では,3SAT問題を解くためのハイブリッド量子コンピューティング戦略について述べる。 この近似の性能は、量子コンピューティングの観点から3-SATを扱う際に、一連の代表的なシナリオで検証されている。
  論文  参考訳（メタデータ） (2023-06-07T12:19:22Z)
• Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
  我々は3つのハイブリッド量子k-Meansアルゴリズムを設計、実装、評価する。 我々は距離の計算を高速化するために量子現象を利用する。 我々は、我々のハイブリッド量子k-平均アルゴリズムが古典的バージョンよりも効率的であることを示す。
  論文  参考訳（メタデータ） (2022-12-13T16:04:16Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)
• Polynomial T-depth Quantum Solvability of Noisy Binary Linear Problem: From Quantum-Sample Preparation to Main Computation [0.0]
  雑音二元線形問題(NBLP)の量子可解性について完全解析する。 NBLPの解くコストは、指数関数的に増大する論理量子ビットを犠牲にして、問題の規模で解決できることが示される。
  論文  参考訳（メタデータ） (2021-09-23T07:46:20Z)
• Transformer-based Machine Learning for Fast SAT Solvers and Logic Synthesis [63.53283025435107]
  CNFベースのSATとMaxSATは論理合成と検証システムの中心である。 そこで本研究では,Transformerアーキテクチャから派生したワンショットモデルを用いて,MaxSAT問題の解法を提案する。
  論文  参考訳（メタデータ） (2021-07-15T04:47:35Z)
• Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
  3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。 本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。 提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
  論文  参考訳（メタデータ） (2021-07-08T17:59:55Z)
• Quantum verification of NP problems with single photons and linear optics [14.092977584342378]
  量子検証アルゴリズムは古典的なビット列ではなく量子ビットに解を符号化する。 チューナブルな光学装置を用いることで、満足できるSATインスタンスと不満足なSATインスタンスを効率よく検証する。 我々の結果は、本質的に量子優位性への新たな経路を開き、光学量子コンピューティングの計算能力を拡張する。
  論文  参考訳（メタデータ） (2020-08-12T17:37:22Z)

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

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