The class of problems that can be solved efficiently using physical means?

Question

By "physical means", I mean, for example, using water pouring down tubes, or combining chemicals, etc. Basically, using some experiment in the physical world to perform some computation. I'll call this physical computation.

As the simplest example, if I want to add the numbers 3 and 5, I could just pour 3mL into a cup and 5mL into the same cup, and measure how many mL I end up with.

I know that physical computation will probably not be completely precise, but ignore that, and assume that all experiments and measurements are carried out at their theoretical perfect precision. Another way to think about it is that we have a perfect physics simulator that's efficient up to real time.

Let the class of problems that can be solved efficiently (in a polynomial number of steps) through physical computation be called Phys-P.

My question is: what is Phys-P's relation with P? Are there problems that physical compututation can solve faster than traditional computation? Does leveraging nature and physics give you an exponential speed-up? I'd like to think yes, but I can't think of a particular NP-hard problem that physical computation would solve efficiently. Maybe something like how the structure of a crystal that grows (given some initial conditions) will solve TSP, or something like that.

If possible, I'd like to keep BQP (e.g. quantum computation) out of the discussion, and focus on running physical/chemical experiments.

Answer 1

It's not clear what "can be solved" actually means here. Let me explain with a real example.

It is known that NP-hard problems can be solved on an analog computer in polynomial time.

Suppose that you have a SAT problem in CNF with $m$ clauses and $n$ variables.

Define $c_{i,v}$ to equal $1$ if variable $v$ appears positively in clause $i$, $-1$ if variable $v$ appears negatively in clause $i$, and $0$ if it does not appear in clause $i$. So, for example, if this is clause $5$:

$$x_{3} \vee \bar{x}_{10} \vee x_{31}$$

Then $c_{5,3} = 1$, $c_{5,10} = -1$, $c_{5,31} = 1$, and for all other $j$, $c_{5,j} = 0$.

To find the solution to the SAT problem, we use spin variables $s_v$ where $s_v = -1$ if $x_v$ is false in a satisfying assignment, and $s_v = 1$ if $x_v$ is true in a satisfying assignment.

For each clause $j$ we define the function:

$$K_j(\vec{s}) = 2^{-k_j} \prod_{v} \left( 1 - s_v c_{j,v}\right)$$

where $k_j$ is the number of variables in clause $j$.

Notice that clause $j$ is satisfied exactly when $K_j(\vec{s}) = 0$. So this is a constrained optimisation problem, which has a standard solution by introducing Lagrange multiplier variables $a_j$. The Lagrangian is:

$$\mathcal{L}\left(\vec{a},\vec{s}\right) = \sum_{j} a_j K_j(\vec{s})^2$$

And a solution is any point where:

$$\nabla_{\vec{a},\vec{s}} \mathcal{L} = 0$$

The Lagrangian in this case is positive definite, so on an analog computer, you can solve this system using gradient descent. Make the variables $s_v$ and $a_j$ functions of time, and set up this system of differential equations:

$$\begin{eqnarray*}\frac{d s_v}{dt} & = & - \sum_{j} 2 a_j c_{j,v} \frac{K_j(\vec{s})^2}{1 - c_{j,v}s_{v}} \\ \frac{d a_j}{dt} & = & a_j K_j(\vec{s})\end{eqnarray*}$$

(Note that in the equations for $s_v$, you don't actually need circuitry to perform the division, since the divisor is a factor of $K_j$.)

This dynamical system, if implemented on an analog computer, will find the solution in polynomial time.

Oh, but there's a catch. There's always a catch. The formal solution for the Lagrange multiplier variables is

$$a_j(t) = a_j(0)\,e^{\int_{0}^{t} K_j\,dt'},$$

which is to say, the voltages become exponentially large over time if the problem is stiff.

So while SAT can indeed be solved in polynomial time on an analog computer, it's not clear that this computer is physically realisable in practice.

Answer 2

No one knows. The extended Church-Turing hypothesis is sometimes described as saying that the answer is Phys-P = BPP. This is a conjecture or hypothesis but it is not proven. The answer depends on the physics that underlies the universe. It is widely suspected (but not proven) that BPP = P. So, roughly speaking, the extended Church-Turing hypothesis amounts to saying that no physically realizable machine can give you more than a polynomial speedup.

We already know that the ECT is most likely not quite right, as we already believe that quantum physics is correct, not Newtonian physics. As a result, many expect that quantum computing is likely to disprove the ECT. But one can correct for this by conjecturing that Phys-P = BQP. As far as know, that conjecture could well be correct.

There are various exotic possibilities in which this hypothesis might be wrong. My favorite example is that, if time travel is possible, then we can compute anything in PSPACE in polynomial time. See Scott Aaronson's lecture notes or his earlier explanation. Alternatively, from a different perspective, if we live in a closed universe, then there is some constant upper bound on the maximum number of bits that can be stored in the universe ($10^{80}$ or something; the holographic bound), which implies that computation could be simulated by a finite-state machine -- not a very helpful point of view, and somewhat pedantic and nitpicky.

I suspect you might be interested in https://en.wikipedia.org/wiki/DNA_computing, even though it doesn't change the complexity class of what we can compute, and you might be interested in Scott Aaronson's comments on analog classical computers at https://scottaaronson.blog/?p=5517.