Quantum witness
= Quantum witness
{title2=$|w\rangle\in(\mathbb C^2)^{\otimes m}$}
A <quantum witness> is a polynomial-size <quantum state> supplied to a verifier as evidence for a YES instance. The verifier fixes its own <ancilla qubits> independently. Pure <quantum witnesses> suffice when maximizing a linear acceptance functional on <density operators>. <Quantum witnesses> are not generally restricted to basis vectors or product states.