Physical Review Letters
Maximum Amount of Information Obtainable from a Single Quantum Query of a Database
Masato Koashi, Nobuyuki Imoto
Abstract
The maximum amount of information obtainable from a single query of a database through an $n$-bit bus register is $n$ bits in a classical algorithm. A quantum algorithm can exceed this bound by a factor of 2, and this limit can be reached by encoding the excess $n$ bits of information on the quantum phases of the register. We further show that the information in amounts close to this limit can also be extracted even if the database does not utilize quantum phases directly.