Given a Boolean function $f$ provided as a black-box with $n$ variables, this paper will propose a quantum algorithm for testing if a certain variable is junta or $ε$ -far from being junta. The proposed algorithm constructs another black-box using two copies of the provided black-box. The constructed black-box is used with the partial diffusion operator in an amplitude amplification technique to test whether the variable being tested is junta or not, using $\mathcal{O}(\sqrt{2^n})$ queries to the constructed black-box. The proposed algorithm considers a Boolean function of general form, contrary to relevant algorithms proposed by others.Given a Boolean function $f$ provided as a black-box with $n$ variables, this paper will propose a quantum algorithm for testing if a certain variable is junta or $ε$-far from being junta. The proposed algorithm constructs another black-box using two copies of the provided black-box. The constructed black-box is used with the partial diffusion operator in an amplitude amplification technique to test whether the variable being tested is junta or not, using $\mathcal{O}(\sqrt{2^n})$ queries to the constructed black-box. The proposed algorithm considers a Boolean function of general form, contrary to relevant algorithms proposed by others.

arXiv:1701.02143Jan 9, 20176 citations

Quantum Complexity of Boolean Matrix Multiplication and Related Problems

François Le Gall

Lecture notes in computer scienceJan 1, 20141 citation

High precision quantum query algorithm for computing AND-based boolean functions

Alina Vasilieva, Taisia Mischenko-Slatenkova

Quantum algorithms can be analyzed in a query model to compute Boolean functions. Function input is provided in a black box, and the aim is to compute the function value using as few queries to the black box as possible. The complexity of the algorithm is measured by the number of queries on the worst-case input. In this paper we consider computing AND Boolean function. First, we present a quantum algorithm for AND of two bits. Our algorithm uses one quantum query and correct result is obtained with a probability p=4/5, that improves previous results. The main result is generalization of our approach to design efficient quantum algorithms for computing composite function AND(f1,f2) where fi is a Boolean function. Finally, we demonstrate another kind of an algorithm for AND of two variables, that has a correct answer probability p=9/10, but cannot be extended to compute AND(f1,f2).Quantum algorithms can be analyzed in a query model to compute Boolean functions. Function input is provided in a black box, and the aim is to compute the function value using as few queries to the black box as possible. The complexity of the algorithm is measured by the number of queries on the worst-case input. In this paper we consider computing AND Boolean function. First, we present a quantum algorithm for AND of two bits. Our algorithm uses one quantum query and correct result is obtained with a probability p=4/5, that improves previous results. The main result is generalization of our approach to design efficient quantum algorithms for computing composite function AND(f1,f2) where fi is a Boolean function. Finally, we demonstrate another kind of an algorithm for AND of two variables, that has a correct answer probability p=9/10, but cannot be extended to compute AND(f1,f2).

ACM International Conference on Computing Frontiers (CF)May 17, 20100 citations

Quantum Query Complexity of Boolean Functions with Small On-Sets

Andris Ambainis, Kazuo Iwama, Masaki Nakanishi +4 more

Lecture notes in computer scienceJan 1, 20089 citations

Quantum Lower Bounds by Polynomials

Robert Beals, Harry Buhrman, Richard Cleve +2 more

We examine the number T of queries that a quantum network requires to compute several Boolean functions on {0,1}^N in the black-box model. We show that, in the black-box model, the exponential quantum speed-up obtained for partial functions (i.e. problems involving a promise on the input) by Deutsch and Jozsa and by Simon cannot be obtained for any total function: if a quantum algorithm computes some total Boolean function f with bounded-error using T black-box queries then there is a classical deterministic algorithm that computes f exactly with O(T^6) queries. We also give asymptotically tight characterizations of T for all symmetric f in the exact, zero-error, and bounded-error settings. Finally, we give new precise bounds for AND, OR, and PARITY. Our results are a quantum extension of the so-called polynomial method, which has been successfully applied in classical complexity theory, and also a quantum extension of results by Nisan about a polynomial relationship between randomized and deterministic decision tree complexity.We examine the number T of queries that a quantum network requires to compute several Boolean functions on {0,1}^N in the black-box model. We show that, in the black-box model, the exponential quantum speed-up obtained for partial functions (i.e. problems involving a promise on the input) by Deutsch and Jozsa and by Simon cannot be obtained for any total function: if a quantum algorithm computes some total Boolean function f with bounded-error using T black-box queries then there is a classical deterministic algorithm that computes f exactly with O(T^6) queries. We also give asymptotically tight characterizations of T for all symmetric f in the exact, zero-error, and bounded-error settings. Finally, we give new precise bounds for AND, OR, and PARITY. Our results are a quantum extension of the so-called polynomial method, which has been successfully applied in classical complexity theory, and also a quantum extension of results by Nisan about a polynomial relationship between randomized and deterministic decision tree complexity.

arXiv:quant-ph/9802049Feb 18, 1998164 citations

Given a Boolean function

f

provided as a black-box with

n

variables, this paper will propose a quantum algorithm for testing if a certain variable is junta or

ε

-far from being junta. The proposed algorithm constructs another black-box using two copies of the provided black-box. The constructed black-box is used with the partial diffusion operator in an amplitude amplification technique to test whether the variable being tested is junta or not, using

\mathcal{O}(\sqrt{2^n})

queries to the constructed black-box. The proposed algorithm considers a Boolean function of general form, contrary to relevant algorithms proposed by others.