Economic feasibility of mapping optimization problems onto second-order neural-network computation: conditions and fair comparison with conventional computing

The open research question left by the 1986-1987 Science exchange around Hopfield and Tank's article 'Computing with neural circuits: a model' and its Technical Comments cluster 'Computing with neural networks': under what general conditions is it economically feasible to transform an optimization problem into a neural-network computation via decomposition into second-order functionals (pairwise, quadratic energy terms realizable as synaptic connections) - for example in the required network size - and by what unified complexity framework can such analog, special-purpose network computation be fairly compared with conventional digital computation? Sparse coding for associative-memory capacity was executed by 1988 (Tsodyks-Feigel'man); polynomial-overhead second-order encodings of all NP problems are now standard (Lucas; Ising-machine literature); but the economic-feasibility characterization - encoding overhead in neurons, interconnections, precision, and connectivity, together with solution quality and time-to-solution - and a fair, unified comparison framework remain open, as the 2022-2025 literature on Ising machines (special-purpose hardware that physically minimizes pairwise quadratic energies) and neuromorphic benchmarking explicitly acknowledges.

Background

A Hopfield network is a system of $n$ neuron-like elements with symmetric pairwise synaptic connections; its dynamics monotonically decreases a quadratic "energy" function, so the stable states of the network are local minima of that energy. Hopfield (1982) showed that such a network implements content-addressable (associative) memory - stored patterns retrievable from partial cues - and estimated that only about $0.15n$ random patterns with 50% activity can be stored reliably. Hopfield and Tank extended the idea from memory to computation (1985; 1986): with graded-response (analog, continuously valued) neurons and symmetric couplings, one designs a quadratic energy whose minima correspond to good solutions of an optimization problem, and the network's collective dynamics performs a massively parallel local search. The essential device is the decomposition of the problem's cost function into second-order functionals - terms each involving products of at most two neuron-state variables, each realizable as a single synaptic connection - yielding a network energy of the form $E=\sum_{ij}T_{ij}V_iV_j+\sum_i I_iV_i$. They demonstrated the construction on the travelling salesman problem (TSP, the task of finding the shortest closed tour through a given set of cities; a canonical NP-hard problem - NP is the class of decision problems whose candidate solutions can be verified quickly, and NP-hard problems are at least as hard as every problem in NP), on analog-to-digital conversion, and related tasks, and argued that the approach is naturally suited to analog, special-purpose hardware rather than to von Neumann digital computers (the stored-program architecture of ordinary computers). The 1986 Science article prompted a Technical Comments exchange in Science 235 (6 March 1987) titled "Computing with neural networks" - comments by Carpenter, Cohen, and Grossberg; by Kohonen and Oja; and by Palm, with a Response by Hopfield and Tank. Palm's comment observed that the capacity debate had overlooked pattern coding: coding stored patterns as sparse 0-1 sequences (few ones per codeword), an idea going back to the non-holographic associative memory of Willshaw, Buneman, and Longuet-Higgins (1969), lets $z$ patterns with $x$ bits of information each be stored effectively in a network of $n=2\sqrt{x\cdot z}$ elements, so that $z$ can greatly exceed $n$ and network retrieval can need fewer operations than conventional pattern matching; Palm identified investigating sparse-coding techniques as the next step for the network approach to memory. The same exchange confronted the optimization program directly: it asked under what general conditions transforming an optimization problem into a neural-network computation via decomposition into second-order functionals is economically feasible - for example in the required network size - and observed that comparing network computation with conventional computation is difficult because the network approach is rooted in analog and special-purpose hardware and no unified complexity framework spans both.

What is known since: (a) the sparse-coding program was executed - Tsodyks and Feigel'man (1988) showed that low activity level substantially enhances storage capacity, and sparse coding is now standard in associative-memory theory; (b) the possibility of second-order encodings is settled in the complexity-theoretic sense - every NP problem (hence the standard world of combinatorial optimization) admits an Ising/QUBO (pairwise, second-order; QUBO, quadratic unconstrained binary optimization, denotes the same pairwise quadratic energy written as a polynomial over 0-1 variables) formulation with polynomial, at most cubic, size overhead (Lucas 2014; restated for Ising machines - special-purpose hardware that physically minimizes such a pairwise energy - by Mohseni, McMahon, and Byrnes 2022); (c) in practice the original constructions were fragile and expensive - the Hopfield-Tank TSP method resisted scaling to sizes of real interest (Wilson and Pawley 1988), and its $N$-city encoding uses $N^2$ neurons and on the order of $N^4$ pairwise connections, motivating high-order and compact variants (Samad and Harper 1990; Jayadeva et al. 1998) and a current literature on auxiliary-variable, bit-width, and connectivity overhead of QUBO/Ising encodings (Oku et al. 2022; Kalinin et al. 2023); (d) on comparison, the computational power of analog recurrent networks was characterized theoretically (Siegelmann and Sontag 1995), but the neuromorphic community still identifies the lack of standardized, fair benchmarks against conventional computation as an open gap (Schuman et al. 2022; Stewart et al. 2024). No later work supplies the source question's target: a characterization of when the second-order network transformation is economical, or a unified framework under which network and conventional computation of the same optimization problem can be fairly compared.

Problem Statement

As posed by the 1986-1987 Science exchange around Hopfield and Tank's article 'Computing with neural circuits: a model' and its Technical Comments cluster 'Computing with neural networks', and still unanswered: under what general conditions is it economically feasible to transform an optimization problem into a neural-network computation by decomposing its objective into second-order functionals (pairwise, quadratic energy terms, each realizable as a single synaptic connection), and how is such network computation to be compared with conventional digital computation?

The question has two linked aspects, in service of the single objective of deciding when network computation of optimization problems is worthwhile. The feasibility aspect concerns general conditions under which the second-order transformation is economical, where economy is measured in the network resources the transformation consumes: number of neurons, number and degree of interconnections, weight precision or bit-width, and connectivity, together with - where dynamics claims are made - time-to-solution and the quality of the solutions the network's descent dynamics reaches on its analog or special-purpose substrate. The comparison aspect concerns a basis on which network computation and conventional digital computation of the same optimization problem can be fairly compared, given that the network approach is rooted in analog and special-purpose hardware and no unified complexity framework spans both computing bases.

The source's phrase "economically feasible, for example in terms of the required network size" denotes, in the field conventions these sources established, network size as numbers of neurons and interconnections, later extended in the same literature to weight precision and connectivity constraints. The objective is the general economic-feasibility characterization of the second-order transformation, together with a unified framework for comparing network computation with conventional computation of the same optimization problem.

References

1. Hopfield, J. J., and D. W. Tank. "Response: Computing with Neural Networks." Science 235 (4793), 1228-1229 (1987). DOI 10.1126/science.235.4793.1228, https://doi.org/10.1126/science.235.4793.1228
2. Palm, G. "Computing with Neural Networks." Science 235 (4793), 1227b-1228b (1987). DOI 10.1126/science.235.4793.1227b, https://doi.org/10.1126/science.235.4793.1227b
3. Kohonen, T., and E. Oja. "Computing with Neural Networks." Science 235 (4793), 1227a (1987). DOI 10.1126/science.235.4793.1227a, https://doi.org/10.1126/science.235.4793.1227a
4. Carpenter, G. A., M. A. Cohen, and S. Grossberg. "Computing with Neural Networks." Science 235 (4793), 1226-1227 (1987). DOI 10.1126/science.3823881, https://doi.org/10.1126/science.3823881
5. Hopfield, J. J., and D. W. Tank. "Computing with Neural Circuits: A Model." Science 233 (4764), 625-633 (1986). DOI 10.1126/science.3755256, https://doi.org/10.1126/science.3755256 (the article commented on by the 1987 exchange)
6. Hopfield, J. J., and D. W. Tank. "'Neural' computation of decisions in optimization problems." Biological Cybernetics 52, 141-152 (1985). DOI 10.1007/BF00339943, https://doi.org/10.1007/BF00339943
7. Hopfield, J. J. "Neural networks and physical systems with emergent collective computational abilities." Proceedings of the National Academy of Sciences 79 (8), 2554-2558 (1982). DOI 10.1073/pnas.79.8.2554, https://doi.org/10.1073/pnas.79.8.2554
8. Willshaw, D. J., O. P. Buneman, and H. C. Longuet-Higgins. "Non-holographic associative memory." Nature 222, 960-962 (1969). DOI 10.1038/222960a0, https://doi.org/10.1038/222960a0
9. Tsodyks, M. V., and M. V. Feigel'man. "The enhanced storage capacity in neural networks with low activity level." Europhysics Letters 6 (2), 101-105 (1988). DOI 10.1209/0295-5075/6/2/002, https://doi.org/10.1209/0295-5075/6/2/002
10. Wilson, G. V., and G. S. Pawley. "On the stability of the Travelling Salesman Problem algorithm of Hopfield and Tank." Biological Cybernetics 58 (1), 63-70 (1988). DOI 10.1007/BF00363956, https://doi.org/10.1007/BF00363956
11. Samad, T., and P. Harper. "High-order Hopfield and Tank optimization networks." Parallel Computing 16, 287-292 (1990). DOI 10.1016/0167-8191(90)90066-I, https://doi.org/10.1016/0167-8191(90)90066-I
12. Jayadeva, S. C. Dutta Roy, and A. Chaudhary. "The compact analog neural network-model of a new paradigm for neural based optimization, and its hardware realization." Proceedings of IEEE TENCON '98, IEEE Region 10 International Conference on Global Connectivity in Energy, Computer, Communication and Control (1998). DOI 10.1109/TENCON.1998.797055, https://doi.org/10.1109/TENCON.1998.797055
13. Siegelmann, H. T., and E. D. Sontag. "On the computational power of neural nets." Journal of Computer and System Sciences 50 (1), 132-150 (1995). DOI 10.1006/jcss.1995.1013, https://doi.org/10.1006/jcss.1995.1013
14. Lucas, A. "Ising formulations of many NP problems." Frontiers in Physics 2, 5 (2014). DOI 10.3389/fphy.2014.00005, https://doi.org/10.3389/fphy.2014.00005
15. Oku, D., M. Tawada, S. Tanaka, and N. Togawa. "How to reduce the bit-width of an Ising model by adding auxiliary spins." IEEE Transactions on Computers 71, 223-234 (2022). DOI 10.1109/TC.2020.3045112, https://doi.org/10.1109/TC.2020.3045112
16. Mohseni, N., P. L. McMahon, and T. Byrnes. "Ising machines as hardware solvers of combinatorial optimization problems." Nature Reviews Physics 4, 363-379 (2022). DOI 10.1038/s42254-022-00440-8, https://doi.org/10.1038/s42254-022-00440-8
17. Kalinin, K. P., G. Mourgias-Alexandris, H. Ballani, N. G. Berloff, J. H. Clegg, D. Cletheroe, C. Gkantsidis, I. Haller, V. Lyutsarev, F. Parmigiani, L. Pickup, and A. Rowstron. "Analog Iterative Machine (AIM): using light to solve quadratic optimization problems with mixed variables." arXiv:2304.12594 (2023). arXiv ID 2304.12594, https://arxiv.org/abs/2304.12594
18. Nguyen, L., M.-A. Miri, R. J. Rupert, W. Dyk, S. Wu, N. Vrahoretis, I. Huang, M. Begliarbekov, N. Chancellor, U. Chukwu, P. Mahamuni, C. Martinez-Delgado, D. Haycraft, C. Spear, J. R. Huffman, Y. M. Sua, and Y.-P. Huang. "Entropy Computing, A Paradigm for Optimization in Open Photonic Systems." Communications Physics 8, 411 (2025). DOI 10.1038/s42005-025-02324-6, https://doi.org/10.1038/s42005-025-02324-6 (preprint arXiv:2407.04512, https://arxiv.org/abs/2407.04512)
19. Schuman, C. D., S. R. Kulkarni, M. Parsa, J. P. Mitchell, P. Date, and B. Kay. "Opportunities for neuromorphic computing algorithms and applications." Nature Computational Science 2, 10-19 (2022). DOI 10.1038/s43588-021-00184-y, https://doi.org/10.1038/s43588-021-00184-y
20. Stewart, T. C., C. Schuman, Y. Sandamirskaya, S. Furber, and G. Indiveri. "Focus on benchmarks for neuromorphic computing." Neuromorphic Computing and Engineering 4, 040202 (2024). DOI 10.1088/2634-4386/ad962f, https://doi.org/10.1088/2634-4386/ad962f