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?)

  • 6
    $\begingroup$ At the Barriers II Workshop, Ronald deWolf gave a talk (video and slides) based on the paper you mention. $\endgroup$ – Tyson Williams Oct 10 '11 at 16:24
  • $\begingroup$ this seems related, a classic problem that was recently extended to QM/entanglement with major fanfare? Interactive proofs-- 10yr problem in TCS falls $\endgroup$ – vzn Aug 13 '12 at 15:11
  • 1
    $\begingroup$ @TysonWilliams I remember Ronald's talk, and I asked him if there were any such results of a more combinatorial nature. He said that there wasn't too much... $\endgroup$ – Robert Robere Aug 13 '12 at 22:11

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.

  • $\begingroup$ +1 for the analogy between the Quantum language and C++ $\endgroup$ – Alessandro Cosentino Oct 11 '11 at 16:31

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.


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.

  • 5
    $\begingroup$ ah. totally awesome. $\endgroup$ – Suresh Venkat Dec 8 '11 at 23:10
  • $\begingroup$ fyi the Fiorini et al paper is regarded as best in 2012 complexity theory by Fortnow, Gasarch, & Lipton on their blogs for resolving a 2-decade old conjecture by Yannakakis related to $P\stackrel{?}{=}NP$. see also TCS+ google video talk on it by coauthor de Wolf $\endgroup$ – vzn Feb 22 '13 at 16:05

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

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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