  A foundational question in quantum computational complexity asks how much
more useful a quantum state can be in a given task than a comparable, classical
string. Aaronson and Kuperberg showed such a separation in the presence of a
quantum oracle, a black box unitary callable during quantum computation. Their
quantum oracle responds to a random, marked, quantum state, which is
intractable to specify classically. We constrain the marked state in ways that
make it easy to specify classically while retaining separations in task
complexity. Our method replaces query by state complexity. Furthermore,
assuming a widely believed separation between the difficulty of creating a
random, complex state and creating a specified state, we propose an
experimental demonstration of quantum witness advantage on near-term,
distributed quantum computers. Finally, using the fact that a standard,
classically defined oracle may enable a quantum algorithm to prepare an
otherwise hard state in polynomial steps, we observe quantum-classical oracle
separation in heavy output sampling.
