Time-Efficient Quantum Entropy Estimator via Samplizer
- URL: http://arxiv.org/abs/2401.09947v1
- Date: Thu, 18 Jan 2024 12:50:20 GMT
- Title: Time-Efficient Quantum Entropy Estimator via Samplizer
- Authors: Qisheng Wang and Zhicheng Zhang
- Abstract summary: 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)$.
- Score: 8.646488471216262
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Entropy is a measure of the randomness of a system. Estimating the entropy of
a quantum state is a basic problem in quantum information. In this paper, 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$, given access to independent samples of $\rho$.
Specifically, we provide the following quantum estimators.
1. A quantum estimator for $S(\rho)$ with time complexity $\widetilde
O(N^2)$, improving the prior best time complexity $\widetilde O (N^6)$ by
Acharya, Issa, Shende, and Wagner (2020) and Bavarian, Mehraba, and Wright
(2016).
2. A quantum estimator for $S_\alpha(\rho)$ with time complexity $\widetilde
O(N^{4/\alpha-2})$ for $0 < \alpha < 1$ and $\widetilde O(N^{4-2/\alpha})$ for
$\alpha > 1$, improving the prior best time complexity $\widetilde
O(N^{6/\alpha})$ for $0 < \alpha < 1$ and $\widetilde O(N^6)$ for $\alpha > 1$
by Acharya, Issa, Shende, and Wagner (2020), though at a cost of a slightly
larger sample complexity.
Moreover, these estimators are naturally extensible to the low-rank case.
Technically, our method is quite different from the previous ones that are
based on weak Schur sampling and Young diagrams. At the heart of our
construction, is a novel tool called samplizer, which can "samplize" a quantum
query algorithm to a quantum algorithm with similar behavior using only samples
of quantum states; this suggests a unified framework for estimating quantum
entropies. Specifically, when a quantum oracle $U$ block-encodes a mixed
quantum state $\rho$, any quantum query algorithm using $Q$ queries to $U$ can
be samplized to a $\delta$-close (in the diamond norm) quantum algorithm using
$\widetilde \Theta(Q^2/\delta)$ samples of $\rho$. Moreover, this samplization
is proven to be optimal, up to a polylogarithmic factor.
Related papers
- Measuring quantum relative entropy with finite-size effect [53.64687146666141]
We study the estimation of relative entropy $D(rho|sigma)$ when $sigma$ is known.
Our estimator attains the Cram'er-Rao type bound when the dimension $d$ is fixed.
arXiv Detail & Related papers (2024-06-25T06:07:20Z) - Circuit Complexity of Sparse Quantum State Preparation [0.0]
We show that any $n$-qubit $d$-sparse quantum state can be prepared by a quantum circuit of size $O(fracdnlog d)$ and depth $Theta(log dn)$ using at most $O(fracndlog d )$ ancillary qubits.
We also establish the lower bound $Omega(fracdnlog(n + m) + log d + n)$ on the circuit size with $m$ ancillary qubits available.
arXiv Detail & Related papers (2024-06-23T15:28:20Z) - 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) - On the exact quantum query complexity of $\text{MOD}_m^n$ and
$\text{EXACT}_{k,l}^n$ [0.0]
We present an exact quantum algorithm for computing $textMOD_mn$.
We show exact quantum query complexity of a broad class of symmetric functions that map $0,1n$ to a finite set $X$ is less than $n$.
arXiv Detail & Related papers (2023-03-20T08:17:32Z) - 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) - A Quantum Algorithm Framework for Discrete Probability Distributions with Applications to Rényi Entropy Estimation [13.810917492304565]
We propose a unified quantum algorithm framework for estimating properties of discrete probability distributions.
Our framework estimates $alpha$-R'enyi entropy $H_alpha(p)$ to within additive error $epsilon$ with probability at least $2/3$.
arXiv Detail & Related papers (2022-12-03T08:01:55Z) - 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 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 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) - Quantum Coupon Collector [62.58209964224025]
We study how efficiently a $k$-element set $Ssubseteq[n]$ can be learned from a uniform superposition $|Srangle of its elements.
We give tight bounds on the number of quantum samples needed for every $k$ and $n$, and we give efficient quantum learning algorithms.
arXiv Detail & Related papers (2020-02-18T16:14:55Z)
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.