論文の概要: Quantum algorithms for learning a hidden graph and beyond
- arxiv url: http://arxiv.org/abs/2011.08611v2
- Date: Sat, 23 Jan 2021 10:43:50 GMT
- ステータス: 処理完了
- システム内更新日: 2022-09-24 17:50:17.899380
- Title: Quantum algorithms for learning a hidden graph and beyond
- Title（参考訳）: 隠れグラフを学習するための量子アルゴリズム
- Authors: Ashley Montanaro and Changpeng Shao
- Abstract要約: 本稿では、量子アルゴリズムを用いて、託宣によって提供された未知のグラフを学習する問題について研究する。
ORおよびパリティクエリモデルにおいて、最も優れた古典的アルゴリズムの高速化を実現する量子アルゴリズムを提供する。
さらに、グループテスト問題の"ガッペ"バージョンに対して、Ambainisらのアルゴリズムに基づいて、この問題に対する時間効率の量子アルゴリズムを与える。
- 参考スコア（独自算出の注目度）: 0.05076419064097732
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study the problem of learning an unknown graph provided via an oracle
using a quantum algorithm. We consider three query models. In the first model
("OR queries"), the oracle returns whether a given subset of the vertices
contains any edges. In the second ("parity queries"), the oracle returns the
parity of the number of edges in a subset. In the third model, we are given
copies of the graph state corresponding to the graph.
We give quantum algorithms that achieve speedups over the best possible
classical algorithms in the OR and parity query models, for some families of
graphs, and give quantum algorithms in the graph state model whose complexity
is similar to the parity query model. For some parameter regimes, the speedups
can be exponential in the parity query model. On the other hand, without any
promise on the graph, no speedup is possible in the OR query model.
A main technique we use is the quantum algorithm for solving the
combinatorial group testing problem, for which a query-efficient quantum
algorithm was given by Belovs. Here we additionally give a time-efficient
quantum algorithm for this problem, based on the algorithm of Ambainis et al.\
for a "gapped" version of the group testing problem. We also give simple
time-efficient quantum algorithms based on Fourier sampling and amplitude
amplification for learning the exact-half and majority functions, which almost
match the optimal complexity of Belovs' algorithms.
- Abstract（参考訳）: 量子アルゴリズムを用いてオラクルによって提供される未知のグラフを学習する問題を考察する。
3つのクエリモデルを考える。
最初のモデル(ORクエリ)では、オラクルは頂点の特定の部分集合がエッジを含むかどうかを返します。
第2の「パリティクエリ」では、オラクルはサブセット内のエッジの数のパリティを返します。
第3のモデルでは、グラフに対応するグラフ状態のコピーが与えられます。
ORおよびパリティ問合せモデルにおける最良な古典的アルゴリズムの高速化を実現する量子アルゴリズムをグラフの族に与え、複雑性がパリティ問合せモデルに類似したグラフ状態モデルに量子アルゴリズムを与える。
いくつかのパラメータでは、スピードアップはパリティクエリモデルで指数関数化できる。
一方、グラフに何の約束もなく、orクエリモデルではスピードアップは不可能である。
私たちが使用する主なテクニックは、クエリ効率の高い量子アルゴリズムがbelovsによって与えられた組合せ群テスト問題を解決するための量子アルゴリズムです。
さらに, ambainisらによるアルゴリズムに基づいて, この問題に対する時間効率の良い量子アルゴリズムを提案する。
グループテスト問題の "gapped" バージョンに対する。
また、フーリエサンプリングと振幅増幅に基づく簡単な時間効率の量子アルゴリズムも提供し、ベロフスのアルゴリズムの最適複雑さにほぼ一致する正確な半値関数と多数値関数を学習する。
関連論文リスト
- Quantum algorithms for Hopcroft's problem [45.45456673484445]
計算幾何学の基本的な問題であるホップクロフト問題に対する量子アルゴリズムについて検討する。
この問題の古典的な複雑さはよく研究されており、最もよく知られているアルゴリズムは$O(n4/3)の時間で動作する。
我々の結果は、時間複雑性が$widetilde O(n5/6)$の2つの異なる量子アルゴリズムである。
論文 参考訳（メタデータ） (2024-05-02T10:29:06Z) - Variational Quantum Algorithms for the Allocation of Resources in a Cloud/Edge Architecture [1.072460284847973]
変分量子アルゴリズムは, 近い将来, 古典的アルゴリズムの代替となる可能性が示唆された。
特に、2つのアルゴリズム、すなわち量子近似最適化アルゴリズム(QAOA)と変分量子固有解器(VQE)の性能を比較した。
シミュレーション実験は、クラウドと2つのエッジノードを含む %CM230124 の単純な問題に対して実施され、VQE アルゴリズムは、検索空間を制限できる適切な回路テクスタイタンサッチを備えている場合に、より良い性能を保証することを示す。
論文 参考訳（メタデータ） (2024-01-25T17:37:40Z) - Generalized quantum Arimoto-Blahut algorithm and its application to
quantum information bottleneck [55.22418739014892]
量子アリーモト・ブラフトアルゴリズムをRamakrishnanらにより一般化する。
3つの量子系を持つ量子情報ボトルネックに対して,我々のアルゴリズムを適用した。
数値解析により,我々のアルゴリズムはアルゴリズムよりも優れていることが示された。
論文 参考訳（メタデータ） (2023-11-19T00:06:11Z) - Comparison among Classical, Probabilistic and Quantum Algorithms for
Hamiltonian Cycle problem [0.0]
ハミルトニアンサイクル問題(HCP)は、n 個のノードと m 個のエッジを持つグラフ G を持ち、各ノードを正確に1度に接続する経路を見つけることである。
本稿では、計算の異なるモデル、特に確率的および量子的モデルを用いて、aHCPを解くアルゴリズムを比較する。
論文 参考訳（メタデータ） (2023-11-18T02:36:10Z) - Mind the $\tilde{\mathcal{O}}$: Asymptotically Better, but Still
Impractical, Quantum Distributed Algorithms [0.0]
確率の高い分散計算の量子ConGEST-CLIQUEモデルに2つのアルゴリズムを提案する。
従来のCONGEST-CLIQUEモデルでは、既知のアルゴリズムよりもラウンドとメッセージの複雑さが低い。
Groverの検索アルゴリズムの分散バージョンを使用して三角形探索を高速化する既存のフレームワークは、スピードアップのコアにある。
論文 参考訳（メタデータ） (2023-04-06T02:18:52Z) - Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
我々は3つのハイブリッド量子k-Meansアルゴリズムを設計、実装、評価する。
我々は距離の計算を高速化するために量子現象を利用する。
我々は、我々のハイブリッド量子k-平均アルゴリズムが古典的バージョンよりも効率的であることを示す。
論文 参考訳（メタデータ） (2022-12-13T16:04:16Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳（メタデータ） (2022-05-26T20:32:36Z) - Faster quantum mixing of Markov chains in non-regular graph with fewer
qubits [0.0]
量子の場合、マルコフ連鎖からのqsamplingは、定常分布の平方根に任意に近い振幅を持つ量子状態の準備として構成することができる。
本稿では,すべての可逆マルコフ連鎖に対する新しいqsamplingアルゴリズムを離散時間量子ウォークを用いて構築する。
非正規グラフでは、量子高速フォワードアルゴリズムの起動は、離散時間と連続時間の両方で既存の最先端のqsamplingアルゴリズムを加速させる。
論文 参考訳（メタデータ） (2022-05-12T14:08:08Z) - Quadratic Quantum Speedup for Perceptron Training [0.0]
バイナリ分類を行うパーセプトロンは、ニューラルネットワークの基本的な構成要素である。
パーセプトロンのためのオラクルを構築するためのクエリの複雑さは、古典的手法よりも2次的に改善されていることを示す。
我々のアルゴリズムはニューラルネットワークのようなより複雑な機械学習モデルを訓練するために一般化することができる。
論文 参考訳（メタデータ） (2021-09-10T06:50:57Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - Sparse Hashing for Scalable Approximate Model Counting: Theory and
Practice [36.8421113576893]
n 変数上の CNF 式 F が与えられたとき、モデルカウントや #SAT の問題は F の満足な割り当ての数を計算することである。
近年,効率的なアルゴリズム技術開発への取り組みが急増している。
論文 参考訳（メタデータ） (2020-04-30T11:17:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。