Distributed inner product estimation with limited quantum communication

• URL: http://arxiv.org/abs/2410.12684v1
• Date: Wed, 16 Oct 2024 15:46:59 GMT
• Title: Distributed inner product estimation with limited quantum communication
• Authors: Srinivasan Arunachalam, Louis Schatzki,
• Abstract summary: We consider the task of distributed inner product estimation when allowed limited quantum communication. We show that $k=Theta(sqrt2n-q)$ copies are essentially necessary and sufficient for this task. We also consider estimating $|langle psi|M|phirangle|2$, for arbitrary Hermitian $M$.
• Score: 3.729242965449096
• License:
• Abstract: We consider the task of distributed inner product estimation when allowed limited quantum communication. Here, Alice and Bob are given $k$ copies of an unknown $n$-qubit quantum states $\vert \psi \rangle,\vert \phi \rangle$ respectively. They are allowed to communicate $q$ qubits and unlimited classical communication, and their goal is to estimate $|\langle \psi|\phi\rangle|^2$ up to constant accuracy. We show that $k=\Theta(\sqrt{2^{n-q}})$ copies are essentially necessary and sufficient for this task (extending the work of Anshu, Landau and Liu (STOC'22) who considered the case when $q=0$). Additionally, we consider estimating $|\langle \psi|M|\phi\rangle|^2$, for arbitrary Hermitian $M$. For this task we show that certain norms on $M$ characterize the sample complexity of estimating $|\langle \psi|M|\phi\rangle|^2$ when using only classical~communication.

Related papers

• On estimating the trace of quantum state powers [2.637436382971936]
  We investigate the computational complexity of estimating the trace of quantum state powers $texttr(rhoq)$ for an $n$-qubit mixed quantum state $rho$. Our speedup is achieved by introducing efficiently computable uniform approximations of positive power functions into quantum singular value transformation.
  arXiv  Detail & Related papers  (2024-10-17T13:57:13Z)
• On the sample complexity of purity and inner product estimation [8.94496959777308]
  We study the sample complexity of the tasks quantum purity estimation and quantum inner product estimation. In purity estimation, we are to estimate $tr(rho2)$ of an unknown quantum state $rho$ to additive error $epsilon$. For quantum inner product estimation, Alice and Bob are to estimate $tr(rhosigma)$ to additive error $epsilon$ given copies of unknown quantum state $rho$ and $sigma$.
  arXiv  Detail & Related papers  (2024-10-16T16:17:21Z)
• Optimal tradeoffs for estimating Pauli observables [13.070874080455862]
  We revisit the problem of Pauli shadow tomography: given copies of an unknown $n$-qubit quantum state $rho$, estimate $texttr(Prho)$ for some set of Pauli operators $P$ to within additive error $epsilon$. We show any protocol that makes $textpoly(n)$-copy measurements must make $Omega (1/epsilon4)$ measurements. The protocols we propose can also estimate the actual values $texttr(Prho)$, rather than just their absolute values
  arXiv  Detail & Related papers  (2024-04-29T20:57:05Z)
• Dimension Independent Disentanglers from Unentanglement and Applications [55.86191108738564]
  We construct a dimension-independent k-partite disentangler (like) channel from bipartite unentangled input. We show that to capture NEXP, it suffices to have unentangled proofs of the form $| psi rangle = sqrta | sqrt1-a | psi_+ rangle where $| psi_+ rangle has non-negative amplitudes.
  arXiv  Detail & Related papers  (2024-02-23T12:22:03Z)
• Enlarging the notion of additivity of resource quantifiers [62.997667081978825]
  Given a quantum state $varrho$ and a quantifier $cal E(varrho), it is a hard task to determine $cal E(varrhootimes N)$. We show that the one shot distillable entanglement of certain spherically symmetric states can be quantitatively approximated by such an augmented additivity.
  arXiv  Detail & Related papers  (2022-07-31T00:23:10Z)
• Divide-and-conquer verification method for noisy intermediate-scale quantum computation [0.0]
  noisy intermediate-scale quantum computations can be regarded as logarithmic-depth quantum circuits on a sparse quantum computing chip. We propose a method to efficiently verify such noisy intermediate-scale quantum computation.
  arXiv  Detail & Related papers  (2021-09-30T08:56:30Z)
• The Quantum Supremacy Tsirelson Inequality [0.22843885788439797]
  For a quantum circuit $C$ on $n$ qubits and a sample $z in 0,1n$, the benchmark involves computing $|langle z|C|0n rangle|2$. We show that for any $varepsilon ge frac1mathrmpoly(n)$, outputting a sample $z$ is the optimal 1-query for $|langle z|C|0nrangle|2$ on average.
  arXiv  Detail & Related papers  (2020-08-20T01:04:32Z)
• Locally Private Hypothesis Selection [96.06118559817057]
  We output a distribution from $mathcalQ$ whose total variation distance to $p$ is comparable to the best such distribution. We show that the constraint of local differential privacy incurs an exponential increase in cost. Our algorithms result in exponential improvements on the round complexity of previous methods.
  arXiv  Detail & Related papers  (2020-02-21T18:30:48Z)
• 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)
• Tight Quantum Lower Bound for Approximate Counting with Quantum States [49.6558487240078]
  We prove tight lower bounds for the following variant of the counting problem considered by Aaronson, Kothari, Kretschmer, and Thaler ( 2020) The task is to distinguish whether an input set $xsubseteq [n]$ has size either $k$ or $k'=(1+varepsilon)k$.
  arXiv  Detail & Related papers  (2020-02-17T10:53:50Z)
• Communication Cost of Quantum Processes [49.281159740373326]
  A common scenario in distributed computing involves a client who asks a server to perform a computation on a remote computer. An important problem is to determine the minimum amount of communication needed to specify the desired computation. We analyze the total amount of (classical and quantum) communication needed by a server in order to accurately execute a quantum process chosen by a client.
  arXiv  Detail & Related papers  (2020-02-17T08:51:42Z)

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.