Quantum proofs of classical theorems

Question

I'm interested in examples of problems where a theorem which seemingly has nothing to do with quantum mechanics/information (e.g. states something about purely classical objects) can nevertheless be proved using quantum tools. A survey Quantum Proofs for Classical Theorems (A. Drucker, R. Wolf) gives a nice list of such problems, but surely there are many more.

Particularly interesting would be examples where a quantum proof is not only possible, but also "more illuminating", in analogy with real and complex analysis, where putting a real problem in the complex setting often makes it more natural (e.g. geometry is simpler since $\mathbb{C}$ is algebraically closed etc.); in other words, classical problems for which quantum world is their "natural habitat".

(I'm not defining "quantumness" here in any precise sense and one could argue that all such arguments eventually boil down to linear algebra; well, one can also translate any argument using complex numbers to use only pairs of reals - but so what?)

Answer 1

There is a recent paper from Scott Aaronson which provides a new proof that the permanent is #P-hard. This proof is based on the model of linear-optical quantum computing and is more intuitive than that of Leslie Valiant.

Answer 2

In my opinion, I like the following paper:

Katalin Friedl, Gabor Ivanyos, Miklos Santha. Efficient testing of groups. In STOC'05.

Here they define a "classical" tester for abelian groups. However, first they start by giving a quantum tester, and then they go on by eliminating all the quantum parts.

What I like of this paper is that they use the quantum tester to gain intuition and use it to approach the problem. May sound a more difficult approach (start from quantum and the go classical), but the authors are well known researchers in quantum computing. So maybe for them its easier to start with that.

I would say that their main technical contribution is a tester for homomorphism, which they use to eliminate the quantum parts.

Answer 3

Two very recent and interesting results:

• Samuel Fiorini, Serge Massar, Sebastian Pokutta, Hans Raj Tiwary and Ronald de Wolf proved that "there exists no polynomial-size linear program (LP) whose associated polytope projects to the traveling salesman polytope, even if the LP is not required to be symmetric" (quoted from the abstract).
  They use quantum communication complexity as a tool. See their paper and Gil Kalai's blog post. Also notice Dave's comment under Gil Kalai's post. I haven't read the paper yet, so I can't comment myself about where and how quantum stuff are used.

• Andrew M. Childs, Shelby Kimmel and Robin Kothari used quantum query complexity to prove lower bounds for a very classical measure, which is the formula gate count of functions such as PARITY. See their paper.

Answer 4

As permanents give the probability amplitudes of measurement outcomes of bosons after they interfere in a linear interferometer, Scheel obtained a simple "quantum" proof that the absolute value of the permanent of any unitary matrix is 1 (http://arxiv.org/abs/quant-ph/0406127).

Answer 5

• 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...