We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Quantum search algorithm for set operation.
- Authors
Pang, Chao-Yang; Zhou, Ri-Gui; Ding, Cong-Bao; Hu, Ben-Qiong
- Abstract
The operations of data set, such as intersection, union and complement, are the fundamental calculation in mathematics. It's very significant that designing fast algorithm for set operation. In this paper, the quantum algorithm for calculating intersection set $${\text{C}=\text{A}\cap \text{B}}$$ is presented. Its runtime is $${O\left( {\sqrt{\left| A \right|\times \left| B \right|\times \left|C \right|}}\right)}$$ for case $${\left| C \right|\neq \phi}$$ and $${O\left( {\sqrt{\left| A \right|\times \left| B \right|}}\right)}$$ for case $${\left| C \right|=\phi}$$ (i.e. C is empty set), while classical computation needs O (| A| × | B|) steps of computation in general, where |.| denotes the size of set. The presented algorithm is the combination of Grover's algorithm, classical memory and classical iterative computation, and the combination method decrease the complexity of designing quantum algorithm. The method can be used to design other set operations as well.
- Subjects
QUANTUM information theory; SEARCH algorithms; ITERATIVE methods (Mathematics); SYSTEMS design; SET theory; MATHEMATICS
- Publication
Quantum Information Processing, 2013, Vol 12, Issue 1, p481
- ISSN
1570-0755
- Publication type
Article
- DOI
10.1007/s11128-012-0385-8