Shorter unentangled proofs for ground state connectivity

2018 
Can one considerably shorten a proof for a quantum problem by using a protocol with a constant number of unentangled provers? We consider a frustration-free variant of the \(\textsf {QCMA}\)-complete ground state connectivity (GSCON) problem for a system of size n with a proof of superlinear size. We show that we can shorten this proof in \(\textsf {QMA}(2)\): There exists a two-copy, unentangled proof with length of order n, up to logarithmic factors, while the completeness–soundness gap of the new protocol becomes a small inverse polynomial in n.
    • Correction
    • Source
    • Cite
    • Save
    • Machine Reading By IdeaReader
    22
    References
    0
    Citations
    NaN
    KQI
    []