  We explore the space "just above" BQP by defining a complexity class PDQP
(Product Dynamical Quantum Polynomial time) which is larger than BQP but does
not contain NP relative to an oracle. The class is defined by imagining that
quantum computers can perform measurements that do not collapse the
wavefunction. This (non-physical) model of computation can efficiently solve
problems such as Graph Isomorphism and Approximate Shortest Vector which are
believed to be intractable for quantum computers. Furthermore, it can search an
unstructured N-element list in $\tilde O$(N^{1/3}) time, but no faster than
{\Omega}(N^{1/4}), and hence cannot solve NP-hard problems in a black box
manner. In short, this model of computation is more powerful than standard
quantum computation, but only slightly so.
  Our work is inspired by previous work of Aaronson on the power of sampling
the histories of hidden variables. However Aaronson's work contains an error in
its proof of the lower bound for search, and hence it is unclear whether or not
his model allows for search in logarithmic time. Our work can be viewed as a
conceptual simplification of Aaronson's approach, with a provable polynomial
lower bound for search.
