Near optimal quantum algorithm for estimating Shannon entropy

• URL: http://arxiv.org/abs/2509.07452v1
• Date: Tue, 09 Sep 2025 07:24:29 GMT
• Title: Near optimal quantum algorithm for estimating Shannon entropy
• Authors: Myeongjin Shin, Kabgyun Jeong,
• Abstract summary: We present a near-optimal quantum algorithm, up to logarithmic factors, for estimating the Shannon entropy in the quantum probability oracle model.<n>Our results show that the tight query complexity for estimating the Shannon entropy within $epsilon$-additive error is given by $tildeThetaleft(tfracsqrtnepsilonright)$.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We present a near-optimal quantum algorithm, up to logarithmic factors, for estimating the Shannon entropy in the quantum probability oracle model. Our approach combines the singular value separation algorithm with quantum amplitude amplification, followed by the application of quantum singular value transformation. On the lower bound side, we construct probability distributions encoded via Hamming weights in the oracle, establishing a tight query lower bound up to logarithmic factors. Consequently, our results show that the tight query complexity for estimating the Shannon entropy within $\epsilon$-additive error is given by $\tilde{\Theta}\left(\tfrac{\sqrt{n}}{\epsilon}\right)$.

Related papers

• On Estimating the Quantum Tsallis Relative Entropy [10.925697720070426]
  The relative entropy between quantum states quantifies their distinguishability.<n>We show that for any constant $alpha in (0, 1)$, the $alpha$-Tsallis relative entropy between two quantum states of rank $r$ can be estimated.<n>We also show that the quantum state distinguishability problems with respect to the quantum $alpha$-Tsallis relative entropy and quantum Hellinger distance are $mathsfQSZK$-complete in a certain regime.
  arXiv  Detail & Related papers  (2025-10-01T10:38:59Z)
• Quantum Annealing Algorithms for Estimating Ising Partition Functions [2.8311048083168657]
  Estimating partition functions of Ising spin glasses is crucial in statistical physics, optimization, and machine learning.<n>This work bridges quantum dynamics with computational complexity, offering a practical pathway to quantum advantage in spin glass thermodynamics.
  arXiv  Detail & Related papers  (2025-04-30T14:09:40Z)
• Reducing the sampling complexity of energy estimation in quantum many-body systems using empirical variance information [45.18582668677648]
  We consider the problem of estimating the energy of a quantum state preparation for a given Hamiltonian in Pauli decomposition.<n>We construct an adaptive estimator using the state's actual variance.
  arXiv  Detail & Related papers  (2025-02-03T19:00:01Z)
• Optimizing random local Hamiltonians by dissipation [44.99833362998488]
  We prove that a simplified quantum Gibbs sampling algorithm achieves a $Omega(frac1k)$-fraction approximation of the optimum. Our results suggest that finding low-energy states for sparsified (quasi)local spin and fermionic models is quantumly easy but classically nontrivial.
  arXiv  Detail & Related papers  (2024-11-04T20:21:16Z)
• Semidefinite optimization of the quantum relative entropy of channels [3.9134031118910264]
  This paper introduces a method for calculating the quantum relative entropy of channels. It provides efficiently computable upper and lower bounds that sandwich the true value with any desired precision.
  arXiv  Detail & Related papers  (2024-10-21T18:00:01Z)
• Stochastic Quantum Sampling for Non-Logconcave Distributions and Estimating Partition Functions [13.16814860487575]
  We present quantum algorithms for sampling from nonlogconcave probability distributions. $f$ can be written as a finite sum $f(x):= frac1Nsum_k=1N f_k(x)$.
  arXiv  Detail & Related papers  (2023-10-17T17:55:32Z)
• Algorithmic Cluster Expansions for Quantum Problems [0.0]
  We establish a general framework for developing approximation algorithms for a class of counting problems. We apply our framework to approximating probability amplitudes of a class of quantum circuits close to the identity. We show that our algorithmic condition is almost optimal for expectation values and optimal for thermal expectation values in the sense of zero freeness.
  arXiv  Detail & Related papers  (2023-06-15T09:11:48Z)
• Analyzing Prospects for Quantum Advantage in Topological Data Analysis [35.423446067065576]
  We analyze and optimize an improved quantum algorithm for topological data analysis. We show that super-quadratic quantum speedups are only possible when targeting a multiplicative error approximation. We argue that quantum circuits with tens of billions of Toffoli can solve seemingly classically intractable instances.
  arXiv  Detail & Related papers  (2022-09-27T17:56:15Z)
• 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)
• Tight Exponential Analysis for Smoothing the Max-Relative Entropy and for Quantum Privacy Amplification [56.61325554836984]
  The max-relative entropy together with its smoothed version is a basic tool in quantum information theory. We derive the exact exponent for the decay of the small modification of the quantum state in smoothing the max-relative entropy based on purified distance.
  arXiv  Detail & Related papers  (2021-11-01T16:35:41Z)
• Quantum Sub-Gaussian Mean Estimator [0.0]
  We present a new quantum algorithm for estimating the mean of a real-valued random variable. Our estimator achieves a nearly-optimal quadratic speedup over the number of classical i.i.d. samples.
  arXiv  Detail & Related papers  (2021-08-27T08:34:26Z)
• Bosonic field digitization for quantum computers [62.997667081978825]
  We address the representation of lattice bosonic fields in a discretized field amplitude basis. We develop methods to predict error scaling and present efficient qubit implementation strategies.
  arXiv  Detail & Related papers  (2021-08-24T15:30:04Z)
• Boundaries of quantum supremacy via random circuit sampling [69.16452769334367]
  Google's recent quantum supremacy experiment heralded a transition point where quantum computing performed a computational task, random circuit sampling. We examine the constraints of the observed quantum runtime advantage in a larger number of qubits and gates.
  arXiv  Detail & Related papers  (2020-05-05T20:11:53Z)

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.