Span-Program-Based Quantum Algorithms for Graph Bipartiteness and Connectivity

详细信息    查看全文

• 刊名：Lecture Notes in Computer Science
• 出版年：2016
• 出版时间：2016
• 年：2016
• 卷：9548
• 期：1
• 页码：35-41
• 全文大小：156 KB
• 参考文献：1.Ambainis, A., Balodis, K., Iraids, J., Ozols, R., Smotrovs, J.: Parameterized quantum query complexity of graph collision. CoRR abs/1305.1021 (2013). http://​arxiv.​org/​abs/​1305.​1021
  2.Belovs, A.: Span-program-based quantum algorithm for the rank problem. CoRR abs/1103.0842 (2011). http://​arxiv.​org/​abs/​1103.​0842
  3.Belovs, A.: Learning-graph-based quantum algorithm for k-distinctness. In: IEEE 53rd Annual Symposium on Foundations of Computer Science (FOCS), pp. 207–216. IEEE (2012). http://​ieeexplore.​ieee.​org/​xpls/​abs_​all.​jsp?​arnumber=​6375298
  4.Belovs, A.: Span programs for functions with constant-sized 1-certificates. In: Proceedings of the 44th Symposium on Theory of Computing, pp. 77–84. ACM (2012). http://​dl.​acm.​org/​citation.​cfm?​id=​2213985
  5.Belovs, A., Reichardt, B.W.: Span programs and quantum algorithms for st-connectivity and claw detection. In: Epstein, L., Ferragina, P. (eds.) ESA 2012. LNCS, vol. 7501, pp. 193–204. Springer, Heidelberg (2012). http://​dx.​doi.​org/​10.​1007/​978-3-642-33090-2_​18 CrossRef
  6.Berzina, A., Dubrovsky, A., Freivalds, R., Lace, L., Scegulnaja, O.: Quantum query complexity for some graph problems. In: Van Emde Boas, P., Pokorný, J., Bieliková, M., Štuller, J. (eds.) SOFSEM 2004. LNCS, vol. 2932, pp. 140–150. Springer, Heidelberg (2004). http://​dx.​doi.​org/​10.​1007/​978-3-540-24618-3_​11 CrossRef
  7.Dürr, C., Heiligman, M., Høyer, P., Mhalla, M.: Quantum query complexity of some graph problems. In: Díaz, J., Karhumäki, J., Lepistö, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol. 3142, pp. 481–493. Springer, Heidelberg (2004). http://​dx.​doi.​org/​10.​1007/​978-3-540-27836-8_​42 CrossRef
  8.Furrow, B.: A panoply of quantum algorithms. Quantum Info. Comput. 8(8), 834–859 (2008). http://​dl.​acm.​org/​citation.​cfm?​id=​2017011.​2017022 MathSciNet MATH
  9.Karchmer, M., Wigderson, A.: On span programs. In: Proceedings of the Eighth Annual Structure in Complexity Theory Conference, pp. 102–111. IEEE (1993). http://​ieeexplore.​ieee.​org/​xpls/​abs_​all.​jsp?​arnumber=​336536
  10.Reichardt, B.W.: Span programs and quantum query complexity: the general adversary bound is nearly tight for every boolean function. In: 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 544–551. IEEE (2009). http://​ieeexplore.​ieee.​org/​xpls/​abs_​all.​jsp?​arnumber=​5438598
  11.Reichardt, B.W.: Reflections for quantum query algorithms. In: Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 560–569. SIAM (2011). http://​dl.​acm.​org/​citation.​cfm?​id=​2133080
  12.Reichardt, B.W., Spalek, R.: Span-program-based quantum algorithm for evaluating formulas. In: Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, STOC 2008, pp. 103–112. ACM, New York (2008). http://​doi.​acm.​org/​10.​1145/​1374376.​1374394
  
• 作者单位：Agnis Āriņš (15)
  
  15. University of Latvia, Raiņa Bulvāris 19, Riga, 1586, Latvia
  
• 丛书名：Mathematical and Engineering Methods in Computer Science
• ISBN：978-3-319-29817-7
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349

文摘

Span program is a linear-algebraic model of computation which can be used to design quantum algorithms. For any Boolean function there exists a span program that leads to a quantum algorithm with optimal quantum query complexity. In general, finding such span programs is not an easy task.