Dimension Independent Disentanglers from Unentanglement and Applications

• URL: http://arxiv.org/abs/2402.15282v1
• Date: Fri, 23 Feb 2024 12:22:03 GMT
• Title: Dimension Independent Disentanglers from Unentanglement and Applications
• Authors: Fernando G. Jeronimo and Pei Wu
• Abstract summary: 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.
• Score: 55.86191108738564
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Quantum entanglement is a key enabling ingredient in diverse applications. However, the presence of unwanted adversarial entanglement also poses challenges in many applications. In this paper, we explore methods to "break" quantum entanglement. Specifically, we construct a dimension-independent k-partite disentangler (like) channel from bipartite unentangled input. We show: For every $d,\ell\ge k$, there is an efficient channel $\Lambda: \mathbb{C}^{d\ell} \otimes \mathbb{C}^{d\ell} \to \mathbb{C}^{dk}$ such that for every bipartite separable state $\rho_1\otimes \rho_2$, the output $\Lambda(\rho_1\otimes\rho_2)$ is close to a k-partite separable state. Concretely, for some distribution $\mu$ on states from $\mathbb{C}^d$, $$ \left\|\Lambda(\rho_1 \otimes \rho_2) - \int | \psi \rangle \langle \psi |^{\otimes k} d\mu(\psi)\right\|_1 \le \tilde O \left(\left(\frac{k^{3}}{\ell}\right)^{1/4}\right). $$ Moreover, $\Lambda(| \psi \rangle \langle \psi |^{\otimes \ell}\otimes | \psi \rangle \langle \psi |^{\otimes \ell}) = | \psi \rangle \langle \psi |^{\otimes k}$. Without the bipartite unentanglement assumption, the above bound is conjectured to be impossible. Leveraging our disentanglers, we show that unentangled quantum proofs of almost general real amplitudes capture NEXP, greatly relaxing the nonnegative amplitudes assumption in the recent work of QMA^+(2)=NEXP. Specifically, our findings show that to capture NEXP, it suffices to have unentangled proofs of the form $| \psi \rangle = \sqrt{a} | \psi_+ \rangle + \sqrt{1-a} | \psi_- \rangle$ where $| \psi_+ \rangle$ has non-negative amplitudes, $| \psi_- \rangle$ only has negative amplitudes and $| a-(1-a) | \ge 1/poly(n)$ with $a \in [0,1]$. Additionally, we present a protocol achieving an almost largest possible gap before obtaining QMA^R(k)=NEXP$, namely, a 1/poly(n) additive improvement to the gap results in this equality.

Related papers

• Sparsifying Suprema of Gaussian Processes [6.638504164134713]
  We show that there is an $O_varepsilon(1)$-size subset $S subseteq T$ and a set of real values $c_s_s in S$. We also use our sparsification result for suprema of centered Gaussian processes to give a sparsification lemma for convex sets of bounded geometric width.
  arXiv  Detail & Related papers  (2024-11-22T01:43:58Z)
• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  We show that this problem has randomized communication complexity $Omega(frac1kcdot n2log|mathbbF|)$. As an application, we obtain an $Omega(frac1kcdot n2log|mathbbF|)$ space lower bound for any streaming algorithm with $k$ passes.
  arXiv  Detail & Related papers  (2024-10-26T06:21:42Z)
• Quantum Algorithms and Lower Bounds for Finite-Sum Optimization [22.076317220348145]
  We give a quantum algorithm with complexity $tildeObig(n+sqrtd+sqrtell/mubig)$, improving the classical tight bound $tildeThetabig(n+sqrtnell/mubig)$. We also prove a quantum lower bound $tildeOmega(n+n3/4(ell/mu)1/4)$ when $d$ is large enough.
  arXiv  Detail & Related papers  (2024-06-05T07:13:52Z)
• Quantization Condition of the Bound States in $n$th-order Schr\"{o}dinger equations [2.5822051639377137]
  We will prove a general approximate quantization rule $% int_L_ER_Ek. The only hypothesis is that all exponentially growing components are negligible, which is appropriate for not narrow wells.
  arXiv  Detail & Related papers  (2023-04-03T12:07:34Z)
• A universal framework for entanglement detection under group symmetry [1.384055225262046]
  We prove that all $(overlinepi_Aotimes pi_B)$-invariant quantum states are separable if and only if all extremal unital positive $(pi_A,pi_B)$-covariant maps are decomposable. $Phi(rho)=arho+brhoT+fracctextTr(rho)dtextId_d+ (1-a-b-c)textdiag(rho)
  arXiv  Detail & Related papers  (2023-01-10T08:43:41Z)
• Time Evolution of Typical Pure States from a Macroscopic Hilbert Subspace [0.0]
  We consider a macroscopic quantum system with unitarily evolving pure state $psi_tin mathcalH$. We prove two facts about the evolution of the superposition weights $|P_nupsi_t|2$.
  arXiv  Detail & Related papers  (2022-10-18T17:37:42Z)
• The Approximate Degree of DNF and CNF Formulas [95.94432031144716]
  For every $delta>0,$ we construct CNF and formulas of size with approximate degree $Omega(n1-delta),$ essentially matching the trivial upper bound of $n. We show that for every $delta>0$, these models require $Omega(n1-delta)$, $Omega(n/4kk2)1-delta$, and $Omega(n/4kk2)1-delta$, respectively.
  arXiv  Detail & Related papers  (2022-09-04T10:01:39Z)
• 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)
• Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
  We study the problem of PAC learning halfspaces on $mathbbRd$ with Massart noise under Gaussian marginals. Our results qualitatively characterize the complexity of learning halfspaces in the Massart model.
  arXiv  Detail & Related papers  (2021-08-19T16:16:48Z)
• On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions [62.01594253618911]
  We exploit the finite noise structure of finite sums to derive a matching $O(n2)$-upper bound under the global oracle model. Following a similar approach, we propose a novel adaptation of SVRG which is both emphcompatible with oracles, and achieves complexity bounds of $tildeO(n2+nsqrtL/mu)log (1/epsilon)$ and $O(nsqrtL/epsilon)$, for $mu>0$ and $mu=0$
  arXiv  Detail & Related papers  (2020-02-09T03:39:46Z)

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.