Quantum algorithms for the triangle problem

ABSTRACT

We present two new quantum algorithms that either find a triangle (a copy of K3) in an undirected graph G on n nodes, or reject if G is triangle free. The first algorithm uses combinatorial ideas with Grover Search and makes Õ(n^10/7) queries. The second algorithm uses Õ(n^13/10) queries, and it is based on a new design concept of Ambainis [6] that incorporates the benefits of quantum walks into Grover search [18]. The first algorithm uses only O(log n) qubits in its quantum subroutines, whereas the second one uses O(n) qubits. The Triangle Problem was first treated in [12], where an algorithm with O(n + √n|E|) query complexity was presented (here |E| is the number of edges of G).

REFERENCES

• 1: Scott Aaronson, Quantum lower bound for the collision problem, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509999]
• 2: Dorit Aharonov , Andris Ambainis , Julia Kempe , Umesh Vazirani, Quantum walks on graphs, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.50-59, July 2001, Hersonissos, Greece [doi>10.1145/380752.380758]
• 3: N. Alon, R. Yuster, and U. Zwick. Finding and counting given length cycles. Algorithmica, 17(3):209--223, 1997.
• 4: Andris Ambainis, Quantum lower bounds by quantum arguments, Journal of Computer and System Sciences, v.64 n.4, p.750-767, June 2002 [doi>10.1006/jcss.2002.1826]
• 5: Andris Ambainis, Polynomial Degree vs. Quantum Query Complexity, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.230, October 11-14, 2003
• 6: Andris Ambainis, Quantum Walk Algorithm for Element Distinctness, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.22-31, October 17-19, 2004 [doi>10.1109/FOCS.2004.54]
• 7: Andris Ambainis , Eric Bach , Ashwin Nayak , Ashvin Vishwanath , John Watrous, One-dimensional quantum walks, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.37-49, July 2001, Hersonissos, Greece [doi>10.1145/380752.380757]
• 8: H. Barnum, M. Saks, and M. Szegedy. Quantum decision trees and semidefinite programming. In Proceedings of the 18th IEEE Conference on Computational Complexity, pages 179--193, 2003.
• 9: Robert Beals , Harry Buhrman , Richard Cleve , Michele Mosca , Ronald de Wolf, Quantum lower bounds by polynomials, Journal of the ACM (JACM), v.48 n.4, p.778-797, July 2001 [doi>10.1145/502090.502097]
• 10: G. Brassard, P. Høyer, M. Mosca, and A. Tapp. Quantum amplitude amplification and estimation. In Quantum Computation and Quantum Information: A Millennium Volume, volume 305. AMS Contemporary Mathematics Series, 2002.
• 11: Harry Buhrman , Richard Cleve , Ronald de Wolf , Christof Zalka, Bounds for Small-Error and Zero-Error Quantum Algorithms, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.358, October 17-18, 1999
• 12: Harry Buhrman , Ronald de Wolf , Christoph Dürr , Mark Heiligman , Peter Hyer , Frédéric Magniez , Miklos Santha, Quantum Algorithms for Element Distinctness, Proceedings of the 16th Annual Conference on Computational Complexity, p.131, June 18-21, 2001
• 13: Amit Chakrabarti , Subhash Khot, Improved Lower Bounds on the Randomized Complexity of Graph Properties, Proceedings of the 28th International Colloquium on Automata, Languages and Programming,, p.285-296, July 08-12, 2001
• 14: A. Childs and J. Eisenberg. Quantum algorithms for subset finding. Technical Report quant-ph/0311038, arXiv, 2003.
• 15: D. Deutsch. Quantum theory, the Church-Turing principle and the universal quantum computer. In Proceedings of the Royal Society of London A, volume 400, pages 97--117, 1985.
• 16: D. Deutsch and R. Jozsa. Rapid solution of problems by quantum computation. In Proceedings of the Royal Society A, volume 439, 1992.
• 17: M. Ettinger, P. Høyer, and E. Knill. Hidden subgroup states are almost orthogonal. Technical Report quant-ph/9901034, arXiv, 1999.
• 18: Lov K. Grover, A fast quantum mechanical algorithm for database search, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.212-219, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237866]
• 19: P. Hajnal. An n4/3 lower bound on the randomized complexity of graph properties. Combinatorica, 11:131--143, 1991.
• 20: A. Yu. Kitaev , A. H. Shen , M. N. Vyalyi, Classical and Quantum Computation, American Mathematical Society, Boston, MA, 2002
• 21: Sophie Laplante , Frederic Magniez, Lower Bounds for Randomized and Quantum Query Complexity Using Kolmogorov Arguments, Proceedings of the 19th IEEE Annual Conference on Computational Complexity, p.294-304, June 21-24, 2004 [doi>10.1109/CCC.2004.17]
• 22: Quantum computation and quantum information, Cambridge University Press, New York, NY, 2000
• 23: R. Rivest and J. Vuillemin. On recognizing graph properties from adjacency matrices. Theoretical Computer Science, 3:371--384, 1976.
• 24: Arnold L. Rosenberg, On the time required to recognize properties of graphs: a problem, ACM SIGACT News, v.5 n.4, p.15-16, October 1973 [doi>10.1145/1008299.1008302]
• 25: Yaoyun Shi, Quantum Lower Bounds for the Collision and the Element Distinctness Problems, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.513-519, November 16-19, 2002
• 26: Daniel R. Simon, On the Power of Quantum Computation, SIAM Journal on Computing, v.26 n.5, p.1474-1483, Oct. 1997 [doi>10.1137/S0097539796298637]
• 27: M. Szegedy. On the quantum query complexity of detecting triangles in graphs. Technical Report quant-ph/0310107, arXiv archive, 2003.
• 28: E. Szemerédi. Regular partitions of graphs. Colloques Internationaux du CNRS, 260 -- Problèmes combinatoires et théorie des graphes:399--401, 1976.
• 29: John Watrous, Quantum simulations of classical random walks and undirected graph connectivity, Journal of Computer and System Sciences, v.62 n.2, p.376-391, March 2001 [doi>10.1006/jcss.2000.1732 ]
• 30: A. Yao. Lower bounds to randomized algorithms for graph properties. In Proceedings of 28th IEEE Symposium on Foundations of Computer Science, pages 393--400, 1987.
• 31: A. Yao. Personal communication, 2003.
• 32: S. Zhang. On the power of Ambainis's lower bounds. In Proceedings of 31st International Colloquium on Automata, Languages and Programming, 2004. To appear.