Fugu-MT 論文翻訳(概要): A quantum algorithm to estimate the closeness to the Strict Avalanche criterion in Boolean functions

論文の概要: A quantum algorithm to estimate the closeness to the Strict Avalanche criterion in Boolean functions

arxiv url: http://arxiv.org/abs/2211.15356v1
Date: Fri, 25 Nov 2022 12:32:01 GMT
ステータス: 処理完了
システム内更新日: 2023-01-17 20:33:35.171100
Title: A quantum algorithm to estimate the closeness to the Strict Avalanche criterion in Boolean functions
Title（参考訳）: ブール関数におけるStrict Avalanche criterionの近さを推定する量子アルゴリズム
Authors: C. A. Jothishwaran, Abhishek Chakraborty, Vishvendra Singh Poonia, Pantelimon Stanica, Sugata Gangopadhyay
Abstract要約: 与えられたブール関数の近さを厳密な雪崩基準を満たすもの(SAC)に推定する量子アルゴリズムを提案する。このアルゴリズムはBoolean関数のoracleの$n$クエリを必要とし、$n$は入力変数の数である。このアルゴリズムは、SACを量子オラクルへの最も少ない呼び出しで検証し、与えられた信頼境界に対して最も少ないサンプルを必要とすることを示す。
参考スコア（独自算出の注目度）: 4.392337343771302
License: http://creativecommons.org/licenses/by/4.0/
Abstract: We propose a quantum algorithm (in the form of a quantum oracle) that estimates the closeness of a given Boolean function to one that satisfies the ``strict avalanche criterion'' (SAC). This algorithm requires $n$ queries of the Boolean function oracle, where $n$ is the number of input variables, this is fewer than the queries required by the classical algorithm to perform the same task. We compare our approach with other quantum algorithms that may be used for estimating the closeness to SAC and it is shown our algorithm verifies SAC with the fewest possible calls to quantum oracle and requires the fewest samples for a given confidence bound.
Abstract（参考訳）: 本稿では,与えられたブール関数の閉度を,' `strict avalanche criterion'' (SAC) を満たすものに推定する量子アルゴリズムを提案する。このアルゴリズムはBoolean関数のoracleの$n$クエリを必要とし、$n$は入力変数の数であり、同じタスクを実行するのに古典的なアルゴリズムが必要とするクエリよりも少ない。我々は、SACの近さを推定するために用いられる他の量子アルゴリズムと比較し、SACを量子オラクルへの最も少ない呼び出しで検証し、与えられた信頼境界に対して最も少ないサンプルを必要とすることを示す。

関連論文リスト

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)
Efficient Implementation of a Quantum Search Algorithm for Arbitrary N [0.0]
本稿では,$N$が2のパワーではないインスタンスに対するGroverの探索アルゴリズムの拡張について述べる。計算基底状態のサブセット上での均一な量子重ね合わせ状態の生成に効率的なアルゴリズムを用いることで、多くのケースにおいてオラクル呼び出し(およびグローバーの反復)の数を大幅に削減できることを実証する。
論文参考訳（メタデータ） (2024-06-19T19:16:40Z)
When can you trust feature selection? -- I: A condition-based analysis of LASSO and generalised hardness of approximation [49.1574468325115]
近似入力を読み取る際に、LASSOのミニミサの正しいサポートセットを(確率$>1/2$で)決定できないことを示す。不適切な入力の場合、アルゴリズムは永遠に動作するので、間違った答えを出すことはない。無限条件数を持つ点を含む開集合上で定義される任意のアルゴリズムに対して、アルゴリズムが永久に実行されるか、間違った解を生成するような入力が存在する。
論文参考訳（メタデータ） (2023-12-18T18:29:01Z)
Generalized quantum Arimoto-Blahut algorithm and its application to quantum information bottleneck [55.22418739014892]
量子アリーモト・ブラフトアルゴリズムをRamakrishnanらにより一般化する。 3つの量子系を持つ量子情報ボトルネックに対して,我々のアルゴリズムを適用した。数値解析により,我々のアルゴリズムはアルゴリズムよりも優れていることが示された。
論文参考訳（メタデータ） (2023-11-19T00:06:11Z)
A Review on Quantum Approximate Optimization Algorithm and its Variants [47.89542334125886]
量子近似最適化アルゴリズム(Quantum Approximate Optimization Algorithm、QAOA)は、難解な最適化問題を解くことを目的とした、非常に有望な変分量子アルゴリズムである。この総合的なレビューは、様々なシナリオにおけるパフォーマンス分析を含む、QAOAの現状の概要を提供する。我々は,提案アルゴリズムの今後の展望と方向性を探りながら,選択したQAOA拡張と変種の比較研究を行う。
論文参考訳（メタデータ） (2023-06-15T15:28:12Z)
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 algorithm for finding minimum values in a Quantum Random Access Memory [0.0]
最適古典的決定論的アルゴリズムは、データベース内の要素数と線形に増加する時間複雑性で最小値を見つけることができる。本稿では,データベースの最小値を求める量子アルゴリズムを提案する。
論文参考訳（メタデータ） (2023-01-12T16:22:17Z)
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)
Quantum Speedup for Higher-Order Unconstrained Binary Optimization and MIMO Maximum Likelihood Detection [2.5272389610447856]
実数値の高次非制約二項最適化問題をサポートする量子アルゴリズムを提案する。提案アルゴリズムは,古典的領域におけるクエリの複雑さを低減し,量子領域における2次高速化を実現する。
論文参考訳（メタデータ） (2022-05-31T00:14:49Z)
Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文参考訳（メタデータ） (2022-05-26T20:32:36Z)

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