論文の概要: HighDist Framework: Algorithms and Applications
- arxiv url: http://arxiv.org/abs/2103.09033v2
- Date: Tue, 22 Feb 2022 08:16:25 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-07 23:42:01.535865
- Title: HighDist Framework: Algorithms and Applications
- Title（参考訳）: HighDist Framework:アルゴリズムとアプリケーション
- Authors: Debajyoti Bera, Tharrmashastha Sapv
- Abstract要約: 量子回路の出力分布のモードが与えられた閾値よりも大きいかどうかを判定する問題を導入する。
空間複雑性が分布領域の大きさの対数的であるこれらの問題の有望バージョンに対する量子アルゴリズムを設計する。
- 参考スコア（独自算出の注目度）: 0.5584060970507505
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: We introduce the problem of determining if the mode of the output
distribution of a quantum circuit (given as a black-box) is larger than a given
threshold, named HighDist, and a similar problem based on the absolute values
of the amplitudes, named HighAmp. We design quantum algorithms for promised
versions of these problems whose space complexities are logarithmic in the size
of the domain of the distribution, but the query complexities are independent.
Using these, we further design algorithms to estimate the largest probability
and the largest amplitude among the output distribution of a quantum black-box.
All of these allow us to improve the query complexity of a few recently studied
problems, namely, $k$-distinctness and its gapped version, estimating the
largest frequency in an array, estimating the min-entropy of a distribution,
and the non-linearity of a Boolean function, in the $\tilde{O}(1)$-qubits
scenario. The time-complexities of almost all of our algorithms have a small
overhead over their query complexities making them efficiently implementable on
currently available quantum backends.
- Abstract（参考訳）: 本稿では,量子回路(ブラックボックスとして提供される)の出力分布のモードが,所定のしきい値であるHighDistよりも大きいかどうかを判定する問題と,その振幅の絶対値であるHighAmpに基づく類似の問題を紹介する。
空間複雑度が分布領域の大きさの対数的であるが、クエリ複雑度は独立であるような、これらの問題の有望なバージョンに対する量子アルゴリズムを設計する。
これらを用いて、量子ブラックボックスの出力分布の中で最大確率と最大振幅を推定するアルゴリズムを更に設計する。
これらにより、最近研究されたいくつかの問題、すなわち$k$-distinctnessとそのギャップのあるバージョンにおけるクエリの複雑さを改善し、配列の最大の周波数を推定し、分布の最小エントロピーを推定し、$\tilde{O}(1)$-qubitsのシナリオでブール関数の非線形性を推定することができる。
ほぼ全てのアルゴリズムの時間的複雑さは、クエリの複雑さに対して小さなオーバーヘッドを持ち、現在利用可能な量子バックエンド上で効率的に実装できる。
関連論文リスト
- Halving the Cost of Quantum Algorithms with Randomization [0.138120109831448]
量子信号処理(QSP)は、線形演算子の変換を実装するための体系的なフレームワークを提供する。
近年の研究では、量子チャネルへのユニタリゲートを促進する技術であるランダム化コンパイルが開発されている。
提案アルゴリズムは, 平均進化が対象関数に収束するように戦略的に選択されたランダム化の確率的混合を実装し, 誤差は等価個体よりも2次的に小さい。
論文 参考訳（メタデータ） (2024-09-05T17:56:51Z) - Analysis of the Non-variational Quantum Walk-based Optimisation Algorithm [0.0]
本稿では,多種多様な最適化問題を解くために設計された非変分量子アルゴリズムを詳細に紹介する。
このアルゴリズムは、増幅状態の繰り返しの準備と測定から最適解とほぼ最適解を返す。
論文 参考訳（メタデータ） (2024-07-29T13:54:28Z) - Stochastic Quantum Sampling for Non-Logconcave Distributions and
Estimating Partition Functions [13.16814860487575]
非対数確率分布からサンプリングする量子アルゴリズムを提案する。
f$ は有限和 $f(x):= frac1Nsum_k=1N f_k(x)$ と書くことができる。
論文 参考訳（メタデータ） (2023-10-17T17:55:32Z) - Multi-sequence alignment using the Quantum Approximate Optimization
Algorithm [0.0]
本稿では、変分量子近似最適化アルゴリズム(QAOA)を用いた多重系列アライメント問題のハミルトニアン定式化と実装について述べる。
我々は、量子シミュレーターと実際の量子コンピュータ上での性能の両方において、我々のQAOA-MSAアルゴリズムの小さな例を考える。
調査されたMSAのインスタンスに対する理想的な解決策は、浅いp5量子回路でサンプリングされた最も可能性の高い状態であることが示されているが、現在のデバイスにおけるノイズのレベルは依然として深刻な課題である。
論文 参考訳（メタデータ） (2023-08-23T12:46:24Z) - Quantum Search Approaches to Sampling-Based Motion Planning [0.0]
本稿では,従来のサンプリング型モーションプランナを,量子探索アルゴリズムを用いて解くことのできるデータベース・オーラル構造として,新しい定式化を提案する。
より単純なスパース環境では、量子完全経路探索アルゴリズム (Quantum Full Path Search Algorithm, Q-FPS) を定式化し、完全なランダムパス解の重ね合わせを生成する。
密集した非構造環境において、親子接続の量子重ね合わせを生成する量子高速探索ランダムツリーアルゴリズム q-RRT を定式化する。
論文 参考訳（メタデータ） (2023-04-10T19:12:25Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - A single $T$-gate makes distribution learning hard [56.045224655472865]
この研究は、局所量子回路の出力分布の学習可能性に関する広範な評価を提供する。
ハイブリッド量子古典アルゴリズムを含む多種多様な学習アルゴリズムにおいて、深度$d=omega(log(n))$ Clifford回路に関連する生成的モデリング問題さえも困難であることを示す。
論文 参考訳（メタデータ） (2022-07-07T08:04:15Z) - A Hybrid Quantum-Classical Algorithm for Robust Fitting [47.42391857319388]
本稿では,ロバストフィッティングのためのハイブリッド量子古典アルゴリズムを提案する。
私たちのコアコントリビューションは、整数プログラムの列を解く、新しい堅牢な適合式である。
実際の量子コンピュータを用いて得られた結果について述べる。
論文 参考訳（メタデータ） (2022-01-25T05:59:24Z) - Detailed Account of Complexity for Implementation of Some Gate-Based
Quantum Algorithms [55.41644538483948]
特に、状態準備および読み出しプロセスのような実装のいくつかのステップは、アルゴリズム自体の複雑さの側面を超越することができる。
本稿では、方程式の線形系と微分方程式の線形系を解くための量子アルゴリズムの完全な実装に関わる複雑性について述べる。
論文 参考訳（メタデータ） (2021-06-23T16:33:33Z) - Space-efficient binary optimization for variational computing [68.8204255655161]
本研究では,トラベリングセールスマン問題に必要なキュービット数を大幅に削減できることを示す。
また、量子ビット効率と回路深さ効率のモデルを円滑に補間する符号化方式を提案する。
論文 参考訳（メタデータ） (2020-09-15T18:17:27Z) - On estimating the entropy of shallow circuit outputs [49.1574468325115]
確率分布と量子状態のエントロピーを推定することは情報処理の基本的な課題である。
本稿では,有界ファンインと非有界ファンアウトのゲートを持つ対数深度回路か定数深度回路のいずれかによって生成された分布や状態に対するエントロピー推定が,少なくともLearning with Errors問題と同程度難しいことを示す。
論文 参考訳（メタデータ） (2020-02-27T15:32:08Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。