Questions tagged [statistical-physics]
The statistical-physics tag has no usage guidance.
22 questions
48
votes
17
answers
4k
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
...
- 13.8k
29
votes
3
answers
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 ...
- 7,030
16
votes
1
answer
2k
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, ...
- 1,071
9
votes
1
answer
6k
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 ...
- 661
8
votes
2
answers
1k
views
Isn't it "trivial" to represent/reduce any classical physics problem into a Spin-Glass which is NP-Complete?
In the late 80's there were several highly cited efforts to use Spin-Glass models to formulate other computational problems such as: Protein Folding and Neural Networks.
Isn't it straight forward to ...
- 463
8
votes
2
answers
889
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,731
6
votes
1
answer
230
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 $(...
- 4,731
5
votes
1
answer
368
views
Is it possible to infer on the thermodynamics of two problems if a 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 can we say ...
- 463
5
votes
0
answers
142
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,731
4
votes
1
answer
639
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 ...
- 661
4
votes
2
answers
261
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 $...
- 4,731
4
votes
0
answers
248
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}} \...
- 4,731
3
votes
1
answer
286
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 ...
- 661
3
votes
1
answer
310
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)...
- 745
2
votes
0
answers
93
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$ ...
- 121
2
votes
0
answers
139
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
0
answers
349
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 ...
- 661
1
vote
1
answer
285
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 ...
- 661
1
vote
0
answers
166
views
Computational complexity of higher order cumulants
From Wikipedia:
In probability theory and statistics, the cumulants κn of a probability distribution are a set of quantities that provide an alternative to the moments of the distribution. Any two ...
- 661
1
vote
0
answers
102
views
Software tool to generate the Ising model for random $k$-SAT problems
Is there a software tool available to study the phase transition of the underlying Ising model for a given class of random $k$-SAT problems? I am basically asking whether the framework presented in ...
- 661
1
vote
0
answers
115
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 ...
- 848
1
vote
0
answers
105
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 ...
- 111