論文の概要: Following Forrelation -- Quantum Algorithms in Exploring Boolean
Functions' Spectra
- arxiv url: http://arxiv.org/abs/2104.12212v2
- Date: Tue, 28 Sep 2021 05:18:11 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-02 10:59:42.325204
- Title: Following Forrelation -- Quantum Algorithms in Exploring Boolean
Functions' Spectra
- Title（参考訳）: フォリレーション-ブール関数のスペクトル探索における量子アルゴリズム
- Authors: Suman Dutta, Subhamoy Maitra and Chandra Sekhar Mukherjee
- Abstract要約: 我々は、Forrelation値を得るために量子アルゴリズムを再検討する。
屈曲双対性に基づく約束問題を含む既存の2次元フォルレレーションの定式化を導入する。
線形関数の重ね合わせで量子アルゴリズムを微調整し、相互相関サンプリング技術を得る。
- 参考スコア（独自算出の注目度）: 3.2498534294827044
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Here we revisit the quantum algorithms for obtaining Forrelation [Aaronson et
al, 2015] values to evaluate some of the well-known cryptographically
significant spectra of Boolean functions, namely the Walsh spectrum, the
cross-correlation spectrum and the autocorrelation spectrum. We introduce the
existing 2-fold Forrelation formulation with bent duality based promise
problems as desirable instantiations. Next we concentrate on the $3$-fold
version through two approaches. First, we judiciously set-up some of the
functions in $3$-fold Forrelation, so that given an oracle access, one can
sample from the Walsh Spectrum of $f$. Using this, we obtain improved results
than what we obtain from the Deutsch-Jozsa algorithm, and in turn it has
implications in resiliency checking. Furthermore, we use similar idea to obtain
a technique in estimating the cross-correlation (and thus autocorrelation)
value at any point, improving upon the existing algorithms. Finally, we tweak
the quantum algorithm with superposition of linear functions to obtain a
cross-correlation sampling technique. To the best of our knowledge, this is the
first cross-correlation sampling algorithm with constant query complexity. This
also provides a strategy to check if two functions are uncorrelated of degree
$m$. We further modify this using Dicke states so that the time complexity
reduces, particularly for constant values of $m$.
- Abstract（参考訳）: ここでは,forrelation [aaronson et al, 2015]値を得るための量子アルゴリズムを再検討し,ブール関数(ウォルシュスペクトル,相互相関スペクトル,自己相関スペクトル)の暗号学的に重要なスペクトルを評価する。
本稿では, 2-fold forrelation 式と有向双対性に基づくpromise問題を望ましいインスタンス化として導入する。
次に、2つのアプローチで3ドルのバージョンに集中します。
まず、いくつかの関数を$$$-fold forrelationで任意に設定するので、oracleアクセスがあれば、walshのスペクトルから$f$のサンプルを取得できます。
これを用いることで、deutsch-jozsaアルゴリズムで得られるものよりも優れた結果を得ることができ、その結果、レジリエンスチェックに影響を及ぼす。
さらに、類似のアイデアを用いて任意の時点における相互相関(および自己相関)値を推定し、既存のアルゴリズムを改良する手法を得る。
最後に,線形関数の重畳による量子アルゴリズムの微調整を行い,相互相関サンプリング手法を提案する。
我々の知る限りでは、これはクエリの複雑さが一定である最初のクロス相関サンプリングアルゴリズムである。
これはまた、2つの関数が次数$m$と無関係かどうかをチェックする戦略を提供する。
さらに、Dickeステートを使って、特に$m$の定数値に対して、時間複雑性が減少するように修正する。
関連論文リスト
- Quantum Algorithms for the Pathwise Lasso [1.8058773918890538]
古典的LARS(Least Angle Regression)パスワイズアルゴリズムに基づく新しい量子高次元線形回帰アルゴリズムを提案する。
我々の量子アルゴリズムは、ペナルティ項が変化するにつれて、完全な正規化パスを提供するが、特定の条件下では、イテレーション毎に2次的に高速である。
我々は、KKT条件の近似バージョンと双対性ギャップにより、LARSアルゴリズムがエラーに対して堅牢であることを証明した。
論文 参考訳（メタデータ） (2023-12-21T18:57:54Z) - 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) - Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and
Optimal Algorithms [64.10576998630981]
最適なヘッセン依存型サンプルの複雑さを, 初めて厳密に評価した。
ヘシアン非依存のアルゴリズムは、すべてのヘシアンインスタンスに対して最適なサンプル複雑さを普遍的に達成する。
本アルゴリズムにより得られたサンプルの最適複雑さは,重み付き雑音分布においても有効である。
論文 参考訳（メタデータ） (2023-06-21T17:03:22Z) - Non-asymptotic convergence bounds for Sinkhorn iterates and their
gradients: a coupling approach [10.568851068989972]
本稿では,アルゴリズムの効率的な解法を実現するために,元のOT問題であるエントロピックOT問題の緩和に焦点をあてる。
この定式化はSchr"odinger Bridge問題としても知られ、特に最適制御(SOC)と結びつき、人気のあるシンクホーンアルゴリズムで解くことができる。
論文 参考訳（メタデータ） (2023-04-13T13:58:25Z) - Twisted hybrid algorithms for combinatorial optimization [68.8204255655161]
提案されたハイブリッドアルゴリズムは、コスト関数をハミルトニアン問題にエンコードし、回路の複雑さの低い一連の状態によってエネルギーを最適化する。
レベル$p=2,ldots, 6$の場合、予想される近似比をほぼ維持しながら、レベル$p$を1に減らすことができる。
論文 参考訳（メタデータ） (2022-03-01T19:47:16Z) - Quantum algorithms for approximate function loading [0.0]
我々は,Grover-RudolphアルゴリズムにインスパイアされたNISQ時代の量子状態生成法を2つ導入した。
上述の滑らかさ条件を超えて関数をロードできる変分アルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-11-15T17:36:13Z) - Solving correlation clustering with QAOA and a Rydberg qudit system: a
full-stack approach [94.37521840642141]
量子近似最適化アルゴリズム(QAOA)とクォーディットを用いた相関クラスタリング問題について検討する。
具体的には、中性原子量子コンピュータを検討し、相関クラスタリングのためのフルスタックアプローチを提案する。
ゲート数によって定量化されるように、quditの実装はqubitエンコーディングよりも優れていることを示す。
論文 参考訳（メタデータ） (2021-06-22T11:07:38Z) - Classical algorithms for Forrelation [2.624902795082451]
1対の$n$-bit Boolean 関数 $f$ と $g$ が与えられたとき、$f$ と $g$ のフーリエ変換の間の相関を推定する。
この問題は、クエリの複雑さの観点から最大の量子スピードアップをもたらすことが知られている。
グラフに基づく回帰問題は、任意の二部グラフに対して時間$O(n)$で解けることを示す。
論文 参考訳（メタデータ） (2021-02-13T17:25:41Z) - Finite-Time Analysis for Double Q-learning [50.50058000948908]
二重Q-ラーニングのための非漸近的有限時間解析を初めて提供する。
同期と非同期の二重Q-ラーニングの両方が,グローバル最適化の$epsilon$-accurate近辺に収束することが保証されていることを示す。
論文 参考訳（メタデータ） (2020-09-29T18:48:21Z) - Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth
Nonlinear TD Learning [145.54544979467872]
本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。
本研究の結果は, 同時一次および二重側収束の形で表される。
論文 参考訳（メタデータ） (2020-08-23T20:36:49Z) - Exploiting Higher Order Smoothness in Derivative-free Optimization and
Continuous Bandits [99.70167985955352]
強凸関数のゼロ次最適化問題について検討する。
予測勾配降下アルゴリズムのランダム化近似を考察する。
その結果,0次アルゴリズムはサンプルの複雑性や問題パラメータの点でほぼ最適であることが示唆された。
論文 参考訳（メタデータ） (2020-06-14T10:42:23Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。