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:2601.13333

Polynomial-time certification of fidelity for many-body mixed states and mixed-state universality classes

Yuhan Liu, Yijian Zou

quant-phcond-mat.str-elSubmitted Jan 19, 2026• Announced Jan 21, 2026• 0 citations
arXivHTMLPDF

Abstract

Computation of Uhlmann fidelity between many-body mixed states generally involves full diagonalization of exponentially large matrices. In this work, we introduce a polynomial-time algorithm to compute certified lower and upper bounds for the fidelity between matrix product density operators (MPDOs). Our method maps the fidelity estimation problem to a variational optimization of sequential quantum circuits, allowing for systematic improvement of the lower bounds by increasing the circuit depth. Complementarily, we obtain certified upper bounds on fidelity by variational lower bounds on the trace distance through the same framework. We demonstrate the power of this approach with two examples: fidelity correlators in critical mixed states, and codeword distinguishability in an approximate quantum error-correcting code. Remarkably, the variational lower bound accurately track the universal scaling behavior of the fidelity with a size-consistent relative error, allowing for the extraction of previously unknown critical exponents. Our results offer an exponential improvement in precision over known moment-based bounds and establish a scalable framework for the verification of many-body quantum systems.

Comments
5+8 pages, 8 figures

Related papers

Efficient algorithm for fidelity estimation of two quantum states

Anumita Mukhopadhyay, Shibdas Roy, Arun Kumar Pati

The fidelity estimation between two quantum states is crucial for quantum computation and information science. However, an efficacious method for this, especially for mixed states and higher-dimensional density matrices, remains elusive. While there are many existing algorithms on computing the fidelity between two pure states, there is not much work on how to obtain the fidelity between two mixed states. Here, an efficient quantum algorithm for the fidelity estimation is proposed, based primarily on the density matrix exponentiation and interferometeric scheme for mixed states, with a time complexity of $O(κ^2N^2/ε^7)$, where $N$ is the system size, $κ$ is the larger of the condition number of the density matrices and $ε$ is a precision error. This algorithm may serve as a resource-efficient technique to deduce fidelity of any two (pure or mixed) unknown or known quantum states, when the density matrices of the quantum states commute with each other.

quant-pharXiv:2511.13383•Advanced Quantum Technologies•Nov 18, 2025•0 citations

Tensor-Network Algorithm for Many-Body Trace Norms

Seunghun Lee, Eun-Gook Moon

Trace norms are fundamental to quantum information theory, yet in many-body systems their evaluation remains a major computational bottleneck, as it generally requires diagonalizing exponentially large operators. Here, we overcome this bottleneck by introducing a controlled tensor-network algorithm for estimating the trace norm of matrix product operators without full diagonalization. The key idea is to combine Zolotarev's rational approximation to the sign function with a variational formulation solved using a density-matrix-renormalization-group-like algorithm. The resulting approximation is systematically improvable, with its accuracy controlled by the rational approximation parameters and the spectral weight near zero. Beyond the reach of exact diagonalization, we demonstrate controlled trace-norm calculations for entanglement negativity, quantum fidelity and quantum Fisher information, achieving substantially improved accuracy over polynomial-based Lanczos approaches. Our results establish trace-norm-based quantities as practical tensor-network observables, opening a route toward tensor-network studies of quantum information in mixed states.

quant-pharXiv:2606.11882•Jun 11, 2026•0 citations

Certifying Ground-State Properties of Many-Body Systems

Jie Wang, Jacopo Surace, Irénée Frérot +4 more

A ubiquitous problem in quantum physics is to understand the ground-state properties of many-body systems. Confronted with the fact that exact diagonalization quickly becomes impossible when increasing the system size, variational approaches are typically employed as a scalable alternative: Energy is minimized over a subset of all possible states and then different physical quantities are computed over the solution state. Despite remarkable success, rigorously speaking, all that variational methods offer are upper bounds on the ground-state energy. On the other hand, so-called relaxations of the ground-state problem based on semidefinite programming represent a complementary approach, providing lower bounds to the ground-state energy. However, in their current implementation, neither variational nor relaxation methods offer provable bound on other observables in the ground state beyond the energy. In this work, we show that the combination of the two classes of approaches can be used to derive certifiable bounds on the value of any observable in the ground state, such as correlation functions of arbitrary order, structure factors, or order parameters. We illustrate the power of this approach in paradigmatic examples of 1D and 2D spin- 1 / 2 Heisenberg models. To improve the scalability of the method, we exploit the symmetries and sparsity of the considered systems to reach sizes of hundreds of particles at much higher precision than previous works. Our analysis therefore shows how to obtain certifiable bounds on many-body ground-state properties beyond energy in a scalable way. Published by the American Physical Society 2024

arXiv:2310.05844•Physical Review X•Jul 11, 2024•15 citations

Variational quantum algorithms for trace distance and fidelity estimation

Ranyiliu Chen, Zhixin Song, Xuanqiang Zhao +1 more

Abstract Estimating the difference between quantum data is crucial in quantum computing. However, as typical characterizations of quantum data similarity, the trace distance and quantum fidelity are believed to be exponentially-hard to evaluate in general. In this work, we introduce hybrid quantum–classical algorithms for these two distance measures on near-term quantum devices where no assumption of input state is required. First, we introduce the variational trace distance estimation (VTDE) algorithm. We in particular provide the technique to extract the desired spectrum information of any Hermitian matrix by local measurement. A novel variational algorithm for trace distance estimation is then derived from this technique, with the assistance of a single ancillary qubit. Notably, VTDE could avoid the barren plateau issue with logarithmic depth circuits due to a local cost function. Second, we introduce the variational fidelity estimation algorithm. We combine Uhlmann’s theorem and the freedom in purification to translate the estimation task into an optimization problem over a unitary on an ancillary system with fixed purified inputs. We then provide a purification subroutine to complete the translation. Both algorithms are verified by numerical simulations and experimental implementations, exhibiting high accuracy for randomly generated mixed states.

arXiv:2012.05768•Quantum Science and Technology•Nov 11, 2021•58 citations

Quantum Algorithm for Fidelity Estimation

Qisheng Wang, Zhicheng Zhang, Kean Chen +4 more

For two unknown mixed quantum states$\rho $and$\sigma $in an$N$-dimensional Hilbert space, computing their fidelity$F(\rho,\sigma)$is a basic problem with many important applications in quantum computing and quantum information, for example verification and characterization of the outputs of a quantum computer, and design and analysis of quantum algorithms. In this paper, we propose a quantum algorithm that solves this problem in${\mathrm{ poly}}(\log (N), r, 1/\varepsilon)$time, where$r$is the lower rank of$\rho $and$\sigma $, and$\varepsilon $is the desired precision, provided that the purifications of$\rho $and$\sigma $are prepared by quantum oracles. This algorithm exhibits an exponential speedup over the best known algorithm (based on quantum state tomography) which has time complexity polynomial in$N$.

arXiv:2103.09076•IEEE Transactions on Information Theory•Sep 5, 2022•37 citations

Scalable Ground-State Certification of Quantum Spin Systems via Structured Noncommutative Polynomial Optimization

Jie Wang, David Jansen, Irénée Frerot +3 more

A fundamental challenge in quantum physics is determining the ground-state properties of many-body systems. Whereas standard variational approaches posit a wave-function ansatz and minimize over the possible states expressible by that ansatz, the problem can alternatively be formulated as a noncommutative polynomial optimization problem and treated through a hierarchy of semidefinite programming relaxations. In contrast to variational calculations, these relaxations provide lower bounds on ground-state energies and both lower and upper bounds on observable expectation values. However, this approach typically suffers from severe scalability issues, limiting its applicability to small-to-medium-scale systems. In this article, we demonstrate that systematically leveraging the inherent structures of the system can substantially mitigate these scalability challenges and thus permits computing meaningful bounds for quantum spin systems on square lattices of size up to $16\times16$.

quant-pharXiv:2604.01555•SciPost Physics•Apr 3, 2026•0 citations
Computation of Uhlmann fidelity between many-body mixed states generally involves full diagonalization of exponentially large matrices. In this work, we introduce a polynomial-time algorithm to compute certified lower and upper bounds for the fidelity between matrix product density operators (MPDOs). Our method maps the fidelity estimation problem to a variational optimization of sequential quantum circuits, allowing for systematic improvement of the lower bounds by increasing the circuit depth. Complementarily, we obtain certified upper bounds on fidelity by variational lower bounds on the trace distance through the same framework. We demonstrate the power of this approach with two examples: fidelity correlators in critical mixed states, and codeword distinguishability in an approximate quantum error-correcting code. Remarkably, the variational lower bound accurately track the universal scaling behavior of the fidelity with a size-consistent relative error, allowing for the extraction of previously unknown critical exponents. Our results offer an exponential improvement in precision over known moment-based bounds and establish a scalable framework for the verification of many-body quantum systems.
The fidelity estimation between two quantum states is crucial for quantum computation and information science. However, an efficacious method for this, especially for mixed states and higher-dimensional density matrices, remains elusive. While there are many existing algorithms on computing the fidelity between two pure states, there is not much work on how to obtain the fidelity between two mixed states. Here, an efficient quantum algorithm for the fidelity estimation is proposed, based primarily on the density matrix exponentiation and interferometeric scheme for mixed states, with a time complexity of O(κ2N2/ε7)O(κ^2N^2/ε^7)O(κ2N2/ε7), where NNN is the system size, κκκ is the larger of the condition number of the density matrices and εεε is a precision error. This algorithm may serve as a resource-efficient technique to deduce fidelity of any two (pure or mixed) unknown or known quantum states, when the density matrices of the quantum states commute with each other.
Trace norms are fundamental to quantum information theory, yet in many-body systems their evaluation remains a major computational bottleneck, as it generally requires diagonalizing exponentially large operators. Here, we overcome this bottleneck by introducing a controlled tensor-network algorithm for estimating the trace norm of matrix product operators without full diagonalization. The key idea is to combine Zolotarev's rational approximation to the sign function with a variational formulation solved using a density-matrix-renormalization-group-like algorithm. The resulting approximation is systematically improvable, with its accuracy controlled by the rational approximation parameters and the spectral weight near zero. Beyond the reach of exact diagonalization, we demonstrate controlled trace-norm calculations for entanglement negativity, quantum fidelity and quantum Fisher information, achieving substantially improved accuracy over polynomial-based Lanczos approaches. Our results establish trace-norm-based quantities as practical tensor-network observables, opening a route toward tensor-network studies of quantum information in mixed states.
A ubiquitous problem in quantum physics is to understand the ground-state properties of many-body systems. Confronted with the fact that exact diagonalization quickly becomes impossible when increasing the system size, variational approaches are typically employed as a scalable alternative: Energy is minimized over a subset of all possible states and then different physical quantities are computed over the solution state. Despite remarkable success, rigorously speaking, all that variational methods offer are upper bounds on the ground-state energy. On the other hand, so-called relaxations of the ground-state problem based on semidefinite programming represent a complementary approach, providing lower bounds to the ground-state energy. However, in their current implementation, neither variational nor relaxation methods offer provable bound on other observables in the ground state beyond the energy. In this work, we show that the combination of the two classes of approaches can be used to derive certifiable bounds on the value of any observable in the ground state, such as correlation functions of arbitrary order, structure factors, or order parameters. We illustrate the power of this approach in paradigmatic examples of 1D and 2D spin- 1 / 2 Heisenberg models. To improve the scalability of the method, we exploit the symmetries and sparsity of the considered systems to reach sizes of hundreds of particles at much higher precision than previous works. Our analysis therefore shows how to obtain certifiable bounds on many-body ground-state properties beyond energy in a scalable way. Published by the American Physical Society 2024
Abstract Estimating the difference between quantum data is crucial in quantum computing. However, as typical characterizations of quantum data similarity, the trace distance and quantum fidelity are believed to be exponentially-hard to evaluate in general. In this work, we introduce hybrid quantum–classical algorithms for these two distance measures on near-term quantum devices where no assumption of input state is required. First, we introduce the variational trace distance estimation (VTDE) algorithm. We in particular provide the technique to extract the desired spectrum information of any Hermitian matrix by local measurement. A novel variational algorithm for trace distance estimation is then derived from this technique, with the assistance of a single ancillary qubit. Notably, VTDE could avoid the barren plateau issue with logarithmic depth circuits due to a local cost function. Second, we introduce the variational fidelity estimation algorithm. We combine Uhlmann’s theorem and the freedom in purification to translate the estimation task into an optimization problem over a unitary on an ancillary system with fixed purified inputs. We then provide a purification subroutine to complete the translation. Both algorithms are verified by numerical simulations and experimental implementations, exhibiting high accuracy for randomly generated mixed states.
For two unknown mixed quantum states$\rho andandand\sigma inanin aninanN−dimensionalHilbertspace,computingtheirfidelity-dimensional Hilbert space, computing their fidelity−dimensionalHilbertspace,computingtheirfidelityF(\rho,\sigma)isabasicproblemwithmanyimportantapplicationsinquantumcomputingandquantuminformation,forexampleverificationandcharacterizationoftheoutputsofaquantumcomputer,anddesignandanalysisofquantumalgorithms.Inthispaper,weproposeaquantumalgorithmthatsolvesthisprobleminis a basic problem with many important applications in quantum computing and quantum information, for example verification and characterization of the outputs of a quantum computer, and design and analysis of quantum algorithms. In this paper, we propose a quantum algorithm that solves this problem inisabasicproblemwithmanyimportantapplicationsinquantumcomputingandquantuminformation,forexampleverificationandcharacterizationoftheoutputsofaquantumcomputer,anddesignandanalysisofquantumalgorithms.Inthispaper,weproposeaquantumalgorithmthatsolvesthisproblemin{\mathrm{ poly}}(\log (N), r, 1/\varepsilon)time,wheretime, wheretime,whereristhelowerrankofis the lower rank ofisthelowerrankof\rho andandand\sigma ,and, and,and\varepsilon isthedesiredprecision,providedthatthepurificationsofis the desired precision, provided that the purifications ofisthedesiredprecision,providedthatthepurificationsof\rho andandand\sigma arepreparedbyquantumoracles.Thisalgorithmexhibitsanexponentialspeedupoverthebestknownalgorithm(basedonquantumstatetomography)whichhastimecomplexitypolynomialinare prepared by quantum oracles. This algorithm exhibits an exponential speedup over the best known algorithm (based on quantum state tomography) which has time complexity polynomial inarepreparedbyquantumoracles.Thisalgorithmexhibitsanexponentialspeedupoverthebestknownalgorithm(basedonquantumstatetomography)whichhastimecomplexitypolynomialinN$.
A fundamental challenge in quantum physics is determining the ground-state properties of many-body systems. Whereas standard variational approaches posit a wave-function ansatz and minimize over the possible states expressible by that ansatz, the problem can alternatively be formulated as a noncommutative polynomial optimization problem and treated through a hierarchy of semidefinite programming relaxations. In contrast to variational calculations, these relaxations provide lower bounds on ground-state energies and both lower and upper bounds on observable expectation values. However, this approach typically suffers from severe scalability issues, limiting its applicability to small-to-medium-scale systems. In this article, we demonstrate that systematically leveraging the inherent structures of the system can substantially mitigate these scalability challenges and thus permits computing meaningful bounds for quantum spin systems on square lattices of size up to 16×1616\times1616×16.