論文の概要: Matching Triangles and Triangle Collection: Hardness based on a Weak Quantum Conjecture

• arxiv url: http://arxiv.org/abs/2207.11068v1
• Date: Fri, 22 Jul 2022 13:16:50 GMT
• ステータス: 処理完了
• システム内更新日: 2023-02-04 02:54:07.947652
• Title: Matching Triangles and Triangle Collection: Hardness based on a Weak Quantum Conjecture
• Title（参考訳）: 三角形のマッチングと三角形の収集:弱量子予想に基づく硬さ
• Authors: Andris Ambainis, Harry Buhrman, Koen Leijnse, Subhasree Patro, Florian Speelman
• Abstract要約: これら2つのグラフ問題のいずれかに対する$n1.5-epsilon$の時間量子アルゴリズムは、k-SAT, 3SUM, APSPの量子アルゴリズムを高速化することを示す。 また、データ構造とアムバイニスの変動時間探索を慎重に利用する必要がある量子アルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 0.8924669503280332
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Classically, for many computational problems one can conclude time lower bounds conditioned on the hardness of one or more of key problems: k-SAT, 3SUM and APSP. More recently, similar results have been derived in the quantum setting conditioned on the hardness of k-SAT and 3SUM. This is done using fine-grained reductions, where the approach is to (1) select a key problem $X$ that, for some function $T$, is conjectured to not be solvable by any $O(T(n)^{1-\epsilon})$ time algorithm for any constant $\epsilon > 0$ (in a fixed model of computation), and (2) reduce $X$ in a fine-grained way to these computational problems, thus giving (mostly) tight conditional time lower bounds for them. Interestingly, for Delta-Matching Triangles and Triangle Collection, classical hardness results have been derived conditioned on hardness of all three mentioned key problems. More precisely, it is proven that an $n^{3-\epsilon}$ time classical algorithm for either of these two graph problems would imply faster classical algorithms for k-SAT, 3SUM and APSP, which makes Delta-Matching Triangles and Triangle Collection worthwhile to study. In this paper, we show that an $n^{1.5-\epsilon}$ time quantum algorithm for either of these two graph problems would imply faster quantum algorithms for k-SAT, 3SUM, and APSP. We first formulate a quantum hardness conjecture for APSP and then present quantum reductions from k-SAT, 3SUM, and APSP to Delta-Matching Triangles and Triangle Collection. Additionally, based on the quantum APSP conjecture, we are also able to prove quantum lower bounds for a matrix problem and many graph problems. The matching upper bounds follow trivially for most of them, except for Delta-Matching Triangles and Triangle Collection for which we present quantum algorithms that require careful use of data structures and Ambainis' variable time search.
• Abstract（参考訳）: 古典的には、多くの計算問題に対して、k-sat、3sum、apspといった1つ以上の主要な問題の硬度に基づく時間下限を結論付けることができる。 最近では、k-SAT と 3SUM の硬さを条件とした量子環境でも同様の結果が導出されている。 これは、(1)ある関数$t$ に対して、ある定数 $o(t(n)^{1-\epsilon}) に対して、任意の定数 $\epsilon > 0$ (計算の固定モデルにおいて) の時間アルゴリズムで解くことができないと推測される、(2)これらの計算問題に対して、きめ細かい方法で$x$ を還元する、という方法である。 興味深いことに、Delta-Matching Triangles と Triangle Collection では、古典的な硬さの結果は、3つの主要な問題の硬さを条件に導出されている。 より正確には、これらの2つのグラフ問題のいずれかに対して、$n^{3-\epsilon} の時間的古典的アルゴリズムが k-SAT, 3SUM, APSP の古典的アルゴリズムを高速化することを証明している。 本稿では,k-SAT, 3SUM, APSPのいずれのグラフ問題に対しても,$n^{1.5-\epsilon} の時間量子アルゴリズムがより高速であることを示す。 まず、APSP の量子硬度予想を定式化し、k-SAT, 3SUM, APSP から Delta-Matching Triangles and Triangle Collection への量子還元を示す。 さらに、量子APSP予想に基づいて、行列問題や多くのグラフ問題に対して量子下界を証明できる。 それらの上界のマッチングは、データ構造を慎重に利用し、アンビニの可変時間探索を必要とする量子アルゴリズムを提示するデルタマッチング三角形と三角形集合を除いて、ほとんどの場合、自明に従う。

関連論文リスト

• 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)
• Local Quantum Search Algorithm for Random $k$-SAT with $Ω(n^{1+ε})$ Clauses [0.0]
  平均ケース複雑性理論に基づいて,$m=Omega(n2+delta+epsilon)$のとき,max-k-SSAT が平均計算アルゴリズムであることを示す。 また、平均ケース複雑性理論に基づいて$m=Omega(n2+delta+epsilon)$のとき、max-k-SSATが平均であることが証明される。
  論文  参考訳（メタデータ） (2024-03-05T15:03:47Z)
• Using 1-Factorization from Graph Theory for Quantum Speedups on Clique Problems [0.0]
  完全グラフの一因子化に基づく新しい量子オラクル設計を提供する。 また、Triangle Findingの時間複雑性を$O(n2.25 poly(log n))$に下げる際の、これらのオラクルの1つの利用についても論じる。
  論文  参考訳（メタデータ） (2023-08-31T15:59:35Z)
• A hybrid Quantum proposal to deal with 3-SAT problem [75.38606213726906]
  本稿では,3SAT問題を解くためのハイブリッド量子コンピューティング戦略について述べる。 この近似の性能は、量子コンピューティングの観点から3-SATを扱う際に、一連の代表的なシナリオで検証されている。
  論文  参考訳（メタデータ） (2023-06-07T12:19:22Z)
• From Bit-Parallelism to Quantum String Matching for Labelled Graphs [0.0]
  二次時間で解ける多くの問題は、ビットパラレルのスピードアップが$w$で、$w$はコンピュータワードサイズである。 このような制限されたグラフの族上の単純なビット並列アルゴリズムは、現実的な量子アルゴリズムに変換可能であることを示す。
  論文  参考訳（メタデータ） (2023-02-06T15:14:34Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)
• On Applying the Lackadaisical Quantum Walk Algorithm to Search for Multiple Solutions on Grids [63.75363908696257]
  不足量子ウォーク(英: lackadaisical quantum walk)は、頂点が重量$l$の自己ループを持つグラフ構造を探索するために開発されたアルゴリズムである。 本稿では,グリッド上の複数解の探索に不連続な量子ウォークを適用した際の問題に対処する。
  論文  参考訳（メタデータ） (2021-06-11T09:43:09Z)
• Limits of quantum speed-ups for computational geometry and other problems: Fine-grained complexity via quantum walks [0.0]
  いくつかの計算問題に対して、量子アルゴリズムの時間的複雑さを最適に下界として証明する。 我々の下界のほとんどは、既知の上界と一致しているため、量子スピードアップに厳しい制限が課せられるため、最適である。
  論文  参考訳（メタデータ） (2021-06-03T17:22:08Z)
• Quantum algorithm of a set of quantum 2-sat problem [0.0]
  本稿では,量子2-満足度(Q2SAT)問題に対する量子断熱アルゴリズムを提案する。 Q2SAT 問題に対して、ハイゼンベルク連鎖に類似したハミルトニアンを構成する。
  論文  参考訳（メタデータ） (2020-09-05T21:01:27Z)
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms [87.04438831673063]
  本稿では、生成した状態の古典的ベクトル形式を生成する効率的な読み出しプロトコルを提案する。 我々のプロトコルは、出力状態が入力行列の行空間にある場合に適合する。 我々の技術ツールの1つは、Gram-Schmidt正則手順を実行するための効率的な量子アルゴリズムである。
  論文  参考訳（メタデータ） (2020-04-14T11:05:26Z)

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

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