論文の概要: A polynomial quantum computing algorithm for solving the dualization
problem
- arxiv url: http://arxiv.org/abs/2308.14819v1
- Date: Mon, 28 Aug 2023 18:12:54 GMT
- ステータス: 処理完了
- システム内更新日: 2023-08-30 17:08:52.485915
- Title: A polynomial quantum computing algorithm for solving the dualization
problem
- Title(参考訳): 双対化問題を解決する多項式量子計算アルゴリズム
- Authors: Mauro Mezzini, Fernando Cuartero Gomez, Fernando Pelayo, Jose Javier
Paulet Gonzales, Hernan Indibil de la Cruz Calvo, Vicente Pascual
- Abstract要約: 2つの単調素関数 $f:0,1n to 0,1$ と $g:0,1n to 0,1$ が与えられたとき、双対化問題は$g$が$f$の双対かどうかを決定することである。
本稿では,双対化問題の決定版を時間内に解く量子コンピューティングアルゴリズムを提案する。
- 参考スコア(独自算出の注目度): 75.38606213726906
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Given two prime monotone boolean functions $f:\{0,1\}^n \to \{0,1\}$ and
$g:\{0,1\}^n \to \{0,1\}$ the dualization problem consists in determining if
$g$ is the dual of $f$, that is if $f(x_1, \dots, x_n)=
\overline{g}(\overline{x_1}, \dots \overline{x_n})$ for all $(x_1, \dots x_n)
\in \{0,1\}^n$. Associated to the dualization problem there is the
corresponding decision problem: given two monotone prime boolean functions $f$
and $g$ is $g$ the dual of $f$? In this paper we present a quantum computing
algorithm that solves the decision version of the dualization problem in
polynomial time.
- Abstract(参考訳): 2つの素単調ブール関数 $f:\{0,1\}^n \to \{0,1\}$ と $g:\{0,1\}^n \to \{0,1\}$ が$f$の双対であるかどうか、すなわち$f(x_1, \dots, x_n)= \overline{g}(\overline{x_1}, \dots \overline{x_n})$ がすべての$(x_1, \dots x_n) \in \{0,1\}^n$ に対して成り立つ。
2つの単調素ブール関数が$f$と$g$が$f$の双対であるとき、$g$は$f$?
本稿では,多項式時間における双対化問題の決定バージョンを解く量子計算アルゴリズムを提案する。
関連論文リスト
- Dimension Independent Disentanglers from Unentanglement and Applications [55.86191108738564]
両部非絡み込み入力から次元独立なk-パーティイトディジアンタングル(類似)チャネルを構築する。
NEXP を捉えるためには、$| psi rangle = sqrta | sqrt1-a | psi_+ rangle という形の非負の振幅を持つのに十分であることを示す。
論文 参考訳(メタデータ) (2024-02-23T12:22:03Z) - Quantum and classical query complexities of functions of matrices [0.0]
任意の連続関数 $f(x):[-1,1]rightarrow [-1,1]$ に対して、計算の量子クエリ複雑性 $brai f(A) ketjpm varepsilon/4$ は$Omega(widetildedeg_varepsilon(f))$ で制限される。
論文 参考訳(メタデータ) (2023-11-13T00:45:41Z) - The SUSY partners of the QES sextic potential revisited [0.0]
準可解(QES)性ポテンシャル $Vrm qes(x) = nu, x6 + 2, nu, mu,x4 + left[mu2-(4N+3)nu right], x2$, $N in mathbbZ+$。
論文 参考訳(メタデータ) (2023-11-10T18:38:02Z) - Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix
Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。
目標は、低ランク因子の積として$mathbfA$を近似することである。
我々の手法はBMF問題の他の一般的な変種に一般化する。
論文 参考訳(メタデータ) (2023-06-02T18:55:27Z) - The Approximate Degree of DNF and CNF Formulas [95.94432031144716]
すべての$delta>0に対して、$はCNFと近似次数$Omega(n1-delta)の式を構築し、基本的には$nの自明な上限に一致する。
すべての$delta>0$に対して、これらのモデルは$Omega(n1-delta)$、$Omega(n/4kk2)1-delta$、$Omega(n/4kk2)1-delta$が必要です。
論文 参考訳(メタデータ) (2022-09-04T10:01:39Z) - Low-degree learning and the metric entropy of polynomials [49.1574468325115]
少なくとも$Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon)は2辺の推定値$c(1-varepsilon)2dlogを満たす。
論文 参考訳(メタデータ) (2022-03-17T23:52:08Z) - An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
論文 参考訳(メタデータ) (2020-08-24T06:50:57Z) - Learning sums of powers of low-degree polynomials in the non-degenerate
case [2.6109033135086777]
我々は、ある非退化条件が成立すれば、同じモデルに対する下界から算術回路モデルの学習アルゴリズムを与える。
本アルゴリズムは,同じモデルに対する下界から算術回路モデルの学習アルゴリズムを得るためのスキームに基づいている。
論文 参考訳(メタデータ) (2020-04-15T06:18:41Z) - Fast digital methods for adiabatic state preparation [0.0]
ゲート型量子コンピュータにおいて,逆誤差の複雑多元対数を伴う断熱状態生成のための量子アルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-04-08T18:00:01Z) - Quantum algorithms for the Goldreich-Levin learning problem [3.8849433921565284]
Goldreich-Levinアルゴリズムは元々暗号目的のために提案され、その後学習に適用された。
ウォルシュ係数を持つベクトルを$w$で出力するには$poly(n,frac1epsilonlogfrac1delta)$時間を要する。
本稿では,この問題に対する量子アルゴリズムをクエリ複雑性$O(fraclogfrac1deltaepsilon4)$で与えられる。
論文 参考訳(メタデータ) (2019-12-31T14:52:36Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。