Fugu-MT 論文翻訳(概要): A quantum algorithm to estimate the Gowers $U_2$ norm and linearity testing of Boolean functions

論文の概要: A quantum algorithm to estimate the Gowers $U_2$ norm and linearity testing of Boolean functions

arxiv url: http://arxiv.org/abs/2006.16523v1
Date: Tue, 30 Jun 2020 04:39:20 GMT
ステータス: 処理完了
システム内更新日: 2023-05-12 01:33:27.314284
Title: A quantum algorithm to estimate the Gowers $U_2$ norm and linearity testing of Boolean functions
Title（参考訳）: ガワーズ$U_2$ノルムを推定する量子アルゴリズムとブール関数の線形性試験
Authors: C. A. Jothishwaran, Anton Tkachenko, Sugata Gangopadhyay, Constanza Riera, Pantelimon Stanica
Abstract要約: ブール関数の Gowers $U$ norm を推定する量子アルゴリズムを提案する。線形ブール関数と、線型ブール関数の集合から$epsilon$-farのブール関数を区別する第2のアルゴリズムに拡張する。
参考スコア（独自算出の注目度）: 6.8072479152471566
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We propose a quantum algorithm to estimate the Gowers $U_2$ norm of a Boolean function, and extend it into a second algorithm to distinguish between linear Boolean functions and Boolean functions that are $\epsilon$-far from the set of linear Boolean functions, which seems to perform better than the classical BLR algorithm. Finally, we outline an algorithm to estimate Gowers $U_3$ norms of Boolean functions.
Abstract（参考訳）: 本稿では,ガワーズ$U_2$ノルムを推定する量子アルゴリズムを提案し,それを2番目のアルゴリズムに拡張して,古典的BLRアルゴリズムよりも優れた線形ブール関数の集合から$\epsilon$-farの線形ブール関数とブール関数を区別する。最後に,ブール関数の Gowers $U_3$ ノルムを推定するアルゴリズムを概説する。

関連論文リスト

A Discrete Particle Swarm Optimizer for the Design of Cryptographic Boolean Functions [1.6574413179773761]
このアルゴリズムはHu, Eberhart, Shiによる置換PSOの修正版である。 PSO速度方程式のパラメータは2つのメタ最適化手法を用いて調整される。
論文参考訳（メタデータ） (2024-01-09T14:08:42Z)
Gradient-free optimization of highly smooth functions: improved analysis and a new algorithm [87.22224691317766]
この研究は、目的関数が極めて滑らかであるという仮定の下で、ゼロ次ノイズオラクル情報による問題を研究する。ゼロオーダー射影勾配勾配アルゴリズムを2種類検討する。
論文参考訳（メタデータ） (2023-06-03T17:05:13Z)
Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
論文参考訳（メタデータ） (2023-01-30T15:46:39Z)
Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
本稿では,n+1$ qubitsしか使用しないGoemans-Williamsonアルゴリズムの変分量子アルゴリズムを提案する。補助量子ビット上で適切にパラメータ化されたユニタリ条件として目的行列を符号化することにより、効率的な最適化を実現する。各種NPハード問題に対して,Goemans-Williamsonアルゴリズムの量子的効率的な実装を考案し,提案プロトコルの有効性を実証する。
論文参考訳（メタデータ） (2022-06-30T03:15:23Z)
Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。両レベル最適化のための2つの新しいアルゴリズムを提案する。両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
論文参考訳（メタデータ） (2021-06-08T21:05:30Z)
Bayesian Optimistic Optimisation with Exponentially Decaying Regret [58.02542541410322]
現在の実用的なBOアルゴリズムは、$mathcalO(fraclogNsqrtN)$から$mathcalO(e-sqrtN)$まで、$N$は評価の数である。本稿では,boと木に基づく楽観的楽観化の概念を絡み合うことにより,無音環境における後悔を改善できる可能性について検討する。次数$mathcal O(N-sqrt)で指数的再帰を達成できる最初の実践的手法であるBOOアルゴリズムを提案する。
論文参考訳（メタデータ） (2021-05-10T13:07:44Z)
Quantum and Randomised Algorithms for Non-linearity Estimation [0.5584060970507505]
函数の非線型性は、それが任意の線型函数からの距離を示す。非線型加算誤差を近似するために、高効率な量子およびランダム化アルゴリズムを設計する。
論文参考訳（メタデータ） (2021-03-14T14:13:50Z)
Non-Boolean Quantum Amplitude Amplification and Quantum Mean Estimation [0.0]
本稿では, 量子振幅増幅と振幅推定アルゴリズムを非ブールオラクルで動作するように一般化する。非ブールオラクルの固有値 $exp(ivarphi(x)$ は$pm 1$ に制限されない。このような非ブールオラクルに基づく2つの新しい分子アルゴリズムが導入された。
論文参考訳（メタデータ） (2021-02-09T17:48:38Z)
Parameter-free Stochastic Optimization of Variationally Coherent Functions [19.468067110814808]
我々は$mathbbRdilon上で関数のクラスを1次最適化するためのアルゴリズムを設計・解析する。この2つを同時に実現したのは初めてである。
論文参考訳（メタデータ） (2021-01-30T15:05:34Z)
Quantum algorithms for spectral sums [50.045011844765185]
正半定値行列(PSD)のスペクトル和を推定するための新しい量子アルゴリズムを提案する。本稿では, スペクトルグラフ理論における3つの問題に対して, アルゴリズムと手法が適用可能であることを示す。
論文参考訳（メタデータ） (2020-11-12T16:29:45Z)
Exact Quantum Query Algorithms Outperforming Parity -- Beyond The Symmetric functions [3.652509571098291]
まず、$Omega left(2fracsqrtn2 right)$非対称関数の直和に基づくクラスに対して、最適な正確な量子クエリアルゴリズム(Q_algo(f)$)を得る。 Q_algo$のクエリ複雑性は$lceil frac3n4 rceil$であるのに対して、$D_oplus(f)$は$n-1$と$lceil frac3n4 rceの間で異なる。
論文参考訳（メタデータ） (2020-08-14T12:17:48Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。