論文の概要: 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$? 本稿では,多項式時間における双対化問題の決定バージョンを解く量子計算アルゴリズムを提案する。

関連論文リスト

• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。 アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
  論文  参考訳（メタデータ） (2024-10-26T06:21:42Z)
• Partially Unitary Learning [0.0]
  ヒルベルト空間の最適写像 $IN$ of $left|psirightrangle$ と $OUT$ of $left|phirightrangle$ が提示される。 この最適化問題の大域的な最大値を求める反復アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2024-05-16T17:13:55Z)
• 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)
• 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)
• 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)
• Fast digital methods for adiabatic state preparation [0.0]
  ゲート型量子コンピュータにおいて,逆誤差の複雑多元対数を伴う断熱状態生成のための量子アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-04-08T18:00:01Z)
• Tight Quantum Lower Bound for Approximate Counting with Quantum States [49.6558487240078]
  Aaronson, Kothari, Kretschmer, Thaler (2020) が考える数え上げ問題の次の変種に対する厳密な下界を証明する。 このタスクは、入力セット$xsubseteq [n]$が$k$か$k'=(1+varepsilon)k$であるかどうかを識別する。
  論文  参考訳（メタデータ） (2020-02-17T10:53:50Z)
• Quantum algorithms for the Goldreich-Levin learning problem [3.8849433921565284]
  Goldreich-Levinアルゴリズムは元々暗号目的のために提案され、その後学習に適用された。 ウォルシュ係数を持つベクトルを$w$で出力するには$poly(n,frac1epsilonlogfrac1delta)$時間を要する。 本稿では,この問題に対する量子アルゴリズムをクエリ複雑性$O(fraclogfrac1deltaepsilon4)$で与えられる。
  論文  参考訳（メタデータ） (2019-12-31T14:52:36Z)

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

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。