Publications [#237031] of John H. Reif

Journal articles or Book chapters PUBLISHED

1. Reif, JH; Chakraborty, S, Efficient and exact quantum compression, Information and Computation, vol. 205 no. 7 (January, 2007), pp. 967-981, Elsevier BV, ISSN 0890-5401 [doi]
   (last updated on 2026/01/15)

   Abstract:
   We present a divide and conquer based algorithm for optimal quantum compression/decompression, using O(n(log⁴ n) log log n) elementary quantum operations. Our result provides the first quasi-linear time algorithm for asymptotically optimal (in size and fidelity) quantum compression and decompression. We also outline the quantum gate array model to bring about this compression in a quantum computer. Our method uses various classical algorithmic tools to significantly improve the bound from the previous best known bound of O(n³) for this operation. © 2007 Elsevier Inc. All rights reserved.