Time-Space Efficient Simulations of Quantum Computations
by Dieter van Melkebeek and Thomas Watson
Theory of Computing, Volume 8(1), pp. 1-51, 2012
Bibliography with links to cited articles
[1] Leonard Adleman, Jonathan DeMarrais, and Ming-Deh Huang: Quantum computability. SIAM J. Comput., 26(5):1524–1540, 1997. [doi:10.1137/S0097539795293639]
[2] Eric Allender, Michal Koucký, Detlef Ronneburger, Sambuddha Roy, and V. Vinay: Time-space tradeoffs in the counting hierarchy. In Proceedings of the 16th IEEE Conference on Computational Complexity, pp. 295–302. IEEE Comp. Soc. Press, 2001.
[3] Eric Allender and Mitsunori Ogihara: Relationships among PL, #L, and the determinant. RAIRO – Theoretical Informatics and Applications, 30:1–21, 1996.
[4] Eric Allender and Klaus Wagner: Counting hierarchies: Polynomial time and constant depth circuits. In Grzegorz Rozenberg and Arto Salomaa, editors, Current Trends in Theoretical Computer Science, pp. 469–483. World Scientific, 1993.
[5] Stefan Arnold: Personal communication, November 2010.
[6] Adriano Barenco: A universal two-bit gate for quantum computation. Proc. R. Soc. Lond. Ser. A Math. Phys. Eng. Sci., 449:679–683, 1995. [JSTOR:52687]
[7] Adriano Barenco, Charles Bennett, Richard Cleve, David DiVincenzo, Norman Margolus, Peter Shor, Tycho Sleator, John Smolin, and Harald Weinfurter: Elementary gates for quantum computation. Phys. Rev. A, 52:3457–3467, 1995. [doi:10.1103/PhysRevA.52.3457]
[8] Ethan Bernstein and Umesh Vazirani: Quantum complexity theory. SIAM J. Comput., 26(5):1411–1473, 1997. [doi:10.1137/S0097539796300921]
[9] Patrick Oscar Boykin, Tal Mor, Matthew Pulver, Vwani Roychowdhury, and Farrokh Vatan: A new universal and fault-tolerant quantum basis. Inform. Process. Lett., 75(3):101–107, 2000. [doi:10.1016/S0020-0190(00)00084-3]
[10] J. Chiaverini, J. Britton, D. Leibfried, E. Knill, M. Barrett, R. Blakestad, W. Itano, J. Jost, C. Langer, R. Ozeri, T. Schaetz, and D. Wineland: Implementation of the semiclassical quantum Fourier transform in a scalable system. Science, 308(5724):997–1000, 2005. [doi:10.1126/science.1110335]
[11] Christopher Dawson and Michael Nielsen: The Solovay-Kitaev algorithm. Quantum Inf. Comput., 6(1):81–95, 2006.
[12] David Deutsch: Quantum computational networks. Proc. R. Soc. Lond. Ser. A Math. Phys. Eng. Sci., 425:73–90, 1989. [JSTOR:2398494]
[13] David Deutsch, Adriano Barenco, and Artur Ekert: Universality in quantum computation. Proc. R. Soc. Lond. Ser. A Math. Phys. Eng. Sci., 449:669–677, 1995. [JSTOR:52686]
[14] Scott Diehl and Dieter van Melkebeek: Time-space lower bounds for the polynomial-time hierarchy on randomized machines. SIAM J. Comput., 36(3):563–594, 2006. [doi:10.1137/050642228]
[15] David DiVincenzo: Two-bit gates are universal for quantum computation. Phys. Rev. A, 51:1015–1022, 1995. [doi:10.1103/PhysRevA.51.1015]
[16] David DiVincenzo: The physical implementation of quantum computation. Fortschritte der Physik, 48:771–784, 2000.
[17] Lance Fortnow: Time-space tradeoffs for satisfiability. J. Comput. System Sci., 60(2):337–353, 2000. [doi:10.1006/jcss.1999.1671]
[18] Lance Fortnow, Richard Lipton, Dieter van Melkebeek, and Anastasios Viglas: Time-space lower bounds for satisfiability. J. ACM, 52(6):835–865, 2005. [doi:10.1145/1101821.1101822]
[19] Lance Fortnow and John Rogers: Complexity limitations on quantum computation. J. Comput. System Sci., 59(2):240–252, 1999. [doi:10.1006/jcss.1999.1651]
[20] Gene Golub and Charles Van Loan: Matrix Computations. The Johns Hopkins University Press, third edition, 1996.
[21] Lov Grover: A fast quantum mechanical algorithm for database search. In Proc. 28th STOC, pp. 212–219. ACM Press, 1996. [doi:10.1145/237814.237866]
[22] Aram Harrow, Benjamin Recht, and Isaac Chuang: Efficient discrete approximations of quantum gates. J. Math. Phys., 43(9):4445–4451, 2002. [doi:10.1063/1.1495899]
[23] William Hesse: Division is in uniform TC0. In Proceedings of the 28th International Colloquium On Automata, Languages, and Programming, pp. 104–114. Springer, 2001. [doi:10.1007/3-540-48224-5_9]
[24] Roger Horn and Charles Johnson: Topics in Matrix Analysis. Cambridge University Press, 1994.
[25] Alexei Kitaev: Quantum computations: Algorithms and error correction. Russian Math. Surveys, 52(6):1191–1249, 1997. [doi:10.1070/RM1997v052n06ABEH002155]
[26] Alexei Kitaev, Alexander Shen, and Mikhail Vyalyi: Classical and Quantum Computation. American Mathematical Society, 2002.
[27] Seth Lloyd: Almost any quantum logic gate is universal. Phys. Rev. Lett., 75:346–349, 1995. [doi:10.1103/PhysRevLett.75.346]
[28] M. Mariantoni, H. Wang, T. Yamamoto, M. Neeley, R. Bialczak, Y. Chen, M. Lenander, E. Lucero, A. O’Connell, D. Sank, M. Weides, J. Wenner, Y. Yin, J. Zhao, A. Korotkov, A. Cleland, and J. Martinis: Implementing the quantum von Neumann architecture with superconducting circuits. Science Express, 2011. [doi:10.1126/science.1208517]
[29] Amin Mobasher, Saeed Fathololoumi, and Somayyeh Rahimi: Quantum dot quantum computation. Technical Report 2007-05, University of Waterloo Electrical and Computer Engineering Department, 2007.
[30] Attila Nagy: On an implementation of the Solovay-Kitaev algorithm. CoRR, abs/quant-ph/0606077v1, 2006. [arXiv:quant-ph/0606077v1]
[31] Michael Nielsen and Isaac Chuang: Quantum Computation and Quantum Information. Cambridge University Press, 2000.
[32] Simon Perdrix and Philippe Jorrand: Classically controlled quantum computation. Math. Structures Comput. Sci., 16(4):601–620, 2006. [doi:10.1016/j.entcs.2005.09.026]
[33] Alberto Politi, Jonathan Matthews, and Jeremy O’Brien: Shor’s quantum factoring algorithm on a photonic chip. Science, 325(5945):1221, 2009. [doi:10.1126/science.1173731]
[34] Yaoyun Shi: Both Toffoli and controlled-NOT need little help to do universal quantum computation. Quantum Inf. Comput., 3(1):84–92, 2003.
[35] Peter 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]
[36] Seinosuke Toda: PP is as hard as the polynomial time hierarchy. SIAM J. Comput., 20(5):865–877, 1991. [doi:10.1137/0220053]
[37] Dieter van Melkebeek: A survey of lower bounds for satisfiability and related problems. Found. Trends Theor. Comput. Sci., 2:197–303, 2007. [doi:10.1561/0400000012]
[38] John Watrous: Space-bounded quantum complexity. J. Comput. System Sci., 59(2):281–326, 1999. [doi:10.1006/jcss.1999.1655]
[39] John Watrous: On the complexity of simulating space-bounded quantum computations. Computational Complexity, 12(1-2):48–84, 2003. [doi:10.1007/s00037-003-0177-8]
[40] Ryan Williams: Inductive time-space lower bounds for SAT and related problems. Comput. Complexity, 15(4):433–470, 2006. [doi:10.1007/s00037-007-0221-1]
[41] Ryan Williams: Time-space tradeoffs for counting NP solutions modulo integers. Comput. Complexity, 17(2):179–219, 2008. [doi:10.1007/s00037-008-0248-y]
[42] Howard Wiseman and Gerard Milburn: Quantum Measurement and Control. Cambridge University Press, 2009.
[43] Abuzer Yakarylmaz and A. C. Cem Say: Unbounded-error quantum computation with small space bounds. Inform. and Comput., 209(6):873–892, 2011. [doi:10.1016/j.ic.2011.01.008]