Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > QMA:
Reports tagged with QMA:
TR08-051 | 4th April 2008
Scott Aaronson, Salman Beigi, Andrew Drucker, Bill Fefferman, Peter Shor

#### The Power of Unentanglement

The class QMA(k), introduced by Kobayashi et al., consists
of all languages that can be verified using k unentangled quantum
proofs. Many of the simplest questions about this class have remained
embarrassingly open: for example, can we give any evidence that k
quantum proofs are more powerful than one? Can ... more >>>

TR08-067 | 4th June 2008
Scott Aaronson

#### On Perfect Completeness for QMA

Whether the class QMA (Quantum Merlin Arthur) is equal to QMA1, or QMA with one-sided error, has been an open problem for years. This note helps to explain why the problem is difficult, by using ideas from real analysis to give a "quantum oracle" relative to which QMA and QMA1 ... more >>>

TR11-001 | 2nd January 2011
Scott Aaronson

#### Impossibility of Succinct Quantum Proofs for Collision-Freeness

We show that any quantum algorithm to decide whether a function $f:\left[n\right] \rightarrow\left[ n\right]$ is a permutation or far from a permutation\ must make $\Omega\left( n^{1/3}/w\right)$ queries to $f$, even if the algorithm is given a $w$-qubit quantum witness in support of $f$ being a permutation. This implies ... more >>>

TR11-110 | 10th August 2011
Alessandro Chiesa, Michael Forbes

#### Improved Soundness for QMA with Multiple Provers

Revisions: 1

We present three contributions to the understanding of QMA with multiple provers:

1) We give a tight soundness analysis of the protocol of [Blier and Tapp, ICQNM '09], yielding a soundness gap $\Omega(N^{-2})$, which is the best-known soundness gap for two-prover QMA protocols with logarithmic proof size. Maybe ... more >>>

TR16-109 | 18th July 2016
Scott Aaronson

#### The Complexity of Quantum States and Transformations: From Quantum Money to Black Holes

This mini-course will introduce participants to an exciting frontier for quantum computing theory: namely, questions involving the computational complexity of preparing a certain quantum state or applying a certain unitary transformation. Traditionally, such questions were considered in the context of the Nonabelian Hidden Subgroup Problem and quantum interactive proof systems, ... more >>>

ISSN 1433-8092 | Imprint