×

The computational complexity of linear optics. (English) Zbl 1298.81046

Summary: We give new evidence that quantum computers – moreover, rudimentary quantum computers built entirely out of linear-optical elements – cannot be efficiently simulated by classical computers. In particular, we define a model of computation in which identical photons are generated, sent through a linear-optical network, then nonadaptively measured to count the number of photons in each mode. This model is not known or believed to be universal for quantum computation, and indeed, we discuss the prospects for realizing the model using current technology. On the other hand, we prove that the model is able to solve sampling problems and search problems that are classically intractable under plausible assumptions. Our first result says that, if there exists a polynomial-time classical algorithm that samples from the same probability distribution as a linear-optical network, then \(\mathsf P^{\mathsf{\#P}}=\mathsf{BPP}^{\mathsf{NP}}\), and hence the polynomial hierarchy collapses to the third level. Unfortunately, this result assumes an extremely accurate simulation. Our main result suggests that even an approximate or noisy classical simulation would already imply a collapse of the polynomial hierarchy. For this, we need two unproven conjectures: the Permanent-of-Gaussians Conjecture, which says that it is \(\mathsf{\#P}\)-hard to approximate the permanent of a matrix \(A\) of independent \(\mathcal N( 0,1)\) Gaussian entries, with high probability over \(A\); and the Permanent Anti-Concentration Conjecture, which says that \(|\operatorname{Per}(A)|\geq\sqrt{n!}/\operatorname{poly}(n)\) with high probability over \(A\). We present evidence for these conjectures, both of which seem interesting even apart from our application. This paper does not assume knowledge of quantum optics. Indeed, part of its goal is to develop the beautiful theory of noninteracting bosons underlying our model, and its connection to the permanent function, in a self-contained way accessible to theoretical computer scientists.

MSC:

81P68 Quantum computation
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
68Q12 Quantum algorithms and complexity in the theory of computing
78A10 Physical optics
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] [1] SCOTTAARONSON: Algorithms for Boolean function query properties.SIAM J. Comput., 32(5):1140–1157, 2003. [doi:10.1137/S0097539700379644]173
[2] [2] SCOTTAARONSON: Quantum computing, postselection, and probabilistic polynomial-time. Proc. Roy. Soc. A, 461(2063):3473–3482, 2005. Preprint atarXiv. [doi:10.1098/rspa.2005.1546]150, 159,162,175,179
[3] [3] SCOTTAARONSON: BQP and the polynomial hierarchy. In Proc. 42nd STOC, pp. 141–150. ACM Press, 2010. Preprint atarXiv. [doi:10.1145/1806689.1806711]150,160,161
[4] [4] SCOTTAARONSON: The equivalence of sampling and searching. In 6th Internat. Comp. Sci. Symp. in Russia (CSR’11), pp. 1–14. Springer, 2011. Available atECCC. Preprint atarXiv. [doi:10.1007/978-3-642-20712-9_1]151,163
[5] [5] SCOTTAARONSON ANDDANIELGOTTESMAN: Improved simulation of stabilizer circuits. Phys. Rev. A, 70(5):052328, 2004. Preprint atarXiv. [doi:10.1103/PhysRevA.70.052328]156,158
[6] [6] DANIELS. ABRAMS ANDSETHLLOYD: Simulation of many-body Fermi systems on a universal quantum computer.Phys. Rev. Lett., 79(13):2586–2589, 1997.Preprint atarXiv. [doi:10.1103/PhysRevLett.79.2586]174
[7] [7] DORITAHARONOV ANDMICHAELBEN-OR: Fault-tolerant quantum computation with constant error rate. SIAM J. Comput., 38(4):1207–1282, 2008. Preliminary version inSTOC’97. Preprint at arXiv. [doi:10.1137/S0097539799359385]146,202
[8] [8] SANJEEVARORA, ARNABBHATTACHARYYA, RAJSEKARMANOKARAN,ANDSUSHANT SACHDEVA: Testing permanent oracles - revisited. In Proc. 16th Internat. Workshop on Randomization and Computation (RANDOM’12), pp. 362–373, 2012. Available atECCC. Preprint at arXiv. [doi:10.1007/978-3-642-32512-0_31]205,228,237
[9] [9] STEPHEND. BARTLETT ANDBARRYC. SANDERS: Requirement for quantum computation. J. Modern Optics, 50(15-17):2331–2340, 2003. Preprint atarXiv. [doi:10.1080/09500340308233564] 156,157,199
[10] [10] CARLOW. J. BEENAKKER, DAVIDP. DIVINCENZO, CLIVEEMARY,ANDMARCOKINDERMANN: Charge detection enables free-electron quantum computation. Phys. Rev. Lett., 93(2):020501, 2004. Preprint atarXiv. [doi:10.1103/PhysRevLett.93.020501]159 THEORY OFCOMPUTING, Volume 9 (4), 2013, pp. 143–252246 THECOMPUTATIONALCOMPLEXITY OFLINEAROPTICS
[11] [11] ETHANBERNSTEIN ANDUMESHVAZIRANI: Quantum complexity theory. SIAM J. Comput., 26(5):1411–1473, 1997. Preliminary version inSTOC’93. [doi:10.1137/S0097539796300921]146, 159
[12] [12] MICHAELJ. BREMNER, RICHARDJOZSA,ANDDANJ. SHEPHERD: Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy. Proc. Roy. Soc. A, 467(2126):459–472, 2011. Preprint atarXiv. [doi:10.1098/rspa.2010.0301]149,150,159,160, 179,236,246
[13] [13] MATTHEWA. BROOME, ALESSANDROFEDRIZZI, SALEHRAHIMI-KESHARI, JUSTINDOVE, SCOTTAARONSON, TIMOTHYC. RALPH,ANDANDREWG. WHITE: Photonic boson sampling in a tunable circuit. Science, 2012 (online). Preprint atarXiv. [doi:10.1126/science.1231440]154, 200
[14] [14] HARRYBUHRMAN, RICHARDCLEVE, RONALD DEWOLF,ANDCHRISTOFZALKA: Bounds for small-error and zero-error quantum algorithms. In Proc. 40th FOCS, pp. 358–368. IEEE Comp. Soc. Press, 1999. Preprint atarXiv. [doi:10.1109/SFFCS.1999.814607]233
[15] [15] EDUARDOR. CAIANIELLO: On quantum field theory, I: explicit solution of Dyson’s equation in electrodynamics without use of Feynman graphs. Nuovo Cimento, 10(12):1634–1652, 1953. [doi:10.1007/BF02781659]158
[16] [16] DAVIDM. CEPERLEY: An overview of quantum Monte Carlo methods. Reviews in Mineralogy and Geochemistry, 71(1):129–135, 2010. [doi:10.2138/rmg.2010.71.6]159
[17] [17] RICHARDCLEVE ANDJOHNWATROUS: Fast parallel circuits for the quantum Fourier transform. In Proc. 41st FOCS, pp. 526–536. IEEE Comp. Soc. Press, 2000. Preprint atarXiv. [doi:10.1109/SFCS.2000.892140]146
[18] [18] KEVINP. COSTELLO ANDVANH. VU: Concentration of random determinants and permanent estimators.SIAM J. Discrete Math., 23(3):1356–1371, 2009.Preprint atarXiv. [doi:10.1137/080733784]221
[19] [19] ANDREACRESPI, ROBERTOOSELLAME, ROBERTARAMPONI, DANIELJ. BROD, ERNESTOF. GALVÃO, NICOLÒSPAGNOLO, CHIARAVITELLI, ENRICOMAIORINO, PAOLOMATALONI, ANDFABIOSCIARRINO: Experimental boson sampling in arbitrary integrated photonic circuits. 2012. [arXiv:1212.2783]154,200
[20] [20] CONSTANTINOSDASKALAKIS, PAULW. GOLDBERG,ANDCHRISTOSH. PAPADIMITRIOU: The complexity of computing a Nash equilibrium.Commun. ACM, 52(2):89–97, 2009. [doi:10.1145/1461928.1461951]163
[21] [21] CONSTANTINOSDASKALAKIS, PAULW. GOLDBERG,ANDCHRISTOSH. PAPADIMITRIOU: The complexity of computing a Nash equilibrium. SIAM J. Comput., 39(1):195–259, 2009. Preliminary version inSTOC’06. [doi:10.1137/070699652]163 THEORY OFCOMPUTING, Volume 9 (4), 2013, pp. 143–252247 SCOTTAARONSON ANDALEXARKHIPOV
[22] [22] GEORGYP. EGORYCHEV: Proof of the van der Waerden conjecture for permanents. Sibirsk. Mat. Zh., 22(6):65–71, 1981. English translation in Siberian Math. J. 22 (6), pp. 854-859, 1981. [doi:10.1007/BF00968054]228
[23] [23] DMITRYI. FALIKMAN: Proof of the van der Waerden conjecture regarding the permanent of a doubly stochastic matrix. Mat. Zametki, 29(6):931–938, 1981. English translation in Math. Notes 29 (6), pp. 475-479, 1981. [doi:10.1007/BF01163285]228
[24] [24] BILLFEFFERMAN ANDCHRISUMANS: Pseudorandom generators and the BQP vs. PH problem. 2010. [arXiv:1007.0305]150
[25] [25] STEPHENFENNER, FREDERICGREEN, STEVENHOMER,ANDRANDALLPRUIM: Determining acceptance possibility for a quantum computation is hard for the polynomial hierarchy. Proc. Roy. Soc. A, 455(1991):3953–3966, 1999. Preprint atarXiv. [doi:10.1098/rspa.1999.0485]159
[26] [26] RICHARDP. FEYNMAN: Simulating physics with computers. Int. J. Theoretical Physics, 21(67):467–488, 1982. [doi:10.1007/BF02650179]174
[27] [27] LANCEFORTNOW ANDJOHND. ROGERS: Complexity limitations on quantum computation. J. Comput. System Sci., 59(2):240–252, 1999. Preliminary version inCCC’98. Preprint atarXiv. [doi:10.1006/jcss.1999.1651]237
[28] [28] PETERGEMMELL, RICHARDJ. LIPTON, RONITTRUBINFELD, MADHUSUDAN,ANDAVI WIGDERSON: Self-testing/correcting for polynomials and for approximate functions. In Proc. 23rd STOC, pp. 33–42. ACM Press, 1991. [doi:10.1145/103418.103429]229
[29] [29] PETERGEMMELL ANDMADHUSUDAN: Highly resilient correctors for polynomials. Inform. Process. Lett., 43(4):169–174, 1992. [doi:10.1016/0020-0190(92)90195-2]229
[30] [30] VIACHESLAVL. GIRKO: A refinement of the Central Limit Theorem for random determinants. Teor. Veroyatnost. i Primenen, 42(1):63–73, 1997. Translation in Theory Probab. Appl 42 (1) (1998), 121-129. [doi:10.1137/S0040585X97975939]221
[31] [31] CHRISD. GODSIL ANDIVANGUTMAN: On the matching polynomial of a graph. In Algebraic Methods in Graph Theory I, pp. 241–249. North Holland, 1981.219
[32] [32] DANIELGOTTESMAN, ALEXEIKITAEV,ANDJOHNPRESKILL: Encoding a qubit in an oscillator. Phys. Rev. A, 64(1):012310, 2001. Preprint atarXiv. [doi:10.1103/PhysRevA.64.012310]155,156
[33] [33] LEONIDGURVITS: On the complexity of mixed discriminants and related problems. In 30th Internat. Symp. Mathematical Foundations of Computer Science (MFCS’05), pp. 447–458. Springer, 2005. [doi:10.1007/11549345_39]153,157,164,228,239,240
[34] [34] YENJOHAN, LANEA. HEMASPAANDRA,ANDTHOMASTHIERAUF: Threshold computation and cryptographic security. SIAM J. Comput., 26(1):59–78, 1997. Preliminary version inISAAC’93. [doi:10.1137/S0097539792240467]162 THEORY OFCOMPUTING, Volume 9 (4), 2013, pp. 143–252248 THECOMPUTATIONALCOMPLEXITY OFLINEAROPTICS
[35] [35] JOHANHÅSTAD: Computational Limitations for Small Depth Circuits. MIT Press, 1987.160
[36] [36] C. K. HONG, ZHE-YUOU,ANDLEONARDMANDEL: Measurement of subpicosecond time intervals between two photons by interference.Phys. Rev. Lett., 59(18):2044–2046, 1987. [doi:10.1103/PhysRevLett.59.2044]158,196,200
[37] [37] MARKJERRUM, ALISTAIRSINCLAIR,ANDERICVIGODA: A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries. J. ACM, 51(4):671–697, 2004. Preliminary version inSTOC’01. [doi:10.1145/1008731.1008738]148,175,228
[38] [38] TIEFENGJIANG: How many entries of a typical orthogonal matrix can be approximated by independent normals? Ann. Probab., 34(4):1497–1529, 2006. [doi:10.1214/009117906000000205] 183,200,246
[39] [39] STEPHENP. JORDAN: Permutational quantum computing. Quantum Information & Computation, 10(5):470–497, 2010. Preprint atarXiv. [ACM:2011369]157 · Zbl 1237.81051
[40] [40] SUBHASHKHOT: On the Unique Games Conjecture. In Proc. 25th IEEE Conf. on Computational Complexity (CCC’10), pp. 99–121. IEEE Comp. Soc. Press, 2010. [doi:10.1109/CCC.2010.19]152
[41] [41] EMANUELKNILL: Fermionic linear optics and matchgates. 2001. [arXiv:quant-ph/0108033]158
[42] [42] EMANUELKNILL ANDRAYMONDLAFLAMME: Power of one bit of quantum information. Phys. Rev. Lett., 81(25):5672–5675, 1998. Preprint atarXiv. [doi:10.1103/PhysRevLett.81.5672]157
[43] [43] EMANUELKNILL, RAYMONDLAFLAMME,ANDGERARDJ. MILBURN: A scheme for efficient quantum computation with linear optics. Nature, 409(6816):46–52, 2001. See alsoarXiv:quantph/0006088. [doi:10.1038/35051009]150,155,156,157,175,179,180,181
[44] [44] EMANUELKNILL, RAYMONDLAFLAMME,ANDWOJCIECHH. ZUREK: Resilient quantum computation. Science, 279(5349):342–345, 1998. Preprint atarXiv. [doi:10.1126/science.279.5349.342] 146,202
[45] [45] KENNETHLANGE: Applied Probability. Springer, 2003.224
[46] [46] YUANLIANGLIM ANDALMUTBEIGE: Generalized Hong-Ou-Mandel experiments with bosons and fermions. New J. Phys., 7(155):1–10, 2005. Preprint atarXiv. [doi:10.1088/1367-2630/7/1/155] 158
[47] [47] RICHARDJ. LIPTON: New directions in testing. In Distributed Computing and Cryptography, pp. 191–202. AMS, 1991.153,228,229
[48] [48] BRAHIMLOUNIS ANDMICHELORRIT: Single-photon sources. Reports on Progress in Physics, 68(5):1129–1179, 2005. [doi:10.1088/0034-4885/68/5/R04]199
[49] [49] CHRISTIANMASTRODONATO ANDRODERICHTUMULKA: Elementary proof for asymptotics of large Haar-distributed unitary matrices. Letters in Mathematical Physics, 82(1):51–59, 2007. Preprint atarXiv. [doi:10.1007/s11005-007-0194-7]184 THEORY OFCOMPUTING, Volume 9 (4), 2013, pp. 143–252249 SCOTTAARONSON ANDALEXARKHIPOV
[50] [50] MICHAELA. NIELSEN ANDISAACL. CHUANG: Quantum Computation and Quantum Information. Cambridge University Press, 2000.156,174
[51] [51] RAMAMOHANPATURI: On the degree of polynomials that approximate symmetric Boolean functions. In Proc. 24th STOC, pp. 468–474. ACM Press, 1992. [doi:10.1145/129712.129758]233
[52] [52] DÉNESPETZ ANDJÚLIARÉFFY: On asymptotics of large Haar distributed unitary matrices.Periodica Mathematica Hungarica, 49(1):103–117, 2004.Preprint atarXiv. [doi:10.1023/B:MAHU.0000040542.56072.ab]184
[53] [53] DÉNÉSPETZ ANDJÚLIARÉFFY: Large deviation theorem for the empirical eigenvalue distribution of truncated Haar unitary matrices. Prob. Theory and Related Fields, 133(2):175–189, 2005. Preprint atarXiv. [doi:10.1007/s00440-004-0420-5]184
[54] [54] MICHAELRECK, ANTONZEILINGER, HERBERTJ. BERNSTEIN,ANDPHILIPBERTANI: Experimental realization of any discrete unitary operator. Phys. Rev. Lett., 73(1):58–61, 1994. [doi:10.1103/PhysRevLett.73.58]165,201
[55] [55] JÚLIARÉFFY: Asymptotics of random unitaries. Ph. D. thesis, Budapest University of Technology and Economics, 2005.http://www.math.bme.hu/ reffyj/disszer.pdf.184,185
[56] [56] TERRYRUDOLPH: A simple encoding of a quantum circuit amplitude as a matrix permanent. Phys. Rev. A, 80(5), 2009. [doi:10.1103/PhysRevA.80.054302,arXiv:0909.3005]159
[57] [57] STEFANSCHEEL: Permanents in linear optical networks. 2004. [arXiv:quant-ph/0406127]158
[58] [58] DANSHEPHERD ANDMICHAELJ. BREMNER: Temporally unstructured quantum computation. Proc. Roy. Soc. A, 465(2105):1413–1439, 2009. Preprint atarXiv. [doi:10.1098/rspa.2008.0443] 160
[59] [59] YAOYUNSHI: Both Toffoli and controlled-NOT need little help to do universal quantum computing. Quantum Information & Computation, 3(1):84–92, 2003. Preprint atarXiv. [ACM:2011515]181 · Zbl 1152.81811
[60] [60] PETERW. SHOR: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput., 26(5):1484–1509, 1997. Preliminary version inFOCS’94. Preprint atarXiv. [doi:10.1137/S0097539795293172]146,161
[61] [61] DANIELR. SIMON: On the power of quantum computation. SIAM J. Comput., 26(5):1474–1483, 1997. Preliminary version inFOCS’94. [doi:10.1137/S0097539796298637]161
[62] [62] JUSTINB. SPRING, BENJAMINJ. METCALF, PETERC. HUMPHREYS, W. STEVENKOLTHAMMER, XIAN-MINJIN, MARCOBARBIERI, ANIMESHDATTA, NICHOLASTHOMAS-PETER, NATHANK. LANGFORD, DMYTROKUNDYS, JAMESC. GATES, BRIANJ. SMITH, PETERG. R. SMITH,ANDIANA. WALMSLEY: Boson sampling on a photonic chip. Science, 2012 (online). Preprint atarXiv. [doi:10.1126/science.1231692]154,200
[63] [63] LARRYJ. STOCKMEYER: On approximation algorithms for #P. SIAM J. Comput., 14(4):849–861, 1985. Preliminary version inSTOC’83. [doi:10.1137/0214060]175 THEORY OFCOMPUTING, Volume 9 (4), 2013, pp. 143–252250 THECOMPUTATIONALCOMPLEXITY OFLINEAROPTICS · Zbl 0589.68031
[64] [64] MADHUSUDAN: Maximum likelihood decoding of Reed Solomon codes. In Proc. 37th FOCS, pp. 164–172. IEEE Comp. Soc. Press, 1996. [doi:10.1109/SFCS.1996.548475]229
[65] [65] TERENCETAO ANDVANH. VU: On the permanent of random Bernoulli matrices. Advances in Mathematics, 220(3):657–669, 2009. Preprint atarXiv. [doi:10.1016/j.aim.2008.09.006]153,218, 219 · Zbl 1229.05265
[66] [66] BARBARAM. TERHAL ANDDAVIDP. DIVINCENZO: Classical simulation of noninteractingfermion quantum circuits.Phys. Rev. A, 65(3):032325, 2002.Preprint atarXiv. [doi:10.1103/PhysRevA.65.032325]158
[67] [67] BARBARAM. TERHAL ANDDAVIDP. DIVINCENZO: Adaptive quantum computation, constantdepth quantum circuits and Arthur-Merlin games. Quantum Information & Computation, 4(2):134– 145, 2004. Preprint atarXiv. [ACM:2011582]160,180
[68] [68] MAXTILLMANN, BORIVOJEDAKI \'{}C, RENÉHEILMANN, STEFANNOLTE, ALEXANDERSZAMEIT,ANDPHILIPWALTHER: Experimental boson sampling. 2012. [arXiv:1212.2240]154, 200
[69] [69] SEINOSUKETODA: PP is as hard as the polynomial-time hierarchy. SIAM J. Comput., 20(5):865– 877, 1991. Preliminary version inFOCS’89. [doi:10.1137/0220053]150,154,179
[70] [70] LIDRORTROYANSKY ANDNAFTALITISHBY: Permanent uncertainty: On the quantum evaluation of the determinant and the permanent of a matrix. In Proc. 4th Workshop on Physics and Computation (PhysComp’96), 1996. Availablehere.158
[71] [71] LESLIEG. VALIANT: The complexity of computing the permanent. Theoret. Comput. Sci., 8(2):189– 201, 1979. [doi:10.1016/0304-3975(79)90044-6]158,175
[72] [72] LESLIEG. VALIANT: Quantum circuits that can be simulated classically in polynomial time.SIAM J. Comput., 31(4):1229–1254, 2002.Preliminary version inSTOC’01. [doi:10.1137/S0097539700377025]158
[73] [73] LIEVENM. K. VANDERSYPEN, MATTHIASSTEFFEN, GREGORYBREYTA, COSTANTINOS. YANNONI, MARKH. SHERWOOD,ANDISAACL. CHUANG: Experimental realization of Shor’s quantum factoring algorithm using nuclear magnetic resonance. Nature, 414(6866):883–887, 2001. Preprint atarXiv. [doi:10.1038/414883a]155
[74] [74] JIN YICAI, ADURIPAVAN,ANDD. SIVAKUMAR: On the hardness of permanent. In Proc. 16th Symp. Theoretical Aspects of Comp. Sci. (STACS’99), pp. 90–99, 1999. [doi:10.1007/3-540-491163_8]229 THEORY OFCOMPUTING, Volume 9 (4), 2013, pp. 143–252251 SCOTTAARONSON ANDALEXARKHIPOV
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.