6533b7defe1ef96bd1275bed
RESEARCH PRODUCT
Quantum Query Algorithms for Conjunctions
Alina VasilievaTaisia Mischenko-slatenkovasubject
Product termTheoretical computer scienceParity functionAnd-inverter graphMaximum satisfiability problemQuantum phase estimation algorithmBoolean expressionQuantum algorithmBoolean functionAlgorithmMathematicsdescription
Every Boolean function can be presented as a logical formula in conjunctive normal form. Fast algorithm for conjunction plays significant role in overall algorithm for computing arbitrary Boolean function. First, we present a quantum query algorithm for conjunction of two bits. Our algorithm uses one quantum query and correct result is obtained with a probability p = 4/5, that improves the previous result. Then, we present the main result - generalization of our approach to design efficient quantum algorithms for computing conjunction of two Boolean functions. Finally, we demonstrate another kind of an algorithm for conjunction of two bits, that has a correct answer probability p = 9/10. This algorithm improves success probability by 10%, but stands aside and cannot be extended to compute conjunction of Boolean functions.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2010-01-01 |