Quantum models of computation are widely believed to be more powerful than
classical ones. Efforts center on proving that, for a given problem, quantum
algorithms are more resource efficient than any classical one. All this,
however, assumes a standard predictive paradigm of reasoning where, given
initial conditions, the future holds the answer. How about bringing information
from the future to the present and exploit it to one's advantage? This is a
radical new approach for reasoning, so-called Retrodictive Computation, that
benefits from the specific form of the computed functions. We demonstrate how
to use tools of symbolic computation to realize retrodictive quantum computing
at scale and exploit it to efficiently, and classically, solve instances of the
quantum Deutsch-Jozsa, Bernstein-Vazirani, Simon, Grover, and Shor's
algorithms.
