Quantum Algorithms for the Triangle Problem

2003/10/21 by Magniez, Frederic, Santha, Miklos, Szegedy, Mario · 6 citations
#FOS: Physical sciences #Quantum Physics (quant-ph)

paper · doi:10.48550/arxiv.quant-ph/0310134

Abstract

We present two new quantum algorithms that either find a triangle (a copy of K₃) 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 O(n^10/7) queries. The second algorithm uses O(n^13/10) queries, and it is based on a design concept of Ambainis~\citeamb04 that incorporates the benefits of quantum walks into Grover search~\citegro96. 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~\citebdhhmsw01, where an algorithm with O(n+√(nm)) query complexity was presented, where m is the number of edges of G.

Cited by

• Direct Equivalence between Dynamics of Quantum Walks and Coupled Classical Oscillators
• Limitation of Quantum Walk Approach to the Maximum Matching Problem
• A hybrid quantum walk model unifying discrete and continuous quantum walks
• Compositional Quantum Control Flow with Efficient Compilation in Qunity
• Quantum Walks on Arbitrary Spatial Networks with Rydberg Atoms
• Deterministic quantum search on all Laplacian integral graphs

Related

• On the Quantum Query Complexity of Detecting Triangles in Graphs
• Extended Learning Graphs for Triangle Finding
• Improved Quantum Query Algorithms for Triangle Finding and Associativity Testing
• Matching Triangles and Triangle Collection: Hardness based on a Weak Quantum Conjecture
• Hiding, Shuffling, and Cycle Finding: Quantum Algorithms on Edge Lists