Span-Program-Based Quantum Algorithm for Evaluating Formulas
by Ben Reichardt and Robert Špalek
Theory of Computing, Volume 8(13), pp. 291-319, 2012
Bibliography with links to cited articles
[1] Eric Allender, Robert Beals, and Mitsunori Ogihara: The complexity of matrix rank and feasible systems of linear equations. Comput. Complexity, 8(2):99–126, 1999. Preliminary version in STOC’96. [doi:10.1007/s000370050023]
[2] Kazuyuki Amano: Bounding the randomized decision tree complexity of read-once boolean functions. In Proc. 22nd Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’11), pp. 1729–1744. ACM Press, 2011. [ACM:2133169]
[3] Andris Ambainis: Polynomial degree vs. quantum query complexity. J. Comput. System Sci., 72(2):220–238, 2006. Preliminary version in FOCS’03. [doi:10.1016/j.jcss.2005.06.006, arXiv:quant-ph/0305028]
[4] Andris Ambainis, Andrew M. Childs, Ben W. Reichardt, Robert Špalek, and Shengyu Zhang: Any AND-OR formula of size N can be evaluated in time N1∕2+o(1) on a quantum computer. SIAM J. Comput., 39(6):2513–2530, 2010. Preliminary version in FOCS’07. [doi:10.1137/080712167]
[5] László Babai, Anna Gál, and Avi Wigderson: Superpolynomial lower bounds for monotone span programs. Combinatorica, 19(3):301–319, 1999. Preliminary version in STOC’96. [doi:10.1007/s004930050058]
[6] Howard Barnum and Michael Saks: A lower bound on the quantum query complexity of read-once functions. J. Comput. System Sci., 69(2):244–258, 2004. [doi:10.1016/j.jcss.2004.02.002, arXiv:quant-ph/0201007]
[7] Howard Barnum, Michael Saks, and Mario Szegedy: Quantum query complexity and semi-definite programming. In Proc. 18th IEEE Conf. on Computational Complexity (CCC’03), pp. 179–193. IEEE Comp. Soc. Press, 2003. [doi:10.1109/CCC.2003.1214419]
[8] Amos Beimel, Anna Gál, and Mike Paterson: Lower bounds for monotone span programs. Comput. Complexity, 6(1):29–45, 1996. Preliminary version in FOCS’95. [doi:10.1007/BF01202040]
[9] Aleksandrs Belovs: Span-program-based quantum algorithm for the rank problem. Technical report, 2011. [arXiv:1103.0842]
[10] Aleksandrs Belovs: Span programs for functions with constant-sized 1-certificates: extended abstract. In Proc. 44th STOC. ACM Press, 2012. [doi:10.1145/2213977.2213985, arXiv:quant-ph/0611054]
[11] Aleksandrs Belovs and Troy Lee: Quantum algorithm for k-distinctness with prior knowledge on the input. Technical report, 2011. [arXiv:1108.3022]
[12] Aleksandrs Belovs and Ben W. Reichardt: Span programs and quantum algorithms for st-connectivity and claw detection. Technical report, 2012. [arXiv:1203.2603]
[13] Maria Luisa Bonet and Samuel R. Buss: Size-depth tradeoffs for Boolean formulae. Inform. Process. Lett., 49(3):151–155, 1994. [doi:10.1016/0020-0190(94)90093-0]
[14] Nader H. Bshouty, Richard Cleve, and Wayne Eberly: Size-depth tradeoffs for algebraic formulas. SIAM J. Comput., 24(4):682–705, 1995. Preliminary version in FOCS’91. [doi:10.1137/S0097539792232586]
[15] Andrew M. Childs, Richard Cleve, Stephen P. Jordan, and David L. Yonge-Mallo: Discrete-query quantum algorithm for NAND trees. Theory of Computing, 5(1):119–123, 2009. [doi:10.4086/toc.2009.v005a005]
[16] Ronald Cramer and Serge Fehr: Optimal black-box secret sharing over arbitrary abelian groups. In 22nd Ann. Internat. Cryptology Conf. (CRYPTO’02), pp. 272–287. Springer, 2002. [doi:10.1007/3-540-45708-9_18]
[17] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann: A quantum algorithm for the Hamiltonian NAND tree. Theory of Computing, 4(1):169–190, 2008. [doi:10.4086/toc.2008.v004a008]
[18] Dmitry Gavinsky and Tsuyoshi Ito: A quantum query algorithm for the graph collision problem. Technical report, 2012. [arXiv:1204.1527]
[19] Gene H. Golub and Charles F. Van Loan: Matrix Computations. Johns Hopkins, Baltimore, 3rd edition, 1996.
[20] 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]
[21] Lov K. Grover: Tradeoffs in the quantum search algorithm. Phys. Rev. A, 66:052314, 2002. [doi:10.1103/PhysRevA.66.052314, arXiv:quant-ph/0201152]
[22] Rafi Heiman and Avi Wigderson: Randomized vs. deterministic decision tree complexity for read-once Boolean functions. Comput. Complexity, 1:311–329, 1991. Preliminary version in Structure in Complexity Theory’91. [doi:10.1007/BF01212962]
[23] Peter Høyer, Troy Lee, and Robert Špalek: Source codes of semidefinite programs for ADV±. [Link], 2006.
[24] Peter Høyer, Troy Lee, and Robert Špalek: Negative weights make adversaries stronger. In Proc. 39th STOC, pp. 526–535. ACM Press, 2007. [doi:10.1145/1250790.1250867, arXiv:quant-ph/0611054]
[25] T. S. Jayram, Ravi Kumar, and D. Sivakumar: Two applications of information complexity. In Proc. 35th STOC, pp. 673–682. ACM Press, 2003. [doi:10.1145/780542.780640]
[26] Mauricio Karchmer and Avi Wigderson: On span programs. In Proc. 8th IEEE Conf. on Structure in Complexity Theory, pp. 102–111. IEEE Comp. Soc. Press, 1993. [doi:10.1109/SCT.1993.336536]
[27] Shelby Kimmel: Quantum adversary (upper) bound. Technical report, 2011. [arXiv:1101.0797]
[28] A. Yu. Kitaev: Quantum measurements and the Abelian stabilizer problem. Technical report, 1995. [arXiv:quant-ph/9511026]
[29] Troy Lee, Frédéric Magniez, and Miklos Santha: A learning graph based quantum query algorithm for finding constant-size subgraphs. Technical report, 2011. [arXiv:1109.5135]
[30] Troy Lee, Rajat Mittal, Ben W. Reichardt, Robert Špalek, 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]
[31] Frédéric Magniez, Ashwin Nayak, Miklos Santha, and David Xiao: Improved bounds for the randomized decision tree complexity of recursive majority. In Proc. 38th Internat. Colloq. on Automata, Languages and Programming (ICALP’11), pp. 317–329. Springer, 2011. [doi:10.1007/978-3-642-22006-7_27]
[32] Daniel Nagaj, Pawel Wocjan, and Yong Zhang: Fast amplification of QMA. Quantum Inf. Comput., 9(11):1053–1068, 2011. [ACM:2012106, arXiv:0904.1549]
[33] Michael A. Nielsen and Isaac L. Chuang: Quantum computation and quantum information. Cambridge University Press, Cambridge, 2000.
[34] Ventzislav Nikov, Svetla Nikova, and Bart Preneel: On the size of monotone span programs. In 4th Internat. Conf. on Security in Communication Networks (SCN’04), pp. 249–262. Springer, 2004. [doi:10.1007/978-3-540-30598-9_18]
[35] Ben W. Reichardt: Span programs and quantum query complexity: The general adversary bound is nearly tight for every boolean function (70 pp.). Technical report, 2009. Extended abstract in FOCS’09. [arXiv:0904.2759]
[36] Ben Reichardt: Faster quantum algorithm for evaluating game trees. In Proc. 22nd Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’11), pp. 546–559. ACM Press, 2011. [ACM:2133079, arXiv:0907.1623]
[37] Ben Reichardt: Reflections for quantum query algorithms. In Proc. 22nd Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’11), pp. 560–569. ACM Press, 2011. [ACM:2133080, arXiv:1005.1601]
[38] Ben W. Reichardt: Span-program-based quantum algorithm for evaluating unbalanced formulas. 6th Conf. Theory of Quantum Computation, Communication and Cryptography (TQC), 2011. [arXiv:0907.1622]
[39] Ben W. Reichardt and Robert Špalek: Span-program-based quantum algorithm for evaluating formulas. In Proc. 40th STOC, pp. 103–112. ACM Press, 2008. [doi:10.1145/1374376.1374394, arXiv:0710.2630v3]
[40] Michael E. Saks and Avi Wigderson: Probabilistic Boolean decision trees and the complexity of evaluating game trees. In Proc. 27th FOCS, pp. 29–38. IEEE Comp. Soc. Press, 1986. [doi:10.1109/SFCS.1986.44]
[41] Miklos Santha: On the Monte Carlo boolean decision tree complexity of read-once formulae. Random Structures Algorithms, 6(1):75–88, 1995. Preliminary version in Structure in Complexity Theory’91. [doi:10.1002/rsa.3240060108]
[42] Marc Snir: Lower bounds on probabilistic linear decision trees. Theoret. Comput. Sci., 38:69–82, 1985. [doi:10.1016/0304-3975(85)90210-5]
[43] Mario Szegedy: Quantum speed-up of Markov chain based algorithms. In Proc. 45th FOCS, pp. 32–41. IEEE Comp. Soc. Press, 2004. [doi:10.1109/FOCS.2004.53, arXiv:quant-ph/0401053]
[44] Bohua Zhan, Shelby Kimmel, and Avinatan Hassidim: Super-polynomial quantum speed-ups for boolean evaluation trees with hidden structure. In Innovations in Theoretical Computer Science 2012 (ITCM’12), pp. 249–265. ACM Press, 2012. [doi:10.1145/2090236.2090258, arXiv:1101.0796]
[45] Yechao Zhu: Quantum query complexity of subgraph containment with constant-sized certificates. Technical report, 2011. [arXiv:1109.4165]