On the power of quantum proofs

Ran Raz, Amir Shpilka

Research output: Contribution to journalConference article

21 Scopus citations

Abstract

The power of quantum proofs in two well studied models of quantum computation was discussed. The main results were obtained for the communication complexity model. A very simple proof for the exponential separation between quantum Merlin-Arthur (QMA) black box complexity and MA block complexity was obtained. Lower bounds for the QMA black box complexity of several functions is proved.

Original languageEnglish (US)
Pages (from-to)260-274
Number of pages15
JournalProceedings of the Annual IEEE Conference on Computational Complexity
Volume19
StatePublished - Oct 18 2004
Externally publishedYes
EventProceedings - 19th IEEE Annual Conference on Computational Complexity - Amherst, MA, United States
Duration: Jun 21 2004Jun 24 2004

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Computational Mathematics

Fingerprint Dive into the research topics of 'On the power of quantum proofs'. Together they form a unique fingerprint.

  • Cite this