論文の概要: 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予想に基づいて、行列問題や多くのグラフ問題に対して量子下界を証明できる。
それらの上界のマッチングは、データ構造を慎重に利用し、アンビニの可変時間探索を必要とする量子アルゴリズムを提示するデルタマッチング三角形と三角形集合を除いて、ほとんどの場合、自明に従う。
関連論文リスト
- Efficiency of k-Local Quantum Search and its Adiabatic Variant on Random
k-SAT [0.0]
本稿では、$k$-local quantum searchと呼ばれる、構造化量子探索アルゴリズムのファミリーを紹介する。
最大$k$-SSATは、平均ケース複雑性理論に基づく$m=Omega(n2+epsilon)$が平均であることを証明する。
論文 参考訳(メタデータ) (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) - Complexity-Theoretic Limitations on Quantum Algorithms for Topological
Data Analysis [59.545114016224254]
トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。
我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。
我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
論文 参考訳(メタデータ) (2022-09-28T17:53:25Z) - Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。
本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。
提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
論文 参考訳(メタデータ) (2021-07-08T17:59:55Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。