QMA with subset state witnesses

DOI10.1007/978-3-662-48054-0_14MaRDI QIDQ2946385zbMATH OpenOpenAlexFDO

Authors Alex Bredariol Grilo, Iordanis Kerenidis, Jamie Sikora

Publication date 16 September 2015

Published in Mathematical Foundations of Computer Science 2015 (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1410.2882

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

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

Recommendations

• QMA with subset state witnesses
• Two QCMA-complete problems
• On perfect completeness for QMA
• Quantum vs. classical proofs and subset verification
• Classical verification of quantum proofs

Cites work

• scientific article; zbMATH DE number 5320237 (Why is no real title available?)
• scientific article; zbMATH DE number 1776257 (Why is no real title available?)
• Achieving perfect completeness in classical-witness quantum Merlin-Arthur proof systems
• Complexity classification of local Hamiltonian problems
• On perfect completeness for QMA
• Probabilistic checking of proofs
• Product-state approximations to quantum ground states
• Proof verification and the hardness of approximation problems
• QMA with subset state witnesses
• Quantum Arthur-Merlin games
• Stronger methods of making quantum interactive proofs perfectly complete
• The complexity of quantum spin systems on a two-dimensional square lattice
• The complexity of theorem-proving procedures
• The detectability lemma and quantum gap amplification
• Two QCMA-complete problems
• Two-Message Quantum Interactive Proofs Are in PSPACE

Cited in

(9)

• Characterising the intersection of QMA and coQMA
• On the power of a unique quantum witness
• QMA with subset state witnesses
• Quantum vs. classical proofs and subset verification
• Total functions in QMA
• Two QCMA-complete problems
• QMA with subset state witnesses
• StoqMA meets distribution testing
• Fast amplification of QMA

This page was built for publication: QMA with subset state witnesses

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2946385)