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 ...


4

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 complexity classes. For the question regarding whether we have a procedure of finding a witness of a $\mathsf{QCMA}$ instance or not. The short answer is not known. ...


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 ...


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 ...


1

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 the FCI problem with a polynomial number of quantum-computer gates, so there are many algorithms that show promise for building the high-accuracy potential ...


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