論文の概要: Quantum Speedup and Limitations on Matroid Property Problems
- arxiv url: http://arxiv.org/abs/2111.12900v2
- Date: Fri, 25 Mar 2022 00:56:59 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-06 21:55:11.250577
- Title: Quantum Speedup and Limitations on Matroid Property Problems
- Title（参考訳）: マットロイド特性問題における量子スピードアップと限界
- Authors: Xiaowei Huang, Jingquan Luo, Lvzhou Li
- Abstract要約: 二次量子スピードアップは、マトロイドのサーキット(ベース、フラット、ハイパープレーン)の数を求める計算問題に対して可能である。
ほぼ最適な量子アルゴリズムは、クエリ複雑性$O(log nsqrtbinomnlfloor n/2rfloor/n)$で与えられる。
舗装マトロイド決定問題では、クエリの複雑さについて低い境界$Omega(sqrtbinomnlfloor n/2rfloor/n)$を得る。
- 参考スコア（独自算出の注目度）: 5.654637296499481
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: This paper initiates the study of quantum algorithms for matroid property
problems. It is shown that quadratic quantum speedup is possible for the
calculation problem of finding the girth or the number of circuits (bases,
flats, hyperplanes) of a matroid, and for the decision problem of deciding
whether a matroid is uniform or Eulerian, by giving a uniform lower bound
$\Omega(\sqrt{\binom{n}{\lfloor n/2\rfloor}})$ on the query complexity for all
these problems. On the other hand, for the uniform matroid decision problem, an
asymptotically optimal quantum algorithm is proposed which achieves the lower
bound, and for the girth problem, an almost optimal quantum algorithm is given
with query complexity $O(\log n\sqrt{\binom{n}{\lfloor n/2\rfloor}})$. In
addition, for the paving matroid decision problem, a lower bound
$\Omega(\sqrt{\binom{n}{\lfloor n/2\rfloor}/n})$ on the query complexity is
obtained, and an $O(\sqrt{\binom{n}{\lfloor n/2\rfloor}})$ quantum algorithm is
presented.
- Abstract（参考訳）: 本稿では,matroid特性問題に対する量子アルゴリズムの研究を開始する。
二次量子スピードアップは、マトロイドのサースや回路(ベース、フラット、ハイパープレーン)数を求める計算問題や、マトロイドが均一であるかユーレリアであるかを決定する決定問題に対して、これらの問題すべてに対するクエリ複雑性について、一様下界$\Omega(\sqrt{\binom{n}{\lfloor n/2\rfloor}})を与えられることによって可能である。
一方、一様マトロイド決定問題に対しては、下限値を達成する漸近的最適量子アルゴリズムが提案され、桁問題に対しては、クエリ複雑性$o(\log n\sqrt{\binom{n}{\lfloor n/2\rfloor}})$でほぼ最適量子アルゴリズムが与えられる。
また, 舗装マトロイド決定問題に対して, クエリの複雑性について, 低界$\Omega(\sqrt{\binom{n}{\lfloor n/2\rfloor}/n})$を求め, 量子アルゴリズムで$O(\sqrt{\binom{n}{\lfloor n/2\rfloor}})$Oを示す。
関連論文リスト
- 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) - A square-root speedup for finding the smallest eigenvalue [0.6597195879147555]
エルミート行列の最小固有値を求める量子アルゴリズムについて述べる。
このアルゴリズムは、量子位相推定と量子振幅推定を組み合わせて、2次高速化を実現する。
また、同じランタイムで同様のアルゴリズムを提供し、行列の低エネルギー部分空間に主に置かれる量子状態の準備を可能にします。
論文 参考訳（メタデータ） (2023-11-07T22:52:56Z) - Near-Optimal Bounds for Learning Gaussian Halfspaces with Random
Classification Noise [50.64137465792738]
この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。
我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
論文 参考訳（メタデータ） (2023-07-13T18:59:28Z) - Information-Computation Tradeoffs for Learning Margin Halfspaces with
Random Classification Noise [50.64137465792738]
ランダム分類ノイズを用いたPAC$gamma$-marginハーフスペースの問題について検討する。
我々は、問題のサンプル複雑性と計算効率の良いアルゴリズムのサンプル複雑性との間に固有のギャップを示唆する情報計算トレードオフを確立する。
論文 参考訳（メタデータ） (2023-06-28T16:33:39Z) - Quantum and classical query complexities for determining connectedness
of matroids [5.654637296499481]
接続性はマトロイドの基本的な構造特性であり、アルゴリズムによって50年以上研究されてきた。
量子アルゴリズムは$O(n3/2)$クエリで、古典的なクエリよりも証明可能な量子スピードアップを示す。
論文 参考訳（メタデータ） (2023-06-21T08:31:52Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文 参考訳（メタデータ） (2022-12-03T02:45:23Z) - Pauli String Partitioning Algorithm with the Ising Model for
Simultaneous Measurement [0.0]
本研究では,パウリ弦を1つの量子回路で同時に測定可能な部分群に分割する効率的なアルゴリズムを提案する。
我々の分割アルゴリズムは、量子化学のための変分量子固有解法における測定総数を劇的に削減する。
論文 参考訳（メタデータ） (2022-05-09T01:49:21Z) - Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。
この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
論文 参考訳（メタデータ） (2021-08-19T16:16:48Z) - An Online Algorithm for Maximum-Likelihood Quantum State Tomography [6.261444979025642]
最大類似量子状態トモグラフィのための最初のオンラインアルゴリズムを提案する。
アルゴリズムの期待される数値誤差は$o(sqrt ( 1 / t ) d log d )$であり、ここで$t$は反復数を表す。
論文 参考訳（メタデータ） (2020-12-31T08:21:50Z) - Second-order Conditional Gradient Sliding [79.66739383117232]
本稿では,emphSecond-Order Conditional Gradient Sliding (SOCGS)アルゴリズムを提案する。
SOCGSアルゴリズムは、有限個の線形収束反復の後、原始ギャップに二次的に収束する。
実現可能な領域が線形最適化オラクルを通してのみ効率的にアクセスできる場合に有用である。
論文 参考訳（メタデータ） (2020-02-20T17:52:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。