Hot answers tagged

6

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 containment is known to hold. And the answer is that the reverse containment is not known to hold (and I think is not expected to hold). Of course, computational ...


4

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 (in which case, you can decrypt the message using a quantum computer, but not with a classical computer unless NP=QMA), or not (in which case you cannot decrypt ...


2

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 encoding. There must (or better be) some way to sanitize the input, right? But this is the point! We asume Merlin is powerful enough to prepare a uniform ...


2

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 implies that QMA(2) is contained in PSPACE. It was shown in HM13 that QMA(k) = QMA(2) for k >= 2. However we still do not know if QMA(2) = QMA. The best ...


1

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 rates or transition rates will be much more difficult compared with this 3-qubit job. Note a large amount of chemistry happens either in solution or in the solid ...


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