論文の概要: A measurement-driven quantum algorithm for SAT: Performance guarantees via spectral gaps and measurement parallelization

• arxiv url: http://arxiv.org/abs/2511.09647v1
• Date: Fri, 14 Nov 2025 01:02:16 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-14 22:53:22.389883
• Title: A measurement-driven quantum algorithm for SAT: Performance guarantees via spectral gaps and measurement parallelization
• Title（参考訳）: SATのための測定駆動量子アルゴリズム:スペクトルギャップと測定並列化による性能保証
• Authors: Franz J. Schreiber, Maximilian J. Kramer, Alexander Nietner, Jens Eisert,
• Abstract要約: この研究は、測定駆動量子SATソルバの厳密な最悪の実行時解析を示す。 この量子アルゴリズムはGrover型法にのみ依存せず,有望な数値性能を示す。 また,複数のタスクを満足するインスタンスに対しても,効率的に解を見つける新しい読み出しルーチンを開発した。
• 参考スコア（独自算出の注目度）: 39.146761527401424
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The Boolean satisfiability problem (SAT) is of central importance in both theory and practice. Yet, most provable guarantees for quantum algorithms rely exclusively on Grover-type methods that cap the possible advantage at only quadratic speed-ups, making the search for approaches that surpass this quadratic barrier a key challenge. In this light, this work presents a rigorous worst-case runtime analysis of a recently introduced measurement-driven quantum SAT solver. Importantly, this quantum algorithm does not exclusively rely on Grover-type methods and shows promising numerical performance. Our analysis establishes that the algorithm's runtime depends on an exponential trade-off between two key properties: the spectral gap of the associated Hamiltonian and the success probability of the driving measurements. We show that this trade-off can be systematically controlled by a tunable rotation angle. Beyond establishing a worst-case runtime expression, this work contributes significant algorithmic improvements. First, we develop a new readout routine that efficiently finds a solution even for instances with multiple satisfying assignments. Second, a measurement parallelization scheme, based on perfect hash families, is introduced. Third, we establish an amplitude-amplified version of the measurement-driven algorithm. Finally, we demonstrate the practical utility of our framework: By suitably scheduling the algorithm's parameters, we show that its runtime collapses from exponential to polynomial on a special class of SAT instances, consistent with their known classical tractability. A problem we leave open is to establish a non-trivial lower bound on the spectral gap as a function of the rotation angle. Resolving this directly translates into an improved worst-case runtime, potentially realizing a super-quadratic quantum advantage.
• Abstract（参考訳）: ブール充足可能性問題(SAT)は理論と実践の両方において重要な問題である。 しかし、量子アルゴリズムの最も証明可能な保証は、この二次的障壁を超えるアプローチを探索することが重要な課題である。 本研究は、最近導入された測定駆動量子SATソルバの厳密な最悪の実行時解析を示す。 重要なことに、この量子アルゴリズムはグローバー型法にのみ依存せず、有望な数値性能を示している。 解析により、アルゴリズムのランタイムは、関連するハミルトニアンのスペクトルギャップと駆動測定の成功確率の2つの重要な性質の間の指数的トレードオフに依存することが判明した。 このトレードオフは、調整可能な回転角によって体系的に制御可能であることを示す。 最悪の実行時表現の確立以外にも、この作業はアルゴリズムの大幅な改善に貢献している。 まず,複数のタスクを満足するインスタンスに対しても効率的に解を見つける新しい読み出しルーチンを開発する。 第二に、完全ハッシュ族に基づく測定並列化方式を導入する。 第3に、測定駆動アルゴリズムの振幅増幅版を確立する。 アルゴリズムのパラメータを適切にスケジューリングすることにより、その実行時がSATインスタンスの特別なクラスで指数関数から多項式に崩壊し、既知の古典的トラクタビリティと整合することを示す。 開き放たれた問題は、回転角の関数としてスペクトルギャップ上の非自明な下界を確立することである。 この問題の解決は、改善された最悪の実行環境へと直接変換され、超四重項量子優位性を実現する可能性がある。

関連論文リスト

• Learning Feasible Quantum States for Quadratic Constrained Binary Optimization Problems [41.23247424467223]
  我々はQCBOの制約を満たす量子状態の同値重ね合わせを生成する変動的アプローチを開発する。 結果として生じる同値な重ね合わせは、QUBO/QCBOを解く量子アルゴリズムの初期状態として使用できる。
  論文  参考訳（メタデータ） (2025-08-04T16:44:53Z)
• Solving quadratic binary optimization problems using quantum SDP methods: Non-asymptotic running time analysis [1.9081120388919084]
  量子コンピュータは、最先端の古典的手法よりも優れたスケールのリソースを用いて、半定値プログラム(SDP)を解くことができる。 本稿では,量子SDPソルバの非漸近的リソース要求の解析を行う。
  論文  参考訳（メタデータ） (2025-02-21T12:54:05Z)
• Provable Scaling Laws for the Test-Time Compute of Large Language Models [84.00141420901038]
  本研究では,大規模言語モデルのテスト時間計算において,証明可能なスケーリング法則を享受する2つのアルゴリズムを提案する。 1つは2段階ノックアウト方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。 もう1つは2段階のリーグ方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。
  論文  参考訳（メタデータ） (2024-11-29T05:29:47Z)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  本稿では,n+1$ qubitsしか使用しないGoemans-Williamsonアルゴリズムの変分量子アルゴリズムを提案する。 補助量子ビット上で適切にパラメータ化されたユニタリ条件として目的行列を符号化することにより、効率的な最適化を実現する。 各種NPハード問題に対して,Goemans-Williamsonアルゴリズムの量子的効率的な実装を考案し,提案プロトコルの有効性を実証する。
  論文  参考訳（メタデータ） (2022-06-30T03:15:23Z)
• Quantifying Grover speed-ups beyond asymptotic analysis [0.0]
  古典的なエミュレーションと、すべての定数を含む詳細な複雑性境界を組み合わせたアプローチを考える。 本手法を古典的アルゴリズムの単純量子スピードアップに適用し,よく研究されたMAX-$k$-SAT最適化問題を解く。 これは、2つの重要な量子サブルーチンの期待と最悪のケースの複雑さに厳密な境界(全定数を含む)を必要とする。
  論文  参考訳（メタデータ） (2022-03-09T19:00:00Z)
• Near-term Efficient Quantum Algorithms for Entanglement Analysis [5.453850739960517]
  絡み合いは量子物理学において重要な役割を担い、量子情報処理の鍵となる資源である。 本研究は、この困難に対処するために、ハイブリッド量子古典的手法を利用した3つの短期的効率的なアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-09-22T15:15:58Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。 本研究の結果は, 同時一次および二重側収束の形で表される。
  論文  参考訳（メタデータ） (2020-08-23T20:36:49Z)
• Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
  離散値のランダムフィールドにおけるMAP推論の最大化は、機械学習の基本的な問題である。 この問題の難しさから、特殊メッセージパッシングアルゴリズムの導出には線形プログラミング(LP)緩和が一般的である。 古典的加速勾配の根底にある手法を活用することにより,これらのアルゴリズムを高速化するランダム化手法を提案する。
  論文  参考訳（メタデータ） (2020-07-01T18:43:32Z)

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

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