Quantum Algorithms for the Triangle Problem

DOI10.1137/050643684MaRDI QIDQ5386207zbMATH OpenOpenAlexWikidataFDO

Authors Frédéric Magniez, Miklos Santha, Mario Szegedy

Publication date 22 April 2008

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/quant-ph/0310134

zbMATH Keywords

quantum algorithmquantum walkquery complexitytriangle problem

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Quantum computation (81P68)

Abstract: We present two new quantum algorithms that either find a triangle (a copy of $K_3$) 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 $ildeO(n^{10/7})$ queries. The second algorithm uses $ildeO(n^{13/10})$ queries, and it is based on a design concept of Ambainis~cite{amb04} that incorporates the benefits of quantum walks into Grover search~cite{gro96}. The first algorithm uses only $O(logn)$ qubits in its quantum subroutines, whereas the second one uses O(n) qubits. The Triangle Problem was first treated in~cite{bdhhmsw01}, where an algorithm with $O(n+sqrtnm)$ query complexity was presented, where $m$ is the number of edges of $G$.

Recommendations

• Quantum algorithms for the triangle problem
• Improved quantum query algorithms for triangle finding and associativity testing
• Improved quantum query algorithms for triangle detection and associativity testing

Cited in

(84)

• Claw finding algorithms using quantum walk
• Quantum field as a quantum cellular automaton: the Dirac free evolution in one dimension
• Equivalence of Szegedy's and coined quantum walks
• Quantum algorithm design: techniques and applications
• Two quantum coins sharing a walker
• Quantum walks: a comprehensive review
• Applied quantum physics for novel quantum computation approaches: an update
• Quantum search with variable times
• Constructing quantum hash functions based on quantum walks on Johnson graphs
• Element distinctness revisited
• A quantum searching model finding one of the edges of a subgraph in a complete graph
• Faster search of clustered marked states with lackadaisical quantum walks
• Randomizing quantum walk
• Fooling views: a new lower bound technique for distributed computations under congestion
• Quantum search algorithm for exceptional vertexes in regular graphs and its circuit implementation
• Extended learning graphs for triangle finding
• Hash function based on quantum walks
• Quantum walks for the determination of commutativity of finite dimensional algebras
• On the hitting times of quantum versus random walks
• Quantum walks can find a marked element on any graph
• The staggered quantum walk model
• Quantum walk and its application domains: a systematic review
• Szegedy quantum walks with memory on regular graphs
• Overview: recent development and applications of reduction and lackadaisicalness techniques for spatial search quantum walk in the near term
• Three-state quantum walk on the Cayley graph of the dihedral group
• Novel two-party quantum private comparison via quantum walks on circle
• Quantum search of matching on signed graphs
• Quantum meets fine-grained complexity: sublinear time quantum algorithms for string problems
• Quantum query complexity of constant-sized subgraph containment
• Establishing the equivalence between Szegedy's and coined quantum walks using the staggered model
• Quantum algorithms for the triangle problem
• Quantum complexity of Boolean matrix multiplication and related problems
• Adjacent vertices can be hard to find by quantum walks
• Path-integral solution of the one-dimensional Dirac quantum cellular automaton
• Quantum algorithms for algebraic problems
• Quantum property testing for bounded-degree graphs
• Generating reversible circuits from higher-order functional programs
• Quantum Walk Based Search Algorithms
• A panoply of quantum algorithms
• Path-sum solution of the Weyl quantum walk in 3+1 dimensions
• Solving Lyapunov equation by quantum algorithm
• Limiting properties of stochastic quantum walks on directed graphs
• Multiparty quantum communication complexity of triangle finding
• On the power of non-adaptive learning graphs
• Quantum Chebyshev's Inequality and Applications
• Improved quantum query algorithms for triangle detection and associativity testing
• The polynomial method strikes back: tight quantum query bounds via dual polynomials
• Symmetries of the Dirac quantum walk and emergence of the De Sitter group
• One-dimensional quantum walks with a position-dependent coin
• Connecting coined quantum walks with Szegedy's model
• Quantum state transfer on unsymmetrical graphs via discrete-time quantum walk
• Span programs for functions with constant-sized 1-certificates (extended abstract)
• Quantum Random Walks – New Method for Designing Quantum Algorithms
• Quantum Walks with Multiple or Moving Marked Locations
• Improved quantum query algorithms for triangle finding and associativity testing
• Improved output-sensitive quantum algorithms for Boolean matrix multiplication
• Optimizing the walk coin in the quantum random walk search algorithm
• Improvement of quantum walks search algorithm in single-marked vertex graph
• A high-fidelity quantum state transfer algorithm on the complete bipartite graph
• Quantum algorithm for lexicographically minimal string rotation
• Discrete-time semiclassical Szegedy quantum walks
• The Witten index for one-dimensional split-step quantum walks under the non-Fredholm condition
• Near-optimal quantum algorithms for string problems
• The hitting time of quantum walk on 2D lattice
• Search algorithm on strongly regular graph by lackadaisical quantum walk
• Quantum walks as thermalisations, with application to fullerene graphs
• Robustness of quantum walk search with neighbors measurement
• Exponential decay property for eigenfunctions of quantum walks
• Recovering the original simplicity: succinct and exact quantum algorithm for the welded tree problem
• Symmetries, graph properties, and quantum speedups
• Quantum data structure for range minimum query
• Efficient preparation method for arbitrary multiqubit states based on quantum walk
• Unbounded quantum-classical separation in sample complexity for sphere center finding
• Scaling in the dynamics of directed lackadaisical quantum walks
• Robustness of quantum random walk search with multi-phase matching
• Listing 4-cycles
• Derandomization of quantum algorithm for triangle finding
• Quantum walks advantage on the dihedral group for uniform sampling problem
• Quantum counterfeit coin problems
• A unified framework of quantum walk search
• Parameterized quantum query algorithms for graph problems
• A new quantum lower bound method, with applications to direct product theorems and time-space tradeoffs
• Weyl, Dirac and Maxwell quantum cellular automata
• Quantum algorithms for finding constant-sized sub-hypergraphs

This page was built for publication: Quantum Algorithms for the Triangle Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5386207)