論文の概要: Quantum search by continuous-time quantum walk on t-designs
- arxiv url: http://arxiv.org/abs/2310.14141v1
- Date: Sun, 22 Oct 2023 00:37:52 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-25 01:45:13.154809
- Title: Quantum search by continuous-time quantum walk on t-designs
- Title（参考訳）: t-設計上の連続時間量子ウォークによる量子探索
- Authors: Pedro H. G. Lug\~ao, Renato Portugal
- Abstract要約: 本研究は、連続時間量子ウォークを用いて、複数のマークされた要素を持つ$t$-designs上の量子検索アルゴリズムの時間的複雑さについて検討する。
ランダムウォークに基づく探索アルゴリズムと比較して,成功に導かれる二部グラフのサブセットを同定する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: This work examines the time complexity of quantum search algorithms on
combinatorial $t$-designs with multiple marked elements using the
continuous-time quantum walk. Through a detailed exploration of $t$-designs and
their incidence matrices, we identify a subset of bipartite graphs that are
conducive to success compared to random-walk-based search algorithms. These
graphs have adjacency matrices with eigenvalues and eigenvectors that can be
determined algebraically and are also suitable for analysis in the
multiple-marked vertex scenario. We show that the continuous-time quantum walk
on certain symmetric $t$-designs achieves an optimal running time of
$O(\sqrt{n})$, where $n$ is the number of points and blocks, even when
accounting for an arbitrary number of marked elements. Upon examining two
primary configurations of marked elements distributions, we observe that the
success probability is consistently $o(1)$, but it approaches 1 asymptotically
in certain scenarios.
- Abstract（参考訳）: 本研究は、連続時間量子ウォークを用いて、複数のマーク要素を持つ組合せ $t$-designs 上の量子探索アルゴリズムの時間複雑性について検討する。
t$-designsとその入射行列の詳細な調査を通じて、ランダムウォークに基づく検索アルゴリズムと比較して成功に導かれる二部グラフのサブセットを特定する。
これらのグラフは固有値を持つ隣接行列と代数的に決定でき、多点頂点シナリオの解析にも適する固有ベクトルを持つ。
ある対称な$t$-デザイン上の連続時間量子ウォークは、任意の数のマークされた要素を計算しても、_n$が点数とブロック数である場合であっても、最適な実行時間である$o(\sqrt{n})$が得られる。
マークされた要素分布の2つの一次配置を調べると、成功確率は一貫して$o(1)$となるが、特定のシナリオでは漸近的に1に近づく。
関連論文リスト
- Quantum Walk Search on Complete Multipartite Graph with Multiple Marked Vertices [7.922488341886121]
本稿では,完全多部グラフ上での量子ウォーク探索アルゴリズムについて検討する。
我々は、量子ウォークモデルを用いて、二次的なスピードアップを実現する。
また、量子アルゴリズムの数値シミュレーションと回路実装も提供する。
論文 参考訳（メタデータ） (2024-10-07T11:13:41Z) - Quantum algorithms for Hopcroft's problem [45.45456673484445]
計算幾何学の基本的な問題であるホップクロフト問題に対する量子アルゴリズムについて検討する。
この問題の古典的な複雑さはよく研究されており、最もよく知られているアルゴリズムは$O(n4/3)の時間で動作する。
我々の結果は、時間複雑性が$widetilde O(n5/6)$の2つの異なる量子アルゴリズムである。
論文 参考訳（メタデータ） (2024-05-02T10:29:06Z) - Quantum walks advantage on the dihedral group for uniform sampling
problem [0.0]
歩行を混合することは、マルコフ連鎖が群に対する定常分布を近似する過程である。
量子ウォークは古典的な場合よりも時間混合の潜在的な利点を示しているが、有限群の場合では一般的な証明が欠如している。
この研究は、非アーベル群、グラフ同型テスト等をサンプリングするアルゴリズムに潜在的な応用がある。
論文 参考訳（メタデータ） (2023-12-25T11:21:55Z) - Taming Quantum Time Complexity [45.867051459785976]
時間複雑性の設定において、正確さと遠心性の両方を達成する方法を示します。
我々は、トランスデューサと呼ばれるものに基づく量子アルゴリズムの設計に新しいアプローチを採用する。
論文 参考訳（メタデータ） (2023-11-27T14:45:19Z) - On the average-case complexity of learning output distributions of
quantum circuits [55.37943886895049]
統計的クエリモデルでは,ブロックワークランダムな量子回路の出力分布の学習は平均ケースハードであることが示されている。
この学習モデルは、ほとんどの一般的な学習アルゴリズムの抽象的な計算モデルとして広く利用されている。
論文 参考訳（メタデータ） (2023-05-09T20:53:27Z) - Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。
異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。
我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
論文 参考訳（メタデータ） (2022-06-07T18:00:01Z) - Quantum Approximate Counting for Markov Chains and Application to
Collision Counting [0.0]
我々は,ブラザード,ホイヤー,タップ(ICALP 1998)によって開発された量子近似計数法を一般化し,マルコフ連鎖のマーク状態の数を推定する方法を示す。
これにより、Magniez、Nayak、Roland、Santhaによって確立された強力な"量子ウォークベースサーチ"フレームワークに基づいて、量子検索アルゴリズムから量子近似カウントアルゴリズムを構築することができる。
論文 参考訳（メタデータ） (2022-04-06T03:04:42Z) - Multimarked Spatial Search by Continuous-Time Quantum Walk [0.0]
任意のグラフ上の連続時間量子ウォークによる空間探索の計算複雑性を決定するためのフレームワークについて述べる。
量子ウォークは、マークされた頂点の存在によって修正されたグラフの隣接行列に由来するハミルトン行列によって駆動される。
論文 参考訳（メタデータ） (2022-03-27T20:22:17Z) - Quantum walk-based search algorithms with multiple marked vertices [0.0]
量子ウォークは量子アルゴリズムを開発するための強力なツールである。
我々は、Szegedyの量子ウォークに基づく従来の解析手法を拡張した。
2次元格子とハイパーキューブ上の量子ウォークに基づく2つの例は、我々の方法の詳細を示している。
論文 参考訳（メタデータ） (2021-03-23T22:57:07Z) - Random quantum circuits anti-concentrate in log depth [118.18170052022323]
本研究では,典型的な回路インスタンスにおける測定結果の分布に要するゲート数について検討する。
我々の反集中の定義は、予測衝突確率が分布が均一である場合よりも大きい定数因子に過ぎないということである。
ゲートが1D環上で最寄りである場合と、ゲートが長距離である場合の両方において、$O(n log(n))ゲートも十分であることを示す。
論文 参考訳（メタデータ） (2020-11-24T18:44:57Z) - Ranking a set of objects: a graph based least-square approach [70.7866286425868]
同一労働者の群集によるノイズの多いペアワイズ比較から始まる$N$オブジェクトのランク付けの問題について考察する。
品質評価のために,最小二乗内在的最適化基準に依存する非適応的ランキングアルゴリズムのクラスを提案する。
論文 参考訳（メタデータ） (2020-02-26T16:19:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。