  The oracle model of computation is believed to allow a rigorous proof of
quantum over classical computational superiority. Since quantum and classical
oracles are essentially different, a correspondence principle is commonly
implicitly used as a platform for comparison of oracle complexity. Here, we
question the grounds on which this correspondence is based. Obviously, results
on quantum speed-up depend on the chosen correspondence. So, we introduce the
notion of genuine quantum speed-up which can serve as a tool for reliable
comparison of quantum vs classical complexity, independently of the chosen
correspondence principle.
