Studies On The Quantum Counting Algorithm

Counting problem is not only one of the basic problems in mathematics and statistics,but also one of the essential steps in procedures of solving practical works(e.g.np-complete problem).It answers the question: how many solutions satisfy certain criteria in the given solution space? When the solution space is small,the most common way of solving a counting problem is by the enumeration method.Otherwise,the enumeration method needs high requirement on time complexity,and the cost of solving the problem is too high to meet the practical needs.With the rapid increase in the size of the data set,in order to improve the efficiency of solving problems,the solution to the counting problem has been continuously improved,including using machinery instead of manpower to design automatic counting devices,and using intelligent recognition algorithms to increase target retrieval speed.Faced with a huge data set,classical approach called proportion estimation is often used to reduce the time requirement.To reduce the size of the search space,it searches solutions in the sample space instead of the original solution space.Since Deutsch-Jozsa quantum algorithm proposed in 1992,the emergence of quantum algorithms is expected to solve the difficult problem of big data processing brought by the era of information explosion.A great many scientific researchers take much interest and confidence in it.The development of quantum computing technology brings a new solution to the counting problem.By using the characteristics of quantum state: superposition,entanglement,etc.,quantum counting algorithm was proposed in1996.Examples show that for the same problem,under the same accuracy,the quantum counting algorithm can provide quadratic acceleration compared to the traditional algorithm.Based on this,the paper made some researches on quantum counting algorithm:(1)Non-uniform initial amplitude distribution is possible due to the diversity of situations on counting problems or external noise in the amplitude initialization procedure.By modelling in three-dimensional space spanned by unmarked state,marked state and free state to the entire Hilbert space of n qubits,we find Grover iteration can be regarded as improper rotation in the space.This allows us to give formula to solve counting problem.Furthermore,we express initial amplitude distribution in the eigenvector basis of improper rotation matrix.This is necessary to obtain mathematical analysis of counting problem on various situations.A generalized quantum counting algorithm,which is suitable for non-uniform initial amplitude distribution,is designed from the analysis results.(2)Entanglement is a unique characteristic of quantum states,many interesting applications such as quantum teleportation have been developed using this characteristic.But is the entanglement related to the performance of quantum algorithms? The role of entanglement in achieving the quantum computational speedup is not fully understood.By theoretical analysis and numerical calculation of four practical use cases,we investigate the entanglement features of the quantum states employed in quantum phase estimation algorithm and quantum counting algorithm.The results show that whether these two algorithms generate entanglement depend on whether the input quantum state of the second register is a superposition state of the eigenstates.(3)Using theoretical analysis and numerical calculation of practical use cases,we investigate the entanglement features of the quantum states used in the quantum counting algorithm.The results show that if and only if the solution number is 0 or equal to item number in the search space,the algorithm generates no entanglement.It has been theoretically justified that when the counting result M is large,the quantum counting algorithm achieves much faster convergence rate than the classical proportion estimation method.We provide further evidence that the quantum approach has the same time complexity as the classical approach when it generates no entanglement.In summary,this paper did some painstaking work on quantum counting algorithm.For the universality of the algorithm,We designed generalized quantum counting algorithm to suitable for non-uniform initial amplitude distribution.For the algorithm itself,through comparison between quantum approach and classical proportion estimation method,we studied the role of entanglement,a fascinating nonclassical feature,in quantum counting algorithm.