19 votes
Accepted

Entropy and computational complexity

Yes, but most of the work so far (except very recently, see below) has focused on turning irreversible computations into reversible ones, thereby hoping to avoid any entropy generation. (Note: there ...
9 votes

Isn't it "trivial" to represent/reduce any classical physics problem into a Spin-Glass which is NP-Complete?

Classical physical problems often involve real-number positions or parameter values rather than values from a discrete set (such as the integers) which would be more typical of NP-complete problems. ...
8 votes
Accepted

Quantum annealing vs adiabatic quantum computation

Adiabatic quantum computing (AQC) is a computational model (as Peter said in the comments). Compare AQC with other models of computation such as: circuit-based quantum computing (CBQC) Adleman-...
6 votes

Is it possible to infer on the thermodynamics of two problems if a reduction from $B$ to $A$ exists?

With thermodynamics you have to be careful with the kind of reductions you allow, or (as Peter Shor pointed out) there can be essentially no thermodynamic relationship implied by a reduction. For ...
2 votes
Accepted

Isn't it "trivial" to represent/reduce any classical physics problem into a Spin-Glass which is NP-Complete?

It was only recently (2016) that it was proved mathematically that all of classical spin physics can be reproduced by the 2D Ising Model with linear terms (what physicists call "fields") with at most ...
2 votes

Physics results in TCS?

I know some examples in machine learning. It is very common for thermodynamic ideas to be used in this area: Boltzmann machine, Hopfield network, Wake-sleep algorithm. Markov Chain were initially used ...

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