論文の概要: Quantum property testing in sparse directed graphs

• arxiv url: http://arxiv.org/abs/2410.05001v1
• Date: Mon, 7 Oct 2024 13:00:43 GMT
• ステータス: 処理完了
• システム内更新日: 2024-11-02 00:48:04.706938
• Title: Quantum property testing in sparse directed graphs
• Title（参考訳）: スパース指向グラフにおける量子特性試験
• Authors: Simon Apers, Frédéric Magniez, Sayantan Sen, Dániel Szabó,
• Abstract要約: 古典的な一方向モデルでは、$k$-star-freeness、より一般に$k$-source-subgraph-freenessをテストするという問題は、大きめの$k$にとってほとんど極端に難しい。 量子的にも線形なクエリ数が必要であることも示しています。
• 参考スコア（独自算出の注目度）: 0.9624643581968987
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We initiate the study of quantum property testing in sparse directed graphs, and more particularly in the unidirectional model, where the algorithm is allowed to query only the outgoing edges of a vertex. In the classical unidirectional model the problem of testing $k$-star-freeness, and more generally $k$-source-subgraph-freeness, is almost maximally hard for large $k$. We prove that this problem has almost quadratic advantage in the quantum setting. Moreover, we prove that this advantage is nearly tight, by showing a quantum lower bound using the method of dual polynomials on an intermediate problem for a new, property testing version of the $k$-collision problem that was not studied before. To illustrate that not all problems in graph property testing admit such a quantum speedup, we consider the problem of $3$-colorability in the related undirected bounded-degree model, when graphs are now undirected. This problem is maximally hard to test classically, and we show that also quantumly it requires a linear number of queries.
• Abstract（参考訳）: 我々は、スパース指向グラフにおける量子特性試験の研究を始め、特に一方向モデルにおいて、アルゴリズムは頂点の外縁のみを問うことができる。 古典的な一方向モデルでは、$k$-star-freeness、より一般に$k$-source-subgraph-freenessをテストするという問題は、大きめの$k$にとってほとんど極端に難しい。 我々は、この問題が量子環境においてほぼ2次的な優位性を持っていることを証明した。 さらに、この利点は、以前に研究されなかった$k$-collision問題の新しい特性試験バージョンに対して、中間問題に対する双対多項式法を用いて量子下界を示すことにより、ほぼ緊密であることを示す。 グラフ特性検定におけるすべての問題がそのような量子スピードアップを許容するわけではないことを示すために、グラフが現在無向化されているとき、関連する無向有界次数モデルにおける3$-colorabilityの問題を考察する。 この問題は古典的なテストが極端に困難であり、量子的にも線形なクエリ数を必要とすることを示す。

関連論文リスト

• Global Phase Helps in Quantum Search: Yet Another Look at the Welded Tree Problem [55.80819771134007]
  本稿では、離散時間量子ウォークによる溶接木問題に対する最適線形打撃時間の簡単な証明を行う。 同じ手法は他の1次元階層グラフにも適用できる。
  論文  参考訳（メタデータ） (2024-04-30T11:45:49Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。 我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
  論文  参考訳（メタデータ） (2024-01-17T18:59:38Z)
• Lower Bounds for Unitary Property Testing with Proofs and Advice [0.0]
  本稿では,一元性検定における量子クエリの下位境界を証明するための新しい手法を提案する。 すべての得られる下限は$mathsfC$-testerで$mathsfC subseteq mathsfQMA(2)/mathsfqpoly$である。 我々は、$mathsfQMA(2) notsupset mathsfSBQP$と$mathsfQMA/mathsfqpolyの量子オラクルが存在することを示した。
  論文  参考訳（メタデータ） (2024-01-15T19:00:36Z)
• New Approaches to Complexity via Quantum Graphs [0.0]
  量子グラフに対するclique問題を紹介し,研究する。 我々の問題に対する入力は、回路によって誘導される量子チャネルとして表現される。 言語内のチャネルのコレクションを変更することで、これらがクラス$textsfNP$, $textsfMA$, $textsfQMA$, $textsfQMA(2)$の完全な問題を引き起こします。
  論文  参考訳（メタデータ） (2023-09-22T14:20:14Z)
• 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)
• Experimental analysis of quantum annealers and hybrid solvers using benchmark optimization problems [0.0]
  本稿では、D-Waveの量子システムにおけるハミルトンサイクル問題(HCP)とトラベリングセールスマン問題(TSP)について検討する。
  論文  参考訳（メタデータ） (2022-02-17T23:46:27Z)
• Learning Sparse Graph with Minimax Concave Penalty under Gaussian Markov Random Fields [51.07460861448716]
  本稿では,データから学ぶための凸解析フレームワークを提案する。 三角凸分解はその上部に対応する変換によって保証されることを示す。
  論文  参考訳（メタデータ） (2021-09-17T17:46:12Z)
• 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)
• Graph Coloring with Quantum Annealing [0.0]
  そこで我々は,D-Wave 2X を独立セットサンプリングとして用いたグラフカラー化近似アルゴリズムを開発した。 ランダムに生成された小さなグラフインスタンスのセットは、テストセットとして役立ちます。 我々の性能分析は、ハイブリッド量子古典アルゴリズムにおける量子優位性に限界があることを示唆している。
  論文  参考訳（メタデータ） (2020-12-08T15:08:22Z)
• Sample-efficient learning of quantum many-body systems [17.396274240172122]
  ギブス状態から得られた量子多体系のハミルトニアンを学習する問題について検討する。 量子ハミルトン学習問題に対する最初のサンプル効率アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-04-15T18:01:59Z)

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

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