اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدRepresentation of Boolean functions in terms of quantum computation
97
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
The relationship between quantum physics and discrete mathematics is reviewed in this article. The Boolean functions unitary representation is considered. The relationship between Zhegalkin polynomial, which defines the algebraic normal form of Boolean function, and quantum logic circuits is described. It is shown that quantum information approach provides simple algorithm to construct Zhegalkin polynomial using truth table. Developed methods and algorithms have arbitrary Boolean function generalization with multibit input and multibit output. Such generalization allows us to use many-valued logic (k-valued logic, where k is a prime number). Developed methods and algorithms can significantly improve quantum technology realization. The presented approach is the baseline for transition from classical machine logic to quantum hardware.
قيم البحث
اقرأ أيضاً
The goal in the area of functions property testing is to determine whether a given black-box Boolean function has a particular given property or is $varepsilon$-far from having that property. We investigate here several types of properties testing fo
r Boolean functions (identity, correlations and balancedness) using the Deutsch-Jozsa algorithm (for the Deutsch-Jozsa (D-J) problem) and also the amplitude amplification technique. At first, we study here a particular testing problem: namely whether a given Boolean function $f$, of $n$ variables, is identical with a given function $g$ or is $varepsilon$-far from $g$, where $varepsilon$ is the parameter. We present a one-sided error quantum algorithm to deal with this problem that has the query complexity $O(frac{1}{sqrt{varepsilon}})$. Moreover, we show that our quantum algorithm is optimal. Afterwards we show that the classical randomized query complexity of this problem is $Theta(frac{1}{varepsilon})$. Secondly, we consider the D-J problem from the perspective of functional correlations and let $C(f,g)$ denote the correlation of $f$ and $g$. We propose an exact quantum algorithm for making distinction between $|C(f,g)|=varepsilon$ and $|C(f,g)|=1$ using six queries, while the classical deterministic query complexity for this problem is $Theta(2^{n})$ queries. Finally, we propose a one-sided error quantum query algorithm for testing whether one Boolean function is balanced versus $varepsilon$-far balanced using $O(frac{1}{varepsilon})$ queries. We also prove here that our quantum algorithm for balancedness testing is optimal. At the same time, for this balancedness testing problem we present a classical randomized algorithm with query complexity of $O(1/varepsilon^{2})$. Also this randomized algorithm is optimal. Besides, we link the problems considered here together and generalize them to the general case.
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 prove that quantum-hard one-way functions imply simulation-secure quantum oblivious transfer (QOT), which is known to suffice for secure computation of arbitrary quantum functionalities. Furthermore, our construction only makes black-box use of th
e quantum-hard one-way function. Our primary technical contribution is a construction of extractable and equivocal quantum bit commitments based on the black-box use of quantum-hard one-way functions in the standard model. Instantiating the Crepeau-Kilian (FOCS 1988) framework with these commitments yields simulation-secure QOT.
We study the efficiency of quantum algorithms which aim at obtaining phase space distribution functions of quantum systems. Wigner and Husimi functions are considered. Different quantum algorithms are envisioned to build these functions, and compared
with the classical computation. Different procedures to extract more efficiently information from the final wave function of these algorithms are studied, including coarse-grained measurements, amplitude amplification and measure of wavelet-transformed wave function. The algorithms are analyzed and numerically tested on a complex quantum system showing different behavior depending on parameters, namely the kicked rotator. The results for the Wigner function show in particular that the use of the quantum wavelet transform gives a polynomial gain over classical computation. For the Husimi distribution, the gain is much larger than for the Wigner function, and is bigger with the help of amplitude amplification and wavelet transforms. We also apply the same set of techniques to the analysis of real images. The results show that the use of the quantum wavelet transform allows to lower dramatically the number of measurements needed, but at the cost of a large loss of information.
We study the volatility of the output of a Boolean function when the input bits undergo a natural dynamics. For $n = 1,2,ldots$, let $f_n:{0,1}^{m_n} ra {0,1}$ be a Boolean function and $X^{(n)}(t)=(X_1(t),ldots,X_{m_n}(t))_{t in [0,infty)}$ be a vec
tor of i.i.d. stationary continuous time Markov chains on ${0,1}$ that jump from $0$ to $1$ with rate $p_n in [0,1]$ and from $1$ to $0$ with rate $q_n=1-p_n$. Our object of study will be $C_n$ which is the number of state changes of $f_n(X^{(n)}(t))$ as a function of $t$ during $[0,1]$. We say that the family ${f_n}_{nge 1}$ is volatile if $C_n ra iy$ in distribution as $ntoinfty$ and say that ${f_n}_{nge 1}$ is tame if ${C_n}_{nge 1}$ is tight. We study these concepts in and of themselves as well as investigate their relationship with the recent notions of noise sensitivity and noise stability. In addition, we study the question of lameness which means that $Pro(C_n =0)ra 1$ as $ntoinfty$. Finally, we investigate these properties for a number of standard Boolean functions such as the majority function, iterated 3-majority, the AND/OR function on the binary tree and percolation on certain trees at various levels of the parameter $p_n$.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
