What is the most efficient non-quantum computer that can be built?

Question

I am aware of two models of computation, neither of which describe the optimal computer we can build:

1. Turing machine: This model is not optimal due to the head having to travel a large distance taking time $O(n)$ to access memory at address $n$.
2. Random-access machine: This model is unrealistic because it assumes constant-time memory access, but due to the speed of light limit, the best we can do is $O(\sqrt[3]{n})$ by making our memory an infinite 3D grid of bits.

I'm looking for the most efficient model of computation that describes an actual computer that could be built using only classical physics. The computer can be of infinite size, but all the input and output must be read and written at a single point in space.

One option I can imagine would be to have an infinite 3D grid of random-access machines, each of which with a finite amount of memory, and the ability to communicate with its six neighboring machines. Here, the machine could read a problem in $O(n)$ and split it into subproblems that it distributes to surrounding machines (though not infinitely many, as the speed of light limits to how many machines the problem can be sent before it becomes more efficient to just solve it locally). Is something like this optimal?

Answer 1

One way to formalize this, advocated by Dan Bernstein in several of his papers, is via the price-performance ratio: the cost of a machine to solve the problem (e.g., measured in dollars) divided by its performance (the number of computations/problems solved per second). Equivalently, this is the cost of the machine multiplied by the time to solve the problem.

For instance, you can work in the circuit model. Then you can measure the price-performance ratio as the product $AT$, where $A$ is the area of the circuit (a proxy for the cost of the circuit) and $T$ is the time it takes for the circuit to solve one instance of the problem.

See, e.g., https://cr.yp.to/nfscircuit/opcost.html, https://cr.yp.to/nfscircuit/exactcost.html.

You might also be interested in the "full cost" model advocated by cryptographers like Michael Wiener and others. For more reading, see, e.g.,

The Full Cost of Cryptanalytic Attacks, Michael J. Wiener.