How is theoretical computer science getting united with physics? Phenomena like Quantum Computing uses Quantum Mechanics to be able to compute things, how are computers helping not just to model our equations but actually predict new equations, helping us to see the computational aspect of nature and how various things are being looked at from new perspectives using Computer Science?


closed as too broad by ACuriousMind, John Rennie, Kyle Kanos, Qmechanic May 24 '15 at 19:03

Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. Avoid asking multiple distinct questions at once. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ see also physics results in TCS tcs.se $\endgroup$ – vzn Dec 9 '13 at 19:28
  • 1
    $\begingroup$ In essence, everything is Physics... $\endgroup$ – Johannes Pille Sep 28 '14 at 14:17

this is a broad, complex, somewhat tricky question with many angles that an entire survey or book could be written on but unfortunately it seems one hasnt yet. heres a "grab bag" of some deep parallels noticed over the years that such a book might cover & "research leads" for further inquiry.

  • Modelling and simulation. as computing capability has increased, greater verisimilitude/fidelity can be be achieved in physics simulations. this has major implications in eg fluid/aerodynamics or also molecular dynamic simulations. the recent 2013 Nobel prize was awared for accurate molecular modelling algorithms. this is also used heavily in particle physics to classify particle traces and detect new particles. also significant progress/advances on the protein folding problem continues.

  • QM computing has an extremely tight coupling between the physical computing model and its theoretical capabilities. in some ways it seems a step away from the abstraction of the classic CS model of the Turing machine because the QM abstraction apparently holds most of the same dynamics as the QM reality (its not much of a simplication as is the TM). leaders in the QM field eg Wheeler have taken an increasingly information-centric view of QM physics. the breakthrough Shors algorithm seems to indicate that a strict analysis of the physical computing model is required to accurately measure the inherent computational complexity of a problem (in this case factoring).

  • a (half-century)-old famous/classic essay on the subject that deserves updating for the "algorithmic age": The unreasonable effectiveness of mathematics in the natural sciences by Wigner, 1960, where "algorithm" could nearly substitute for "mathematics" in the title and contents. the more modern parallel seems to be what is being called "the algorithmic lens" and has wide applicability across multiple sciences esp physics and bioinformatics.

  • the transition point phenomenon in NP complete problems and other CS problems. as outlined by Walsh its a broad phenomenon that has very deep ties to statistical physics phenomena. this has been esp. explored/pioneered by Mezard.

  • as already cited information entropy seems to have strong connections with physics entropy concepts and this link is an ongoing/active area of research. it appears that important CS problems related to complexity class separations are about an "order versus disorder" or "randomness" concept/phenomenon similar to entropy, eg as in the concept/paper Natural Proofs.

  • Rolf Landauers research shows deep connections between physics and information processing eg in limits of energy dissipation. "Rolf Landauer did more than anyone else to establish the physics of information processing as a serious subject for scientific inquiry" says Bennett.

  • 1
    $\begingroup$ to summarize, a lot of overlap/nexus between physics/CS is in the keyword "information" and also broad interpretation of the word "algorithm". also, DNA computing is an area of strong/emerging overlap. $\endgroup$ – vzn Dec 10 '13 at 17:49
  • $\begingroup$ see also formal notion for energy complexity of computational problems tcs.se $\endgroup$ – vzn Dec 17 '13 at 4:39
  • $\begingroup$ othe great figures that exemplify this synergy: nobel prize winning physicist feynman is the conceptual originator of QM computing, not any TCS figure! and wolfram with Phd physics is arguably one of the originators (along with fredkin) of "the algorithmic lens" now swirling through the sciences.... $\endgroup$ – vzn Jan 31 '14 at 19:11
  • $\begingroup$ deutsch is also a crosscutting figure at the founding of QM computing $\endgroup$ – vzn Feb 1 '14 at 20:24

There are numerous examples of people using genetic algorithms, for example, to optimize some output where an actual solution of the equation would be otherwise impossible. Information entropy, which is a generic computing concept, has some hold on statistical physics. But I cannot think of a case I have seen where a concept from cutting edge computer science informed a new physical theory directly. Advanced CS concepts typically end up as tools in a physicist's arsenal, or inform new discoveries, but I do not think a computer has predicted anything that would be generally regarded as "fundamental physics".


The link between Computer Science and Physics can be very subtle sometimes. For example, consider this article:


The point is the following. Consider a quantum algorithm in order to solve an NP-complete problem (i.e.: a hard problem, which is conjectured not to be solvable in polynomial time). Now, consider a classical simulation of that problem. Of course, the classical simulation is performed in a classical computer... and thus, it can not give the solution in polynomial time. Either it will fail, or it will take longer times. The article discusses a certain simulation technique for quantum computing, which is known to yield the correct results, but in unknown time. If we assume that NP-complete problems can not be solved in polynomial time (as conjectured), then "something" must prevent the classical simulation from doing so. In the discussed case, it must be the maximal entanglement achieved during the procedure, which must increase fast enough with the system size.

In conclusion: the paper extracts some physical predictions out of a computer science "conjecture". That is not as strange as it sounds, because theoretical computer science, and computational complexity are branches of mathematics.


Not the answer you're looking for? Browse other questions tagged or ask your own question.