ECCC-Report TR08-085https://eccc.weizmann.ac.il/report/2008/085Comments and Revisions published for TR08-085en-usMon, 25 Jan 2010 13:05:16 +0200
Revision 1
| On Complexity of Quantum Branching Programs Computing Equality-like Boolean Functions |
Farid Ablayev,
Airat Khasianov,
Alexander Vasiliev
https://eccc.weizmann.ac.il/report/2008/085#revision1We consider the Hidden Subgroup, and Equality-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 in circuit notation. Our algorithms
require at most logarithmic number of qubits.Mon, 25 Jan 2010 13:05:16 +0200https://eccc.weizmann.ac.il/report/2008/085#revision1
Paper TR08-085
| On Complexity of Quantum Branching Programs Computing Equality-like Boolean Functions |
Farid Ablayev,
Airat Khasianov,
Alexander Vasiliev
https://eccc.weizmann.ac.il/report/2008/085We 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 in circuit notation. Our algorithms require at most
logarithmic number of qubits.
Wed, 17 Sep 2008 18:02:40 +0300https://eccc.weizmann.ac.il/report/2008/085