Consider the accepting POVM ($\Pi$, $I-\Pi$) of a fixed QMA machine. Let d be the number of eigenstates of $\Pi$ that are at least 2/3. Decide if d is at least some fixed s, or at most s/2. This i...
The complexity class QMA(2) has no known upper bounds aside from NEXP. It is unknown whether this class lies in BQEXP, which gives a quantum computer exponential time to decide a problem with $\ge ...
QAC0 is the class of constant-depth quantum circuits with single-qubit gates and Toffoli gates. Is QAC0 with fanout more powerful than QAC0 with fanout *only allowed at the beginning of the circuit...
Let $F_k(G)$ be the $k$-token graph of $G$, which has: * ${n \choose k}$ vertices, represented by $S \subseteq [n]$ of size $|S| = k$ * each edge $(S,T)$ is where the symmetric difference of S and T...
The Parisi value (approximately -0.763166...) represents the ground state energy density of the SK model in the thermodynamic limit. The main conjecture is whether QAOA, as depth p approaches infinity...
What is the complexity of computing the ground state energy of the EPR Hamiltonian? The EPR Hamiltonian is a quantum Hamiltonian defined on a graph where each edge contains a projector onto the sym...