論文の概要: Quantum algorithm of a set of quantum 2-sat problem
- arxiv url: http://arxiv.org/abs/2009.02600v2
- Date: Sat, 31 Oct 2020 15:38:43 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-03 18:41:47.845051
- Title: Quantum algorithm of a set of quantum 2-sat problem
- Title(参考訳): 量子 2-sat 問題の集合の量子アルゴリズム
- Authors: Yanglin Hu, Zhelun Zhang, Biao Wu
- Abstract要約: 本稿では,量子2-満足度(Q2SAT)問題に対する量子断熱アルゴリズムを提案する。
Q2SAT 問題に対して、ハイゼンベルク連鎖に類似したハミルトニアンを構成する。
- 参考スコア(独自算出の注目度): 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We present a quantum adiabatic algorithm for a set of quantum
2-satisfiability (Q2SAT) problem, which is a generalization of 2-satisfiability
(2SAT) problem. For a Q2SAT problem, we construct the Hamiltonian which is
similar to that of a Heisenberg chain. All the solutions of the given Q2SAT
problem span the subspace of the degenerate ground states. The Hamiltonian is
adiabatically evolved so that the system stays in the degenerate subspace. Our
numerical results suggest that the time complexity of our algorithm is
$O(n^{3.9})$ for yielding non-trivial solutions for problems with the number of
clauses $m=dn(n-1)/2\ (d\lesssim 0.1)$. We discuss the advantages of our
algorithm over the known quantum and classical algorithms.
- Abstract(参考訳): 2-satisfiability (2sat) 問題の一般化である量子2-satisfiability (q2sat) 問題に対する量子断熱アルゴリズムを提案する。
Q2SAT 問題に対して、ハイゼンベルク連鎖に類似したハミルトニアンを構成する。
与えられたQ2SAT問題のすべての解は退化基底状態の部分空間にまたがる。
ハミルトニアンは、システムが退化部分空間に留まるように、断続的に進化する。
我々の数値的な結果から、我々のアルゴリズムの時間複雑性は$O(n^{3.9})$であり、$m=dn(n-1)/2\ (d\lesssim 0.1)$である。
既知の量子および古典的アルゴリズムに対するアルゴリズムの利点について議論する。
関連論文リスト
- Quantum Approximate Optimisation for Not-All-Equal SAT [9.427635404752936]
変動量子アルゴリズムのQAOAを、満足度問題(SAT: Not-All-Equal SAT)の変種に適用する。
両ソルバのランタイムは問題サイズとともに指数関数的にスケールするが,QAOAのスケーリングは回路深さが十分に大きい場合に小さくなることを示す。
論文 参考訳(メタデータ) (2024-01-05T15:11:24Z) - Generalized quantum Arimoto-Blahut algorithm and its application to
quantum information bottleneck [55.22418739014892]
量子アリーモト・ブラフトアルゴリズムをRamakrishnanらにより一般化する。
3つの量子系を持つ量子情報ボトルネックに対して,我々のアルゴリズムを適用した。
数値解析により,我々のアルゴリズムはアルゴリズムよりも優れていることが示された。
論文 参考訳(メタデータ) (2023-11-19T00:06:11Z) - Quantum optimization algorithm based on multistep quantum computation [0.0]
本稿では,多段階量子計算に基づく関数の最小値を求める量子アルゴリズムを提案する。
このアルゴリズムでは、問題の探索空間の次元を指数関数的に段階的に減らすことができる。
連続的なテスト関数のアルゴリズムを検証した。
論文 参考訳(メタデータ) (2023-06-30T01:58:23Z) - A hybrid Quantum proposal to deal with 3-SAT problem [75.38606213726906]
本稿では,3SAT問題を解くためのハイブリッド量子コンピューティング戦略について述べる。
この近似の性能は、量子コンピューティングの観点から3-SATを扱う際に、一連の代表的なシナリオで検証されている。
論文 参考訳(メタデータ) (2023-06-07T12:19:22Z) - Logarithmic-Regret Quantum Learning Algorithms for Zero-Sum Games [7.962205145083434]
ゲーム設定下において,$tilde O(1)$ regret のゼロサムゲームに対する最初のオンライン量子アルゴリズムを提案する。
我々の量子アルゴリズムは、量子時間で$varepsilon$-approximate Nash平衡の$m倍n$行列ゼロサムゲームを計算する。
論文 参考訳(メタデータ) (2023-04-27T14:02:54Z) - 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) - Reflection-Based Adiabatic State Preparation [0.0]
我々のアルゴリズムは、断熱スケジュールに沿って定義された瞬時ハミルトンの固有空間から決定される一連の反射をデプロイする。
我々は,探索問題に対して,アルゴリズムがGroverの探索よりも高速に解を見つけることができることを示す数値的な証拠を提供する。
論文 参考訳(メタデータ) (2021-11-10T00:03:00Z) - Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。
本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。
提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
論文 参考訳(メタデータ) (2021-07-08T17:59:55Z) - On Applying the Lackadaisical Quantum Walk Algorithm to Search for
Multiple Solutions on Grids [63.75363908696257]
不足量子ウォーク(英: lackadaisical quantum walk)は、頂点が重量$l$の自己ループを持つグラフ構造を探索するために開発されたアルゴリズムである。
本稿では,グリッド上の複数解の探索に不連続な量子ウォークを適用した際の問題に対処する。
論文 参考訳(メタデータ) (2021-06-11T09:43:09Z) - Limits of quantum speed-ups for computational geometry and other
problems: Fine-grained complexity via quantum walks [0.0]
いくつかの計算問題に対して、量子アルゴリズムの時間的複雑さを最適に下界として証明する。
我々の下界のほとんどは、既知の上界と一致しているため、量子スピードアップに厳しい制限が課せられるため、最適である。
論文 参考訳(メタデータ) (2021-06-03T17:22:08Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。