Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Acta Physica Sinica

A novel scheme of quantum state tomography based on quantum algorithms

Le Yang, Kai Li, Hong‐Yi Dai, Ming Zhang

Published Jan 1, 2019• 4 citations
Publisher

Abstract

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 \begin{document}$ O(d^{4}) $\end{document} to \begin{document}$ O(d\mathrm{poly}\log d) $\end{document} when both the condition number \begin{document}$ \kappa $\end{document} of related matrices and the reciprocal of precision \begin{document}$ \varepsilon $\end{document} are \begin{document}$ O(\mathrm{poly}\log d) $\end{document} , and quantum states of the same order \begin{document}$ O(d) $\end{document} can be simultaneously prepared. This is in contrast to the observation that quantum algorithms can reduce the time complexity of quantum state tomography to \begin{document}$O(d^3) $\end{document} 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.

DOI
10.7498/aps.68.20190157

Related papers

Impact of quantum algorithms on time complexity of classical-data problems

Kai Li, Le Yang, Dai HongYi +1 more

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.

Chinese Control Conference (CCC)•Jul 1, 2019•5 citations

Quantum Algorithms for Solving Linear Regression Equation

Kai Li, Hong‐Yi Dai, Jing Feng +4 more

Abstract Linear regression is one of the most important and common analytical methods in mathematical statistics. The letter studies a general model of linear regression problem based on least squares method, and investigates the impact of quantum algorithms on the time complexity of solving linear regression problem when quantum algorithms can be implemented on quantum computers. With the help of the general model of linear regression problem in terms of least squares method, we propose a novel simplified quantum scheme for solving linear regression equation based on the sparsity-independent quantum singular value estimation algorithm. For a linear regression equation with dimension n, our scheme can reduce the time complexity from O(Nn 2) to O ( N log N ) when both the condition number κ of related matrices and the reciprocal of precision ∈ are small in size O(play logN), where m is the dimension of the input u and N is the number of samples.

Journal of Physics Conference Series•Jan 1, 2021•6 citations

Reconstructing quantum states efficiently

M. Cramer, Martin Bodo Plenio

Quantum state tomography, the ability to deduce the density matrix of a quantum system from measured data, is of fundamental importance for the verification of present and future quantum devices. It has been realized in systems with few components but for larger systems it becomes rapidly infeasible because the number of quantum measurements and computational resources required to process them grow exponentially in the system size. Here we show that we can gain an exponential advantage over direct state tomography for quantum states typically realized in nature. Based on singular value thresholding and matrix product state methods we introduce a state reconstruction scheme that relies only on a linear number of measurements. The computational resources for the postprocessing required to reconstruct the state with high fidelity from these measurements is polynomial in the system size.

arXiv:1002.3780•Feb 19, 2010•5 citations

Quantum State Tomography via Compressed Sensing

David Gross, Yi-Kai Liu, Steven T. Flammia +2 more

We establish methods for quantum state tomography based on compressed sensing. These methods are specialized for quantum states that are fairly pure, and they offer a significant performance improvement on large quantum systems. In particular, they are able to reconstruct an unknown density matrix of dimension d and rank r using O(rdlog²d) measurement settings, compared to standard methods that require d² settings. Our methods have several features that make them amenable to experimental implementation: they require only simple Pauli measurements, use fast convex optimization, are stable against noise, and can be applied to states that are only approximately low rank. The acquired data can be used to certify that the state is indeed close to pure, so no a priori assumptions are needed.

arXiv:0909.3304•Physical Review Letters•Oct 4, 2010•1,097 citations

Quantum Reconstruction Algorithm

Jincheng Zhang

Quantum reconstruction algorithms represent a significant advancement in the field of quantum information processing, offering the potential to reconstruct complex quantum states from a single measurement. This paper explores the development of a novel quantum reconstruction algorithm, designed to efficiently restore quantum systems and predict quantum parameter values. We present a robust and scalable approach leveraging quantum state analysis and rapid reconstruction capabilities, addressing the limitations of existing methods. The core mechanism centers around a quantum state reconstruction process that minimizes computational overhead while maximizing accuracy.

•Sep 3, 2026•0 citations

Efficient Quantum Tomography with Fidelity Estimation.

Zhaoyu Han, Jun Wang, Songbo Wang +4 more

We propose a quantum tomography scheme for pure states which adopts machine learning methods, along with a built-in fidelity estimation approach to assess the reliability of the tomographic state. We prove the validity of the scheme theoretically and perform numerically simulated experiments on several typical target quantum states such as W, cluster and dimer states. We find that the required number of measurements to meet the convergence criterion does not grow exponentially in the number of qubits, thus the scheme achieves high efficiency that is crucial for large-scale quantum states tomography in a laboratory.

•Dec 8, 2017•3 citations
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 \begin{document}O(d4)O(d^{4})O(d4)\end{document} to \begin{document}O(dpolylog⁡d)O(d\mathrm{poly}\log d)O(dpolylogd)\end{document} when both the condition number \begin{document}κ\kappaκ\end{document} of related matrices and the reciprocal of precision \begin{document}ε\varepsilonε\end{document} are \begin{document}O(polylog⁡d)O(\mathrm{poly}\log d)O(polylogd)\end{document} , and quantum states of the same order \begin{document}O(d)O(d)O(d)\end{document} can be simultaneously prepared. This is in contrast to the observation that quantum algorithms can reduce the time complexity of quantum state tomography to \begin{document}O(d3)O(d^3) O(d3)\end{document} 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.
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.
Abstract Linear regression is one of the most important and common analytical methods in mathematical statistics. The letter studies a general model of linear regression problem based on least squares method, and investigates the impact of quantum algorithms on the time complexity of solving linear regression problem when quantum algorithms can be implemented on quantum computers. With the help of the general model of linear regression problem in terms of least squares method, we propose a novel simplified quantum scheme for solving linear regression equation based on the sparsity-independent quantum singular value estimation algorithm. For a linear regression equation with dimension n, our scheme can reduce the time complexity from O(Nn 2) to O ( N log N ) when both the condition number κ of related matrices and the reciprocal of precision ∈ are small in size O(play logN), where m is the dimension of the input u and N is the number of samples.
Quantum state tomography, the ability to deduce the density matrix of a quantum system from measured data, is of fundamental importance for the verification of present and future quantum devices. It has been realized in systems with few components but for larger systems it becomes rapidly infeasible because the number of quantum measurements and computational resources required to process them grow exponentially in the system size. Here we show that we can gain an exponential advantage over direct state tomography for quantum states typically realized in nature. Based on singular value thresholding and matrix product state methods we introduce a state reconstruction scheme that relies only on a linear number of measurements. The computational resources for the postprocessing required to reconstruct the state with high fidelity from these measurements is polynomial in the system size.
We establish methods for quantum state tomography based on compressed sensing. These methods are specialized for quantum states that are fairly pure, and they offer a significant performance improvement on large quantum systems. In particular, they are able to reconstruct an unknown density matrix of dimension d and rank r using O(rdlog²d) measurement settings, compared to standard methods that require d² settings. Our methods have several features that make them amenable to experimental implementation: they require only simple Pauli measurements, use fast convex optimization, are stable against noise, and can be applied to states that are only approximately low rank. The acquired data can be used to certify that the state is indeed close to pure, so no a priori assumptions are needed.
Quantum reconstruction algorithms represent a significant advancement in the field of quantum information processing, offering the potential to reconstruct complex quantum states from a single measurement. This paper explores the development of a novel quantum reconstruction algorithm, designed to efficiently restore quantum systems and predict quantum parameter values. We present a robust and scalable approach leveraging quantum state analysis and rapid reconstruction capabilities, addressing the limitations of existing methods. The core mechanism centers around a quantum state reconstruction process that minimizes computational overhead while maximizing accuracy.
We propose a quantum tomography scheme for pure states which adopts machine learning methods, along with a built-in fidelity estimation approach to assess the reliability of the tomographic state. We prove the validity of the scheme theoretically and perform numerically simulated experiments on several typical target quantum states such as W, cluster and dimer states. We find that the required number of measurements to meet the convergence criterion does not grow exponentially in the number of qubits, thus the scheme achieves high efficiency that is crucial for large-scale quantum states tomography in a laboratory.