Skip to main content

Questions tagged [statistical-physics]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1 vote
0 answers
146 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 ...
Omar Shehab's user avatar
1 vote
0 answers
99 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 ...
Omar Shehab's user avatar
1 vote
0 answers
113 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 ...
delete000's user avatar
  • 828
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 ...
0x90's user avatar
  • 463
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 ...
0x90's user avatar
  • 463
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, ...
XL _At_Here_There's user avatar
2 votes
0 answers
90 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$ ...
a_guest's user avatar
  • 121
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 ...
crestmods's user avatar
  • 111
2 votes
0 answers
135 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 ...
QIBincomplete's user avatar
2 votes
0 answers
345 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 ...
Omar Shehab's user avatar
3 votes
1 answer
281 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 ...
Omar Shehab's user avatar
4 votes
1 answer
637 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 ...
Omar Shehab's user avatar
1 vote
1 answer
278 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 ...
Omar Shehab's user avatar
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 ...
Omar Shehab's user avatar
3 votes
1 answer
301 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)...
Elliot JJ's user avatar
  • 745
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 ...
Yaroslav Bulatov's user avatar
4 votes
0 answers
247 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}} \...
Yaroslav Bulatov's user avatar
6 votes
1 answer
229 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 $(...
Yaroslav Bulatov's user avatar
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 ...
Joe Fitzsimons's user avatar
6 votes
2 answers
841 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 ...
Yaroslav Bulatov's user avatar
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 $...
Yaroslav Bulatov's user avatar
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 ...
arnab's user avatar
  • 7,020