論文の概要: Limitation of Quantum Walk Approach to the Maximum Matching Problem
- arxiv url: http://arxiv.org/abs/2510.26246v1
- Date: Thu, 30 Oct 2025 08:29:44 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-10-31 16:05:09.711407
- Title: Limitation of Quantum Walk Approach to the Maximum Matching Problem
- Title（参考訳）: 最大マッチング問題に対する量子ウォークアプローチの限界
- Authors: Alcides Gomes Andrade Júnior, Akira Matsubayashi,
- Abstract要約: 最大マッチング問題は、隣接行列で表される$n$頂点上のグラフに対して$Omega(n3/2)$以下の量子クエリ複雑性を持つ。
現在の最良の量子アルゴリズムは、クエリ複雑性$O(n7/4)$であり、これは自明な有界な$O(n2)$に対する改善である。
量子ウォーク法は、既知の(あるいは自明な)上界をクエリの複雑さで改善する高速なアルゴリズムを作成できないことを示す。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The Maximum Matching problem has a quantum query complexity lower bound of $\Omega(n^{3/2})$ for graphs on $n$ vertices represented by an adjacency matrix. The current best quantum algorithm has the query complexity $O(n^{7/4})$, which is an improvement over the trivial bound $O(n^2)$. Constructing a quantum algorithm for this problem with a query complexity improving the upper bound $O(n^{7/4})$ is an open problem. The quantum walk technique is a general framework for constructing quantum algorithms by transforming a classical random walk search into a quantum search, and has been successfully applied to constructing an algorithm with a tight query complexity for another problem. In this work we show that the quantum walk technique fails to produce a fast algorithm improving the known (or even the trivial) upper bound on the query complexity. Specifically, if a quantum walk algorithm designed with the known technique solves the Maximum Matching problem using $O(n^{2-\epsilon})$ queries with any constant $\epsilon>0$, and if the underlying classical random walk is independent of an input graph, then the guaranteed time complexity is larger than any polynomial of $n$.
- Abstract（参考訳）: 最大マッチング問題は、隣接行列で表される$n$頂点上のグラフに対して$\Omega(n^{3/2})$の量子クエリ複雑性の低い境界を持つ。
現在の最良の量子アルゴリズムは、クエリ複雑性$O(n^{7/4})$であり、これは自明な有界な$O(n^2)$に対する改善である。
この問題に対して上界の$O(n^{7/4})$を改善するクエリ複雑性を持つ量子アルゴリズムを構築することは、オープンな問題である。
量子ウォーク法は、古典的なランダムウォーク探索を量子探索に変換することによって量子アルゴリズムを構築するための一般的なフレームワークであり、他の問題に対する厳密なクエリ複雑性を持つアルゴリズムの構築に成功している。
この研究で、量子ウォーク法は、既知の(あるいは自明な)上界がクエリの複雑さに依存するように、高速なアルゴリズムを作成できないことを示す。
具体的には、既知の手法で設計された量子ウォークアルゴリズムが、任意の定数$\epsilon>0$で$O(n^{2-\epsilon})$クエリを使用して最大マッチング問題を解くと、基礎となる古典的ランダムウォークが入力グラフから独立であれば、保証された時間複雑性は$n$の多項式よりも大きい。
関連論文リスト
- Qudit-based scalable quantum algorithm for solving the integer programming problem [0.0]
プログラミング (IP) はNPのハードな最適化問題であり、現実世界の様々な問題を表現するために広く使われている。
IPを解くためのほとんどの量子アルゴリズムは、整数を量子ビットにエンコードするため、非常に非効率である。
本研究では,回路ベースでスケーラブルな量子アルゴリズムを複数の相互作用量子ビットを用いて提案し,量子スピードアップを示す。
論文 参考訳（メタデータ） (2025-08-19T15:06:49Z) - Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている
SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。
この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文 参考訳（メタデータ） (2024-08-14T19:04:13Z) - Quantum algorithms for Hopcroft's problem [45.45456673484445]
計算幾何学の基本的な問題であるホップクロフト問題に対する量子アルゴリズムについて検討する。
この問題の古典的な複雑さはよく研究されており、最もよく知られているアルゴリズムは$O(n4/3)の時間で動作する。
我々の結果は、時間複雑性が$widetilde O(n5/6)$の2つの異なる量子アルゴリズムである。
論文 参考訳（メタデータ） (2024-05-02T10:29:06Z) - Taming Quantum Time Complexity [45.867051459785976]
時間複雑性の設定において、正確さと遠心性の両方を達成する方法を示します。
我々は、トランスデューサと呼ばれるものに基づく量子アルゴリズムの設計に新しいアプローチを採用する。
論文 参考訳（メタデータ） (2023-11-27T14:45:19Z) - On the exact quantum query complexity of $\text{MOD}_m^n$ and $\text{EXACT}_{k,l}^n$ [4.956977275061968]
我々は、$textMOD_mn$を計算するための正確な量子アルゴリズムを示す。
我々は、0,1n$ を有限集合 $X$ が$n$ 未満であるような対称関数の広いクラスの正確な量子クエリ複雑性を示す。
論文 参考訳（メタデータ） (2023-03-20T08:17:32Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - Variational learning algorithms for quantum query complexity [3.980076328494117]
量子クエリの複雑さを研究するための変分学習アルゴリズムを開発した。
量子クエリの複雑さの様々なケースを解析するために,本手法を適用した。
本手法は,NISQ(Noisy Intermediate-Scale Quantum)デバイス上で容易に実装できる。
論文 参考訳（メタデータ） (2022-05-16T05:16:15Z) - Time and Query Optimal Quantum Algorithms Based on Decision Trees [2.492300648514128]
量子アルゴリズムは時間$tilde O(sqrtGT)$で実装可能であることを示す。
本アルゴリズムは,非バイナリスパンプログラムとその効率的な実装に基づいている。
論文 参考訳（メタデータ） (2021-05-18T06:51:11Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。