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.
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.
Bernstein-Vazirani algorithm (the one-query algorithm) can identify a completely specified linear Boolean function using a single query to the oracle with certainty. The first aim of the paper is to show that if the provided Boolean function is affine, then one more query to the oracle (the two-query algorithm) is required to identify the affinity of the function with certainty. The second aim of the paper is to show that if the provided Boolean function is incompletely defined, then the one-query and the two-query algorithms can be used as bounded-error quantum polynomial algorithms to identify certain classes of incompletely defined linear and affine Boolean functions respectively with probability of success at least 2/3.
We discuss quantum algorithms, based on the Bernstein-Vazirani algorithm, for finding which variables a Boolean function depends on. There are 2^n possible linear Boolean functions of n variables; given a linear Boolean function, the Bernstein-Vazirani quantum algorithm can deterministically identify which one of these Boolean functions we are given using just one single function query. The same quantum algorithm can also be used to learn which input variables other types of Boolean functions depend on, with a success probability that depends on the form of the Boolean function that is tested, but does not depend on the total number of input variables. We also outline a procedure to futher amplify the success probability, based on another quantum algorithm, the Grover search.
Let X = (z,, , z,-,) be a sequence of n numbers.For 6 > 0, we say that 5; is an e-approximate median if the number of elements strictly less than zi and the number of elements strictly greater than zi are each less than (1 + 6):.We consider the quantum query complexity of computing an c-approximate median, given the sequence X as an oracle.We prove a lower bound of n(min{t,n}) queries for any quantum algorithm that computes an r-approximate median with any constant probability greater than l/2.We also show how an c-approximate median may be computed with 0( $ log(t) log log( $)) oracle queries, which rep resents an improvement over an earlier algorithm due to Grover [ll, 121.Thus, the lower bound we obtain is essentially optimal.The upper and the lower bound both hold in the comparison tree model as well.Our lower bound result is an application of the polynomial paradigm recently introduced to quantum complexity theory by Be& et ol.[l].The main ingredient in the proof is a polynomial degree lower bound far real multilinear polynomials that "approximate" symmetric partial boolean functions.The degree bound extends a result of Patti[15] and also immediately yields lower bounds for the problems of approximating the kth-smallest element, approximating the mean of a sequence of numbers, and approximately counting the number of ones of a boolean function.All bounds obtained come within a polylogarithmic factor of the optimal (as we show by presenting algorithms where no such optimal or near optimal algorithms were known), thus demonstrating the power of the polynomial method.
Quantum oracle of Boolean functions is one of the central bridges between classical and quantum algorithms, but the study focusing at quantum circuit optimization of such oracle is yet closed. In this paper, we propose nearly optimal tradeoffs among circuit size, circuit depth and ancilla count, for quantum oracles of three kinds of Boolean functions:
general total Boolean functions with output size b: with 1≤m≤Θ(n2n) ancilla, size O(log(n+m)b2n), depth O(n+mb2n);
partial Boolean functions of effective support size d and output size b: with Θ(logd)≤m≤Θ(d) ancilla, size O(nlogd+bd), depth O(n+mnlognlogd+logn+md(logd+blogm));
sparse Boolean functions of true input size d: with Θ(logn+logd)≤m≤Θ(logdnd) ancilla, size O(n2logd+log(logd+m/n)nd), depth O(n+mn2lognlogd+logn+mnd).
All the size and depth bounds are asymptotically optimal up to logarithmic factors in the corresponding ancilla count regions. We hope these results find applications in scenarios where classical procedures are needed to be embedded into quantum circuits, such as QROM implementation and quantum algorithm design.
We discuss quantum algorithms based on the Bernstein–Vazirani algorithm for finding which input variables a Boolean function depends on. There are 2 n possible linear Boolean functions of n input variables; given a linear Boolean function, the Bernstein–Vazirani quantum algorithm can deterministically identify which one of these Boolean functions we are given using just one single function query. We show how the same quantum algorithm can also be used to learn which input variables any other type of Boolean function} depends on. The success probability of learning that the function depends on a particular input variable depends on} the form of the Boolean function that is tested, but does not depend on the total number of input variables. We also outline a procedure based on another quantum algorithm, the Grover search, to amplify further the success probability. Finally, we discuss quantum algorithms for learning the exact form of certain quadratic and cubic Boolean functions.
Our problem is to evaluate a multi-valued Boolean function F through oracle calls. If F is one-to-one and the size of its domain and range is the same, then our problem can be formulated as follows: Given an oracle f(a,x):{0,1}n×{0,1}n→{0,1} and a fixed (but hidden) value a0, we wish to obtain the value of a0 by querying the oracle f(a0,x). Our goal is to minimize the number of such oracle calls (the query complexity) using a quantum mechanism. Two popular oracles are the EQ-oracle defined as f(a,x)=1 iff x=a and the IP-oracle defined as f(a,x)=a⋅xmod2. It is also well-known that the query complexity is Θ(N) (N=2n) for the EQ-oracle while only O(1) for the IP-oracle. The main purpose of this paper is to fill this gap or to investigate what causes this large difference. To do so, we introduce a parameter K as the maximum number of 1's in a single column of Tf where Tf is the N×N truth-table of the oracle f(a,x). Our main result shows that the (quantum) query complexity is heavily governed by this parameter K: (i) The query complexity is Ω(N/K). (ii) This lower bound is tight in the sense that we can construct an explicit oracle whose query complexity is O(N/K). (iii) The tight complexity, Θ(KN+logK), is also obtained for the classical case. Thus, the quantum algorithm needs a quadratically less number of oracle calls when K is small and this merit becomes larger when K is large, e.g., logK v.s. constant when K=cN.