Volume 8 (2012) Article 17 pp. 375-400

On the Power of a Unique Quantum Witness

by Rahul Jain, Iordanis Kerenidis, Greg Kuperberg, Miklos Santha, Or Sattath, and Shengyu Zhang

Received: January 31, 2012
Published: August 14, 2012

$ \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.

DOI: 10.4086/toc.2012.v008a017

© 2012 Rahul Jain, Iordanis Kerenidis, Greg Kuperberg, Miklos Santha, Or Sattath, and Shengyu Zhang
Licensed under a Creative Commons Attribution License (CC-BY)