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

arXiv:2610.34696

Rank-one Factored Gradient Descent without Restricted Isometry: Application to Quantum Pure State Tomography on Multi-Qubits

Takahiro Kajisa

quant-phmath.OCSubmitted Oct 26, 2026• Announced Oct 27, 2026• 0 citations
arXivHTMLPDF

Abstract

Factored gradient descent (FGD) is a scalable nonconvex method for low-rank positive semidefinite matrix recovery, in which the rank and positivity constraints are satisfied automatically by the factorization. Most of the existing theory that certifies benignity of its loss landscape, however, relies on a restricted isometry property (RIP) of the measurement map. In quantum state tomography, one of its applications, the measurements that can be acquired with stable statistics are limited by detection efficiency and drift to Pauli observables of low weight; we first show that under such partial-weight Pauli measurements RIP fails in the worst possible way. We then bundle the mutually commuting observables setting by setting, pushing the state forward to the probability distribution of each setting, and introduce a max-sliced total-variation loss. On the stratum where the setting attaining the maximum is unique there is no spurious local minimum, and provided only that the measurement map is injective on generic pure states, the global minimum is the truth up to a phase. Finally we verify these claims numerically on four qubits and compare against FGD with the ordinary loss.

AI Summary

The paper studies rank-one factored optimization for pure-state tomography when only partial-weight Pauli measurements are available. For $n=2N$ qubits, it considers all Pauli expectations of weight at most $N$, invoking generic identifiability among pure states. A GHZ-phase family shows that measurements supported on proper subsets have a nonzero rank-two kernel element, ruling out rank-two restricted isometry with $\delta_2<1$. The proposed loss groups commuting observables into measurement settings and minimizes the maximum, over settings, of the $\ell^1$ discrepancy between predicted and observed outcome distributions. Its landscape theorem applies at positive-loss points with a unique maximizing setting: stationarity holds exactly when every deficient outcome cell has zero predicted probability. Such stationary points admit an explicit second-order descent direction, so no positive-loss local minimum occurs on this stratum. The proof characterizes realizable first-order probability flows and constructs descent by populating an empty deficient cell. With exact data and an identifiable truth, zero loss determines the state up to phase. Four-qubit simulations use 54 settings and perturbed cluster-state targets. On noiseless data, momentum-assisted max-sliced descent succeeds in 100/100 trials, versus 75/100 for Pauli least squares. With finite shots, max-sliced initialization followed by least-squares polishing performs best among the tested schemes. The theorem leaves multiple-maximizer tie points unresolved; no global convergence guarantee is established. Experiments are limited to four qubits, omit detection inefficiency and drift, and report some near-tie stalling at low shot counts.

No sign of AI-generated textAI use disclosedOverclaimsStrong assumptions
we used generative AI tools for implementing the numerical experiments, for translating and copy-editing the manuscript, and for producing the figure sources.

Error found: Generic injectivity guarantees a unique zero-loss solution only for an identifiable truth, a qualification missing from the abstract and required by the paper's own GHZ counterexample. The generic-identifiability proposition and global-uniqueness corollary incorrectly include two qubits, whose generic pure states retain an undetermined relative Schmidt phase when only one-qubit marginals are measured.

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Related papers

Quantum State Tomography via Nonconvex Riemannian Gradient Descent

Ming-Chien Hsu, En-Jui Kuo, Wei-Hsuan Yu +2 more

The recovery of an unknown density matrix of large size requires huge computational resources. State-of-the-art performance has recently been achieved with the factored gradient descent (FGD) algorithm and its variants since they are able to mitigate the dimensionality barrier by utilizing some of the underlying structures of the density matrix. Despite the theoretical guarantee of a linear convergence rate, convergence in practical scenarios is still slow because the contracting factor of the FGD algorithms depends on the condition number κ of the ground truth state. Consequently, the total number of iterations needed to achieve the estimation error ϵ can be as large as O(sqrt[κ]ln(1/ϵ)). In this Letter, we derive a quantum state tomography scheme that improves the dependence on κ to the logarithmic scale. Thus, our algorithm can achieve the approximation error ϵ in O(ln(1/κϵ)) steps. The improvement comes from the application of nonconvex Riemannian gradient descent (RGD). The contracting factor in our approach is thus a universal constant that is independent of the given state. Our theoretical results of extremely fast convergence and nearly optimal error bounds are corroborated by the numerical results.

arXiv:2210.04717•Physical Review Letters•Jun 13, 2024•18 citations

Efficient factored gradient descent algorithm for quantum state tomography

Yong Wang, Lijun Liu, Shuming Cheng +2 more

Reconstructing the state of quantum many-body systems is of fundamental importance in quantum information tasks, but extremely challenging due to the curse of dimensionality. In this work, we present an efficient quantum tomography protocol that combines the state-factored with eigenvalue mapping to address the rank-deficient issue and incorporates a momentum-accelerated gradient descent algorithm to speed up the optimization process. We implement extensive numerical experiments to demonstrate that our factored gradient descent algorithm efficiently mitigates the rank-deficient problem and admits orders of magnitude better tomography accuracy and faster convergence. We also find that our method can accomplish the full-state tomography of random 11-qubit mixed states within one minute. Published by the American Physical Society 2024

arXiv:2207.05341•Physical Review Research•Jul 8, 2024•15 citations

Local Stochastic Factored Gradient Descent for Distributed Quantum State Tomography

Junhyung Lyle Kim, Mohammad Taha Toghani, César A. Uribe +1 more

We propose a distributed Quantum State Tomography (QST) protocol, named Local Stochastic Factored Gradient Descent (Local SFGD), to learn the low-rank factor of a density matrix over a set of local machines. QST is the canonical procedure to characterize the state of a quantum system, which we formulate as a stochastic non-convex smooth optimization problem. Physically, the estimation of a low-rank density matrix helps characterizing the amount of noise introduced by quantum computation. Theoretically, we prove the local convergence of Local SFGD for a general class of restricted strongly convex/smooth loss functions. Local SFGD converges locally to a small neighborhood of the global optimum at a linear rate with a constant step size, while it locally converges exactly at a sub-linear rate with diminishing step sizes. With a proper initialization, local convergence results imply global convergence. We validate our theoretical findings with numerical simulations of QST on the Greenberger-Horne-Zeilinger (GHZ) state.

arXiv:2203.11579•IEEE Control Systems Letters•Jun 28, 2022•2 citations

Universal Low-rank Matrix Recovery from Pauli Measurements

Yi-Kai Liu

We study the problem of reconstructing an unknown matrix M of rank r and dimension d using O(rd poly log d) Pauli measurements. This has applications in quantum state tomography, and is a non-commutative analogue of a well-known problem in compressed sensing: recovering a sparse vector from a few of its Fourier coefficients. We show that almost all sets of O(rd log^6 d) Pauli measurements satisfy the rank-r restricted isometry property (RIP). This implies that M can be recovered from a fixed ("universal") set of Pauli measurements, using nuclear-norm minimization (e.g., the matrix Lasso), with nearly-optimal bounds on the error. A similar result holds for any class of measurements that use an orthonormal operator basis whose elements have small operator norm. Our proof uses Dudley's inequality for Gaussian processes, together with bounds on covering numbers obtained via entropy duality.

arXiv:1103.2816•Mar 14, 2011•101 citations

Rank-Adaptive Matrix-Free Atomic Quantum State Tomography

Amirhossein Taherpour, Alireza Sadeghi, Georgios B. Giannakis

Quantum state tomography estimates an unknown density operator from measurement data. Dense reconstruction however, can be impractical for many-qubit systems because the Hilbert-space dimension grows exponentially. This contribution develops a rank-adaptive matrix-free approach to low-rank quantum state tomography based on rank-one atomic coordinates. The density operator is represented as a convex combination of pure-state atoms, which preserves positivity and unit trace while avoiding dense density, measurement, and gradient matrices. The resultant algorithm combines atom updates, simplex-constrained coefficient reweighting, and periodic spectral refactorization using only predicted probability vectors, atom vectors, and descriptor-level measurement actions. These computations decompose across measurement outcomes, and admit a master--worker implementation with the measurements partitioned across workers. A rank penalty adapts the representation size during optimization. Provable feasibility, prediction consistency, monotone descent of the penalized objective, and an exact spectral proximal characterization of the refactorization step are established. Simulations with Pauli measurements show favorable accuracy--runtime--memory tradeoffs relative to competing alternatives.

quant-pharXiv:2607.19577•Jul 23, 2026•2 citations

Rigorous maximum-likelihood estimation for quantum states

K. Aditi, Stephen Becker

Existing quantum state tomography methods are limited in scalability due to their high computation and memory demands, making them impractical for the recovery of large quantum states. In this work, we address these limitations by reformulating the maximum likelihood estimation problem using the Burer--Monteiro factorization, resulting in a nonconvex but low-rank parametrization of the density matrix. We derive a fully unconstrained formulation by analytically eliminating the trace-one and positive-semidefinite constraints, thereby avoiding the need for projection steps during optimization. Furthermore, we determine the Lagrange multiplier associated with the unit-trace constraint a priori, reducing computational overhead. The resulting formulation is amenable to scalable first-order optimization, and we demonstrate its tractability using the limited-memory Broyden-Fletcher-Goldfarb-Shanno method. Importantly, we also propose a low-memory version of the above algorithm to fully recover certain large quantum states with Pauli-based positive-operator-value measurements. Our low-memory algorithm avoids explicitly forming any density matrix, and does not require the density matrix to have a matrix product state or other tensor structure. For a fixed number of measurements and fixed rank, our algorithm requires just $O(d{log}_{2}d)$ complexity per iteration to recover a $d\ifmmode\times\else\texttimes\fi{}d$ density matrix. Additionally, we derive a useful error bound that can be used to give a rigorous termination criterion. We numerically demonstrate that our method is competitive with state-of-the-art algorithms for moderately sized problems, and then demonstrate that our method can solve a 20-qubit problem on a laptop in under 5 hours.

arXiv:2506.16646•Physical Review A•Nov 19, 2025•1 citation
Factored gradient descent (FGD) is a scalable nonconvex method for low-rank positive semidefinite matrix recovery, in which the rank and positivity constraints are satisfied automatically by the factorization. Most of the existing theory that certifies benignity of its loss landscape, however, relies on a restricted isometry property (RIP) of the measurement map. In quantum state tomography, one of its applications, the measurements that can be acquired with stable statistics are limited by detection efficiency and drift to Pauli observables of low weight; we first show that under such partial-weight Pauli measurements RIP fails in the worst possible way. We then bundle the mutually commuting observables setting by setting, pushing the state forward to the probability distribution of each setting, and introduce a max-sliced total-variation loss. On the stratum where the setting attaining the maximum is unique there is no spurious local minimum, and provided only that the measurement map is injective on generic pure states, the global minimum is the truth up to a phase. Finally we verify these claims numerically on four qubits and compare against FGD with the ordinary loss.
The paper studies rank-one factored optimization for pure-state tomography when only partial-weight Pauli measurements are available. For n=2Nn=2Nn=2N qubits, it considers all Pauli expectations of weight at most NNN, invoking generic identifiability among pure states. A GHZ-phase family shows that measurements supported on proper subsets have a nonzero rank-two kernel element, ruling out rank-two restricted isometry with δ2<1\delta_2<1δ2​<1.
The proposed loss groups commuting observables into measurement settings and minimizes the maximum, over settings, of the ℓ1\ell^1ℓ1 discrepancy between predicted and observed outcome distributions. Its landscape theorem applies at positive-loss points with a unique maximizing setting: stationarity holds exactly when every deficient outcome cell has zero predicted probability. Such stationary points admit an explicit second-order descent direction, so no positive-loss local minimum occurs on this stratum. The proof characterizes realizable first-order probability flows and constructs descent by populating an empty deficient cell. With exact data and an identifiable truth, zero loss determines the state up to phase.
Four-qubit simulations use 54 settings and perturbed cluster-state targets. On noiseless data, momentum-assisted max-sliced descent succeeds in 100/100 trials, versus 75/100 for Pauli least squares. With finite shots, max-sliced initialization followed by least-squares polishing performs best among the tested schemes. The theorem leaves multiple-maximizer tie points unresolved; no global convergence guarantee is established. Experiments are limited to four qubits, omit detection inefficiency and drift, and report some near-tie stalling at low shot counts.
The recovery of an unknown density matrix of large size requires huge computational resources. State-of-the-art performance has recently been achieved with the factored gradient descent (FGD) algorithm and its variants since they are able to mitigate the dimensionality barrier by utilizing some of the underlying structures of the density matrix. Despite the theoretical guarantee of a linear convergence rate, convergence in practical scenarios is still slow because the contracting factor of the FGD algorithms depends on the condition number κ of the ground truth state. Consequently, the total number of iterations needed to achieve the estimation error ϵ can be as large as O(sqrt[κ]ln(1/ϵ)). In this Letter, we derive a quantum state tomography scheme that improves the dependence on κ to the logarithmic scale. Thus, our algorithm can achieve the approximation error ϵ in O(ln(1/κϵ)) steps. The improvement comes from the application of nonconvex Riemannian gradient descent (RGD). The contracting factor in our approach is thus a universal constant that is independent of the given state. Our theoretical results of extremely fast convergence and nearly optimal error bounds are corroborated by the numerical results.
Reconstructing the state of quantum many-body systems is of fundamental importance in quantum information tasks, but extremely challenging due to the curse of dimensionality. In this work, we present an efficient quantum tomography protocol that combines the state-factored with eigenvalue mapping to address the rank-deficient issue and incorporates a momentum-accelerated gradient descent algorithm to speed up the optimization process. We implement extensive numerical experiments to demonstrate that our factored gradient descent algorithm efficiently mitigates the rank-deficient problem and admits orders of magnitude better tomography accuracy and faster convergence. We also find that our method can accomplish the full-state tomography of random 11-qubit mixed states within one minute. Published by the American Physical Society 2024
We propose a distributed Quantum State Tomography (QST) protocol, named Local Stochastic Factored Gradient Descent (Local SFGD), to learn the low-rank factor of a density matrix over a set of local machines. QST is the canonical procedure to characterize the state of a quantum system, which we formulate as a stochastic non-convex smooth optimization problem. Physically, the estimation of a low-rank density matrix helps characterizing the amount of noise introduced by quantum computation. Theoretically, we prove the local convergence of Local SFGD for a general class of restricted strongly convex/smooth loss functions. Local SFGD converges locally to a small neighborhood of the global optimum at a linear rate with a constant step size, while it locally converges exactly at a sub-linear rate with diminishing step sizes. With a proper initialization, local convergence results imply global convergence. We validate our theoretical findings with numerical simulations of QST on the Greenberger-Horne-Zeilinger (GHZ) state.
We study the problem of reconstructing an unknown matrix M of rank r and dimension d using O(rd poly log d) Pauli measurements. This has applications in quantum state tomography, and is a non-commutative analogue of a well-known problem in compressed sensing: recovering a sparse vector from a few of its Fourier coefficients. We show that almost all sets of O(rd log^6 d) Pauli measurements satisfy the rank-r restricted isometry property (RIP). This implies that M can be recovered from a fixed ("universal") set of Pauli measurements, using nuclear-norm minimization (e.g., the matrix Lasso), with nearly-optimal bounds on the error. A similar result holds for any class of measurements that use an orthonormal operator basis whose elements have small operator norm. Our proof uses Dudley's inequality for Gaussian processes, together with bounds on covering numbers obtained via entropy duality.
Quantum state tomography estimates an unknown density operator from measurement data. Dense reconstruction however, can be impractical for many-qubit systems because the Hilbert-space dimension grows exponentially. This contribution develops a rank-adaptive matrix-free approach to low-rank quantum state tomography based on rank-one atomic coordinates. The density operator is represented as a convex combination of pure-state atoms, which preserves positivity and unit trace while avoiding dense density, measurement, and gradient matrices. The resultant algorithm combines atom updates, simplex-constrained coefficient reweighting, and periodic spectral refactorization using only predicted probability vectors, atom vectors, and descriptor-level measurement actions. These computations decompose across measurement outcomes, and admit a master--worker implementation with the measurements partitioned across workers. A rank penalty adapts the representation size during optimization. Provable feasibility, prediction consistency, monotone descent of the penalized objective, and an exact spectral proximal characterization of the refactorization step are established. Simulations with Pauli measurements show favorable accuracy--runtime--memory tradeoffs relative to competing alternatives.
Existing quantum state tomography methods are limited in scalability due to their high computation and memory demands, making them impractical for the recovery of large quantum states. In this work, we address these limitations by reformulating the maximum likelihood estimation problem using the Burer--Monteiro factorization, resulting in a nonconvex but low-rank parametrization of the density matrix. We derive a fully unconstrained formulation by analytically eliminating the trace-one and positive-semidefinite constraints, thereby avoiding the need for projection steps during optimization. Furthermore, we determine the Lagrange multiplier associated with the unit-trace constraint a priori, reducing computational overhead. The resulting formulation is amenable to scalable first-order optimization, and we demonstrate its tractability using the limited-memory Broyden-Fletcher-Goldfarb-Shanno method. Importantly, we also propose a low-memory version of the above algorithm to fully recover certain large quantum states with Pauli-based positive-operator-value measurements. Our low-memory algorithm avoids explicitly forming any density matrix, and does not require the density matrix to have a matrix product state or other tensor structure. For a fixed number of measurements and fixed rank, our algorithm requires just O(dlog2d)O(d{log}_{2}d)O(dlog2​d) complexity per iteration to recover a $d\ifmmode\times\else\texttimes\fi{}d$ density matrix. Additionally, we derive a useful error bound that can be used to give a rigorous termination criterion. We numerically demonstrate that our method is competitive with state-of-the-art algorithms for moderately sized problems, and then demonstrate that our method can solve a 20-qubit problem on a laptop in under 5 hours.