Hot answers tagged

7 votes
Accepted

How is a promise gap related to a spectral gap?

The spectral gap is pretty much independent of the promise gap. (First off, my feeling is that "promise gap" is a little bit misleading, though formally correct: What it really refers to, in ...
Norbert Schuch's user avatar
6 votes
Accepted

Relation between $\mathrm{QMA}$ and $\mathrm{P^{QMA}}$

Clearly $\mathrm{QMA \subseteq P^{QMA}}$, as we can construct a $\mathrm{P^{QMA}}$ algorithm to solve any problem in $\mathrm{QMA}$, by using an oracle call. The question is whether the reverse ...
Niel de Beaudrap's user avatar
6 votes

Self reducibility of QCMA problems

self-reducible is a term regarding function class, such as $\mathsf{FNP}$, which is slightly different from what I am going to talk about, namely a witness-finding procedure for some quantum ...
Yupan Liu's user avatar
  • 488
5 votes

How can I show that $\mathsf{QMA}\subseteq \mathsf{PSPACE}$

Well, it is not such hard to show a $\mathsf{PSPACE}$-containment of $\mathsf{QMA}$... Recall that the maximum acceptance probability of a $\mathsf{QMA}$ verifier $V_x$ is $\max_{|\psi\rangle} \| |1\...
Yupan Liu's user avatar
  • 488
5 votes

How can I show that $\mathsf{QMA}\subseteq \mathsf{PSPACE}$

Kitaev showed the following that gives the result: Kitaevs Theorem: $\mathsf{QMA} \subseteq \mathsf{P}^{\# \mathsf{P}} \subseteq \mathsf{PSPACE}$. Later it was shown an even stronger result: Kitaev ...
R.W's user avatar
  • 2,327
5 votes
Accepted

How do we understand Jordan's Lemma?

It means to find a basis for the Hilbert space that can be partitioned into singles and pairs of vectors which form one- and two-dimensional subspaces left invariant by the action of the projectors $\...
glS's user avatar
  • 24.1k
5 votes
Accepted

Quantum proof for the group non-membership problem

I think the idea of the proof is that if $|h\rangle$ can be shown to be orthogonal to $|\mathcal H\rangle$ then it would imply that that $h \not\in \mathcal{H}$. Otherwise, $h\in \mathcal{H}$. Not ...
glS's user avatar
  • 24.1k
4 votes

What classical public key cryptography protocols exist for which hacking is QMA complete or QMA hard?

Please start by reading my answer here. I believe you've mistaken the requirements for post-quantum crypto. If you use a scheme which is QMA-hard, then that means either your problem is QMA-complete (...
DaftWullie's user avatar
  • 57.1k
4 votes
Accepted

Upper Bounds for QMA Quantum Merlin Arthur, and QMA(k)

You probably want to check out the complexity zoo for known results. For example, the listing on QMA(2) states: It was shown in ABD+08 that a conjecture they call the Strong Amplification Conjecture ...
DaftWullie's user avatar
  • 57.1k
4 votes

Is verifying the solution to a QMA-complete problem efficient?

Unless QMA = NP (which is generally believed not to be the case - at least so I think), there are problems in QMA for which the proof (at least in part of the instances) cannot be efficiently checked ...
Norbert Schuch's user avatar
4 votes

Quantum proof for the group non-membership problem

This result concerns the black-box group model, which is a fairly standard model in computational group theory. It is intended to represent minimal assumptions on the groups we're working with. In the ...
John Watrous's user avatar
  • 5,703
3 votes

Complexity of Quantum Satisfiability vs Local Hamiltonians

"2QSAT+" can be defined in two different ways: You can define it such that you allow for general Hamiltonians, but you demand that for a "yes"-instance, the ground state has the ...
Norbert Schuch's user avatar
3 votes

The complexity of LH with constant gap

The reasoning is naively wrong: When talking about the Local Hamiltonian problem with a specific promise gap (or spectral gap), you need to fix the overall energy scale. Usually, this means that the ...
Norbert Schuch's user avatar
2 votes

Marriott-Watrous style amplification with a quantum input

QMA verification includes three registers, with appropriate bounds on the length of each register: $x$, a (classical) description of the (quantum) circuit used for verification, along with the ...
Mark Spinelli's user avatar
2 votes
Accepted

Quantum State Sanitizing

Then I realized it is not just that; if we ever want to compute a superposition over some artificial objects, it is almost inevitable to get your superposition with some components being non-sense ...
Mark Spinelli's user avatar
2 votes

Quantum Chemistry and Quantum Computing

You may be referring to works like Simulation of Chemical Isomerization Reaction Dynamics on a NMR Quantum Simulator (arXiv version). However, I'd say that in general the prediction of reaction ...
agaitaarino's user avatar
  • 3,817
2 votes
Accepted

The complexity of LH restricted to projectors

The standard Kitaev construction yields a Hamiltonian where the individual terms are projectors (up to energy shift & rescaling), each of which constrains the system to a subspace. Thus, the ...
Norbert Schuch's user avatar
2 votes
Accepted

If all terms of a local Hamiltonian commute, how hard is it to learn the ground state (energy)?

Much less is known about the complexity of commuting local Hamiltonians than one might think or hope. The best we know in the general case is that it is (1) NP-hard (as already classical local ...
Norbert Schuch's user avatar
1 vote
Accepted

Is verifying the solution to a QMA-complete problem efficient?

Indeed for the standard, conventional QMA-complete Local Hamiltonian problem, An all-powerful Merlin and a BQP-capable Arthur agree on a local Hamiltonian $\mathcal H$ acting on $n$ qubits; Merlin ...
Mark Spinelli's user avatar
1 vote

How can one cheat in Mahadev's classical verification protocol if one can find a "claw''?

I don't understand all of the details of the protocol, but to provide a tentative answer, in Mahadev's scheme the verifier (Vickey) is always purely classical, and only trades classical information ...
Mark Spinelli's user avatar
1 vote
Accepted

The complexity of LH with constant gap

In the standard survey LH is defined with normalization 1 on the single terms $h_{i}$. The actual promised gap $b-a$ for the least eigenvalue of the total hamiltonian $H=\sum_{i}^{m}h_{i}$ is referred ...
J.Ask's user avatar
  • 119
1 vote

On the probability of preparing of a uniform superposition by performing a controlled-multiplication and post-selecting $0$

CW from self-answer, and also because this is more of an extended comment than an answer. Let $A$ be the adjacency matrix of the Cayley graph of our group $\mathcal{H}$ of order $N$. Notice that $A$ ...
1 vote

Quantum Chemistry and Quantum Computing

No quantum computing approach has ever been successful for predicting a reaction rate or transition state that a classical computer could not already do. There are many quantum algorithms for solving ...
user1271772's user avatar
  • 13.6k
1 vote

Upper Bounds for QMA Quantum Merlin Arthur, and QMA(k)

Before talking about upper bounds for $\mathsf{QMA(k)}$, let us first concentrate on upper bounds for $\mathsf{QMA}$. Recall that the maximum acceptance probability of a $\mathsf{QMA}$ verifier $V_x$ ...
Yupan Liu's user avatar
  • 488

Only top scored, non community-wiki answers of a minimum length are eligible