論文の概要: Quantum and Randomised Algorithms for Non-linearity Estimation
- arxiv url: http://arxiv.org/abs/2103.07934v2
- Date: Mon, 27 Dec 2021 11:47:42 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-08 04:26:54.295077
- Title: Quantum and Randomised Algorithms for Non-linearity Estimation
- Title（参考訳）: 非線型性推定のための量子およびランダム化アルゴリズム
- Authors: Debajyoti Bera, Tharrmashastha Sapv
- Abstract要約: 函数の非線型性は、それが任意の線型函数からの距離を示す。
非線型加算誤差を近似するために、高効率な量子およびランダム化アルゴリズムを設計する。
- 参考スコア（独自算出の注目度）: 0.5584060970507505
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: Non-linearity of a Boolean function indicates how far it is from any linear
function. Despite there being several strong results about identifying a linear
function and distinguishing one from a sufficiently non-linear function, we
found a surprising lack of work on computing the non-linearity of a function.
The non-linearity is related to the Walsh coefficient with the largest absolute
value; however, the naive attempt of picking the maximum after constructing a
Walsh spectrum requires $\Theta(2^n)$ queries to an $n$-bit function. We
improve the scenario by designing highly efficient quantum and randomised
algorithms to approximate the non-linearity allowing additive error, denoted
$\lambda$, with query complexities that depend polynomially on $\lambda$. We
prove lower bounds to show that these are not very far from the optimal ones.
The number of queries made by our randomised algorithm is linear in $n$,
already an exponential improvement, and the number of queries made by our
quantum algorithm is surprisingly independent of $n$. Our randomised algorithm
uses a Goldreich-Levin style of navigating all Walsh coefficients and our
quantum algorithm uses a clever combination of Deutsch-Jozsa, amplitude
amplification and amplitude estimation to improve upon the existing quantum
versions of the Goldreich-Levin technique.
- Abstract（参考訳）: ブール関数の非線形性は、どの線型関数からの距離を示す。
線形関数を同定し,その関数を十分に非線形な関数と区別することに関して,いくつかの強い結果が得られたが,関数の非線形性を計算する作業が驚くほど欠如していることがわかった。
非線形性は絶対値が最も大きいウォルシュ係数と関係があるが、ウォルシュスペクトルを構築した後の最大値の選択には$\theta(2^n)$クエリを$n$-bit関数に要求する。
我々は,高効率な量子アルゴリズムとランダム化アルゴリズムを設計し,加法誤差を許容する非線形性,すなわち$\lambda$を近似し,多項式的に$\lambda$に依存する問合せ複雑度を求める。
我々はこれらが最適値からそれほど遠くないことを示すために下界を証明する。
ランダム化アルゴリズムによるクエリの数は$n$で線形であり、すでに指数関数的に改善されており、量子アルゴリズムによるクエリの数は$n$とは驚くほど無関係である。
我々のランダム化アルゴリズムは、全てのウォルシュ係数をナビゲートするゴルトライヒ=レーヴィン方式を使用し、我々の量子アルゴリズムは、Deutsch-Jozsa、振幅増幅、振幅推定の巧妙な組み合わせを用いて、既存のGoldreich-Levin法の量子バージョンを改善する。
関連論文リスト
- Quantum Algorithms for Non-smooth Non-convex Optimization [30.576546266390714]
本稿では、リプシッツ連続目的の$(,epsilon)$-Goldstein定常点を求める問題を考える。
代理オラクル関数に対するゼロ階量子推定器を構築する。
論文 参考訳（メタデータ） (2024-10-21T16:52:26Z) - Quantum and classical algorithms for nonlinear unitary dynamics [0.5729426778193399]
我々は$fracd|urangledtという形の非線形微分方程式に対する量子アルゴリズムを提案する。
また,Euler法に基づく古典的アルゴリズムを導入し,制限された場合の量子アルゴリズムへのコンパラブルなスケーリングを実現する。
論文 参考訳（メタデータ） (2024-07-10T14:08:58Z) - Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。
我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
論文 参考訳（メタデータ） (2024-01-17T18:59:38Z) - The discrete adiabatic quantum linear system solver has lower constant factors than the randomized adiabatic solver [2.350508194508073]
複雑性上の上界に対する明示的な定数係数は、上界から直観的に予想されるよりもはるかに効率的であることを示す。
特に、より効率的であると主張する[arXiv:2305.11352]からのランダム化アプローチよりも、桁違いに効率的である。
論文 参考訳（メタデータ） (2023-12-12T19:36:41Z) - Gradient-free optimization of highly smooth functions: improved analysis
and a new algorithm [87.22224691317766]
この研究は、目的関数が極めて滑らかであるという仮定の下で、ゼロ次ノイズオラクル情報による問題を研究する。
ゼロオーダー射影勾配勾配アルゴリズムを2種類検討する。
論文 参考訳（メタデータ） (2023-06-03T17:05:13Z) - Efficient quantum linear solver algorithm with detailed running costs [0.0]
量子信号処理に基づくフィルタリング手法を用いて,アイデアダイアバティックな量子コンピューティングを組み合わせた量子線形解法アルゴリズムを提案する。
我々のプロトコルは、初期実装において、最先端技術に対する量子線形解決器のコストを桁違いに削減する。
論文 参考訳（メタデータ） (2023-05-19T00:07:32Z) - Deterministic Nonsmooth Nonconvex Optimization [94.01526844386977]
次元自由な次元自由アルゴリズムを得るにはランダム化が必要であることを示す。
我々のアルゴリズムは、ReLUネットワークを最適化する最初の決定論的次元自由アルゴリズムを得る。
論文 参考訳（メタデータ） (2023-02-16T13:57:19Z) - 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) - Optimal scaling quantum linear systems solver via discrete adiabatic
theorem [0.9846257338039974]
離散的に最適となる線形系を解くための量子アルゴリズムを開発した。
既存の最適化手法と比較して,本アルゴリズムはよりシンプルで実装が容易である。
論文 参考訳（メタデータ） (2021-11-16T00:21:37Z) - Quantum algorithms for spectral sums [50.045011844765185]
正半定値行列(PSD)のスペクトル和を推定するための新しい量子アルゴリズムを提案する。
本稿では, スペクトルグラフ理論における3つの問題に対して, アルゴリズムと手法が適用可能であることを示す。
論文 参考訳（メタデータ） (2020-11-12T16:29:45Z) - Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions [84.49087114959872]
非滑らかで非滑らかな関数の定常点を見つけるための最初の非漸近解析を提供する。
特に、アダマール半微分可能函数(おそらく非滑らか関数の最大のクラス)について研究する。
論文 参考訳（メタデータ） (2020-02-10T23:23:04Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。