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 Yakaryilmaz 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]