Skip to main content

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.

Filter by
Sorted by
Tagged with
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 ...
Dudu Ponar's user avatar
2 votes
1 answer
156 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 $[...
Mark Spinelli's user avatar
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 ...
Mark Spinelli's user avatar
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 $|...
benimus's user avatar
  • 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 ...
Josh's user avatar
  • 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
omerna's user avatar
  • 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$, ...
snickers_stickers's user avatar
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 ...
Arnab's user avatar
  • 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, ...
J.Ask's user avatar
  • 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 ...
J.Ask's user avatar
  • 159
7 votes
1 answer
557 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 ...
Mark Spinelli's user avatar
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 ...
J.Ask's user avatar
  • 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 ...
BlackHat18's user avatar
  • 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}$ ...
Mark Spinelli's user avatar
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 ...
BlackHat18's user avatar
  • 1,373
5 votes
1 answer
514 views

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 ...
bean's user avatar
  • 331
8 votes
0 answers
195 views

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 ...
bean's user avatar
  • 331
3 votes
0 answers
81 views

Quantum Metropolis Algorithm: why is Quantum Simulated Annealing necessary?

I'm studying how Quantum Metropolis Algorithm (QMA) works and I think that I've understood it. Generally, the basic Metropolis step for a gave hamiltonian at the inverse temperature $\beta$ is: 1) it ...
kekambas35's user avatar
4 votes
1 answer
256 views

Quantum State Sanitizing

I was reading these lecture notes from Prof. Aaronson about Watrous's MA protocol for the group non-membership problem. At the end of the description, there's an approach to distinguish if Merlin ...
Taylor Huang's user avatar
3 votes
0 answers
151 views

Does strong error reduction for PostQMA exist?

$\mathsf{PostQMA}$ can be defined as the following (see Morimae-Nishimura and Usher-Hoban-Browne): A promise problem $\mathcal{L}=(\mathcal{L_{yes},L_{no}})$ is in $\mathsf{PostQMA(c,s)}$ if there ...
Yupan Liu's user avatar
  • 488
5 votes
2 answers
405 views

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, ..., ...
Sanchayan Dutta's user avatar
7 votes
1 answer
164 views

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's user avatar
6 votes
1 answer
214 views

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's user avatar
10 votes
2 answers
716 views

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 ...
user3483902's user avatar
7 votes
2 answers
280 views

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$ ...
user3483902's user avatar