  Computational devices may be supplied with external sources of information
(oracles). Quantum oracles may transmit phase information which is available to
a quantum computer but not a classical computer. One consequence of this
observation is that there is an oracle which is of no assistance to a classical
computer but which allows a quantum computer to solve undecidable problems.
Thus useful relativized separations between quantum and classical complexity
classes must exclude the transmission of phase information from oracle to
computer.
