Quantum vs. Classical Read-Once Branching Programs

Author Martin Sauerhoff



PDF
Thumbnail PDF

File

DagSemProc.06111.15.pdf
  • Filesize: 257 kB
  • 13 pages

Document Identifiers

Author Details

Martin Sauerhoff

Cite AsGet 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)}.
Keywords
  • Quantum branching program
  • randomized branching program
  • read-once

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail