Geodesic
On quantum realisation of Boolean functions by the fingerprinting technique
Diskretnaya Matematika, Tome 21 (2009) no. 4, pp. 3-19

Voir la notice de l'article provenant de la source Math-Net.Ru

In this paper, we develop the fingerprinting technique of calculation of Boolean functions in quantum calculation models. The use of the fingerprinting technique is demonstrated on the example of calculation of the function $\mathrm{MOD}_m$ in the class of quantum OBDD (oblivious read-once branching programs). Next, the potentialities of the fingerprinting technique are demonstrated in the example of realisation of the “equality” function in the quantum model of communication with a referee (the SMP communication model) and in examples of recognition of languages in quantum automata. All given realisations of Boolean functions in various quantum calculation models (OBDD, SMP communication model, and a finite automaton) are asymptotically optimal. The authors thank Juhani Karhumäki for the invitation to the University of Turku and fruitful discussions of this research. 
@article{DM_2009_21_4_a0,
     author = {F. M. Ablayev and A. V. Vasilyev},
     title = {On quantum realisation of {Boolean} functions by the fingerprinting technique},
     journal = {Diskretnaya Matematika},
     pages = {3--19},
     publisher = {mathdoc},
     volume = {21},
     number = {4},
     year = {2009},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2009_21_4_a0/}
}
TY  - JOUR
AU  - F. M. Ablayev
AU  - A. V. Vasilyev
TI  - On quantum realisation of Boolean functions by the fingerprinting technique
JO  - Diskretnaya Matematika
PY  - 2009
SP  - 3
EP  - 19
VL  - 21
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2009_21_4_a0/
LA  - ru
ID  - DM_2009_21_4_a0
ER  - 
%0 Journal Article
%A F. M. Ablayev
%A A. V. Vasilyev
%T On quantum realisation of Boolean functions by the fingerprinting technique
%J Diskretnaya Matematika
%D 2009
%P 3-19
%V 21
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2009_21_4_a0/
%G ru
%F DM_2009_21_4_a0
F. M. Ablayev; A. V. Vasilyev. On quantum realisation of Boolean functions by the fingerprinting technique. Diskretnaya Matematika, Tome 21 (2009) no. 4, pp. 3-19. http://geodesic.mathdoc.fr/item/DM_2009_21_4_a0/