Journal
PROCEEDINGS OF THE ROYAL SOCIETY A-MATHEMATICAL PHYSICAL AND ENGINEERING SCIENCES
Volume 467, Issue 2136, Pages 3393-3405Publisher
ROYAL SOC
DOI: 10.1098/rspa.2011.0232
Keywords
bosons; permanent; quantum computing; valiant; #P-complete; linear optics
Categories
Funding
- National Science Foundation [0844626]
- DARPA
- Sloan Fellowship
- Direct For Computer & Info Scie & Enginr
- Division of Computing and Communication Foundations [0844626] Funding Source: National Science Foundation
Ask authors/readers for more resources
One of the crown jewels of complexity theory is Valiant's theorem that computing the permanent of an n x 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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available
Share Paper
