Efficient and exact quantum compression

被引：3

作者：

Reif, John H. ^{[1
]}

Chakraborty, Sukhendu ^{[1
]}

机构：

[1] Duke Univ, Dept Comp Sci, Durham, NC 27708 USA

来源：

INFORMATION AND COMPUTATION | 2007年 / 205卷 / 07期

关键词：

quantum computing; quantum compression; algorithm;

D O I：

10.1016/j.ic.2007.01.005

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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

引用

页码：967 / 981

页数：15

共 28 条

[1]

[Anonymous], 1932, MATH FDN QUANTUM MEC

[2]

[Anonymous], 1973, ART COMPUTER PROGRAM

[3] ELEMENTARY GATES FOR QUANTUM COMPUTATION [J].

BARENCO, A ;

BENNETT, CH ;

CLEVE, R ;

DIVINCENZO, DP ;

MARGOLUS, N ;

SHOR, P ;

SLEATOR, T ;

SMOLIN, JA ;

WEINFURTER, H .

PHYSICAL REVIEW A, 1995, 52 (05) :3457-3467

[4] General fidelity limit for quantum channels [J].

Barnum, H ;

Fuchs, CA ;

Jozsa, R ;

Schumacher, B .

PHYSICAL REVIEW A, 1996, 54 (06) :4707-4711

[5] THE FUNDAMENTAL PHYSICAL LIMITS OF COMPUTATION [J].

BENNETT, CH ;

LANDAUER, R .

SCIENTIFIC AMERICAN, 1985, 253 (01) :48-56

[6] TIME-SPACE TRADE-OFFS FOR REVERSIBLE COMPUTATION [J].

BENNETT, CH .

SIAM JOURNAL ON COMPUTING, 1989, 18 (04) :766-776

[7] LOGICAL REVERSIBILITY OF COMPUTATION [J].

BENNETT, CH .

IBM JOURNAL OF RESEARCH AND DEVELOPMENT, 1973, 17 (06) :525-532

[8] QUANTUM INFORMATION AND COMPUTATION [J].

BENNETT, CH .

PHYSICS TODAY, 1995, 48 (10) :24-30

[9]

BENNETT CH, 1994, J MOD OPT

[10] A quantum analog of Huffman coding [J].

Braunstein, SL ;

Fuchs, CA ;

Gottesman, D ;

Lo, HK .

IEEE TRANSACTIONS ON INFORMATION THEORY, 2000, 46 (04) :1644-1649

← 1 2 3 →