Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with quantum branching programs:
TR08-059 | 20th May 2008
Farid Ablayev, Alexander Vasiliev

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

Revisions: 1

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 ... more >>>

TR08-085 | 19th June 2008
Farid Ablayev, Airat Khasianov, Alexander Vasiliev

On Complexity of Quantum Branching Programs Computing Equality-like Boolean Functions

Revisions: 1

We consider Generalized Equality, the Hidden Subgroup,
and related problems in the context of quantum Ordered Binary
Decision Diagrams. For the decision versions of considered problems
we show polynomial upper bounds in terms of quantum OBDD width. We
apply a new modification of the fingerprinting technique and present
the algorithms ... more >>>

ISSN 1433-8092 | Imprint