Eliminating intermediate measurements in space-bounded quantum computation. (English) Zbl 07765253
Khuller, Samir (ed.) et al., Proceedings of the 53rd annual ACM SIGACT symposium on theory of computing, STOC ’21, virtual, Italy, June 21–25, 2021. New York, NY: Association for Computing Machinery (ACM). 1343-1356 (2021).
MSC:
| 68Qxx | Theory of computing |
Keywords:
algorithms for linear algebra; approximation algorithms; quantum computation; space complexityReferences:
| [1] | Scott Aaronson. 2009. ON PERFECT COMPLETENESS FOR QMA. Quantum Information and Computation, 9, 1, 2009. Pages 0081-0089. · Zbl 1160.81320 |
| [2] | Dorit Aharonov, Alexei Kitaev, and Noam Nisan. 1998. Quantum circuits with mixed states. In Proceedings of the thirtieth annual ACM symposium on Theory of computing. Pages 20-30. · Zbl 1028.68054 |
| [3] | Dorit Aharonov and Tomer Naveh. 2002. Quantum NP-a survey. arXiv preprint quant-ph/0210077, 2002. |
| [4] | Eric Allender and Mitsunori Ogihara. 1996. Relationships Among PL, #L, and the Determinant. RAIRO-Theoretical Informatics and Applications, 30, 1, 1996. Pages 1-21. · Zbl 0851.68033 |
| [5] | Charles H Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani. 1997. Strengths and weaknesses of quantum computing. SIAM journal on Computing, 26, 5, 1997. Pages 1510-1523. · Zbl 0895.68044 |
| [6] | Stuart J Berkowitz. 1984. On computing the determinant in small parallel time using a small number of processors. Information processing letters, 18, 3, 1984. Pages 147-150. · Zbl 0541.68019 |
| [7] | Dominic W Berry, Andrew M Childs, Richard Cleve, Robin Kothari, and Rolando D Somma. 2014. Exponential improvement in precision for simulating sparse Hamiltonians. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing. Pages 283-292. · Zbl 1315.68133 |
| [8] | Enric Boix-Adser\`a, Lior Eldar, and Saeed Mehraban. 2019. Approximating the Determinant of Well-Conditioned Matrices by Shallow Circuits. arXiv preprint arXiv:1912.03824, 2019. |
| [9] | Sergey Bravyi. 2011. Efficient algorithm for a quantum analogue of 2-SAT. Contemp. Math., 536, 2011. Pages 33-48. · Zbl 1218.81032 |
| [10] | Harry Buhrman, John Tromp, and Paul Vitányi. 2001. Time and space bounds for reversible simulation. In International Colloquium on Automata, Languages, and Programming. Pages 1017-1027. · Zbl 0986.68512 |
| [11] | Andrew M Childs. 2010. On the relationship between continuous-and discrete-time quantum walk. Communications in Mathematical Physics, 294, 2, 2010. Pages 581-603. · Zbl 1207.81029 |
| [12] | Stephen A Cook. 1985. A taxonomy of problems with fast parallel algorithms. Information and Control, 64, 1-3, 1985. Pages 2-22. · Zbl 0575.68045 |
| [13] | C Damm. 1991. DET=L(#L). Fachbereich Informatik der Humboldt-Universitat zu, Berlin, 1991. |
| [14] | David P DiVincenzo. 2000. The physical implementation of quantum computation. Fortschritte der Physik: Progress of Physics, 48, 9-11, 2000. Pages 771-783. · Zbl 1071.81510 |
| [15] | Dean Doron, Amir Sarid, and Amnon Ta-Shma. 2017. On approximating the eigenvalues of stochastic matrices in probabilistic logspace. computational complexity, 26, 2, 2017. Pages 393-420. · Zbl 1378.68049 |
| [16] | Dean Doron and Amnon Ta-Shma. 2015. On the de-randomization of space-bounded approximate counting problems. Inform. Process. Lett., 115, 10, 2015. Pages 750-753. · Zbl 1329.68287 |
| [17] | Bill Fefferman, Hirotada Kobayashi, Cedric Yen-Yu Lin, Tomoyuki Morimae, and Harumichi Nishimura. 2016. Space-Efficient Error Reduction for Unitary Quantum Computations. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). · Zbl 1388.68067 |
| [18] | Bill Fefferman and Cedric Yen-Yu Lin. 2018. A Complete Characterization of Unitary Quantum Space. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). |
| [19] | Bill Fefferman and Zachary Remscrim. 2020. Eliminating intermediate measurements in space-bounded quantum computation. arXiv preprint arXiv:2006.03530, 2020. |
| [20] | Richard P Feynman. 1999. Simulating physics with computers. Int. J. Theor. Phys, 21, 6/7, 1999. |
| [21] | Uma Girish, Ran Raz, and Wei Zhan. 2020. Quantum logspace algorithm for powering matrices with bounded norm. arXiv preprint arXiv:2006.04880, 2020. |
| [22] | Aram W Harrow, Avinatan Hassidim, and Seth Lloyd. 2009. Quantum algorithm for linear systems of equations. Physical review letters, 103, 15, 2009. Pages 150502. |
| [23] | Mark Jerrum, Alistair Sinclair, and Eric Vigoda. 2004. A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries. Journal of the ACM (JACM), 51, 4, 2004. Pages 671-697. · Zbl 1204.65044 |
| [24] | Stephen P Jordan, Hirotada Kobayashi, Daniel Nagaj, and Harumichi Nishimura. 2012. Achieving perfect completeness in classical-witness quantum Merlin-Arthur proof systems. Quantum Information & Computation, 12, 5-6, 2012. Pages 461-471. · Zbl 1260.81019 |
| [25] | Richard Jozsa, Barbara Kraus, Akimasa Miyake, and John Watrous. 2010. Matchgate and space-bounded quantum computations are equivalent. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 466, 2115, 2010. Pages 809-830. · Zbl 1195.81034 |
| [26] | Aleksei Yur’evich Kitaev. 1997. Quantum computations: algorithms and error correction. Uspekhi Matematicheskikh Nauk, 52, 6, 1997. Pages 53-112. · Zbl 0917.68063 |
| [27] | Hirotada Kobayashi, Keiji Matsumoto, and Tomoyuki Yamakami. 2003. Quantum Merlin-Arthur proof systems: Are multiple Merlins more helpful to Arthur? In International Symposium on Algorithms and Computation. Pages 189-198. · Zbl 1205.68159 |
| [28] | Rolf Landauer. 1961. Irreversibility and heat generation in the computing process. IBM journal of research and development, 5, 3, 1961. Pages 183-191. · Zbl 1160.68305 |
| [29] | Klaus-Jörn Lange, Pierre McKenzie, and Alain Tapp. 2000. Reversible space equals deterministic space. J. Comput. System Sci., 60, 2, 2000. Pages 354-367. · Zbl 0956.68057 |
| [30] | Seth Lloyd. 1996. Universal quantum simulators. Science, 1996. Pages 1073-1078. · Zbl 1226.81059 |
| [31] | Meena Mahajan and V Vinay. 1997. Determinant: Combinatorics, Algorithms, and Complexity. Chicago Journal of Theoretical Computer Science, 1997. · Zbl 0924.68088 |
| [32] | Chris Marriott and John Watrous. 2005. Quantum Arthur-Merlin games. Computational Complexity, 14, 2, 2005. Pages 122-152. · Zbl 1085.68052 |
| [33] | Dieter van Melkebeek and Thomas Watson. 2012. Time-space efficient simulations of quantum computations. Theory of Computing, 8, 1, 2012. Pages 1-51. · Zbl 1253.68136 |
| [34] | Daniel Nagaj, Pawel Wocjan, and Yong Zhang. 2009. Fast amplification of QMA. Quantum Information & Computation, 9, 11, 2009. Pages 1053-1068. · Zbl 1183.81040 |
| [35] | Michael A Nielsen and Isaac Chuang. 2002. Quantum computation and quantum information. |
| [36] | Noam Nisan. 1992. Pseudorandom generators for space-bounded computation. Combinatorica, 12, 4, 1992. Pages 449-461. · Zbl 0759.68024 |
| [37] | Simon Perdrix and Philippe Jorrand. 2006. Classically controlled quantum computation. Mathematical Structures in Computer Science, 16, 4, 2006. Pages 601-620. · Zbl 1122.68061 |
| [38] | Zachary Remscrim. 2020. The Power of a Single Qubit: Two-Way Quantum Finite Automata and the Word Problem. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs). 168, Pages 139:1-139:18. |
| [39] | Zachary Remscrim. 2021. Lower Bounds on the Running Time of Two-Way Quantum Finite Automata and Sublogarithmic-Space Quantum Turing Machines. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). |
| [40] | Wojciech Roga, Zbigniew Puchala, Lukasz Rudnicki, and Karol Zyczkowski. 2013. Entropic trade-off relations for quantum operations. Physical Review A, 87, 3, 2013. Pages 032308. |
| [41] | Michael Saks. 1996. Randomization and derandomization in space-bounded computation. In Proceedings of Computational Complexity (Formerly Structure in Complexity Theory). Pages 128-149. |
| [42] | Michael Saks and Shiyu Zhou. 1999. BPhSPACE(s) in DSPACE(s\^3/2). Journal of computer and system sciences, 58, 2, 1999. Pages 376-403. · Zbl 0922.68083 |
| [43] | Miklos Santha and Sovanna Tan. 1998. Verifying the determinant in parallel. Computational Complexity, 7, 2, 1998. Pages 128-151. · Zbl 0912.68053 |
| [44] | Peter W Shor. 1994. Algorithms for quantum computation: Discrete logarithms and factoring. In Proceedings 35th annual symposium on foundations of computer science. Pages 124-134. |
| [45] | Peter W Shor and Stephen P Jordan. 2008. Estimating Jones polynomials is a complete problem for one clean qubit. Quantum Information & Computation, 8, 8, 2008. Pages 681-714. · Zbl 1236.81069 |
| [46] | Amnon Ta-Shma. 2013. Inverting well conditioned matrices in quantum logspace. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing. Pages 881-890. · Zbl 1293.68129 |
| [47] | Seinosuke Toda. 1991. Counting problems computationally equivalent to the determinant. |
| [48] | Leslie G Valiant. 1992. Why is Boolean complexity theory difficult. Boolean Function Complexity, 169, 1992. Pages 84-94. · Zbl 0769.68050 |
| [49] | V Vinay. 1991. Counting auxiliary pushdown automata and semi-unbounded arithmetic circuits. In Proceedings of the Sixth Annual Structure in Complexity Theory Conference. Pages 270-284. |
| [50] | John Watrous. 1999. Space-bounded quantum complexity. J. Comput. System Sci., 59, 2, 1999. Pages 281-326. · Zbl 0947.68051 |
| [51] | John Watrous. 2001. Quantum simulations of classical random walks and undirected graph connectivity. Journal of computer and system sciences, 62, 2, 2001. Pages 376-391. · Zbl 0990.68519 |
| [52] | John Watrous. 2003. On the complexity of simulating space-bounded quantum computations. Computational Complexity, 12, 1-2, 2003. Pages 48-84. · Zbl 1068.68066 |
| [53] | John Watrous. 2009. Encyclopedia of Complexity and System Science, chapter Quantum computational complexity. |
| [54] | John Watrous. 2009. Zero-knowledge against quantum attacks. SIAM J. Comput., 39, 1, 2009. Pages 25-58. · Zbl 1186.81048 |
| [55] | John Watrous. 2018. The theory of quantum information. Cambridge University Press. · Zbl 1393.81004 |
| [56] | Stathis Zachos and Martin Furer. 1987. Probabilistic quantifiers vs. distrustful adversaries. In International Conference on Foundations of Software Technology and Theoretical Computer Science. Pages 443-455. · Zbl 0647.68052 |
| [57] | Scott Aaronson. 2009. ON PERFECT COMPLETENESS FOR QMA. Quantum Information and Computation, 9, 1, 2009. Pages 0081-0089. · Zbl 1160.81320 |
| [58] | Dorit Aharonov, Alexei Kitaev, and Noam Nisan. 1998. Quantum circuits with mixed states. In Proceedings of the thirtieth annual ACM symposium on Theory of computing. Pages 20-30. · Zbl 1028.68054 |
| [59] | Dorit Aharonov and Tomer Naveh. 2002. Quantum NP-a survey. arXiv preprint quant-ph/0210077, 2002. |
| [60] | Eric Allender and Mitsunori Ogihara. 1996. Relationships Among PL, #L, and the Determinant. RAIRO-Theoretical Informatics and Applications, 30, 1, 1996. Pages 1-21. · Zbl 0851.68033 |
| [61] | Charles H Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani. 1997. Strengths and weaknesses of quantum computing. SIAM journal on Computing, 26, 5, 1997. Pages 1510-1523. · Zbl 0895.68044 |
| [62] | Stuart J Berkowitz. 1984. On computing the determinant in small parallel time using a small number of processors. Information processing letters, 18, 3, 1984. Pages 147-150. · Zbl 0541.68019 |
| [63] | Dominic W Berry, Andrew M Childs, Richard Cleve, Robin Kothari, and Rolando D Somma. 2014. Exponential improvement in precision for simulating sparse Hamiltonians. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing. Pages 283-292. · Zbl 1315.68133 |
| [64] | Enric Boix-Adser\`a, Lior Eldar, and Saeed Mehraban. 2019. Approximating the Determinant of Well-Conditioned Matrices by Shallow Circuits. arXiv preprint arXiv:1912.03824, 2019. |
| [65] | Sergey Bravyi. 2011. Efficient algorithm for a quantum analogue of 2-SAT. Contemp. Math., 536, 2011. Pages 33-48. · Zbl 1218.81032 |
| [66] | Harry Buhrman, John Tromp, and Paul Vitányi. 2001. Time and space bounds for reversible simulation. In International Colloquium on Automata, Languages, and Programming. Pages 1017-1027. · Zbl 0986.68512 |
| [67] | Andrew M Childs. 2010. On the relationship between continuous-and discrete-time quantum walk. Communications in Mathematical Physics, 294, 2, 2010. Pages 581-603. · Zbl 1207.81029 |
| [68] | Stephen A Cook. 1985. A taxonomy of problems with fast parallel algorithms. Information and Control, 64, 1-3, 1985. Pages 2-22. · Zbl 0575.68045 |
| [69] | C Damm. 1991. DET=L(#L). Fachbereich Informatik der Humboldt-Universitat zu, Berlin, 1991. |
| [70] | David P DiVincenzo. 2000. The physical implementation of quantum computation. Fortschritte der Physik: Progress of Physics, 48, 9-11, 2000. Pages 771-783. · Zbl 1071.81510 |
| [71] | Dean Doron, Amir Sarid, and Amnon Ta-Shma. 2017. On approximating the eigenvalues of stochastic matrices in probabilistic logspace. computational complexity, 26, 2, 2017. Pages 393-420. · Zbl 1378.68049 |
| [72] | Dean Doron and Amnon Ta-Shma. 2015. On the de-randomization of space-bounded approximate counting problems. Inform. Process. Lett., 115, 10, 2015. Pages 750-753. · Zbl 1329.68287 |
| [73] | Bill Fefferman, Hirotada Kobayashi, Cedric Yen-Yu Lin, Tomoyuki Morimae, and Harumichi Nishimura. 2016. Space-Efficient Error Reduction for Unitary Quantum Computations. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). · Zbl 1388.68067 |
| [74] | Bill Fefferman and Cedric Yen-Yu Lin. 2018. A Complete Characterization of Unitary Quantum Space. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). |
| [75] | Bill Fefferman and Zachary Remscrim. 2020. Eliminating intermediate measurements in space-bounded quantum computation. arXiv preprint arXiv:2006.03530, 2020. |
| [76] | Richard P Feynman. 1999. Simulating physics with computers. Int. J. Theor. Phys, 21, 6/7, 1999. |
| [77] | Uma Girish, Ran Raz, and Wei Zhan. 2020. Quantum logspace algorithm for powering matrices with bounded norm. arXiv preprint arXiv:2006.04880, 2020. |
| [78] | Aram W Harrow, Avinatan Hassidim, and Seth Lloyd. 2009. Quantum algorithm for linear systems of equations. Physical review letters, 103, 15, 2009. Pages 150502. |
| [79] | Mark Jerrum, Alistair Sinclair, and Eric Vigoda. 2004. A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries. Journal of the ACM (JACM), 51, 4, 2004. Pages 671-697. · Zbl 1204.65044 |
| [80] | Stephen P Jordan, Hirotada Kobayashi, Daniel Nagaj, and Harumichi Nishimura. 2012. Achieving perfect completeness in classical-witness quantum Merlin-Arthur proof systems. Quantum Information & Computation, 12, 5-6, 2012. Pages 461-471. · Zbl 1260.81019 |
| [81] | Richard Jozsa, Barbara Kraus, Akimasa Miyake, and John Watrous. 2010. Matchgate and space-bounded quantum computations are equivalent. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 466, 2115, 2010. Pages 809-830. · Zbl 1195.81034 |
| [82] | Aleksei Yur’evich Kitaev. 1997. Quantum computations: algorithms and error correction. Uspekhi Matematicheskikh Nauk, 52, 6, 1997. Pages 53-112. · Zbl 0917.68063 |
| [83] | Hirotada Kobayashi, Keiji Matsumoto, and Tomoyuki Yamakami. 2003. Quantum Merlin-Arthur proof systems: Are multiple Merlins more helpful to Arthur? In International Symposium on Algorithms and Computation. Pages 189-198. · Zbl 1205.68159 |
| [84] | Rolf Landauer. 1961. Irreversibility and heat generation in the computing process. IBM journal of research and development, 5, 3, 1961. Pages 183-191. · Zbl 1160.68305 |
| [85] | Klaus-Jörn Lange, Pierre McKenzie, and Alain Tapp. 2000. Reversible space equals deterministic space. J. Comput. System Sci., 60, 2, 2000. Pages 354-367. · Zbl 0956.68057 |
| [86] | Seth Lloyd. 1996. Universal quantum simulators. Science, 1996. Pages 1073-1078. · Zbl 1226.81059 |
| [87] | Meena Mahajan and V Vinay. 1997. Determinant: Combinatorics, Algorithms, and Complexity. Chicago Journal of Theoretical Computer Science, 1997. · Zbl 0924.68088 |
| [88] | Chris Marriott and John Watrous. 2005. Quantum Arthur-Merlin games. Computational Complexity, 14, 2, 2005. Pages 122-152. · Zbl 1085.68052 |
| [89] | Dieter van Melkebeek and Thomas Watson. 2012. Time-space efficient simulations of quantum computations. Theory of Computing, 8, 1, 2012. Pages 1-51. · Zbl 1253.68136 |
| [90] | Daniel Nagaj, Pawel Wocjan, and Yong Zhang. 2009. Fast amplification of QMA. Quantum Information & Computation, 9, 11, 2009. Pages 1053-1068. · Zbl 1183.81040 |
| [91] | Michael A Nielsen and Isaac Chuang. 2002. Quantum computation and quantum information. |
| [92] | Noam Nisan. 1992. Pseudorandom generators for space-bounded computation. Combinatorica, 12, 4, 1992. Pages 449-461. · Zbl 0759.68024 |
| [93] | Simon Perdrix and Philippe Jorrand. 2006. Classically controlled quantum computation. Mathematical Structures in Computer Science, 16, 4, 2006. Pages 601-620. · Zbl 1122.68061 |
| [94] | Zachary Remscrim. 2020. The Power of a Single Qubit: Two-Way Quantum Finite Automata and the Word Problem. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs). 168, Pages 139:1-139:18. |
| [95] | Zachary Remscrim. 2021. Lower Bounds on the Running Time of Two-Way Quantum Finite Automata and Sublogarithmic-Space Quantum Turing Machines. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). |
| [96] | Wojciech Roga, Zbigniew Puchala, Lukasz Rudnicki, and Karol Zyczkowski. 2013. Entropic trade-off relations for quantum operations. Physical Review A, 87, 3, 2013. Pages 032308. |
| [97] | Michael Saks. 1996. Randomization and derandomization in space-bounded computation. In Proceedings of Computational Complexity (Formerly Structure in Complexity Theory). Pages 128-149. |
| [98] | Michael Saks and Shiyu Zhou. 1999. BPhSPACE(s) in DSPACE(s\^3/2). Journal of computer and system sciences, 58, 2, 1999. Pages 376-403. · Zbl 0922.68083 |
| [99] | Miklos Santha and Sovanna Tan. 1998. Verifying the determinant in parallel. Computational Complexity, 7, 2, 1998. Pages 128-151. · Zbl 0912.68053 |
| [100] | Peter W Shor. 1994. Algorithms for quantum computation: Discrete logarithms and factoring. In Proceedings 35th annual symposium on foundations of computer science. Pages 124-134. |
| [101] | Peter W Shor and Stephen P Jordan. 2008. Estimating Jones polynomials is a complete problem for one clean qubit. Quantum Information & Computation, 8, 8, 2008. Pages 681-714. · Zbl 1236.81069 |
| [102] | Amnon Ta-Shma. 2013. Inverting well conditioned matrices in quantum logspace. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing. Pages 881-890. · Zbl 1293.68129 |
| [103] | Seinosuke Toda. 1991. Counting problems computationally equivalent to the determinant. |
| [104] | Leslie G Valiant. 1992. Why is Boolean complexity theory difficult. Boolean Function Complexity, 169, 1992. Pages 84-94. · Zbl 0769.68050 |
| [105] | V Vinay. 1991. Counting auxiliary pushdown automata and semi-unbounded arithmetic circuits. In Proceedings of the Sixth Annual Structure in Complexity Theory Conference. Pages 270-284. |
| [106] | John Watrous. 1999. Space-bounded quantum complexity. J. Comput. System Sci., 59, 2, 1999. Pages 281-326. · Zbl 0947.68051 |
| [107] | John Watrous. 2001. Quantum simulations of classical random walks and undirected graph connectivity. Journal of computer and system sciences, 62, 2, 2001. Pages 376-391. · Zbl 0990.68519 |
| [108] | John Watrous. 2003. On the complexity of simulating space-bounded quantum computations. Computational Complexity, 12, 1-2, 2003. Pages 48-84. · Zbl 1068.68066 |
| [109] | John Watrous. 2009. Encyclopedia of Complexity and System Science, chapter Quantum computational complexity. |
| [110] | John Watrous. 2009. Zero-knowledge against quantum attacks. SIAM J. Comput., 39, 1, 2009. Pages 25-58. · Zbl 1186.81048 |
| [111] | John Watrous. 2018. The theory of quantum information. Cambridge University Press. · Zbl 1393.81004 |
| [112] | Stathis Zachos and Martin Furer. 1987. Probabilistic quantifiers vs. distrustful adversaries. In International Conference on Foundations of Software Technology and Theoretical Computer Science. Pages 443-455. · Zbl 0647.68052 |
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.
