[1]   Scott Aaronson: QMA/qpoly ⊆ PSPACE/poly: De-Merlinizing quantum protocols. In Proc. 21st IEEE Conf. on Computational Complexity (CCC’06), pp. 261–273. IEEE Comp. Soc. Press, 2006. [doi:10.1109/CCC.2006.36, arXiv:quant-ph/0510230]

[2]   Scott Aaronson: BQP and the Polynomial Hierarchy. In Proc. 42nd STOC, pp. 141–150. ACM Press, 2010. [doi:10.1145/1806689.1806711, arXiv:0910.4698]

[3]   Scott Aaronson and Andris Ambainis: The need for structure in quantum speedups. Theory of Computing, 10(6):133–166, 2014. Preliminary version in ICS’11. [doi:10.4086/toc.2014.v010a006, arXiv:0911.0996]

[4]   Scott Aaronson and Andris Ambainis: Forrelation: A problem that optimally separates quantum from classical computing. In Proc. 47th STOC, pp. 307–316. ACM Press, 2015. Preliminary version in ECCC. [doi:10.1145/2746539.2746547, arXiv:1411.5729]

[5]   Scott Aaronson, Salman Beigi, Andrew Drucker, Bill Fefferman, and Peter W. Shor: The power of unentanglement. Theory of Computing, 5(1):1–42, 2009. Preliminary version in CCC’08. [doi:10.4086/toc.2009.v005a001, arXiv:0804.0802]

[6]   Scott Aaronson and Daniel Gottesman: Identifying stabilizer states, 2008. Talk at PIRSA, available on video.

[7]   Scott Aaronson and Yaoyun Shi: Quantum lower bounds for the collision and the element distinctness problems. J. ACM, 51(4):595–605, 2004. Preliminary version in FOCS’02. [doi:10.1145/1008731.1008735]

[8]   Antonio Acín: Statistical distinguishability between unitary operations. Phys. Rev. Lett., 87(17):177901, 2001. [doi:10.1103/PhysRevLett.87.177901, arXiv:quant-ph/0102064]

[9]   Antonio Acín, Nicolas Brunner, Nicolas Gisin, Serge Massar, Stefano Pironio, and Valerio Scarani: Device-independent security of quantum cryptography against collective attacks. Phys. Rev. Lett., 98(23):230501, 2007. [doi:10.1103/PhysRevLett.98.230501, arXiv:quant-ph/0702152]

[10]   Dorit Aharonov, Itai Arad, and Thomas Vidick: The quantum PCP conjecture. ACM SIGACT News, 44(2):47–79, 2013. [doi:10.1145/2491533.2491549, arXiv:1309.7495]

[11]   Dorit Aharonov and Lior Eldar: Quantum locally testable codes. SIAM J. Comput., 44(5):1230–1262, 2015. [doi:10.1137/140975498, arXiv:1310.5664]

[12]   Dorit Aharonov, Aram Wettroth Harrow, Zeph Landau, Daniel Nagaj, Mario Szegedy, and Umesh V. Vazirani: Local tests of global entanglement and a counterexample to the generalized area law. In Proc. 55th FOCS, pp. 246–255. IEEE Comp. Soc. Press, 2014. [doi:10.1109/FOCS.2014.34]

[13]   Noga Alon, Eldar Fischer, Ilan Newman, and Asaf Shapira: A combinatorial characterization of the testable graph properties: It’s all about regularity. SIAM J. Comput., 39(1):143–167, 2009. Preliminary version in STOC’06. [doi:10.1137/060667177]

[14]   Noga Alon, Tali Kaufman, Michael Krivelevich, Simon Litsyn, and Dana Ron: Testing Reed-Muller codes. IEEE Trans. Inform. Theory, 51(11):4032–4039, 2005. Preliminary version in RANDOM’03. [doi:10.1109/TIT.2005.856958]

[15]   Andris Ambainis: Quantum lower bounds by quantum arguments. J. Comput. System Sci., 64(4):750–767, 2002. Preliminary version in STOC’00. [doi:10.1006/jcss.2002.1826, arXiv:quant-ph/0002066]

[16]   Andris Ambainis: Quantum walk algorithm for element distinctness. SIAM J. Comput., 37(1):210–239, 2007. Preliminary version in FOCS’04. [doi:10.1137/S0097539705447311, arXiv:quant-ph/0311001]

[17]   Andris Ambainis, Aleksandrs Belovs, Oded Regev, and Ronald de Wolf: Efficient quantum algorithms for (gapped) group testing and junta testing. In Proc. 27th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’16), pp. 903–922. ACM Press, 2016. [doi:10.1137/1.9781611974331.ch65, arXiv:1507.03126]

[18]    Andris Ambainis, Andrew M. Childs, and Yi-Kai Liu: Quantum property testing for bounded-degree graphs. In Proc. 15th Internat. Workshop on Randomization and Computation (RANDOM’11), volume 6845 of LNCS, pp. 365–376. Springer, 2011. [doi:10.1007/978-3-642-22935-0_31]

[19]   Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy: Proof verification and the hardness of approximation problems. J. ACM, 45(3):501–555, 1998. Preliminary version in FOCS’92. [doi:10.1145/278298.278306]

[20]   Alp Atc and Rocco A. Servedio: Quantum algorithms for learning and testing juntas. Quantum Inf. Processing, 6(5):323–348, 2007. [doi:10.1007/s11128-007-0061-6, arXiv:0707.3479]

[21]   Koenraad M. R. Audenaert: A digest on representation theory of the symmetric group, 2006. Available at author’s website.

[22]   Koenrad M. R. Audenaert, Michael Nussbaum, Arleta Szkoła, and Frank Verstraete: Asymptotic error rates in quantum hypothesis testing. Comm. in Math. Physics, 279(1):251–283, 2008. [doi:10.1007/s00220-008-0417-5, arXiv:0708.4282]

[23]   László Babai, Lance Fortnow, and Carsten Lund: Non-deterministic exponential time has two-prover interactive protocols. Comput. Complexity, 1(1):3–40, 1991. Preliminary version in FOCS’90. [doi:10.1007/BF01200056]

[24]   David Bacon, Isaac L. Chuang, and Aram Wettroth Harrow: Efficient quantum circuits for Schur and Clebsch-Gordan transforms. Phys. Rev. Lett., 97(17):170502, 2006. [doi:10.1103/PhysRevLett.97.170502, arXiv:quant-ph/0407082]

[25]   Jean-Daniel Bancal, Miguel Navascués, Valerio Scarani, Tamás Vértesi, and Tzyh Haur Yang: Physical characterization of quantum devices from nonlocal correlations. Phys. Rev. A, 91(2):022115, 2013. [doi:10.1103/PhysRevA.91.022115, arXiv:1307.7053]

[26]   Adriano Barenco, André Berthiaume, David Deutsch, Artur Ekert, Richard Jozsa, and Chiara Macchiavello: Stabilization of quantum computations by symmetrization. SIAM J. Comput., 26(5):1541–1557, 1997. [doi:10.1137/S0097539796302452]

[27]   Stephen M. Barnett and Sarah Croke: Quantum state discrimination. Advances in Optics and Photonics, 1(2):238–278, 2009. [doi:10.1364/AOP.1.000238, arXiv:0810.1970]

[28]   Jonathan Barrett, Lucien Hardy, and Adrian Kent: No signaling and quantum key distribution. Phys. Rev. Lett., 95(1):010503, 2005. [doi:10.1103/PhysRevLett.95.010503, arXiv:quant-ph/0405101]

[29]   Tuǧkan Batu, Lance Fortnow, Eldar Fischer, Ravi Kumar, Ronitt Rubinfeld, and Patrick White: Testing random variables for independence and identity. In Proc. 42nd FOCS, pp. 442–451. IEEE Comp. Soc. Press, 2001. [doi:10.1109/SFCS.2001.959920]

[30]   Tuǧkan Batu, Lance Fortnow, Ronitt Rubinfeld, Warren D. Smith, and Patrick White: Testing closeness of discrete distributions. J. ACM, 60(1):4:1–4:25, 2013. Preliminary version in FOCS’00. [doi:10.1145/2432622.2432626, arXiv:1009.5397]

[31]   Robert Beals: Quantum computation of Fourier transforms over symmetric groups. In Proc. 29th STOC, pp. 48–53. ACM Press, 1997. [doi:10.1145/258533.258548]

[32]   Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf: Quantum lower bounds by polynomials. J. ACM, 48(4):778–797, 2001. Preliminary version in FOCS’98. [doi:10.1145/502090.502097, arXiv:quant-ph/9802049]

[33]   Mihir Bellare, Don Coppersmith, Johan Håstad, Marcos A. Kiwi, and Madhu Sudan: Linearity testing in characteristic two. IEEE Trans. Inform. Theory, 42(6):1781–1795, 1996. Preliminary version in FOCS’95. [doi:10.1109/18.556674]

[34]   Aleksandrs Belovs: Quantum algorithms for learning symmetric juntas via adversary bound. Comput. Complexity, 24(2):255–293, 2015. Preliminary version in CCC’14. [doi:10.1007/s00037-015-0099-2, arXiv:1311.6777]

[35]   Charles H. Bennett, Ethan Bernstein, Gilles Brassard, and Umesh V. Vazirani: Strengths and weaknesses of quantum computing. SIAM J. Comput., 26(5):1510–1523, 1997. [doi:10.1137/S0097539796300933, arXiv:quant-ph/9701001]

[36]   Ethan Bernstein and Umesh V. Vazirani: Quantum complexity theory. SIAM J. Comput., 26(5):1411–1473, 1997. Preliminary version in STOC’93. [doi:10.1137/S0097539796300921]

[37]   Eric Blais: Testing juntas nearly optimally. In Proc. 41st STOC, pp. 151–158. ACM Press, 2009. [doi:10.1145/1536414.1536437]

[38]   Eric Blais, Joshua Brody, and Kevin Matulef: Property testing lower bounds via communication complexity. Comput. Complexity, 21(2):311–358, 2012. Preliminary version in CCC’11. [doi:10.1007/s00037-012-0040-x]

[39]   Manuel Blum, Michael Luby, and Ronitt Rubinfeld: Self-testing/correcting with applications to numerical problems. J. Comput. System Sci., 47(3):549–595, 1993. Preliminary version in STOC’90. [doi:10.1016/0022-0000(93)90044-W]

[40]   Adam D. Bookatz: QMA-complete problems. Quantum Inf. Comput., 14(5-6):361–383, 2014. ACM DL. [arXiv:1212.6312]

[41]   Gilles Brassard and Peter Høyer: An exact quantum polynomial-time algorithm for Simon’s problem. In Proc. 5th Israel Symp. on Theory of Comput. Sys. (ISTCS’97), pp. 12–23. IEEE Comp. Soc. Press, 1997. [doi:10.1109/ISTCS.1997.595153, arXiv:quant-ph/9704027]

[42]   Gilles Brassard, Peter Høyer, Michele Mosca, and Alain Tapp: Quantum amplitude amplification and estimation. In Quantum Computation and Quantum Information: A Millennium Volume, volume 305 of AMS Contemporary Mathematics Series, pp. 53–74. Amer. Math. Soc., 2002. [arXiv:quant-ph/0005055]

[43]   Samuel L. Braunstein, Ady Mann, and Michael Revzen: Maximal violation of Bell inequalities for mixed states. Phys. Rev. Lett., 68(22):3259–3261, 1992. [doi:10.1103/PhysRevLett.68.3259]

[44]   Sergey Bravyi, Aram Wettroth Harrow, and Avinatan Hassidim: Quantum algorithms for testing properties of distributions. IEEE Trans. Inform. Theory, 57(6):3971–3981, 2011. Preliminary version in STACS’10. [doi:10.1109/TIT.2011.2134250, arXiv:0907.3920]

[45]   Todd A. Brun: Measuring polynomial functions of states. Quantum Inf. Comput., 4(5):401–408, 2004. [arXiv:quant-ph/0401067]

[46]   Nicolas Brunner, Daniel Cavalcanti, Stefano Pironio, Valerio Scarani, and Stephanie Wehner: Bell nonlocality. Reviews of Modern Physics, 86(2):419–478, 2014. [doi:10.1103/RevModPhys.86.419, arXiv:1303.2849]

[47]   Dagmar Bruß and Chiara Macchiavello: Optimal state estimation for d-dimensional quantum systems. Physics Letters A, 253(5–6):249–251, 1999. [doi:10.1016/S0375-9601(99)00099-7, arXiv:quant-ph/9812016]

[48]   Harry Buhrman, Richard Cleve, John Watrous, and Ronald de Wolf: Quantum fingerprinting. Phys. Rev. Lett., 87(16):167902, 2001. [doi:10.1103/PhysRevLett.87.167902, arXiv:quant-ph/0102001]

[49]   Harry Buhrman, Lance Fortnow, Ilan Newman, and Hein Röhrig: Quantum property testing. SIAM J. Comput., 37(5):1387–1400, 2008. Preliminary version in SODA’03. [doi:10.1137/S0097539704442416, arXiv:quant-ph/0201117]

[50]   Harry Buhrman, David García-Soriano, Arie Matsliah, and Ronald de Wolf: The non-adaptive query complexity of testing k-parities. Chicago J. of Theoret. Comput. Sci., 2013(6), 2013. [doi:10.4086/cjtcs.2013.006, arXiv:1209.3849]

[51]   Harry Buhrman and Ronald de Wolf: Complexity measures and decision tree complexity: a survey. Theoret. Comput. Sci., 288(1):21–43, 2002. [doi:10.1016/S0304-3975(01)00144-X]

[52]   Kaushik Chakraborty and Subhamoy Maitra: Improved quantum test for linearity of a Boolean function, 2013. [arXiv:1306.6195]

[53]   Sourav Chakraborty, Eldar Fischer, Arie Matsliah, and Ronald de Wolf: New results on quantum property testing. In Proc. 30th Internat. Conf. on Foundation of Software Tech. and Theoret. Comput. Sci. (FSTTCS’10), volume 8 of LIPIcs, pp. 145–156. Springer, 2010. [doi:10.4230/LIPIcs.FSTTCS.2010.145, arXiv:1005.0523]

[54]   Siu-on Chan, Ilias Diakonikolas, Paul Valiant, and Gregory Valiant: Optimal algorithms for testing closeness of discrete distributions. In Proc. 25th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’14), pp. 1193–1203. ACM Press, 2014. [doi:10.1137/1.9781611973402.88, arXiv:1308.3946]

[55]   Anthony Chefles: Quantum state discrimination. Contemporary Physics, 41(6):401–424, 2001. [doi:10.1080/00107510010002599, arXiv:quant-ph/0010114]

[56]   Andrew M. Childs, Aram Wettroth Harrow, and Pawel Wocjan: Weak Fourier-Schur sampling, the hidden subgroup problem, and the quantum collision problem. In Proc. 24th Symp. Theoretical Aspects of Comp. Sci. (STACS’07), volume 4393 of LNCS, pp. 598–609. Springer, 2007. [doi:10.1007/978-3-540-70918-3_51, arXiv:quant-ph/0609110]

[57]   Hana Chockler and Dan Gutfreund: A lower bound for testing juntas. Inform. Process. Lett., 90(6):301–305, 2004. [doi:10.1016/j.ipl.2004.01.023]

[58]   Man-Duen Choi: Completely positive linear maps on complex matrices. Linear Algebra and its Applications, 10(3):285–290, 1975. [doi:10.1016/0024-3795(75)90075-0]

[59]   Matthias Christandl: The Structure of Bipartite Quantum States – Insights from Group Theory and Cryptography. Ph. D. thesis, University of Cambridge, 2006. [arXiv:quant-ph/0604183]

[60]   Boris S. Cirel’son: Quantum generalizations of Bell’s inequality. Letters in Math. Physics, 4(2):93–100, 1980. [doi:10.1007/BF00417500]

[61]   John F. Clauser, Michael A. Horne, Abner Shimony, and Richard A. Holt: Proposed experiment to test local hidden-variable theories. Phys. Rev. Lett., 23(15):880–884, 1969. [doi:10.1103/PhysRevLett.23.880]

[62]   Roger Colbeck: Quantum and relativistic protocols for secure multi-party computation. Ph. D. thesis, University of Cambridge, 2006. [arXiv:0911.3814]

[63]   Marcus Cramer, Martin B. Plenio, Steven T. Flammia, Rolando Somma, David Gross, Stephen D. Bartlett, Olivier Landon-Cardinal, David Poulin, and Yi-Kai Liu: Efficient quantum state tomography. Nature Communications, 1(9):49, 2010. [doi:10.1038/ncomms1147, arXiv:1101.4366]

[64]   Anirban Dasgupta, Ravi Kumar, and D. Sivakumar: Sparse and lopsided set disjointness via information theory. In Proc. 16th Internat. Workshop on Randomization and Computation (RANDOM’12), volume 7408 of LNCS, pp. 517–528. Springer, 2012. [doi:10.1007/978-3-642-32512-0_44]

[65]   Runyao Duan, Yuan Feng, Yu Xin, and Mingsheng Ying: Distinguishability of quantum states by separable operations. IEEE Trans. Inform. Theory, 55(3):1320–1330, 2009. [doi:10.1109/TIT.2008.2011524, arXiv:0705.0795]

[66]   Eldar Fischer: The art of uninformed decisions. Bulletin of the EATCS, 75:97, 2001. [doi:10.1142/9789812562494_0014]

[67]   Eldar Fischer, Guy Kindler, Dana Ron, Shmuel Safra, and Alex Samorodnitsky: Testing juntas. J. Comput. System Sci., 68(4):753–787, 2004. Preliminary version in FOCS’02. [doi:10.1016/j.jcss.2003.11.004]

[68]   Steven T. Flammia, David Gross, Yi-Kai Liu, and Jens Eisert: Quantum tomography via compressed sensing: Error bounds, sample complexity, and efficient estimators. New J. of Phys., 14(9):095022, 2012. [doi:10.1088/1367-2630/14/9/095022, arXiv:1205.2300]

[69]   Steven T. Flammia and Yi-Kai Liu: Direct fidelity estimation from few Pauli measurements. Phys. Rev. Lett., 106(23):230501, 2011. [doi:10.1103/PhysRevLett.106.230501, arXiv:1104.4695]

[70]   Katalin Friedl, Gábor Ivanyos, and Miklos Santha: Efficient testing of groups. In Proc. 37th STOC, pp. 157–166. ACM Press, 2005. [doi:10.1145/1060590.1060614]

[71]   Katalin Friedl, Miklos Santha, Frédéric Magniez, and Pranab Sen: Quantum testers for hidden group properties. Fundam. Inform., 91(2):325–340, 2009. Preliminary version in MFCS’03. [doi:10.3233/FI-2009-0046, arXiv:quant-ph/0208184]

[72]   Jingliang Gao: Quantum union bounds for sequential projective measurements. Phys. Rev. A, 92(5):052331, 2015. [doi:10.1103/PhysRevA.92.052331, arXiv:1410.5688]

[73]   Sevag Gharibian: Strong NP-hardness of the quantum separability problem. Quantum Inf. Comput., 10(3&4):343–360, 2010. [arXiv:0810.4507]

[74]   Lev Glebsky: Almost commuting matrices with respect to normalized Hilbert-Schmidt norm, 2010. [arXiv:1002.3082]

[75]   Oded Goldreich, editor. Property Testing: Current Research and Surveys. Volume 6390. Springer, 2010. [doi:10.1007/978-3-642-16367-8]

[76]   Oded Goldreich, Shafi Goldwasser, and Dana Ron: Property testing and its connection to learning and approximation. J. ACM, 45(4):653–750, 1998. Preliminary version in FOCS’96. [doi:10.1145/285055.285060]

[77]   Oded Goldreich and Dana Ron: Property testing in bounded degree graphs. Algorithmica, 32(2):302–343, 2002. Preliminary version in STOC’97. [doi:10.1007/s00453-001-0078-7]

[78]   Oded Goldreich and Dana Ron: On testing expansion in bounded-degree graphs. In Studies in Complexity and Cryptography, volume 6650, pp. 68–75. Springer, 2011. Preliminary version in ECCC. [doi:10.1007/978-3-642-22670-0_9]

[79]   Daniel Gottesman: Stabilizer Codes and Quantum Error Correction. Ph. D. thesis, Caltech, 1999. [arXiv:quant-ph/9705052]

[80]   Daniel M. Greenberger, Michael A. Horne, and Anton Zeilinger: Going beyond Bell’s theorem. In Bell’s Theorem, Quantum Theory, and Conceptions of the Universe, pp. 69–72. Springer, 1989. [doi:10.1007/978-94-017-0849-4_10, arXiv:0712.0921]

[81]   David Gross, Yi-Kai Liu, Steven T. Flammia, Stephen Becker, and Jens Eisert: Quantum state tomography via compressed sensing. Phys. Rev. Lett., 105(15):150401, 2010. [doi:10.1103/PhysRevLett.105.150401, arXiv:0909.3304]

[82]   Lov K. Grover: A fast quantum mechanical algorithm for database search. In Proc. 28th STOC, pp. 212–219. ACM Press, 1996. [doi:10.1145/237814.237866, arXiv:quant-ph/9605043]

[83]   Otfried Gühne and Géza Tóth: Entanglement detection. Physics Reports, 474(1–6):1–75, 2009. [doi:10.1016/j.physrep.2009.02.004, arXiv:0811.2803]

[84]   Leonid Gurvits: Classical deterministic complexity of Edmonds’ problem and quantum entanglement. In Proc. 35th STOC, pp. 10–19. ACM Press, 2003. [doi:10.1145/780542.780545]

[85]   Gus Gutoski, Patrick Hayden, Kevin Milner, and Mark M. Wilde: Quantum interactive proofs and the complexity of separability testing. Theory of Computing, 11(3):59–103, 2015. [doi:10.4086/toc.2015.v011a003, arXiv:1308.5788]

[86]   Jeongwan Haah, Aram Wettroth Harrow, Zheng-Feng Ji, Xiaodi Wu, and Nengkun Yu: Sample-optimal tomography of quantum states. In Proc. 48th STOC, pp. 913–925. ACM Press, 2016. [doi:10.1145/2897518.2897585, arXiv:1508.01797]

[87]   Hartmut Häffner, W. Hänsel, Christian F. Roos, J. Benhelm, D. Chek-al-kar, Michael Chwalla, T. Körber, Umakant Rapol, Mark Riebe, Piet O. Schmidt, Christoph Becher, Otfried Gühne, Wolfgang Dür, and Rainer Blatt: Scalable multiparticle entanglement of trapped ions. Nature, 438:643–646, 2005. [doi:10.1038/nature04279, arXiv:quant-ph/0603217]

[88]   Lisa Hales: The Quantum Fourier Transform and Extensions of the Abelian Hidden Subgroup Problem. Ph. D. thesis, University of California, Berkeley, 2002. [arXiv:quant-ph/0212002]

[89]   Lisa Hales and Sean Hallgren: An improved quantum Fourier transform algorithm and applications. In Proc. 41st FOCS, pp. 515–525. IEEE Comp. Soc. Press, 2000. [doi:10.1109/SFCS.2000.892139]

[90]   Aram Wettroth Harrow: Applications of coherent classical communication and the Schur transform to quantum information theory. Ph. D. thesis, Massachusetts Institute of Technology, 2005. [arXiv:quant-ph/0512255]

[91]   Aram Wettroth Harrow and Ashley Montanaro: Testing product states, quantum Merlin-Arthur games and tensor optimization. J. ACM, 60(1):3, 2013. [doi:10.1145/2432622.2432625, arXiv:1001.0017]

[92]   Patrick Hayden, Debbie W. Leung, and Andreas Winter: Aspects of generic entanglement. Comm. in Math. Physics, 265(1):95–117, 2006. [doi:10.1007/s00220-006-1535-6, arXiv:quant-ph/0407049]

[93]   Patrick Hayden, Kevin Milner, and Mark M. Wilde: Two-message quantum interactive proofs and the quantum separability problem. Quantum Inf. Comput., 14(5-6):384–416, 2014. Preliminary version in CCC’13. ACM DL. [arXiv:1211.6120]

[94]   Carl W. Helstrom: Quantum Detection and Estimation Theory. Academic Press, New York, 1976.

[95]   Mark Hillery and Erika Andersson: Quantum tests for the linearity and permutation invariance of Boolean functions. Phys. Rev. A, 84(6):062329, 2011. [doi:10.1103/PhysRevA.84.062329, arXiv:1106.4831]

[96]   Alexander S. Holevo: Bounds for the quantity of information transmitted by a quantum communication channel. Problemy Peredachi Informatsii, 9(3):3–11, 1973. Available at Mathnet. English translation Problems of Information Transmission, vol. 9, pp. 177-183, 1973.

[97]   Shlomo Hoory, Nathan Linial, and Avi Wigderson: Expander graphs and their applications. Bulletin of the AMS, 43(4):439–561, 2006. [doi:10.1090/S0273-0979-06-01126-8]

[98]   Ryszard Horodecki, Paweł Horodecki, Michał Horodecki, and Karol Horodecki: Quantum entanglement. Reviews of Modern Physics, 81(2):865–942, 2009. [doi:10.1103/RevModPhys.81.865, arXiv:quant-ph/0702225]

[99]   Peter Høyer, Troy Lee, and Robert Spalek: Negative weights make adversaries stronger. In Proc. 39th STOC, pp. 526–535. ACM Press, 2007. [doi:10.1145/1250790.1250867, arXiv:quant-ph/0611054]

[100]   Yoshifumi Inui and François Le Gall: Quantum property testing of group solvability. Algorithmica, 59(1):35–47, 2011. Preliminary version in LATIN’08. [doi:10.1007/s00453-009-9338-8, arXiv:0712.3829]

[101]   Tsuyoshi Ito and Thomas Vidick: A multi-prover interactive proof for NEXP sound against entangled provers. In Proc. 53rd FOCS, pp. 243–252. IEEE Comp. Soc. Press, 2012. Preliminary version in ECCC. [doi:10.1109/FOCS.2012.11, arXiv:1207.0550]

[102]   Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay, and John Watrous: QIP = PSPACE. J. ACM, 58(6):30, 2011. Preliminary version in STOC’10. [doi:10.1145/2049697.2049704, arXiv:0907.4737]

[103]   Andrzej Edmund Jamiołkowski: Linear transformations which preserve trace and positive semidefiniteness of operators. Reports on Math. Physics, 3(4):275–278, 1972. [doi:10.1016/0034-4877(72)90011-0]

[104]   Dominik Janzing, Pawel Wocjan, and Thomas Beth: Non-identity check is QMA-complete. Internat. J. Quantum Inf., 3(3):463–473, 2005. [doi:10.1142/S0219749905001067, arXiv:quant-ph/0305050]

[105]   Masaru Kada, Harumichi Nishimura, and Tomoyuki Yamakami: The efficiency of quantum identity testing of multiple states. J. Phys. A: Mathematical and Theoretical, 41(39):395309, 2008. [doi:10.1088/1751-8113/41/39/395309, arXiv:0809.2037]

[106]   Bala Kalyanasundaram and Georg Schnitger: The probabilistic communication complexity of set intersection. SIAM J. Discrete Math., 5(4):545–557, 1992. [doi:10.1137/0405044]

[107]   Daniel M. Kane and Samuel A. Kutin: Quantum interpolation of polynomials. Quantum Inf. Comput., 11(1&2):95–103, 2011. [arXiv:1509.09271]

[108]   Julia Kempe, Alexei Kitaev, and Oded Regev: The complexity of the local Hamiltonian problem. SIAM J. Comput., 35(5):1070–1097, 2006. Preliminary version in FSTTCS’04. [doi:10.1137/S0097539704445226, arXiv:quant-ph/0406180]

[109]   Michael Keyl and Reinhard F. Werner: Estimating the spectrum of a density operator. Phys. Rev. A, 64(5):052311, 2001. [doi:10.1103/PhysRevA.64.052311, arXiv:quant-ph/0102027]

[110]   Alexei Kitaev, Alexander H. Shen, and Michael N. Vyalyi: Classical and Quantum Computation. Volume 47 of Graduate Studies in Mathematics. Amer. Math. Soc., 2002. [doi:10.1090/gsm/047]

[111]   Alexei Kitaev and John Watrous: Parallelization, amplification, and exponential time simulation of quantum interactive proof systems. In Proc. 32nd STOC, pp. 608–617. ACM Press, 2000. [doi:10.1145/335305.335387]

[112]   Hirotada Kobayashi, Keiji Matsumoto, and Tomoyuki Yamakami: Quantum Merlin-Arthur proof systems: Are multiple Merlins more helpful to Arthur? Chicago J. of Theoret. Comput. Sci., 2009(3), 2009. Preliminary version in ISAAC’03. [doi:10.4086/cjtcs.2009.003]

[113]   Pascal Koiran, Vincent Nesme, and Natacha Portier: A quantum lower bound for the query complexity of Simon’s problem. In Proc. 32th Internat. Colloq. on Automata, Languages and Programming (ICALP’05), volume 3580 of LNCS, pp. 1287–1298. Springer, 2005. [doi:10.1007/11523468_104, arXiv:quant-ph/0501060]

[114]   Robert Krauthgamer and Ori Sasson: Property testing of data dimensionality. In Proc. 14th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’03), pp. 18–27. ACM Press, 2003. ACM DL.

[115]   Eyal Kushilevitz and Noam Nisan: Communication Complexity. Cambridge Univ. Press, 1997.

[116]   Oded Lachish and Ilan Newman: Testing periodicity. Algorithmica, 60(2):401–420, 2011. Preliminary versions in RANDOM’05 and ECCC. [doi:10.1007/s00453-009-9351-y]

[117]   François Le Gall and Yuichi Yoshida: Property testing for cyclic groups and beyond. J. Combinat. Optim., 26(4):636–654, 2013. Preliminary version in COCOON’11. [doi:10.1007/s10878-011-9445-8, arXiv:1105.1842]

[118]   Troy Lee, Rajat Mittal, Ben W. Reichardt, Robert Spalek, and Mario Szegedy: Quantum query complexity of state conversion. In Proc. 52nd FOCS, pp. 344–353. IEEE Comp. Soc. Press, 2011. [doi:10.1109/FOCS.2011.75, arXiv:1011.3020]

[119]   Richard A. Low: Learning and testing algorithms for the Clifford group. Phys. Rev. A, 80(5):052314, 2009. [doi:10.1103/PhysRevA.80.052314, arXiv:0907.2833]

[120]   Florence Jessie MacWilliams and Neil James Alexander Sloane: The Theory of Error-Correcting Codes. North-Holland, Amsterdam, 1983.

[121]   Frédéric Magniez, Dominic Mayers, Michele Mosca, and Harold Ollivier: Self-testing of quantum circuits. In Proc. 33th Internat. Colloq. on Automata, Languages and Programming (ICALP’06), volume 4051 of LNCS, pp. 72–83. Springer, 2006. [doi:10.1007/11786986_8, arXiv:quant-ph/0512111]

[122]   Krzysztof Majewski and Nicholas Pippenger: Attribute estimation and testing quasi-symmetry. Inform. Process. Lett., 109(4):233–237, 2009. [doi:10.1016/j.ipl.2008.10.011, arXiv:0708.2105]

[123]   Dominic Mayers and Andrew Chi-Chih Yao: Quantum cryptography with imperfect apparatus. In Proc. 39th FOCS, pp. 503–509. IEEE Comp. Soc. Press, 1998. [doi:10.1109/SFCS.1998.743501, arXiv:quant-ph/9809039]

[124]   Dominic Mayers and Andrew Chi-Chih Yao: Self testing quantum apparatus. Quantum Inf. Comput., 4(4):273–286, 2004. ACM DL. [arXiv:quant-ph/0307205]

[125]   Matthew McKague: Self-testing graph states. In Proc. 6th Conf. on Theory of Quantum Comput., Comm. and Crypt. (TQC’11), volume 6745 of Lecture Notes in Computer Science, pp. 104–120. Springer, 2011. [doi:10.1007/978-3-642-54429-3_7, arXiv:1010.1989]

[126]   Matthew McKague: Interactive proofs for BQP via self-tested graph states. Theory of Computing, 12(3):1–42, 2016. [doi:10.4086/toc.2016.v012a003]

[127]   Matthew McKague, Tzyh Haur Yang, and Valerio Scarani: Robust self-testing of the singlet. J. Phys. A: Mathematical and Theoretical, 45(45):455304, 2012. [doi:10.1088/1751-8113/45/45/455304, arXiv:1203.2976]

[128]   Carl A. Miller and Yaoyun Shi: Optimal robust self-testing by binary nonlocal XOR games. In Proc. 8th Conf. on Theory of Quantum Comput., Comm. and Crypt. (TQC’13), volume 22 of LIPIcs, pp. 254–262. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2013. [doi:10.4230/LIPIcs.TQC.2013.254, arXiv:1207.1819]

[129]   Florian Mintert, Marek Kuś, and Andreas Buchleitner: Concurrence of mixed multipartite quantum states. Phys. Rev. Lett., 95(26):260502, 2005. [doi:10.1103/PhysRevLett.95.260502, arXiv:quant-ph/0411127]

[130]   Ashley Montanaro: Symmetric functions of qubits in an unknown basis. Phys. Rev. A, 79(6):062316, 2009. [doi:10.1103/PhysRevA.79.062316, arXiv:0903.5466]

[131]   Ashley Montanaro: Quantum speedup of Monte Carlo methods. Proc. Roy. Soc. Ser. A, 471(2181):20150301, 2015. [doi:10.1098/rspa.2015.0301, arXiv:1504.06987]

[132]   Ashley Montanaro and Tobias J. Osborne: Quantum boolean functions. Chicago J. of Theoret. Comput. Sci., 2010(1), 2010. [doi:10.4086/cjtcs.2010.001, arXiv:0810.2435]

[133]   Michael A. Nielsen: Continuity bounds for entanglement. Phys. Rev. A, 61(6):064301, 2000. [doi:10.1103/PhysRevA.61.064301, arXiv:quant-ph/9908086]

[134]   Michael A. Nielsen and Isaac L. Chuang: Quantum Computation and Quantum Information. Cambridge Univ. Press, 2000.

[135]   Ryan O’Donnell: Analysis of Boolean Functions. Cambridge Univ. Press, 2014.

[136]   Ryan O’Donnell and John Wright: Quantum spectrum testing. In Proc. 47th STOC, pp. 529–538. ACM Press, 2015. [doi:10.1145/2746539.2746582, arXiv:1501.05028]

[137]   Ryan O’Donnell and John Wright: Efficient quantum tomography. In Proc. 48th STOC, pp. 899–912. ACM Press, 2016. [doi:10.1145/2897518.2897544]

[138]   Tomohiro Ogawa and Hiroshi Nagaoka: A new proof of the channel coding theorem via hypothesis testing in quantum information theory. In Proc. IEEE Internat. Symp. on Information Theory (ISIT’02), p. 73. IEEE Comp. Soc. Press, 2002. [doi:10.1109/ISIT.2002.1023345, arXiv:quant-ph/0208139]

[139]   Matteo Paris and Jaroslav Řeháček, editors. Quantum State Estimation. Volume 649 of Lecture Notes in Physics. Springer, 2004. [doi:10.1007/b98673]

[140]   David Pérez-García, Frank Verstraete, Michael M. Wolf, and J. Ignacio Cirac: Matrix product state representations. Quantum Inf. Comput., 7(5):401–430, 2007. ACM DL. [arXiv:quant-ph/0608197]

[141]   Marco Piani and John Watrous: All entangled states are useful for channel discrimination. Phys. Rev. Lett., 102(25):250501, 2009. [doi:10.1103/PhysRevLett.102.250501, arXiv:0901.2118]

[142]   Sandu Popescu and Daniel Rohrlich: Which states violate Bell’s inequality maximally? Physics Letters A, 169(6):411–414, 1992. [doi:10.1016/0375-9601(92)90819-8]

[143]    Robert Raussendorf, Dan Browne, and Hans Briegel: Measurement-based quantum computation with cluster states. Phys. Rev. A, 68(2):022312, 2003. [doi:10.1103/PhysRevA.68.022312, arXiv:quant-ph/0301052]

[144]   Alexander A. Razborov: On the distributional complexity of disjointness. Theoret. Comput. Sci., 106(2):385–390, 1992. Preliminary version in ICALP’90. [doi:10.1016/0304-3975(92)90260-M]

[145]   Ben W. Reichardt: Span programs and quantum query complexity: The general adversary bound is nearly tight for every Boolean function. In Proc. 50th FOCS, pp. 544–551. IEEE Comp. Soc. Press, 2009. Preliminary version in ECCC. [doi:10.1109/FOCS.2009.55, arXiv:0904.2759]

[146]   Ben W. Reichardt, Falk Unger, and Umesh V. Vazirani: Classical command of quantum systems. Nature, 496(7446):456–460, 2013. [doi:10.1038/nature12035, arXiv:1209.0448, arXiv:1209.0449]

[147]   Dana Ron: Property testing: A learning theory perspective. Foundations and Trends in Machine Learning, 1(3):307–402, 2008. Preliminary abstract in COLT’07. [doi:10.1561/2200000004]

[148]   Bill Rosgen: Distinguishing short quantum computations. In Proc. 25th Symp. Theoretical Aspects of Comp. Sci. (STACS’08), volume 1 of LIPIcs, pp. 597–608. Springer, 2008. [doi:10.4230/LIPIcs.STACS.2008.1322, arXiv:0712.2595]

[149]   Bill Rosgen: Computational distinguishability of degradable and antidegradable channels. Quantum Inf. Comput., 10(9&10):735–746, 2010. [arXiv:0911.2109]

[150]   Bill Rosgen and John Watrous: On the hardness of distinguishing mixed-state quantum computations. In Proc. 20th IEEE Conf. on Computational Complexity (CCC’05), pp. 344–354. IEEE Comp. Soc. Press, 2005. [doi:10.1109/CCC.2005.21, arXiv:cs/0407056]

[151]   Massimiliano F. Sacchi: Optimal discrimination of quantum operations. Phys. Rev. A, 71(6):062340, 2005. [doi:10.1103/PhysRevA.71.062340, arXiv:quant-ph/0505183]

[152]   Miklos Santha: Quantum walk based search algorithms. In Proc. 5th Internat. Conf. on Theory and Appl. of Models of Comput. (TAMC’08), pp. 31–46. Springer, 2008. [doi:10.1007/978-3-540-79228-4_3, arXiv:0808.0059]

[153]   Pranab Sen: Achieving the Han–Kobayashi inner bound for the quantum interference channel. In IEEE Internat. Symp. on Information Theory (ISIT’12), pp. 736–740. IEEE, 2012. [doi:10.1109/ISIT.2012.6284656, arXiv:1109.0802]

[154]   Peter W. Shor: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput., 26(5):1484–1509, 1997. [doi:10.1137/S0097539795293172, arXiv:quant-ph/9508027]

[155]   Marcus P. da Silva, Olivier Landon-Cardinal, and David Poulin: Practical characterization of quantum devices without tomography. Phys. Rev. Lett., 107(21):210404, 2011. [doi:10.1103/PhysRevLett.107.210404, arXiv:1104.3835]

[156]   Daniel R. Simon: On the power of quantum computation. SIAM J. Comput., 26(5):1474–1483, 1997. Preliminary version in FOCS’94. [doi:10.1137/S0097539796298637]

[157]   Robert Špalek and Mario Szegedy: All quantum adversary methods are equivalent. Theory of Computing, 2(1):1–18, 2006. Preliminary version in ICALP’05. [doi:10.4086/toc.2006.v002a001, arXiv:quant-ph/0409116]

[158]   Stephen J. Summers and Reinhard F. Werner: Maximal violation of Bell’s inequalities is generic in quantum field theory. Comm. in Math. Physics, 110(2):247–259, 1987. [doi:10.1007/BF01207366]

[159]   Boris S. Tsirelson: Some results and problems on quantum Bell-type inequalities. Hadronic Journal Supplement, 8:329–345, 1993. Available at author’s website.

[160]   Paul Valiant: Testing symmetric properties of distributions. SIAM J. Comput., 40(6):1927–1968, 2011. Preliminary versions in STOC’08 and ECCC. [doi:10.1137/080734066]

[161]   Wim van Dam, Frédéric Magniez, Michele Mosca, and Miklos Santha: Self-testing of universal and fault-tolerant sets of quantum gates. SIAM J. Comput., 37(2):611–629, 2007. Preliminary version in STOC’00. [doi:10.1137/S0097539702404377, arXiv:quant-ph/9904108]

[162]   Umesh V. Vazirani and Thomas Vidick: Certifiable quantum dice: Or, true random number generation secure against quantum adversaries. Philosophical Trans. of the Royal Soc. A, 370(1971), 2012. Preliminary version, with subtitle “Or, true random number generation secure against quantum adversaries,” in STOC’12. [doi:10.1098/rsta.2011.0336]

[163]   Umesh V. Vazirani and Thomas Vidick: Fully device-independent quantum key distribution. Phys. Rev. Lett., 113(14):140501, 2014. [doi:10.1103/PhysRevLett.113.140501, arXiv:1210.1810]

[164]   Guoming Wang: Property testing of unitary operators. Phys. Rev. A, 84(5):052328, 2011. [doi:10.1103/PhysRevA.84.052328, arXiv:1110.1133]

[165]   Guoming Wang: Property testing of quantum measurements, 2012. [arXiv:1205.0828]

[166]   John Watrous: Theory of Quantum Information, lecture notes, 2008. https://cs.uwaterloo.ca/~watrous/LectureNotes.html.

[167]   Mark M. Wilde: Sequential decoding of a general classical–quantum channel. Proc. Royal Society A, 469(2157):20130259, 2013. [doi:10.1098/rspa.2013.0259, arXiv:1303.0808]

[168]   Andreas J. Winter: Coding theorem and strong converse for quantum channels. IEEE Trans. Inform. Theory, 45(7):2481–2485, 1999. [doi:10.1109/18.796385, arXiv:1409.2536]

[169]   Ronald de Wolf: A Brief Introduction to Fourier Analysis on the Boolean Cube. Volume 1 of Graduate Surveys. Theory of Computing Library, 2008. [doi:10.4086/toc.gs.2008.001]

[170]   Tzyh Haur Yang and Miguel Navascués: Robust self testing of unknown quantum systems into any entangled two-qubit states. Phys. Rev. A, 87(5):050102, 2013. [doi:10.1103/PhysRevA.87.050102, arXiv:1210.4409]

[171]   Andrew Chi-Chih Yao: Probabilistic computations: Toward a unified measure of complexity. In Proc. 18th FOCS, pp. 222–227. IEEE Comp. Soc. Press, 1977. [doi:10.1109/SFCS.1977.24]

[172]   Andrew Chi-Chih Yao: Some complexity questions related to distributive computing (preliminary report). In Proc. 11th STOC, pp. 209–213. ACM Press, 1979. [doi:10.1145/800135.804414]