Randomized truncation of quantum states

• URL: http://arxiv.org/abs/2510.08518v1
• Date: Thu, 09 Oct 2025 17:47:07 GMT
• Title: Randomized truncation of quantum states
• Authors: Aram W. Harrow, Angus Lowe, Freek Witteveen,
• Abstract summary: We give efficient algorithms for finding mixtures of sparse states that optimally approximate a given pure state in either trace distance or robustness.<n>These algorithms also yield descriptions of efficiently samplable ensembles of sparse, or less-entangled, states that correspond to these optimal mixed approximations.
• Score: 0.16567880228735354
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: A fundamental task in quantum information is to approximate a pure quantum state in terms of sparse states or, for a bipartite system, states of bounded Schmidt rank. The optimal deterministic approximation in each case is straightforward, and maximizes the fidelity: keep the largest entries or singular values. On the other hand, random mixtures of sparse states can achieve quadratically improved trace distances, and yield nontrivial bounds on other distance measures like the robustness. In this work, we give efficient algorithms for finding mixtures of sparse states that optimally approximate a given pure state in either trace distance or robustness. These algorithms also yield descriptions of efficiently samplable ensembles of sparse, or less-entangled, states that correspond to these optimal mixed approximations. This can be used for the truncation step of algorithms for matrix product states, improving their accuracy while using no extra memory, and we demonstrate this improvement numerically. Our proofs use basic facts about convex optimization and zero-sum games, as well as rigorous guarantees for computing maximum-entropy distributions.

Related papers

• Efficient algorithm for fidelity estimation of two quantum states [0.0]
  We propose an efficient algorithm for the fidelity estimation, based primarily on the density matrix exponentiation and interferometeric scheme for mixed states.<n>Our 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.
  arXiv  Detail & Related papers  (2025-11-17T13:54:47Z)
• Rigorous Maximum Likelihood Estimation for Quantum States [2.5782420501870296]
  Existing quantum state tomography avoids rigorous termination of limited scalability due to their high computation and memory demands.<n>In this paper, we address these limitations by reforming a matrix by a factor.<n>We show that our method can demonstrate a laptop-of-the-art solution to state-of-the-art problems in under 5 hours.
  arXiv  Detail & Related papers  (2025-06-19T23:18:50Z)
• Mitigating sloppiness in joint estimation of successive squeezing parameters [2.0249250133493195]
  Two successive squeezing operations with the same phase are applied to a field mode.<n> reliably estimating the amplitude of each is impossible because the output state depends solely on their sum.<n>We analyze in detail the effects of a phase-shift scrambling transformation, optimized to reduce sloppiness and maximize the overall estimation precision.
  arXiv  Detail & Related papers  (2025-06-18T17:08:18Z)
• Solving quadratic binary optimization problems using quantum SDP methods: Non-asymptotic running time analysis [1.9081120388919084]
  Quantum computers can solve semidefinite programs (SDPs) using resources that scale better than state-of-the-art classical methods.<n>We present an analysis of the non-asymptotic resource requirements of a quantum SDP solver.
  arXiv  Detail & Related papers  (2025-02-21T12:54:05Z)
• Algorithm for evaluating distance-based entanglement measures [0.0]
  We propose an efficient algorithm for evaluating distance-based entanglement measures. Our approach builds on Gilbert's algorithm for convex optimization, providing a reliable upper bound on the entanglement of a given arbitrary state.
  arXiv  Detail & Related papers  (2023-08-04T13:42:55Z)
• Linearized Wasserstein dimensionality reduction with approximation guarantees [65.16758672591365]
  LOT Wassmap is a computationally feasible algorithm to uncover low-dimensional structures in the Wasserstein space. We show that LOT Wassmap attains correct embeddings and that the quality improves with increased sample size. We also show how LOT Wassmap significantly reduces the computational cost when compared to algorithms that depend on pairwise distance computations.
  arXiv  Detail & Related papers  (2023-02-14T22:12:16Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  Efficient computation of the optimal transport distance between two distributions serves as an algorithm that empowers various applications. This paper develops a scalable first-order optimization-based method that computes optimal transport to within $varepsilon$ additive accuracy.
  arXiv  Detail & Related papers  (2023-01-30T15:46:39Z)
• Efficient and Flexible Sublabel-Accurate Energy Minimization [62.50191141358778]
  We address the problem of minimizing a class of energy functions consisting of data and smoothness terms. Existing continuous optimization methods can find sublabel-accurate solutions, but they are not efficient for large label spaces. We propose an efficient sublabel-accurate method that utilizes the best properties of both continuous and discrete models.
  arXiv  Detail & Related papers  (2022-06-20T06:58:55Z)
• Improved Quantum Algorithms for Fidelity Estimation [77.34726150561087]
  We develop new and efficient quantum algorithms for fidelity estimation with provable performance guarantees. Our algorithms use advanced quantum linear algebra techniques, such as the quantum singular value transformation. We prove that fidelity estimation to any non-trivial constant additive accuracy is hard in general.
  arXiv  Detail & Related papers  (2022-03-30T02:02:16Z)
• Near-optimal estimation of smooth transport maps with kernel sums-of-squares [81.02564078640275]
  Under smoothness conditions, the squared Wasserstein distance between two distributions could be efficiently computed with appealing statistical error upper bounds. The object of interest for applications such as generative modeling is the underlying optimal transport map. We propose the first tractable algorithm for which the statistical $L2$ error on the maps nearly matches the existing minimax lower-bounds for smooth map estimation.
  arXiv  Detail & Related papers  (2021-12-03T13:45:36Z)
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
  It is essential to theoretically guarantee that algorithms provide small objective residual with high probability. Existing methods for non-smooth convex optimization have complexity bounds with dependence on confidence level. We propose novel stepsize rules for two methods with gradient clipping.
  arXiv  Detail & Related papers  (2021-06-10T17:54:21Z)
• Variational Quantum Algorithms for Trace Distance and Fidelity Estimation [7.247285982078057]
  We introduce hybrid quantum-classical algorithms for two distance measures on near-term quantum devices. First, we introduce the Variational Trace Distance Estimation (VTDE) algorithm. Second, we introduce the Variational Fidelity Estimation (VFE) algorithm.
  arXiv  Detail & Related papers  (2020-12-10T15:56:58Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  We investigate the problem of best-policy identification in discounted Markov Decision (MDPs) when the learner has access to a generative model. The advantages of state-of-the-art algorithms are discussed and illustrated.
  arXiv  Detail & Related papers  (2020-09-28T15:22:24Z)

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.