اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدExact quantum algorithms have advantage for almost all Boolean functions
148
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
It has been proved that almost all $n$-bit Boolean functions have exact classical query complexity $n$. However, the situation seemed to be very different when we deal with exact quantum query complexity. In this paper, we prove that almost all $n$-bit Boolean functions can be computed by an exact quantum algorithm with less than $n$ queries. More exactly, we prove that ${AND}_n$ is the only $n$-bit Boolean function, up to isomorphism, that requires $n$ queries.
قيم البحث
اقرأ أيضاً
We show that almost all n-bit Boolean functions have bounded-error quantum query complexity at least n/2, up to lower-order terms. This improves over an earlier n/4 lower bound of Ambainis, and shows that van Dams oracle interrogation is essentially
optimal for almost all functions. Our proof uses the fact that the acceptance probability of a T-query algorithm can be written as the sum of squares of degree-T polynomials.
We provide two sufficient and necessary conditions to characterize any $n$-bit partial Boolean function with exact quantum 1-query complexity. Using the first characterization, we present all $n$-bit partial Boolean functions that depend on $n$ bits
and have exact quantum 1-query complexity. Due to the second characterization, we construct a function $F$ that maps any $n$-bit partial Boolean function to some integer, and if an $n$-bit partial Boolean function $f$ depends on $k$ bits and has exact quantum 1-query complexity, then $F(f)$ is non-positive. In addition, we show that the number of all $n$-bit partial Boolean functions that depend on $k$ bits and have exact quantum 1-query complexity is not bigger than $n^{2}2^{2^{n-1}(1+2^{2-k})+2n^{2}}$ for all $ngeq 3$ and $kgeq 2$.
Boolean functions can be represented in many ways including logical forms, truth tables, and polynomials. Additionally, Boolean functions have different canonical representations such as minimal disjunctive normal forms. Other canonical representatio
n is based on the polynomial representation of Boolean functions where they can be written as a nested product of canalizing layers and a polynomial that contains the noncanalizing variables. In this paper we study the problem of identifying the canalizing layers format of Boolean functions. First, we show that the problem of finding the canalizing layers is NP-hard. Second, we present several algorithms for finding the canalizing layers of a Boolean function, discuss their complexities, and compare their performances. Third, we show applications where the computation of canalizing layers can be used for finding a disjunctive normal form of a nested canalizing function. Another application deals with the reverse engineering of Boolean networks with a prescribed layering format. Finally, implementations of our algorithms in Python and in the computer algebra system Macaulay2 are available at https://github.com/ckadelka/BooleanCanalization.
Quantum discord quantifies non-classical correlations in a quantum system including those not captured by entanglement. Thus, only states with zero discord exhibit strictly classical correlations. We prove that these states are negligible in the whol
e Hilbert space: typically a state picked out at random has positive discord; and, given a state with zero discord, a generic arbitrarily small perturbation drives it to a positive-discord state. These results hold for any Hilbert-space dimension, and have direct implications on quantum computation and on the foundations of the theory of open systems. In addition, we provide a simple necessary criterion for zero quantum discord. Finally, we show that, for almost all positive-discord states, an arbitrary Markovian evolution cannot lead to a sudden, permanent vanishing of discord.
We present a number of results related to quantum algorithms with small error probability and quantum algorithms that are zero-error. First, we give a tight analysis of the trade-offs between the number of queries of quantum search algorithms, their
error probability, the size of the search space, and the number of solutions in this space. Using this, we deduce new lower and upper bounds for quant
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
