Fugu-MT 論文翻訳(概要): Using 1-Factorization from Graph Theory for Quantum Speedups on Clique Problems

論文の概要: Using 1-Factorization from Graph Theory for Quantum Speedups on Clique Problems

arxiv url: http://arxiv.org/abs/2308.16827v1
Date: Thu, 31 Aug 2023 15:59:35 GMT
ステータス: 処理完了
システム内更新日: 2023-09-01 13:55:10.113871
Title: Using 1-Factorization from Graph Theory for Quantum Speedups on Clique Problems
Title（参考訳）: グラフ理論からの1要素化を用いた斜め問題の量子スピードアップ
Authors: Ali Hadizadeh Moghadam, Payman Kazemikhah, Hossein Aghababa
Abstract要約: 完全グラフの一因子化に基づく新しい量子オラクル設計を提供する。また、Triangle Findingの時間複雑性を$O(n2.25 poly(log n))$に下げる際の、これらのオラクルの1つの利用についても論じる。
参考スコア（独自算出の注目度）: 0.0
License: http://creativecommons.org/licenses/by/4.0/
Abstract: The clique problems, including $k$-CLIQUE and Triangle Finding, form an important class of computational problems; the former is an NP-complete problem, while the latter directly gives lower bounds for Matrix Multiplication. A number of previous efforts have approached these problems with Quantum Computing methods, such as Amplitude Amplification. In this paper, we provide new Quantum oracle designs based on the 1-factorization of complete graphs, all of which have depth $O(n)$ instead of the $O(n^2)$ presented in previous studies. Also, we discuss the usage of one of these oracles in bringing the Triangle Finding time complexity down to $O(n^{2.25} poly(log n))$, compared to the $O(n^{2.38})$ classical record. Finally, we benchmark the number of required Amplitude Amplification iterations for another presented oracle, for solving $k$-CLIQUE.
Abstract（参考訳）: k$-CLIQUE や Triangle Finding といったclique の問題は計算問題の重要なクラスを形成し、前者はNP完全問題であり、後者は行列乗法に下位境界を与える。 Amplitude Amplification(振幅増幅)のような量子コンピューティングの手法でこれらの問題にアプローチした。本稿では,完備グラフの1因子化に基づく新しい量子オラクル設計を提案し,これらはすべて,以前の研究で提示された$O(n^2)$の代わりに深さ$O(n)$を持つ。また、これらのオラクルの1つを使って、古典レコードの$O(n^{2.38})と比較して、Triangle Findingの時間複雑性を$O(n^{2.25} poly(log n))$に下げる方法について論じる。最後に、$k$-CLIQUEを解くために、別のオラクルに対して必要な振幅増幅イテレーションの数をベンチマークする。

関連論文リスト

Pauli quantum computing: $I$ as $|0\rangle$ and $X$ as $|1\rangle$ [0.0]
パウリ量子コンピューティングという新しい量子コンピューティング形式を提案する。この形式主義では、密度行列の非対角ブロック上のパウリ基底$I$と$X$を使って情報を符号化する。パウリ量子コンピューティングにおいて、想像上の時間進化を実現し、安定的な基底状態を作成するためにリンドブラディアンを設計する方法を示す。
論文参考訳（メタデータ） (2024-12-04T08:15:31Z)
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)
Efficient Solution of Point-Line Absolute Pose [52.775981113238046]
点や線である可能性のある特徴間の3D--2D対応に基づくポーズ推定の特定の問題を再検討する。得られた解法は数値的に安定かつ高速であることを示す。
論文参考訳（メタデータ） (2024-04-25T12:09:16Z)
Quantum One-Wayness of the Single-Round Sponge with Invertible Permutations [49.1574468325115]
スポンジハッシュは、広く使われている暗号ハッシュアルゴリズムのクラスである。これまでのところ、不規則な置換は根本的なオープンな問題のままである。ランダムな2n$-bit置換でゼロペアを見つけるには、少なくとも$Omega(2n/2)$多くのクエリが必要である。
論文参考訳（メタデータ） (2024-03-07T18:46:58Z)
Quantum Speedup for the Maximum Cut Problem [6.588073742048931]
古典的なグラフに対して2次スピードアップを施した任意のグラフ$G$に対する最大カット問題を解く量子アルゴリズムを提案する。 NP完全問題に対するオラクル関連量子アルゴリズムについて,本アルゴリズムを最適とみなす。
論文参考訳（メタデータ） (2023-05-26T05:31:25Z)
Quantum Depth in the Random Oracle Model [57.663890114335736]
浅量子回路の計算能力と古典計算の組合せを包括的に評価する。いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
論文参考訳（メタデータ） (2022-10-12T17:54:02Z)
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)
Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
論文参考訳（メタデータ） (2022-06-07T18:00:01Z)
The First Optimal Acceleration of High-Order Methods in Smooth Convex Optimization [88.91190483500932]
本研究では,滑らかな凸最小化問題の解法として最適高次アルゴリズムを求めるための基本的オープンな問題について検討する。この理由は、これらのアルゴリズムが複雑なバイナリプロシージャを実行する必要があるため、最適でも実用でもないからである。我々は、最初のアルゴリズムに$mathcalOleft(epsilon-2/(p+1)right)$pthのオーダーオーラクル複雑性を与えることで、この根本的な問題を解決する。
論文参考訳（メタデータ） (2022-05-19T16:04:40Z)
Classical algorithms for Forrelation [2.624902795082451]
1対の$n$-bit Boolean 関数 $f$ と $g$ が与えられたとき、$f$ と $g$ のフーリエ変換の間の相関を推定する。この問題は、クエリの複雑さの観点から最大の量子スピードアップをもたらすことが知られている。グラフに基づく回帰問題は、任意の二部グラフに対して時間$O(n)$で解けることを示す。
論文参考訳（メタデータ） (2021-02-13T17:25:41Z)
Quantum algorithms for escaping from saddle points [7.191453718557392]
本研究では,サドル点からの脱出を保証できる保証付き量子アルゴリズムについて検討する。我々の主な貢献は、勾配降下法における古典的摂動を置き換えるという考え方である。また、Jordanによる量子勾配計算アルゴリズムの使い方を示す。
論文参考訳（メタデータ） (2020-07-20T16:42:53Z)

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