論文の概要: The Power of Adaptivity in Quantum Query Algorithms
- arxiv url: http://arxiv.org/abs/2311.16057v2
- Date: Thu, 7 Dec 2023 16:34:14 GMT
- ステータス: 処理完了
- システム内更新日: 2023-12-08 21:19:39.066542
- Title: The Power of Adaptivity in Quantum Query Algorithms
- Title（参考訳）: 量子クエリアルゴリズムにおける適応性のパワー
- Authors: Uma Girish, Makrand Sinha, Avishay Tal, Kewen Wu
- Abstract要約: 問合せモデルにおける深度計算のトレードオフについて検討し、その深さは適応的な問合せラウンドの数と1ラウンド当たりの並列クエリ数に対応する。
我々は、量子アルゴリズム間の最も強力な分離を$r$対$r-1$の適応性を持つラウンドで達成する。
- 参考スコア（独自算出の注目度）: 0.5702169790677977
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Motivated by limitations on the depth of near-term quantum devices, we study
the depth-computation trade-off in the query model, where the depth corresponds
to the number of adaptive query rounds and the computation per layer
corresponds to the number of parallel queries per round. We achieve the
strongest known separation between quantum algorithms with $r$ versus $r-1$
rounds of adaptivity. We do so by using the $k$-fold Forrelation problem
introduced by Aaronson and Ambainis (SICOMP'18). For $k=2r$, this problem can
be solved using an $r$ round quantum algorithm with only one query per round,
yet we show that any $r-1$ round quantum algorithm needs an exponential (in the
number of qubits) number of parallel queries per round.
Our results are proven following the Fourier analytic machinery developed in
recent works on quantum-classical separations. The key new component in our
result are bounds on the Fourier weights of quantum query algorithms with
bounded number of rounds of adaptivity. These may be of independent interest as
they distinguish the polynomials that arise from such algorithms from arbitrary
bounded polynomials of the same degree.
- Abstract（参考訳）: 短期量子デバイスの深さの制限によって動機づけられた問合せモデルの深度計算トレードオフについて検討し,その深さは適応的な問合せラウンド数に対応し,各層毎の計算はラウンド毎の並列クエリ数に対応している。
我々は、量子アルゴリズム間の最も強力な分離を$r$対$r-1$の適応性を持つラウンドで達成する。
我々は、Aaronson and Ambainis (SICOMP'18) が導入した$k$-fold Forrelation 問題を用いる。
この問題は、$k=2r$の場合、1ラウンドにつき1つのクエリしか持たない$r$ラウンド量子アルゴリズムで解決できるが、任意の$r-1$ラウンド量子アルゴリズムが1ラウンド当たりの並列クエリの指数(キュービット数)を必要とすることを示す。
この結果は、量子古典的分離に関する最近の研究で開発されたフーリエ解析機械によって証明される。
我々の結果における重要な新しい要素は、適応性の有界数を持つ量子クエリアルゴリズムのフーリエ重みに関するものである。
これらは、そのようなアルゴリズムから生じる多項式と、同じ次数の任意の有界多項式を区別するため、独立した関心を持つかもしれない。
関連論文リスト
- Halving the Cost of Quantum Algorithms with Randomization [0.138120109831448]
量子信号処理(QSP)は、線形演算子の変換を実装するための体系的なフレームワークを提供する。
近年の研究では、量子チャネルへのユニタリゲートを促進する技術であるランダム化コンパイルが開発されている。
提案アルゴリズムは, 平均進化が対象関数に収束するように戦略的に選択されたランダム化の確率的混合を実装し, 誤差は等価個体よりも2次的に小さい。
論文 参考訳（メタデータ） (2024-09-05T17:56:51Z) - 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) - Depth scaling of unstructured search via quantum approximate optimization [0.0]
変分量子アルゴリズムは、現在の量子計算のデファクトモデルとなっている。
そのような問題の1つは、ある文字列の特定のビットを見つけることで構成される非構造化探索である。
我々は、CTQWを用いてQAOA配列を復元し、最近のトロッター公式の理論の進歩を利用して、クエリの複雑さを束縛する。
論文 参考訳（メタデータ） (2024-03-22T18:00:03Z) - Quantum Subroutine for Variance Estimation: Algorithmic Design and Applications [80.04533958880862]
量子コンピューティングは、アルゴリズムを設計する新しい方法の基礎となる。
どの場の量子スピードアップが達成できるかという新たな課題が生じる。
量子サブルーチンの設計は、従来のサブルーチンよりも効率的で、新しい強力な量子アルゴリズムに固い柱を向ける。
論文 参考訳（メタデータ） (2024-02-26T09:32:07Z) - Quantum algorithms: A survey of applications and end-to-end complexities [90.05272647148196]
期待されている量子コンピュータの応用は、科学と産業にまたがる。
本稿では,量子アルゴリズムの応用分野について検討する。
私たちは、各領域における課題と機会を"エンドツーエンド"な方法で概説します。
論文 参考訳（メタデータ） (2023-10-04T17:53:55Z) - Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
我々は3つのハイブリッド量子k-Meansアルゴリズムを設計、実装、評価する。
我々は距離の計算を高速化するために量子現象を利用する。
我々は、我々のハイブリッド量子k-平均アルゴリズムが古典的バージョンよりも効率的であることを示す。
論文 参考訳（メタデータ） (2022-12-13T16:04:16Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - Variational learning algorithms for quantum query complexity [3.980076328494117]
量子クエリの複雑さを研究するための変分学習アルゴリズムを開発した。
量子クエリの複雑さの様々なケースを解析するために,本手法を適用した。
本手法は,NISQ(Noisy Intermediate-Scale Quantum)デバイス上で容易に実装できる。
論文 参考訳（メタデータ） (2022-05-16T05:16:15Z) - Pauli String Partitioning Algorithm with the Ising Model for
Simultaneous Measurement [0.0]
本研究では,パウリ弦を1つの量子回路で同時に測定可能な部分群に分割する効率的なアルゴリズムを提案する。
我々の分割アルゴリズムは、量子化学のための変分量子固有解法における測定総数を劇的に削減する。
論文 参考訳（メタデータ） (2022-05-09T01:49:21Z) - Using Shor's algorithm on near term Quantum computers: a reduced version [0.0]
我々は、ノイズの多い量子デバイス上で分解可能な数値の範囲を拡大するステップを推し進めるShorのアルゴリズムの縮小版を導入する。
特に、ほとんどのケースで注目すべき結果が得られており、しばしば提案されたアルゴリズムの1つで与えられた数を分解できる。
論文 参考訳（メタデータ） (2021-12-23T15:36:59Z) - Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。
本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。
提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
論文 参考訳（メタデータ） (2021-07-08T17:59:55Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。