Efficient and exact quantum compression


Journal Article

We present a divide and conquer based algorithm for optimal quantum compression/decompression, using O(n(log4 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(n3) for this operation. © 2007 Elsevier Inc. All rights reserved.

Full Text

Duke Authors

Cited Authors

  • Reif, JH; Chakraborty, S

Published Date

  • January 1, 2007

Published In

Volume / Issue

  • 205 / 7

Start / End Page

  • 967 - 981

Electronic International Standard Serial Number (EISSN)

  • 1090-2651

International Standard Serial Number (ISSN)

  • 0890-5401

Digital Object Identifier (DOI)

  • 10.1016/j.ic.2007.01.005

Citation Source

  • Scopus