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

TR19-015 | 7th February 2019
William Kretschmer

#### QMA Lower Bounds for Approximate Counting

We prove a query complexity lower bound for $QMA$ protocols that solve approximate counting: estimating the size of a set given a membership oracle. This gives rise to an oracle $A$ such that $SBP^A \not\subset QMA^A$, resolving an open problem of Aaronson [2]. Our proof uses the polynomial method to ... more >>>

TR19-121 | 17th September 2019
Alexander A. Sherstov, Justin Thaler

#### Vanishing-Error Approximate Degree and QMA Complexity

The $\epsilon$-approximate degree of a function $f\colon X \to \{0, 1\}$ is the least degree of a multivariate real polynomial $p$ such that $|p(x)-f(x)| \leq \epsilon$ for all $x \in X$. We determine the $\epsilon$-approximate degree of the element distinctness function, the surjectivity function, and the permutation testing problem, showing ... more >>>

TR19-131 | 11th September 2019
Lieuwe Vinkhuijzen, André Deutz

#### A Simple Proof of Vyalyi's Theorem and some Generalizations

In quantum computational complexity theory, the class QMA models the set of problems efficiently verifiable by a quantum computer the same way that NP models this for classical computation. Vyalyi proved that if $\text{QMA}=\text{PP}$ then $\text{PH}\subseteq \text{QMA}$. In this note, we give a simple, self-contained proof of the theorem, using ... more >>>

ISSN 1433-8092 | Imprint