1Department of Computer Science, University of Warwick, UK
2Department of Mathematics, UC Berkeley, USA & Department of Computer Science, University of Oxford, UK
3Department of Computer Science, Georgetown University, USA
Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.
Abstract
We initiate the systematic study of QMA algorithms in the setting of property testing, to which we refer as QMA $textit{proofs of proximity}$ (QMAPs). These are quantum query algorithms that receive explicit access to a sublinear-size untrusted proof and are required to accept inputs having a property $Pi$ and reject inputs that are $varepsilon$-far from $Pi$, while only probing a minuscule portion of their input.
We investigate the complexity landscape of this model, showing that QMAPs can be $exponentially$ stronger than both classical proofs of proximity and quantum testers. To this end, we extend the methodology of Blais, Brody, and Matulef (Computational Complexity, 2012) to prove quantum property testing lower bounds via reductions from communication complexity. This also resolves a question raised in 2013 by Montanaro and de Wolf (cf. Theory of Computing, 2016).
Our algorithmic results include a purpose an algorithmic framework that enables quantum speedups for testing an expressive class of properties, namely, those that are succinctly $decomposable$. A consequence of this framework is a QMA algorithm to verify the Parity of an $n$-bit string with $O(n^{2/3})$ queries and proof length. We also propose a QMA algorithm for testing graph bipartitneness, a property that lies outside of this family, for which there is a quantum speedup.
Featured image: Separations among QMAP and related complexity classes
[embedded content]
Popular summary
– Is verifying the solution to a computational problem easier than deciding if one exists?
– Can quantum computers solve problems their classical counterparts cannot?
Indeed, their formalisation in the model of polynomial-time computation yields the foundational P vs. NP and BPP vs. BQP problems. A related problem is the quantum analog of P vs. NP, namely, is QMA a strict subset of BQP? Less formally:
– Is verification easier than decision for quantum computers?
We study this question in the property-testing setting, which models super-efficient algorithms that only probe a minuscule portion of their input. In this setting, separations between verification and decision as well as quantum and classical computing are known. In other words, answers to the property-testing analogues of P vs. NP and BQP vs. BPP questions have been known for some time.
However, the property-testing analogue of QMA has not heretofore been systematically explored. Our paper fills this gap by initiating its study. We formalise super-efficient quantum verifiers, i.e., quantum proofs of proximity, and study their power and limitations. Among our results is a separation between quantum and classical proofs of proximity. This answers the QMA vs. BQP question in the property-testing setting.
► BibTeX data
► References
[1] Scott Aaronson. BQP and the polynomial hierarchy. In Leonard J. Schulman, editor, Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010, pages 141–150. ACM, 2010. 10.1145/1806689.1806711.
https://doi.org/10.1145/1806689.1806711
[2] Scott Aaronson. Impossibility of succinct quantum proofs for collision-freeness. Quantum Inf. Comput., 12 (1-2): 21–28, 2012. 10.26421/QIC12.1-2-3.
https://doi.org/10.26421/QIC12.1-2-3
[3] Scott Aaronson and Andris Ambainis. Forrelation: A problem that optimally separates quantum from classical computing. SIAM J. Comput., 47 (3): 982–1038, 2018. 10.1137/15M1050902.
https://doi.org/10.1137/15M1050902
[4] Scott Aaronson and Greg Kuperberg. Quantum versus classical proofs and advice. In 22nd Annual IEEE Conference on Computational Complexity (CCC 2007), 13-16 June 2007, San Diego, California, USA, pages 115–128. IEEE Computer Society, 2007. 10.1109/CCC.2007.27.
https://doi.org/10.1109/CCC.2007.27
[5] Dorit Aharonov, Itai Arad, and Thomas Vidick. Guest column: the quantum PCP conjecture. SIGACT News, 44 (2): 47–79, 2013. 10.1145/2491533.2491549.
https://doi.org/10.1145/2491533.2491549
[6] Dorit Aharonov, Jordan Cotler, and Xiao-Liang Qi. Quantum algorithmic measurement. Nature Communications, 13 (1): 1–9, 2022. 10.1038/s41467-021-27922-0.
https://doi.org/10.1038/s41467-021-27922-0
[7] Andris Ambainis. Quantum walk algorithm for element distinctness. SIAM J. Comput., 37 (1): 210–239, 2007. 10.1137/S0097539705447311.
https://doi.org/10.1137/S0097539705447311
[8] Andris Ambainis, Andrew M. Childs, and Yi-Kai Liu. Quantum property testing for bounded-degree graphs. In Leslie Ann Goldberg, Klaus Jansen, R. Ravi, and José D. P. Rolim, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques – 14th International Workshop, APPROX 2011, and 15th International Workshop, RANDOM 2011, Princeton, NJ, USA, August 17-19, 2011. Proceedings, volume 6845 of Lecture Notes in Computer Science, pages 365–376. Springer, 2011. 10.1007/978-3-642-22935-0_31.
https://doi.org/10.1007/978-3-642-22935-0_31
[9] Andris Ambainis, Aleksandrs Belovs, Oded Regev, and Ronald de Wolf. Efficient quantum algorithms for (gapped) group testing and junta testing. In Robert Krauthgamer, editor, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 903–922. SIAM, 2016. 10.1137/1.9781611974331.ch65.
https://doi.org/10.1137/1.9781611974331.ch65
[10] Vahid R. Asadi and Igor Shinkar. Relaxed locally correctable codes with improved parameters. In Nikhil Bansal, Emanuela Merelli, and James Worrell, editors, 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, July 12-16, 2021, Glasgow, Scotland (Virtual Conference), volume 198 of LIPIcs, pages 18:1–18:12. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021. 10.4230/LIPIcs.ICALP.2021.18.
https://doi.org/10.4230/LIPIcs.ICALP.2021.18
[11] James Aspnes, Richard Beigel, Merrick L. Furst, and Steven Rudich. The expressive power of voting polynomials. In Cris Koutsougeras and Jeffrey Scott Vitter, editors, Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, May 5-8, 1991, New Orleans, Louisiana, USA, pages 402–409. ACM, 1991. 10.1145/103418.103461.
https://doi.org/10.1145/103418.103461
[12] Costin Badescu, Ryan O’Donnell, and John Wright. Quantum state certification. In Moses Charikar and Edith Cohen, editors, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 503–514. ACM, 2019. 10.1145/3313276.3316344.
https://doi.org/10.1145/3313276.3316344
[13] Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, and Salil P. Vadhan. Robust PCPs of proximity, shorter PCPs, and applications to coding. SIAM J. Comput., 36 (4): 889–974, 2006. 10.1137/S0097539705446810.
https://doi.org/10.1137/S0097539705446810
[14] Eli Ben-Sasson, Alessandro Chiesa, Ariel Gabizon, Michael Riabzev, and Nicholas Spooner. Interactive oracle proofs with constant rate and query complexity. In Ioannis Chatzigiannakis, Piotr Indyk, Fabian Kuhn, and Anca Muscholl, editors, 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland, volume 80 of LIPIcs, pages 40:1–40:15. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2017. 10.4230/LIPIcs.ICALP.2017.40.
https://doi.org/10.4230/LIPIcs.ICALP.2017.40
[15] Itay Berman, Ron D. Rothblum, and Vinod Vaikuntanathan. Zero-knowledge proofs of proximity. In Anna R. Karlin, editor, 9th Innovations in Theoretical Computer Science Conference, ITCS 2018, January 11-14, 2018, Cambridge, MA, USA, volume 94 of LIPIcs, pages 19:1–19:20. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2018. 10.4230/LIPIcs.ITCS.2018.19.
https://doi.org/10.4230/LIPIcs.ITCS.2018.19
[16] Eric Blais, Joshua Brody, and Kevin Matulef. Property testing lower bounds via communication complexity. Comput. Complex., 21 (2): 311–358, 2012. 10.1007/s00037-012-0040-x.
https://doi.org/10.1007/s00037-012-0040-x
[17] Gilles Brassard, Peter Hoyer, Michele Mosca, and Alain Tapp. Quantum amplitude amplification and estimation. Contemporary Mathematics, 305: 53–74, 2002. 10.1090/conm/305/05215.
https://doi.org/10.1090/conm/305/05215
[18] Sébastien Bubeck, Sitan Chen, and Jerry Li. Entanglement is necessary for optimal quantum property testing. In Sandy Irani, editor, 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 692–703. IEEE, 2020. 10.1109/FOCS46700.2020.00070.
https://doi.org/10.1109/FOCS46700.2020.00070
[19] Harry Buhrman, Lance Fortnow, Ilan Newman, and Hein Röhrig. Quantum property testing. SIAM J. Comput., 37 (5): 1387–1400, 2008. 10.1137/S0097539704442416.
https://doi.org/10.1137/S0097539704442416
[20] Clément L. Canonne, Elena Grigorescu, Siyao Guo, Akash Kumar, and Karl Wimmer. Testing $k$-monotonicity: The rise and fall of boolean functions. Theory Comput., 15: 1–55, 2019. 10.4086/toc.2019.v015a001.
https://doi.org/10.4086/toc.2019.v015a001
[21] Kaushik Chakraborty and Subhamoy Maitra. Improved quantum test for linearity of a boolean function. CoRR, abs/1306.6195, 2013. 10.48550/arXiv.1306.6195.
https://doi.org/10.48550/arXiv.1306.6195
[22] Sourav Chakraborty, Eldar Fischer, Arie Matsliah, and Ronald de Wolf. New results on quantum property testing. In Kamal Lodaya and Meena Mahajan, editors, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2010, December 15-18, 2010, Chennai, India, volume 8 of LIPIcs, pages 145–156. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2010. 10.4230/LIPIcs.FSTTCS.2010.145.
https://doi.org/10.4230/LIPIcs.FSTTCS.2010.145
[23] Anthony Chefles. Quantum state discrimination. Contemporary Physics, 41 (6): 401–424, 2000. 10.1080/00107510010002599.
https://doi.org/10.1080/00107510010002599
[24] Lijie Chen. A note on oracle separations for BQP. CoRR, abs/1605.00619, 2016. 10.48550/arXiv.1605.00619.
https://doi.org/10.48550/arXiv.1605.00619
[25] Alessandro Chiesa, Tom Gur, and Igor Shinkar. Relaxed locally correctable codes with nearly-linear block length and constant query complexity. In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 1395–1411, 2020. 10.1137/1.9781611975994.84.
https://doi.org/10.1137/1.9781611975994.84
[26] Severin Daiss, Stefan Langenfeld, Stephan Welte, Emanuele Distante, Philip Thomas, Lukas Hartung, Olivier Morin, and Gerhard Rempe. A quantum-logic gate between distant quantum-network modules. Science, 371 (6529): 614–617, 2021. 10.1126/science.abe3150.
https://doi.org/10.1126/science.abe3150
[27] Marcel Dall’Agnol, Tom Gur, and Oded Lachish. A structural theorem for local algorithms with applications to coding, testing, and privacy. In Dániel Marx, editor, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 – 13, 2021, pages 1651–1665. SIAM, 2021. 10.1137/1.9781611976465.100.
https://doi.org/10.1137/1.9781611976465.100
[28] Jens Eisert, Dominik Hangleiter, Nathan Walk, Ingo Roth, Damian Markham, Rhea Parekh, Ulysse Chabaud, and Elham Kashefi. Quantum certification and benchmarking. Nature Reviews Physics, pages 1–9, 2020. 10.1038/s42254-020-0186-4.
https://doi.org/10.1038/s42254-020-0186-4
[29] Funda Ergün, Ravi Kumar, and Ronitt Rubinfeld. Fast approximate probabilistically checkable proofs. Inf. Comput., 189 (2): 135–159, 2004. 10.1016/j.ic.2003.09.005.
https://doi.org/10.1016/j.ic.2003.09.005
[30] Eldar Fischer, Yonatan Goldhirsh, and Oded Lachish. Partial tests, universal tests and decomposability. In Moni Naor, editor, Innovations in Theoretical Computer Science, ITCS’14, Princeton, NJ, USA, January 12-14, 2014, pages 483–500. ACM, 2014. 10.1145/2554797.2554841.
https://doi.org/10.1145/2554797.2554841
[31] Alexandru Gheorghiu, Theodoros Kapourniotis, and Elham Kashefi. Verification of quantum computation: An overview of existing approaches. Theory Comput Syst, 63 (4): 715–808, 2019. 10.1007/s00224-018-9872-3.
https://doi.org/10.1007/s00224-018-9872-3
[32] András Gilyén and Tongyang Li. Distributional property testing in a quantum world. In Thomas Vidick, editor, 11th Innovations in Theoretical Computer Science Conference, ITCS 2020, January 12-14, 2020, Seattle, Washington, USA, volume 151 of LIPIcs, pages 25:1–25:19. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2020. 10.4230/LIPIcs.ITCS.2020.25.
https://doi.org/10.4230/LIPIcs.ITCS.2020.25
[33] Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone. Quantum random access memory. Phys. Rev. Lett., 100: 160501, Apr 2008. 10.1103/PhysRevLett.100.160501.
https://doi.org/10.1103/PhysRevLett.100.160501
[34] Oded Goldreich. On multiple input problems in property testing. In Klaus Jansen, José D. P. Rolim, Nikhil R. Devanur, and Cristopher Moore, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2014, September 4-6, 2014, Barcelona, Spain, volume 28 of LIPIcs, pages 704–720. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2014. 10.4230/LIPIcs.APPROX-RANDOM.2014.704.
https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.704
[35] Oded Goldreich. Introduction to Property Testing. Cambridge University Press, 2017. ISBN 978-1-107-19405-2. 10.1017/9781108135252.
https://doi.org/10.1017/9781108135252
[36] Oded Goldreich. On the communication complexity methodology for proving lower bounds on the query complexity of property testing. In Computational Complexity and Property Testing – On the Interplay Between Randomness and Computation, volume 12050 of Lecture Notes in Computer Science, pages 87–118. Springer, 2020. 10.1007/978-3-030-43662-9_7.
https://doi.org/10.1007/978-3-030-43662-9_7
[37] Oded Goldreich and Tom Gur. Universal locally verifiable codes and 3-round interactive proofs of proximity for CSP. Theor. Comput. Sci., 878-879: 83–101, 2021. 10.1016/j.tcs.2021.05.030.
https://doi.org/10.1016/j.tcs.2021.05.030
[38] Oded Goldreich and Dana Ron. A sublinear bipartiteness tester for bounded degree graphs. Comb., 19 (3): 335–373, 1999. 10.1007/s004930050060.
https://doi.org/10.1007/s004930050060
[39] Oded Goldreich and Dana Ron. Property testing in bounded degree graphs. Algorithmica, 32 (2): 302–343, 2002. 10.1007/s00453-001-0078-7.
https://doi.org/10.1007/s00453-001-0078-7
[40] Oded Goldreich, Shafi Goldwasser, Eric Lehman, Dana Ron, and Alex Samorodnitsky. Testing monotonicity. Comb., 20 (3): 301–337, 2000. 10.1007/s004930070011.
https://doi.org/10.1007/s004930070011
[41] Oded Goldreich, Tom Gur, and Ron D. Rothblum. Proofs of proximity for context-free languages and read-once branching programs. Inf. Comput., 261: 175–201, 2018. 10.1016/j.ic.2018.02.003.
https://doi.org/10.1016/j.ic.2018.02.003
[42] Oded Goldreich, Tom Gur, and Ilan Komargodski. Strong locally testable codes with relaxed local decoders. ACM Trans. Comput. Theory, 11 (3): 17:1–17:38, 2019. 10.1145/3319907.
https://doi.org/10.1145/3319907
[43] Mika Göös and Gilbert Maystre. A majority lemma for randomised query complexity. In Valentine Kabanets, editor, 36th Computational Complexity Conference, CCC 2021, July 20-23, 2021, Toronto, Ontario, Canada (Virtual Conference), volume 200 of LIPIcs, pages 18:1–18:15. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021. 10.4230/LIPIcs.CCC.2021.18.
https://doi.org/10.4230/LIPIcs.CCC.2021.18
[44] Tom Gur and Oded Lachish. On the power of relaxed local decoding algorithms. SIAM J. Comput., 50 (2): 788–813, 2021. 10.1137/19M1307834.
https://doi.org/10.1137/19M1307834
[45] Tom Gur and Ron D. Rothblum. A hierarchy theorem for interactive proofs of proximity. In Christos H. Papadimitriou, editor, 8th Innovations in Theoretical Computer Science Conference, ITCS 2017, January 9-11, 2017, Berkeley, CA, USA, volume 67 of LIPIcs, pages 39:1–39:43. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2017. 10.4230/LIPIcs.ITCS.2017.39.
https://doi.org/10.4230/LIPIcs.ITCS.2017.39
[46] Tom Gur and Ron D. Rothblum. Non-interactive proofs of proximity. Comput. Complex., 27 (1): 99–207, 2018. 10.1007/s00037-016-0136-9.
https://doi.org/10.1007/s00037-016-0136-9
[47] Tom Gur, Yang P. Liu, and Ron D. Rothblum. An exponential separation between MA and AM proofs of proximity. Comput. Complex., 30 (2): 12, 2021. 10.1007/s00037-021-00212-3.
https://doi.org/10.1007/s00037-021-00212-3
[48] Jeongwan Haah, Aram W. Harrow, Zhengfeng Ji, Xiaodi Wu, and Nengkun Yu. Sample-optimal tomography of quantum states. IEEE Trans. Inf. Theory, 63 (9): 5628–5641, 2017. 10.1109/TIT.2017.2719044.
https://doi.org/10.1109/TIT.2017.2719044
[49] Yenjo Han, Lane A. Hemaspaandra, and Thomas Thierauf. Threshold computation and cryptographic security. SIAM J. Comput., 26 (1): 59–78, 1997. 10.1137/S0097539792240467.
https://doi.org/10.1137/S0097539792240467
[50] Aram W. Harrow and Ashley Montanaro. Testing product states, quantum Merlin-Arthur games and tensor optimization. J. ACM, 60 (1): 3:1–3:43, 2013. 10.1145/2432622.2432625.
https://doi.org/10.1145/2432622.2432625
[51] Aram W. Harrow, Cedric Yen-Yu Lin, and Ashley Montanaro. Sequential measurements, disturbance and property testing. In Philip N. Klein, editor, Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 1598–1611. SIAM, 2017. 10.1137/1.9781611974782.105.
https://doi.org/10.1137/1.9781611974782.105
[52] Mark Hillery and Erika Andersson. Quantum tests for the linearity and permutation invariance of boolean functions. Phys. Rev. A, 84: 062329, Dec 2011. 10.1103/PhysRevA.84.062329.
https://doi.org/10.1103/PhysRevA.84.062329
[53] Yael Tauman Kalai and Ron D. Rothblum. Arguments of proximity – [extended abstract]. In Rosario Gennaro and Matthew Robshaw, editors, Advances in Cryptology – CRYPTO 2015 – 35th Annual Cryptology Conference, Santa Barbara, CA, USA, August 16-20, 2015, Proceedings, Part II, volume 9216 of Lecture Notes in Computer Science, pages 422–442. Springer, 2015. 10.1007/978-3-662-48000-7_21.
https://doi.org/10.1007/978-3-662-48000-7_21
[54] Subhash Khot, Dor Minzer, and Muli Safra. On monotonicity testing and boolean isoperimetric-type theorems. SIAM J. Comput., 47 (6): 2238–2276, 2018. 10.1137/16M1065872.
https://doi.org/10.1137/16M1065872
[55] Leonid A. Levin. One-way functions and pseudorandom generators. Comb., 7 (4): 357–363, 1987. 10.1007/BF02579323.
https://doi.org/10.1007/BF02579323
[56] Harry Levine, Alexander Keesling, Giulia Semeghini, Ahmed Omran, Tout T. Wang, Sepehr Ebadi, Hannes Bernien, Markus Greiner, Vladan Vuletić, Hannes Pichler, and Mikhail D. Lukin. Parallel implementation of high-fidelity multiqubit gates with neutral atoms. Phys. Rev. Lett., 123: 170503, Oct 2019. 10.1103/PhysRevLett.123.170503.
https://doi.org/10.1103/PhysRevLett.123.170503
[57] Junyu Liu, Connor T. Hann, and Liang Jiang. Quantum data center: Theories and applications. CoRR, abs/2207.14336, 2022. 10.48550/arXiv.2207.14336.
https://doi.org/10.48550/arXiv.2207.14336
[58] Chris Marriott and John Watrous. Quantum Arthur-Merlin games. Comput. Complex., 14 (2): 122–152, 2005. 10.1007/s00037-005-0194-x.
https://doi.org/10.1007/s00037-005-0194-x
[59] C. Monroe, R. Raussendorf, A. Ruthven, K. R. Brown, P. Maunz, L.-M. Duan, and J. Kim. Large-scale modular quantum-computer architecture with atomic memory and photonic interconnects. Phys. Rev. A, 89: 022317, Feb 2014. 10.1103/PhysRevA.89.022317.
https://doi.org/10.1103/PhysRevA.89.022317
[60] Ashley Montanaro and Ronald de Wolf. A survey of quantum property testing. Theory Comput., 7: 1–81, 2016. 10.4086/toc.gs.2016.007.
https://doi.org/10.4086/toc.gs.2016.007
[61] Anand Natarajan and Thomas Vidick. A quantum linearity test for robustly verifying entanglement. In Hamed Hatami, Pierre McKenzie, and Valerie King, editors, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 1003–1015. ACM, 2017. 10.1145/3055399.3055468.
https://doi.org/10.1145/3055399.3055468
[62] Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information (10th Anniversary edition). Cambridge University Press, 2016. ISBN 978-1-10-700217-3. 10.1017/CBO9780511976667.
https://doi.org/10.1017/CBO9780511976667
[63] Ryan O’Donnell and Rocco A. Servedio. New degree bounds for polynomial threshold functions. In Lawrence L. Larmore and Michel X. Goemans, editors, Proceedings of the 35th Annual ACM Symposium on Theory of Computing, June 9-11, 2003, San Diego, CA, USA, pages 325–334. ACM, 2003. 10.1145/780542.780592.
https://doi.org/10.1145/780542.780592
[64] Ryan O’Donnell and John Wright. Quantum spectrum testing. In Rocco A. Servedio and Ronitt Rubinfeld, editors, Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, pages 529–538. ACM, 2015. 10.1145/2746539.2746582.
https://doi.org/10.1145/2746539.2746582
[65] Ryan O’Donnell and John Wright. Efficient quantum tomography. In Daniel Wichs and Yishay Mansour, editors, Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 899–912. ACM, 2016. 10.1145/2897518.2897544.
https://doi.org/10.1145/2897518.2897544
[66] Vern Paulsen. Completely Bounded Maps and Operator Algebras. Cambridge University Press, 2003. 10.1017/CBO9780511546631.
https://doi.org/10.1017/CBO9780511546631
[67] Ran Raz and Amir Shpilka. On the power of quantum proofs. In 19th Annual IEEE Conference on Computational Complexity (CCC 2004), 21-24 June 2004, Amherst, MA, USA, pages 260–274. IEEE Computer Society, 2004. 10.1109/CCC.2004.1313849.
https://doi.org/10.1109/CCC.2004.1313849
[68] A A Razborov. Quantum communication complexity of symmetric predicates. Izvestiya: Mathematics, 67 (1): 145–159, Feb 2003. ISSN 1468-4810. 10.1070/im2003v067n01abeh000422.
https://doi.org/10.1070/im2003v067n01abeh000422
[69] Omer Reingold, Guy N. Rothblum, and Ron D. Rothblum. Constant-round interactive proofs for delegating computation. SIAM J. Comput., 50 (3), 2021. 10.1137/16M1096773.
https://doi.org/10.1137/16M1096773
[70] Marc Olivier Renou, Jędrzej Kaniewski, and Nicolas Brunner. Self-testing entangled measurements in quantum networks. Phys. Rev. Lett., 121: 250507, Dec 2018. 10.1103/PhysRevLett.121.250507.
https://doi.org/10.1103/PhysRevLett.121.250507
[71] Guy N. Rothblum and Ron D. Rothblum. Batch verification and proofs of proximity with polylog overhead. In Rafael Pass and Krzysztof Pietrzak, editors, Theory of Cryptography – 18th International Conference, TCC 2020, Durham, NC, USA, November 16-19, 2020, Proceedings, Part II, volume 12551 of Lecture Notes in Computer Science, pages 108–138. Springer, 2020. 10.1007/978-3-030-64378-2_5.
https://doi.org/10.1007/978-3-030-64378-2_5
[72] Guy N. Rothblum, Salil P. Vadhan, and Avi Wigderson. Interactive proofs of proximity: delegating computation in sublinear time. In Dan Boneh, Tim Roughgarden, and Joan Feigenbaum, editors, Symposium on Theory of Computing Conference, STOC’13, Palo Alto, CA, USA, June 1-4, 2013, pages 793–802. ACM, 2013. 10.1145/2488608.2488709.
https://doi.org/10.1145/2488608.2488709
[73] Alexander A. Sherstov and Justin Thaler. Vanishing-error approximate degree and QMA complexity. CoRR, abs/1909.07498, 2019. 10.48550/arXiv.1909.07498.
https://doi.org/10.48550/arXiv.1909.07498
[74] W. Forrest Stinespring. Positive functions on C*-algebras. Proceedings of the American Mathematical Society, 6 (2): 211–216, 1955. 10.2307/2032342.
https://doi.org/10.2307/2032342
[75] Ivan Šupić and Joseph Bowles. Self-testing of quantum systems: a review. Quantum, 4: 337, 2020. 10.22331/q-2020-09-30-337.
https://doi.org/10.22331/q-2020-09-30-337
[76] Armin Tavakoli, Jędrzej Kaniewski, Tamás Vértesi, Denis Rosset, and Nicolas Brunner. Self-testing quantum states and measurements in the prepare-and-measure scenario. Phys. Rev. A, 98: 062307, Dec 2018. 10.1103/PhysRevA.98.062307.
https://doi.org/10.1103/PhysRevA.98.062307
[77] John Watrous. Quantum computational complexity. In Robert A. Meyers, editor, Encyclopedia of Complexity and Systems Science, pages 7174–7201. Springer, 2009. 10.1007/978-0-387-30440-3_428.
https://doi.org/10.1007/978-0-387-30440-3_428
[78] Stephanie Wehner, David Elkouss, and Ronald Hanson. Quantum internet: A vision for the road ahead. Science, 362 (6412): eaam9288, 2018. 10.1126/science.aam9288.
https://doi.org/10.1126/science.aam9288
Cited by
[1] Adrian She and Henry Yuen, “Unitary property testing lower bounds by polynomials”, arXiv:2210.05885.
The above citations are from SAO/NASA ADS (last updated successfully 2022-10-15 10:36:12). The list may be incomplete as not all publishers provide suitable and complete citation data.
On Crossref’s cited-by service no data on citing works was found (last attempt 2022-10-15 10:36:10).
This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.
