Computationally Efficient Quantum Expectation with Extended Bell
Measurements
- URL: http://arxiv.org/abs/2110.09735v2
- Date: Fri, 8 Apr 2022 08:04:35 GMT
- Title: Computationally Efficient Quantum Expectation with Extended Bell
Measurements
- Authors: Ruho Kondo, Yuki Sato, Satoshi Koide, Seiji Kajita, Hideki Takamatsu
- Abstract summary: We propose a method for evaluating an expectation value of an arbitrary observable $Ainmathbb C2ntimes 2n$ through na"ive Pauli measurements.
This analytical method quickly assembles the $4n$ matrix elements into at most $2n+1$ groups for simultaneous measurements.
- Score: 7.620967781722716
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Evaluating an expectation value of an arbitrary observable $A\in{\mathbb
C}^{2^n\times 2^n}$ through na\"ive Pauli measurements requires a large number
of terms to be evaluated. We approach this issue using a method based on Bell
measurement, which we refer to as the extended Bell measurement method. This
analytical method quickly assembles the $4^n$ matrix elements into at most
$2^{n+1}$ groups for simultaneous measurements in $O(nd)$ time, where $d$ is
the number of non-zero elements of $A$. The number of groups is particularly
small when $A$ is a band matrix. When the bandwidth of $A$ is $k=O(n^c)$, the
number of groups for simultaneous measurement reduces to $O(n^{c+1})$. In
addition, when non-zero elements densely fill the band, the variance is
$O((n^{c+1}/2^n)\,{\rm tr}(A^2))$, which is small compared with the variances
of existing methods. The proposed method requires a few additional gates for
each measurement, namely one Hadamard gate, one phase gate and at most $n-1$
CNOT gates. Experimental results on an IBM-Q system show the computational
efficiency and scalability of the proposed scheme, compared with existing
state-of-the-art approaches. Code is available at
https://github.com/ToyotaCRDL/extended-bell-measurements.
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) - Quantum (Inspired) $D^2$-sampling with Applications [0.138120109831448]
We show a quantum implementation of $k$-means++ that runs in time $tildeO(zeta2 k2)$.
It can be shown through a robust approximation analysis of $k$-means++ that the quantum version preserves its $O(logk)$ approximation guarantee.
This results in a fast quantum-inspired classical implementation of $k$-means++, which we call QI-$k$-means++, with a running time $O(Nd) + tildeO(zeta
arXiv Detail & Related papers (2024-05-22T05:13:28Z) - Identification of Mixtures of Discrete Product Distributions in
Near-Optimal Sample and Time Complexity [6.812247730094931]
We show, for any $ngeq 2k-1$, how to achieve sample complexity and run-time complexity $(1/zeta)O(k)$.
We also extend the known lower bound of $eOmega(k)$ to match our upper bound across a broad range of $zeta$.
arXiv Detail & Related papers (2023-09-25T09:50:15Z) - Do you know what q-means? [50.045011844765185]
Clustering is one of the most important tools for analysis of large datasets.
We present an improved version of the "$q$-means" algorithm for clustering.
We also present a "dequantized" algorithm for $varepsilon which runs in $Obig(frack2varepsilon2(sqrtkd + log(Nd))big.
arXiv Detail & Related papers (2023-08-18T17:52:12Z) - A Quantum Approximation Scheme for k-Means [0.16317061277457]
We give a quantum approximation scheme for the classical $k$-means clustering problem in the QRAM model.
Our quantum algorithm runs in time $tildeO left( 2tildeO(frackvarepsilon) eta2 dright)$.
Unlike previous works on unsupervised learning, our quantum algorithm does not require quantum linear algebra subroutines.
arXiv Detail & Related papers (2023-08-16T06:46:37Z) - Quantum Metropolis-Hastings algorithm with the target distribution
calculated by quantum Monte Carlo integration [0.0]
Quantum algorithms for MCMC have been proposed, yielding the quadratic speedup with respect to the spectral gap $Delta$ compered to classical counterparts.
We consider not only state generation but also finding a credible interval for a parameter, a common task in Bayesian inference.
In the proposed method for credible interval calculation, the number of queries to the quantum circuit to compute $ell$ scales on $Delta$, the required accuracy $epsilon$ and the standard deviation $sigma$ of $ell$ as $tildeO(sigma/epsilon
arXiv Detail & Related papers (2023-03-10T01:05:16Z) - Reward-Mixing MDPs with a Few Latent Contexts are Learnable [75.17357040707347]
We consider episodic reinforcement learning in reward-mixing Markov decision processes (RMMDPs)
Our goal is to learn a near-optimal policy that nearly maximizes the $H$ time-step cumulative rewards in such a model.
arXiv Detail & Related papers (2022-10-05T22:52:00Z) - TURF: A Two-factor, Universal, Robust, Fast Distribution Learning
Algorithm [64.13217062232874]
One of its most powerful and successful modalities approximates every distribution to an $ell$ distance essentially at most a constant times larger than its closest $t$-piece degree-$d_$.
We provide a method that estimates this number near-optimally, hence helps approach the best possible approximation.
arXiv Detail & Related papers (2022-02-15T03:49:28Z) - How to simulate quantum measurement without computing marginals [3.222802562733787]
We describe and analyze algorithms for classically computation measurement of an $n$-qubit quantum state $psi$ in the standard basis.
Our algorithms reduce the sampling task to computing poly(n)$ amplitudes of $n$-qubit states.
arXiv Detail & Related papers (2021-12-15T21:44:05Z) - Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean
Estimation [58.24280149662003]
We study the problem of list-decodable mean estimation, where an adversary can corrupt a majority of the dataset.
We develop new algorithms for list-decodable mean estimation, achieving nearly-optimal statistical guarantees.
arXiv Detail & Related papers (2021-06-16T03:34:14Z) - A Randomized Algorithm to Reduce the Support of Discrete Measures [79.55586575988292]
Given a discrete probability measure supported on $N$ atoms and a set of $n$ real-valued functions, there exists a probability measure that is supported on a subset of $n+1$ of the original $N$ atoms.
We give a simple geometric characterization of barycenters via negative cones and derive a randomized algorithm that computes this new measure by "greedy geometric sampling"
We then study its properties, and benchmark it on synthetic and real-world data to show that it can be very beneficial in the $Ngg n$ regime.
arXiv Detail & Related papers (2020-06-02T16:38:36Z)
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.