An Online Algorithm for Maximum-Likelihood Quantum State Tomography

• URL: http://arxiv.org/abs/2012.15498v1
• Date: Thu, 31 Dec 2020 08:21:50 GMT
• Title: An Online Algorithm for Maximum-Likelihood Quantum State Tomography
• Authors: Chien-Ming Lin, Yu-Min Hsu, Yen-Huan Li
• Abstract summary: We propose the first online algorithm for maximum-likelihood quantum state tomography. The expected numerical error of the algorithm is $O(sqrt ( 1 / T ) D log D )$, where $T$ denotes the number of iterations.
• Score: 6.261444979025642
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We propose, to the best of our knowledge, the first online algorithm for maximum-likelihood quantum state tomography. Suppose the quantum state to be estimated corresponds to a \( D \)-by-\( D \) density matrix. The per-iteration computational complexity of the algorithm is \( O ( D ^ 3 ) \), independent of the data size. The expected numerical error of the algorithm is $O(\sqrt{ ( 1 / T ) D \log D })$, where $T$ denotes the number of iterations. The algorithm can be viewed as a quantum extension of Soft-Bayes, a recent algorithm for online portfolio selection (Orseau et al. Soft-Bayes: Prod for mixtures of experts with log-loss. \textit{Int. Conf. Algorithmic Learning Theory}. 2017).

Related papers

• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
  arXiv  Detail & Related papers  (2024-08-14T19:04:13Z)
• Generalized quantum Arimoto-Blahut algorithm and its application to quantum information bottleneck [55.22418739014892]
  We generalize the quantum Arimoto-Blahut algorithm by Ramakrishnan et al. We apply our algorithm to the quantum information bottleneck with three quantum systems. Our numerical analysis shows that our algorithm is better than their algorithm.
  arXiv  Detail & Related papers  (2023-11-19T00:06:11Z)
• A square-root speedup for finding the smallest eigenvalue [0.6597195879147555]
  We describe a quantum algorithm for finding the smallest eigenvalue of a Hermitian matrix. This algorithm combines Quantum Phase Estimation and Quantum Amplitude Estimation to achieve a quadratic speedup. We also provide a similar algorithm with the same runtime that allows us to prepare a quantum state lying mostly in the matrix's low-energy subspace.
  arXiv  Detail & Related papers  (2023-11-07T22:52:56Z)
• Efficient quantum linear solver algorithm with detailed running costs [0.0]
  We introduce a quantum linear solver algorithm combining ideasdiabatic quantum computing with filtering techniques based on quantum signal processing. Our protocol reduces the cost of quantum linear solvers over state-of-the-art close to an order of magnitude for early implementations.
  arXiv  Detail & Related papers  (2023-05-19T00:07:32Z)
• Private estimation algorithms for stochastic block models and mixture models [63.07482515700984]
  General tools for designing efficient private estimation algorithms. First efficient $(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery.
  arXiv  Detail & Related papers  (2023-01-11T09:12:28Z)
• Manifold Learning for Dimensionality Reduction: Quantum Isomap algorithm [15.622577797491788]
  Isomap algorithm is widely used in neuroimaging, spectral analysis and other fields. We propose the quantum Isomap algorithm, which consists of two sub-algorithms. The time complexity of quantum Isomap algorithm is $O(dNpolylogN)$.
  arXiv  Detail & Related papers  (2022-12-07T12:29:41Z)
• Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
  Quantum algorithms for topological data analysis seem to provide an exponential advantage over the best classical approach. We show that the central task of TDA -- estimating Betti numbers -- is intractable even for quantum computers. We argue that an exponential quantum advantage can be recovered if the input data is given as a specification of simplices.
  arXiv  Detail & Related papers  (2022-09-28T17:53:25Z)
• 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)
• Maximum-Likelihood Quantum State Tomography by Cover's Method with Non-Asymptotic Analysis [10.758021887982782]
  We propose an iterative algorithm that computes the maximum-likelihood estimate in quantum state tomography. The per-iteration computational complexity of the algorithm is $O ( D 3 + N D 2 )$, where $N$ denotes the number of measurement outcomes.
  arXiv  Detail & Related papers  (2021-10-02T08:03:13Z)
• Low depth algorithms for quantum amplitude estimation [6.148105657815341]
  We design and analyze two new low depth algorithms for amplitude estimation (AE) These algorithms bring quantum speedups for Monte Carlo methods closer to realization.
  arXiv  Detail & Related papers  (2020-12-06T18:39:20Z)
• 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)

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.