論文の概要: 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のとき、それらを見つける。
関連論文リスト
- The quantum beam splitter with many partially indistinguishable photons:
multiphotonic interference and asymptotic classical correspondence [44.99833362998488]
量子双極子干渉計の解析は、$n右ローinfty$制限の$n$を部分的に区別できない光子で行う。
我々の主な結果は、出力分布が、ある$j*$の周りの$O(sqrtn)$チャネルに支配されていることである。
この形式は基本的に2j*$の区別不可能な光子から生じ、対応する古典的な強度分布を再現する分布の2つの半古典的エンベロープである。
論文 参考訳(メタデータ) (2023-12-28T01:48: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) - 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) - Random Subgraph Detection Using Queries [45.55323995672117]
植込み高密度部分グラフ検出問題は、与えられた(ランダム)グラフに異常に密度の高い部分グラフが存在するかどうかをテストするタスクを指す。
任意の(おそらくランダム化される)アルゴリズムは、$mathsfQ = Omega(fracn2k2chi4(p||q)log2n)$アダプティブクエリを生成する必要がある。
我々は、$mathsfQ = O(fracn3) とすることで、高い確率で植込み部分グラフを検出する準多項式時間アルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-10-02T07:41:17Z) - Unstructured Search by Random and Quantum Walk [0.0]
ソートされていない$N$要素のリストのエントリを探すと、古典的なコンピュータのオラクルに$O(N)$クエリーを取るのが有名である。
離散的かつ連続的なランダムウォークと量子ウォークがこの問題をいかに解決するかを導出する。
論文 参考訳(メタデータ) (2020-11-30T04:00:31Z) - Quantum Coupon Collector [62.58209964224025]
我々は、$k$-要素集合$Ssubseteq[n]$が、その要素の一様重ね合わせ$|Srangleからいかに効率的に学習できるかを研究する。
我々は、$k$と$n$ごとに必要となる量子サンプルの数に厳密な制限を与え、効率的な量子学習アルゴリズムを与える。
論文 参考訳(メタデータ) (2020-02-18T16:14:55Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。