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 algorithmquery complexityquantum walktriangle 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

(83)

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

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)