中国物理B ›› 2006, Vol. 15 ›› Issue (3): 618-623.doi: 10.1088/1009-1963/15/3/029
周正威1, 陈平形1, 郭光灿1, 庞朝阳2
Pang Chao-Yang (庞朝阳)ab, Zhou Zheng-Wei (周正威)a, Chen Ping-Xing (陈平形)a, Guo Guang-Can (郭光灿)a
摘要: 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.
中图分类号: (Quantum computation architectures and implementations)