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 #Phard. 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 #Phardness 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 #Phard. Much like Aaronson's original proof, this implies that even a multiplicative approximation remains #Phard 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 #Phardness 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:119:29},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770699},
ISSN = {18688969},
year = {2018},
volume = {102},
editor = {Rocco A. Servedio},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8870},
URN = {urn:nbn:de:0030drops88702},
doi = {10.4230/LIPIcs.CCC.2018.19},
annote = {Keywords: Permanent, Linear optics, #Phardness, Orthogonal matrices}
}
2018
Keywords: 

Permanent, Linear optics, #Phardness, Orthogonal matrices 
Seminar: 

33rd Computational Complexity Conference (CCC 2018)

Issue date: 

2018 
Date of publication: 

2018 