Prefer a chat interface with context about you and your work?
The Pursuit of Uniqueness: Extending Valiant-Vazirani Theorem to the Probabilistic and Quantum Settings
Valiant-Vazirani showed in 1985 \cite{VV85} that solving NP with the promise that "yes" instances have only one witness is powerful enough to solve the entire NP class (under randomized reductions).We are interested in extending this result to the quantum setting. We prove extensions to the classes Merlin-Arthur MA and Quantum-Classical-Merlin-Arthur …