Resource-efficient algorithm for estimating the trace of quantum state powers

• URL: http://arxiv.org/abs/2408.00314v2
• Date: Tue, 18 Feb 2025 08:33:10 GMT
• Title: Resource-efficient algorithm for estimating the trace of quantum state powers
• Authors: Myeongjin Shin, Junseo Lee, Seungwoo Lee, Kabgyun Jeong,
• Abstract summary: Estimating the trace of quantum state powers, $textTr(rhok)$, for $k$ identical quantum states is a fundamental task.<n>We introduce an algorithm that requires only $mathcalO(tilder)$ qubits and $mathcalO(tilder)$ multi-qubit gates.<n>We extend our algorithm to the estimation of $textTr(rhok)$ for arbitrary observables and $textTr(rhok)
• Score: 1.5133368155322298
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Estimating the trace of quantum state powers, $\text{Tr}(\rho^k)$, for $k$ identical quantum states is a fundamental task with numerous applications in quantum information processing, including nonlinear function estimation of quantum states and entanglement detection. On near-term quantum devices, reducing the required quantum circuit depth, the number of multi-qubit quantum operations, and the copies of the quantum state needed for such computations is crucial. In this work, inspired by the Newton-Girard method, we significantly improve upon existing results by introducing an algorithm that requires only $\mathcal{O}(\tilde{r})$ qubits and $\mathcal{O}(\tilde{r})$ multi-qubit gates, where $\tilde{r} = \min\left\{\text{rank}(\rho), \left\lfloor\ln\left({2k}/{\epsilon}\right)\right\rfloor\right\}$. Furthermore, we prove that estimating $\{\text{Tr}(\rho^i)\}_{i=1}^{\tilde{r}}$ is sufficient to approximate $\text{Tr}(\rho^k)$ even for large integers $k > \tilde{r}$. This leads to a rank-dependent complexity for solving the problem, providing an efficient algorithm for low-rank quantum states while also improving existing methods when the rank is unknown or when the state is not low-rank. Building upon these advantages, we extend our algorithm to the estimation of $\text{Tr}(M\rho^k)$ for arbitrary observables and $\text{Tr}(\rho^k \sigma^l)$ for multiple quantum states.

Related papers

• Quantum oracles for the finite element method [45.200826131319815]
  This study examines the quantum routines required for the implementation of oracles used in the block-encoding of the $N times N stiffness and mass matrices. We show how to construct the necessary oracles, which require the calculation of element geometry, square root and the implementation of conditional operations.
  arXiv  Detail & Related papers  (2025-04-28T14:28:31Z)
• Distributed quantum algorithm for divergence estimation and beyond [16.651306526783564]
  We propose a distributed quantum algorithm framework to compute $rm Tr(f(A)g(B))$ within an additive error $varepsilon$. This framework holds broad applicability across a range of distributed quantum computing tasks.
  arXiv  Detail & Related papers  (2025-03-12T14:28:22Z)
• Quantum Algorithms for Non-smooth Non-convex Optimization [30.576546266390714]
  This paper considers the problem for finding the $(,epsilon)$-Goldstein stationary point of Lipschitz continuous objective. We construct a zeroth-order quantum estimator for the surrogate oracle function.
  arXiv  Detail & Related papers  (2024-10-21T16:52:26Z)
• 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)
• Quantum algorithms for Hopcroft's problem [45.45456673484445]
  We study quantum algorithms for Hopcroft's problem which is a fundamental problem in computational geometry. The classical complexity of this problem is well-studied, with the best known algorithm running in $O(n4/3)$ time. Our results are two different quantum algorithms with time complexity $widetilde O(n5/6)$.
  arXiv  Detail & Related papers  (2024-05-02T10:29:06Z)
• Time-Efficient Quantum Entropy Estimator via Samplizer [7.319050391449301]
  Estimating the entropy of a quantum state is a basic problem in quantum information. We introduce a time-efficient quantum approach to estimating the von Neumann entropy $S(rho)$ and R'enyi entropy $S_alpha(rho)$ of an $N$-dimensional quantum state $rho.
  arXiv  Detail & Related papers  (2024-01-18T12:50:20Z)
• Spacetime-Efficient Low-Depth Quantum State Preparation with Applications [93.56766264306764]
  We show that a novel deterministic method for preparing arbitrary quantum states requires fewer quantum resources than previous methods. We highlight several applications where this ability would be useful, including quantum machine learning, Hamiltonian simulation, and solving linear systems of equations.
  arXiv  Detail & Related papers  (2023-03-03T18:23:20Z)
• 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.