pdf icon
Volume 8 (2012) Article 17 pp. 375-400
On the Power of a Unique Quantum Witness
Received: January 31, 2012
Published: August 14, 2012
Download article from ToC site:
[PDF (325K)] [PS (1351K)] [Source ZIP]
Keywords: Valiant-Vazirani Theorem, unique witness, quantum, QMA
ACM Classification: F.1.3
AMS Classification: 81P68

Abstract: [Plain Text Version]

$ \newcommand{\h}{{\mathcal{H}}} \newcommand{\hd}{{\mathcal{H}^{\otimes d}}} \newcommand{\watd}{{{W}^{\otimes d}}} \newcommand\np{\mathsf{NP}} \newcommand\qma{\mathsf{QMA}} $

In a celebrated paper, Valiant and Vazirani (1985) raised the question of whether the difficulty of $\np$-complete problems was due to the wide variation of the number of witnesses of their instances. They gave a strong negative answer by showing that distinguishing between instances having zero or one witnesses is as hard as recognizing $\np$, under randomized reductions.

We consider the same question in the quantum setting and investigate the possibility of reducing quantum witnesses in the context of the complexity class $\qma$, the quantum analogue of $\np$. The natural way to quantify the number of quantum witnesses is the dimension of the witness subspace $W$ in some appropriate Hilbert space $\h$. We present an efficient deterministic procedure that reduces any problem where the dimension $d$ of $W$ is bounded by a polynomial to a problem with a unique quantum witness. The main idea of our reduction is to consider the Alternating subspace of the tensor power $\hd$. Indeed, the intersection of this subspace with $\watd$ is one-dimensional, and therefore can play the role of the unique quantum witness.