A novel scheme of quantum state tomography based on quantum algorithms

Recently, we try to answer the following question: what will happen to our life if quantum computers can be physically realized. In this research, we explore the impact of quantum algorithms on the time complexity of quantum state tomography based on the linear regression algorithm if quantum states can be efficiently prepared by classical information and quantum algorithms can be implemented on quantum computers. By studying current quantum algorithms based on quantum singular value decomposition (SVE) of calculating matrix multiplication, solving linear equations and eigenvalue and eigenstate estimation and so on, we propose a novel scheme to complete the mission of quantum state tomography. We show the calculation based on our algorithm as an example at last. Although quantum state preparations and extra measurements are indispensable in our quantum algorithm scheme compared with the existing classical algorithm, the time complexity of quantum state tomography can be remarkably declined. For a quantum system with dimension d, the entire quantum scheme can reduce the time complexity of quantum state tomography from O(d(4)) to O(dpoly log d) when both the condition number kappa of related matrices and the reciprocal of precision epsilon are O(poly log d), and quantum states of the same order O(d) can be simultaneously prepared. This is in contrast to the observation that quantum algorithms can reduce the time complexity of quantum state tomography to O(d(3)) when quantum states can not be efficiently prepared. In other words, the preparing of quantum states efficiently has become a bottleneck constraining the quantum acceleration.