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...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften
2022-03-01
|
| Series: | Quantum |
| Online Access: | https://quantum-journal.org/papers/q-2022-03-17-668/pdf/ |