  We study how the choices made when designing an oracle affect the complexity
of quantum property testing problems defined relative to this oracle. We encode
a regular graph of even degree as an invertible function $f$, and present $f$
in different oracle models. We first give a one-query QMA protocol to test if a
graph encoded in $f$ has a small disconnected subset. We then use
representation theory to show that no classical witness can help a quantum
verifier efficiently decide this problem relative to an in-place oracle.
Perhaps surprisingly, a simple modification to the standard oracle prevents a
quantum verifier from efficiently deciding this problem, even with access to an
unbounded witness.
