QMA with subset state witnesses

DOI10.1007/978-3-662-48054-0_14zbMATH Open1465.68096arXiv1410.2882OpenAlexW1548627985MaRDI QIDQ2946385FDOQ2946385

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)

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

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

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

Mathematics Subject Classification ID

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

Cites Work

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

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)