2022/01/26 by Sauerhoff, Martin
#Quantum branching program #randomized branching program #read-once
paper · doi:10.4230/dagsemproc.06111.15
A simple, explicit boolean function on 2n input bits is presented that is computable by errorfree quantum read-once branching programs of size O(n3), while each classical randomized read-once branching program and each quantum OBDD for this function with bounded two-sided error requires size 2omega(n).