論文の概要: Testing quantum satisfiability

• arxiv url: http://arxiv.org/abs/2301.10699v2
• Date: Mon, 06 Jan 2025 19:03:22 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-08 15:47:24.861480
• Title: Testing quantum satisfiability
• Title（参考訳）: 量子充足可能性のテスト
• Authors: Ashley Montanaro, Changpeng Shao, Dominic Verdon,
• Abstract要約: 量子k-SATはランダムな時間で解けることを示す。 まず、量子 k-SAT の充足可能なインスタンスに対して、一定数の量子ビット上のほとんどの部分プロブレムは積状態によって満足できることを示す。 次に、積状態によって満足できない量子 k-SAT のインスタンスの場合、ほとんどのサブプロブレムは積状態によって満足できないことを示す。
• 参考スコア（独自算出の注目度）: 0.0
• License:
• Abstract: Quantum k-SAT (the problem of determining whether a k-local Hamiltonian is frustration-free) is known to be QMA_1-complete for k >= 3, and hence likely hard for quantum computers to solve. Building on a classical result of Alon and Shapira, we show that quantum k-SAT can be solved in randomised polynomial time given the `property testing' promise that the instance is either satisfiable (by any state) or far from satisfiable by a product state; by `far from satisfiable by a product state' we mean that \epsilon n^k constraints must be removed before a product state solution exists, for some fixed \epsilon > 0. The proof has two steps: we first show that for a satisfiable instance of quantum k-SAT, most subproblems on a constant number of qubits are satisfiable by a product state. We then show that for an instance of quantum k-SAT which is far from satisfiable by a product state, most subproblems are unsatisfiable by a product state. Given the promise, quantum k-SAT may therefore be solved by checking satisfiability by a product state on randomly chosen subsystems of constant size.
• Abstract（参考訳）: 量子k-SAT(k-局所ハミルトニアンがフラストレーションフリーかどうかを決定する問題)は、k >= 3 に対して QMA_1-完全であることが知られており、量子コンピュータが解くのが困難である。 Alon と Shapira の古典的な結果に基づいて、ある固定された \epsilon > 0 に対して、量子 k-SAT が無作為多項式時間で解けることを示す。 証明には2つのステップがある: まず、量子 k-SAT の満足できるインスタンスに対して、定数数の量子ビット上のほとんどの部分プロブレムは積状態によって満足できることを示す。 次に、積状態によって満足できない量子 k-SAT のインスタンスの場合、ほとんどのサブプロブレムは積状態によって満足できないことを示す。 したがって、量子k-SATは、一定の大きさのランダムに選択されたサブシステム上の積状態によって満足度をチェックすることで解決することができる。

関連論文リスト

• The PRODSAT phase of random quantum satisfiability [7.5465062534540515]
  k$-QSAT問題は、有名な$k$-SAT制約満足度問題の量子アナログである。 ゼロエネルギーの積状態が高い確率で存在することは、基礎因子グラフが節被覆二量体構成を持つ場合に限る。
  論文  参考訳（メタデータ） (2024-04-29T06:10:45Z)
• The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
  非負の振幅を持つ非絡み合った量子証明のパワー、つまり $textQMA+(2)$ を表すクラスについて研究する。 特に,小集合拡張,ユニークなゲーム,PCP検証のためのグローバルプロトコルを設計する。 QMA(2) が $textQMA+(2)$ に等しいことを示す。
  論文  参考訳（メタデータ） (2024-02-29T01:35:46Z)
• Quantum Approximate Optimisation for Not-All-Equal SAT [9.427635404752936]
  変動量子アルゴリズムのQAOAを、満足度問題(SAT: Not-All-Equal SAT)の変種に適用する。 両ソルバのランタイムは問題サイズとともに指数関数的にスケールするが,QAOAのスケーリングは回路深さが十分に大きい場合に小さくなることを示す。
  論文  参考訳（メタデータ） (2024-01-05T15:11:24Z)
• A Parallel and Distributed Quantum SAT Solver Based on Entanglement and Quantum Teleportation [1.5201992393140886]
  並列量子SATソルバは,線形時間 O(m) から定数時間 O(1) までの繰り返しの時間複雑性を,余分な絡み合った量子ビットを用いて低減する。 我々は、我々のアプローチの正しさを証明し、シミュレーションでそれらを実証した。
  論文  参考訳（メタデータ） (2023-08-07T06:52:06Z)
• Amplitude amplification-inspired QAOA: Improving the success probability for solving 3SAT [55.78588835407174]
  振幅増幅アルゴリズムは、可変代入を満たすために非構造化探索に適用することができる。 Quantum Approximate Optimization Algorithm (QAOA)は、ノイズのある中間量子デバイスのための3SATを解くための有望な候補である。 振幅増幅によるQAOAの変種を導入し、3SATの成功確率を改善する。
  論文  参考訳（メタデータ） (2023-03-02T11:52:39Z)
• Quantum Programming of the Satisfiability Problem with Rydberg Atom Graphs [1.2179548969182574]
  実験では、リドベルク原子を用いて(すなわち、満足度(3-SAT)の問題をプログラムし、解を求める)。
  論文  参考訳（メタデータ） (2023-02-28T07:49:10Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)
• Average-case Speedup for Product Formulas [69.68937033275746]
  製品公式(英: Product formulas)またはトロッター化(英: Trotterization)は、量子系をシミュレートする最も古い方法であり、いまだに魅力的な方法である。 我々は、ほとんどの入力状態に対して、トロッター誤差が定性的に優れたスケーリングを示すことを証明した。 我々の結果は、平均的なケースにおける量子アルゴリズムの研究の扉を開く。
  論文  参考訳（メタデータ） (2021-11-09T18:49:48Z)
• Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
  3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。 本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。 提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
  論文  参考訳（メタデータ） (2021-07-08T17:59:55Z)
• Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
  形状対応を見つけることは、NP-hard quadratic assignment problem (QAP)として定式化できる。 本稿では,アルファ拡大アルゴリズムに触発されたQAPの反復量子法Q-Matchを提案する。 Q-Match は、実世界の問題にスケールできるような長文対応のサブセットにおいて、反復的に形状マッチング問題に適用できる。
  論文  参考訳（メタデータ） (2021-05-06T17:59:38Z)
• Quantum algorithm of a set of quantum 2-sat problem [0.0]
  本稿では,量子2-満足度(Q2SAT)問題に対する量子断熱アルゴリズムを提案する。 Q2SAT 問題に対して、ハイゼンベルク連鎖に類似したハミルトニアンを構成する。
  論文  参考訳（メタデータ） (2020-09-05T21:01:27Z)

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

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