A linear-optical proof that the permanent is #P-hard
One of the crown jewels of complexity theory is Valiant's theorem that computing the permanent of an n×n matrix is #P-hard. Here we show that, by using the model of linear-optical quantum computing—and in particular, a universality theorem owing to Knill, Laflamme and Milburn—one can give a dif...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Royal Society, The
2012
|
| Online Access: | http://hdl.handle.net/1721.1/72067 https://orcid.org/0000-0003-1333-4045 |
| Summary: | One of the crown jewels of complexity theory is Valiant's theorem that computing the permanent of an n×n matrix is #P-hard. Here we show that, by using the model of linear-optical quantum computing—and in particular, a universality theorem owing to Knill, Laflamme and Milburn—one can give a different and arguably more intuitive proof of this theorem. |
|---|