- see also classical computing embraces quantum ideas a sort of semi-pop-science overview/survey of this classical/quantum dichotomy phenomenon by Wolchover writing for the Simons institute with some examples & leads/refs.
In recent years, quantum ideas have helped researchers prove the security of promising data encryption schemes called lattice-based cryptosystems, some applications of which can shroud users’ sensitive information, such as DNA, even from the companies that process it. A quantum computing proof also led to a formula for the minimum length of error-correcting codes, which are safeguards against data corruption.
Quantum ideas have also inspired a number of important theoretical results, such as a refutation of an old, erroneous algorithm that claimed to efficiently solve the famously difficult traveling salesman problem, which asks how to find the fastest route through multiple cities.
- another recent example that is similar to the research direction of the Razborov/Rudich Natural Proofs (which related complexity class separations to breaking random number generators)
A quantum lower bound for distinguishing random functions from random permutations Henry Yuen
The problem of distinguishing between a random function and a random permutation on a domain of size N is important in theoretical cryptography, where the security of many primitives depend on the problem’s hardness. We study the quantum query complexity of this problem...
