論文の概要: Quantum-classical algorithm interpolation for spatial search

• arxiv url: http://arxiv.org/abs/2610.19255v1
• Date: Tue, 13 Oct 2026 22:25:20 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-15 21:06:15.829349
• Title: Quantum-classical algorithm interpolation for spatial search
• Title（参考訳）: 空間探索のための量子古典的アルゴリズム補間
• Abstract要約: 量子ウォークアルゴリズムは、古典的ヒット時間$mathrmHT$に対する空間探索の依存を2次的に低減することができる。 我々は、古典的および完全コヒーレントな量子状態の間に連続的に補間する、ハイブリッド量子古典空間探索アルゴリズムのパラメータ化された族を導出する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Quantum-walk algorithms can quadratically reduce the dependence of spatial search on the classical hitting time $\mathrm{HT}$. Realising this speedup using standard quantum-walk algorithms, however, requires deep coherent circuits, limiting their applicability on near-term and early fault-tolerant quantum devices. We derive a parameterised family of hybrid quantum-classical spatial search algorithms that continuously interpolates between the classical and fully coherent quantum regimes, trading off circuit depth for total query complexity. For any $γ\in[0,1]$, our algorithms use circuits of depth $\widetilde{O}(\mathrm{HT}^{γ/2})$ and find a marked vertex with constant success probability at total cost $\widetilde{O}(\mathrm{HT}^{1-γ}\mathsf{S} + \mathrm{HT}^{1-γ/2}(\mathsf{U} + \mathsf{C}))$, where $\mathsf{S}$, $\mathsf{U}$, and $\mathsf{C}$ denote the setup, update, and checking costs, respectively. We also derive an optimal continuous depth-query trade-off for fixed-point amplitude amplification, providing a potential building block for other hybrid designs.
• Abstract（参考訳）: 量子ウォークアルゴリズムは古典的打撃時間$\mathrm{HT}$に対する空間探索の依存性を2次的に減少させることができる。 しかし、標準的な量子ウォークアルゴリズムを用いてこのスピードアップを実現するには深いコヒーレント回路が必要であり、短期および早期のフォールトトレラント量子デバイスに適用性を制限する。 我々は、古典的および完全一貫性のある量子状態間の連続的な補間を行い、全クエリの複雑さを回路深さから引き離す、ハイブリッド量子古典空間探索アルゴリズムのパラメータ化されたファミリーを導出する。 任意の$γ\in[0,1]$に対して、我々のアルゴリズムは深さ$\widetilde{O}(\mathrm{HT}^{γ/2})$の回路を使用し、総コスト$\widetilde{O}(\mathrm{HT}^{1-γ}\mathsf{S} + \mathrm{HT}^{1-γ/2}(\mathsf{U} + \mathsf{C})$, $\mathsf{S}$, $\mathsf{U}$, $\mathsf{C}$のセットアップ、更新、コストのチェックを行う。 我々はまた、固定点振幅増幅のための最適連続深さ回路トレードオフを導出し、他のハイブリッド設計のための潜在的なビルディングブロックを提供する。

関連論文リスト

• Fourier Spectrum of Noisy Quantum Algorithms [0.0]
  量子アルゴリズムに作用する雑音は、ノイズの種類と複雑に結びついている方法でフーリエ成長を阻害することを示す。 特に,2-Forrelationと3-Forrelationは,それぞれ$mathsfDQC_k$と$frac12mathsfBQP$モデルで,$NOmega(1)$クエリを必要とすることを示す。
  論文  参考訳（メタデータ） (2025-10-07T19:07:59Z)
• Quantum Algorithms for Finite-horizon Markov Decision Processes [40.812944518646006]
  我々は、時間依存および有限水平マルコフ決定過程(MDP)を解くために、古典的アルゴリズムよりも効率的な量子アルゴリズムを設計する。 正確なダイナミックス設定において、我々の$textbfQVI-1$アルゴリズムがアクション空間$(A)$の2次スピードアップを達成することを証明している。 生成モデル設定において、我々のアルゴリズムである$textbfQVI-3$と$textbfQVI-4$が、最先端(SOTA)古典アルゴリズムよりも複雑なサンプルを実現することを証明している。
  論文  参考訳（メタデータ） (2025-08-07T09:00:23Z)
• Quantum Algorithm for the Fixed-Radius Neighbor Search [39.58317527488534]
  本稿では,Grover アルゴリズムの固定点バージョンに基づく固定 RAdius Neighbor Search problem (FRANS) の量子アルゴリズムを提案する。 我々は,FRANSを,粒子数$N$の線形クエリ複雑性で解くための効率的な回路を導出する。 読み出し誤差に対するモデルのレジリエンスを評価し,結果の精度を確認するための誤り訂正フリー戦略を提案する。
  論文  参考訳（メタデータ） (2025-07-04T10:01:10Z)
• Slow Mixing of Quantum Gibbs Samplers [47.373245682678515]
  一般化されたボトルネック補題を用いて、これらのツールの量子一般化を示す。 この補題は、古典的なハミング距離に類似する距離の量子測度に焦点を当てるが、一意に量子原理に根ざしている。 ポアソン・ファインマン・カック法を用いて古典的な緩やかな混合結果を持ち上げる方法を示す。
  論文  参考訳（メタデータ） (2024-11-06T22:51:27Z)
• Calculating response functions of coupled oscillators using quantum phase estimation [40.31060267062305]
  量子コンピュータを用いた結合型古典的高調波発振器系の周波数応答関数の推定問題について検討する。 提案する量子アルゴリズムは,標準的な$sスパース,オーラクルベースのクエリアクセスモデルで動作する。 そこで,本アルゴリズムの簡単な適応により,時間内に無作為な結束木問題を解くことを示す。
  論文  参考訳（メタデータ） (2024-05-14T15:28:37Z)
• Quantum algorithms for Hopcroft's problem [45.45456673484445]
  計算幾何学の基本的な問題であるホップクロフト問題に対する量子アルゴリズムについて検討する。 この問題の古典的な複雑さはよく研究されており、最もよく知られているアルゴリズムは$O(n4/3)の時間で動作する。 我々の結果は、時間複雑性が$widetilde O(n5/6)$の2つの異なる量子アルゴリズムである。
  論文  参考訳（メタデータ） (2024-05-02T10:29:06Z)
• A Quadratic Speedup in the Optimization of Noisy Quantum Optical Circuits [5.074606924176912]
  光子数分解(PNR)検出器を用いた線形光量子回路は、ガウスボソンサンプリング(GBS)とゴッテマン・キタエフ・プレスキル(GKP)のような非ガウス状態の準備の両方に使用される。 本稿では,回路パラメトリゼーションに関する検出確率,条件状態,およびそれらの勾配を計算するアルゴリズム群を紹介する。 これらのアルゴリズムは、オープンソースのフォトニック最適化ライブラリMrMustardで実装され、使用可能である。
  論文  参考訳（メタデータ） (2023-03-15T18:51:36Z)
• Quantum Algorithms for Sampling Log-Concave Distributions and Estimating Normalizing Constants [8.453228628258778]
  我々は,対数凹分布をサンプリングし,正規化定数を推定するための量子アルゴリズムを開発した。 我々はモンテカルロ法と量子ウォークの量子アナログを利用する。 また、正規化定数を推定するための1/epsilon1-o(1)$量子下界も証明する。
  論文  参考訳（メタデータ） (2022-10-12T19:10:43Z)
• Quantum learning algorithms imply circuit lower bounds [7.970954821067043]
  量子アルゴリズムの設計と回路下界の一般接続を確立する。 我々の証明は、学習理論、擬似ランダム性、計算複雑性に関するいくつかの研究に基づいている。
  論文  参考訳（メタデータ） (2020-12-03T14:03:20Z)

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

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