Papers for

quantum complexity analysts

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

QMA quantum proofs can always be made perfectly complete

QMA has perfect completeness

Abstract: We prove $\mathsf{QMA} = \mathsf{QMA_1}$, i.e., every quantum Merlin-Arthur proof system can be made perfectly complete. Our construction uses only Hadamard, Toffoli, and $X$ gates, yielding a universal gate set for $\mathsf{QMA_1}$. As a consequence, quantum $3$-SAT is $\mathsf{QMA}$-complete. The construction relativizes to classical oracles, so known classical-oracle separations of $\mathsf{QMA}$ from $\mathsf{QCMA}$ extend to $\mathsf{QMA_1}$.

Fri 11 SeptComputational Complexity
The gist
Some computer problems can be checked using quantum proofs, but these checks sometimes have a small chance of rejecting a correct proof. The authors show that it is possible to design these quantum proof systems so that if the proof is correct, it will always be accepted. They achieve this using a specific set of basic quantum operations. This result also confirms that an important quantum logic problem remains one of the hardest in quantum computation.
Open → 2609.13032v1