論文の概要: Quantum search of matching on signed graphs
- arxiv url: http://arxiv.org/abs/2007.07223v1
- Date: Mon, 13 Jul 2020 09:36:08 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-10 04:20:08.633663
- Title: Quantum search of matching on signed graphs
- Title（参考訳）: 符号付きグラフ上のマッチングの量子探索
- Authors: Etsuo Segawa, Yusuke Yoshie
- Abstract要約: 我々は,量子ウォークによって駆動される符号付きエッジの量子探索モデルを構築した。
完全グラフ上のマッチングを与える任意のエッジカラー化の下で、完全グラフのエッジ集合から有色エッジの量子探索を考える。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We construct a quantum searching model of a signed edge driven by a quantum
walk. The time evolution operator of this quantum walk provides a weighted
adjacency matrix induced by the assignment of sign to each edge. This sign can
be regarded as so called the edge coloring. Then as an application, under an
arbitrary edge coloring which gives a matching on a complete graph, we consider
a quantum search of a colored edge from the edge set of a complete graph. We
show that this quantum walk finds a colored edge within the time complexity of
$O(n^{\frac{2-\alpha}{2}})$ with probability $1-o(1)$ while the corresponding
random walk on the line graph finds them within the time complexity of
$O(n^{2-\alpha})$ if we set the number of the edges of the matching by
$O(n^{\alpha})$ for $0 \le \alpha \le 1$.
- Abstract（参考訳）: 量子ウォークによって駆動される符号付きエッジの量子探索モデルを構築する。
この量子ウォークの時間発展演算子は、各辺への符号の割り当てによって引き起こされる重み付き隣接行列を提供する。
この記号は、エッジカラーと呼ばれるものと見なすことができる。
そして、アプリケーションとして、完備グラフ上のマッチングを与える任意のエッジカラー化の下で、完備グラフのエッジ集合から有色エッジの量子探索を考える。
この量子ウォークは、時間複雑性$O(n^{\frac{2-\alpha}{2}})$が確率1-o(1)$であるのに対し、ライングラフ上の対応するランダムウォークは時間複雑性$O(n^{2-\alpha})$が一致するエッジの数を$O(n^{\alpha})$が$0のとき、それらを見つける。
関連論文リスト
- Quantum Walk Search on Complete Multipartite Graph with Multiple Marked Vertices [7.922488341886121]
本稿では,完全多部グラフ上での量子ウォーク探索アルゴリズムについて検討する。
我々は、量子ウォークモデルを用いて、二次的なスピードアップを実現する。
また、量子アルゴリズムの数値シミュレーションと回路実装も提供する。
論文 参考訳（メタデータ） (2024-10-07T11:13:41Z) - Navigable Graphs for High-Dimensional Nearest Neighbor Search: Constructions and Limits [24.592554830963966]
グラフが任意の開始ノードから任意のターゲットノードへの移動に成功すれば、グラフはナビゲート可能である。
アプリケーションにとって重要な問題は、スペーサーグラフを構築することができるかどうかである。
任意の次元において、任意の距離関数に対して、平均次数$O(sqrtn log n )$の任意の$n$点に対してナビゲート可能なグラフを構築するための単純かつ効率的な方法を与える。
論文 参考訳（メタデータ） (2024-05-29T01:07:26Z) - Quantum search by continuous-time quantum walk on t-designs [0.0]
本研究は、連続時間量子ウォークを用いて、複数のマークされた要素を持つ$t$-designs上の量子検索アルゴリズムの時間的複雑さについて検討する。
ランダムウォークに基づく探索アルゴリズムと比較して,成功に導かれる二部グラフのサブセットを同定する。
論文 参考訳（メタデータ） (2023-10-22T00:37:52Z) - Moments, Random Walks, and Limits for Spectrum Approximation [40.43008834125277]
我々は、ワッサーシュタイン1距離において精度$epsilon$に近似できない$[-1,1]$に分布が存在することを示す。
正規化グラフ隣接行列のスペクトルに対する$epsilon$-accurate近似を一定の確率で計算することはできない。
論文 参考訳（メタデータ） (2023-07-02T05:03:38Z) - Quantum Speedups for Zero-Sum Games via Improved Dynamic Gibbs Sampling [30.53587208999909]
我々は、ゼロサムゲームにおける$epsilon$-approximate Nash平衡を、有界なエントリを持つ$m倍n$ペイオフ行列で計算するための量子アルゴリズムを与える。
ペイオフ行列にアクセスするための標準的な量子オラクルが与えられたとき、我々のアルゴリズムは$widetildeO(sqrtm + ncdot epsilon-2.5 + epsilon-3)$で実行され、$epsilon$-approximate Nash平衡の古典的な表現を出力する。
論文 参考訳（メタデータ） (2023-01-10T02:56:49Z) - Sample optimal tomography of quantum Markov chains [23.427626096032803]
三部量子系上の状態 $mathcalH_Aotimes MathcalH_B$ はマルコフ連鎖、すなわち量子条件独立性、すなわち$mathcalH_Aotimes MathcalH_B$ の限界から再構成可能である。
$mathcalH_B$から$mathcalH_BotimesmathcalH_C$への量子演算
論文 参考訳（メタデータ） (2022-09-06T06:30:37Z) - Walking on Vertices and Edges by Continuous-Time Quantum Walk [0.0]
私たちは、歩行者が頂点から端までホップできる連続時間量子ウォークのバージョンを定義します。
両部グラフ上の空間探索アルゴリズムをハミルトン版の修正により解析する。
論文 参考訳（メタデータ） (2022-06-07T15:10:18Z) - Multimarked Spatial Search by Continuous-Time Quantum Walk [0.0]
任意のグラフ上の連続時間量子ウォークによる空間探索の計算複雑性を決定するためのフレームワークについて述べる。
量子ウォークは、マークされた頂点の存在によって修正されたグラフの隣接行列に由来するハミルトン行列によって駆動される。
論文 参考訳（メタデータ） (2022-03-27T20:22:17Z) - A quantum searching model finding one of the edges of a subgraph in a
complete graph [0.0]
我々は,与えられた部分グラフのエッジの1つを完全グラフで探索する量子探索モデルを構築した。
モデルが任意の部分グラフ、すなわち完備グラフに対して有効であることを示す。
論文 参考訳（メタデータ） (2022-02-03T08:45:39Z) - On quantum algorithms for the Schr\"odinger equation in the
semi-classical regime [27.175719898694073]
半古典的状態におけるシュル・オーディンガーの方程式を考える。
このようなシュル・オーディンガー方程式はボルン=オッペンハイマーの分子動力学やエレンフェストの動力学など多くの応用を見出す。
論文 参考訳（メタデータ） (2021-12-25T20:01:54Z) - Quantum Coupon Collector [62.58209964224025]
我々は、$k$-要素集合$Ssubseteq[n]$が、その要素の一様重ね合わせ$|Srangleからいかに効率的に学習できるかを研究する。
我々は、$k$と$n$ごとに必要となる量子サンプルの数に厳密な制限を与え、効率的な量子学習アルゴリズムを与える。
論文 参考訳（メタデータ） (2020-02-18T16:14:55Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。