論文の概要: On Multi-Constrained Path Finding utilizing Grover Search and Decoded Quantum Interferometry
- arxiv url: http://arxiv.org/abs/2611.15794v1
- Date: Wed, 11 Nov 2026 18:08:14 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-11-14 01:36:33.246847
- Title: On Multi-Constrained Path Finding utilizing Grover Search and Decoded Quantum Interferometry
- Title(参考訳): グローバー探索とデコード量子干渉計を用いた多重制約経路探索について
- Abstract要約: 我々はIBM Heronプロセッサ上で2つのバイナリインスタンスを実行し、一様サンプリングよりも67%と15%の理想的なゲインを保持する。
ノード非依存の線形重みを持つステージドファブリックでは、満足度を最大化することは最大LINSATである。
- 参考スコア(独自算出の注目度): 0.0
- License: http://creativecommons.org/publicdomain/zero/1.0/
- Abstract: Finding a path whose totals under several additive metrics all fall inside prescribed ranges is weakly NP-complete. We ask what two quantum algorithms can do for it, against strong classical baselines. For directed acyclic graphs (DAGs) we give a Grover search whose state preparation builds the uniform superposition over all source-to-destination paths with one qubit per arc and no ancilla. We prove it correct, give its exact gate count, and show that measured strings form an error- detecting code whose distance is a girth-like graph parameter. We complete the oracle and count its gates: one search on our largest instance, 136 arc qubits and 262,144 paths, needs about 4.4 x 10^5 Toffoli gates, while classical dynamic programming decides the same instance with 18,754 labels. Grover search needs O(sqrt(N/M)) oracle calls for M good paths among N . Classical meet-in-the-middle matches this exponent in the worst case, and known quantum algorithms with quantum memory beat it. For a staged fabric with node-independent linear weights, maximizing the number of satisfied metrics is max-LINSAT, and with power- of-index weights it is Optimal Polynomial Intersection, where no known polynomial-time classical algorithm matches decoded quantum interferometry (DQI). We verify this translation in simulation and run two small binary instances on IBM Heron processors, which keep 67 % and 15 % of the ideal gain over uniform sampling.
- Abstract(参考訳): 複数の加法的指標の下にある経路を見つけることは、すべて所定の範囲内にあるが、NP完全である。
我々は、2つの量子アルゴリズムがそれに対して何ができるかを尋ねる。
有向非巡回グラフ (DAGs) に対して、Grover 探索(英語版)を行い、その状態準備は、弧ごとに1 qubit で ancilla を含まない全てのソース対決定経路上の一様重ね合わせを構築する。
我々は,その正しさを証明し,正確なゲート数を与えるとともに,距離がガースのようなグラフパラメータである誤差検出符号を形成することを示す。
最大の例である136 arc qubits と 262,144 パスでは、約 4.4 x 10^5 のトフォリゲートが必要であるが、古典的動的プログラミングでは18,754 のラベルで同じケースを決定する。
グロバー探索には O(sqrt(N/M)) のオラクルが N 間の M 良い経路を要求する。
古典的なミート・イン・ザ・ミドルは、最悪の場合、この指数と一致し、量子メモリを持つ既知の量子アルゴリズムがそれを上回った。
ノード非依存の線形重みを持つステージドファブリックでは、満足度測定値の最大化は max-LINSAT であり、インデックス重みのパワーは Optimal Polynomial Intersection であり、既知の多項式時間古典アルゴリズムはデコード量子干渉法(DQI)と一致しない。
我々はこの変換をシミュレーションで検証し、IBM Heronプロセッサ上で2つの小さなバイナリインスタンスを実行する。
関連論文リスト
- Hardness of Pathfinding in a Welded Tree [0.2864713389096699]
我々は、出口から出口までの経路を見つけるために指数的量子クエリを低い境界で証明する。
我々の証明では,アルゴリズムが学習し忘れたグラフ情報を追跡するデータベースを構築するために,圧縮置換オラクル法を用いている。
論文 参考訳(メタデータ) (2026-09-17T16:29:09Z) - Verifiable quantum advantage in extremely low depth [52.51019642214249]
浅量子回路では解けない問題を格子ベースの仮定で解くのが困難である。
浅量子回路は、解を効率よく検証できる古典的な難題を解くのに十分な構造を持っていることを証明している。
論文 参考訳(メタデータ) (2026-09-01T15:54:34Z) - Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている
SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。
この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文 参考訳(メタデータ) (2024-08-14T19:04:13Z) - Distributed Exact Generalized Grover's Algorithm [9.675088142486729]
本稿では,汎用探索問題の解法として,分散Exactized Grover's Algorithm (DEGGA)を提案する。
我々のアルゴリズムは、目標状態が100%$の理論的確率で精度を保証します。
我々の方法は合計$n$ qubitsを必要とし、補助的なqubitsは不要である。
論文 参考訳(メタデータ) (2024-05-11T09:17:11Z) - Mind the $\tilde{\mathcal{O}}$: Asymptotically Better, but Still
Impractical, Quantum Distributed Algorithms [0.0]
確率の高い分散計算の量子ConGEST-CLIQUEモデルに2つのアルゴリズムを提案する。
従来のCONGEST-CLIQUEモデルでは、既知のアルゴリズムよりもラウンドとメッセージの複雑さが低い。
Groverの検索アルゴリズムの分散バージョンを使用して三角形探索を高速化する既存のフレームワークは、スピードアップのコアにある。
論文 参考訳(メタデータ) (2023-04-06T02:18:52Z) - Complexity-Theoretic Limitations on Quantum Algorithms for Topological
Data Analysis [59.545114016224254]
トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。
我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。
我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
論文 参考訳(メタデータ) (2022-09-28T17:53:25Z) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。