Rank Is All You Need: Estimating the Trace of Powers of Density Matrices

• URL: http://arxiv.org/abs/2408.00314v1
• Date: Thu, 1 Aug 2024 06:23:52 GMT
• Title: Rank Is All You Need: Estimating the Trace of Powers of Density Matrices
• Authors: Myeongjin Shin, Junseo Lee, Seungwoo Lee, Kabgyun Jeong,
• Abstract summary: Estimating the trace of powers of identical $k$ density matrices is a crucial subroutine for many applications. Inspired by the Newton-Girard method, we developed an algorithm that uses only $mathcalO(r)$ qubits and $mathcalO(r)$ multi-qubit gates.
• Score: 1.5133368155322298
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Estimating the trace of powers of identical $k$ density matrices (i.e., $\text{Tr}(\rho^k)$) is a crucial subroutine for many applications such as calculating nonlinear functions of quantum states, preparing quantum Gibbs states, and mitigating quantum errors. Reducing the requisite number of qubits and gates is essential to fit a quantum algorithm onto near-term quantum devices. Inspired by the Newton-Girard method, we developed an algorithm that uses only $\mathcal{O}(r)$ qubits and $\mathcal{O}(r)$ multi-qubit gates, where $r$ is the rank of $\rho$. We prove that the estimation of $\{\text{Tr}(\rho^i)\}_{i=1}^r$ is sufficient for estimating the trace of powers with large $k > r$. With these advantages, our algorithm brings the estimation of the trace of powers closer to the capabilities of near-term quantum processors. We show that our results can be generalized for estimating $\text{Tr}(M\rho^k)$, where $M$ is an arbitrary observable, and demonstrate the advantages of our algorithm in several applications.

Related papers

• Calculating response functions of coupled oscillators using quantum phase estimation [40.31060267062305]
  We study the problem of estimating frequency response functions of systems of coupled, classical harmonic oscillators using a quantum computer. Our proposed quantum algorithm operates in the standard $s-sparse, oracle-based query access model. We show that a simple adaptation of our algorithm solves the random glued-trees problem in time.
  arXiv  Detail & Related papers  (2024-05-14T15:28:37Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$. We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
  arXiv  Detail & Related papers  (2024-01-17T18:59:38Z)
• Fast Quantum Algorithms for Trace Distance Estimation [8.646488471216262]
  We propose efficient quantum algorithms for estimating the trace distance within additive error $varepsilon$ between mixed quantum states of rank $r$. We show that the decision version of low-rank trace distance estimation is $mathsfBQP$-complete.
  arXiv  Detail & Related papers  (2023-01-17T10:16:14Z)
• Predicting Gibbs-State Expectation Values with Pure Thermal Shadows [1.4050836886292868]
  We propose a quantum algorithm that can predict $M$ linear functions of an arbitrary Gibbs state with only $mathcalO(logM)$ experimental measurements. We show that the algorithm can be successfully employed as a subroutine for training an eight-qubit fully connected quantum Boltzmann machine.
  arXiv  Detail & Related papers  (2022-06-10T18:00:08Z)
• Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
  We provide circuit-level implementations and resource estimates for several methods of block-encoding a dense $Ntimes N$ matrix of classical data to precision $epsilon$. We examine resource tradeoffs between the different approaches and explore implementations of two separate models of quantum random access memory (QRAM) Our results go beyond simple query complexity and provide a clear picture into the resource costs when large amounts of classical data are assumed to be accessible to quantum algorithms.
  arXiv  Detail & Related papers  (2022-06-07T18:00:01Z)
• Quantum Approximate Counting for Markov Chains and Application to Collision Counting [0.0]
  We show how to generalize the quantum approximate counting technique developed by Brassard, Hoyer and Tapp [ICALP 1998] to estimating the number of marked states of a Markov chain. This makes it possible to construct quantum approximate counting algorithms from quantum search algorithms based on the powerful "quantum walk based search" framework established by Magniez, Nayak, Roland and Santha.
  arXiv  Detail & Related papers  (2022-04-06T03:04:42Z)
• Robust Estimation for Random Graphs [47.07886511972046]
  We study the problem of robustly estimating the parameter $p$ of an ErdHos-R'enyi random graph on $n$ nodes. We give an inefficient algorithm with similar accuracy for all $gamma 1/2$, the information-theoretic limit.
  arXiv  Detail & Related papers  (2021-11-09T18:43:25Z)
• Divide-and-conquer verification method for noisy intermediate-scale quantum computation [0.0]
  noisy intermediate-scale quantum computations can be regarded as logarithmic-depth quantum circuits on a sparse quantum computing chip. We propose a method to efficiently verify such noisy intermediate-scale quantum computation.
  arXiv  Detail & Related papers  (2021-09-30T08:56:30Z)
• Quantum Algorithm for Fidelity Estimation [8.270684567157987]
  For two unknown mixed quantum states $rho$ and $sigma$ in an $N$-dimensional space, computing their fidelity $F(rho,sigma)$ is a basic problem. We propose a quantum algorithm that solves this problem in $namepoly(log (N), r, 1/varepsilon)$ time.
  arXiv  Detail & Related papers  (2021-03-16T13:57:01Z)
• Quantum algorithms for spectral sums [50.045011844765185]
  We propose new quantum algorithms for estimating spectral sums of positive semi-definite (PSD) matrices. We show how the algorithms and techniques used in this work can be applied to three problems in spectral graph theory.
  arXiv  Detail & Related papers  (2020-11-12T16:29:45Z)
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms [87.04438831673063]
  We present an efficient read-out protocol that yields the classical vector form of the generated state. Our protocol suits the case that the output state lies in the row space of the input matrix. One of our technical tools is an efficient quantum algorithm for performing the Gram-Schmidt orthonormal procedure.
  arXiv  Detail & Related papers  (2020-04-14T11:05:26Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.