Questions tagged [qma]
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.
25
questions
1
vote
0
answers
36
views
Proving CLDM is in QMA, In particular why is it possible to assume that the given input is a product of copies in the soundness section?
I'm wondering about a specific proof for Consistency of Local Density Matrices (CLDM) $ \in $ QMA appearing in "QMA-hardness of Consistency of Local Density Matrices with Applications to Quantum ...
- 430
2
votes
1
answer
157
views
If all terms of a local Hamiltonian commute, how hard is it to learn the ground state (energy)?
Suppose we have a $k$-local Hamiltonian with each of $m$ terms acting on $k$ of $n$ qudits of constant dimension $d$:
$$H=H_1+H_2+\cdots+H_m.$$
If at least some of the terms don't commute, e.g., if $[...
- 12.9k
4
votes
0
answers
86
views
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 ...
- 12.9k
2
votes
0
answers
31
views
Why is 3-Coloring in PQMA(2)?
I'm reading https://arxiv.org/abs/0709.0738 about the complexity of PQMA(2) and its relation to NP. It describes a PQMA(2) protocol (3.1) for 3-coloring which contains the following check:
For both $|...
- 21
3
votes
3
answers
305
views
Is verifying the solution to a QMA-complete problem efficient?
I am interested in the current state of the art on the difficulty of verifiability of a QMA complete problem, such as the local Hamiltonian problem. Suppose you are given a solution to a QMA complete ...
- 417
6
votes
2
answers
467
views
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
- 189
8
votes
1
answer
1k
views
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$, ...
5
votes
1
answer
303
views
How can one cheat in Mahadev's classical verification protocol if one can find a "claw''?
I was going through the seminal paper of Urmila Mahadev on Classical Verification of Quantum Computations(for an overview see this excellent talk by her). As a physicist by training, I am not very ...
- 221
3
votes
1
answer
156
views
Complexity of Quantum Satisfiability vs Local Hamiltonians
$k$QSAT$c$ is the promise problem where the input, given in an explicit encoding with finite number of bits, is a set $\{p_{1},p_{2},\ldots p_{m}\}$ of $k$-local projectors over a $n$-qbits register, ...
- 159
3
votes
1
answer
78
views
The complexity of LH restricted to projectors
Let's denote $kLP_{c}$ the promise problem where the input, given in an explicit encoding with finite number of bits, is a set $\{p_{1},p_{2},\ldots p_{m}\}$ of k-local projectors over a n-qbits ...
- 159
7
votes
1
answer
558
views
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 ...
- 12.9k
6
votes
2
answers
310
views
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 ...
- 159
4
votes
0
answers
134
views
How close is the history state to the ground state in the Kitaev clock construction?
Consider a standard circuit to Hamiltonian reduction in QMA. For example, refer here (Vazirani's lecture notes) or page 235 of here (survey by Gharibian et al).
The history state of the Kitaev clock ...
- 1,373
3
votes
1
answer
274
views
On the probability of preparing of a uniform superposition by performing a controlled-multiplication and post-selecting $0$
I take as a starting point Watrous's celebrated paper defining the Quantum Merlin-Arthur (QMA) class. He provides a protocol for Arthur to test whether an element $h$ is not in a group $\mathcal{H}$ ...
- 12.9k
6
votes
1
answer
282
views
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 ...
- 1,373