<p>There is <a href="http://eccc.hpi-web.de/report/2011/043/download">a recent paper</a> 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.</p>

CC BY-SA 3.0
2011-10-11T16:31:52.197Z
+1 for the analogy between the Quantum language and C++
Alessandro Cosentino
CC BY-SA 3.0
2011-10-10T09:50:24.673Z
2011-10-10T09:50:24.673Z
Lamine
<p>In my opinion, I like the following paper:</p>

<p><a href="http://dl.acm.org/citation.cfm?id=1060614">Katalin Friedl, Gabor Ivanyos, Miklos Santha. Efficient testing of groups. In STOC'05.</a></p>

<p>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.</p>

<p>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.</p>

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

CC BY-SA 3.0
2011-10-10T01:47:09.130Z
2011-10-10T01:47:09.130Z
Marcos Villagra
<p>Two very recent and interesting results:</p>

<ul>
<li><p>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).<br>
They use <em>quantum communication complexity</em> as a tool. See their <a href="http://arxiv.org/abs/1111.0837">paper</a> and <a href="http://gilkalai.wordpress.com/2011/12/07/projections-to-the-tsp-polytope/">Gil Kalai's blog post</a>. 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. </p></li>
<li><p>Andrew M. Childs, Shelby Kimmel and Robin Kothari used <em>quantum query complexity</em> to prove lower bounds for a very classical measure, which is the formula gate count of functions such as PARITY.
See their <a href="http://arxiv.org/abs/1112.0548">paper</a>.</p></li>
</ul>

CC BY-SA 3.0
2011-12-08T23:10:20.720Z
ah. totally awesome.
Suresh Venkat
CC BY-SA 3.0
2013-02-22T16:05:15.833Z
fyi the [Fiorini et al paper](http://dl.acm.org/citation.cfm?doid=2213977.2213988) 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](https://sites.google.com/site/plustcs/past-talks)
vzn
CC BY-SA 3.0
2011-12-08T20:02:07.610Z
2011-12-08T20:02:07.610Z
Alessandro Cosentino
<p>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 (<a href="http://arxiv.org/abs/quant-ph/0406127" rel="nofollow">http://arxiv.org/abs/quant-ph/0406127</a>).</p>

CC BY-SA 3.0
2013-11-11T18:27:52.193Z
2013-11-11T18:27:52.193Z
Ernesto Fagundes Galvao
<ul>
<li>see also <a href="https://www.simonsfoundation.org/quanta/20121218-classical-computing-embraces-quantum-ideas/" rel="nofollow noreferrer">classical computing embraces quantum ideas</a> a sort of semi-pop-science overview/survey of this classical/quantum dichotomy phenomenon by Wolchover writing for the Simons institute with some examples &amp; leads/refs.</li>
</ul>
<blockquote>
<p>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.</p>
<p>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.</p>
</blockquote>
<ul>
<li>another recent example that is similar to the research direction of the Razborov/Rudich <a href="http://en.wikipedia.org/wiki/Natural_proof" rel="nofollow noreferrer">Natural Proofs</a> (which related complexity class separations to breaking random number generators)</li>
</ul>
<p><a href="http://arxiv.org/pdf/1310.2885v1.pdf" rel="nofollow noreferrer">A quantum lower bound for distinguishing random functions from random permutations</a> Henry Yuen</p>
<blockquote>
<p>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...</p>
</blockquote>

CC BY-SA 3.0
2013-11-13T02:30:27.990Z
2013-11-13T02:30:27.990Z
2020-06-17T09:38:08.363Z
vzn
<p>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 <a href="http://arxiv.org/abs/0910.3376">Quantum Proofs for Classical Theorems</a> (A. Drucker, R. Wolf) gives a nice list of such problems, but surely there are many more. </p>

<p>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".</p>

<p>(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?)</p>

CC BY-SA 3.0
2011-10-10T16:24:12.590Z
At the [Barriers II Workshop](http://intractability.princeton.edu/blog/2010/02/workshop-barriers-ii/), Ronald deWolf gave a talk ([video](http://intractability.princeton.edu/videos/stream/videoplay.html?videofile=cs/Barriers10/dewolf.mp4) and [slides](http://www.cs.princeton.edu/~zdvir/barriers2/dewolf.pdf)) based on the paper you mention.
Tyson Williams
CC BY-SA 3.0
2012-08-13T15:11:09.763Z
this seems related, a classic problem that was recently extended to QM/entanglement with major fanfare? [Interactive proofs-- 10yr problem in TCS falls](http://www.sciencedaily.com/releases/2012/07/120730124236.htm)
vzn
CC BY-SA 3.0
2012-08-13T22:11:00.780Z
@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...
Robert Robere
<quantum-computing><big-list><proofs>
Quantum proofs of classical theorems
Marcin Kotowski
# Quantum proofs of classical theorems

(Asked by: username_0 on 2011-10-09)

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](http://arxiv.org/abs/0910.3376) (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?)

**Tags:** quantum-computing, big-list, proofs
> **Comments:**
> **username_1**: At the [Barriers II Workshop](http://intractability.princeton.edu/blog/2010/02/workshop-barriers-ii/), Ronald deWolf gave a talk ([video](http://intractability.princeton.edu/videos/stream/videoplay.html?videofile=cs/Barriers10/dewolf.mp4) and [slides](http://www.cs.princeton.edu/~zdvir/barriers2/dewolf.pdf)) based on the paper you mention.  
> **username_2**: this seems related, a classic problem that was recently extended to QM/entanglement with major fanfare? [Interactive proofs-- 10yr problem in TCS falls](http://www.sciencedaily.com/releases/2012/07/120730124236.htm)  
> **username_3**: @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...  

---

## 5 answers

### Answer by username_4 on 2011-10-10. Score: 14

There is [a recent paper](http://eccc.hpi-web.de/report/2011/043/download) 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.

> **Comments:**
> **username_5**: +1 for the analogy between the Quantum language and C++  

---

### Answer by username_6 on 2011-10-10. Score: 11

In my opinion, I like the following paper:

[Katalin Friedl, Gabor Ivanyos, Miklos Santha. Efficient testing of groups. In STOC'05.](http://dl.acm.org/citation.cfm?id=1060614)

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 by username_5 on 2011-12-08. Score: 9

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](http://arxiv.org/abs/1111.0837) and [Gil Kalai's blog post](http://gilkalai.wordpress.com/2011/12/07/projections-to-the-tsp-polytope/). 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](http://arxiv.org/abs/1112.0548).

> **Comments:**
> **username_7**: ah. totally awesome.  
> **username_2**: fyi the [Fiorini et al paper](http://dl.acm.org/citation.cfm?doid=2213977.2213988) 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](https://sites.google.com/site/plustcs/past-talks)  

---

### Answer by username_8 on 2013-11-11. Score: 2

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 by username_2 on 2013-11-13. Score: 1

* see also [classical computing embraces quantum ideas](https://www.simonsfoundation.org/quanta/20121218-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](http://en.wikipedia.org/wiki/Natural_proof) (which related complexity class separations to breaking random number generators)

[A quantum lower bound for distinguishing random functions from random permutations](http://arxiv.org/pdf/1310.2885v1.pdf) 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...


---

