On the power of quantum proofs

Ran Raz, Amir Shpilka

Research output: Contribution to journalConference articlepeer-review

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