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/

[1] Shor P. W., “Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer”, SIAM J. Comput., 26 (1997), 1484–1509 | DOI | MR | Zbl

[2] Wegener I., Branching programs and binary decision diagrams, SIAM Press, Philadelphia, 2000 | MR | Zbl

[3] Nakanishi M., Hamaguchi K., Kashiwabara T., “Ordered quantum branching programs are more powerful than ordered probabilistic branching programs under a bounded-width restriction”, Lect. Notes Comput. Sci., 1858, 2000, 467–476 | MR | Zbl

[4] Barrington D. A., “Bounded-width polynomial-size branching programs recognize exactly those languages in $NC^1$”, J. Comput. Syst. Sci., 38 (1989), 150–164 | DOI | MR | Zbl

[5] Sauerhoff M., Sieling D., “Quantum branching programs and space-bounded nonuniform quantum complexity”, Theor. Comput. Sci., 334 (2005), 177–225 | DOI | MR | Zbl

[6] Ablayev F., Gainutdinova A., Karpinski M., “On computational power of quantum branching programs”, Lect. Notes Comput. Sci., 2138, 2001, 59–70 | MR | Zbl

[7] Ablayev F., Gainutdinova A., Karpinski M., Moore C., Pollette C., “On the computational power of probabilistic and quantum branching programs of constant width”, Inf. Comput., 203 (2005), 145–162 | DOI | MR | Zbl

[8] Freivalds R., “Fast probabilistic algorithms”, Lect. Notes Comput. Sci., 74, 1979, 57–69 | MR | Zbl

[9] Motwani R., Raghavan P., Randomized algorithms, Cambridge University Press, Cambridge, 1995 | MR | Zbl

[10] Buhrman H., Cleve R., Watrous J., Wolf R., “Quantum fingerprinting”, Phys. Rev. Lett., 87:16 (2001), 167902 | DOI

[11] Ambainis A., Freivalds R., “1-way quantum finite automata: strengths, weaknesses and generalization”, Proc. 39th FOCS, IEEE Computer Society, 1998, 332–342

[12] Ambainis A., Nahimovs N., “Improved constructions of quantum automata”, Lect. Notes Comput. Sci., 5106, 2008, 47–56 | MR | Zbl

[13] Ablaev F. M., Vasilev A. V., “O vychisleniyakh v kvantovykh vetvyaschikhsya programmakh metodom kharakternykh priznakov”, Tez. dokl. XV Mezhdunarodnoi konf. “Problemy teoreticheskoi kibernetiki”, Kazan, 2008, 1 (Russian)

[14] Moore C., Crutchfield J. P., “Quantum automata and quantum grammars”, Theor. Comput. Sci., 237 (2000), 275–306 | DOI | MR | Zbl

[15] Nielsen M. A., Chuang I. L., Quantum computation and quantum information, Cambridge University Press, Cambridge, 2000 | MR

[16] Yao A., “Some complexity questions related to distributive computing”, Proc. 11th STOC, 1979, 209–213