DagSemProc.06111.15.pdf
- Filesize: 257 kB
- 13 pages
Document
Quantum vs. Classical Read-Once Branching Programs
Author
-
Part of:
Volume:
Dagstuhl Seminar Proceedings, Volume 6111
Series: Dagstuhl Seminar Proceedings (DagSemProc) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2006-11-20
Cite As Get BibTex
Martin Sauerhoff. Quantum vs. Classical Read-Once Branching Programs. In Complexity of Boolean Functions. Dagstuhl Seminar Proceedings, Volume 6111, pp. 1-13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)
https://doi.org/10.4230/DagSemProc.06111.15
Abstract
A simple, explicit boolean function on 2n input bits is presented that is
computable by errorfree quantum read-once branching programs of size
O(n^3), while each classical randomized read-once branching program
and each quantum OBDD for this function with bounded two-sided error
requires size 2^{omega(n)}.
Subject Classification
Keywords
- Quantum branching program
- randomized branching program
- read-once
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads