中国物理B ›› 2006, Vol. 15 ›› Issue (3): 618-623.doi: 10.1088/1009-1963/15/3/029

• • 上一篇    下一篇

Design of quantum VQ iteration and quantum VQ encoding algorithm taking $O(\sqrt N )$ steps for data compression

周正威1, 陈平形1, 郭光灿1, 庞朝阳2   

  1. (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
  • 收稿日期:2005-05-10 修回日期:2005-09-15 出版日期:2006-03-20 发布日期:2006-03-20
  • 基金资助:
    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).

Design of quantum VQ iteration and quantum VQ encoding algorithm taking $O(\sqrt N )$ steps for data compression

Pang Chao-Yang (庞朝阳)ab, Zhou Zheng-Wei (周正威)a, Chen Ping-Xing (陈平形)a, Guo Guang-Can (郭光灿)a   

  1. a Key Laboratory of Quantum Information, University of Science and Technology of China, Hefei 230026, China; b College of Mathematics and Software Science, Sichuan Normal University, Chengdu 610066, China
  • Received:2005-05-10 Revised:2005-09-15 Online:2006-03-20 Published:2006-03-20
  • Supported by:
    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).

PDF (PC)

563

赞

摘要： 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.

关键词: data compression, vector quantization, Grover's algorithm, quantum VQ iteration

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.

Key words: data compression, vector quantization, Grover's algorithm, quantum VQ iteration

中图分类号:  (Quantum computation architectures and implementations)

  • 03.67.Lx
03.67.Mn (Entanglement measures, witnesses, and other characterizations)