6533b82dfe1ef96bd1291bd7
RESEARCH PRODUCT
High precision quantum query algorithm for computing AND-based boolean functions
Alina VasilievaTaisia Mischenko-slatenkovasubject
Theoretical computer scienceBoolean networkComputer scienceParity functionBoolean circuitQuantum phase estimation algorithmBoolean expressionQuantum algorithmBoolean functionAlgorithmQuantum computerdescription
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).
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2010-05-17 | Proceedings of the 7th ACM international conference on Computing frontiers |