論文の概要: Hiding, Shuffling, and Triangle Finding: Quantum Algorithms on Edge Lists
- arxiv url: http://arxiv.org/abs/2412.17786v1
- Date: Mon, 23 Dec 2024 18:43:41 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-12-24 15:55:42.513624
- Title: Hiding, Shuffling, and Triangle Finding: Quantum Algorithms on Edge Lists
- Title（参考訳）: Hiding, Shuffling, and Triangle Finding: エッジリスト上の量子アルゴリズム
- Authors: Amin Shiraz Gilani, Daochen Wang, Pei Wu, Xingyu Zhou,
- Abstract要約: 三角形探索問題の3つの変種の量子クエリ複雑性について検討する。
Zhandryのレコードクエリフレームワークのバウンダリが低いことを証明します。
我々はBelovsの学習グラフアルゴリズムを3ドルで適用する。
- 参考スコア（独自算出の注目度）: 5.127310126394387
- License:
- Abstract: The edge list model is arguably the simplest input model for graphs, where the graph is specified by a list of its edges. In this model, we study the quantum query complexity of three variants of the triangle finding problem. The first asks whether there exists a triangle containing a target edge and raises general questions about the hiding of a problem's input among irrelevant data. The second asks whether there exists a triangle containing a target vertex and raises general questions about the shuffling of a problem's input. The third asks for finding a triangle in the input edge list; this problem bridges the $3$-distinctness and $3$-sum problems, which have been extensively studied by both cryptographers and complexity theorists. We provide tight or nearly tight results for all of our problems as well as some first answers to the general questions they raise. In particular, given a graph with low maximum degree, such as a random sparse graph, we prove that the quantum query complexity of triangle finding in its length-$m$ edge list is $m^{5/7 \pm o(1)}$. We prove the lower bound in Zhandry's recording query framework [CRYPTO '19] and the upper bound by adapting Belovs's learning graph algorithm for $3$-distinctness [FOCS '12].
- Abstract（参考訳）: エッジリストモデルはグラフの最も単純な入力モデルであり、グラフはそのエッジのリストによって指定される。
本モデルでは,三角形探索問題の3つの変種の量子クエリ複雑性について検討する。
第一は、対象エッジを含む三角形が存在するかどうかを問うとともに、無関係データ間の問題入力の隠蔽に関する一般的な疑問を提起する。
第二に、対象頂点を含む三角形が存在するかどうかを問うとともに、問題の入力のシャッフルに関する一般的な疑問を提起する。
この問題は、暗号学者と複雑性理論家の両方によって広く研究されている3$不連続性と3$-sum問題に橋渡しする。
すべての問題に対して,厳密あるいはほぼ厳密な結果を提供すると同時に,彼らが提起する一般的な質問に対する最初の回答も提供しています。
特に、ランダムスパースグラフのような低次グラフが与えられたとき、その長さ-m$エッジリスト中の三角形の量子的クエリの複雑さが$m^{5/7 \pm o(1)}$であることを証明する。
本研究では,Zhandry のレコードクエリフレームワーク (CRYPTO '19] の下位境界と,Belovs の学習グラフアルゴリズムを3$-distinctness [FOCS '12] に適応させることにより,上位境界を証明した。
関連論文リスト
- Quantum One-Wayness of the Single-Round Sponge with Invertible Permutations [49.1574468325115]
スポンジハッシュは、広く使われている暗号ハッシュアルゴリズムのクラスである。
これまでのところ、不規則な置換は根本的なオープンな問題のままである。
ランダムな2n$-bit置換でゼロペアを見つけるには、少なくとも$Omega(2n/2)$多くのクエリが必要である。
論文 参考訳（メタデータ） (2024-03-07T18:46:58Z) - Toward Computing Bounds for Ramsey Numbers Using Quantum Annealing [0.0]
単色三角形問題とラムゼー数問題を考える。
量子ハードウェア上では、2次非制約バイナリ最適化(QUBO)形式への変換が必要である。
我々は、D波アドバンテージ量子アニール上での動作における実装、制限、および結果について議論する。
論文 参考訳（メタデータ） (2023-11-08T00:16:46Z) - Quantum computing algorithms for inverse problems on graphs and an
NP-complete inverse problem [2.107421958337625]
有限グラフ $(X,E)$ に対する逆問題を考える。
この問題には特定の条件下でのユニークな解法があることを示し、量子計算法を開発した。
論文 参考訳（メタデータ） (2023-06-08T14:48:48Z) - Quantum Speedup for the Maximum Cut Problem [6.588073742048931]
古典的なグラフに対して2次スピードアップを施した任意のグラフ$G$に対する最大カット問題を解く量子アルゴリズムを提案する。
NP完全問題に対するオラクル関連量子アルゴリズムについて,本アルゴリズムを最適とみなす。
論文 参考訳（メタデータ） (2023-05-26T05:31:25Z) - Matching Triangles and Triangle Collection: Hardness based on a Weak
Quantum Conjecture [0.8924669503280332]
これら2つのグラフ問題のいずれかに対する$n1.5-epsilon$の時間量子アルゴリズムは、k-SAT, 3SUM, APSPの量子アルゴリズムを高速化することを示す。
また、データ構造とアムバイニスの変動時間探索を慎重に利用する必要がある量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-07-22T13:16:50Z) - Shortest Paths in Graphs with Matrix-Valued Edges: Concepts, Algorithm
and Application to 3D Multi-Shape Analysis [69.08838724594584]
グラフ内の最短経路を見つけることは、コンピュータビジョンやグラフィックスにおける多くの問題に関係している。
本稿では,行列値のエッジを持つグラフにおいて,最短経路のグラフ理論を新たに導入する。
論文 参考訳（メタデータ） (2021-12-08T08:23:37Z) - Random Subgraph Detection Using Queries [29.192695995340653]
植込み高密度部分グラフ検出問題は、与えられた(ランダム)グラフに異常に密度の高い部分グラフが存在するかどうかをテストするタスクを指す。
本稿では,適応的なエッジクエリを用いてグラフの比較的小さな部分のみを観測できる,上記の問題の自然な変形について考察する。
このモデルでは,植込み部分グラフの存在を検出するのに必要なクエリ数と十分なクエリ数(準多項式最適アルゴリズムを伴う)を決定する。
論文 参考訳（メタデータ） (2021-10-02T07:41:17Z) - Solving correlation clustering with QAOA and a Rydberg qudit system: a
full-stack approach [94.37521840642141]
量子近似最適化アルゴリズム(QAOA)とクォーディットを用いた相関クラスタリング問題について検討する。
具体的には、中性原子量子コンピュータを検討し、相関クラスタリングのためのフルスタックアプローチを提案する。
ゲート数によって定量化されるように、quditの実装はqubitエンコーディングよりも優れていることを示す。
論文 参考訳（メタデータ） (2021-06-22T11:07:38Z) - 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) - A simple geometric proof for the benefit of depth in ReLU networks [57.815699322370826]
本論文では, 多層フィードフォワードネットワークにおける深度の利点を, 整流活性化(深度分離)により証明する。
我々は、線形深さ($m$)と小さな定数幅($leq 4$)を持つ具体的なニューラルネットワークを示し、問題をゼロエラーで分類する。
論文 参考訳（メタデータ） (2021-01-18T15:40:27Z) - Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
我々は高密度サブグラフ発見のための新しい学習問題を導入する。
まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。
そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
論文 参考訳（メタデータ） (2020-06-24T11:37:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。