David P. DiVincenzo, Barbara M. Terhal
Foundations of Physics
An explicit algorithm for performing Schumacher’s noiseless compression of quantum bits is given. This algorithm is based on a combinatorial expression for a particular bijection among binary strings. The algorithm, which adheres to the rules of reversible programming, is expressed in a high-level pseudocode language. It is implemented using O([Formula Presented]) two- and three-bit primitive reversible operations, where n is the length of the qubit strings to be compressed. Also, the algorithm makes use of O(n) auxiliary qubits. Space-saving techniques based on those proposed by Bennett are developed which reduce this workspace to O(√n) while maintaining a running time of O([Formula Presented]) (albeit with a larger constant). This latter algorithm is of interest because it has a slightly smaller time-space product, which is considered to be the relevant figure of merit for efficiency in some physical models. © 1996 The American Physical Society.
David P. DiVincenzo, Barbara M. Terhal
Foundations of Physics
David P. DiVincenzo
Nobel Symposium: Qubits for Future Quantum Information 2009
Barbara M. Terhal, Micha Horodecki, et al.
Journal of Mathematical Physics
David P. DiVincenzo, William Krakow, et al.
Journal of Non-Crystalline Solids