Chicago Journal of Theoretical Computer Science

Volume 2016

Article 4

Published by the Department of Computer Science, The University of Chicago.


QMA with subset state witnesses

Alex Bredariol Grilo
Université Paris Diderot 7
Paris France;
abgrilo AT liafa DOT univ-paris-diderot DOT fr

Iordanis Kerenidis
Université Paris Diderot 7
Paris France;
and
CQT
National University of Singapore
Singapore
jkeren AT liafa DOT univ-paris-diderot DOT fr

Jamie Sikora
CQT
National University of Singapore
Singapore
cqtjwjs AT nus DOT edu DOT sg

March 23, 2016

Abstract

The class QMA plays a fundamental role in quantum complexity theory and it has found surprising connections to condensed matter physics and in particular in the study of the minimum energy of quantum systems. In this paper, we further investigate the class QMA and its related class QCMA by asking what makes quantum witnesses potentially more powerful than classical ones. We provide a definition of a new class, SQMA, where we restrict the possible quantum witnesses to the "simpler" subset states, i.e. a uniform superposition over the elements of a subset of $n$-bit strings. Surprisingly, we prove that this class is equal to QMA, hence providing a new characterisation of the class QMA. We also prove the analogous result for QMA(2) and describe a new complete problem for QMA and a stronger lower bound for the class QMA$_1$

.

Submitted November 5, 2015, revised March 10, 2016, published March 23, 2016.

DOI: 10.4086/cjtcs.2016.004


[] Volume 2016, Article 3
[back] Volume 2016 [back] Published articles
[CJCTS home]