| Design of quantum VQ iteration and quantum VQ encoding algorithm taking O（√N） steps for data compression |
| |
| 引用本文： | 庞朝阳,周正威,陈平形,郭光灿.Design of quantum VQ iteration and quantum VQ encoding algorithm taking O（√N） steps for data compression[J].中国物理 B,2006,15(3):618-623. |
| |
| 作者姓名： | 庞朝阳 周正威 陈平形 郭光灿 |
| |
| 作者单位： | (1)Key Laboratory of Quantum Information, University of Science and Technology of China, Hefei 230026, China; (2)Key Laboratory of Quantum Information, University of Science and
Technology of China, Hefei 230026, China;College of Mathematics and Software Science, Sichuan Normal University,Chengdu 610066, China |
| |
| 基金项目： | Project supported by the National Fundamental Research Program of China (Grant No 2001CB309300), the Innovation Funds of the Chinese Academy of Sciences and the Fundamental Research of Sichuan Normal University (Grant No 037003). |
| |
| 摘 要： | Vector quantization (VQ) is an important data compression
method. The key of the encoding of VQ is to find the closest vector among
N vectors for a feature vector. Many classical linear search algorithms
take $O(N)$ steps of distance computing between two vectors. The quantum VQ iteration and corresponding quantum VQ encoding algorithm that takes
$O(\sqrt N )$ steps are presented in this paper. The unitary operation of
distance computing can be performed on a number of vectors simultaneously
because the quantum state exists in a superposition of states. The quantum VQ iteration comprises three oracles, by contrast many quantum algorithms have only one oracle, such as Shor's factorization algorithm and Grover's algorithm. Entanglement state is generated and used, by contrast the state in Grover's algorithm is not an entanglement state. The quantum VQ iteration is a rotation over subspace, by contrast the Grover iteration is a rotation over global space. The quantum VQ iteration extends the Grover iteration to the more complex search that requires more oracles. The method of the quantum VQ iteration is universal.
|
| 关 键 词： | 量子VQ编码算法 数据压缩 Grover算法 量子化向量 |
| 收稿时间： | 2005-05-10 |
| 修稿时间： | 2005-05-102005-09-15 |
Design of quantum VQ iteration and quantum VQ encoding algorithm taking $O(\sqrt N )$ steps for data compression |
| |
| Pang Chao-Yang,Zhou Zheng-Wei,Chen Ping-Xing and Guo Guang-Can.Design of quantum VQ iteration and quantum VQ encoding algorithm taking $O(\sqrt N )$ steps for data compression[J].Chinese Physics B,2006,15(3):618-623. |
| |
| Authors: | Pang Chao-Yang Zhou Zheng-Wei Chen Ping-Xing and Guo Guang-Can |
| |
| Institution: | Key Laboratory of Quantum Information, University of Science and Technology of China, Hefei 230026, China; College of Mathematics and Software Science, Sichuan Normal University, Chengdu 610066, China |
| |
| Abstract: | Vector quantization (VQ) is an important data compression
method. The key of the encoding of VQ is to find the closest vector among
N vectors for a feature vector. Many classical linear search algorithms
take $O(N)$ steps of distance computing between two vectors. The quantum VQ iteration and corresponding quantum VQ encoding algorithm that takes
$O(\sqrt N )$ steps are presented in this paper. The unitary operation of
distance computing can be performed on a number of vectors simultaneously
because the quantum state exists in a superposition of states. The quantum VQ iteration comprises three oracles, by contrast many quantum algorithms have only one oracle, such as Shor's factorization algorithm and Grover's algorithm. Entanglement state is generated and used, by contrast the state in Grover's algorithm is not an entanglement state. The quantum VQ iteration is a rotation over subspace, by contrast the Grover iteration is a rotation over global space. The quantum VQ iteration extends the Grover iteration to the more complex search that requires more oracles. The method of the quantum VQ iteration is universal. |
| |
| Keywords: | data compression vector quantization Grover's algorithm quantum VQ iteration |
| 本文献已被 维普 等数据库收录！ |
| 点击此处可从《中国物理 B》浏览原始摘要信息 |
| 点击此处可从《中国物理 B》下载免费的PDF全文 |
