IQC Math and CS seminar featuring Dorian Rudolph

On the Complexity of Pure-State Consistency of Local Density Matrices

Dorian Rudolph | University of Paderborn

In this work we investigate the computational complexity of the pure consistency of local density matrices (CLDM) and pure N-representability problems. In these problems the input is a set of reduced density matrices and the task is to determine whether there exists a global pure state consistent with these reduced density matrices. While mixed CLDM, i.e. where the global state can be mixed, was proven to be QMA-complete by Broadbent and Grilo [JoC 2022], almost nothing was known about the complexity of the pure version. Before our work the best upper and lower bounds were QMA(2) and QMA. Our contribution to the understanding of these problems is twofold.

Firstly, we define a pure state analogue of the complexity class QMA+ of Aharanov and Regev [FOCS 2003], which we call PureSuperQMA. We prove that both PureCLDM and Pure-N-representability are complete for this new class. Along the way we supplement Broadbent and Grilo by proving hardness for 2-qubit reduced density matrices and showing that mixed N-representability is QMA complete.

Secondly, we improve the upper bound on PureCLDM. Using methods from algebraic geometry, we prove that PureSuperQMA ⊆ PSPACE. Our methods, and the PSPACE upper bound, are also valid for PureCLDM with exponential or even perfect precision, hence precisePureCLDM is not preciseQMA(2) = NEXP-complete, unless PSPACE = NEXP. We view this as evidence for a negative answer to the longstanding open question whether PureCLDM is QMA(2)-complete.

Location

• Online on Zoom

  • Meeting ID: 970 5527 1363

  • Passcode: 673302