論文の概要: Time complexity of a monitored quantum search with resetting

• arxiv url: http://arxiv.org/abs/2601.20560v1
• Date: Wed, 28 Jan 2026 12:55:49 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-29 15:46:06.934873
• Title: Time complexity of a monitored quantum search with resetting
• Title（参考訳）: リセットによる監視量子探索の時間複雑性
• Authors: Emma C. King, Sayan Roy, Francesco Mattiotti, Maximilian Kiefer-Emmanouilidis, Markus Bläser, Giovanna Morigi,
• Abstract要約: ランダム化アルゴリズムの量子アナログの時間的複雑さについて検討し,フィードバックを簡単な形で実装する。 探索は完全なグラフ上の連続時間量子ウォークであり、ターゲットは検出器によって継続的に監視される。 我々は,ホッピング振幅,検出率,リセット率の関数として探索時間を最適化し,Groverのスケーリングを上回り得る条件を特定する。
• 参考スコア（独自算出の注目度）: 7.7152006741337615
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Searching a database is a central task in computer science and is paradigmatic of transport and optimization problems in physics. For an unstructured search, Grover's algorithm predicts a quadratic speedup, with the search time $τ(N)=Θ(\sqrt{N})$ and $N$ the database size. Numerical studies suggest that the time complexity can change in the presence of feedback, injecting information during the search. Here, we determine the time complexity of the quantum analog of a randomized algorithm, which implements feedback in a simple form. The search is a continuous-time quantum walk on a complete graph, where the target is continuously monitored by a detector. Additionally, the quantum state is reset if the detector does not click within a specified time interval. This yields a non-unitary, non-Markovian dynamics. We optimize the search time as a function of the hopping amplitude, detection rate, and resetting rate, and identify the conditions under which time complexity could outperform Grover's scaling. The overall search time does not violate Grover's optimality bound when including the time budget of the physical implementation of the measurement. For databases of finite sizes monitoring can warrant rapid convergence and provides a promising avenue for fault-tolerant quantum searches.
• Abstract（参考訳）: データベースの検索は計算機科学における中心的な課題であり、物理学における輸送と最適化の問題のパラダイムである。 構造化されていない探索の場合、Groverのアルゴリズムは2次スピードアップを予測し、検索時間は$τ(N)=\(\sqrt{N})$と$N$である。 数値的な研究は、フィードバックの存在によって時間的複雑さが変化し、探索中に情報を注入できることを示唆している。 ここでは、単純な形式でフィードバックを実装するランダム化アルゴリズムの量子アナログの時間的複雑さを決定する。 探索は完全なグラフ上の連続時間量子ウォークであり、ターゲットは検出器によって継続的に監視される。 さらに、検出器が特定の時間間隔でクリックしない場合、量子状態はリセットされる。 これは非ユニタリで非マルコフ力学をもたらす。 我々は,ホッピング振幅,検出率,リセット率の関数として探索時間を最適化し,Groverのスケーリングを上回り得る条件を特定する。 全体的な探索時間は、測定の物理的実装の時間予算を含むと、Groverの最適性に反しない。 有限サイズのデータベースの場合、モニタリングは急激な収束を保証し、フォールトトレラントな量子探索のための有望な道を提供する。

関連論文リスト

• Dynamical localization in 2D topological quantum random walks [0.0]
  本研究では, 位相分割型量子ランダムウォーク(QRW)の離散時間発展の動的局所化について検討した。 離散時間進化作用素のスペクトル特性を調べた結果,トラップ状態と初期均一分布状態との重なりが大きいことがわかった。 特定した局所化のメカニズムは、障害の影響に対して堅牢であることを示す。
  論文  参考訳（メタデータ） (2024-06-26T21:36:47Z)
• Deterministic Search on Complete Bipartite Graphs by Continuous Time Quantum Walk [0.8057006406834466]
  本稿では,完全二部グラフ上の決定論的探索アルゴリズムを提案する。 複数のマーク状態の最も一般的なケースに対処するため、マーク状態の数を推定する問題が存在する。 探索演算子のスペクトル構造に基づく量子カウントアルゴリズムを構築する。
  論文  参考訳（メタデータ） (2024-04-02T05:09:33Z)
• Taming Quantum Time Complexity [45.867051459785976]
  時間複雑性の設定において、正確さと遠心性の両方を達成する方法を示します。 我々は、トランスデューサと呼ばれるものに基づく量子アルゴリズムの設計に新しいアプローチを採用する。
  論文  参考訳（メタデータ） (2023-11-27T14:45:19Z)
• Iterative Qubits Management for Quantum Index Searching in a Hybrid System [56.39703478198019]
  IQuCSは、量子古典ハイブリッドシステムにおけるインデックス検索とカウントを目的としている。 我々はQiskitでIQuCSを実装し、集中的な実験を行う。 その結果、量子ビットの消費を最大66.2%削減できることが示されている。
  論文  参考訳（メタデータ） (2022-09-22T21:54:28Z)
• Quantum speedup for track reconstruction in particle accelerators [51.00143435208596]
  我々は,各局所追跡法に存在する基本ルーチンを4つ同定し,標準追跡アルゴリズムの文脈でどのようにスケールするかを解析する。 発見された量子スピードアップは穏やかだが、これは私たちの知識の中でも最高のものであり、高エネルギーの物理データ処理タスクに対する量子上の優位性の最初の厳密な証拠である。
  論文  参考訳（メタデータ） (2021-04-23T13:32:14Z)
• Hardware Efficient Quantum Search Algorithm [17.74233101199813]
  本稿では,この課題を克服するために,ハードウェアの効率的な量子探索アルゴリズムを提案する。 我々の鍵となる考え方は、グローバル拡散操作を低コストな局所拡散に置き換えることである。 回路コストの削減は、システムの成功率を著しく向上させる。
  論文  参考訳（メタデータ） (2021-03-26T01:08:50Z)
• Efficient Algorithms for Causal Order Discovery in Quantum Networks [44.356294905844834]
  入力および出力システムへのブラックボックスアクセスを前提として,最初の効率的な量子因果順序探索アルゴリズムを開発した。 我々は、量子コムを用いて因果順序をモデル化し、我々のアルゴリズムは、与えられたプロセスと互換性のある入力と出力の順序を出力する。 我々のアルゴリズムは、量子通信ネットワークで利用可能な伝送経路を効率的に検出し、最適化する方法を提供する。
  論文  参考訳（メタデータ） (2020-12-03T07:12:08Z)
• Quantifying Computational Advantage of Grover's Algorithm with the Trace Speed [0.0]
  本稿では,Groverの探索アルゴリズムにおけるトレース速度と量子スピードアップの密接な関係について報告する。 ノイズのないアルゴリズムでは、量子スピードアップと擬似純粋状態の偏極の1対1対応を見出す。
  論文  参考訳（メタデータ） (2020-01-13T19:01:09Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。