Abstract | ||
---|---|---|
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 -complete ground state connectivity (GSCON) problem for a system of size with a proof of superlinear size. We show that we can shorten this proof in : There exists a two-copy, unentangled proof with length of order , up to logarithmic factors, while the completeness–soundness gap of the new protocol becomes a small inverse polynomial in . |
Year | DOI | Venue |
---|---|---|
2018 | https://doi.org/10.1007/s11128-018-1944-4 | Quantum Information Processing |
Keywords | Field | DocType |
Quantum complexity,QMA(2),Unentanglement,Short proofs,Ground state connectivity problem (GSCON) | Quantum,Discrete mathematics,Inverse,Ground state,Existential quantification,Polynomial,Quantum mechanics,Mathematical proof,Logarithm,Physics | Journal |
Volume | Issue | ISSN |
17 | 7 | Quantum Inf Process (2018) 17: 174 |
Citations | PageRank | References |
0 | 0.34 | 7 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Libor Caha | 1 | 0 | 0.34 |
Daniel Nagaj | 2 | 57 | 5.84 |
Martin Schwarz | 3 | 0 | 0.68 |