Testing matrix product states
- URL: http://arxiv.org/abs/2201.01824v1
- Date: Wed, 5 Jan 2022 21:10:50 GMT
- Title: Testing matrix product states
- Authors: Mehdi Soleimanifar, John Wright
- Abstract summary: We study the problem of testing whether an unknown state $|psirangle$ is a matrix product state (MPS) in the property testing model.
MPS are a class of physically-relevant quantum states which arise in the study of quantum many-body systems.
- Score: 5.225550006603552
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Devising schemes for testing the amount of entanglement in quantum systems
has played a crucial role in quantum computing and information theory. Here, we
study the problem of testing whether an unknown state $|\psi\rangle$ is a
matrix product state (MPS) in the property testing model. MPS are a class of
physically-relevant quantum states which arise in the study of quantum
many-body systems. A quantum state $|\psi_{1,...,n}\rangle$ comprised of $n$
qudits is said to be an MPS of bond dimension $r$ if the reduced density matrix
$\psi_{1,...,k}$ has rank $r$ for each $k \in \{1,...,n\}$. When $r=1$, this
corresponds to the set of product states. For larger values of $r$, this yields
a more expressive class of quantum states, which are allowed to possess limited
amounts of entanglement. In the property testing model, one is given $m$
identical copies of $|\psi\rangle$, and the goal is to determine whether
$|\psi\rangle$ is an MPS of bond dimension $r$ or whether $|\psi\rangle$ is far
from all such states. For the case of product states, we study the product
test, a simple two-copy test previously analyzed by Harrow and Montanaro (FOCS
2010), and a key ingredient in their proof that
$\mathsf{QMA(2)}=\mathsf{QMA}(k)$ for $k \geq 2$. We give a new and simpler
analysis of the product test which achieves an optimal bound for a wide range
of parameters, answering open problems of Harrow and Montanaro (FOCS 2010) and
Montanaro and de Wolf (2016). For the case of $r\geq 2$, we give an efficient
algorithm for testing whether $|\psi\rangle$ is an MPS of bond dimension $r$
using $m = O(n r^2)$ copies, independent of the dimensions of the qudits, and
we show that $\Omega(n^{1/2})$ copies are necessary for this task. This lower
bound shows that a dependence on the number of qudits $n$ is necessary, in
sharp contrast to the case of product states where a constant number of copies
suffices.
Related papers
- Testing classical properties from quantum data [0.0]
We show that the speedup lost when restricting classical testers to samples can be recovered by testers that use quantum data.
For monotonicity testing, we give a quantum algorithm that uses $tildemathcalO(n2)$ function state copies as compared to the $2Omega(sqrtn)$ samples required classically.
We also present $mathcalO(1)$-copy testers for symmetry and triangle-freeness, comparing favorably to classical lower bounds of $Omega(n1/4)$ and $Omega(n
arXiv Detail & Related papers (2024-11-19T18:52:55Z) - Nearly tight bounds for testing tree tensor network states [0.0]
Tree tensor network states (TTNS) generalize the notion of having low Schmidt-rank to multipartite quantum states.
We study the task of testing whether an unknown pure state is a TTNS on $n$ qudits with bond dimension at most $r$.
We also study the performance of tests using measurements performed on a small number of copies at a time.
arXiv Detail & Related papers (2024-10-28T18:13:38Z) - Testing multipartite productness is easier than testing bipartite productness [0.0]
We show that $Omega(n / log n)$ copies are required (for fixed $epsilon leq frac12$)
We discuss implications for testing graph states and computing the generalised geometric measure of entanglement.
arXiv Detail & Related papers (2024-06-24T17:36:57Z) - Pseudorandom and Pseudoentangled States from Subset States [49.74460522523316]
A subset state with respect to $S$, a subset of the computational basis, is [ frac1sqrt|S|sum_iin S |irangle.
We show that for any fixed subset size $|S|=s$ such that $s = 2n/omega(mathrmpoly(n))$ and $s=omega(mathrmpoly(n))$, a random subset state is information-theoretically indistinguishable from a Haar random state even provided
arXiv Detail & Related papers (2023-12-23T15:52:46Z) - Learning Distributions over Quantum Measurement Outcomes [4.467248776406005]
Shadow tomography for quantum states provides a sample efficient approach for predicting the properties of quantum systems.
We develop an online shadow tomography procedure that solves this problem with high success probability.
arXiv Detail & Related papers (2022-09-07T09:08:58Z) - Beyond the Berry Phase: Extrinsic Geometry of Quantum States [77.34726150561087]
We show how all properties of a quantum manifold of states are fully described by a gauge-invariant Bargmann.
We show how our results have immediate applications to the modern theory of polarization.
arXiv Detail & Related papers (2022-05-30T18:01:34Z) - Uncertainties in Quantum Measurements: A Quantum Tomography [52.77024349608834]
The observables associated with a quantum system $S$ form a non-commutative algebra $mathcal A_S$.
It is assumed that a density matrix $rho$ can be determined from the expectation values of observables.
Abelian algebras do not have inner automorphisms, so the measurement apparatus can determine mean values of observables.
arXiv Detail & Related papers (2021-12-14T16:29:53Z) - Quantum double aspects of surface code models [77.34726150561087]
We revisit the Kitaev model for fault tolerant quantum computing on a square lattice with underlying quantum double $D(G)$ symmetry.
We show how our constructions generalise to $D(H)$ models based on a finite-dimensional Hopf algebra $H$.
arXiv Detail & Related papers (2021-06-25T17:03:38Z) - 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)
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.