Document Open Access Logo

New Hardness Results for the Permanent Using Linear Optics

Authors Daniel Grier, Luke Schaeffer

PDF
Thumbnail PDF

File

LIPIcs.CCC.2018.19.pdf
  • Filesize: 0.68 MB
  • 29 pages

Document Identifiers

Author Details

Daniel Grier
  • MIT, Cambridge, USA
Luke Schaeffer
  • MIT, Cambridge, USA

Funding

Both authors were supported by the Vannevar Bush Faculty Fellowship from the US Department of Defense. Part of this research was completed while visiting UT Austin.
  • Grier, Daniel: Supported by an NSF Graduate Research Fellowship under Grant No. 1122374.

Cite AsGet BibTex

Daniel Grier and Luke Schaeffer. New Hardness Results for the Permanent Using Linear Optics. In 33rd Computational Complexity Conference (CCC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 102, pp. 19:1-19:29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.CCC.2018.19

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Problems, reductions and completeness
Keywords
  • Permanent
  • Linear optics
  • #P-hardness
  • Orthogonal matrices

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. S. Aaronson. Quantum computing, postselection, and probabilistic polynomial-time. Proc. Roy. Soc. London, A461(2063):3473-3482, 2005. quant-ph/0412187. Google Scholar
  2. S. Aaronson. A linear-optical proof that the permanent is #P-hard. Proc. Roy. Soc. London, A467(2088):3393-3405, 2011. arXiv:1109.1674. Google Scholar
  3. S. Aaronson and A. Arkhipov. The computational complexity of linear optics. Theory of Computing, 9(4):143-252, 2013. Conference version in Proceedings of ACM STOC'2011. ECCC TR10-170, arXiv:1011.3245. Google Scholar
  4. S. Aaronson, D. Grier, and L. Schaeffer. The classification of reversible bit operations. arXiv preprint arXiv:1504.05155, 2015. Google Scholar
  5. Leonard M. Adleman, Jonathan DeMarrais, and Ming-Deh A. Huang. Quantum computability. SIAM J. Comput., 26(5):1524-1540, 1997. URL: http://dx.doi.org/10.1137/S0097539795293639.
  6. A. Ben-Dor and S. Halevi. Zero-one permanent is #P-complete, a simpler proof. In ISTCS, pages 108-117, 1993. Google Scholar
  7. S. J. Berkowitz. On computing the determinant in small parallel time using a small number of processors. Information processing letters, 18(3):147-150, 1984. Google Scholar
  8. M. Bremner, R. Jozsa, and D. Shepherd. Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy. Proc. Roy. Soc. London, A467(2126):459-472, 2010. arXiv:1005.1407. Google Scholar
  9. E. R. Caianiello. On quantum field theory, 1: explicit solution of Dyson’s equation in electrodynamics without use of Feynman graphs. Nuovo Cimento, 10:1634-1652, 1953. Google Scholar
  10. L. Chakhmakhchyan, N. J. Cerf, and R. Garcia-Patron. A quantum-inspired algorithm for estimating the permanent of positive semidefinite matrices. arXiv preprint arXiv:1609.02416, 2016. Google Scholar
  11. A. Drucker and R. de Wolf. Quantum proofs for classical theorems. Theory of Computing Graduate Surveys, pages 1-54, 2011. arXiv:0910.3376, ECCC TR03-048. Google Scholar
  12. S. Fenner, F. Green, S. Homer, and R. Pruim. Quantum NP is hard for PH. In Proceedings of 6th Italian Conference on theoretical Computer Science, pages 241-252. Citeseer, 1998. Google Scholar
  13. Stephen A. Fenner, Lance Fortnow, and Stuart A. Kurtz. Gap-definable counting classes. J. Comput. Syst. Sci., 48(1):116-148, 1994. URL: http://dx.doi.org/10.1016/S0022-0000(05)80024-8.
  14. Leonid Gurvits. On the complexity of mixed discriminants and related problems. In Joanna Jedrzejowicz and Andrzej Szepietowski, editors, Mathematical Foundations of Computer Science 2005, 30th International Symposium, MFCS 2005, Gdansk, Poland, August 29 - September 2, 2005, Proceedings, volume 3618 of Lecture Notes in Computer Science, pages 447-458. Springer, 2005. URL: http://dx.doi.org/10.1007/11549345_39.
  15. C. K. Hong, Z. Y. Ou, and L. Mandel. Measurement of subpicosecond time intervals between two photons by interference. Phys. Rev. Lett., 59(18):2044-2046, 1987. Google Scholar
  16. E. Knill. Quantum gates using linear optics and postselection. Physical Review A, 66(5), 2002. URL: http://dx.doi.org/10.1103/PhysRevA.66.052306.
  17. E. Knill, R. Laflamme, and G. J. Milburn. A scheme for efficient quantum computation with linear optics. Nature, 409:46-52, 2001. See also quant-ph/0006088. Google Scholar
  18. G. Kogan. Computing permanents over fields of characteristic 3: Where and why it becomes difficult. In Foundations of Computer Science, 1996. Proceedings., 37th Annual Symposium on, pages 108-114. IEEE, 1996. Google Scholar
  19. G. Kuperberg. How hard is it to approximate the Jones polynomial? Theory of Computing, 11(6):183-219, 2015. Google Scholar
  20. M. Nielsen and I. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, 2000. Google Scholar
  21. S. Rahimi-Keshari, A. P. Lund, and T. C. Ralph. What can quantum optics say about computational complexity theory? Physical review letters, 114(6):060501, 2015. Google Scholar
  22. Terry Rudolph. Simple encoding of a quantum circuit amplitude as a matrix permanent. Physical Review A, 80(5):054302, 2009. Google Scholar
  23. Rimli Sengupta. Cancellation is exponentially powerful for computing the determinant. Information Processing Letters, 62(4):177-181, 1997. Google Scholar
  24. Y. Shi. Both Toffoli and controlled-NOT need little help to do universal quantum computation. Quantum Information and Computation, 3(1):84-92, 2002. quant-ph/0205115. Google Scholar
  25. L. J. Stockmeyer. The complexity of approximate counting. In Proc. ACM STOC, pages 118-126, 1983. Google Scholar
  26. S. Toda. PP is as hard as the polynomial-time hierarchy. SIAM J. Comput., 20(5):865-877, 1991. Google Scholar
  27. Seinosuke Toda and Mitsunori Ogiwara. Counting classes are at least as hard as the polynomial-time hierarchy. SIAM J. Comput., 21(2):316-328, 1992. URL: http://dx.doi.org/10.1137/0221023.
  28. T. Toffoli. Reversible computing. In Proc. Intl. Colloquium on Automata, Languages, and Programming (ICALP), pages 632-644. Springer, 1980. Google Scholar
  29. L. Troyansky and N. Tishby. Permanent uncertainty: On the quantum evaluation of the determinant and the permanent of a matrix. In Proceedings of PhysComp, 1996. Google Scholar
  30. N. Tschebotareff. Die bestimmung der dichtigkeit einer menge von primzahlen, welche zu einer gegebenen substitutionsklasse gehören. Mathematische Annalen, 95(1):191-228, 1926. URL: http://dx.doi.org/10.1007/BF01206606.
  31. L. G. Valiant. The complexity of computing the permanent. Theoretical Comput. Sci., 8(2):189-201, 1979. Google Scholar
  32. Leslie G. Valiant. Completeness classes in algebra. In Michael J. Fischer, Richard A. DeMillo, Nancy A. Lynch, Walter A. Burkhard, and Alfred V. Aho, editors, Proceedings of the 11h Annual ACM Symposium on Theory of Computing, April 30 - May 2, 1979, Atlanta, Georgia, USA, pages 249-261. ACM, 1979. URL: http://dx.doi.org/10.1145/800135.804419.
  33. Leslie G. Valiant. Negation can be exponentially powerful. In Michael J. Fischer, Richard A. DeMillo, Nancy A. Lynch, Walter A. Burkhard, and Alfred V. Aho, editors, Proceedings of the 11h Annual ACM Symposium on Theory of Computing, April 30 - May 2, 1979, Atlanta, Georgia, USA, pages 189-196. ACM, 1979. URL: http://dx.doi.org/10.1145/800135.804412.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact