論文の概要: 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を量子オラクルへの最も少ない呼び出しで検証し、与えられた信頼境界に対して最も少ないサンプルを必要とすることを示す。
関連論文リスト
- 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) - 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) - Variational learning algorithms for quantum query complexity [3.980076328494117]
量子クエリの複雑さを研究するための変分学習アルゴリズムを開発した。
量子クエリの複雑さの様々なケースを解析するために,本手法を適用した。
本手法は,NISQ(Noisy Intermediate-Scale Quantum)デバイス上で容易に実装できる。
論文 参考訳(メタデータ) (2022-05-16T05:16:15Z) - Resource Optimisation of Coherently Controlled Quantum Computations with
the PBS-calculus [55.2480439325792]
量子計算のコヒーレント制御は、いくつかの量子プロトコルやアルゴリズムを改善するために使用できる。
我々は、量子光学にインスパイアされたコヒーレント制御のためのグラフィカル言語PBS計算を洗練する。
論文 参考訳(メタデータ) (2022-02-10T18:59:52Z) - Best Arm Identification for Cascading Bandits in the Fixed Confidence
Setting [81.70513857417106]
CascadeBAIを設計し、分析する。これは、$K$アイテムのベストセットを見つけるアルゴリズムである。
CascadeBAIの時間的複雑さの上限は、決定的な分析課題を克服することによって導かれる。
その結果,カスケードBAIの性能は,時間的複雑性の低い境界の導出により,いくつかの実践的状況において最適であることが示唆された。
論文 参考訳(メタデータ) (2020-01-23T16:47:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。