論文の概要: Optimal and Deterministic Quantum Search on the Simplex of Complete Graphs
- arxiv url: http://arxiv.org/abs/2608.03777v1
- Date: Tue, 04 Aug 2026 15:00:39 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-08-05 15:30:23.261483
- Title: Optimal and Deterministic Quantum Search on the Simplex of Complete Graphs
- Title（参考訳）: 完全グラフの単純度に基づく最適および決定論的量子探索
- Abstract要約: 完備グラフの単純集合、あるいは一階 truncated simplex 格子(英: First-order truncated simplex lattice)は、M+1$ 同一完全グラフのネットワークである。
このグラフ上で最適量子探索の最初の解析的証明を与え、橋の重みが$M$と等しいときに起こることを証明した。
このアルゴリズムは、重量が$sqrtM$から$M$の間でスケールする場合にも決定論的であり、これは完備グラフの単純点上の量子探索の最初の例である。
- 参考スコア（独自算出の注目度）: 0.10923877073891441
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The simplex of complete graphs, also known as the first-order truncated simplex lattice, is a network of $M+1$ identical complete graphs, each with $M$ vertices, such that each clique contains an edge or bridge to every other clique. It contains $N = M(M+1)$ vertices, and previous asymptotic results using a continuous-time quantum walk to search this graph for a single marked vertex have either numerically demonstrated an optimal runtime of $O(\sqrt{N})$, or analytically proved a deterministic success probability of 1, but not both, even when the bridges are weighted. In this paper, we give the first analytical proof of optimal quantum search on this graph, proving that it occurs when the weight of the bridges equals $M$. In addition, we numerically show that the optimal runtime is achieved more broadly whenever the weight is at least $\sqrt{M}$. Furthermore, the algorithm is also deterministic when the weight scales between $\sqrt{M}$ and $M$, and this is the first example of quantum search on the simplex of complete graphs that is both asymptotically optimal and deterministic. In addition, for weights where the algorithm is nondeterministic, we give a way to find the marked vertex by inspecting neighboring vertices. Finally, while it is known that connectivity is not a reliable indicator of fast quantum search when comparing different graph families, we show that it is also unreliable within the graph family of weighted simplex of complete graphs.
- Abstract（参考訳）: 一階 truncated simplex 格子(英: first-order truncated simplex lattice)は、M+1$同じ完全グラフのネットワークであり、それぞれが$M$頂点を持つ。
これには$N = M(M+1)$ vertices が含まれており、このグラフを1つのマークされた頂点に対して探索するために連続時間量子ウォークを用いた以前の漸近の結果は、$O(\sqrt{N})$の最適ランタイムを数値的に証明したか、1の決定論的成功確率を解析的に証明したかのいずれかであるが、橋が重み付けられたとしても両方ではない。
本稿では,このグラフ上での最適量子探索の最初の解析的証明を行い,橋梁の重みが$M$と等しい場合に発生することを証明した。
さらに、重みが少なくとも$\sqrt{M}$である場合、最適ランタイムがより広く達成されることを数値的に示す。
さらに、このアルゴリズムは、重量が$\sqrt{M}$と$M$の間でスケールする場合にも決定論的であり、これは漸近的に最適かつ決定論的である完備グラフの単純点上の量子探索の最初の例である。
さらに,アルゴリズムが非決定論的である重みに対して,隣接する頂点を検査してマークされた頂点を見つける方法を提案する。
最後に、接続性は異なるグラフファミリを比較する際に高速量子探索の信頼性指標ではないことが知られているが、完全グラフの重み付き単純グラフのグラフファミリでは信頼できないことを示す。
関連論文リスト
- Quantum Algorithms for Approximate Graph Isomorphism Testing [0.0]
近似グラフ同型テストの量子クエリ複雑性について検討する。
入力グラフの積グラフ$(G,H)$に対するMNRS量子ウォーク探索に基づく量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2026-03-03T06:43:41Z) - Monogamy of Entanglement Bounds and Improved Approximation Algorithms for Qudit Hamiltonians [37.96754147111215]
我々は、一局所項のないランク1プロジェクターの2局所キュディト・ハミルトン多様体に対するエンタングルメント境界の新しいモノガミーを証明した。
特に、基礎となる相互作用グラフの最大整合性の観点から、低次二乗和を用いて基底状態エネルギーを認証する。
論文 参考訳（メタデータ） (2024-10-21T00:10:51Z) - Unifying quantum spatial search, state transfer and uniform sampling on graphs: simple and exact [2.871419116565751]
本稿では,量子ウォークの交互化による新しい,簡潔なアルゴリズムフレームワークを提案する。
量子空間探索、状態移動、および大規模なグラフの均一サンプリングを統一する。
このアプローチは、グラフのラプラシア固有値集合の深さにのみ依存する簡潔な形式性を持っているため、簡単に利用できる。
論文 参考訳（メタデータ） (2024-07-01T06:09:19Z) - Differentiable Proximal Graph Matching [40.41380102260085]
微分可能近位グラフマッチング(DPGM)と呼ばれる近位演算子に基づくグラフマッチングアルゴリズムを提案する。
アルゴリズム全体をグラフ親和性行列からノード対応の予測への微分可能な写像とみなすことができる。
数値実験により、PGMは様々なデータセット上で既存のグラフマッチングアルゴリズムより優れていることが示された。
論文 参考訳（メタデータ） (2024-05-26T08:17:13Z) - Universal approach to deterministic spatial search via alternating
quantum walks [2.940962519388297]
本稿では,量子ウォークを交互に組み合わせることで,様々なグラフ上で決定論的量子探索アルゴリズムを設計するための新しいアプローチを提案する。
我々のアプローチは、異なるグラフに対してインスタンス固有の分析を必要としないため、普遍的である。
論文 参考訳（メタデータ） (2023-07-30T05:14:19Z) - Moments, Random Walks, and Limits for Spectrum Approximation [40.43008834125277]
我々は、ワッサーシュタイン1距離において精度$epsilon$に近似できない$[-1,1]$に分布が存在することを示す。
正規化グラフ隣接行列のスペクトルに対する$epsilon$-accurate近似を一定の確率で計算することはできない。
論文 参考訳（メタデータ） (2023-07-02T05:03:38Z) - Multimarked Spatial Search by Continuous-Time Quantum Walk [0.0]
任意のグラフ上の連続時間量子ウォークによる空間探索の計算複雑性を決定するためのフレームワークについて述べる。
量子ウォークは、マークされた頂点の存在によって修正されたグラフの隣接行列に由来するハミルトン行列によって駆動される。
論文 参考訳（メタデータ） (2022-03-27T20:22:17Z) - The Exact Class of Graph Functions Generated by Graph Neural Networks [43.25172578943894]
グラフ関数と出力が同一のグラフニューラルネットワーク(GNN)?
本稿では,この疑問に完全に答え,GNNで表現可能なグラフ問題のクラスを特徴付ける。
この条件は2次的に多くの制約をチェックすることで効率よく検証できることを示す。
論文 参考訳（メタデータ） (2022-02-17T18:54:27Z) - Fast Computation of Generalized Eigenvectors for Manifold Graph
Embedding [38.902986549367434]
我々は、高速実行に既存の高速極端固有ベクトル計算アルゴリズムを利用する。
我々の埋め込みは文献の中では最速であり、多様体グラフのクラスタリング性能は最高のものとなっている。
論文 参考訳（メタデータ） (2021-12-15T03:45:39Z) - A framework for optimal quantum spatial search using alternating
phase-walks [0.0]
我々は、マーク頂点位相シフトと連続時間量子ウォークの交互適用により、Childs & Goldstone(mathcalCG$)アルゴリズムを一般化する。
様々なグラフ上の$mathcalO(sqrtN)$検索にアルゴリズムを適用することで,アルゴリズムの有効性を実証する。
論文 参考訳（メタデータ） (2021-09-29T11:16:52Z) - A Thorough View of Exact Inference in Graphs from the Degree-4
Sum-of-Squares Hierarchy [37.34153902687548]
各エッジの1つの破損した観測からノードの未知の接地型バイナリラベリングを正確に回収する問題に取り組む。
この問題に対して、和の平方階層と呼ばれるリラクゼーションの階層を適用します。
我々は、緩和問題の双対の解がジョンソングラフとクネーサーグラフのエッジウェイトを見つけることに関連していることを示した。
論文 参考訳（メタデータ） (2021-02-16T08:36:19Z) - Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
我々は高密度サブグラフ発見のための新しい学習問題を導入する。
まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。
そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
論文 参考訳（メタデータ） (2020-06-24T11:37:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。