Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR08-059 | 28th October 2010 18:13

On the Computation of Boolean Functions by Quantum Branching Programs via Fingerprinting

RSS-Feed




Revision #1
Authors: Farid Ablayev, Alexander Vasiliev
Accepted on: 28th October 2010 18:13
Downloads: 3655
Keywords: 


Abstract:

We develop quantum fingerprinting technique for constructing quantum
branching programs (QBPs), which are considered as circuits with an
ability to use classical bits as control variables.

We demonstrate our approach constructing optimal quantum ordered
binary decision diagram (QOBDD) for $MOD_m$ and $DMULT_n$ Boolean
functions. The construction of our technique also allows to extend
the recent result of Ambainis and Nahimovs it is based on. In
addition we show how our technique works for encoding quantum
information for the equality problem in the simultaneous message
passing model.



Changes to previous version:

Removed the erroneous algorithm fo DMULT function.


Paper:

TR08-059 | 20th May 2008 00:00

On the Computation of Boolean Functions by Quantum Branching Programs via Fingerprinting





TR08-059
Authors: Farid Ablayev, Alexander Vasiliev
Publication: 4th June 2008 17:39
Downloads: 2995
Keywords: 


Abstract:

We develop quantum fingerprinting technique for constructing quantum
branching programs (QBPs), which are considered as circuits with an
ability to use classical bits as control variables.

We demonstrate our approach constructing optimal quantum ordered
binary decision diagram (QOBDD) for $MOD_m$ and $DMULT_n$ Boolean
functions. The construction of our technique also allows to extend
the recent result of Ambainis and Nahimovs it is based on. In
addition we show how our technique works for encoding quantum
information for the equality problem in the simultaneous message
passing model.



ISSN 1433-8092 | Imprint