Report

The computational complexity of entanglement detection Figure 3: A two-message quant um int eract ive proof syst em for QSEP-STATE1,1-L OCC . wit h t he veriﬁer execut ing t he circuit U⇢ t hat generat es t he st at e ⇢A B . He sends t he syst em t o t he prover. In t he case t hat ⇢A B is separable, t he prover should be able t o a unit ary on t he reference syst em and some ancillas in order t o generat e a puriﬁcat io ext ension of ⇢A B . T he prover sends all of t he ext ension syst ems back t o t he veriﬁer, performs phase est imat ion over t he symmet ric group (a quant um Fourier t ransform follo cont rolled permut at ion) in order t o t est if t he st at e sent by t he prover is really a k-ext en The universe as seen by entanglement detection where { |xi R 0} is some ort honormal basis for t he reference syst em. Since all puriﬁcat ions a by unit aries on t he reference syst em, t he prover can append ancilla qubit s t o t he R syst em from t he veriﬁer and perform a unit ary P1 t hat t akes | ⇢i RA B |0i t o |φk,⇢i R 0A B B 2 ···B k . T t hen sends t he syst ems B 2, . . . , B k t o t he veriﬁer. T he veriﬁer performs a permut at ion t e syst ems B , B 2, . . . , B k . Since t he st at e |φk,⇢i R 0A B B 2 ···B k is invariant under permut at io syst ems B , B 2, . . . , B k , t he qubit s in t he cont rol regist er C do not acquire a phase. T hus, ﬁnal quant um Fourier t ransform is applied, t he qubit s in t he cont rol regist er C are in t h st at e wit h cert ainty. T he analysis for a YES inst ance follows t he above int uit ion closely. In t his case, t her st at e σA B 2 S t hat is δc-close in t race dist ance t o ⇢A B . By Uhlmann’s t heorem in (8) Fuchs-van-de-Graaf inequalit ies in (9), t here is a puriﬁcat ion | σ i RA B of σA B such t hat p | ⇢i h ⇢|RA B − | σ i h σ |RA B 1 2 δc. Mark M. Wilde : 1-LOCC : Trace Louisiana State University Oval = complete Box = containment So t he prover can just operat e as above, but choosing his unit ary P1 t o correspond t o | σ i RA B inst ead. Writ ing as U t he unit ary corresponding t o P1 followed by t he permut a we obt ain t he following lower bound on t he probability wit h which t he veriﬁer accept s: n o Tr |0i h0|C U | ⇢i h ⇢|RA B U † n o = Tr U † |0i h0|C U | ⇢i h ⇢|RA B n o ≥ Tr U † |0i h0|C U (| σ i h σ |RA B ) − | ⇢i h ⇢|RA B − | σ i h σ |RA B 1 p ≥ 1 − 2 δc, Based on 1211.6120 and 1308.5788 With Gus Gutoski, Patrick Hayden, and Kevin Milner How hard is entanglement detection? • Given a matrix describing a bipartite state, is the state separable or entangled? – NP-hard for d x d, promise gap 1/poly(d) [Gurvits ’04 + Gharibian ‘10] – Quasipolynomial time for constant gap [Brandao et al. ’10] • Probably not the right question for large systems. • Given a description of a physical process for preparing a quantum state (i.e. quantum circuit), is the state separable or entangled? • Variants: – – – – Pure versus mixed State versus channel Product versus separable Choice of distance measure (equivalently, nature of promise) Entanglement detection: The platonic Natural entanglement detectionideal problems α NO α YES β Some complexity classes… P / BPP / BQP = QIP(0) NP / MA / QMA = QIP(1) AM / QIP(2) Cryptographic variant: Zero-knowledge Verifier, in YES instances, can “simulate” prover ZK / SZK / QSZK = QSZK(2) QMA(2) QIP = QIP(3) = PSPACE [Jain et al. ‘09] Our results Our State results version: Results: States • Unitary circuit State version: • Product Pure state circuit circuit state? • Unitary Product output? • Trace distance • Product state? Trace distance • Trace distance ever, much is known of other variants State version: Mixed state circuitcircuit • Non-unitary State version: Product output? • Product state? • Non-unitary circuit Trace distance • Trace distance • Product state? • Trace distance Mixed state circuit Channel Separable version: output? • Unitary circuit 1-LOCC distance (1/poly) Channel version: • Separable state? • Unitary circuit • Separable state? BQP-complete QSZK-complete NP-hard distance QSZK-hard 1-LOCC 1-LOCC distance In QIP(2) Trace distance Trace distance Results: Channels State version: Channel version: • Non-unitary circuit • Unitary circuit • Product state? Isometric channel • Separable state? • Separable output? Trace distance 1-LOCC distance ever, much is known of other variants Channel version: • Isometric Unitarychannel circuit output? • Separable Separable state? Trace distance Noisy channel Separable output? 1-LOCC distance 1-LOCC distance QMA-complete Trace distance 1-LOCC distance QMA(2)-complete Trace distance QIP-complete The computational universe through the entanglement lens The universe as seen by entanglement detection : 1-LOCC : Trace Oval = complete Box = containment Our results Our State results version: Results: States • Unitary circuit State version: • Product Pure state circuit circuit state? • Unitary Product output? • Trace distance • Product state? Trace distance • Trace distance ever, much is known of other variants State version: Mixed state circuitcircuit • Non-unitary State version: Product output? • Product state? • Non-unitary circuit Trace distance • Trace distance • Product state? • Trace distance Mixed state circuit Channel Separable version: output? • Unitary circuit 1-LOCC distance Channel version: • Separable state? • Unitary circuit • Separable state? BQP-complete QSZK-complete NP-hard distance QSZK-hard 1-LOCC 1-LOCC distance In QIP(2) Trace distance Detecting mixed product states Detecting mixed product states is QSZK-complete Detecting mixed product states Detecting mixed product states is QSZK-complete Detecting is mixed product (verifier) states in QSZK 1. QPROD-STATE Prover U* U* Completeness: YES instances 1a. QPROD-STATE QSZK(completeness) (completeness) 1a. QPROD-STATEis is in in QSZK W W* W* W W W W U* U* W U* Soundness: NO instances 1a. QPROD-STATE QSZK(completeness) (completeness) 1a. QPROD-STATEis is in in QSZK W W* W* W W W W U* U* W U* Zero-knowledge (YES instances): Verifier can simulate prover output 1b. QPROD-STATE is in QSZK (zero-knowledge) Looks just like the prover's message! U* U* QPROD-STATE is QSZK-hard 2. QPROD-STATE is QSZK-hard Reduction from co-QSD to QPROD-STATE Reduction from co-QSD to QPROD-STATE Our results Our State results version: Results: States • Unitary circuit State version: • Product Pure state circuit circuit state? • Unitary Product output? • Trace distance • Product state? Trace distance • Trace distance ever, much is known of other variants State version: Mixed state circuitcircuit • Non-unitary State version: Product output? • Product state? • Non-unitary circuit Trace distance • Trace distance • Product state? • Trace distance Mixed state circuit Channel Separable version: output? • Unitary circuit 1-LOCC distance Channel version: • Separable state? • Unitary circuit • Separable state? BQP-complete QSZK-complete NP-hard distance QSZK-hard 1-LOCC 1-LOCC distance In QIP(2) Trace distance Thus, we show a two-message protocol to determine separability by sending the reference system for our bipartite state to the prover and receiving back a suitably large k-extension. Detecting mixed separable states ρAB close to separable iff it has a suitable k-extension for sufficiently large k. [BCY ‘10] Send R to the prover, who will try to produce the k-extension. Use phase estimation to verify that the resulting state is a k-extension. Summary • Entanglement detection provides a unifying paradigm for parametrizing quantum complexity classes • Tunable knobs: – State versus channel – Pure versus mixed – Trace norm versus 1-LOCC norm – Product versus separable