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 |
| _version_ | 1826199457696317440 |
|---|---|
| author | Aaronson, Scott |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Aaronson, Scott |
| author_sort | Aaronson, Scott |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T11:20:31Z |
| format | Article |
| id | mit-1721.1/72067 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T11:20:31Z |
| publishDate | 2012 |
| publisher | Royal Society, The |
| record_format | dspace |
| spelling | mit-1721.1/720672022-10-01T02:56:17Z A linear-optical proof that the permanent is #P-hard Aaronson, Scott Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Aaronson, Scott Aaronson, Scott 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. National Science Foundation (U.S.) (grant 0844626) United States. Defense Advanced Research Projects Agency (YFA grant) 2012-08-09T14:47:58Z 2012-08-09T14:47:58Z 2011-12 2011-04 Article http://purl.org/eprint/type/ConferencePaper 1471-2946 http://hdl.handle.net/1721.1/72067 Aaronson, S. “A linear-optical proof that the permanent is #P-hard.” Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 467.2136 (2011): 3393-3405. https://orcid.org/0000-0003-1333-4045 en_US http://dx.doi.org/10.1098/rspa.2011.0232 Proceedings of The Royal Society A: Mathematical, Physical and Engineering Sciences Creative Commons Attribution-Noncommercial-Share Alike 3.0 http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf Royal Society, The MIT web domain |
| spellingShingle | Aaronson, Scott A linear-optical proof that the permanent is #P-hard |
| title | A linear-optical proof that the permanent is #P-hard |
| title_full | A linear-optical proof that the permanent is #P-hard |
| title_fullStr | A linear-optical proof that the permanent is #P-hard |
| title_full_unstemmed | A linear-optical proof that the permanent is #P-hard |
| title_short | A linear-optical proof that the permanent is #P-hard |
| title_sort | linear optical proof that the permanent is p hard |
| url | http://hdl.handle.net/1721.1/72067 https://orcid.org/0000-0003-1333-4045 |
| work_keys_str_mv | AT aaronsonscott alinearopticalproofthatthepermanentisphard AT aaronsonscott linearopticalproofthatthepermanentisphard |