License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CCC.2018.19
URN: urn:nbn:de:0030-drops-88702
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8870/
Grier, Daniel ;
Schaeffer, Luke
New Hardness Results for the Permanent Using Linear Optics
Abstract
In 2011, Aaronson gave a striking proof, based on quantum linear optics, that the problem of computing the permanent of a matrix is #P-hard. Aaronson's proof led naturally to hardness of approximation results for the permanent, and it was arguably simpler than Valiant's seminal proof of the same fact in 1979. Nevertheless, it did not show #P-hardness of the permanent for any class of matrices which was not previously known. In this paper, we present a collection of new results about matrix permanents that are derived primarily via these linear optical techniques.
First, we show that the problem of computing the permanent of a real orthogonal matrix is #P-hard. Much like Aaronson's original proof, this implies that even a multiplicative approximation remains #P-hard to compute. The hardness result even translates to permanents of orthogonal matrices over the finite field F_{p^4} for p != 2, 3. Interestingly, this characterization is tight: in fields of characteristic 2, the permanent coincides with the determinant; in fields of characteristic 3, one can efficiently compute the permanent of an orthogonal matrix by a nontrivial result of Kogan.
Finally, we use more elementary arguments to prove #P-hardness for the permanent of a positive semidefinite matrix. This result shows that certain probabilities of boson sampling experiments with thermal states are hard to compute exactly, despite the fact that they can be efficiently sampled by a classical computer.
BibTeX - Entry
@InProceedings{grier_et_al:LIPIcs:2018:8870,
author = {Daniel Grier and Luke Schaeffer},
title = {{New Hardness Results for the Permanent Using Linear Optics}},
booktitle = {33rd Computational Complexity Conference (CCC 2018)},
pages = {19:1--19:29},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-069-9},
ISSN = {1868-8969},
year = {2018},
volume = {102},
editor = {Rocco A. Servedio},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2018/8870},
URN = {urn:nbn:de:0030-drops-88702},
doi = {10.4230/LIPIcs.CCC.2018.19},
annote = {Keywords: Permanent, Linear optics, #P-hardness, Orthogonal matrices}
}
|
Keywords: |
|
Permanent, Linear optics, #P-hardness, Orthogonal matrices |
|
Collection: |
|
33rd Computational Complexity Conference (CCC 2018) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
04.06.2018 |
