Incoming links: Cryptography
A branch of mathematics that attempts to prove stuff about computers.
Unfortunately, all software engineers already know the answer to the useful theorems though (except perhaps notably for cryptography), e.g. all programmers obviously know that iehter P != NP or that this is unprovable or some other "for all practical purposes practice P != NP", even though they don't have proof.
And 99% of their time, software engineers are not dealing with mathematically formulatable problems anyways, which is sad.
The only useful "computer science" subset every programmer ever needs to know is:
- for arrays: dynamic array vs linked list
- for associative array: binary search tree vs hash table. See also Heap vs Binary Search Tree (BST). No need to understand the algorithmic details of the hash function, the NSA has already done that for you.
- don't use Bubble sort for sorting
- you can't parse HTML with regular expressions: stackoverflow.com/questions/1732348/regex-match-open-tags-except-xhtml-self-contained-tags/1732454#1732454 because of formal language theory
Funnily, due to the formalization of mathematics, mathematics can be seen as a branch of computer science, just like computer science can be seen as a branch of Mathematics!
Basically the opposite of security through obscurity, though slightly more focused on cryptography.
Bibliography:
- on Quanta Magazine: www.quantamagazine.org/cryptographys-future-will-be-quantum-safe-heres-how-it-will-work-20221109/ "Cryptography’s Future Will Be Quantum-Safe. Here’s How It Will Work." (2024)
Ciro Santilli would like to fully understand the statements and motivations of each the problems!
Easy to understand the motivation:
- Navier-Stokes existence and smoothness is basically the only problem that is really easy to understand the statement and motivation :-)
- p versus NP problem
Hard to understand the motivation!
- Riemann hypothesis: a bunch of results on prime numbers, and therefore possible applications to cryptographyOf course, everything of interest has already been proved conditionally on it, and the likely "true" result will in itself not have any immediate applications.As is often the case, the only usefulness would be possible new ideas from the proof technique, and people being more willing to prove stuff based on it without the risk of the hypothesis being false.
- Yang-Mills existence and mass gap: this one has to do with finding/proving the existence of a more decent formalization of quantum field theory that does not resort to tricks like perturbation theory and effective field theory with a random cutoff valueThis is important because the best theory of light and electrons (and therefore chemistry and material science) that we have today, quantum electrodynamics, is a quantum field theory.
This is the true key question: what are the most important algorithms that would be accelerated by quantum computing?
Some candidates:
- Shor's algorithm: this one will actually make humanity worse off, as we will be forced into post-quantum cryptography that will likely be less efficient than existing classical cryptography to implement
- quantum algorithm for linear systems of equations, and related application of systems of linear equations
- Grover's algorithm: speedup not exponential. Still useful for anything?
- Quantum Fourier transform: TODO is the speedup exponential or not?
- Deutsch: solves an useless problem
- NISQ algorithms
Do you have proper optimization or quantum chemistry algorithms that will make trillions?
Maybe there is some room for doubt because some applications might be way better in some implementations, but we should at least have a good general idea.
However, clear information on this really hard to come by, not sure why.
Whenever asked e.g. at: physics.stackexchange.com/questions/3390/can-anybody-provide-a-simple-example-of-a-quantum-computer-algorithm/3407 on Physics Stack Exchange people say the infinite mantra:
Lists:
- Quantum Algorithm Zoo: the leading list as of 2020
- quantum computing computational chemistry algorithms is the area that Ciro and many people are te most excited about is
- cstheory.stackexchange.com/questions/3888/np-intermediate-problems-with-efficient-quantum-solutions
- mathoverflow.net/questions/33597/are-there-any-known-quantum-algorithms-that-clearly-fall-outside-a-few-narrow-cla