Impact of quantum algorithms on time complexity of classical-data problems
Kai Li, Le Yang, Dai HongYi, Ming Zhang · 2019
We explore the impact of quantum algorithms on classical-data problems if quantum algorithms can be implemented on quantum computers. It is underlined in this paper that both state estimator design problems for classical linear systems and quantum state tomography can be considered as classical-data problems. Our recent research indicated that the time complexity of state estimator design problems can be reduced to O(qn) in comparison to the time complexity O(n6) in traditional classical algorithms when quantum states can be efficiently prepared, the system matrix is sparse, and both the condition number κ and the reciprocal of precision ε are small in size O(poly log(n)), where n is the dimension of the state x(t) and q is the dimension of the input u(t). This is in contrast to the further observation that the time complexity of state estimator design problems is O(n2) when quantum states cannot be efficiently prepared. The time complexity of quantum state tomography with dimension d is O(d4) when classical algorithms are adopted. We have demonstrated that if the system matrix is sparse, and both the condition number κ and the reciprocal of precision ε are small in size O(poly log(d)), quantum algorithms can reduce the time complexity of quantum state tomography to O(dpoly log d) or O(d3) when quantum states can or cannot be efficiently prepared. In other words, preparing quantum states efficiently has become a bottleneck constraint for quantum acceleration. Our recent researches can be regarded as a novel attempt of enriching application area of quantum computation.