Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [statistical-physics]

The tag has no usage guidance.

1
vote
0answers
95 views

Growth of random square lattice trees

Consider the problem of growing a random tree on a $L\times L$ square lattice of initially disconnected vertices, starting from an isolated vertex on one of the corners of the lattice and proceeding ...
3
votes
1answer
180 views

How to study the thermodynamics of 2 problems if reduction from $B$ to $A$ exists?

Peter Shor commented on this post: years of experience in theoretical computer science says that the thermodynamic behavior of two NP complete problems are in general not similar. What do we know ...
5
votes
2answers
710 views

Isn't it trivial to represent any classical Physics problem in a Spin-Glass format which is NP-Complete?

In the late 80's there were several efforts to use Spin-Glass models to formulate other computational problems such as: Protein Folding and Neural Networks. Wouldn't it be straight forward to reduce ...
12
votes
1answer
1k views

Entropy and computational complexity

There are researcher showing that erasing bit has to consume energy, now is there any research done on the average consumption of energy of algorithm with computational complexity $F(n)$? I guess, ...
2
votes
0answers
83 views

How does white noise on the output channels influence the training of a neural network?

Let $\rho(\sigma): \mathbb{R} \rightarrow \mathbb{R}$ be a probability density that is parametrized by a parameter vector $\sigma \in \mathbb{R}^s$ (for example the normal distribution where $s = 1$ ...
1
vote
0answers
95 views

Percolation probabilities

I have a finite undirected graph with a probability $p_e$ given for each edge $e$. This gives a random graph by removing each edge e with probability $1-p_e$ independently of the others. I'm ...
2
votes
0answers
117 views

Calculating the ground state of an Ising model with $\sigma_i = (0,1)$ spin state assignments (do Barahona & Istrail's NP-hardness results hold?)

In a typical Ising model, one has possible spin assignments of $\sigma_i = \pm 1$. However, one can also imagine a $q = 2$ Potts model generalization with spin assignments $\sigma_i = (0,1)$. Is ...
2
votes
0answers
201 views

Which complexity information of Ising model is more important?

In 1982, Barahona proved that finding the ground state of an Ising model is NP-hard. Later, in 2000, Istrail proved that it is NP-complete. When I look up the citations of these two papers using ...
2
votes
1answer
170 views

Proof of an Ising model representation of graph isomorphism problem

I am going to through Ising formulations of many NP problems by Andrew Lucas. In section $9$ on page 22, the author introduced an exact Ising formulation of the graph isomorphism problem. Given two ...
4
votes
1answer
517 views

Parameters of energy function for TSP

[This question was initially asked here. It went unanswered so I thought I should ask it in a different community.] I am reading this paper by Hopfield et al. On page six, the authors defined the ...
1
vote
1answer
195 views

Ising spin vs Pauli spin matrices [closed]

Are Ising spins scalar or operators? I am not a condensed matter physicist hence having some confusion. I have learnt about Ising models from adiabatic quantum algorithm papers. For example this ...
5
votes
1answer
4k views

Quantum annealing vs adiabatic quantum computation

I had this impression that quantum annealing is an optimization technique which may or may not produce exact solutions. On the other hand adiabatic quantum computation always gives exact solutions ...
3
votes
1answer
239 views

Background Required to understand Quantum Monte Carlo techniques?

I'm trying to decide whether or not to do a project for a professor. The project involves writing a survey paper (of high enough quality to get his research group up to speed for a peripheral project)...
5
votes
0answers
136 views

Sampling small separators

Is there a tractable way to define an approximate distribution over small vertex separators of the graph? I'm looking for something along the lines of [Bayati,2008], a way to turn a single "this is a ...
4
votes
0answers
228 views

Ising Model and Eulerian Subgraphs

Let $\mathcal{X}= \{1,-1\}^n$, $E$ the set of edges and $J$ some real-valued matrix. Van der Waerden's theorem gives constant $c$ and set of edge weights such that $$\sum_\mathbf{x\in \mathcal{X}} \...
6
votes
1answer
210 views

Ensemble of tree decompositions for all-pairs problem

Suppose we have a bounded tree width graph $G=\{E,V\}$ and want to count the number of self avoiding walks on $G$ passing through nodes $u$ and $v$ for all pairs of nodes $(u,v)$. For a single pair $(...
42
votes
16answers
3k views

Physics results in TCS?

It seems clear that a number of subfields of theoretical computer science have been significantly impacted by results from theoretical physics. Two examples of this are Quantum computation ...
6
votes
2answers
521 views

When is Ising partition function easy to compute?

Consider Ising model on graph $G$ with uniform coupling strength $J$ and magnetic field $h$. I say its partition function $Z$ is easy to compute if $Z$ can be deterministically computed to arbitrary ...
4
votes
2answers
197 views

Complexity of linearized Ising model at 0

Suppose $Z_G(J,h)$ is a partition function of Ising model with coupling $J$ and magnetic field $h$ on graph $G$. What is the complexity of finding the gradient of Z at $\mathbf{0}$? Specifically, if $...
29
votes
3answers
1k views

What does one mean by heuristic statistical physics arguments?

I have heard that there are heuristic arguments in statistical physics that yield results in probability theory for which rigorous proofs are either unknown or very difficult to arrive at. What is a ...