Abstract
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 MODm 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.
© de Gruyter 2009
