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. Patrick Hayden Stanford University : 1-LOCC : Trace 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, 1301.4504 and 1308.5788 With Gus Gutoski, Daniel Harlow, Kevin Milner and Mark Wilde 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) Why ask? • Provides a natural set of complete problems for many widely studied classes in quantum complexity • Personal motivation: – Quantum gravity! • Personal frustration at inability to find a “fast scrambler” • Possible implications for the black hole firewall problem 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 Baby steps: Detecting pure product states is BQP-complete Detecting pure product states Baby steps: Detecting pure product states Detecting pure product states is BQP-complete 1. QPROD-PURE-STATE is in BQP 1. QPROD-PURE-STATE is in BQP Product test swap test Accept iff both tests pass swap test 2. QPROD-PURE-STATE is BQP-hard 2. QPROD-PURE-STATE is BQP-hard (1 of 2) 2. QPROD-PURE-STATE is BQP-hard 2. QPROD-PURE-STATE is BQP-hard (2 of 2) 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 Jaunty stroll: Detecting mixed product states Detecting mixed product states is QSZK-complete Jaunty stroll: Detecting mixed product states Detecting mixed product states is QSZK-complete Jaunty stroll: 1. QPROD-STATE is in QSZK (verifier) Detecting mixed product states 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 Detecting mixed product states is QSZK-complete QPROD-STATE and Quantum Error Correction QPROD-STATE: Detecting mixed product states is QSZK-complete QEC: R: “System” A: “Reference” B: “Environment” These are the SAME problem! Cloning, Black Holes and Firewalls Quantum information appears to be cloned U V Singularity Spacetime structure prevents comparison of the clones (?) Is unitarity safe? Radial light rays: In Out 2007: H & Preskill study old black holes. (Only just) safe 2012: Almheiri et al. consider φ to be entanglement with late time Hawking photon Firewalls! [Page, Preskill, Susskind 93][Susskind, Thorlacius, Uglum 93] Cloning, Black Holes and Firewalls U V Singularity φ φ If infalling Bob is to experience the vacuum as he crosses the horizon, φ must be in infalling Hawking partner. If black hole entropy is to decrease, φ must be present in early Hawking radiation. But has cloning really occurred? Do two copies of φ exist? Radial light rays: In Out To test, Bob would need to decode (QEC) the early Hawking radiation: QSZK-hard but BH lifetime is poly(# qubits). 2012: Almheiri et al. consider φ to be entanglement with late time Hawking photon Firewalls! [Page, Preskill, Susskind 93][Susskind, Thorlacius, Uglum 93] 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 Jogging: Detecting mixed separable states 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. ρ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 • Implications for the (worst case) complexity of decoding quantum error correcting codes • Provides challenge to the black hole firewall argument Entanglement detection: The platonic Natural entanglement detectionideal problems α NO α YES β Complexity of QSEP-STATE? Who knows? The universe as seen by entanglement detection : 1-LOCC : Trace Oval = complete Box = containment Soundness: NO instances 1c. QPROD-STATE is in QSZK (soundness) Prover U* U* Detour: extendability and all that (2 of 2) 1a. QSEP-ISOMETRY1-LOCC is in QMA (completeness) Prover Verifier permutation test Accept iff both tests pass permutation test 2. QSEP-ISOMETRY1-LOCC is QMA-hard 3a and 3b. QSEP-ISOMETRY1 is in QMA(2) Provers Verifier Product test swap test swap test Accept iff both tests pass 4. QSEP-ISOMETRY1 is QMA(2)-hard