Theorem 1.1 —
ProvedQMAPerfectCompleteness.Main.qma_eq_qma1_hadamard_toffoliEvery quantum Merlin–Arthur proof system can be made perfectly complete using only Hadamard and Toffoli gates:
This is an equality of classes of binary promise problems. Here QMA has completeness and soundness over a universal gate set. A problem lies in if a polynomial-time algorithm maps each input to a verifier over and Toffoli such that on YES inputs some proof, an arbitrary complex density matrix on polynomially many qubits, is accepted with probability exactly , and on NO inputs every proof is accepted with probability at most .
The theorem resolves the question, open since Bravyi introduced , of whether perfect completeness changes the power of QMA. It also shows that is universal for , a question for which approximate synthesis gives no answer because approximating a gate can lower an acceptance probability of one.
Differences from the source:
- encoding: QMA is for any universal gate set , well defined by Solovay-Kitaev and amplification → the fixed gate set ; reason: it is the universal set the source's proof of Lemma 3.1 starts from, and the source states that the choice does not matter
- encoding: a polynomial-time algorithm maps to a verifier → a multi-stack machine (Turing.TM2ComputableInPolyTime) outputs a self-delimiting code of with every number in unary; gate sets are lists of exact unitary matrices, without the approximability clause of §2; reason: all numbers in a polynomial-size circuit are polynomially bounded, so unary and binary codes define the same class, and the three gate sets used here have explicitly computable entries
import Definitions.Def_QMAPerfectCompleteness_Main_Compiler open Matrix
namespace QMAPerfectCompleteness.Main
/-- Theorem 1.1 (p. 2; proof p. 11): `QMA = QMA₁^{HT}`, as classes of promise problems. -/
theorem qma_eq_qma1_hadamard_toffoli : QMA = QMA1 gatesHT := by sorry
end QMAPerfectCompleteness.Main
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.