For question about Quantum Merlin Arthur (QMA), a computational complexity class. QMA is the 'quantum analogue' of NP, that is QMA is to BQP as NP is to P.
Questions tagged [qma]
37 questions
11
votes
2 answers
Quantum Chemistry and Quantum Computing
Predicting the energy of molecules to high accuracy during the course of a chemical reaction, which in turn allows us to predict reaction rates, equilibrium geometries, transition states among others is a Quantum Chemical problem.
Quantum Computing…
user3483902
- 825
- 8
- 15
9
votes
1 answer
How do we understand Jordan's Lemma?
In quantum computing protocols, jordan's lemma keeps cropping up. See, for example, here: https://cims.nyu.edu/~regev/teaching/quantum_fall_2005/ln/qma.pdf
For any two projectors $\phi_1$, $\phi_2$, there exists an orthogonal decomposition of the…
snickers_stickers
- 577
- 2
- 12
8
votes
0 answers
Better "In-Place" Amplification of QMA
$\def\braket#1#2{\langle#1|#2\rangle}\def\bra#1{\langle#1|}\def\ket#1{|#1\rangle}$
In MW05 the authors demonstrate so-called "in-place" amplitude amplification for QMA, exhibiting a method for Arthur to amplify his success probability without…
bean
- 341
- 1
- 4
7
votes
2 answers
Quantum proof for the group non-membership problem
Group non-membership problem:
Input: Group elements $g_1,..., g_k$ and $h$ of $G$.
Yes: $h \not\in \langle g_1, ..., g_k\rangle$
No: $h\in \langle g_1, ..., g_k\rangle$
Notation: $\langle g_1, ..., g_k\rangle$ is the subgroup generated by…
Sanchayan Dutta
- 17,945
- 8
- 50
- 112
7
votes
1 answer
Relation between $\mathrm{QMA}$ and $\mathrm{P^{QMA}}$
What is the relation between $\mathrm{QMA}$ and $\mathrm{P^{QMA}}$ and how do we prove it? Are these classes equal?
BlueLagoon
- 73
- 2
7
votes
2 answers
How can I show that $\mathsf{QMA}\subseteq \mathsf{PSPACE}$
Lately I have seen the claim that $\mathsf{QMA}\subseteq \mathsf{PSPACE}$, and I wonder how can it be proved.
Thanks
omerna
- 199
- 3
7
votes
2 answers
Upper Bounds for QMA Quantum Merlin Arthur, and QMA(k)
QMA (Quantum Merlin Arthur), is the quantum analog of NP, and QMA(k) is the class with $k$ Merlins. These are important classes when studying Quantum Complexity theory. QMA(k) is QMA with $k$ unentangled provers ($k$ Merlins), or BQP verfiers. These…
user3483902
- 825
- 8
- 15
7
votes
1 answer
How is a promise gap related to a spectral gap?
In linear algebra one often concerns oneself with the spectral gap of a given matrix, which may be defined as the difference between the smallest and second-smallest eigenvalue (or, depending on convention and context, between the largest and…
Mark Spinelli
- 15,378
- 3
- 26
- 83
6
votes
1 answer
Self reducibility of QCMA problems
Self reducibility is when search version of the problems in a language reduce to decision versions of the same problems. NP-complete problems are self reducible. Are QCMA complete problems self reducible?
BlackHat18
- 1,527
- 9
- 22
6
votes
1 answer
Marriott-Watrous style amplification with a quantum input
$\def\braket#1#2{\langle#1|#2\rangle}\def\bra#1{\langle#1|}\def\ket#1{|#1\rangle}$
In MW05 the authors demonstrate so-called "in-place" amplitude amplification for QMA, exhibiting a method for Arthur to amplify his success probability without…
bean
- 341
- 1
- 4
6
votes
1 answer
What classical public key cryptography protocols exist for which hacking is QMA complete or QMA hard?
Such a public key cryptosystem would be "quantum safe" in the sense that quantum computers cannot efficiently solve QMA hard problems.
user1271772 No more free time
- 14,286
- 2
- 26
- 76
6
votes
2 answers
The complexity of LH with constant gap
Kitaev's quantum equivalent of the Cook-Levin Theorem, provides a polynomial time classical reduction from a QMA verification circuit to a sum $H$ of local hamiltonians, such that the least eigenvalue of $H$ is either $\leq a$ or $\geq b$, with…
J.Ask
- 159
- 6
5
votes
1 answer
Did Kitaev prove the QMA-completeness of the Local Hamiltonian problem while on a flight to Chicago?
I believe the first publication of the proof of the QMA-completeness of the Local Hamiltonian Problem is as portions of a chapter in the book Classical and Quantum Computation, by Kitaev, Shen, and Vyilyi, published in Russian in 1999 (with an…
Mark Spinelli
- 15,378
- 3
- 26
- 83
5
votes
1 answer
For the Local Hamiltonian Problem, how is soundness proved if Arthur uses phase estimation on the putative ground state provided by Merlin?
Recall that showing QMA-completeness of the Local Hamiltonian Problem includes showing that the problem is both (A) in (promise) QMA and (B) QMA hard. QMA hardness is usually shown with a neat bespoke circuit-to-Hamiltonian construction that…
Mark Spinelli
- 15,378
- 3
- 26
- 83
5
votes
0 answers
How useful is it to know the ground state energy of an arbitrary $k$-local Hamiltonian, if Nature herself can never find such energy?
We know that the $2$-local Hamiltonian problem is (promise) QMA-complete, which under the reasonable assumption that BQP$\subsetneq$QMA implies that no fast quantum algorithm exists to determine the eigenstate, much less the energy, of the ground…
Mark Spinelli
- 15,378
- 3
- 26
- 83